PaperlayerView exact revision on arXiv

Source-linked AI summary

LLR-based Successive Cancellation List Decoding of Polar Codes

Alexios Balatsoukas-Stimming, Mani Bastani Parizi, Andreas Burg

arXiv:1401.3753v4cs.IT

TL;DR

The paper addresses numerical instability and hardware inefficiency in likelihood- and log-likelihood-based SCL decoding. It formulates SCL decoding with LLRs, simplifies path sorting, and evaluates CRC-aided decoding across list sizes. The resulting architecture achieves up to 137% higher hardware efficiency, while CRC length must be matched to list size.

  • Problem

    Likelihood-based SCL decoding is vulnerable to underflow, while log-likelihood implementations use irregular memories and large processing elements that limit hardware efficiency.

  • Method

    The paper introduces an LLR-based path metric, a hardware architecture using LLR-domain decoding, and a pruned radix-2L sorter.

  • Results

    Up to 137% higher hardware efficiency is reported than existing decoders, while CRC-aided SCL decoding achieves lower block-error probability with list-size-dependent CRC selection.

  • Takeaways & Limitations

    CRC length should increase with list size, and CRC-aided decoding can improve hardware efficiency by enabling smaller lists at comparable decoding performance.

Abstract

from arXiv · show

We show that successive cancellation list decoding can be formulated exclusively using log-likelihood ratios. In addition to numerical stability, the log-likelihood ratio based formulation has useful properties which simplify the sorting step involved in successive cancellation list decoding. We propose a hardware architecture of the successive cancellation list decoder in the log-likelihood ratio domain which, compared to a log-likelihood domain implementation, requires less irregular and smaller memories. This simplification together with the gains in the metric sorter, lead to $56\%$ to $137\%$ higher throughput per unit area than other recently proposed architectures. We then evaluate the empirical performance of the CRC-aided successive cancellation list decoder at different list sizes using different CRCs and conclude that it is important to adapt the CRC length to the list size in order to achieve the best error-rate performance of concatenated polar codes. Finally, we synthesize conventional successive cancellation decoders at large block-lengths with the same block-error probability as our proposed CRC-aided successive cancellation list decoders to demonstrate that, while our decoders have slightly lower throughput and larger area, they have a significantly smaller decoding latency.

I. INTRODUCTION

Polar codes offer efficient capacity-achieving decoding, but SC decoding is suboptimal at practical block lengths. This paper addresses numerical, hardware, CRC-design, and latency issues in SCL-based decoding.

  • SC decoding has vanishing block-error probability asymptotically but performs poorly at low-to-moderate block lengths because it is suboptimal.
  • SCL decoding improves error rates and supports CRC-concatenated polar codes whose performance can approach that of state-of-the-art LDPC codes.
  • Likelihood-based SCL implementations risk numerical underflow, while log-likelihood implementations introduce irregular memories and large processing elements.
  • The paper formulates SCL decoding in the LLR domain and uses its properties to simplify sorting and hardware implementation.
  • More than 100% higher throughput per unit area is reported relative to recent SCL decoder architectures.
  • CRC length should be adapted to list size because short CRCs can help small lists, whereas larger CRCs may degrade performance.

A. Polar Codes and Successive Cancellation Decoding

Polar coding transforms a binary-input channel into synthetic channels of differing reliability, then uses SC decoding to estimate information bits sequentially. The decoder computes decision LLRs through structured recursions with O(N log N) updates.

  • Polar Codes: Information bits occupy the least noisy synthetic channels, while the remaining indices are fixed to a known frozen vector.
  • SC Decoding: SC decoding estimates information bits successively, using preceding decisions as side information for later synthetic channels.
  • SC Decoding: The SC decoder performs a greedy one-pass tree search by selecting the child with maximum partial likelihood at each information-bit level.
  • SC Decoding: Decision LLRs are computed with f− and f+ recursions, requiring O(N log N) updates and tracking partial sums.

B. Successive Cancellation List Decoding

SCL decoding broadens SC’s greedy search into a bounded breadth-first search by retaining the most likely paths. Copy-on-write data structures reduce its complexity from naive quadratic scaling in N to O(L · N log N).

  • SCL decoding duplicates each surviving path in both possible directions at information-bit positions, then limits the number of active threads.
  • The decoder processes paths through a bounded breadth-first search rather than SC’s single greedy trajectory.
  • A naive SCL implementation requires at least Ω(L · N^2) complexity because path duplication copies data structures of size Ω(N).
  • Copy-on-write data structures exploit recursive computations to achieve O(L · N log N) decoding complexity.

C. CRC-Aided Successive Cancellation List Decoder

