PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Successive Cancellation Decoding of Polar Codes

Kai Chen, Kai Niu, Jia-Ru Lin

arXiv:1208.3598v2cs.IT

TL;DR

Finite-length SC decoding can lose the most probable codeword through irreversible bit-by-bit decisions, while exhaustive ML search is computationally infeasible. The paper unifies SC, SCL, and SCS as code-tree path searches, introduces SCH and a pruning technique, and reports near-ML performance with complexity near SC at moderate and high SNR.

  • Problem

    SC decoding has limited finite-length performance because an incorrect bit decision cannot be corrected, while exhaustive ML-equivalent search has exponential complexity.

  • Method

    The paper unifies SC, SCL, and SCS as code-tree path-search procedures, proposes SCH, and adds pruning to eliminate unnecessary searches.

  • Results

    With proper configurations and pruning, all three improved SC decoders achieve performance very close to ML decoding, with computational complexities very close to SC in moderate and high SNR regimes.

  • Takeaways & Limitations

    SCH offers a trade-off between computational complexity and space complexity, while pruning reduces unnecessary path-searching operations across the improved SC decoders.

Abstract

from arXiv · show

As improved versions of successive cancellation (SC) decoding algorithm, successive cancellation list (SCL) decoding and successive cancellation stack (SCS) decoding are used to improve the finite-length performance of polar codes. Unified descriptions of SC, SCL and SCS decoding algorithms are given as path searching procedures on the code tree of polar codes. Combining the ideas of SCL and SCS, a new decoding algorithm named successive cancellation hybrid (SCH) is proposed, which can achieve a better trade-off between computational complexity and space complexity. Further, to reduce the complexity, a pruning technique is proposed to avoid unnecessary path searching operations. Performance and complexity analysis based on simulations show that, with proper configurations, all the three improved successive cancellation (ISC) decoding algorithms can have a performance very close to that of maximum-likelihood (ML) decoding with acceptable complexity. Moreover, with the help of the proposed pruning technique, the complexities of ISC decoders can be very close to that of SC decoder in the moderate and high signal-to-noise ratio (SNR) regime.

I. INTRODUCTION

Polar codes achieve symmetric channel capacity asymptotically, but their finite-length performance under SC decoding is unsatisfactory. SCL and SCS improve SC decoding, while SCH and pruning target complexity and resource trade-offs.

  • Motivation: Polar codes achieve symmetric capacities of binary-input discrete memoryless channels with O(N log N) SC encoding and decoding complexity.For sufficiently large N and rates below channel capacity, their block error probability also follows a subexponential bound.
  • Motivation: Finite-length polar-code performance under SC decoding is not satisfying despite strong asymptotic performance.Alternative decoders such as BP can outperform SC in some settings, but their schedule sensitivity limits broader practicality.
  • Improved decoding: SCL approaches ML performance with acceptable complexity, while SCS complexity decreases as SNR increases and can approach SC complexity at high SNR.SCS uses lower computational complexity than SCL, with a different resource profile.
  • Contributions: SCH combines SCL and SCS to trade computational complexity against space complexity more effectively.The three improved SC algorithms are described uniformly as path searches on the polar-code tree.
  • Contributions: A pruning technique avoids unnecessary path-searching operations in the improved SC decoders.The paper then evaluates performance and complexity through simulations.

B. Polar Codes

Polar coding constructs synthesized binary-input channels from independent uses of a binary-input discrete memoryless channel, assigning information bits to the most reliable channels and frozen bits to the rest.

  • Channel model: A binary-input discrete memoryless channel has binary input alphabet X = {0, 1} and transition probabilities W(y|x).The channel input and output alphabets are denoted X and Y, respectively.
  • Polar construction: For N = 2^n and rate R = K/N, polar coding generates N synthesized binary-input channels through channel combining and splitting.These synthesized channels are indexed by i = 1, 2, · · ·, N.
  • Reliability estimation: Channel reliabilities can be evaluated using Bhattacharyya parameters for BECs or density evolution for other channels.These reliability estimates support selecting the channels used for information bits.
  • Bit assignment: The K most reliable synthesized channels form the information set I, while the remaining channels carry fixed frozen bits.The information set has size |I| = K, and its complement is the frozen set F.
  • Encoding: A source block containing K information bits and N−K frozen bits is mapped to a code block using the generator matrix G_N.The encoded bits are transmitted through N independent uses of the underlying channel.

C. Successive Cancellation Decoding

