PaperlayerView exact revision on arXiv

Source-linked AI summary

Hardware Architecture for List SC Decoding of Polar Codes

A. Balatsoukas-Stimming, A. J. Raymond, W. J. Gross, A. Burg

arXiv:1303.7127v3cs.ITcs.ARmath.IT

TL;DR

List SC decoding improves error-correcting performance but carries a cumbersome likelihood-copying step. This paper presents a list SC decoder architecture that avoids copying likelihood values by copying pointers instead. The paper reports this pointer-based approach and the first list SC decoder architecture in the literature.

  • Problem

    List SC decoding offers improved error-correcting performance at increased complexity, but its likelihood-copying step was burdensome and no decoder architecture had been reported.

    Source: §I · p. 1

  • Method

    The decoder uses pointer references to state memories so paths can share stored likelihoods without copying the likelihood values.

    Source: §III · p. 2, A. Low-Complexity State Copying · p. 3

  • Results

    The paper presents the first list SC decoder architecture in the literature and describes avoiding intermediate-likelihood copying by copying pointers instead.

    Source: §V · p. 5

  • Takeaways & Limitations

    Copying references to state memories instead of likelihood values provides a way to avoid the list SC algorithm’s likelihood-copying step.

    Source: A. Low-Complexity State Copying · p. 3

Abstract

from arXiv · show

We present a hardware architecture and algorithmic improvements for list SC decoding of polar codes. More specifically, we show how to completely avoid copying of the likelihoods, which is algorithmically the most cumbersome part of list SC decoding. The hardware architecture was synthesized for a blocklength of N = 1024 bits and list sizes L = 2, 4 using a UMC 90nm VLSI technology. The resulting decoder can achieve a coded throughput of 181 Mbps at a frequency of 459 MHz.

I. INTRODUCTION

The introduction frames list SC decoding as an error-performance improvement with added complexity and an unresolved likelihood-copying burden. The paper presents a list SC architecture and pointer-based copying avoidance, alongside background on polar-code construction.

I. INTRODUCTION

  • List SC decoding improves error-correcting performance but adds complexity, and its likelihood-copying step had no published architecture in the literature.Stack SC is described as less attractive because of high memory requirements, costly metric normalization, and non-deterministic latency.Source: §I · p. 1

Contribution and Outline:

  • The paper presents a list SC decoder architecture and avoids copying intermediate likelihood values by copying pointers instead.The outline assigns algorithmic improvements to Section III and the hardware architecture to Section IV.Source: Contribution and Outline · p. 1

II. POLAR CODES

  • Polar codes are constructed by recursively applying a polarizing transform to a binary input symmetric and memoryless channel.The transform is represented by a 2 × 2 matrix F; its n-fold application gives G = F^⊗n.Source: §II · p. 1

A. Successive Cancellation Decoding

Successive cancellation decodes bits sequentially, using earlier decisions to estimate each next bit. Pairwise likelihood computations follow the code’s dependency graph, yielding O(N log N) complexity when intermediate likelihoods are stored.

A. Successive Cancellation Decoding

  • SC estimates each bit using the received word and the previously decoded bits, then makes a hard decision.The recursive decoding process is illustrated for N = 4.Source: A. Successive Cancellation Decoding · p. 1
  • The decoder combines incoming likelihood pairs at each dependency-graph node using the f or g operation.The graph has N log N nodes grouped into log N stages.Source: A. Successive Cancellation Decoding · p. 1
  • O(N log N) is the computational complexity of SC decoding when intermediate likelihoods are stored.Partial sums are linear combinations of previously decoded codeword bits.Source: A. Successive Cancellation Decoding · p. 2

B. List SC Decoding

List SC searches the decoding tree while retaining multiple candidate paths, allowing it to recover from decisions that single-path SC cannot revisit. Simulations show non-negligible gains at FER 10^-2, with diminishing returns from larger lists in the reported settings.

