PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast and Flexible Successive-Cancellation List Decoders for Polar Codes

Seyyed Ali Hashemi, Carlo Condo, Warren J. Gross

arXiv:1703.08208v2cs.IT

TL;DR

The paper addresses the limited throughput of SCL and the redundant path splitting left by SSCL and SSCL-SPC. It proves list-size-dependent splitting limits, develops Fast-SSCL and Fast-SSCL-SPC, and implements flexible hardware architectures achieving 1.861 Gb/s for N = 1024 and L = 2.

  • Problem

    SCL offers strong error-correction performance but limited throughput, while SSCL and SSCL-SPC do not address redundant path splitting for specific list sizes.

  • Method

    The paper derives the exact useful number of path forks for Rate-1 and SPC nodes, then uses reduced practical fork counts and hardware architectures to accelerate decoding.

  • Results

    1.861 Gb/s throughput and 1.048 mm2 area are achieved for a decoder sized for N = 1024 and L = 2.

  • Takeaways & Limitations

    The proposed Fast-SSCL and Fast-SSCL-SPC decoders reduce required time steps by more than 75% at no error-correction performance cost, depending on L and path forks.

Abstract

from arXiv · show

Polar codes have gained significant amount of attention during the past few years and have been selected as a coding scheme for the next generation of mobile broadband standard. Among decoding schemes, successive-cancellation list (SCL) decoding provides a reasonable trade-off between the error-correction performance and hardware implementation complexity when used to decode polar codes, at the cost of limited throughput. The simplified SCL (SSCL) and its extension SSCL-SPC increase the speed of decoding by removing redundant calculations when encountering particular information and frozen bit patterns (rate one and single parity check codes), while keeping the error-correction performance unaltered. In this paper, we improve SSCL and SSCL-SPC by proving that the list size imposes a specific number of bit estimations required to decode rate one and single parity check codes. Thus, the number of estimations can be limited while guaranteeing exactly the same error-correction performance as if all bits of the code were estimated. We call the new decoding algorithms Fast-SSCL and Fast-SSCL-SPC. Moreover, we show that the number of bit estimations in a practical application can be tuned to achieve desirable speed, while keeping the error-correction performance almost unchanged. Hardware architectures implementing both algorithms are then described and implemented: it is shown that our design can achieve 1.86 Gb/s throughput, higher than the best state-of-the-art decoders.

I. INTRODUCTION

SC decoding offers low complexity but suffers from serial latency and limited practical error-correction performance. SCL improves correction performance by retaining multiple candidate paths, while SSCL-family methods reduce redundant decoding work but leave list-size-specific path splitting unaddressed.

  • Motivation: SC decoding advances bit by bit, causing high hardware latency and low throughput.For moderate-length polar codes, SC also falls short of reasonable error-correction performance.
  • Existing Decoders: Rate-0, Rate-1, repetition, and SPC constituent codes can be decoded in parallel with low-complexity algorithms.These simplifications increase throughput and reduce latency without degrading error-correction performance in the cited approaches.
  • Existing Decoders: SCL estimates each bit as 0 or 1 and retains only L candidate codewords using path metrics.This improves error-correction performance but increases latency, reduces throughput, and raises hardware area relative to SC.
  • Existing Decoders: SSCL avoids redundant SCL calculations while preserving error-correction performance and retaining the conventional SCL sorter.SSCL-SPC further increases throughput and reduces latency using matrix reordering for SPC nodes.
  • Contributions: Fast-SSCL and Fast-SSCL-SPC limit path splitting according to list size, with later splits redundant and earlier splits unable to guarantee preservation.The paper also tunes path forks for practical speed gains with almost no error-correction performance loss and proposes corresponding hardware architectures.
  • Paper Scope: The paper covers polar-code construction, encoding, BPSK modulation, decoder algorithms, architecture, and implementation results.A polar code P(N, K) contains K information bits and N−K frozen bits, with encoding written as x = uG_N.

B. Successive-Cancellation Decoding

SC decoding can be represented as a left-first binary-tree search over recursively constructed polar-code nodes. Soft LLR messages move downward, while hard bit estimates move upward and leaf estimates determine decoded bits.

  • Tree Representation: SC decoding recursively traverses a binary tree whose stage-s node represents a polar code of length N_s = 2^s.The tree passes soft LLR values from parent to child nodes and hard estimates from child to parent nodes.
  • Message Passing: At each tree stage, SC computes left- and right-child messages recursively before combining child estimates.The upward combination uses the left and right child β messages and bitwise XOR.
  • Leaf Decisions: At leaf nodes, the decoder estimates the i-th input bit from the available decoding message.Equation (1) is reformulated into a more hardware-friendly version for implementation.

C. Successive-Cancellation List Decoding

