Ch. 8 — Coding for Wireless Channels

Chapter 8 of Wireless Communications (2nd ed. Draft) — Andrea Goldsmith

Abstract

Chapter 8 establishes the theoretical framework for channel coding in wireless communications, extending error correction principles from AWGN channels to fading environments. It details the implementation of convolutional codes using the Viterbi algorithm and analyzes their performance via free distance and transfer functions. The chapter further explores advanced coding techniques, including turbo codes and low-density parity-check (LDPC) codes that approach Shannon capacity, and integrative schemes like coded modulation and interleaving to combat burst errors in fading channels. These methods collectively address the trade-offs between spectral efficiency, power constraints, and reliability in modern wireless systems.

Key Concepts

• Maximum Likelihood Decoding: This method selects the transmitted sequence $C$ that maximizes the likelihood function $p(R|C)$, corresponding to the path with the maximum metric through the trellis. For AWGN channels, noise affects symbols independently, allowing the likelihood to be expressed as a product of branch probabilities.
• Viterbi Algorithm: An efficient computational procedure that reduces the complexity of maximum likelihood decoding from exponential to linear in the sequence length by retaining only survivor paths at each trellis node. It utilizes the property that the maximum likelihood path through a node must coincide with the path having the largest partial metric up to that node.
• Free Distance ($d_f$): The minimum Hamming distance between the all-zero path and any other valid path through the trellis, defining the error correction capability of a convolutional code. It replaces the minimum distance $d_{min}$ of block codes, as convolutional codes can have infinite length without returning to the all-zero state immediately.
• Transfer Functions: Algebraic representations derived from state diagrams that enumerate paths diverging from and remerging with the all-zero state based on Hamming distance. Extended transfer functions $T(D,N,J)$ additionally track the number of bit errors and path length to facilitate bit error probability analysis.
• Turbo Codes: Parallel concatenated convolutional codes introduced to achieve performance near the Shannon limit using iterative soft-decision decoding (MAP or SOVA) between component decoders. They suffer from an error floor at low bit error probabilities, which can be mitigated by increasing constraint length or optimizing the interleaver design.
• Low-Density Parity-Check (LDPC) Codes: Linear block codes characterized by a sparse parity-check matrix $H$, enabling near-capacity performance via iterative belief propagation decoding. Unlike turbo codes, LDPC codes typically exhibit lower decoding complexity but higher encoding complexity and can detect correct codeword convergence.
• Trellis Coded Modulation (TCM): A technique that jointly optimizes channel coding and modulation to achieve coding gain without bandwidth expansion by mapping coded bits to signal subsets via set partitioning. It maximizes the minimum Euclidean distance between signal sequences while maintaining the average power constraint.
• Bit-Interleaved Coded Modulation (BICM): A fading-channel modulation scheme that interleaves bits before mapping to symbols, decoupling coding from modulation to exploit diversity order rather than Euclidean distance. This approach outperforms symbol-interleaved coded modulation in fading environments by maximizing Hamming distance diversity.
• Interleaving Depth: The parameter determining the time separation of consecutive coded symbols to ensure independent fading across a codeword. For effective diversity in fading channels, the depth must exceed the channel coherence time, though this introduces transmission latency.
• Unequal Error Protection (UEP): A coding strategy assigning different levels of error protection to bit streams based on their priority, implemented via multilevel coding or time-multiplexed coded modulation. It ensures high-priority bits achieve low bit error probability even when channel conditions degrade during deep fades.

Key Equations and Algorithms

• Log-Likelihood Path Metric: ${\sum }_{i=1}^L{\sum }_{j=1}^n\log p(R_{ij}|C_{ij})$. This expression sums the branch metrics along a trellis path, converting a product of probabilities into a sum for computational convenience, where $R_{ij}$ and $C_{ij}$ are received and coded symbols.
• Viterbi Survivor Selection: $P_{new}=\max (P_{old}+\text{branch metric})$. At each trellis node, this procedure calculates partial metrics for entering paths and discards all but the one with the highest metric, reducing memory requirements to $2^{K-1}$ survivor paths for constraint length $K$.
• Transfer Function ($D$-domain): $T(D)={\sum }_d{a}_d{D}^d$. This function counts the number of paths $a_d$ with Hamming distance $d$ from the all-zero path, where the minimum free distance $d_f$ corresponds to the lowest power of $D$ with a non-zero coefficient.
• Extended Transfer Function: $T(D,N,J)={\sum }_{d,w}{a}_{d,w}{D}^d{N}^w{J}^w$. This function extends the standard transfer function by including $N$ for bit errors and $J$ for path length, enabling the derivation of bit error probability bounds.
• Soft Decision Pairwise Error Probability: $P_2(d)\le Q\left(\sqrt{\frac{2d{R}_c{E}_b}{N_0}}\right)$. This bound approximates the probability of mistaking the all-zero sequence for a sequence at distance $d$, assuming coherent BPSK and soft decision decoding over AWGN.
• Channel Coding Gain: $G_c={\left(\frac{d_{min}\Delta }{d_0{\Delta }_0}\right)}^2$. This formula quantifies the signal-to-noise ratio improvement provided by coding, where $\Delta$ is the constellation expansion factor resulting from redundant bits introduced by the encoder.

Key Claims and Findings

• Convolutional code performance is primarily dictated by the minimum free distance $d_f$, which determines the asymptotic error probability slope at high signal-to-noise ratios.
• The Viterbi algorithm achieves exact maximum likelihood decoding with complexity linear in sequence length but exponential in the constraint length $K$, limiting practical implementations to small $K$.
• Turbo codes can operate within a fraction of a decibel of the Shannon capacity limit, provided the interleaver depth is sufficiently large and convergence criteria are met.
• Coded modulation techniques like TCM achieve coding gains without bandwidth expansion by increasing the Euclidean distance between signal sequences in the sequence space.
• Interleaving converts burst errors in fading channels into independent errors, allowing standard codes designed for AWGN channels to recover diversity order proportional to the minimum distance.
• Bit-interleaved coded modulation (BICM) is preferred over symbol interleaving for fading channels because it maximizes Hamming distance diversity rather than Euclidean distance.

Terminology

• Survivor Path: The single path entering a specific trellis node at a given stage that retains the highest partial path metric, while all other competing paths are discarded.
• Branch Metric: The component of the path metric associated with a single transition in the trellis, calculated as $\log p(R_{ij}|C_{ij})$ or its squared Euclidean distance equivalent for AWGN channels.
• Free Distance: The minimum Hamming distance between the all-zero sequence and any other valid infinite-length codeword sequence in a convolutional code.
• Shaping Gain: The theoretical power saving (up to 1.53 dB) achieved by shaping the signal constellation to a spherical boundary rather than a hypercube, independent of channel coding.
• Error Floor: A region in the performance curve where the bit error probability stops decreasing rapidly, often observed in turbo codes at high SNRs due to low-weight error events.
• Set Partitioning: A method of dividing a signal constellation into subsets such that the minimum distance within each subset is maximized, used in TCM to assign coded bits to robust transmission choices.
• Coherence Time: The time duration over which the channel impulse response is essentially constant, determining the minimum interleaver depth required to ensure independent fading across coded symbols.
• Rate-Compatible Punctured Convolutional (RCPC): A family of codes generated from a mother code by puncturing bits, allowing adaptive coding rates while maintaining a compatible trellis structure for variable error protection.