B. List SC Decoding

  • List SC performs a breadth-first search, retaining the L highest-metric paths from the 2L candidates after each non-frozen bit.The surviving path with the highest metric is selected at bit N.Source: B. List SC Decoding · p. 2
  • Unlike SC’s single path, list SC tracks multiple paths and can preserve alternatives to earlier decisions.SC’s erroneous decisions cannot be recovered later; Fig. 2 depicts SC and list SC paths for L = 2.Source: B. List SC Decoding · p. 2
  • At FER 10^-2, list SC’s gain is non-negligible, while returns are small for L > 4 and L > 2 provides almost no gain at high SNR.The comparison uses a (1024, 512) polar code over an AWGN channel, with 10^7 Monte Carlo simulations per data point.Source: Figure 3 · p. 2, B. List SC Decoding · p. 2

III. ALGORITHMIC CONSIDERATIONS

The algorithm avoids copying intermediate likelihoods by using an auxiliary pointer memory to track their locations. Its stage updates and path computations expose parallel work for hardware implementation.

III. ALGORITHMIC CONSIDERATIONS

  • An auxiliary pointer memory avoids the high complexity of copying intermediate likelihoods during list SC decoding.The algorithm instead tracks likelihood-memory references; partial sums and paths use straightforward copying.Source: §III · p. 2
  • The algorithm stores likelihoods, partial sums, and paths per path, while path selection retains the L best of 2L metrics.The path-selection outputs include the selected parent indices and corresponding bit values.Source: §III · p. 2
  • For each bit, LISTSC updates stages below the current stage, with path-loop iterations and stage-node updates available in parallel.Lines 4–10 can run in parallel, as can updates across the 2^s nodes at stage s.Source: §III · p. 3

A. Low-Complexity State Copying

The pointer memory lets each surviving path find its likelihoods by stage without copying the likelihood contents. This is needed because stages for a new path can reside in different state memories.

A. Low-Complexity State Copying

  • A new path may need unprocessed likelihood stages from one state memory and already updated stages from another.This occurs because the SC procedure does not process every decoding-graph stage for each bit.Source: A. Low-Complexity State Copying · p. 3
  • The pointer memory has dimension L×(log N − 1) and tracks which memory holds each path’s likelihoods at each stage.After path selection, copying the references in the pointer memory is sufficient instead of copying likelihood contents.Source: A. Low-Complexity State Copying · p. 3
  • Instead of copying the likelihoods when paths are selected, the algorithm copies their state-memory references.The example has L = 2, with u1 and u2 non-frozen and u3 and u4 frozen.Source: A. Low-Complexity State Copying · p. 3

B. Likelihood Representation

The decoder uses negative log-likelihoods rather than converted LLRs to preserve path-metric ordering. It also simplifies likelihood calculations by factoring out common terms and approximating the f function.

B. Likelihood Representation

  • LLR-to-LL conversion can alter path-metric ordering because the normalization factors differ, so the decoder represents likelihoods in LL form.Negative LLs are positive and need no sign bit, but require more storage.Source: B. Likelihood Representation · p. 3
  • The passage defines μ(x_i) = 1 − 2x_i for binary codeword bits x_i ∈ {0, 1}, calling it the modulated version of the codeword bit before introducing negative-LL forms.Source: B. Likelihood Representation · p. 3
  • The update equations use min* for one likelihood combination and add the partial sum to the paired inputs for the other.The supplied passages give the update expressions for both functions.Source: B. Likelihood Representation · p. 3
  • For the used blocklength and list sizes, omitting the ln(·) term in f makes practically no performance difference; at N = 2^15 the loss is approximately 0.1 dB.The passage reports that the loss grows slightly as blocklength increases.Source: B. Likelihood Representation · p. 3
  • Common constant terms can be recursively factored out without changing path-metric ordering, allowing LL(x_i) = (y_i − μ(x_i))^2.The simplified expression is easier to handle in quantization.Source: B. Likelihood Representation · p. 4

IV. LIST SC DECODER ARCHITECTURE

The proposed decoder combines metric computation, state memories, and path selection. The metric computation unit uses L SC cores, with pointer-controlled likelihood routing and a sorter for the best paths.

