Source-linked AI summary
A Low-Complexity Improved Successive Cancellation Decoder for Polar Codes
Orion Afisiadis, Alexios Balatsoukas-Stimming, Andreas Burg
TL;DR
Finite-blocklength SC decoding gives polar codes inferior error-correcting performance to other modern codes, while list and stack methods increase complexity. The paper introduces SC flip, which retries unreliable decisions and retains low memory use. Its average complexity approaches SC at high signal quality while improving error-correcting performance and approaching more complex decoders.
Problem
At finite blocklengths, SC decoding has inferior error-correcting performance to modern codes, while list and stack alternatives increase computational and memory complexity.
Method
SC flip retries alternative decisions for unreliable bits after a failed initial decoding attempt, exploring decoding-tree passes sequentially.
Results
SC flip retains O(N) memory complexity, has practically O(N log N) average computation at high SNR, and significantly improves error-correcting performance.
Takeaways & Limitations
SC flip keeps average complexity and memory requirements low while approaching the performance of more complex tree-search decoders.
Abstract
from arXiv · showhide
Under successive cancellation (SC) decoding, polar codes are inferior to other codes of similar blocklength in terms of frame error rate. While more sophisticated decoding algorithms such as list- or stack-decoding partially mitigate this performance loss, they suffer from an increase in complexity. In this paper, we describe a new flavor of the SC decoder, called the SC flip decoder. Our algorithm preserves the low memory requirements of the basic SC decoder and adjusts the required decoding effort to the signal quality. In the waterfall region, its average computational complexity is almost as low as that of the SC decoder.
I. INTRODUCTION
Polar codes combine highly structured, provably optimal constructions with low-complexity successive cancellation decoding, but finite-blocklength SC performance motivates more complex alternatives. The SC flip decoder retains SC’s O(N) memory complexity while improving error correction with signal-dependent average effort.
- Polar codes are highly structured and provably optimal for a wide range of applications.
- SC decoding has O(N log N) computational complexity and O(N) memory complexity, while remaining sufficient to establish capacity achievement asymptotically.
- At finite blocklengths, SC has worse error-correcting performance than modern codes such as LDPC codes.
- SC list and stack decoding improve performance by exploring multiple decision-tree paths, with complexities O(LN log N), O(LN), O(DN log N), and O(DN), respectively.
- Hardware implementations of reduced-complexity list and stack decoders still require worst-case O(LN) and O(DN) memory, respectively, and higher computational complexity than SC.
- SC flip retains O(N) memory complexity, achieves practically O(N log N) average computation at high SNR, and significantly improves error-correcting performance.
B. Successive Cancellation Decoding
Successive cancellation decodes information bits sequentially from channel-output likelihoods, using prior decisions and frozen-bit knowledge. Its computation graph supports O(N log N) decoding while memory reuse reduces storage to O(N).
- SC estimates u1, then estimates each subsequent bit using the received channel output and preceding decisions.
- Because frozen bits are known, SC decoding primarily estimates the non-frozen information bits.
- The SC computation graph uses f and g nodes, with g nodes incorporating partial sums as decision feedback.
- The min-sum update rules are f(L1, L2) = sign(L1)sign(L2) min(|L1|, |L2|) and g(L1, L2, u) = (−1)^uL1 + L2.
- Partial sums at stage s−1 are calculated from partial sums at stage s.
- SC decoding has O(N log N) computational complexity, while memory reuse reduces implementation memory from O(N log N) to O(N).
III. ERROR PROPAGATION IN SC DECODING
SC decoding errors arise from channel noise and subsequent error propagation. The first erroneous decision is caused by channel noise, while propagation affects bit error rate but not frame error rate.
- The first erroneous SC decision is caused by channel noise because no previous erroneous decisions exist.
- Error propagation can create later erroneous bit decisions, affecting bit error rate but not frame error rate.
A. Effect of Error Propagation
Erroneous partial sums from prior SC decisions can corrupt later decision LLRs, causing additional erroneous bit decisions beyond the initial channel-induced error.
- A. Effect of Error Propagation: Erroneous decision feedback produces incorrect partial sums that can corrupt decision LLRs throughout the computation graph.The corruption can reach decision LLRs at the highest level of the decoder.
- A. Effect of Error Propagation: The SC computation graph uses f and g nodes, with g nodes receiving partial sums as additional inputs.For N = 8, the graph illustrates how partial sums enter the g-node updates.
- A. Effect of Error Propagation: A channel-induced error in ˆu3 can produce a second erroneous decision when the subsequent g-node calculation uses the wrong partial sum.With the correct partial sum u = 0, the later decision would have been correct.
B. Significance of Error Propagation
The paper examines how many SC decoding errors originate directly from channel noise rather than error propagation, using oracle-assisted decoding and channel-error histograms.
- B. Significance of Error Propagation: The oracle-assisted SC decoder corrects each erroneous decision immediately and counts how often correction was required.This prevents an error from affecting future bit decisions and separates channel-induced errors from propagated errors.
- B. Significance of Error Propagation: Most frequently, the channel introduces only one error, and this pattern becomes more prominent as Eb/N0 increases.The observation concerns polar codes with N = 1024 and R = 0.5 over an AWGN channel.
- B. Significance of Error Propagation: As blocklength increases, synthetic channels become more polarized, making the information channels better.The supplied discussion links this behavior to the changing distribution of channel-induced errors.
C. Oracle-Assisted SC Decoder
The oracle-assisted SC decoder tests how much SC performance could improve if the first erroneous bit decision were identified and corrected. Across the evaluated blocklengths, correcting one such decision significantly improves performance.
- C. Oracle-Assisted SC Decoder: Correcting the first erroneous bit decision is used to assess the potential benefit of eliminating the initial SC error.The second oracle-assisted decoder may intervene only once during decoding.
- C. Oracle-Assisted SC Decoder: Correcting a single erroneous bit decision significantly improves SC-decoding performance.The comparison covers N = 1024, 2048, 4096 and R = 0.5 over an AWGN channel.
- C. Oracle-Assisted SC Decoder: The paper’s SC flip approach aims to identify the first SC error without relying on an oracle.This provides the motivation for replacing oracle assistance with an SC-based decoding procedure.
A. SC Flip Decoding Algorithm
SC flip decoding begins with standard SC decoding and uses CRC feedback to selectively retry likely first-error positions by flipping one decision at a time.
- A CRC checks whether the initial codeword estimate is valid, while extending the information set with reliable CRC channel indices preserves the effective information rate.
- The decoder first performs standard SC decoding and produces an initial estimated codeword.
- If the CRC passes, decoding terminates; otherwise, the decoder selects the T least reliable decisions using the smallest decision-LLR magnitudes.
- The decoder restarts SC decoding for up to T attempts, flipping one selected decision per attempt, and stops when a valid codeword is found or all attempts fail.
- SC flip considers single-error patterns generated online from decision reliabilities, unlike chase decoding's offline patterns based on a priori synthetic-channel reliabilities.
B. Complexity of SC Flip Decoding
SC flip retains linear memory complexity and has a worst-case cost proportional to T, but its average cost approaches standard SC decoding as frame errors become rare at high SNR.
- O(T N log N) is the SCFLIP algorithm's worst-case computational complexity.
- Worst-case complexity grows linearly with T, giving SC flip the same complexity scaling order as SC list decoding in that regime.
- O(N log N(1+T ·Pe(R, SNR))) is the average-case computational complexity of SC flip decoding.
- At high SNR, the frame error rate approaches zero, so average SC flip complexity converges to standard SC complexity.
- O(N) memory positions are required by SCFLIP, with retry decoding reusing the memory allocated for the initial SC decoding.
C. Error Correcting Performance of SC Flip Decoding
SC flip substantially improves finite-blocklength error correction, with performance depending on the trial budget and remaining limited by single-error correction.
- At Eb/N0 = 3.5 dB, SC flip with T = 4 yields a one-order-of-magnitude FER gain over standard SC decoding for N = 1024 and R = 0.5.
- With T = 32, SC flip reaches the oracle-assisted decoder's benefits, with the curve shift matching the rate loss from the 16-bit CRC.
- For N = 4096 with T/N held constant, reaching the oracle-assisted bound becomes more difficult as the number of possible first-error positions increases.
- With T = 32, SC flip has nearly identical performance to SC list decoding with L = 2, while using half the high-Eb/N0 computational complexity and half the memory at all Eb/N0 values.
- SC list decoding with L = 4 outperforms SC flip, whose performance is limited to correcting a single error.
D. Average Computational Complexity of SC Flip Decoding
For N = 1024 and R = 0.5, SC flip decoding’s average complexity depends strongly on signal quality: it is costly at low SNR but nearly matches SC at higher SNR.
- At low SNR, SC flip decoding requires (T + 1) times the average computational complexity of SC decoding.
- At higher SNR, SC flip decoding’s average computational complexity is practically identical to that of standard SC decoding.
- SC flip decoding exhibits energy-proportional behavior because its complexity decreases rapidly as SNR increases, unlike SC list decoding.
- The comparison evaluates average complexity for a polar code with blocklength N = 1024 and rate R = 0.5.
V. CONCLUSION
SC flip decoding improves polar-code frame-error-rate performance by retrying unreliable decisions while preserving low average complexity and memory requirements. Its sequential alternative exploration approaches more complex tree-search decoders without requiring their full search structure.
- SC flip decoding improves frame error rate by retrying alternative decisions for bits identified as unreliable after a failed initial iteration.
- The decoder explores alternative decoding-tree passes sequentially until it finds a correct codeword.
- Sequential exploration keeps average complexity and memory requirements low while approaching more complex tree-search decoders’ performance.