PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Polar Decoders: Algorithm and Implementation

Gabi Sarkis, Pascal Giard, Alexander Vardy, Claude Thibeault, Warren J. Gross

arXiv:1307.7154v2cs.ARcs.IT

TL;DR

Polar decoding needs higher throughput because SC decoding is serial and can be impractical for systems. The paper develops a flexible decoder using direct decoding of additional constituent codes, achieving gigabit-per-second FPGA throughput with reduced latency relative to SC-based designs.

  • Problem

    Serial successive-cancellation decoding limits polar-decoder throughput, while list-CRC decoding is not directly compatible with the proposed single-estimate techniques.

  • Method

    The paper develops a flexible high-throughput polar decoder by directly decoding additional constituent-code classes and implementing the resulting architecture on an FPGA.

  • Results

    1 Gbps information throughput is achieved on an FPGA for a (32768, 29492) polar code at 108 MHz, with substantially higher throughput than SC-based decoders.

  • Takeaways & Limitations

    The results indicate that polar codes are promising candidates for data storage systems and can achieve high throughput with a flexible decoder.

Abstract

from arXiv · show

Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. This work aims to increase the throughput of polar decoder hardware by an order of magnitude relative to the state of the art successive-cancellation decoder. We present an algorithm, architecture, and FPGA implementation of a gigabit-per-second polar decoder.

I. Introduction

Polar codes combine explicit construction and asymptotic capacity achievement with low-complexity decoding, but short-to-moderate lengths and serial SC decoding limit practical performance and throughput. The paper addresses these drawbacks by directly decoding additional constituent-code classes in a flexible high-throughput FPGA decoder.

  • I. Introduction: Polar codes explicitly achieve the symmetric capacity of memoryless channels and offer low error floors and low-complexity implementations.Their large stopping distance contributes to the low error floor.
  • I. Introduction: Short-to-moderate polar codes can underperform LDPC codes, while serial successive-cancellation decoding limits throughput.The paper identifies both error-correction performance and decoding throughput as practical drawbacks.
  • I. Introduction: Longer polar codes can provide error-correction performance comparable to similar-rate LDPC codes with lower decoder complexity.The paper highlights a (32768, 27568) polar code compared with the (2048, 1723) 10GBASE-T LDPC code.
  • I. Introduction: SSC and ML-SSC improve throughput by exploiting polar-code recursion to decode suitable constituent codes directly.SSC handles rate-0 and rate-1 constituents, while ML-SSC also directly decodes smaller constituents.
  • I. Introduction: The proposed decoder recognizes additional directly decodable constituent classes, achieving 40× speedup over SC and more than 8× over the state-of-the-art polar decoder on the same FPGA.It remains flexible and can decode any polar code of a given length.
  • I. Introduction: The evaluation focuses on two length-32768 codes: a rate-0.9 code for storage systems and a code matched to the 10GBASE-T LDPC rate.The latter supports implementation-complexity comparison.

B. Successive-Cancellation Decoding

Successive-cancellation decoding estimates polar-code bits sequentially from channel observations and previously estimated bits using recursively computed LLRs. Its serial nature limits throughput, motivating pruning and direct constituent decoding; performance comparisons also examine polar codes against same-rate LDPC decoding.

  • B. Successive-Cancellation Decoding: SC sequentially estimates each bit using the channel output and previously estimated bits.The bit estimates are denoted ˆu_i and depend on prior decisions.
  • B. Successive-Cancellation Decoding: The decoder represents soft information with LLRs that are recursively calculated using the min-sum approximation.The LLR is defined as a likelihood ratio conditioned on the channel output and prior estimates.
  • B. Successive-Cancellation Decoding: The min-sum update computes λ_u0 from the signs and minimum magnitude of λ_v0 and λ_v1.This is the f-function used in the recursive calculation.
  • B. Successive-Cancellation Decoding: The g-function combines λ_v0 and λ_v1 differently according to the prior estimate ˆu0.The sign of λ_v0 is changed when ˆu0 = 1.
  • B. Successive-Cancellation Decoding: For low error rates, a suitably constructed (32768, 27568) polar code can outperform the (2048, 1723) LDPC code, while combinations of polar codes can help at higher error rates.The comparison uses equal-rate codes over the binary-input AWGN channel with BPSK modulation.
  • B. Successive-Cancellation Decoding: List-CRC decoding with list size 32 and a 32-bit CRC brings the short polar code to similar performance with LDPC, but is outside this work’s single-estimate techniques.The paper identifies adaptation of the throughput techniques to list decoding as future research.
  • B. Successive-Cancellation Decoding: SC throughput is constrained by serial decoding, with 26 Mbps reported for the FPGA-based length-32768 decoder.The fastest cited ASIC implementation reaches 48.75 Mbps for a (1024, 512) code at 150 MHz.