CRC-aided SCL decoding improves path selection by rejecting candidates that fail a CRC, while the paper develops an LLR-based path metric to make this process stable and hardware-efficient. The metric supports path ordering and sorting simplifications.

  • CRC-Aided SCL Decoding: CRC-aided SCL decoding appends CRC bits, discards paths failing the CRC, and selects the most likely remaining path without notably increasing computational complexity.
  • CRC-Aided SCL Decoding: The paper notes that some prior CRC-aided comparisons reduce effective information rate, making comparisons with standard SCL decoding unfair.
  • LLR-Based Path Metric: The LLR-based formulation replaces unstable likelihood computations and enables parallel stable LLR-based SC decoders with tracked path metrics.
  • LLR-Based Path Metric: Comparisons among 2L candidate paths cannot rely on decision LLRs alone, motivating path metrics that incorporate path history.
  • LLR-Based Path Metric: Path metrics can order decoding paths by likelihood, allowing the SCL decoder to compare candidates using metric values.
  • LLR-Based Path Metric: Frozen-bit metric updates can penalize an SC path after an earlier erroneous decision while leaving alternative paths unpenalized.

IV. SCL DECODER HARDWARE ARCHITECTURE

The proposed SCL decoder architecture operates entirely in the LLR domain and combines parallel SC decoding cores with path-management hardware for tree-search coordination.

  • The architecture consists of L parallel SC decoders and a path management unit coordinating the tree search.
  • Five units implement the decoder: memories, metric computation, metric sorting, address translation, and control.

A. LLR and Path Metric Quantization

The decoder quantizes LLRs with Q-bit signed precision and path metrics with M-bit unsigned precision, with M chosen to prevent overflow.

  • LLRs use a Q-bit signed uniform quantizer with step size ∆ = 1, while path metrics use M-bit unsigned quantization.
  • M = n + Q − 1 bits suffice because the maximum path metric is less than 2^(n+Q−1).

B. Metric Computation Unit

The metric computation unit uses L parallel SC decoder cores to compute decision LLRs, then updates and sorts path metrics while synchronizing memory updates.

  • The MCU contains L parallel SC decoder cores that compute the L decision LLRs using a semi-parallel SC architecture with P processing elements.
  • After decision LLR computation, the MCUs wait one clock cycle while updating and sorting the path metrics PM(i)_ℓ.
  • Partial-sum, path, and pointer memories are updated during the same cycle as path-metric updating and sorting.
  • Each decoder core reads input LLRs from one of L physical LLR memory banks using pointer-memory address translation.

C. Memory Unit

The memory unit separates shared channel-LLR storage from path-specific internal storage and uses crossbar-based copying or pointer translation to manage path duplication.

  • Channel LLRs remain fixed for a codeword, so the decoder stores only one copy in a memory N/P words deep and QP bits wide.
  • Internal intermediate-stage LLRs differ across paths, requiring L physical LLR memory banks with N−1 memory positions per bank.
  • All LLR memories have two read ports, allowing all P processing elements to read two Q-bit inputs simultaneously.
  • Path duplication copies N-bit path registers through N L × L crossbars and stalls decoding for one clock cycle.
  • Partial-sum duplication occurs in parallel with path-memory copying through N L × L crossbars during a single clock cycle.
  • Pointer-based virtual internal-LLR memories avoid costly internal-LLR copying, while the path metric sorter processes 2L candidate metrics and returns sorted metrics with path indices and bit values.

F. Control Unit

The decoder’s control and CRC units manage memory operations, path selection, and CRC tracking, while LLR-based metric properties simplify and accelerate candidate sorting.

  • Control and CRC units: The control unit generates memory addresses and includes codeword selection and an optional CRC unit.
  • Control and CRC units: CRC memories are updated for information bits, copied when paths are duplicated, and used to select the lowest-metric passing path.
  • Pruned radix-2L sorter: The pruned sorter also reduces sorting logic complexity and maximum path delay, but requires L−1 (2L−2)-to-1 multiplexers.
  • Pruned radix-2L sorter: The pruned radix-2L sorter uses (L−1)2 comparators to find the L smallest candidates by removing known or irrelevant comparisons.
  • Pruned radix-2L sorter: Because existing path metrics may become unsorted across frozen-bit clusters, additional sorting steps restore the assumption before later information-bit clusters.

C. Latency of Metric Sorting

The implementation study measures sorting latency and decoder efficiency under a common synthesis setup, while also evaluating floating-point and fixed-point SCL performance across SNR.

  • Latency: Metric-sorting latency with the pruned sorter depends on the number of information bits and frozen-bit clusters, adding sorting steps after contiguous frozen sets.
  • Implementation results: The synthesis comparison uses TSMC 90 nm, P = 64 processing elements per SC core, and throughput per unit area as the hardware-efficiency metric.
  • Implementation results: The study compares the proposed LLR-based decoder with prior LL-based architectures, examines the pruned sorter, and evaluates CRC-aided SCL effectiveness.
  • Quantization: Figure 5 reports FER versus SNR for floating-point and fixed-point LL-based and LLR-based SCL decoders on a (1024, 512) polar code.
  • Quantization: Fixed-point simulations use the min-sum approximation and an approximated path-metric update, whereas floating-point simulations use the exact decoder implementation.
  • Quantization: LL-based and LLR-based SCL have practically indistinguishable FER with Q = 4 and Q = 6 bits respectively, while lower quantization degrades performance significantly.

