Constructing Long Codes from Short Ones
摘要
Modern capacity-achieving codes are the topic of this chapter. First, however, the \((u,u+v)\) construction is presented to double the codeword length, generating all Reed-Muller codes in a recursive manner. Likewise, the Turyn construction leads to the extended Golay code. Block and convolutional interleavers are treated to distribute error bursts, thereby improving the burst-error correcting capability. Interleaving is also the key to Turbo coding linking two or more encoders and decoders in a pseudo-random fashion, thereby making them appear as very long codes with still very low-complex constituent codes. Product (array) codes are used to illustrate the Turbo decoding. Turbo coding comes in two flavors, as serial and parallel concatenation, where the conventional serial concatenation is also first introduced. Other capacity-achieving coding schemes discussed are Low-Density Parity-Check (LDPC) and Polar codes. All these schemes are based on iterative decoding, thereby making use of the split between a-priori, intrinsic, and extrinsic information. The iterations are between the decoders of constituent codes in case of Turbo coding, between variable and check nodes in case of LDPC codes. In case of Polar Codes, the description is limited to successive cancellation. To discuss the performance, the information theoretic limits are derived and EXIT charts (for Turbo and LDPC decoding) enable convergence analysis. Density evolution in its simplified and full version is explained, as well. The design of LDPC codes by first determining degree distributions and thereafter, the corresponding parity-check matrix design with random, PEG, Zigzag, ACE, or PEG-ACE algorithms is described. We provide the Protograph construction, Quasi-Cyclic, Spatially-Coupled, Multi-edge-type, and nonbinary LDPC codes. Generalized Concatenated (GC) Codes finalize the chapter. They are to be seen in conjunction with multi-level coded modulation in Chap. 21, which might provide an easier understanding, since there, modulation alphabets are partitioned, where GC codes rely on the partitioning of a code.