III. SSC and ML-SSC Decoding

SC decoding represents a polar code as a recursive binary tree, while SSC and ML-SSC prune the tree by directly decoding suitable constituent codes. ML-SSC extends this pruning with resource-constrained maximum-likelihood decoding of additional constituent codes.

  • Tree structure: A polar code of length N is represented as a binary tree because it recursively concatenates two constituent codes of length N/2.Each node corresponds to a constituent code, with frozen and information leaves represented separately.
  • Tree structure: Each decoder node propagates soft-valued inputs downward and combines child codeword estimates to produce its output estimate.The root receives channel LLRs, and the decoder outputs the estimated systematic codeword.
  • SSC decoding: SSC prunes all-frozen subtrees to zero vectors and all-information subtrees through threshold detection, reducing node visits and latency.The remaining mixed-rate nodes retain the recursive calculations.
  • ML-SSC decoding: ML-SSC additionally uses exhaustive-search maximum-likelihood decoding for constituent codes that satisfy resource constraints.This further prunes the decoder tree beyond SSC.
  • ML-SSC decoding: 7 time steps are required for the (8, 3) ML-SSC decoder when maximum-likelihood nodes are constrained to Nv = 2.The corresponding decoder tree marks these nodes as NML nodes.

C. Performance

The section evaluates throughput-oriented constituent-node decoding and its practical implementation under a memory-access resource constraint. It reports large throughput gains while preserving the polar code, and examines SPC-node prevalence and latency across code rates.

  • Performance: 20 times higher information throughput is estimated for ML-SSC than SC decoding at 100 MHz for a rate-0.9, length-32768 polar code.The reported throughputs are approximately 910 Mbit/s for ML-SSC and 45 Mbit/s for SC.
  • Performance: 520 Mbit/s remains achievable when the same rate-0.9, length-32768 code is constructed for Eb/N0 = 5.0 dB instead of 3.47 dB.The decoder remains 11 times faster than SC at the same 100 MHz clock frequency.
  • Implementation constraint: The proposed transformations and mergers preserve the polar code's frozen and information-bit locations.Throughput improvements from modifying the code itself are outside this preserved-code design.
  • Implementation constraint: The implementation defines P so that 2P is the maximum number of memory elements accessed simultaneously.This generalizes the processing-element interpretation while retaining compatibility when each processing element has two inputs.
  • SPC nodes: 12 steps are required for the specialized SPC decoder versus 46 steps for SSC on a length-4096 SPC code with P = 256 and c = 4.For larger SPC codes, the specialized decoder requires Nv/(2P) + c steps, while SSC uses a longer tree traversal.
  • SPC nodes: Large SPC nodes are prevalent in high-rate polar codes, and their proportion decreases as the code rate decreases.Table I compares SPC-node counts by size for three length-32768 codes with rates 0.9, 0.8413, and 0.5.

B. Repetition Nodes NREP

Repetition nodes decode constituent codes whose only unfrozen bit is the last bit by summing inputs, detecting the sum sign, and replicating the resulting bit. Prediction-based variants reduce latency further, while repetition nodes remain useful across code rates.

  • Repetition-node decoding: Repetition-node decoding sums all input values, applies sign-based threshold detection, and replicates the detected result across the constituent output.This directly decodes a constituent code in which only the last bit is unfrozen.
  • Latency reduction: 75% average latency is achieved by a prediction method that initially sets all output bits to zero and rewrites them only when the sum is negative.A second prediction method similarly reaches 75% of the latency of the basic method.
  • Code-rate dependence: Repetition nodes are more prevalent in lower-rate polar codes, whereas SPC nodes have a more pronounced latency impact in high-rate codes.Despite the smaller tree reduction from repetition nodes, their latency impact is measurable and motivates their inclusion.

C. Repetition-SPC Nodes NREP-SPC

