List Decoding of Polar Codes

Ido Tal; Alexander Vardy

Source-linked AI summary

List Decoding of Polar Codes

Ido Tal, Alexander Vardy

arXiv:1206.0050v1May 31, 2012cs.IT

TL;DR

Polar codes perform disappointingly at short to moderate block lengths despite their asymptotic capacity-achieving property. The paper introduces SCL decoding, showing near-ML performance for most-likely-codeword selection and LDPC-comparable performance with a simple genie approximation, using O(L·n log n) time and O(L·n) space.

Problem
Polar codes are capacity-achieving asymptotically, but their performance at short to moderate block lengths is disappointing, potentially because of weak codes, degraded SC decoding, or both.
Method
The paper generalizes SC decoding into SCL decoding by concurrently considering up to L paths, pruning to the most likely paths, and using a CRC-based genie approximation.
Results
Most-likely-codeword selection produces performance very close to ML decoding for moderate L, while the genie-assisted modification yields performance comparable to state-of-the-art LDPC codes.
Takeaways & Limitations
SCL decoding addresses SC-decoder sub-optimality, and the modified polar-code scheme substantially improves error-rate performance within the reported comparisons.

Abstract

from arXiv · show

We describe a successive-cancellation \emph{list} decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arıkan. In the proposed list decoder, up to $L$ decoding paths are considered concurrently at each decoding stage. Then, a single codeword is selected from the list as output. If the most likely codeword is selected, simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of $L$. Alternatively, if a "genie" is allowed to pick the codeword from the list, the results are comparable to the current state of the art LDPC codes. Luckily, implementing such a helpful genie is easy. Our list decoder doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the $L$ "best" paths. %In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, a straightforward implementation still requires $Ω(L \cdot n^2)$ time, which is in stark contrast with the $O(n \log n)$ complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only $O(L \cdot n \log n)$ time and $O(L \cdot n)$ space.

I. INTRODUCTION

Polar codes are capacity-achieving asymptotically but perform disappointingly at short to moderate block lengths. The paper introduces SCL decoding, whose most-likely-path output approaches ML performance, while a genie-assisted variant is comparable to state-of-the-art LDPC codes.

Polar codes combine explicit construction, efficient encoding and decoding, and capacity achievement over binary-input symmetric memoryless channels.
Short- and moderate-length performance is disappointing, potentially because of weak codes, degraded SC decoding, or both.
SCL decoding generalizes SC decoding by maintaining a list of paths, with L = 1 recovering classic SC decoding.
Choosing the most likely codeword from the list yields performance very close to ML decoding over a large range, even for moderate L.
A simple genie-assisted modification makes polar-code performance comparable to state-of-the-art LDPC codes, although some length-2048 rate-1/2 LDPC codes perform better.
The SCL decoder is implemented with O(L·n log n) time, while the paper reduces SC-decoder space complexity from O(n log n) to O(n).

II. FORMALIZATION OF THE SUCCESSIVE CANCELLATION DECODER

The paper formalizes SC decoding by representing the transmitted polar-code information and codeword vectors, the channel, and the received word. Decoding maps the received word to an estimated codeword and information vector.

The SC decoder is recast in the paper’s notation for later use.
A polar code has length n and dimension k, with n − k frozen bits.
The information-bit vector u includes frozen bits and maps to the corresponding codeword c.
The codeword is transmitted over a binary-input channel W, producing the received word y.
A decoding algorithm applied to y produces a decoded codeword ĉ and corresponding information bits û.

A. An outline of Successive Cancellation

The SC decoder processes phases sequentially, calculating probability pairs before deciding each estimated information bit and ultimately returning a decoded codeword.

At each phase ϕ, the decoder calculates a pair of probabilities for the corresponding bit channel before deciding ˆu_ϕ.
Algorithm 1 takes the received vector y as input and outputs a decoded codeword ˆc.
The main loop iterates over phases ϕ = 0, 1, ..., n − 1.
The decoder returns the codeword corresponding to the estimated information vector ˆu.
The probability calculations use recursively defined channel quantities across layers, with W_0^(0)(y|u) = W(y|u) as the stopping condition.