SCL improves SC by estimating both bit values and retaining only the best L candidate paths, while SSCL prunes constituent-code calculations without sacrificing error-correction performance. However, SSCL does not account for list-size-dependent redundant path splitting.

  • SCL decoding: SCL estimates each bit as 0 and 1, doubling candidate paths before retaining L paths using path metrics.The path metric is updated after each estimation to limit the candidate set.
  • SSCL decoding: SSCL decodes Rate-0, repetition, and Rate-1 nodes without traversing the decoding tree while preserving error-correction performance.Its pruned tree replaces these constituent nodes with efficient specialized decoders.
  • SSCL decoding: Rate-0, repetition, and Rate-1 nodes use specialized low-complexity decoding rules, with repetition nodes requiring one information-bit estimate.The supplied equations and surrounding text define the node-specific decoders and time-step requirements.
  • SSCL decoding: SSCL reduces Rate-1 decoding steps by almost a factor of three but does not address the list size’s effect on maximum path forks.

2) SSCL-SPC Decoding:

SSCL-SPC extends simplified list decoding to single parity-check nodes by pruning the decoding tree and efficiently enforcing parity. Its SPC procedure reduces decoding steps but, like SSCL, initially leaves list-size-dependent path splitting unaddressed.

  • SSCL-SPC decoding: SSCL-SPC combines a repetition node and an SPC node in its pruned decoding tree for the illustrated polar-code example.
  • SPC node decoding: The SPC decoder identifies the least reliable bit and derives its parity before initializing path metrics.The least reliable bit is decoded first to satisfy the even-parity constraint.
  • SPC node decoding: For the remaining bits, path metrics are updated using their LLRs and the parity-related correction term.
  • SPC node decoding: After all bits are estimated, the least reliable bit is set to preserve the even-parity constraint.
  • SSCL-SPC decoding: SSCL-SPC reduces SPC decoding steps by almost a factor of three but does not address list-size effects on maximum path forks.The paper identifies this gap as the motivation for Fast-SSCL-SPC.

III. FAST-SSCL DECODING

Fast-SSCL and Fast-SSCL-SPC derive list-size-dependent limits on path splitting for Rate-1 and SPC nodes, preserving conventional decoding results while reducing unnecessary time steps. The limits can also be tuned in practice for speed with almost no error-correction loss.

  • Contribution: The proposed decoders prove exact path-fork counts for Rate-1 and SPC nodes, with further reductions possible at almost no error-correction performance loss.
  • Rate-1 nodes: Theorem 1 requires min(L −1, Ns) path splits for a Rate-1 node of length Ns to match conventional SSCL results.After the L−1-th bit, remaining bits can use hard decisions when L−1 < Ns.
  • Rate-1 nodes: For L = 2, the empirical Rate-1 decoder using two path forks is redundant because Theorem 1 requires only one.
  • Performance: At FER 10−5, the empirical Rate-1 method loses 0.25dB versus SSCL for P(1024, 860) with L = 128.The comparison uses a CRC length of 32.
  • SPC nodes: Theorem 2 requires min(L, Ns) path forks for an SPC node of length Ns to reproduce conventional SSCL-SPC results.Bits after the L-th can be obtained by hard decisions when L < Ns.
  • Performance: For a length-64 SPC node with L = 4, Fast-SSCL requires 26 time steps whereas Fast-SSCL-SPC requires 5.
  • Performance: Practical polar codes contain many nodes where the list-size limits are smaller than node length, enabling significant time-step savings over SSCL and SSCL-SPC.The paper reports savings across codes with three different rates.

B. Speed Optimization

Fast-SSCL and Fast-SSCL-SPC limit path splitting according to list size while preserving SSCL and SSCL-SPC error-correction performance. Their speed can be tuned through fewer path forks, with savings demonstrated across practical code rates.

  • Fast-SSCL and Fast-SSCL-SPC are exact reformulations of SSCL and SSCL-SPC without error-correction performance loss.
  • For CRC-aided P(1024, 512) with CRC length 16 and L = 2, SRate-1 = 0 causes significant FER and BER degradation, so SRate-1 = 1 is selected.
  • For L = 4 and L = 8, smaller path-fork settings can achieve almost the same FER and BER performance as optimal settings.The reported comparisons are SRate-1 = 1 versus 3 for L = 4, and SRate-1 = 2 versus 7 for L = 8; SPC uses SSPC = 4 versus 8 for L = 8.

IV. DECODER ARCHITECTURE

The decoder architecture replicates datapath and memory resources across list paths while adapting control, path, metric, and CRC operations for Fast-SSCL-SPC. Processing elements operate concurrently, and pipeline registers address critical-path growth.

  • The architecture replicates most datapath and memory components L times so candidate codewords and their LLR values are processed concurrently.
  • Each set of P processing elements computes left and right recursive LLR operations concurrently, with P constrained to a power of 2.When 2s > 2P, the operations require 2s/(2P) time steps; otherwise they require one.
  • At information bits, paths split into 2L candidates, path metrics are computed, and a parallel sorter retains the surviving paths.
  • All decoder memories are register-based, allowing LLR and β values to be read, updated, and written back in one clock cycle.

A. Memory Structure