IV. LIST SC DECODER ARCHITECTURE

  • The architecture has a metric computation unit, a state-memories component, and a path-selection component.The state-memories component consists of L state memories used by the MCU to compute 2L path metrics.Source: §IV · p. 4
  • The metric computation unit contains L SC decoder cores that calculate metrics using the supplied path states.Multiplexers route the likelihoods to the cores according to pointer-memory entries.Source: §IV · p. 4
  • Path selection sorts 2L metrics to find the L best, while the pointer memory manages the cores’ memory reads.The sorter also returns the path index and bit value associated with each selected metric.Source: §IV · p. 4

A. LL Quantization

The LL quantization scheme avoids saturation by increasing the storage width by one bit per stage, leaving channel-LL quantization as the source of performance degradation. The decoder uses Qch = 3 because its degradation is very small relative to floating-point and Qch = 4 implementations.

A. LL Quantization

  • Adding one storage bit per stage avoids LL saturation, so only channel-LL quantization degrades performance relative to floating point.As SC decoding moves toward stage 0, positive LLs have increasing dynamic range, and saturated pairs are useless for decisions.Source: A. LL Quantization · p. 4
  • Qch = 3 has very small performance degradation relative to floating-point and Qch = 4 implementations.The quantization step is ∆ = 1; Fig. 6 shows FER performance for a (1024, 512) code with L = 2.Source: A. LL Quantization · p. 4, Figure 6 · p. 4

B. Metric Computation Unit

The metric computation unit uses parallel SC decoder cores to compute path metrics, while shared channel likelihoods and copied state memories support the list paths.

B. Metric Computation Unit

  • L SC decoder cores each use P processing elements to calculate path metrics, with control and memory addresses driven by (i, s, ps).The design uses P = 64; the cores implement both f and g, and the pointer memory redirects the correct likelihoods to each core.Source: B. Metric Computation Unit · pp. 4–5

C. State-Memory

  • One channel-LL memory is shared across decoder cores, while the remaining likelihood-memory pairs are distinct for each path.The stated total for likelihood storage is (L + 1)N memory-position pairs.Source: C. State-Memory · p. 5
  • Each path has partial-sum and path memories; crossbars copy their contents among the L memories to complete state copying in one cycle.These memories contain 2LN bits in total.Source: C. State-Memory · p. 5
  • The total state-memory bit count is given by Btot = (2L + 2)NQch + 2L(3N − log N − Qch − 2).Source: C. State-Memory · p. 5

D. Path Selection

The path-selection sorter selects the L smallest of 2L metrics in one cycle. Registering its output adds cycle overhead but increases throughput through a higher clock frequency.

D. Path Selection

  • The radix-2L sorter finds the L smallest metrics among 2L values and occupies 0.1% of decoder area for L = 2 and 0.8% for L = 4.It uses 2L(2L − 1)/2 comparators of Qmax-bit quantities.Source: 1) Metric Sorter · p. 5
  • Decoding pauses for an idle cycle whenever sorter output is needed, which occurs RN times per codeword.Source: 1) Metric Sorter · p. 5
  • Despite an overhead of approximately RN cycles, registering the sorter output increases throughput through a higher clock frequency.The overhead is approximately 50R percent when the second term is ignored.Source: 1) Metric Sorter · p. 5

2) Pointer Memory:

The pointer memory provides the likelihood redirection functionality with a small storage footprint. The work presents the first list SC decoder architecture and avoids copying intermediate likelihoods by copying pointers instead.

2) Pointer Memory:

  • For N = 1024 and L = 2 or 4, the pointer memory requires 18 or 72 bits, respectively, and also provides copying functionality.Its size is described as negligible.Source: 2) Pointer Memory · p. 5

V. SYNTHESIS RESULTS & CONCLUSION

  • The synthesis evaluation uses UMC 90nm CMOS at N = 1024 and L = 2 or 4, comparing the design with existing SC decoder synthesis and chip results.The comparison is motivated by the absence of other list SC decoder architectures in the literature.Source: §V · p. 5
  • Copying pointers instead of intermediate likelihood values avoids the likelihood-copying step in the first presented list SC decoder architecture.Source: §V · p. 5
Loading 1303.7127v3…