The proposed decoder identifies frequent NREP-SPC constituent codes and decodes them in parallel using repetition and SPC operations, reducing latency without exhaustive search.

  • NREP-SPC structure: NREP-SPC codes combine a repetition left constituent with an SPC right constituent and dominate short constituent-code enumerations.For length-8 rate-regular nodes, they account for 28% and 25% of NR nodes in the two studied codes.
  • NREP-SPC decoding: Two length-4 SPC decoders process hypotheses corresponding to repetition outputs 0 and 1, while the repetition decoder selects the appropriate result.
  • Complexity: The proposed NREP-SPC decoder has significantly lower complexity than exhaustive-search maximum-likelihood decoding.
  • Node mergers: Merging NREP and NSPC operations allows the decoder to generate NREP-SPC outputs without tree traversal.
  • Decoder functions: The decoder implements 12 functions, using child-rate notation and direct calculations enabled by rate-0 or rate-1 children.

F. Performance with Quantization

Quantization determines the decoder’s error-correction and memory trade-off, while the implementation uses instruction-driven hardware and buffering to support flexible high-throughput decoding.

  • Quantization performance: (7, 5, 1) quantization performs extremely close to floating point, whereas (7, 4, 1) significantly degrades error-correction performance.The quantization tuple is (W, Wc, F), denoting internal bits, channel bits, and fractional bits.
  • Quantization performance: (6, 4, 0) remains within 0.1 dB of floating point across the studied Eb/N0 range for the (32768, 27568) code.
  • Quantization choice: Six internal integer bits and four channel integer bits are sufficient, while fractional bits have a small performance effect.
  • Quantization choice: The (6, 4, 0) scheme reduces memory use with a small performance reduction and is recommended for practical high-rate decoders.
  • Control architecture: An offline instruction list controls the decoder functions, allowing new code-specific function lists to be loaded without reducing flexibility.
  • Buffering trade-off: Including input and output buffers preserves flexibility and full-throughput support across a wider range of codes, especially at high rates.

VI. Architecture: Data Loading and Routing

The architecture separates channel and internal data memories, uses dual-port buffering for loading during decoding, and routes parallel LLR and bit data to sustain throughput.

  • Data loading: The design supplies channel outputs in groups of 32 LLRs, requiring 1024 loading cycles for a length-32768 frame.
  • Data loading: Dual-port channel RAM stores two frames so one frame can be decoded while the next is loaded, then swaps read and write locations.
  • Memory organization: The channel RAM uses 16 banks, each 128 deep and 160 bits wide, to support parallel access while keeping the input bus practical.
  • Memory organization: Separating channel and internal α memories is necessary to avoid stalling frame loading because internal-memory ports are simultaneously used by decoding.
  • Data loading trade-offs: Replacing channel values after use provides insufficient loading time for the rate-0.9 code at full throughput without a wider input bus or faster loading clock.
  • Memory organization: The α-RAM uses two P-LLR-wide memories, with registered forwarding supplying the newest value when read and write addresses coincide.
  • Memory organization: β-RAM uses two dual-port memories of width 2P bits, while simultaneous reads and writes prevent narrower-memory utilization through consecutive-address writes.

D. Estimated Codeword

The decoder buffers estimated codeword bits and uses dedicated routers and specialized processing hardware to support parallel execution and continuous frame handling.

  • Estimated codeword buffering: Estimated codeword bits are generated in 512-bit groups, buffered in codeword RAM, and read through a narrower 256-bit bus.The buffer permits immediate decoding of the following frame and constant-rate output reads.
  • Estimated codeword buffering: Codeword RAM remains separate from internal β memory because sharing ports would stall full-speed decoding during estimated-codeword reads.
  • Routing: The α- and β-routers determine memory selection and addresses for parallel data movement between memories and the processing unit.
  • Data processing unit: Specialized hardware blocks implement the decoder functions as instruction-selected operations in the data processing unit.
  • Data processing unit: The architecture uses multiplexers to select zero vectors, f or g outputs, β outputs, and COMBINE inputs according to the executed opcode.
  • Timing-critical logic: The critical path passes through g, SPC, and COMBINE, motivating fast implementations and a two’s-complement implementation of g.

A. The f and g Blocks

