PaperlayerView exact revision on arXiv

Source-linked AI summary

From sequential decoding to channel polarization and back again

Erdal Arıkan

arXiv:1908.09594v3cs.IT

TL;DR

The note addresses how to construct practical codes that retain reliable transmission while overcoming the complexity barrier associated with sequential decoding. It traces channel polarization from multi-level coding and Pinsker’s scheme to polar and polarization-adjusted convolutional codes, including low-complexity capacity-achieving polar coding and proposed performance improvements. The note also highlights that PAC decoding complexity remains an open issue when using a single sequential decoder.

  • Problem

    Pinsker’s scheme showed that sequential decoding has no fundamental cutoff-rate barrier, but its random inner code and maximum-likelihood decoding make the construction impractical; polar codes also suffer weak finite-length performance.

  • Method

    The note develops channel-polarization schemes, including multi-level coding, recursive low-complexity transforms, polar codes with successive cancellation, and PAC codes that prepend convolutional coding to the polar transform.

  • Results

    Polar coding achieves the capacity of symmetric BMCs with low-complexity encoding, decoding, and construction, while SC-decoded frame error rate is bounded as O(e^−N^0.499) for fixed R < C(W).

  • Takeaways & Limitations

    Recursive polarization can support practical rate assignment and reliable transmission, while outer convolutional coding is proposed to reduce the capacity loss of finite-length polar codes.

  • Takeaways & Limitations

    PAC codes’ ability to operate above R0(W) at low complexity with a single sequential decoder remains only partly resolved because their decoder complexity requires further understanding.

Abstract

from arXiv · show

This note is a written and extended version of the Shannon Lecture I gave at 2019 International Symposium on Information Theory. It gives an account of the original ideas that motivated the development of polar coding and discusses some new ideas for exploiting channel polarization more effectively in order to improve the performance of polar codes.

I. INTRODUCTION

Shannon established the rate–reliability trade-off through channel capacity, but his attainability proof did not address implementation complexity. The note therefore focuses on practically implementable coding ideas for binary-input memoryless channels and introduces relevant channel parameters.

  • I. INTRODUCTION: Shannon’s theorem states that arbitrarily reliable transmission is attainable below capacity C and unattainable above it.The theorem characterizes the trade-off between communication rate R and error probability Pe.
  • I. INTRODUCTION: Random-coding achievability leaves complexity issues unresolved, motivating a search for practically implementable codes.
  • I. INTRODUCTION: The note restricts attention to binary-input memoryless channels with binary source words d ∈ {0, 1}^K.
  • I. INTRODUCTION: The note identifies symmetric capacity, symmetric cutoff rate, and the Bhattacharyya parameter as key channel parameters.The Bhattacharyya parameter is introduced as useful in the subsequent development.
  • I. INTRODUCTION: Symmetric capacity and symmetric cutoff rate are emphasized because linear codes use channel inputs 0 and 1 with equal frequency.For channels with suitable symmetry, these symmetric quantities coincide with their unconstrained counterparts.

II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING

Convolutional codes turn source words into paths in structured code trees, making decoding a tree-search problem. Sequential decoding offers capacity without a complexity limit, but its average complexity becomes prohibitive above the cutoff rate.

  • II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING: Convolutional codes are linear codes whose generator matrix has a special structure corresponding to convolution.Their codewords can be represented as paths through a tree, with branches labeled by codeword symbols.
  • II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING: Each source word defines a path through the convolutional-code tree by selecting branches according to its source bits.
  • II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING: Tree-based decoding searches for the correct path among all possible paths, but exhaustive optimum search is too complex to implement.This motivates low-complexity tree-search heuristics such as depth-first sequential decoding.
  • II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING: Sequential decoding achieves channel capacity without a search-complexity limit, yet its complexity statistics depend on code rate and channel characteristics.
  • II. CONVOLUTIONAL CODES AND SEQUENTIAL DECODING: At rates R > R0(W), the average complexity for correctly decoding the first nR source bits grows roughly as 2^n[R−R0(W)].Below the cutoff rate, virtually error-free communication is possible with constant average complexity per decoded bit.

III. MASSEY’S EXAMPLE

