Source-linked AI summary
Hardware architectures for Successive Cancellation Decoding of Polar Codes
Camille Leroux, Ido Tal, Alexander Vardy, Warren J. Gross
TL;DR
Polar-code SC decoding requires practical hardware architectures beyond the original algorithmic framework. The paper develops shared-resource, overlapping, and logarithmic-domain architectures, showing O(n) processing and memory elements with constant throughput and reduced arithmetic complexity.
Problem
The paper addresses efficient hardware implementation of successive cancellation decoding for polar codes.
Method
The paper uses FFT-like scheduling to design pipelined-tree, line, vector-overlapping, and logarithmic-domain SC-decoder architectures.
Results
The proposed architectures match the FFT-like decoder's throughput with lower hardware complexity, while vector overlapping enhances throughput.
Takeaways & Limitations
SC decoders can exploit scheduling, resource sharing, codeword overlap, and log-domain computation to improve hardware efficiency and throughput.
Takeaways & Limitations
The analysis assumes a binary-input, symmetric, memoryless channel and code lengths n = 2^m.
Abstract
from arXiv · showhide
The recently-discovered polar codes are widely seen as a major breakthrough in coding theory. These codes achieve the capacity of many important channels under successive cancellation decoding. Motivated by the rapid progress in the theory of polar codes, we propose a family of architectures for efficient hardware implementation of successive cancellation decoders. We show that such decoders can be implemented with O(n) processing elements and O(n) memory elements, while providing constant throughput. We also propose a technique for overlapping the decoding of several consecutive codewords, thereby achieving a significant speed-up factor. We furthermore show that successive cancellation decoding can be implemented in the logarithmic domain, thereby eliminating the multiplication and division operations and greatly reducing the complexity of each processing element.
1. INTRODUCTION
Polar codes combine explicit construction with efficient encoding and decoding, and asymptotically achieve channel capacity under binary-input, symmetric, memoryless channels. This paper develops lower-complexity SC-decoder hardware, higher-throughput codeword overlap, and logarithmic-domain computation.
- Polar codes achieve channel capacity asymptotically for binary-input, symmetric, memoryless channels.
- The paper targets SC-decoder hardware complexity O(n), improving on the O(n log2 n) decoding complexity framework.
- Overlapping several consecutive codewords is proposed to increase decoding throughput.
- Logarithmic-domain computation eliminates multiplication and division operations in the computational nodes.
- Approximating the resulting transcendental functions with the minimum function causes negligible performance degradation.
2. POLAR CODES
Polar codes use an FFT-structured encoder and successive cancellation decoding for binary-input, symmetric, memoryless channels. Their construction freezes unreliable input positions, while decoding estimates input bits sequentially from channel outputs.
- Polar codes are linear block error-correcting codes with code length n = 2^m.
- The encoder has an FFT structure, with input-bit ordering represented in bit-reversal order.
- Successive cancellation decoding estimates u0 through u_n−1 sequentially from the received channel output y.
- Polarization makes most bit-estimation probabilities either extremely close to 1 or extremely close to 1/2 as n increases.
- Unreliable input positions are frozen to zero, so they carry no transmitted information.
3. SUCCESSIVE CANCELLATION DECODER IMPLEMENTATION
The paper exploits successive-cancellation scheduling to build hardware architectures with shared processing and memory resources. These designs preserve or enhance throughput while reducing processing-element complexity, and can overlap multiple codewords.
- 3.1. FFT structure: The FFT-like decoder uses m = log2 n stages, each containing n nodes, with channel likelihood ratios entering from the right and estimated bits emerging on the left.Its sequential data dependence requires a defined scheduling strategy.
- 3.1. FFT structure: 2n−2 clock cycles are required to decode n bits under right-to-left scheduling, leaving each node processor active only once per decoding interval.This underutilization motivates merging nodes into shared processing elements.
- 3.2. Pipelined tree architecture: Only 2^l nodes update when stage l is activated, so stage l requires 2^l processing elements rather than n.Memory sharing additionally depends on the liveness of generated variables.
- 3.2. Pipelined tree architecture: The pipelined tree architecture uses n−1 processing elements and n−1 registers, with configurable processing elements performing f or g and a decision unit broadcasting decoded bits.Local connections simplify routing relative to the FFT-like structure and may increase clock frequency and throughput.
- 3.3. Line SC Architecture: The line architecture merges processing elements while retaining the same throughput as the pipelined tree architecture, using multiplexers to emulate the tree connections.The additional multiplexing logic is offset by processing-element savings.
- 3.4. Vector-overlapping SC architecture: Duplicating stage 0 enables up to 3 vectors to overlap, while requiring separate register sets for the concurrently decoded vectors.The resulting architecture enhances parallelism without duplicating all decoder resources.
4. MINIMUM APPROXIMATION
The paper moves SC decoding from the likelihood-ratio domain to the log domain, simplifying hardware operations. It approximates the complex f function with a minimum operation and reports no significant performance loss in AWGN simulations.
- Log-domain implementation: Log-domain SC decoding replaces likelihood-ratio multiplication and division with lower-complexity computational blocks.The g function maps to an adder/subtractor controlled by the partial-sum bit, while f requires approximation.
- Minimum approximation: The f function is approximated with the minimum function because its transcendental operations are complex to implement in hardware.The approximation follows a technique also used in LDPC decoder implementation.
- Performance impact: There was no significant performance loss from the approximation in simulations of polar codes on an AWGN channel with BPSK modulation.
5. CONCLUSION
The proposed architectures exploit SC decoding schedules to reduce hardware complexity while preserving throughput, and vector overlapping can further enhance throughput. For very large code lengths, semi-parallel designs are required because processing elements must be shared.
- Architecture comparison: The pipelined tree and line architectures reach the same throughput as the FFT-like SC decoder with reduced hardware complexity.
- Throughput enhancement: Vector overlapping enhances throughput by decoding several vectors in parallel.
- Scaling to large code lengths: Very large code lengths require semi-parallel architectures that share processing elements within an update phase.The regular structure of polar codes makes these semi-parallel architectures straightforward to implement.