The decoder implements f and g operations with two’s-complement arithmetic, while specialized repetition, SPC, and repetition-SPC blocks decode constituent codes directly. These choices simplify constituent-code processing, but arithmetic range and critical-path effects shape the implementation.

  • Arithmetic blocks: Two’s-complement f and g blocks directly implement the required operations, with saturation applied in g and a restricted negative range in f.The range restriction gives LLR magnitudes Q −1 bits, and the g element saturates at 2Q−1 and −2Q+1.
  • Arithmetic blocks: The f block’s slower two’s-complement implementation does not limit overall clock frequency because its path is short.
  • Arithmetic blocks: Bit-reversed indexing lets f and g operate on adjacent input α values and places outputs correctly without extra multiplexing rules.A non-bit-reversed implementation would increase routing complexity without positive effects.
  • Constituent decoders: The repetition decoder uses a four-level adder tree for constituent codes up to length 16, repeating the sign of the accumulated input as the decoded value.The tree uses two’s-complement arithmetic and combinational logic.
  • Constituent decoders: A sign-majority simplification significantly reduces error-correction performance without perceptibly reducing decoder resource utilization.
  • Constituent decoders: The repetition-SPC block computes candidate SPC inputs in parallel, selects between SPC outputs using the repetition decision, and combines the decoded bits.This node is purely combinational and uses four f elements, eight g elements, two SPC nodes, and one repetition node.

D. Single-Parity-Check Block

The SPC block uses pipelined compare-select logic to decode constituent codes across a wide length range, while the FPGA evaluation compares throughput, resources, and clocking against prior decoders. The proposed design reaches gigabit-scale throughput and substantially exceeds SC-based alternatives, with resource trade-offs against TPSC.

  • D. Single-Parity-Check Block: The SPC block handles constituent lengths [4, 8192] using a compare-select tree to identify the least reliable input bit.Small codes can complete in one cycle, whereas larger inputs require multiple cycles and pipeline-stage selection.
  • D. Single-Parity-Check Block: One extra pipeline clock cycle improves operating frequency and overall throughput.The same pipeline structure is used for parity values.
  • D. Single-Parity-Check Block: Length-4 maximum-likelihood decoding is retained because longer ML nodes form a critical path and become minor after repetition, SPC, and repetition-SPC decoders are introduced.The decoder evaluates four possible codewords using adder and comparator trees.
  • D. Single-Parity-Check Block: The implementation was validated against a bit-accurate software decoder using functional and gate-level simulations with random test vectors.The software model estimated error-correction performance and acceptable quantization levels.
  • D. Single-Parity-Check Block: 1 Gbps information throughput is achieved for the rate-0.9 code under both reported quantization schemes.For the (32768, 27568) code, throughput is 15 to 29 times that of semi-parallel SC; for the rate-0.9 code, it is 19 to 40 times higher depending on P and quantization.
  • D. Single-Parity-Check Block: 16 to 34 times higher throughput is achieved than the maximum possible semi-parallel SC throughput for the (32768, 29492) code.The comparison uses the asymptotic SP-SC throughput limit 0.5 · fclk · R.
  • D. Single-Parity-Check Block: Eight times faster throughput is achieved than TPSC, while using 1.7 times the LUTs, 1.2 times the registers, and 1.4 times the RAM when both designs buffer two frames.At P = 256, the proposed decoder reaches approximately 1.1 Gbps information throughput.

C. Comparison with an LDPC code of similar error correcting performance

The paper compares its FPGA polar decoder with a fully parallel FPGA LDPC decoder offering similar error-correction performance. The polar design uses fewer LUTs but achieves lower information throughput in this comparison.

  • C. Comparison with an LDPC code of similar error correcting performance: 1.1 Gbps information throughput is reached by the fully-parallel (2048, 1723) LDPC decoder on the comparison FPGA.The result is reported at 30.7 MHz on a Xilinx Virtex VI XC6VLX550TL.
  • C. Comparison with an LDPC code of similar error correcting performance: 5 times fewer LUTs are required by the proposed polar decoder, but its information throughput is half that of the LDPC decoder.The comparison uses a (32768, 27568) polar code implemented on the same FPGA as the LDPC decoder.
  • C. Comparison with an LDPC code of similar error correcting performance: The proposed algorithm produces a high-throughput, flexible polar decoder, with an FPGA implementation achieving 1 Gbps for a (32768, 29492) code.The conclusion frames the result as evidence relevant to polar decoders for data storage systems.
Loading 1307.7154v2…