The memory structure stores channel and intermediate LLR values, path decisions, partial sums, and path metrics across list candidates. Memory words are reused after subtree decoding to limit storage demands.

  • The channel memory stores N quantized channel LLR values, while high- and low-stage memories store intermediate LLR values.The channel LLR values are shared among the L datapaths, whereas high- and low-stage memories are separate for each path.
  • High-stage memory words have width QLLR × P, while low-stage memory words have width QLLR.
  • Memory depth and access depend on the processing-element count P and the stage condition 2s ≤ 2P.When 2s = 2P, 2P LLR values are read from high-stage memory and P resulting values are written to low-stage memory.
  • Each candidate codeword uses an N-bit path memory, while β memories store stage values totaling N −1 bits per path.β memories are reused for the right half after the left half of the decoding tree is completed.
  • Path-metric memories store the L path metrics computed during decoding.

B. Special Nodes

Special-node decoding modifies the standard SCL datapath and control flow for Rate-0, Rate-1, repetition, and SPC nodes. Fast variants split selected nodes into phases that reduce path-forking work while preserving the surrounding memory and metric framework.

  • Special Nodes: Fast-SSCL and Fast-SSCL-SPC modify the datapath to simplify Rate-0, Rate-1, repetition, and SPC-node computations.
  • Rate-0 nodes: Rate-0 nodes require one phase, no path splitting, all 2s bits set to 0, and one time step for path-metric updating.
  • Rate-1 nodes: Fast Rate-1 nodes use a fork phase with min(SRate-1, 2s) splits followed by a one-time-step phase assigning the remaining bits and updating metrics.
  • Rep nodes: Repetition nodes use two one-time-step phases: one handles frozen bits and the other estimates the single information bit.
  • SPC nodes: SPC nodes use multiple phases for frozen-bit processing, information-bit estimation, and path-metric handling, while Descend entries provide controller timing after special nodes.
  • Architecture changes: Path, β, path-metric, CRC, and controller modules are modified to support concurrent special-node operations and node-dependent updates.The controller advances the bit index by the number of bits estimated in one special-node time step.

V. RESULTS

The implemented Fast-SSCL and Fast-SSCL-SPC architectures increase throughput but require substantially more area and longer critical paths than SSCL-based designs.

  • Fast-SSCL and Fast-SSCL-SPC show substantial area increases compared with SSCL and SSCL-SPC.The architectures were synthesized in TSMC 65 nm CMOS for list sizes L = 2, 4, and 8.
  • Parallel CRC computation adds area because Rate-1 and SPC nodes update multiple information bits within one time step.The resulting CRC trees are wider and deeper, and additional CRC-tree selection logic is required.
  • Fast-SSCL and Fast-SSCL-SPC also require more complex β-memory update logic for parallel information-bit estimation.An XOR tree computes the selection signal for each information bit estimated in SPC2-2 and RATE1-2 stages.
  • Pipeline registers reduce the impact of longer critical paths, but their added stages lower the practical throughput gain below the theoretical savings.The critical path depends on code length, list size, and parallelism, and may pass through routing, path-metric, sorting, or CRC logic.

B. Comparison with Previous Works

The proposed decoder architectures outperform several prior designs in throughput and latency while retaining flexibility across polar codes, although area trade-offs remain.

  • 72% higher throughput and 42% lower latency are achieved than the multibit decision SCL architecture of for L = 4.The architecture of has smaller area and higher area efficiency.
  • 192% higher throughput, 66% lower latency, and 17% higher area efficiency are achieved than the symbol-decision SCL architecture of for L = 4.The design in occupies less area but has lower throughput and higher latency.
  • For L = 4, the proposed architecture exceeds in throughput and latency while occupying less area, yielding a 12% area-efficiency increase.The comparison also notes that relies on code-specific parameters associated with reported error-correction performance loss after code changes.
  • The architectures are targeted for speed and flexibility and can decode any polar code of any length.The conclusion reports implementation in CMOS 65 nm technology and flexibility regardless of code rate.
  • Compared with, throughput increases by 51% and latency decreases by 34% for L = 2, while throughput increases by 40% and latency decreases by 28% for L = 4.For L = 8, the proposed design achieves 39% higher throughput, 29% lower latency, and 9% higher area efficiency.
  • The proposed design has the shortest latency among the decoders plotted in Fig. 15 for each list size L.In the area-versus-latency plot, shortest latency corresponds to the leftmost position.
  • For N = 1024 and L = 2, the proposed SCL-based decoder reaches 1.861 Gb/s throughput with 1.048 mm2 area.The same design reaches 1.608 Gb/s for L = 4 and 1.198 Gb/s for L = 8.

APPENDIX A PROOF OF THEOREM 2

The proof reduces SPC decoding to a Rate-1 node after estimating the least reliable bit, establishing the required number of path splittings for each list size.

  • The proof initializes path metrics so that the least reliable bit is estimated first.For the remaining bits, a constant path-metric term is removed to define Ns − 1 new LLR values.
  • After removing the least reliable bit, the problem becomes a Rate-1 node of length Ns − 1.The Rate-1 result therefore applies to the transformed SPC decoding problem.
  • Rate-1 decoding requires min(L − 1, Ns − 1) path splittings, while SPC decoding requires min(L, Ns) splittings.These bounds guarantee the same results as SSCL-SPC, and further splitting is redundant.
Loading 1703.08208v2…