Source-linked AI summary
Performance and Construction of Polar Codes on Symmetric Binary-Input Memoryless Channels
Ryuhei Mori, Toshiyuki Tanaka
TL;DR
Polar-code construction was previously exponential in blocklength for general symmetric binary-input memoryless channels, motivating a more efficient general method. The paper proposes linear-complexity construction based on direct bit-error evaluation and derives new block-error bounds for the BEC and arbitrary symmetric B-MCs.
Problem
General polar-code construction was exponential in blocklength, while polynomial-complexity construction had been established only for the BEC.
Method
The paper constructs polar codes for arbitrary symmetric B-MCs in O(N) complexity by directly evaluating bit-error probabilities, and derives bounds using joint density evolution.
Results
The resulting block error probability decays like O(2^-N^β) for any fixed β < 1, and the paper derives new upper and lower bounds for specified channels.
Takeaways & Limitations
The construction and bounds extend polar-code analysis and construction to arbitrary symmetric B-MCs, with applicability also to generalized polar codes.
Abstract
from arXiv · showhide
Channel polarization is a method of constructing capacity achieving codes for symmetric binary-input discrete memoryless channels (B-DMCs) [1]. In the original paper, the construction complexity is exponential in the blocklength. In this paper, a new construction method for arbitrary symmetric binary memoryless channel (B-MC) with linear complexity in the blocklength is proposed. Furthermore, new upper and lower bounds of the block error probability of polar codes are derived for the BEC and the arbitrary symmetric B-MC, respectively.
I. INTRODUCTION
The paper motivates extending polar-code construction beyond the BEC: prior polynomial-complexity construction was limited, while this work targets arbitrary symmetric B-MCs and sharper error bounds.
- Channel polarization constructs capacity-achieving codes for symmetric binary-input discrete memoryless channels with low encoding and decoding complexity.
- The original construction has exponential complexity in blocklength, while polynomial-complexity construction had been introduced only for the BEC.
- The paper proposes O(N)-complexity construction for arbitrary symmetric binary-input memoryless channels.
- It also derives new upper and lower bounds on polar-code block error probability for the BEC and arbitrary symmetric B-MCs, respectively.
- For a symmetric B-MC, the LLR is used as a sufficient statistic, and the associated real-output channel has the same MAP-decoding performance.
1 GN), with input uN
The construction framework combines polarized subchannels through a recursively defined generator matrix and selects reliable subchannels for information transmission.
- Channel polarization splits the total mutual information into subchannel mutual informations through the chain rule.
- Most polarized subchannels have mutual information near zero or one, with approximate counts N(1 − I(W)) and NI(W), respectively.
- Information bits are assigned to subchannels with high mutual information, while non-information bits are clamped to prespecified values.
- The paper assumes all non-information bits are zero because this does not affect performance when the transmitting channel is symmetric.
B. Decoding
Successive cancellation decoding fixes non-information bits and decodes information bits sequentially using maximum-likelihood decisions on polarized subchannels.
- SC decoding sets non-information-bit decisions to zero and decodes information bits sequentially in ascending index order.
- Each information bit is decoded by maximum-likelihood decoding of its corresponding polarized subchannel using previously decoded bits.
- When the two likelihood values are equal, the decoder chooses zero or one with probability 1/2.
C. Upper bound of performance and construction
The paper relates SC bit-error events to block error probability and proposes direct error-probability-based construction instead of Bhattacharyya-parameter selection.
- The SC block error event is the union of events in which the first bit error occurs at each information-bit position.
- Arıkan’s construction selects information indices by minimizing a union bound based on Bhattacharyya parameters.
- The decoding-tree representation uses channel messages at leaves and eliminates nodes already determined or unhelpful for the target bit.
- For the BEC, the Bhattacharyya parameter satisfies Z_N^(i) = 2P(A_i,N), enabling direct correspondence with the bit-error probability.
- The proposed alternative construction directly evaluates P(A_i,N) and chooses the information set minimizing the sum of these probabilities.
III. CONSTRUCTION OF POLAR CODES
The paper constructs polar codes for arbitrary symmetric B-MCs by directly evaluating subchannel error probabilities through density evolution, achieving O(N) construction complexity while retaining the usual error-probability decay.
- Error-probability evaluation: SC decoding errors P(A_i) can be represented as root-node BP errors on tree-like decoding graphs.The tree structure depends on the binary expansion of i−1, with check and variable nodes determined by its bits.
- Error-probability evaluation: Theorem 1 expresses each P(A_i) as an expectation computed from the LLR density of the channel.Variable-node and check-node operations are represented by the corresponding LLR-density convolutions.
- Error performance: O(2^−N^β) bounds the block error probability for every fixed β < 1.The proposed construction inherits this decay because the Bhattacharyya-parameter upper bound also applies to the constructed codes.
- Complexity: O(N) is the resulting construction complexity for arbitrary symmetric B-MCs, including the computation and selection of subchannels.The calculation of all LLR densities and selection of the NR-th smallest value are both bounded linearly in N under the stated operation model.
- Scope and qualification: Higher N requires higher-precision LLR representations, so the stated complexity counts arithmetic or convolution operations rather than numerical precision.Finite-sized density-evolution binning can produce imprecise bounds, while preserving relevance to SC decoding under the same quantization.
IV. LOWER BOUND OF THE BLOCK ERROR PROBABILITY FOR ARBITRARY SYMMETRIC B-MC
The paper introduces a lower bound on polar-code block error probability for arbitrary symmetric B-MCs, using joint density evolution to evaluate pairwise error-event intersections.
- Lower-bound formulation: A lower bound is introduced for a given information-bit set I, addressing the previously noted absence of lower bounds for polar-code block error probability.The bound is developed from probabilities involving the events A_i.
- Lower-bound formulation: Boole’s inequality yields a lower bound based on selected subsets S of the information-bit indices.The events A_i are used because they are easier to handle than the corresponding block-error events B_i.
- Complexity and limitations: Maximizing the lower bound over S is NP-hard because it is equivalent to the Max-Cut problem.The paper notes that non-strict optimization can still produce practically accurate lower bounds for some rates and channels.
- Joint density evolution: Joint density evolution evaluates the pairwise intersections P(A_i ∩ A_j) required by the lower bound.It propagates joint densities through sum and check-node LLR convolutions.
- Joint density evolution: Theorem 2 gives the joint density a_i,j for two subchannel error events of an arbitrary symmetric B-MC.The recursion can be extended to higher-order joint distributions.
- BEC specialization: For the BEC, joint density evolution simplifies to tracking expectations of erasure probabilities.The BEC-specific recursion is stated as Corollary 1 and uses a Dirac delta mass at infinity.
- Complexity and limitations: O(N^s) is the asymptotic complexity for computing all s-joint densities, but the cost grows exponentially in s because density dimension equals s.The pairwise case therefore has quadratic-in-N complexity under the stated convolution-operation measure.
V. NEW UPPER BOUND OF THE BLOCK ERROR PROBABILITY FOR THE BEC
The paper derives a new BEC upper bound that avoids the poor behavior of the earlier bound near capacity by incorporating dependencies among subchannel error events.
- Motivation: The earlier block-error upper bound can exceed one near channel capacity, motivating a new BEC-specific bound.The issue is attributed to correlations among complements of the events A_i.
- Bound construction: The new upper bound uses covariances among complements of {A_i} and a spanning-tree representation over information-bit indices.Parent events are selected through a directed spanning tree whose edge weights are joint probabilities.
- Result: 1 − Q provides a simple upper bound on the BEC block error probability.The paper also describes a more accurate upper-bound refinement.
- Bound construction: A maximum-weight directed spanning tree is used to tighten the bound, with edge weights given by joint complement-event probabilities.The construction is compared structurally with a Chow–Liu tree.
VI. TECHNIQUES FOR TIGHTENING BOUNDS
The paper tightens polar-code block error bounds by exploiting partial ordering and minimal information-bit elements, then extends the approach from the BEC to arbitrary symmetric B-MCs.
- BEC techniques: The BEC analysis evaluates erasure events using LLR behavior under successive-cancellation decoding, where the relevant LLR is either zero or infinity.The method therefore considers erasure events A′i rather than the more general events Ai.
- BEC techniques: Partial ordering on bit indices identifies relations among erasure events, reducing the calculations needed for block erasure probability bounds.The ordering compares the one-positions in the binary expansions of indices minus one.
- BEC techniques: Theorem 3 shows that only the minimal elements M(I) of the information-bit set I need to be considered for the BEC block erasure probability.This reduction can be used to tighten the resulting bounds.
- General symmetric B-MCs: For general symmetric B-MCs, Theorem 4 enables more efficient calculation of grouped joint error probabilities through depth-(n − k) density-evolution trees and limited arithmetic.The theorem replaces direct joint density evolution for the grouped events.
- General symmetric B-MCs: Decomposing the block error event into grouped unions yields a tighter upper bound than summing every bit-error probability separately.For I = {4, 6, 7, 8}, P(A4) + P(A6) + P(A7 ∪ A8) is tighter than P(A4) + P(A6) + P(A7) + P(A8).
VII. NUMERICAL CALCULATIONS AND SIMULATIONS
Numerical calculations compare the proposed and existing bounds with simulations at rate 0.5 and blocklength 1024. The new upper bound tracks simulations more closely and remains below one.
- Numerical comparison: At rate 0.5 and blocklength 1024, Figure 2 compares upper bounds (4) and (6) with lower bound (5).The calculations use only minimal information-bit elements according to Theorem 3.
- Numerical comparison: The lower bound is very close to the upper bound for erasure probability ǫ below 0.4, despite approximate optimization.This comparison concerns the calculated bounds shown for the BEC.
- Numerical comparison: The new upper bound is always smaller than 1 and closer to simulation results, while the union bound exceeds 1 when ǫ > 0.407.These observations distinguish the proposed upper bound from the union bound in the plotted regime.
VIII. CONCLUSION AND FUTURE WORKS
The paper presents linear-complexity construction for polar codes over symmetric B-MCs and derives new block-error bounds, with extensions to generalized polar codes. Higher-order joint distributions and bounds remain future work.
- Conclusion: The proposed construction method for polar codes over symmetric B-MCs has complexity O(N).This is the paper’s stated construction result.
- Conclusion: The paper derives new upper and lower bounds for block error probability and introduces a joint density-evolution method.The method and bounds also apply to generalized polar codes.
- Future work: Computing higher-order joint distributions and deriving bounds with higher-order terms are identified as future work.The paper specifically mentions Boole’s inequality with higher-order terms.