B. Detailed description

The detailed implementation organizes probability and bit information in layer-indexed arrays, recursively propagates values, and establishes correctness through an induction-based invariant.

The implementation uses probability arrays P_λ indexed by channel positions and bit values, together with bit arrays B_λ for decoded inputs.
Branch numbers identify recursive channel inputs and outputs, with branch β mapping to combinations such as u_2ψ ⊕ u_2ψ+1 and u_2ψ+1.
At layer 0, the input and output for branch β correspond to y_β and ˆc_β, respectively.
The first implementation has O(n log n) running time and O(n log n) space complexity.
Algorithms 2–4 are proved valid by showing both that their operations implement SC decoding and that every read array element has been initialized.
Recursive calculations apply the channel recursions separately according to whether the phase is even or odd.

III. SPACE-EFFICIENT SUCCESSIVE CANCELLATION DECODING

The paper reduces SC decoding space from O(n log n) to O(n) by discarding obsolete phase information and renaming bit-array storage without changing the algorithm’s runtime.

The SC decoder runs in O(n log n) time, while the initial implementation uses O(n log n) space.
P-array storage is reduced to O(n) by retaining only probability entries that remain relevant at the current phase.
The B arrays are renamed and resized as C arrays so storage retains branch and phase-parity information while discarding redundant phase indices.
The revised space-efficient decoder is given in Algorithms 5–7.
The space-reduction observations also support the later analysis of the list decoder’s time complexity.

IV. SUCCESSIVE CANCELLATION LIST DECODER

The SCL decoder maintains up to L candidate paths by splitting on unfrozen bits and pruning to the most likely paths, while exploiting polar-code structure to reduce implementation cost.

SCL decoding generalizes SC decoding by maintaining a list of candidate decoding paths controlled by list size L.
At each unfrozen bit, the decoder examines both bit values, doubles the paths, and prunes them to at most L most likely candidates.
Figure 4 shows decoding paths for L = 4, with at most four continuing nodes per level and discontinued paths colored gray.
A naive implementation duplicates each parent path’s data structures, requiring Ω(L · n^2) time because there are Ω(L · n) splits and each path stores Ω(n) data.
The proposed implementation achieves O(L · n log n) time instead of the naive Ω(L · n^2) bound.
The implementation exploits the fact that larger P_λ and C arrays are accessed less frequently, balancing copying cost against access frequency.

A. Low-level functions

The low-level implementation manages active decoding paths and shared probability and bit arrays through indexed banks, reference counts, and path-state operations. It preserves well-defined execution while deliberately favoring simplicity over speed in one copying decision.

Path management: Each path has an index and can transition between active and inactive states, with a stack tracking inactive path indices.The activePath array records whether each path is active, while inactivePathIndices stores reusable inactive indices.
Shared data structures: Probability-pair and bit-pair arrays are organized into banks of L arrays per layer and may be shared by multiple active paths.Pointer mappings connect each path and layer to its corresponding arrays.
Shared data structures: Reference counts track how many paths use each array, allowing zero-reference arrays to be reclaimed through inactive-array stacks.The same reference count applies to the probability and bit-array pointers at a given layer and bank index.
Path management: Cloning a path makes the two resulting paths share probability and bit arrays until later access requires separation.The clone operation is the final step before splitting and initially shares both array types.
Implementation trade-off: The implementation deliberately calls its pointer-access functions before both reads and writes, although copying is needed only before writing.This explicitly sacrifices speed for simplicity.
Correctness conditions: A valid calling sequence guarantees bounded stack operations and ensures every array read follows a prior write.The implementation also proves consistency between active-path states, inactive stacks, and array reference counts.

B. Mid-level functions