SC decoding can be represented as greedy path searching on the polar-code tree using APP-based path metrics. Its bit-by-bit decisions are efficient but can discard the globally most probable codeword.

  • Code-tree representation: The polar-code tree is a full binary tree whose depth-N paths represent candidate codewords.Nodes are organized by depth, and edges are partitioned into N levels.
  • Path metrics: A decoding path is evaluated by the a posteriori probability of its partial bit sequence.APPs are normalized versions of channel transition probabilities and support the path-search interpretation.
  • Path metrics: APP metrics are normalized so paths of equal length have probabilities summing to one, which aids code-tree interpretation and hardware implementation.Logarithmic APPs are used as practical path metrics.
  • SC decoding: SC greedily selects the higher-probability edge at each tree level and determines bits successively from index 1 to N.Its space-efficient implementation has time complexity O(N log N) and space complexity O(N).
  • SC limitation: The SC path is not guaranteed to be the most probable full-length path because an early greedy decision cannot be corrected later.In the example, path 1000 has the largest probability but loses at the first level.

III. IMPROVED SUCCESSIVE CANCELLATION DECODING

SC performance is limited by irreversible bit-by-bit decisions, whereas exhaustive ML-equivalent tree traversal is computationally infeasible. The paper therefore unifies and extends path-searching decoders with SCH and pruning.

  • Motivation: SC cannot correct a bit once it has been wrongly determined during successive decoding.This irreversible decision process limits finite-length performance.
  • Motivation: ML-equivalent decoding can be achieved by traversing all N-length paths, but brute-force traversal has exponential complexity.This makes exhaustive decoding difficult to implement.
  • Existing improvements: SCL and SCS explore more than one edge per tree level and retain multiple candidate paths in a list or stack.They preserve alternative paths while continuing bit-by-bit metric calculations and decisions.
  • Contributions: The paper gives SCL and SCS a unified APP-metric, code-tree framework and introduces SCH to address their respective shortcomings.SCH combines their ideas within a hybrid decoding procedure.
  • Contributions: A pruning technique eliminates unnecessary path-searching calculations to reduce the computational complexity of improved SC decoders.The technique is designed for the unified path-searching framework.

A. Successive Cancellation List Decoding

SCL performs breadth-first path searching on the polar-code tree, retaining up to L candidate paths at each level. This improves path selection but increases metric computations and storage relative to SC.

  • SCL path search: SCL searches level-by-level while retaining at most L candidate paths for further exploration.Each candidate is extended with both possible bits, after which paths with the largest metrics are retained.
  • SCL path search: At each level, SCL doubles the candidates, then keeps up to L paths with the largest metrics for the next level.The final estimate is the leaf path with the largest metric in the list.
  • Algorithm procedure: The SCL algorithm is initialized with a null path whose metric is zero, then repeatedly expands, competes, and determines the output.Competition is skipped when the list contains no more than L paths.
  • Performance example: With L = 2, SCL finds the most probable path 1000, increasing metric computations from four under SC to seven.The example illustrates the performance benefit and computational cost of retaining multiple paths.
  • Complexity: SCL uses O(LN) space and a direct implementation requires O(LN^2) computations.Lazy-copy and space-efficient structures are used to reduce implementation overhead.

B. Successive Cancellation Stack Decoding

SCS searches the code tree with an ordered stack, following the highest-metric candidate while allowing paths of different lengths. This can avoid unnecessary extensions and reduce computation, especially at moderate or high SNR.

  • Search principle: Because a path metric dominates the metrics of its descendants, SCS can continue along one candidate until it is no longer the largest.This avoids extending competing paths when their descendants cannot become preferable under the stated metric property.
  • Stack search: SCS stores candidate paths of different lengths in an ordered stack and follows the highest-metric path.Decoding stops when the top path reaches a leaf node.
  • Decoder parameters: The SCS decoder uses searching width L and maximum stack depth D to control candidate expansion and storage.A counting vector records how many paths of each length have been popped.
  • Algorithm procedure: SCS initializes the null path, expands frozen or information-bit paths, pushes candidates, applies competition, sorts by metric, and determines the output.Competition removes paths whose lengths are at most i − 1 when the relevant count reaches L.
  • Performance example: In the example, SCS finds the most probable path 1000 with two fewer metric computations than SCL.The comparison illustrates the computational saving from stack-based search.
  • Complexity and trade-offs: SCS has O(LN log N) time and O(DN) space complexity, with actual computations much lower than SCL at moderate or high SNR.Its stack can nevertheless require substantially more space than SCL, and the suitable D depends on SNR.

C. Hybrid SCL and SCS

SCH combines SCL-style waiting with SCS-style on-going stack search to balance computational and space complexity. Its performance is less than SCL’s computationally but usually greater than SCS’s, with complexity affected by stack depth D.

  • Design limitation: SCS can require D as large as LN to prevent performance deterioration, while smaller D is sufficient in moderate and high SNR regimes.The appropriate D is difficult to determine because it depends on the specific SNR.
  • Hybrid decoding: SCH alternates between on-going and waiting modes to combine SCS-style best-path search with SCL-like equal-length expansion.It searches forward along the best candidate until the stack nears capacity, then extends shortest paths until candidate lengths equalize.
  • Algorithm procedure: The SCH procedure initializes a stack, zero counting vector, and mode flag before selecting paths according to the current mode.The mode flag distinguishes on-going mode from waiting mode.
  • Complexity: SCH has O(LN log N) time and O(DN) space complexity.These bounds use searching width L and maximum stack depth D.
  • Complexity trade-off: SCH usually performs more computations than SCS but fewer than SCL.When the stack is about to fill, SCH avoids dropping paths and switches to waiting mode to reduce stack occupancy.
  • Stack-depth effects: SCH performance is unaffected by D when no path is dropped, but smaller D increases waiting-mode use and computational complexity.The minimum stack depth for sufficient waiting-mode space is D = 2L.

