Source-linked AI summary
Dynamic-SCFlip Decoding of Polar Codes
Ludovic Chandesris, Valentin Savin, David Declercq
TL;DR
SC decoding can make early errors that later decisions cannot reverse, motivating decoding approaches that improve polar-code error correction without the complexity of large lists. The paper introduces higher-order SCFlip attempts, a metric for choosing promising flips, and a dynamic candidate list. D-SCFlip is reported to approach SCL decoding with list size L = 16 while keeping average complexity close to SC decoding.
Problem
Because SC decoding is sequential, early errors cannot be reversed by later decisions.
Source: §I · p. 2Method
The paper generalizes SCFlip to higher-order bit-flips and proposes a metric and dynamic list construction that orders attempts by estimated probability of success.
Source: §VII · p. 28Results
D-SCFlip provides decoding performance close to SCL with list size L = 16 while keeping computational complexity close to SC decoding.
Source: §VII · p. 28Takeaways & Limitations
The authors present D-SCFlip as an alternative to SCL decoding for polar codes, combining performance close to list size 16 with complexity close to SC.
Source: §VII · p. 28
Abstract
from arXiv · showhide
This paper proposes a generalization of the recently introduced Successive Cancellation Flip (SCFlip) decoding of polar codes, characterized by a number of extra decoding attempts, where one or several positions are flipped from the standard Successive Cancellation (SC) decoding. To make such an approach effective, we first introduce the concept of higher-order bit-flips, and propose a new metric to determine the bit-flips that are more likely to correct the trajectory of the SC decoding. We then propose a generalized SCFlip decoding algorithm, referred to as Dynamic-SCFlip (D-SCFlip), which dynamically builds a list of candidate bit-flips, while guaranteeing that extra decoding attempts are performed by decreasing probability of success. Simulation results show that D-SCFlip is an effective alternative to SC-List decoding of polar codes, by providing very good error correcting performance, with an average computation complexity close to the one of the SC decoder.
I. INTRODUCTION
Incomplete polarization can penalize error correction at short to moderate code lengths, while stronger polar-code decoders often trade increased complexity for performance. This work generalizes SCFlip with higher-order flips and a sequentially informed metric, yielding D-SCFlip with performance close to CRC-aided SCL at lower average complexity.
I. INTRODUCTION
- Incomplete polarization of virtual channels may penalize error correction at short to moderate code lengths.SC decoding is sequential, so early errors cannot be reversed by later decisions.Source: §I · p. 2
- SCL improves error correction but incurs storage and computational complexity that grows linearly with list size.SC-Stack reduces computational complexity at the cost of increased storage complexity.Source: §I · p. 2
- SCFlip retries standard SC decoding after a CRC-detected failure, flipping one initially least-reliable hard-decision bit per attempt until CRC success or the attempt limit.Reliability is ranked by the absolute LLR value of the corresponding bit.Source: §I · p. 3
- The proposed metric uses the sequential nature of SC decoding to identify flips more likely to correct its trajectory, improving error correction and reducing computational complexity versus the conventional LLR-based metric.D-SCFlip extends attempts to nested, higher-order bit-flips and dynamically chooses candidates using prior attempts so each next attempt has the best success probability under the metric.Source: §I · p. 3
- D-SCFlip competes with CRC-aided SCL decoding with list size L = 16 while keeping average computational complexity similar to standard SC at medium to high SNR.The paper also reports that D-SCFlip tightly approaches WER lower bounds for ω ∈ {1, 2}.Source: §I · pp. 3–4
- The paper derives WER lower bounds for SCFlip decoders limited to at most ω flips per attempt, and D-SCFlip tightly approaches them for ω ∈ {1, 2}.The approach generalizes SCFlip by allowing one or several flipped positions in an extra decoding attempt.Source: §I · pp. 3–4
II. PRELIMINARIES
The preliminaries define the polar-code and SC-decoding setting, then describe list-based alternatives that address SC's sequential error propagation with additional decoding paths or stack management.
A. Polar Codes and Successive Cancellation Decoding
- A polar code is specified by (N, K, I), with K information-bit positions and the remaining frozen positions fixed to values known to encoder and decoder.The data vector is encoded using generator matrix G_N, and SC estimates each bit from the received channel data and previous estimates.Source: A. Polar Codes and Successive… · p. 4
B. List decoding of Polar Codes
- SCL addresses irreversible early SC errors by duplicating decoding paths at information positions, retaining up to L paths according to a path metric.Its complexity is O(L · N log(N)) with memory O(L · N), and sufficiently large L can approach ML performance.Source: B. List decoding of Polar Codes · p. 5
- SCS instead extends the highest-metric path from an ordered stack of depth D, allowing paths of different lengths and stopping when the top path reaches length N.It can limit operations relative to SCL, especially when SC already decodes correctly, with lower actual complexity particularly at moderate to high SNR; its worst-case complexity is O(D · N log(N)).Source: B. List decoding of Polar Codes · p. 6
III. GENERALIZED SCFLIP DECODERS
Generalized SCFlip decoding extends ordinary SCFlip by allowing multiple nested decision flips per attempt. It uses a bounded candidate list because exhaustive exploration is impractical, and recovery depends on including the trajectory-correcting flip.
III. GENERALIZED SCFLIP DECODERS
- A flip of order ω is a set of ω information-bit indices whose hard decisions are inverted during an otherwise standard SC attempt.The empty flip reproduces standard SC decoding.Source: §III · p. 7
- Exhaustively testing all flip orders would require 2^(K+r) decoding attempts, so the decoder limits testing to a list of T candidate flips.It performs at most T+1 attempts, starting with standard SC decoding.Source: §III · p. 7
- The generalized decoder tests listed flips after SC and stops when a CRC check passes or all T candidates have been tested.The code concatenates an outer (K+r, K) CRC with an inner polar code.Source: §III · pp. 6, 8
- Recovery after an initial SC failure requires the list to contain the unique flip that corrects the SC trajectory, though that flip alone does not guarantee success.An earlier erroneous attempt may pass the CRC and stop decoding before the correct flip is tested.Source: §III · p. 8
- The candidate list should adapt to the current noise realization, using decoding information and a metric to place likely trajectory-correcting flips early.This motivates dynamically updating the list rather than using a predetermined one.Source: §III · pp. 8–9
IV. WORD ERROR RATE LOWER BOUND FOR GENERALIZED SCFLIP DECODERS
The section defines noise-realization order through the minimum number of flips needed for correction and uses an ideal decoder to establish a WER lower bound. For the studied code, ideal order-1 and order-2 decoding gains increase with flip order.
A. Order of a noise realization
- A noise realization has order ω when an order-ω flip can correct the observed signal; OA-SC computes that order by propagating correct prior decisions.OA-SC performs SC operations with an oracle supplying correct decisions instead of propagating potentially erroneous estimates.Source: A. Order of a noise realization · p. 9
B. WER Lower Bound
- The ideal iSCFlip-ω decoder succeeds on every realization of order at most ω, yielding an iWER-ω lower bound for any practical SCFlip-ω decoder.The ideal decoder assumes all flips through order ω are available and uses a detector that accepts only the correct word.Source: B. WER Lower Bound · p. 10
- The ideal lower bound is not necessarily attainable and can even outperform ML in some cases.For small ω, practical decoders can closely approach it when the CRC is sufficiently reliable.Source: B. WER Lower Bound · p. 10
- At WER = 10^-4, iSCFlip-ω decoders show SNR gains over SC decoding: 0.5 dB for iSCFlip-1 and about 1 dB for iSCFlip-2.The figure identifies a code with (N, K+r) = (1024, 512+16).Source: B. WER Lower Bound · p. 11, Figure 1 · p. 11
C. Impact of the code-length and coding-rate on the ideal WER
The ideal error rate at a fixed flip order is reported to depend chiefly on baseline SC error rate rather than code rate or length. The following section introduces an optimized metric and an efficient strategy for constructing the flip list.
C. Impact of the code-length and coding-rate on the ideal WER
- For a given ω, iWER-ω depends only on iWER-0 and is practically independent of coding rate R for the tested N = 1024 codes.The comparison considers R ∈ {1/3, 1/2, 2/3}.Source: C. Impact of the code-length and… · p. 11
- The analysis concludes that iWER-ω essentially depends on iWER-0, with noise-realization orders expected to have nearly the same distribution for codes sharing SC WER.The passage states this property for two polar codes evaluated at their respective SNRs.Source: C. Impact of the code-length and… · p. 12
V. OPTIMIZED METRIC FOR GENERALIZED SCFLIP DECODERS
- The next section introduces an optimized bit-flip metric for any order ω ≥ 1 and an efficient strategy for building Lflip.The supplied passages defer the list-construction strategy to that next section.Source: §V · p. 13
A. Proposed Metric for Generalized SCFlip Decoder
The proposed metric ranks higher-order flips by their estimated likelihood of correcting the SC trajectory. It accounts for SC's sequential decisions, unlike ranking flips solely by low absolute LLR.
A. Proposed Metric for Generalized SCFlip Decoder
- The usual absolute-LLR ranking is suboptimal because it does not distinguish the first SC error from subsequent errors.Low absolute LLR indicates higher bit-error probability but does not identify which error occurred first in sequential decoding.Source: A. Proposed Metric for Generalized… · p. 13
- The proposed metric estimates the likelihood that a higher-order flip corrects the SC trajectory, rather than merely the chance of individual bit errors.Correcting the trajectory through the last flipped position does not guarantee successful decoding of subsequent bits.Source: A. Proposed Metric for Generalized… · p. 13
- The metric approximates the conditional error probability p_e with q_e and uses α to compensate for that approximation.The conditional probability is difficult to compute because it assumes previously decoded bits were correct.Source: A. Proposed Metric for Generalized… · pp. 14–15
- Mα is used to approximate the probability that a candidate flip corrects the trajectory, and the candidate list favors higher Mα values.The equivalent logarithmic-domain metric is more suitable for practical implementations because of its better computational properties.Source: A. Proposed Metric for Generalized… · pp. 15–16
B. Impact of the α parameter
The section examines how α changes the proposed bit-flip metric’s ordering. Its limiting cases prioritize flips by their last position or by the reliabilities of flipped positions, while intermediate α values provide a tunable balance.
B. Impact of the α parameter
- For α = 0, bit-flips are ordered by the index of their last flipped position.The metric reduces to a function of the number of information positions up to that index.Source: B. Impact of the α parameter · p. 16
- As α approaches infinity, the metric prioritizes the sum of the absolute LLR values at flipped positions.For first-order flips, the metric matches the one in.Source: B. Impact of the α parameter · p. 16
- For finite positive α, Sα(Eω) acts as a penalty that incorporates SC decoding’s sequential aspect and tunes between the two limiting priorities.The endpoints prioritize either the last flipped position or the sum of the flipped positions’ reliabilities.Source: B. Impact of the α parameter · p. 16
- The proposed bit-flip metric resembles the SCL path metric, but frozen bits do not contribute to the bit-flip metric.The section expects optimal α to decrease with SNR because Sα(Eω) becomes negligible as SNR tends to infinity; simulations are said to confirm this trend.Source: B. Impact of the α parameter · pp. 16–17
C. Optimization of the α parameter
This section optimizes α for ranking corrective bit-flips and proposes approximating its optimal value from the SC decoder’s word error rate. The metric is reported to rank corrective flips highly, with little expected ranking difference from the approximation.
C. Optimization of the α parameter
- The bit-flip rank is the position of the corrective flip EY in a list ordered by decreasing Mα(E), whose ordering depends on α and noise realization Y.The optimal α is defined using the expected rank of the corrective flip, conditional on SC failing for the current noise realization.Source: C. Optimization of the α parameter · p. 17
- The study determines αopt by Monte Carlo simulation across code parameters and SNR values, with iWER-0 spanning 10−4 to 10−1.iWER-0 is the SC decoder’s word error rate for the corresponding polar-code parameters.Source: C. Optimization of the α parameter · p. 18
- The proposed metric effectively ranks the corrective bit-flips EY among the top positions.The section also reports that the band of E values in Fig. 3(b) is narrow, so replacing αopt with αmodel should negligibly affect rank expectation.Source: C. Optimization of the α parameter · pp. 18–19
VI. DYNAMIC SCFLIP DECODER
Dynamic SC-Flip (D-SCFlip) builds and updates a candidate bit-flip list during SC decoding. It performs attempts in metric order, and the attempted flips are the highest-ranked ones under the metric among those reached before CRC success.
A. D-SCFlip and D-SCFlip-ω Decoders
- D-SCFlip initializes its list with the T highest-metric first-order flips and updates it after unsuccessful attempts using flips that extend the attempted flip.Only extensions at positions greater than the last flipped position are evaluated; the list retains the T highest-metric candidates.Source: A. D-SCFlip and D-SCFlip-ω Decoders · p. 20
- D-SCFlip’s performed attempts contain the bit-flips with the highest Mα(E) values among all flips considered up to the stopping attempt.The decoder stops when an attempt satisfies the CRC, and its list is built on-the-fly alongside the initial SC decoding.Source: A. D-SCFlip and D-SCFlip-ω Decoders · pp. 19, 21
- D-SCFlip-ω restricts candidates to flips of order at most ω and explores the highest-metric flips within that restriction.The stated purpose is to assess the metric’s effectiveness relative to the ideal iSCFlip-ω decoder; practical benefits or constraints of limiting order are beyond the paper’s scope.Source: A. D-SCFlip and D-SCFlip-ω Decoders · p. 22
B. Practical implementation
The section presents two practical simplifications for reducing D-SCFlip’s computational cost: restarting SC from the first differing bit and limiting metric evaluations during list updates.
B. Practical implementation
- The section frames both the restart rule and update-loop restriction as practical simplifications to reduce computational cost.One targets the cost of new decoding attempts, and the other avoids computing metrics for flips that would not be inserted.Source: B. Practical implementation · p. 22
- When two successive attempts share an initial flip prefix, their SC decoding can restart at the first position where the flips differ.Their LLRs and hard-decision estimates are identical through the earlier indices; they differ only in the hard decision at the first differing index.Source: B. Practical implementation · p. 22
- The update loop can stop evaluating extensions after the last index k whose metric bound remains at least Mflip(T).For indices after k, the proposition states that the extension metric is below Mflip(T), so those candidates would not enter the retained list.Source: B. Practical implementation · p. 23
C. Numerical Results
The numerical results show that D-SCFlip’s modeled α adapts performance across SNR, while increasing the attempt budget improves error correction and can bring performance close to SCL. Extra attempts are used selectively, keeping average complexity low, especially at higher SNR.
C. Numerical Results
- The αmodel curve matches the envelope of fixed-α performance curves, while a fixed α incurs loss across low, medium, or high SNR regimes.Fig. 4 evaluates α for T = 20 on a (1024, 512 + 16) code.Source: C. Numerical Results · p. 24, Figure 4 · p. 24
- At WER = 10−4, D-SCFlip outperforms SCFlip by 0.4 dB at T = 10 and 0.8 dB at T = 400; at T = 400, it closely approaches SCL performance.D-SCFlip outperforms the BP decoder for T ≥ 50.Source: C. Numerical Results · pp. 25–26
- The average number of extra attempts approaches 1 at high SNR, and the contribution of Tave becomes negligible in the SC waterfall region.Overall complexity and average latency increase by a factor of 1 + Tave; average latency is nearly the SC latency, although worst-case latency depends on T.Source: C. Numerical Results · pp. 26–27
- At high SNR, D-SCFlip requires fewer extra attempts than SCFlip, reducing computational complexity while improving error-correction performance.The comparison includes the SCFlip decoder at T = 10.Source: C. Numerical Results · p. 26
VII. CONCLUSION
The generalized SCFlip decoder uses higher-order flips, a sequentially informed metric, and dynamically ordered attempts. D-SCFlip offers a different trade-off from SCL: error performance close to list size 16 with computational complexity close to SC decoding.
VII. CONCLUSION
- The generalized decoder permits T extra attempts, flipping one or several positions from standard SC decoding.An ideal generalized SCFlip study found potential for significant improvements through higher-order bit-flips.Source: §VII · p. 28
- The practical metric supports bit-flips of any order and is optimized to account for SC decoding's sequential behavior.The paper also analyzes α and proposes an empirical model for estimating its optimal value from iWER-0, evaluable with density evolution.Source: §VII · p. 28
- D-SCFlip dynamically builds the bit-flip list so new attempts proceed in decreasing probability of success according to the proposed metric.Source: §VII · p. 28
- Compared with state-of-the-art SCFlip, D-SCFlip offers a substantial gain in WER performance and lower computational complexity.Source: §VII · p. 28
- D-SCFlip provides decoding performance close to SCL with list size L = 16 while keeping computational complexity close to SC decoding.The conclusion characterizes it as a variable-latency approach with a different trade-off from SCL.Source: §VII · p. 28