The mid-level implementation extends the SC calculations across all active list paths while preserving consistency for shared arrays. It also normalizes probabilities to address floating-point underflow, though the correction does not guarantee that underflows never occur.

List-path calculations: Algorithms 14 and 15 implement the SC calculation procedures for list decoding.The new implementations loop over all path indices and use shared-array pointer functions to preserve calculation consistency.
List-path calculations: Shared-array pointer functions maintain consistent calculations when multiple decoding paths use the same probability and bit arrays.The implementations invoke getArrayPointer_P and getArrayPointer_C while iterating over path indices.
Numerical stability: Probability normalization sets the highest probability to 1 after calculation to reduce the risk of meaningless comparisons caused by floating-point underflow.Earlier SC implementations could round both probabilities to 0 for sufficiently long codes, making comparisons meaningless.
Numerical stability: With infinitely accurate floating-point variables, the unnormalized and normalized algorithm variants differ only by multiplicative scaling of probability values.The paper formalizes this equivalence under the perfect-floating-point assumption.
Numerical stability: Normalization does not assure that underflows will never occur, but the probability of a meaningless comparison due to underflow becomes extremely low.This is stated as the correction's remaining limitation.

C. High-level functions

The SCL decoder processes active paths through a main loop, prunes doubled forks to retain the L best paths, and returns the most likely final codeword. Its implementation achieves O(L · n log n) running time and O(L · n) space, avoiding the naive O(L · n^2) copying cost.

Main loop: The main loop initializes the decoder, processes all n phases, and returns the best codeword in the list.The algorithm takes received vector y and list size L as input.
Path pruning: At each split, the decoder marks the ρ largest-probability forks among 2L candidates, kills paths with no continuing fork, and splits paths when both forks continue.Paths are killed before surviving paths are continued or split.
Path pruning: The pruning procedure leaves only the L “best” paths according to their path probabilities.The implementation uses path continuation markers and probability comparisons to perform selection.
Complexity: The SCL decoder has O(L · n) space complexity.The allocated list-decoder data structures use O(L · n) space, with additional O(L), O(1), and O(log n) terms for selection, local variables, and recursion.
Complexity: The SCL decoder has O(L · n log n) running time.With m = log n, the running-time table gives O(L · m · n), and the recursive calculation contributes O(L · m · n).
Complexity: A naive implementation would require Ω(L · n^2) time because each path split duplicates data structures of size Ω(n).Reducing array sizes and exploiting shared structures helps reduce the list-decoding running time.

V. MODIFIED POLAR CODES

Simulations show that increasing the list size improves decoder performance, but with diminishing returns. A CRC-based modification approximates a genie that selects the transmitted path, producing performance comparable to state-of-the-art LDPC codes while reducing the code rate.

Simulation results: Simulation results show that decoder performance improves as the list size L increases.Figure 5 reports word error rate for rate-1/2 polar codes of lengths 2048 and 8192, optimized for SNR = 2 dB.
Simulation results: Increasing the list size exhibits diminishing returns.The paper identifies this phenomenon in the simulated decoder performance.
Simulation results: The ML-bound curve is a lower bound on the ML decoder’s error probability, based on failures where the decoded codeword is more likely than the transmitted codeword.The bound is constructed from simulations with L = 32.
Modified polar codes: With the modification, polar-code performance is comparable to state-of-the-art LDPC codes.The motivation is that the transmitted path often remains in the final list but is not selected because another path is more likely.
Modified polar codes: A CRC-based concatenation approximates a genie by appending an r-bit CRC to the first k − r information bits.The decoder discards paths with invalid CRCs when at least one valid path remains, then chooses the most likely valid path.
Modified polar codes: The modified code reduces its rate from k/n to (k − r)/n.The rate penalty results from reserving the last r unfrozen bits for the CRC.
Modified polar codes: Systematic decoding further improves bit-error rate, but not block-error rate.This comparison concerns the original and modified polar-code variants.