Introduction to Lattice and Trellis Codes

Chapter 14 Introduction to lattice and trellis codes In this chapter we discuss coding techniques for bandwidth-limited (high-SNR) AWGN channels. On bandwidth-limited channels, nonbinary signal alphabets such as M -PAM must be used to approach capacity. Furthermore, the signals should be used with a nonuniform, Gaussian-like probability distribution. Using large-alphabet approximations, we show that the total coding gain of a coded modulation scheme for the bandwidth-limited AWGN channel is the sum of a coding gain due to a denser packing than the baseline M -PAM scheme, plus a shaping gain due to constellation shaping (or equivalently to use of a nonuniform distribution). At high SNRs, the coding and shaping problems are separable. The maximum possible shaping gain is a factor of πe/6 (1.53 dB). Simple shaping methods such as shell mapping and trellis shaping can easily obtain of the order of 1 dB of shaping gain. For moderate coding gains at moderate complexity, the two principal classes of packings are lattices and trellis codes, which are analogous to block and convolutional codes, respectively. By now the principles of construction of the best such codes are well understood, and it seems likely that the best codes have been found. We plot the effective coding gains of these known moderate-complexity lattices and trellis codes versus the branch complexity of their minimal trellises, assuming ML decoding. Trellis codes are somewhat superior, due mainly to their lower error coefficients. We briefly mention higher-performance schemes, including multilevel schemes with multistage decoding and bit-interleaved coded modulation, which allow the use of high-performance binary codes such as those described in the previous chapter to approach capacity. 14.1 Lattices It is clear from Shannon’s capacity theorem that an optimal block code for a bandwidth-limited AWGN channel consists of a dense packing of code points within a sphere in a high-dimensional Euclidean space. Most of the densest known packings are lattices. In this section we briefly describe lattice constellations, and analyze their performance using the union bound estimate and large-constellation approximations. An n-dimensional (n-D) lattice Λ is a discrete subset of n-space Rn that has the group property. Without essential loss of generality, Λ may be assumed to span Rn . The points of the lattice then form a uniform infinite packing of Rn . Example 1. The set of integers Z is a one-dimensional lattice, since Z is a discrete subgroup of R. Any 1-dimensional lattice is of the form Λ = αZ for some scalar α > 0. Example 2. The integer lattice Zn (the set of integer n-tuples) is an n-dimensional lattice for any n ≥ 1. Example 3. The hexagonal lattice A2 = {a(1, 0) + b( 12 , Figure 1. This lattice is the densest packing of R2 . √ 3 2 ) | (a, b) ∈ Z2 } is illustrated in Figure 1. The hexagonal lattice A2 . Exercise 1. Let C be an (n, k, d) binary linear block code. Show that ΛC = {x ∈ Zn | x ≡ c mod 2 for some c ∈ C} (14.1) is an n-dimensional sublattice of Zn (called a “Construction A” or “mod-2” lattice). A general n-dimensional lattice Λ that spans Rn may be characterized by a set of linearly independent generators G = {gj , 1 ≤ j ≤ n} such that Λ is the set of all integer linear combinations of the generators:
Λ = {aG = aj gj | a ∈ Zn }. (14.2) j Thus Λ may be viewed as the image of the integer lattice Zn under a linear transformation of n-space Rn by the linear operator G, as illustrated by Figure 1. By the group property of Λ, any translate Λ + x by a lattice point x ∈ Λ is just Λ again. This implies that a lattice is “geometrically uniform;” every point of the lattice has the same number of neighbors at each distance, and all decision regions of a minimum-distance decoder (“Voronoi regions”) are congruent and form a tessellation of Rn . Indeed, any lattice translate Λ + t is geometrically uniform. The key geometrical parameters of a lattice are: • the minimum squared distance d2min (Λ) between lattice points; • the kissing number Kmin (Λ) (the number of nearest neighbors to any lattice point); • the volume V (Λ) of n-space per lattice point. As indicated in Figure 1, this volume is the volume of the fundamental parallelotope [0, 1)n G = {aG | a ∈ [0, 1)n }. Since the volume of the n-cube [0, 1)n is 1 and the Jacobian of the linear transformation G is its determinant |G|, it follows that V (Λ) = |G| for any generator matrix G of Λ. The Hermite parameter of Λ is the normalized density parameter γc (Λ) = d2min (Λ) , V (Λ)2/n (14.3) which we will shortly identify as its nominal coding gain. The quantity V (Λ)2/n may be thought of as the normalized volume of Λ per two dimensions. 2 Example 3 (cont.) For the hexagonal lattice A2 , the minimum √ squared distance is dmin (A2 ) = 1, the kissing number is Kmin (A2 ) = 6, the volume is V (A2 ) = 3/2, and the Hermite parameter √ is γc (A2 ) = 2/ 3 = 1.155 (0.62 dB). Therefore A2 is denser than the integer lattice Z2 , for which d2min (Z2 ) = V (Z2 ) = γc (Z2 ) = 1. Exercise 1 (cont.) Show that if C is an (n, k, d) binary linear block code with Nd weight-d words, then the mod-2 lattice ΛC has the following geometrical parameters: d2min (ΛC ) = min{d, 4}; ⎧ d if d < 4; ⎨ 2 Nd , 2n, if d > 4; Kmin (ΛC ) = ⎩ d 2 Nd + 2n, if d = 4; V (ΛC ) = 2n−k ; d2min (ΛC ) , γc (ΛC ) = 2η(C) (14.4) (14.5) (14.6) (14.7) where η(C) = 2(n − k)/n is the redundancy of C in bits per two dimensions. Exercise 2. Show that γc (Λ) is invariant to scaling, orthogonal transformations, and Cartesian products; i.e., γc (αU Λm ) = γc (Λ), where α > 0 is any scale factor, U is any orthogonal matrix, and m ≥ 1 is any positive integer. Show that γc (αU Zn ) = 1 for any version αU Zn of any integer lattice Zn . 14.2 Lattice constellations A lattice constellation C(Λ, R) = (Λ + t) ∩ R (14.8) is the finite set of points in a lattice translate Λ + t that lie within a compact bounding region R of n-space. Example 4. An M -PAM constellation α{±1, ±3, . . . , ±(M − 1)} is a one-dimensional lattice constellation C(2αZ, R) with Λ + t = 2α(Z + 1) and R = [−αM, αM ]. The key geometric properties of the region R are • its volume V (R) =  R dx; • the average energy P (R) per dimension of a uniform probability density function over R:  x2 dx . (14.9) P (R) = V (R) R n The normalized second moment of R is defined as the dimensionless parameter G(R) = P (R) . V (R)2/n (14.10) Example 4 (cont.). The key geometrical parameters of R = [−αM, αM ] are V (R) = 2αM , P (R) = α2 M 2 /3, and G(R) = 1/12. Exercise 3. Show that G(R) is invariant to scaling, orthogonal transformations, and Cartesian products; i.e., G(αU Rm ) = G(R), where α > 0 is any scale factor, U is any orthogonal matrix, and m ≥ 1 is any positive integer. Show that G(αU [−1, 1)n ) = 1/12 for any version αU [−1, 1)n of any n-cube [−1, 1)n centered at the origin. For performance analysis of large lattice constellations, one may use the following approximations, the first two of which are together known as the continuous approximation: • The size of the constellation is |C(Λ, R)| ≈ V (R) ; V (Λ) (14.11) • The average energy per dimension of a uniform discrete distribution over C(Λ, R) is P (C(Λ, R)) ≈ P (R); • The average number of nearest neighbors to any point in C(Λ, R) is ≈ Kmin (Λ). (14.12) Again, the union bound estimate (UBE) on probability of block decoding error is   √ d2 (Λ) min Pr(E) ≈ Kmin (Λ)Q . 4σ 2 (14.13) Since V (R) 2 2 ; log2 |C(Λ, R)| ≈ log2 n n V (Λ) P (R) P (C(Λ, R)) ≈ ; SNR = σ2 σ2 SNR V (Λ)2/n P (R) SNRnorm ≈ ρ = , 2 V (R)2/n σ 2 ρ= we may write the UBE as √ Pr(E) ≈ Kmin (Λ)Q (γc (Λ)γs (R)(3 SNRnorm )) , (14.14) where the nominal coding gain of Λ and the shaping gain of R are defined respectively as γc (Λ) = d2min (Λ) ; V (Λ)2/n (14.15) γs (R) = V (R)2/n 1/12 = . 12P (R) G(R) (14.16) For a baseline M -PAM constellation with Λ = 2αZ and R = [−αM, αM ], we have γc (Λ) = γs (R) = 1 and Kmin (Λ) ≈ 2, so the UBE reduces to the baseline expression √ Pr(E) ≈ 2Q (3 SNRnorm ). The nominal coding gain γc (Λ) measures the increase in density of Λ over the baseline integer lattice Z (or Zn ). The shaping gain γs (R) measures the decrease in average energy of R relative to an interval [−α, α] (or√an n-cube [−α, α]n ). Both contribute a multiplicative factor of gain to the argument of the Q (·) function. As before, the effective coding gain is reduced by the error coefficient Kmin (Λ). The probability of block decoding error per two dimensions is √ Ps (E) ≈ Ks (Λ)Q (γc (Λ)γs (R)(3 SNRnorm )), (14.17) in which the normalized error coefficient per two dimensions is Ks (Λ) = 2Kmin (Λ)/n. √ Graphically, a curve of the form Ps (E) ≈ Ks (Λ)Q (γc (Λ)γs (R)(3 SNRnorm )) may be obtained √ simply by moving the baseline curve Ps (E) = 4Q (3 SNRnorm ) to the left by γc (Λ) and γs (R) (in dB), and upward by a factor of Ks (Λ)/4. Such simple manipulations of the baseline curve as a function of γc (Λ), γs (R) and Ks (Λ) again are an easy and useful design tool for lattice constellations of moderate complexity. 14.3 Shaping gain and shaping techniques Although shaping is a newer and less important topic than coding, we discuss it first because its story is quite simple. The n-dimensional shaping region R that minimizes G(R) is obviously an n-sphere. The key geometrical parameters of an n-sphere of radius r (for n even) are: V⊗ (n, r) = P⊗ (n, r) = G⊗ (n, r) = (πr2 )n/2 ; (n/2)! r2 ; n+2 P⊗ (n, r) ((n/2)!)2/n . = π(n + 2) V⊗ (n, r)2/n By Stirling’s approximation, m! → (m/e)m as m → ∞, which implies G⊗ (n, r) → γs ⊗ (n, r) = 1 ; 2πe 1/12 πe → (1.53 dB). G⊗ (n, r) 6 Thus shaping gain is limited to a finite value as n → ∞, namely πe/6 (1.53 dB), which is called the ultimate shaping gain. The shaping gain of an n-sphere is plotted for dimensions n ≤ 24 in Figure 2. Note that the shaping gain of a 16-sphere already exceeds 1 dB. 1.0 Shaping gain (dB) 1.5 0.5 0.0 0 4 8 12 16 20 24 Dimension Figure 2. Shaping gains of n-spheres for n ≤ 24. The projection of a uniform probability distribution over an n-sphere onto one or two dimensions is a nonuniform probability distribution that approaches a Gaussian distribution as n → ∞. The ultimate shaping gain of πe/6 (1.53 dB) may alternatively be derived as the difference between the average power of a uniform distribution over an interval and that of a Gaussian distribution with the same differential entropy. Shaping thus induces a Gaussian-like probability distribution on a one-dimensional PAM or two-dimensional QAM constellation, rather than an equiprobable distribution. In principle, with spherical shaping, the lower-dimensional constellation will become arbitrarily large, even with fixed average power. In practice, the lower-dimensional constellation is constrained by design to a certain region R to limit “shaping constellation expansion.” The n-dimensional shape then only approximates spherical shaping subject to this constraint, and the lower-dimensional probability distribution approaches a truncated Gaussian distribution within the region R. With large constellations, shaping can be implemented almost independently of coding by operations on the “most significant bits” of M -PAM or (M × M )-QAM constellation labels, which affect the gross shape of the n-dimensional constellation. In contrast, coding affects the “least significant bits” and determines fine structure. Two practical schemes that can easily obtain shaping gains of 1 dB or more while limiting 2D shaping constellation expansion to a factor of 1.5 or less are “trellis shaping,” a kind of dual to trellis coding, and “shell mapping,” which uses generating-function techniques to enumerate the points in a Cartesian product constellation in approximate increasing order of energy. 14.4 Coding gains of dense lattices Finding the densest lattice packings in a given number of dimensions is a mathematical problem of long standing. A summary of the densest known packings is given in [Conway and Sloane, Sphere Packings, Lattices and Groups]. The nominal coding gains of these lattices in up to 24 dimensions is plotted in Figure 3. 3 Nominal coding gain (dB) 6 0 0 4 8 12 16 20 24 Dimension Figure 3. Nominal coding gains of densest lattices in dimensions n ≤ 24. In contrast to shaping gain, the nominal coding gains of dense n-dimensional lattices become infinite as n → ∞. Example 5 (Barnes-Wall lattices). For all integer m ≥ 0, there exists a 2m+1 -dimensional Barnes-Wall lattice BW2m+1 whose nominal coding gain is 2m/2 (see next subsection). The twodimensional BW lattice is Z2 . In 4, 8, and 16 dimensions the BW lattices (denoted by D4 , E8 and Λ16 , respectively) are the densest lattices known. For large m, considerably denser lattices are known. Exercise 1 (cont.) Show that the mod-2 lattices corresponding to the (4, 3, 2) and (4, 1, 4) binary linear block codes have coding gain 21/2 (1.51 dB); these lattices are in fact versions of D4 . Show that the mod-2 lattice corresponding to the (8, 4, 4) binary linear block code has coding gain 2 (3.01 dB); this lattice is in fact a version of E8 . Show that no mod-2 lattice has a nominal coding gain more than 4 (6.02 dB). However, effective coding gains cannot become infinite. Indeed, the Shannon limit shows that no lattice can have a combined effective coding gain and shaping gain greater than 9 dB at Ps (E) ≈ 10−6 . This limits the maximum possible effective coding gain to 7.5 dB, since shaping gain can contribute up to 1.53 dB. What limits effective coding gain is the number of near neighbors, which becomes very large for high-dimensional dense lattices. Example 5 (cont.) The kissing number of the 2m+1 -dimensional Barnes-Wall lattice is (2i + 2). Kmin (BW2m+1 ) = 1≤i≤m+1 For m = 0, 1, 2, 3, 4, . . . these numbers are 4, 24, 240, 4320, 146880, . . . . Thus while BW32 has a nominal coding gain of 4 (6.02 dB), its kissing number is 146880, so its effective coding gain by our rule of thumb is only about 3.8 dB. BW128 has a nominal coding gain of 8 (9.03 dB), but a kissing number of 1 260 230 400, so its effective coding gain by our rule of thumb is only about 4.6 dB. These calculations indicate how the effective coding gain of higher-dimensional lattices eventually saturates. Example 6 (Leech Lattice). The Leech lattice L24 , a remarkably dense lattice in 24 dimensions, has a nominal coding gain of 4 (6.02 dB), but it has a kissing number of 196560, so its effective coding gain by our rule of thumb is only about 3.6 dB. 14.4.1 Barnes-Wall lattices The Barnes-Wall lattices (1959) are an infinite family of n-dimensional lattices that are analogous to the Reed-Muller binary block codes. For n ≤ 16, they are the best lattices known. For greater n, they are not in general the best lattices known, but in terms of performance vs. decoding complexity they are still quite good, since they admit relatively simple decoding algorithms. For any integer m ≥ 0, there exists an (n = 2m+1 )-dimensional BW lattice, denoted BW2m+1 , that has minimum squared Euclidean distance d2min (BW2m+1 ) = 2m , normalized volume V (BW2m+1 )2/n = 2m/2 , and therefore nominal coding gain γc (BW2m+1 ) = 2m/2 . In 2 dimensions, the Barnes-Wall lattice BW2 is the integer lattice Z2 , which is the mod-2 lattice corresponding to the (2, 2, 1) code. The mod-2 lattice RZ2 corresponding to the (2, 1, 2) code is a sublattice of Z2 ; it is the set of all integer 2-tuples in which both integers are even or both integers are odd. It can be obtained √ by rotating Z2 by 45◦ and scaling by 2; i.e., by transforming Z2 by the 2 × 2 Hadamard matrix R= 1 1 1 −1 . Consequently d2min (RZ2 ) = 2 and V (RZ2 ) = 2. The lattice 2Z2 (the mod-2 lattice corresponding to the (2, 0, ∞) code) is a sublattice of RZ2 with d2min (2Z2 ) = 4 and V (2Z2 ) = 4. Note that 2Z2 = R(RZ2 ), since R2 = 2I. In fact, we see that there is a lattice chain Z2 /RZ2 /2Z2 /2RZ2 /4Z2 / . . . with minimum squared distances 1/2/4/8/16/ . . .. The remaining BW lattices may be constructed recursively from this chain by the |u|u + v| construction. BW2m+1 is constructed from BW2m and RBW2m as BW2m+1 = {(u, u + v) | u ∈ BW2m , v ∈ RBW2m }. More generally, for any j ≥ 0, Rj BW2m+1 = {(u, u + v) | u ∈ Rj BW2m , v ∈ Rj+1 BW2m }. It is then easy to prove the following facts by recursion: (a) The dimension of BW2m+1 is n = 2m+1 . (b) The volume of BW2m+1 is V (BW2m+1 ) = V (BW2m )V (R(BW2m )) = 22 This recursion yields V (BW2m+1 ) = 2m2 m−1 m−1 V (BW2m )2 . , or V (BW2m+1 )2/n = 2m/2 . (c) The minimum squared distance of BW2m+1 is d2min (BW2m+1 ) = 2m . (d) {Rj BW2m+1 , j ≥ 1} is a chain of sublattices with minimum squared distances and normalized volumes increasing by a factor of 2 for each increment of j. We verify that these assertions hold for BW2 = Z2 . For m ≥ 1, the dimension and volume follow from the construction. We verify the distance as follows: (a) if u = 0, then ||(0, v)||2 = ||v||2 ≥ 2m if v = 0, since v ∈ RBW2m . (b) if u + v = 0, then u = −v ∈ RBW2m and ||(−v, 0)||2 ≥ 2m if v = 0. (c) if u = 0 and u + v = 0, then both u and u + v are in BW2m (since RBW2m is a sublattice of BW2m ), so ||(u, u + v)||2 = ||u||2 + ||u + v||2 ≥ 2 · 2m−1 = 2m . Equality clearly holds for (0, v), (v, 0) or (u, u) if we choose v or u as a minimum-weight vector from their respective lattices. Finally, the sublattice chain for m follows from the sublattice chain for m − 1 by construction. The |u|u + v| construction suggests the following tableau of BW lattices. Here D4 = BW4 , E8 = BW8 , and Λn = BWn for n = 2m+1 ≥ 16. Also, we use R2 = 2I2m . Z2 RZ2 2Z2 2RZ2 4Z2 D4 E8 RD4 Λ16 RE8 2D4 Λ32 RΛ16 2E8 2RD4 Λ64 RΛ32 2Λ16 2RE8 Λ128 RΛ64 2Λ32 Λ256 RΛ128 Λ512 Figure 4. Tableau of Barnes-Wall lattices. In this tableau each BW lattice lies halfway between the two lattices of half the dimension that are used to construct it in the |u|u + v| construction, from which we can immediately deduce its normalized volume. For example, E8 has the same normalized volume as RZ2 , namely V (E8 )2/8 = 2. However, d2min (E8 ) = 4, whereas d2min (RZ2 ) = 2. Therefore the nominal coding gain of E8 is twice that of RZ2 , namely γc (E8 ) = 2 (3.01 dB). 14.5 Trellis codes Trellis codes are dense packings of Euclidean-space sequences in a sequence space which is in principle infinite-dimensional. Trellis codes are to lattices as convolutional codes are to block codes. We will see that, just as binary convolutional codes provide a better performance/complexity tradeoff than binary block codes in the power-limited regime, trellis codes provide a better performance/complexity tradeoff than lattices in the bandwidth-limited regime, although the difference is not as dramatic. The key ideas in the invention of trellis codes were: • use of minimum squared Euclidean distance as the design criterion; • coding on subsets of signal sets using convolutional coding principles (e.g., trellises and the Viterbi algorithm). A typical large-constellation trellis code is designed as follows. One starts with a large lowdimensional constellation, which in practice is almost always a lattice constellation C(Zn , R) based on a version of an n-dimensional integer lattice Zn , such as M -PAM or (M × M )-QAM. (M -PSK constellations are sometimes used in the intermediate (ρ ≈ 2 b/2D) regime because of their constant-energy property, but we will not discuss M -PSK trellis codes here.) One can then form an m-fold Cartesian product constellation C(Zn , R)m = C(Zmn , Rm ), which is still based on an mn-dimensional integer lattice Zmn . The constellation C(Zmn , Rm ) is partitioned into subsets of equal size, where the number of subsets is typically a power of two, say 2b . Initially this was done by a sequence of twoway partitions in which the minimum squared distance within subsets was maximized at each level. Subsequently it was recognized that the resulting constellations were almost always lattice constellations C(Λ , Rm ) based on a sublattice Λ of index |Zmn /Λ | = 2b in Zmn . In other words, Zmn is the union of 2b cosets of Λ , and the 2b subsets are the points of C(Zmn , Rm ) that lie in each such coset. The sublattice Λ is usually chosen to be as dense as possible. Example 7 (1D partitions). In one dimension, there is a chain of sublattices of Z as follows: Z ⊇ 2Z ⊇ 4Z ⊇ 8Z ⊇ · · · , which may alternatively be written as Z/2Z/4Z/8Z/ · · ·. Each partition is two-way; that is, each lattice is the union of two cosets of the next sublattice. The corresponding minimum squared distances are 1/4/16/64/ · · ·. Thus an M -PAM constellation C(Z, [−M/2, M/2]) with minimum squared distance 1 may be partitioned into 2 subsets of the form C(2Z, [−M/2, M/2]) with minimum squared distance 4 within subsets, or 4 subsets of the form C(4Z, [−M/2, M/2]) with minimum squared distance 16 within subsets, and so forth. Example 8 (2D partitions). In two dimensions, there is a chain of sublattices of Z2 as follows: Z2 ⊇ RZ2 ⊇ 2Z2 ⊇ 2RZ2 ⊇ · · · , where R is the 2 × 2 Hadamard matrix as above. This chain may alternatively be written as Z2 /RZ2 /2Z2 /2RZ2 / · · ·. Each partition is two-way. The corresponding minimum squared distances are 1/2/4/8/· · ·. Thus a QAM constellation C(Z2 , R) with minimum squared distance 1 may be partitioned into 2 subsets of the form C(RZ2 , R) with minimum squared distance 2 within subsets, or 4 subsets of the form C(2Z2 , R) with minimum squared distance 4 within subsets, and so forth. The bounding region R should contain an equal number of points in each subset. Example 9 (4D partitions). In four dimensions, there is a chain of sublattices of Z4 as follows: Z4 ⊇ D4 ⊇ RZ4 ⊇ RD4 ⊇ · · · , where D4 is the 4-dimensional Barnes-Wall lattice and R is the 4 × 4 matrix ⎡ ⎤ 1 1 0 0 ⎢ 1 −1 0 ⎥ 0 ⎥ R=⎢ . ⎣ 0 0 1 1 ⎦ 0 0 1 −1 (Alternatively, this is the chain of mod-2 lattices corresponding to the (4, 4, 1), (4, 3, 2), (4, 2, 2) and (4, 1, 4) binary linear block codes.) This chain may alternatively be written as Z4 /D4 /RZ4 /RD4 / · · ·. Each partition is two-way. The corresponding minimum squared distances are 1/2/2/4/· · ·. Thus a 4D constellation C(Z4 , R) with minimum squared distance 1 may be partitioned into 2 subsets of the form C(D4 , R) with minimum squared distance 2 within subsets, 8 subsets of the form C(2D4 , R) with minimum squared distance 4 within subsets, etc. Again, the bounding region R should contain an equal number of points in each subset. A trellis code encoder then operates as shown in Figure 5. Some of the input data bits are encoded in a rate-k/b 2ν -state binary convolutional encoder. Almost always k is chosen to equal b−1, so the code redundancy is 1 bit per mn dimensions. The encoder output sequence of b-tuples selects a corresponding sequence of subsets of C(Zmn , Rm ) (cosets of Λ ). The convolutional code and the labeling of the subsets are chosen primarily to maximize the minimum squared distance d2min (C) between signal point sequences in any possible encoded subset sequence, and secondarily to minimize the maximum possible number Kmin (C) of nearest-neighbor sequences. Finally, other input data bits select the actual signal points to be transmitted from the selected subsets. If there is any shaping, it is done at this level. input data Encoder for convolutional code C coded data (label sequence) Map from labels to subsets (cosets of ' ) � subset sequence other input data (uncoded) Select signal points from subsets signal point sequence in C Figure 5. Trellis code encoder. The nominal coding gain of such a trellis code is γc (C) = d2min (C)2−η(C) , (14.18) where η(C) = 2/mn is the redundancy of the convolutional code in bits per two dimensions. The factor 2η(C) may be thought of as the normalized volume of the trellis code per two dimensions, if the signal constellation is a lattice constellation based on an integer lattice Zmn . The effective coding gain is reduced by the amount that the error coefficient 2Kmin (C)/mn per two dimensions exceeds the baseline M -PAM error coefficient of 4 per two dimensions, again according to the rule of thumb that a factor of 2 increase costs 0.2 dB. Exercise 1 (cont.) Let C be a rate-k/n binary linear convolutional code with free distance d and Nd minimum-weight code sequences per n dimensions. Define the corresponding mod2 trellis code ΛC to be the set of all integer sequences x with D-transform x(D) such that x(D) ≡ c(D) mod 2 for some code sequence c(D) in C. (a) Show that an encoder as in Figure 5 based on the convolutional code C and the lattice partition Zn /2Zn is an encoder for this mod-2 trellis code. (b) Show that ΛC has the group property. (c) Show that ΛC has the following parameters: d2min (ΛC ) = min{d, 4}; ⎧ d if d < 4; ⎨ 2 Nd , 2n, if d > 4; Kmin (ΛC ) = ⎩ d 2 Nd + 2n, if d = 4; γc (ΛC ) = d2min (ΛC )2−η(C) , (14.19) (14.20) (14.21) where η(C) = 2(n − k)/n is the redundancy of C in bits per two dimensions. The encoder redundancy η(C) also leads to a “coding constellation expansion ratio” which √ is a factor of 2η(C) per two dimensions—i.e., a factor of 4, 2, 2, . . . for 1D, 2D, 4D,. . . codes, respectively. Minimization of coding constellation expansion has motivated the increasing use of higher-dimensional trellis codes. A trellis code may be decoded by a Viterbi algorithm (VA) decoder, as follows. Given a received point r in Rmn , the received first finds the closest signal point to r in each subset. A VA decoder then finds the closest code sequence to the entire received sequence. The decoding complexity is usually dominated by the complexity of the VA decoder, which to first order is dominated by the branch complexity 2ν+k of the convolutional code, normalized by the dimension mn. 6 Ung 1D 5 Wei 8D 64-state, 4D coding gain (dB) Ung 2D Wei 4D 16-state, Wei 4D 32-state, 2D Effective Wei 8D 32-state, 4D 4 64-state, 8D Ung 1D 8-state, 2D (V.32) Ung 2D 3 10 100 1000 10000 Normalized complexity Figure 6. Effective coding gain vs. complexity for Ungerboeck and Wei codes. Figure 6 shows the effective coding gains of certain important families of trellis codes versus their decoding complexity, measured by a detailed operation count. The codes considered are: (a) The original 1D (PAM) trellis codes of Ungerboeck (1982), which are based on rate-1/2 convolutional codes (η(C) = 2) with 2 ≤ ν ≤ 9 and the 4-way partition Z/4Z. (b) The 2D (QAM) trellis codes of Ungerboeck, which (apart from the simplest 4-state code) are based on rate-2/3 convolutional codes (η(C) = 1) with 3 ≤ ν ≤ 9 and the 8-way partition Z2 /2RZ2 . (c) The 4D trellis codes of Wei (1987), all with η(C) = 1/2, based on (a) rate-2/3 8- and 16-state convolutional codes and the 8-way partition Z4 /RD4 ; (b) a rate-3/4 32-state convolutional code and the 16-way partition Z4 /2Z4 ; (c) a rate-4/5 64-state convolutional code and the 32-way partition Z4 /2D4 . (d) Two families of 8D trellis codes of Wei (η(C) = 1/4). The V.32 modem (1984) uses an 8-state 2D trellis code, also due to Wei (1984), whose performance/complexity tradeoff is the same as that as that of the original 8-state 2D Ungerboeck code, but which uses a nonlinear convolutional encoder to achieve 90◦ rotational invariance. This code has an effective coding gain of about 3.6 dB, a branch complexity of 25 (per two dimensions), and a coding constellation expansion ratio of 2. The V.34 modem (1994) specifies three 4D trellis codes, with performance and complexity equivalent √ to the 4D Wei codes circled on Figure 6. All have a coding constellation expansion ratio of 2. The 16-state code is the original 16-state 4D Wei code, which has an effective coding gain of about 4.2 dB and a branch complexity of 26 (per four dimensions). The 32-state code is due to Williams and is based on the 16-way partition Z4 /HZ4 , where H is a 4 × 4 Hadamard matrix, to ensure that there are no minimum-distance error events whose length is only two dimensions; it has an effective coding gain of about 4.5 dB and a branch complexity of 28 (per four dimensions) The 64-state code is a modification of the original 4D Wei code, modified to prevent quasicatastrophic error propagation; it has an effective coding gain of about 4.7 dB and a branch complexity of 210 (per four dimensions). It is noteworthy that no one has improved on the performance vs. complexity tradeoff of the original 1D and 2D trellis codes of Ungerboeck or the subsequent multidimensional codes of Wei, and by this time it seems safe to predict that no one will ever do so. There have however been new trellis codes that enjoy other properties with about the same performance and complexity, such as those described in the previous two paragraphs, and there may still be room for further improvements of this kind. Finally, we see that trellis codes have a performance/complexity advantage over lattice codes, when used with maximum-likelihood decoding. Effective coding gains of 4.2–4.7 dB, better than that of the Leech lattice L24 or of BW32 , are attainable with less complexity (and much less constellation expansion). 512-state 1D or 2D trellis codes can achieve effective coding gains of the order of 5.5 dB, which is superior to that of lattice codes of far greater complexity. On the other hand, it seems very difficult to obtain effective coding gains of greater than 6 dB. This is not surprising, because at Ps (E) ≈ 10−6 the effective coding gain at the Shannon limit would be about 7.5 dB, and at the cutoff rate limit it would be about 5.8 dB. To approach the Shannon limit, much more complicated codes and decoding methods are necessary. 14.6 Sequential decoding in the high-SNR regime In the bandwidth-limited regime, the cutoff rate limit is a factor of 4/e (1.68 dB) less than capacity. Therefore sequential decoders should be able to operate within about 1.7 dB of the Shannon limit; i.e., sequential decoders should be able to achieve an effective coding gain of about 6 dB at Ps (E) ≈ 10−6 . Several theses (Wang, Ljungberg, Maurer) have confirmed that sequential decoders are indeed capable of such performance. 14.7 Multilevel codes and multistage decoding To approach the Shannon limit even more closely, it is clear that much more powerful codes must be used, with non-ML but near-ML decoding. Multilevel codes and multistage decoding may be used for this purpose. Multilevel coding may be based on a chain of sublattices of Zn , Λ0 = Zn ⊇ Λ1 ⊇ · · · ⊇ Λr−1 ⊇ Λr , which induce a chain of lattice partitions Λj−1 /Λj , 1 ≤ j ≤ r. A different encoder as in Figure 5 may be used independently on each such lattice partition. Moreover, with multistage decoding, each level is decoded independently. Remarkably, such a multilevel scheme incurs no loss in channel capacity, compared to a singlelevel code based on the partition Zn /Λr ; the capacity C(Zn /Λr ) of the partition Zn /Λr is equal to the sum of the capacities C(Λj−1 /Λj ) at each level. If the partition Zn /Λr is “large enough” and appropriately scaled, then C(Zn /Λr ) approaches the capacity of the Gaussian channel. All of the partitions Λj−1 /Λj may even be binary; e.g., one may use the standard onedimensional or two-dimensional chains Z ⊇ 2Z ⊇ 4Z ⊇ 8Z ⊇ · · · ; Z2 ⊇ RZ2 ⊇ 2Z2 ⊇ 2RZ2 ⊇ 4Z2 ⊇ · · · . Then one can use a binary code of rate close to C(Λj−1 /Λj ) at each level to approach the Shannon limit. In particular, by using binary turbo codes of appropriate rate at each level, it has been shown that one can get within 1 dB of the Shannon limit (Wachsmann and Huber). Powerful probabilistic coding methods such as turbo codes are really needed only at the higher levels. At the lower levels, the channels become quite clean and the capacity C(Λj−1 /Λj ) approaches log2 |Λj−1 /Λj |, so that the desired redundancy approaches zero. For these levels, algebraic codes and decoding methods may be more appropriate. In summary, multilevel codes and multistage decoding allow the Shannon limit to be approached as closely in the bandwidth-limited regime as it can be approached in the power-limited regime with binary codes. 14.8 Multilevel turbo codes A number of varieties of multilevel turbo codes based on multiple component trellis codes have been developed for the bandwidth-limited regime by several authors (e.g., Berrou et al., Benedetto et al., Robertson and Wörz, Divsalar et al.). The performance of these codes seems to be comparable to that of binary turbo codes in the power-limited regime: i.e., within about 1 dB of the Shannon limit. However, such capacity-approaching codes do not seem to have been implemented yet in practice, to the best of our knowledge. 14.9 Bit-interleaved coded modulation In bit-interleaved coded modulation (BICM), the signals in a nonbinary constellation of size 2b are selected by b randomly interleaved encoded bits from a binary encoder. The effective binary channel is then an equiprobable mixture of b parallel channels. The receiver knows which channel is used for each bit, and therefore can compute the correct APP vector for each symbol. Capacityapproaching codes may be designed for this mixture channel. While capacity is typically slightly reduced on an AWGN channel, the “pragmatic” BICM approach has become quite popular.