Massey’s example splits an M-ary erasure channel into correlated binary erasure channels without losing capacity. The split increases the aggregate cutoff rate enough to overcome the sequential-decoding cutoff barrier, though not all the way to capacity.

  • III. MASSEY’S EXAMPLE: An M-ary erasure channel with M = 2^m has capacity C(m) = m(1−ε) and cutoff rate R0(m) = m−log2(1+ε).
  • III. MASSEY’S EXAMPLE: Relabeling each M-ary input and output by m-bit vectors decomposes one channel use into m coordinate binary erasure-channel transmissions.An erasure in the original channel appears simultaneously in every coordinate channel.
  • III. MASSEY’S EXAMPLE: Capacity is conserved under splitting, while the aggregate cutoff rate satisfies R0(m) ≤ mR0(1) with strict inequality unless ε is 0 or 1.For each binary erasure channel, C(1) = 1−ε and R0(1) = 1−log2(1+ε).
  • III. MASSEY’S EXAMPLE: Separate convolutional-encoder and sequential-decoder pairs on the coordinate channels can break the MEC’s cutoff-rate barrier, though Massey’s construction does not reach capacity.The example motivates later schemes that combine and then split binary-input channels into synthesized correlated channels.

IV. PINSKER’S SCHEME

Pinsker’s scheme combines product coding with an inner block code and multiple outer convolutional codes to transform a channel into near-perfect bit-channels. This construction boosts the cutoff rate arbitrarily close to capacity, while its random, ML-decoded inner code makes the scheme impractical.

  • The BSC cutoff-rate-to-capacity ratio approaches 1 as crossover probability p goes to 0, motivating Pinsker’s construction.Pinsker combined this observation with Elias’ product coding idea to boost the cutoff rate to capacity.
  • Pinsker’s scheme uses an inner block code and K identical outer convolutional codes, with each inner block carrying one bit from every outer encoder.Successive bits from each outer encoder travel in separate inner code blocks and therefore experience i.i.d. error events.
  • Choosing the inner-code rate as (1 −δ)C(W) and increasing N can make all bit-channels satisfy R0(Wi) > 1 −ǫ.Each outer convolutional code can then operate at rate 1 −ǫ with average sequential-decoding complexity bounded independently of N.
  • The overall rate is (1 −δ)(1 −ǫ)C(W), which can be made arbitrarily close to C(W) by choosing δ and ǫ sufficiently small.The construction keeps decoding operations below a constant independent of the error probability for rates below capacity.
  • Pinsker’s scheme demonstrates that no fundamental cutoff-rate barrier limits sequential decoding, but its random inner code and complex ML decoding prevent practical implementation.The note presents finding a practically implementable way to break this barrier as the next goal.

V. MULTI-LEVEL CODING

MLC/MSD transforms a channel into bit-channels whose capacities and cutoff rates polarize, enabling simplified polar codes with lower-complexity decoding.

  • Multi-level coding: MLC/MSD creates N bit-channels, each feeding a sequential decoder with the channel output and preceding decoder decisions.The ith channel maps input Ui to the full received vector together with prior decisions.
  • Multi-level coding: The scheme conserves capacity at every finite construction size N, unlike Pinsker’s scheme, which does so only asymptotically.This finite-length conservation can permit comparable performance at smaller construction sizes and lower complexity.
  • Channel polarization: As N grows, the bit-channels polarize: fractions with C(Wi) > 1 − δ and C(Wi) < δ tend to C(W) and 1 − C(W), respectively.For polarizing channels, cutoff rates approach the same endpoint, 0 or 1, as capacity.
  • Channel polarization: The recursive transforms achieve polarization with mapper and demapper complexity O(N log N) per block, or O(log N) per transmitted bit.Their structure avoids the excessive implementation complexity likely from a randomly chosen mapper.
  • Channel polarization: At 3 dB SNR, the polarized capacity profile separates from the identity-transform benchmark, trading an ideal profile for lower implementation complexity.The BIAWGN channel capacity in this example is 0.72 bits.
  • Channel polarization: The polarized cutoff-rate sum is 86.7 versus 69.8 for the unpolarized profile, approaching channel capacity asymptotically.This cutoff-rate boost reproduces Pinsker’s effect while retaining O(log N) mapper and demapper complexity per transmitted source bit.
  • Polar codes: Constraining each component rate Ri to 0 or 1 eliminates the outer convolutional codes and yields stand-alone polar codes with successive-cancellation decoding.With this assignment, decisions can be made independently across mapper blocks, eliminating sequential decoders.

VI. POLAR CODES