D. Pruning Technique

The pruning technique removes low-metric candidate paths during code-tree searching, reducing unnecessary operations while bounding the resulting performance deterioration.

  • Pruning reference: The pruning reference a_i is the largest metric among traversed i-length paths for SCL, while SCS and SCH use the first i-length path popped from the stack.
  • Pruning rule: The decoder drops an i-length path when its metric is smaller than a level-specific reference by more than -log(τ).The threshold parameter τ controls this probability-ratio-based pruning rule.
  • Performance impact: Pruning can discard the correct path, so the additional BLER deterioration and error probability introduced by the threshold are analyzed and bounded.The correct-path-loss event is included among the error events caused by pruning.
  • Performance impact: Correct-path loss can arise from limited search width, a maximum probability ratio, or, for SCS, a maximum stack depth.For SCL, SCH, or SCS with sufficiently large stack depth, the stack-depth loss event has zero conditional probability.
  • Parameter selection: Given a tolerable deterioration Ptol, τ can be configured conservatively, although the actual deterioration is usually far below Ptol because the analytical upper bound is loose.

IV. SIMULATION RESULTS

Simulations evaluate ISC decoder performance and complexity across configurations. With proper settings and pruning, the decoders approach ML performance while their complexity approaches SC in moderate and high SNR.

  • Complexity evaluation: The simulations measure average computational complexity by counting metric recursive operations, with SC requiring approximately N log N operations.For N = 1024, the paper gives 1024 × 10 ≈ 10^4 operations as the SC reference.
  • Performance: Under proper configurations, SCL, SCS, and SCH achieve performance very close to ML decoding.The ML lower bound is estimated using SCL(32) decoding and transmitted-codeword likelihood comparisons.
  • SCH trade-off: SCH has lower computational complexity than SCL and uses less memory than SCS without performance deterioration.SCH can coincide with SCL when D = 2L and with SCS when D is very large.
  • Pruning: With pruning, ISC decoding complexity can become very close to SC in the moderate and high SNR regime.The pruning technique reduces unnecessary path-searching operations.

A. On Different Searching Width L

Increasing the searching width reduces the chance of losing the correct path but increases computational complexity. For N = 1024 and R = 0.5, L = 32 is reported as sufficient.

  • Applicability: The effects of different L values in SCL also apply to SCS and SCH.The paper notes equivalence relations connecting SCL(L), SCH(L, 2L), and SCS(L, D) with sufficiently large D.
  • Searching width: A larger searching width makes losing the correct path less probable.The paper states that P(L_i) decreases as L increases.
  • Complexity: Computational complexity is approximately proportional to the searching width L.The relationship is reported from the results shown in Fig. 10.
  • Configuration: For N = 1024 and R = 0.5, L = 32 is reported as sufficient.The simulations compare SCL widths from 1, equivalent to SC, through 64.

B. On Different Stack Depth D

Stack depth affects SCS performance but primarily changes SCH complexity in the reported simulations. The pruning threshold also trades BLER against complexity, with limited effects in a moderate-SNR case.

  • Stack depth D: For SCS, a stack depth D smaller than 1024 causes significant performance deterioration.The reported simulations indicate that D needs to exceed 1024 for SCS.
  • Stack depth D: For SCH, changing D does not affect BLER performance but increasing D reduces computational complexity.SCH uses less memory than SCS while avoiding performance deterioration in the comparison.
  • SCH trade-off: SCH offers lower complexity than SCL and only slightly higher memory use, while interpolating between SCL and SCS configurations.SCH(L, 2L) is equivalent to SCL(L), whereas SCH(L, D) approaches SCS(L, D) for very large D.
  • Pruning threshold τ: Increasing the pruning threshold τ reduces complexity, but an excessively small τ deteriorates BLER performance.Values from 10^4 to 10^8 introduce little performance deterioration but lead to larger complexities.
  • Pruning threshold τ: At 2.5 dB, where BLER is below 10^-3, SCH and SC complexity differences across the simulated τ values tend to be negligible.This observation is reported for the moderate-SNR regime in the simulations.
  • Overall conclusion: The conclusion reports that pruning brings ISC performance close to ML and complexity close to SC at moderate and high SNR.This summarizes the paper-level simulation conclusion.
Loading 1208.3598v2…