Source-linked AI summary
Polar Subcodes
Peter Trifonov, Vera Miloslavskaya
TL;DR
Moderate-length polar codes face poor performance associated with suboptimal SC decoding and low minimum distance. The paper constructs polar subcodes using data-dependent dynamic frozen symbols and EBCH parent codes. These codes have higher minimum distance than classical polar codes and are reported to outperform LDPC, turbo, and polar codes, including polar codes with CRC.
Problem
Moderate-length polar codes have poor performance associated with suboptimal successive-cancellation decoding and low minimum distance, while the effect of outer-code parameters on concatenated-code performance is unclear.
Source: §1 · p. 1Method
The paper constructs polar subcodes of EBCH codes using data-dependent dynamic frozen symbols, with decoding based on successive-cancellation algorithms and their extensions.
Source: §1 · p. 2, §5 · p. 13Results
The proposed codes have higher minimum distance than classical polar codes and are reported to outperform state-of-the-art polar, LDPC, and turbo codes, including polar codes with CRC.
Source: §1 · p. 2, §6 · p. 21, §7 · p. 23Takeaways & Limitations
The construction generalizes polar codes with CRC as a special case and provides a representation that supports improved polar-subcode performance and more efficient decoding.
Source: §7 · pp. 23–24The authors have no analytical method for selecting the minimum-distance trade-off against decoding complexity, so they rely on simulations to choose it.
Source: §5.1.1 · p. 14
Abstract
from arXiv · showhide
An extension of polar codes is proposed, which allows some of the frozen symbols, called dynamic frozen symbols, to be data-dependent. A construction of polar codes with dynamic frozen symbols, being subcodes of extended BCH codes, is proposed. The proposed codes have higher minimum distance than classical polar codes, but still can be efficiently decoded using the successive cancellation algorithm and its extensions. The codes with Arikan, extended BCH and Reed-Solomon kernel are considered. The proposed codes are shown to outperform LDPC and turbo codes, as well as polar codes with CRC.
1 Introduction
Polar codes offer capacity-achieving, low-complexity coding, but moderate-length performance is limited by successive-cancellation decoding and low minimum distance. This paper proposes polar subcodes of extended BCH codes that retain efficient polar-code decoding while improving minimum distance and reported performance.
1 Introduction
- Moderate-length polar codes perform poorly in part because successive-cancellation decoding is suboptimal and their minimum distance is low.List/stack SC methods outperform SC, while belief propagation remains inferior to list/stack decoding.Source: §1 · p. 1
- Outer error-detecting or error-correcting codes concatenated with polar codes leave the effect of outer-code parameters on minimum distance and finite-length performance unclear.Generalized concatenation with inner polar codes is another proposed approach.Source: §1 · pp. 1–2
- The paper proposes polar subcodes of EBCH codes with higher minimum distance, decoded using polar-coding techniques, and reports gains over state-of-the-art polar, LDPC, and turbo codes.The construction uses dynamic frozen symbols and considers Arikan, EBCH, and Reed-Solomon kernels.Source: §1 · p. 2
2 Background
The background presents generalized concatenated codes and multistage decoding, then reviews polar-code construction and decoding alongside BCH-code structure.
2.1 Generalized concatenated codes
- GCC encoding partitions data into blocks, encodes them with nested outer codes, and applies a matrix to each column to form the codeword.Multistage decoding estimates inner-code symbols successively with SISO decoders and uses those estimates to decode the corresponding outer codes.Source: §2.1 · pp. 2–3
2.2 Polar codes
- A classical polar code selects rows of a polarizing transformation and freezes the remaining symbol indices; SC decoding makes sequential decisions with complexity O(n log n).The standard construction freezes indices with the highest error probabilities, while list or stack variants track multiple candidate vectors.Source: §2.2 · pp. 3–5
2.3 BCH codes
- EBCH codes are specified using distinct field elements as code locators, with a standard digit-order arrangement described for the locators.The passage identifies extended primitive narrow-sense BCH codes by their length, dimension, and minimum-distance parameters.Source: §2.3 · p. 5
3 Interlinked Generalized Concatenated Codes
Interlinked generalized concatenated codes extend GCC encoding by placing data subvectors in outer-code cosets, and generalized Plotkin decomposition provides a recursive representation of linear codes.
3.1 The construction
- IGCC represents a broad class of linear block codes for multilevel decoding, though good performance is not guaranteed for arbitrary IGCCs.Each data subvector is encoded in a coset of its outer code rather than directly in that code; an IGCC can preserve at least the distance of an existing GCC with matching parameters.Source: §3.1 · pp. 5–6
3.2 Generalized Plotkin decomposition of linear codes
- Generalized Plotkin decomposition extends classical Plotkin concatenation and can be applied recursively to represent linear codes.The decomposition supports hard-decision decoding by first decoding a component code and then decoding the resulting residual vectors in another component code.Source: §3.2 · pp. 7–8
- A low minimum distance in the first component can make the described decoding fail even within ⌊(d−1)/2⌋ errors.List decoding the first component and testing corresponding second-component decodes is offered as a workaround.Source: §3.2 · p. 8
4 Dynamic Frozen Symbols
The section represents linear codes through dynamic frozen-symbol constraints, enabling successive-cancellation decoding beyond classical polar codes. It characterizes these constraints for extended BCH codes and compares their decoding performance with polar codes.
4.1 Representation of a linear code for SC decoding
- Gaussian elimination converts a linear code’s parity-check constraints into equations that express selected input symbols using earlier symbols, generalizing fixed-zero frozen symbols.The construction sets the dynamic frozen indices from the constraint matrix; these symbols can take values determined by symbols with smaller indices.Source: §4.1 · pp. 8–9
- Any linear code of length lm can be represented by this system, allowing successive-cancellation decoding and its variations to decode arbitrary linear codes of that length.When preceding input symbols are correct, the symbol-error probability remains as for classical polar codes, so SC error probability is computed as in equation (7).Source: §4.1 · p. 9
- For generic linear codes, dynamic frozen indices may miss high-error symbols, and near-ML list or stack decoding can require complexity exponential in code dimension.Evaluating equation (10) may also raise decoding complexity to O(n^2), although computing the channel expressions remains O(n log n).Source: §4.1 · p. 9
4.2 Extended BCH codes and Arikan kernel
- An EBCH code with design distance d ≥ δ(r, m) + 3 is a subcode of an RM code of order m − r − 1.The EBCH dynamic frozen-index set includes the frozen indices of that RM code; the characterization assumes standard digit ordering.Source: §4.2 · p. 10
- For an extended primitive narrow-sense BCH code, Theorem 2 counts dynamic frozen symbols by index weight using the sizes of the corresponding cyclotomic cosets.The section also views constructing the constraint system for the Arikan transform as a recursive application of the GPD.Source: §4.2 · pp. 10–11
- At list size L = 1, Arikan polar codes far outperform extended BCH codes; box-and-match near-ML decoding gives EBCH codes a significant gain, while list/stack SC needs huge L for comparable performance.Arikan polar codes reach near-ML performance at L = 4.Source: Figure 4 · p. 12, §4.2 · pp. 12–13
5 Polar subcodes
Polar subcodes impose data-dependent dynamic-freezing constraints on parent codes to combine polar-code decoding techniques with higher, controllable minimum distance. The sections develop EBCH-parent constructions and extensions using improved Arikan, EBCH, and Reed-Solomon kernels.
5 Polar subcodes
- Dynamic frozen symbols define a polar subcode by requiring membership in a parent code while adding static constraints to selected high-error subchannels.The construction can be viewed as precoding information with W and then encoding with a polar code; the resulting codeword must belong to the parent code.Source: §5 · p. 13
5.1.1 The construction
- For d up to twice the original polar code’s minimum distance, the rate degradation is negligible.Using EBCH parents can avoid freezing bit subchannels with low Bhattacharyya parameters, improving performance under SC decoding and its variations. Raising parent-code distance can worsen SC error at fixed dimension, so simulations are used to select the distance.Source: §5.1.1 · pp. 14, 16
5.1.2 Encoding and Decoding Complexity
- Encoding complexity does not exceed that of polar codes with an f-bit CRC, while decoding retains the same probability or likelihood-ratio operations as classical polar codes.Decoding adds bit-manipulation work for evaluating dynamic frozen symbols; its cost depends on the implementation and constraints.Source: §5.1.2 · pp. 16–17
5.2 Improved polar subcodes with Arikan kernel
- Improved Arikan-kernel subcodes use EBCH outer codes in an IGCC, with their parameters selected to minimize multistage-decoding error probability.They are intended for block sequential decoding with block size at least 2^s.Source: §5.2 · p. 17
5.3 Polar subcodes with EBCH kernel
- For the EBCH kernel, dynamic-frozen symbols within a block can be recovered jointly by decoding in a coset, potentially improving performance or reducing decoding complexity.This replaces successive decoding of the block’s symbols.Source: §5.3 · p. 19
5.4 Reed-Solomon kernel
- The construction extends to Reed-Solomon kernels by representing an EBCH parent through dynamic-freezing equations and adding static constraints on the highest-error subchannels.Performance evaluation of the subchannels uses simulations, and the resulting codes can be decoded with techniques cited by the paper.Source: §5.4 · pp. 19–20
6 Numeric results
Across the tested settings, proposed polar subcodes show improved performance against classical polar codes and several established alternatives, while decoding complexity varies with the block-sequential parameters. Results cover Arikan and non-Arikan kernels and lengths around 1024 and 2048.
6 Numeric results
- Simulations compare codes over AWGN with BPSK, using block-sequential or sequential decoding for proposed subcodes and established decoders for the comparison codes.The comparisons include classical polar codes, CRC-aided polar codes, LTE turbo codes, and WiMAX and CCSDS LDPC codes.Source: §6 · p. 21
- At length approximately 1024, EBCH polar subcodes significantly outperform classical polar codes of the same length and dimension, as well as Arikan-kernel polar codes with CRC.Increasing s improves block-sequential decoding performance; the best reported result uses improved subcodes with outer EBCH codes of length 32.Source: §6 · p. 21
- For s ≤ 3, block-sequential decoding is slightly inferior to Tal-Vardy list decoding at the same list size, but requires fewer arithmetic operations.This reported trade-off applies to the block-sequential algorithm comparison in the simulation setup.Source: §6 · p. 21
- At length 2048, improved Arikan-kernel polar subcodes outperform LDPC and turbo codes, the MHU construction, and a classical GCC with outer EBCH codes.The paper attributes the improved subcode’s advantage over the classical GCC to its outer-code rate allocation.Source: Figure 9 · p. 22, §6 · pp. 22–23
- Dynamic-freezing constraints prevent wrong paths until the final decoding phase, giving polar subcodes slightly lower average operation counts than polar codes with CRC.The comparison uses block-sequential decoding for polar subcodes and belief propagation for LDPC codes.Source: §6 · p. 22
- With s = 3, polar decoding requires 10 times fewer operations than LDPC decoding; at s = 5, complexity becomes comparable.The authors conclude that increasing list size L can be more advantageous than increasing s, although larger s enables the improved subcode construction.Source: §6 · p. 22
- For non-Arikan kernels, EBCH-kernel subcodes outperform Arikan-kernel codes, and Reed-Solomon-kernel subcodes improve minimum distance and performance over the compared codes.Classical Reed-Solomon-kernel polar codes also outperform comparable Arikan-kernel polar codes despite similarly low minimum distance.Source: Figure 10 · p. 23, §6 · p. 23
7 Conclusions
The paper introduces polar subcodes based on dynamic frozen symbols, combining higher minimum distance than classical polar codes with efficient decoding using successive-cancellation algorithm derivatives. It reports favorable comparisons with some existing LDPC and turbo codes while noting limits in code construction analysis and longer outer-code decoding.
7 Conclusions
- Dynamic-frozen-symbol construction produces subcodes of linear block codes with higher minimum distance than classical polar codes that remain efficiently decodable by successive-cancellation algorithm derivatives.Many existing polar-code constructions, including CRC-aided polar codes, are special cases of the proposed subcodes.Source: §7 · p. 23
- The paper reports that proposed codes outperform some existing LDPC and turbo codes of moderate lengths, but does not prove that they achieve channel capacity.The capacity-proof limitation is stated explicitly in the conclusion.Source: §7 · p. 23
- Code construction relies on heuristic methods because analytical techniques for predicting list/stack successive-cancellation decoding performance are lacking.The paper notes that progress in performance analysis may lead to better code designs.Source: §7 · p. 23
- Longer outer EBCH codes are identified as a route to improved performance, but require efficient list soft-decision decoding algorithms.Source: §7 · p. 24
- The paper extends generalized concatenated codes and introduces a representation of linear block codes that supports successive-cancellation decoding and its variations.The approach also allows near-ML decoding of short Reed-Solomon codes.Source: §7 · p. 24