Polar codes achieve the capacity of symmetric BMCs with low-complexity construction, encoding, and SC decoding, but their finite-length performance can be weak and is improved by CRC-aided list decoding.

  • Code definition: Polar codes are defined by block-length N = 2^n, dimension K, and a data index set A of size K.The set A identifies the positions carrying source bits; the remaining positions are fixed.
  • Code construction: The data indices can be selected using the K smallest Bhattacharyya parameters, equivalently the K largest bit-channel cutoff rates.This construction minimizes the SC frame-error bound.
  • Capacity and complexity: For any fixed rate R < C(W), SC decoding has frame-error probability bounded as O(e^−N^0.499).The bound applies to symmetric BMCs under SC decoding.
  • Capacity and complexity: Polar codes achieve symmetric-channel capacity with low-complexity construction, encoding, and decoding methods.Construction requires O(Npoly(log N)) steps, while encoding and SC decoding require O(N log N) steps.
  • Finite-length performance: At N = 128 and R = 1/2 over BIAWGN, polar-code FER performance is far from optimal, partly because SC decoding is suboptimal and minimum distance is poor.The comparison uses simulated FER curves and a BIAWGN dispersion approximation for average ML performance.
  • Finite-length performance: CRC-aided SC list decoding improves the N = 128, R = 1/2 case using an 8-bit CRC and list size 32.The paper presents this concatenation method as an effective way to address both SC suboptimality and poor minimum distance.

VII. POLARIZATION-ADJUSTED CONVOLUTIONAL CODES

PAC codes combine rate profiling, convolutional preprocessing, and a polar transform, then use sequential decoding on the resulting irregular tree code. Simulations show strong finite-length performance, while data-index design remains a key open issue.

  • Motivation and encoding: PAC codes address finite-length capacity loss by avoiding 0-1 rate assignments that waste capacities of partially polarized bit-channels.Polarization develops relatively slowly at practical small and moderate block-lengths.
  • Motivation and encoding: A PAC code inserts source bits into v according to A, applies a convolution T, and then applies the polar transform P_n to obtain x = v^T P_n.The code is specified by (N, K, A, c), with N constrained to a power of two.
  • Motivation and encoding: The convolution produces an irregular tree code whose branches occur only at indices in A, while non-data positions satisfy v_Ac = 0.The example uses N = 8, K = 4, A = {4, 6, 7, 8}, and c = (1, 1, 1).
  • Performance and design: PAC performance is more sensitive to A than to c, and finding reliable design rules for A remains a research problem.Random choices of c may be acceptable when the convolution constraint length is sufficiently large.
  • Decoding: PAC decoding segments the system into data-carrier formation, irregular-tree encoding, transmission over a polarized channel, sequential decoding, and source-bit extraction.The Fano decoder searches for a path whose metric tends to rise along the correct path and fall after divergence.
  • Performance and design: At N = 128 and R = 1/2, an RM-designed PAC code comes close to the dispersion FER approximation for FER values larger than 10^-3.The example uses c = (1, 0, 1, 1, 0, 1, 1); the paper attributes the behavior to the combined transform G = TP_n appearing sufficiently random.
  • Performance and design: The polar rate profile leaves a greater safety margin below the polarized cutoff-rate profile than the RM profile, which may explain faster Fano decoding with polar-based design.Both RM and polar profiles lie below the polarized cutoff-rate profile in the N = 128, K = 64 example.

VIII. REMARKS AND OPEN PROBLEMS

The paper presents PAC codes as a polar-preprocessed outer convolutional system and identifies unresolved questions about decoding complexity, design universality, and alternative code-generator decompositions.

  • Interpretation: PAC codes are better viewed as an outer convolutional code surrounded by polar preprocessing and postprocessing that supplies polarized information to the decoder.The inner polar transform has rate one and no error-correction capability.
  • Open problems: The single sequential decoder in PAC coding spans only one polarized-channel use, so the usual R0(W) complexity bound applies to longer convolutional codes spanning multiple uses.A better understanding of PAC sequential-decoding complexity is explicitly left open.
  • Open problems: PAC performance and complexity have not yet been studied rigorously, and the best choices of A and c remain to be characterized.PAC codes can achieve channel capacity in general because ordinary polar codes are a special case.
  • Open problems: The paper proposes investigating universal PAC design rules, including whether the RM rule with a suitable c works uniformly across BMCs of a given capacity.This question is motivated by strong RM-rule performance and possible robustness to channel-parameter variation and modeling errors.
  • Open problems: Sequential decoding has variable complexity, motivating fixed-complexity breadth-first alternatives such as list Viterbi or beam search.Tracking only the convolutional encoder state would be suboptimal because the polarized channel also has a state; all possible states number 2^(NR).
  • Further directions: PAC coding can be interpreted as an upper-lower decomposition of a generator matrix, suggesting other linear-algebra decompositions as a route to powerful codes with low-complexity encoding and decoding.The proposed direction concerns solving redundant noisy linear equations through alternative generator-matrix constructions.
Loading 1908.09594v3…