B. Gains due to LLR-based Formulation of SCL Decoding

The LLR reformulation reduces decoder area and improves throughput while enabling sorter pruning, whose benefit depends on list size. Comparisons show substantial hardware-efficiency gains over LL-based architectures, alongside CRC design trade-offs.

  • B. Gains due to LLR-based Formulation of SCL Decoding: The LLR-based and LL-based architectures isolate the hardware gains attributable to reformulating SCL decoding in the LLR domain.The comparison uses architectures that are otherwise identical except for LL versus LLR representation.
  • B. Gains due to LLR-based Formulation of SCL Decoding: 36%, 33%, and 28% smaller area is achieved for list sizes L = 2, L = 4, and L = 8, respectively, versus the LL-based decoder.Memory provides the largest absolute savings, while the MCU has the largest relative reduction, averaging 79%.
  • B. Gains due to LLR-based Formulation of SCL Decoding: 7%, 3%, and 2% higher operating frequency is achieved for L = 2, L = 4, and L = 8, respectively, versus the LL-based decoder.For a (1024, 512) polar code, the full-sorter decoder requires 2592 cycles.
  • B. Gains due to LLR-based Formulation of SCL Decoding: 67%, 55%, and 40% better hardware efficiency results for L = 2, L = 4, and L = 8, respectively, from the LLR-based reformulation.The LLR formulation also reduces comparator bit-width, although sorting logic increasingly dominates sorter area as L grows.
  • D. Comparison with LL-based SCL Decoders: 137%, 118%, and 120% better hardware efficiency is obtained for L = 2, L = 4, and L = 8, respectively, versus the LL-based decoder of.The LLR-based decoder also has approximately 28% smaller area and up to 70% higher throughput than.
  • 2) Comparison with [22]:: 115% and 142% better hardware efficiency is obtained for L = 2 and L = 4, respectively, versus, although the comparison is affected by technology scaling.The decoder is approximately 57% smaller; throughput is 7% lower for L = 2 and 6% higher for L = 4.

1) Choice of CRC:

The best CRC length depends on the SCL list size: shorter CRCs suit L = 2, CRC-8 suits L = 4, and CRC-16 suits L = 8. CRC-aided decoding substantially improves FER, with only a small throughput reduction and low CRC hardware cost.

  • For L = 2, the smallest CRC is best; longer CRCs degrade performance at Eb/N0 ≤ 3 dB and offer no significant high-SNR gain over CRC-4.
  • For L = 4, CRC-8 is most beneficial: it matches CRC-4 below 2.25 dB, improves FER more at higher SNRs, and outperforms CRC-16 in the low-SNR regime.
  • For L = 8, CRC-16 is best, significantly outperforming CRC-4 and CRC-8 for Eb/N0 > 2.5 dB, while all three perform similarly at lower SNRs.
  • CRC-aided SCL decoders perform significantly better than standard SCL decoders for list sizes L = 2, 4, and 8.
  • Adding CRC bits reduces decoder throughput by at most 0.4%, while the CRC unit occupies less than 1 µm^2 and does not affect maximum operating frequency.
  • For Eb/N0 > 2.5 dB, CA-SCLD with L = 2 has lower FER than standard SCL with L = 8 and provides more than five times higher hardware efficiency.

VII. DISCUSSION

The discussion compares shorter CRC-aided SCL decoders with longer conventional SC decoders at comparable block-error probabilities. Although SC offers higher throughput and SCL incurs larger area, LLR-based SCL decoding substantially reduces per-codeword latency and improves hardware efficiency.

  • A. SC Decoding or SCL Decoding?: CA-SCLD at N = 1024 matches the block-error performance of SC decoding at N = 2048 with L = 2 and N = 4096 with L = 4.The comparisons use modified (1024, 512) polar codes under CA-SCLD and longer conventional polar codes under SC decoding.
  • A. SC Decoding or SCL Decoding?: 15% larger area is occupied by the SCL decoders, primarily because partial-sum copying and path memories still use area-intensive L × L crossbars.Eliminating these crossbars is identified as an open architectural problem.
  • A. SC Decoding or SCL Decoding?: 27% higher throughput is achieved by the corresponding SC decoders, due to slightly higher frequency and approximately 20% lower per-bit latency.The lower per-bit latency is attributed to the sorting step required in SCL decoding.
  • A. SC Decoding or SCL Decoding?: 38% and 68% lower per-codeword latency are achieved by the N = 1024 SCL decoders with L = 2 and L = 4, respectively, compared with SC decoders at N = 2048 and N = 4096.These latency reductions come at a small area cost relative to the corresponding SC decoders.
  • B. Simplified SC and SCL Decoders: Up to 137% higher hardware efficiency is reported for the LLR-based SCL decoder than for existing decoders, while CRC-aided decoding improves efficiency by enabling smaller list sizes.The LLR-based path metric also supports numerically stable decoding and a pruned radix-2L sorter.
Loading 1401.3753v4…