Introduction to Binary Block Codes

Chapter 6 Introduction to binary block codes In this chapter we begin to study binary signal constellations, which are the Euclidean-space images of binary block codes. Such constellations have bit rate (nominal spectral efficiency) ρ ≤ 2 b/2D, and are thus suitable only for the power-limited regime. We will focus mainly on binary linear block codes, which have a certain useful algebraic structure. Specifically, they are vector spaces over the binary field F2 . A useful infinite family of such codes is the set of Reed-Muller codes. We discuss the penalty incurred by making hard decisions and then performing classical errorcorrection, and show how the penalty may be partially mitigated by using erasures, or rather completely by using generalized minimum distance (GMD) decoding. 6.1 Binary signal constellations In this chapter we will consider constellations that are the Euclidean-space images of binary codes via a coordinatewise 2-PAM map. Such constellations will be called binary signal constellations. A binary block code of length n is any subset C ⊆ {0, 1}n of the set of all binary n-tuples of length n. We will usually identify the binary alphabet {0, 1} with the finite field F2 with two elements, whose arithmetic rules are those of mod-2 arithmetic. Moreover, we will usually impose the requirement that C be linear ; i.e., that C be a subspace of the n-dimensional vector space (F2 )n of all binary n-tuples. We will shortly begin to discuss such algebraic properties. Each component xk ∈ {0, 1} of a codeword x ∈ C will be mapped to one of the two points ±α of a 2-PAM signal set A = {±α} ⊂ R according to a 2-PAM map s: {0, 1} → A. Explicitly, two standard ways of specifying such a 2-PAM map are s(x) = α(−1)x ; s(x) = α(1 − 2x). The first map is more algebraic in that, ignoring scaling, it is an isomorphism from the additive
binary group Z2 = {0, 1} to the multiplicative binary group {±1}, since s(x)·s(x
) = (−1)x+x = s(x + x
). The second map is more geometric, in that it is the composition of a map from {0, 1} ∈ F2 to {0, 1} ∈ R, followed by a linear transformation and a translation. However, ultimately both formulas specify the same map: {s(0) = α, s(1) = −α}. Under the 2-PAM map, the set (F2 )n of all binary n-tuples maps to the set of all real n-tuples of the form (±α, ±α, . . . , ±α). Geometrically, this is the set of all 2n vertices of an n-cube of side 2α centered on the origin. It follows that a binary signal constellation A
= s(C) based on a binary code C ⊆ (F2 )n maps to a subset of the vertices of this n-cube. The size of an N -dimensional binary constellation A
is thus bounded by |A
| ≤ 2n , and its bit rate ρ = (2/n) log2 |A
| is bounded by ρ ≤ 2 b/2D. Thus binary constellations can be used only in the power-limited regime. Since the n-cube constellation An = s((F2 )n ) = (s(F2 ))n is simply the n-fold Cartesian product An of the 2-PAM constellation A = s(F2 ) = {±α}, its normalized parameters are the same as those of 2-PAM, and it achieves no coding gain. Our hope is that by restricting to a subset A
⊂ An , a distance gain can be achieved that will more than offset the rate loss, thus yielding a coding gain. Example 1. Consider the binary code C = {000, 011, 110, 101}, whose four codewords are binary 3-tuples. The bit rate of C is thus ρ = 4/3 b/2D. Its Euclidean-space image s(C) is a set of four vertices of a 3-cube that form a regular tetrahedron, as shown in Figure 1. The minimum squared Euclidean distance of s(C) is d2min (s(C)) = 8α2 , and every signal point in s(C) has 3 nearest neighbors. The average energy of s(C) is E(s(C)) = 3α2 , so its average energy per bit is Eb = (3/2)α2 , and its nominal coding gain is γc (s(C)) = 4 d2min (s(C)) = 4Eb 3 (1.25 dB). (t000 (  ((((�  ( (  ((( t(  � 110  � @ J J@ � J@ � J@ � J @� t 101J�@ HH@    H@  Ht   011 Figure 1. The Euclidean image of the binary code C = {000, 011, 110, 101} is a regular tetrahedron in R3 . It might at first appear that the restriction of constellation points to vertices of an n-cube might force binary signal constellations to be seriously suboptimal. However, it turns out that when ρ is small, this apparently drastic restriction does not hurt potential performance very much. A capacity calculation using a random code ensemble with binary alphabet A = {±α} rather than R shows that the Shannon limit on Eb /N0 at ρ = 1 b/2D is 0.2 dB rather than 0 dB; i.e., the loss is only 0.2 dB. As ρ → 0, the loss becomes negligible. Therefore at spectral efficiencies ρ ≤ 1 b/2D, binary signal constellations are good enough. 6.2 Binary linear block codes as binary vector spaces Practically all of the binary block codes that we consider will be linear. A binary linear block code is a set of n-tuples of elements of the binary finite field F2 = {0, 1} that form a vector space over the field F2 . As we will see in a moment, this means simply that C must have the group property under n-tuple addition. We therefore begin by studying the algebraic structure of the binary finite field F2 = {0, 1} and of vector spaces over F2 . In later chapters we will study codes over general finite fields. In general, a field F is a set of elements with two operations, addition and multiplication, which satisfy the usual rules of ordinary arithmetic (i.e., commutativity, associativity, distributivity). A field contains an additive identity 0 such that a + 0 = a for all field elements a ∈ F, and every field element a has an additive inverse −a such that a + (−a) = 0. A field contains a multiplicative identity 1 such that a · 1 = a for all field elements a ∈ F, and every nonzero field element a has a multiplicative inverse a−1 such that a · a−1 = 1. The binary field F2 (sometimes called a Galois field, and denoted by GF(2)) is the finite field with only two elements, namely 0 and 1, which may be thought of as representatives of the even and odd integers, modulo 2. Its addition and multiplication tables are given by the rules of mod 2 (even/odd) arithmetic, with 0 acting as the additive identity and 1 as the multiplicative identity: 0+0=0 0·0=0 0+1=1 0·1=0 1+0=1 1·0=0 1+1=0 1·1=1 In fact these rules are determined by the general properties of 0 and 1 in any field. Notice that the additive inverse of 1 is 1, so −a = a for both field elements. In general, a vector space V over a field F is a set of vectors v including 0 such that addition of vectors and multiplication by scalars in F is well defined, and such that various other vector space axioms are satisfied. For a vector space over F2 , multiplication by scalars is trivially well defined, since 0v = 0 and 1v = v are automatically in V . Therefore all that really needs to be checked is additive closure, or the group property of V under vector addition; i.e., for all v, v
∈ V , v + v
is in V . Finally, every vector is its own additive inverse, −v = v, since v + v = 1v + 1v = (1 + 1)v = 0v = 0. In summary, over a binary field, subtraction is the same as addition. A vector space over F2 is called a binary vector space. The set (F2 )n of all binary n-tuples v = (v1 , . . . , vn ) under componentwise binary addition is an elementary example of a binary vector space. Here we consider only binary vector spaces which are subspaces C ⊆ (F2 )n , which are called binary linear block codes of length n. If G = {g1 , . . . , gk } is a set of vectors in a binary vector space V , then the set C(G) of all binary linear combinations � C(G) = { aj gj , aj ∈ F2 , 1 ≤ j ≤ k} j is a subspace of V , since C(G) evidently has the group property. The set G is called linearly independent if these 2k binary linear combinations are all distinct, so that the size of C(G) is |C(G)| = 2k . A set G of linearly independent vectors such that C(G) = V is called a basis for V , and the elements {gj , 1 ≤ j ≤ k} of the basis are called generators. The set G = {g1 , . . . , gk } may be arranged as a k × n matrix over F2 , called a generator matrix for C(G). The dimension of a binary vector space V is the number k of generators in any basis for V . As with any vector space, the dimension k and a basis G for V may be found by the following greedy algorithm: Initialization: Do loop: set k = 0 and G = ∅ (the empty set); if C(G) = V we are done, and dim V = k; otherwise, increase k by 1 and take any v ∈ V − C(G) as gk . Thus the size of V is always |V | = 2k for some integer k = dim V ; conversely, dim V = log2 |V |. An (n, k) binary linear code C is any subspace of the vector space (F2 )n with dimension k, or equivalently size 2k . In other words, an (n, k) binary linear code is any set of 2k binary n-tuples including 0 that has the group property under componentwise binary addition. Example 2 (simple binary linear codes). The (n, n) binary linear code is the set (F2 )n of all binary n-tuples, sometimes called the universe code of length n. The (n, 0) binary linear code is {0}, the set containing only the all-zero n-tuple, sometimes called the trivial code of length n. The code consisting of 0 and the all-one n-tuple 1 is an (n, 1) binary linear code, called the repetition code of length n. The code consisting of all n-tuples with an even number of ones is an (n, n − 1) binary linear code, called the even-weight or single-parity-check (SPC) code of length n. 6.2.1 The Hamming metric The geometry of (F2 )n is defined by the Hamming metric: wH (x) = number of ones in x. The Hamming metric satisfies the axioms of a metric: (a) Strict positivity: wH (x) ≥ 0, with equality if and only if x = 0; (b) Symmetry: wH (−x) = wH (x) (since −x = x); (c) Triangle inequality: wH (x + y) ≤ wH (x) + wH (y). Therefore the Hamming distance, dH (x, y) = wH (x − y) = wH (x + y), may be used to define (F2 )n as a metric space, called a Hamming space. We now show that the group property of a binary linear block code C leads to a remarkable symmetry in the distance distributions from each of the codewords of C to all other codewords. Let x ∈ C be a given codeword of C, and consider the set {x + y | y ∈ C} = x + C as y runs through the codewords in C. By the group property of C, x + y must be a codeword in C. Moreover, since x + y = x + y
if and only if y = y
, all of these codewords must be distinct. But since the size of the set x + C is |C|, this implies that x + C = C; i.e., x + y runs through all codewords in C as y runs through C. Since dH (x, y) = wH (x + y), this implies the following symmetry: Theorem 6.1 (Distance invariance) The set of Hamming distances dH (x, y) from any codeword x ∈ C to all codewords y ∈ C is independent of x, and is equal to the set of distances from 0 ∈ C, namely the set of Hamming weights wH (y) of all codewords y ∈ C. An (n, k) binary linear block code C is said to have minimum Hamming distance d, and is denoted as an (n, k, d) code, if d = min dH (x, y). x=y∈C Theorem 6.1 then has the immediate corollary: Corollary 6.2 (Minimum distance = minimum nonzero weight) The minimum Hamming distance of C is equal to the minimum Hamming weight of any nonzero codeword of C. More generally, the number of codewords y ∈ C at distance d from any codeword x ∈ C is equal to the number Nd of weight-d codewords in C, independent of x. Example 2 (cont.) The (n, n) universe code has minimum Hamming distance d = 1, and the number of words at distance 1 from any codeword is N1 = n. The (n, n − 1) SPC code has minimum weight and distance d = 2, and N2 = n(n − 1)/2. The (n, 1) repetition code has d = n and Nn = 1. By convention, the trivial (n, 0) code {0} is said to have d = ∞. 6.2.2 Inner products and orthogonality A symmetric, bilinear inner product on the vector space (F2 )n is defined by the F2 -valued dot product � x, y = x · y = xyT = xi yi , i where n-tuples are regarded as row vectors and “T ” denotes “transpose.” Two vectors are said to be orthogonal if x, y = 0. However, this F2 inner product does not have a property analogous to strict positivity: x, x = 0 does not imply that x = 0, but only that x has an even number of ones. Thus it is perfectly possible for a nonzero vector to be orthogonal to itself. Hence x, x does not have a key property of the Euclidean squared norm and cannot be used to define a metric space analogous to Euclidean space. The Hamming geometry of (F2 )n is very different from Euclidean geometry. In particular, the projection theorem does not hold, and it is therefore not possible in general to find an orthogonal basis G for a binary vector space C. Example 3. The (3, 2) SPC code consists of the four 3-tuples C = {000, 011, 101, 110}. Any two nonzero codewords form a basis for C, but no two such codewords are orthogonal. The orthogonal code (dual code) C ⊥ to an (n, k) code C is defined as the set of all n-tuples that are orthogonal to all elements of C: C ⊥ = {y ∈ (F2 )n | x, y = 0 for all x ∈ C}. Here are some elementary facts about C ⊥ : (a) C ⊥ is an (n, n − k) binary linear code, and thus has a basis H of size n − k.1 (b) If G is a basis for C, then a set H of n − k linearly independent n-tuples in C ⊥ is a basis for C ⊥ if and only if every vector in H is orthogonal to every vector in G. (c) (C ⊥ )⊥ = C. A basis G for C consists of k linearly independent n-tuples in C, and is usually written as a k × n generator matrix G of rank k. The code C then consists of all binary linear combinations C = {aG, a ∈ (F2 )k }. A basis H for C ⊥ consists of n − k linearly independent n-tuples in C ⊥ , and is usually written as an (n − k) × n matrix H; then C ⊥ = {bH, b ∈ (F2 )n−k }. According to property (b) above, C and C ⊥ are dual codes if and only if their generator matrices satisfy GH T = 0. The transpose H T of a generator matrix H for C ⊥ is called a parity-check matrix for C; it has the property that a vector x ∈ (F2 )n is in C if and only if xH T = 0, since x is in the dual code to C ⊥ if and only if it is orthogonal to all generators of C ⊥ . Example 2 (cont.; duals of simple codes). In general, the (n, n) universe code and the (n, 0) trivial code are dual codes. The (n, 1) repetition code and the (n, n − 1) SPC code are dual codes. Note that the (2, 1) code {00, 11} is both a repetition code and an SPC code, and is its own dual; such a code is called self-dual. (Self-duality cannot occur in real or complex vector spaces.) 6.3 Euclidean-space images of binary linear block codes In this section we derive the principal parameters of a binary signal constellation s(C) from the parameters of the binary linear block code C on which it is based, namely the parameters (n, k, d) and the number Nd of weight-d codewords in C. The dimension of s(C) is N = n, and its size is M = 2k . It thus supports k bits per block. The bit rate (nominal spectral efficiency) is ρ = 2k/n b/2D. Since k ≤ n, ρ ≤ 2 b/2D, and we are in the power-limited regime. Every point in s(C) is of the form (±α, ±α, . . . , ±α), and therefore every point has energy nα2 ; i.e., the signal points all lie on an n-sphere of squared radius nα2 . The average energy per block is thus E(s(C)) = nα2 , and the average energy per bit is Eb = nα2 /k. If two codewords x, y ∈ C have Hamming distance dH (x, y), then their Euclidean images s(x), s(y) will be the same in n − dH (x, y) places, and will differ by 2α in dH (x, y) places, so 1 The standard proof of this fact involves finding a systematic generator matrix G = [Ik | P ] for C, where Ik is the k × k identity matrix and P is a k × (n − k) check matrix. Then C = {(u, uP ), u ∈ (F2 )k }, where u is a free information k-tuple and uP is a check (n − k)-tuple. The dual code C ⊥ is then evidently the code generated by H = [−P T | In−k ], where P T is the transpose of P ; i.e., C ⊥ = {(−vP T , v), v ∈ (F2 )n−k }, whose dimension is n − k. A more elegant proof based on the fundamental theorem of group homomorphisms (which the reader is not expected to know at this point) is as follows. Let M be the |C ⊥ | × n matrix whose rows are the codewords of C ⊥ . ⊥  yM T ; i.e., yM T is the set of inner products Consider the homomorphism M T : (F2 )n → (F2 )|C | defined by y → n of an n-tuple y ∈ (F2 ) with all codewords x ∈ C ⊥ . The kernel of this homomorphism is evidently C. By the fundamental theorem of homomorphisms, the image of M T (the row space of M T ) is isomorphic to the quotient space (F2 )n /C, which is isomorphic to (F2 )n−k . Thus the column rank of M is n − k. But the column rank is equal to the row rank, which is the dimension of the row space C ⊥ of M . their squared Euclidean distance will be2 s(x) − s(y) Therefore 2 = 4α2 dH (x, y). d2min (s(C)) = 4α2 dH (C) = 4α2 d, where d = dH (C) is the minimum Hamming distance of C. It follows that the nominal coding gain of s(C) is γc (s(C)) = d2min (s(C)) kd = . 4Eb n (6.1) Thus the parameters (n, k, d) directly determine γc (s(C)) in this very simple way. (This gives another reason to prefer Eb /N0 to SNRnorm in the power-limited regime.) Moreover, every vector s(x) ∈ s(C) has the same number of nearest neighbors Kmin (s(x)), namely the number Nd of nearest neighbors to x ∈ C. Thus Kmin (s(C)) = Nd , and Kb (s(C)) = Nd /k. Consequently the union bound estimate of Pb (E) is √ Pb (E) ≈ Kb (s(C))Q (γc (s(C))(2Eb /N0 )) � � Nd √ dk Q 2Eb /N0 . = k n (6.2) In summary, the parameters and performance of the binary signal constellation s(C) may be simply determined from the parameters (n, k, d) and Nd of C. Exercise 1. Let C be an � (n, k, d) binary linear code with d odd. Show that if we append an overall parity check p = i xi to each codeword x, then we obtain an (n + 1, k, d + 1) binary linear code C
with d even. Show that the nominal coding gain γc (C
) is always greater than γc (C) if k > 1. Conclude that we can focus primarily on linear codes with d even. Exercise 2. Show that if C is a binary linear block code, then in every coordinate position either all codeword components are 0 or half are 0 and half are 1. Show that a coordinate in which all codeword components are 0 may be deleted (“punctured”) without any loss in performance, but with savings in energy and in dimension. Show that if C has no such all-zero coordinates, then s(C) has zero mean: m(s(C)) = 0. 6.4 Reed-Muller codes The Reed-Muller (RM) codes are an infinite family of binary linear codes that were among the first to be discovered (1954). For block lengths n ≤ 32, they are the best codes known with minimum distances d equal to powers of 2. For greater block lengths, they are not in general the best codes known, but in terms of performance vs. decoding complexity they are still quite good, since they admit relatively simple ML decoding algorithms. 2 Moreover, the Eudlidean-space inner product of s(x) and s(y) is s(x), s(y) = (n − dH (x, y))α2 + dH (x, y)(−α2 ) = (n − 2dH (x, y))α2 . Therefore s(x) and s(y) are orthogonal if and only if dH (x, y) = n/2. Also, s(x) and s(y) are antipodal (s(x) = −s(y)) if and only if dH (x, y) = n. For any integers m ≥ 0 and 0 ≤ r ≤ m, there exists an RM code, denoted by RM(r, m), that has length n = 2m and minimum Hamming distance d = 2m−r , 0 ≤ r ≤ m. For r = m, RM(m, m) is defined as the universe (2m , 2m , 1) code. It is helpful also to define RM codes for r = −1 by RM(−1, m) = (2m , 0, ∞), the trivial code of length 2m . Thus for m = 0, the two RM codes of length 1 are the (1, 1, 1) universe code RM(0, 0) and the (1, 0, ∞) trivial code RM(−1, 0). The remaining RM codes for m ≥ 1 and 0 ≤ r < m may be constructed from these elementary codes by the following length-doubling construction, called the |u|u + v| construction (originally due to Plotkin). RM(r, m) is constructed from RM(r − 1, m − 1) and RM(r, m − 1) as RM(r, m) = {(u, u + v) | u ∈ RM(r, m − 1), v ∈ RM(r − 1, m − 1)}. (6.3) From this construction, it is easy to prove the following facts by recursion: (a) RM(r, m) is a binary linear block code with length n = 2m and dimension k(r, m) = k(r, m − 1) + k(r − 1, m − 1). (b) The codes are nested, in the sense that RM(r − 1, m) ⊆ RM(r, m). (c) The minimum distance of RM(r, m) is d = 2m−r if r ≥ 0 (if r = −1, then d = ∞). We verify that these assertions hold for RM(0, 0) and RM(−1, 0). For m ≥ 1, the linearity and length of RM(r, m) are obvious from the construction. The dimension (size) follows from the fact that (u, u + v) = 0 if and only if u = v = 0. Exercise 5 below shows that the recursion for k(r, m) leads to the explicit formula � �m� k(r, m) = , j (6.4) 0≤j≤r where �m� j denotes the combinatorial coefficient m! j!(m−j)! . The nesting property for m follows from the nesting property for m − 1. Finally, we verify that the minimum nonzero weight of RM(r, m) is 2m−r as follows: (a) if u = 0, then wH ((0, v)) = wH (v) ≥ 2m−r if v = 0, since v ∈ RM(r − 1, m − 1). (b) if u + v = 0, then u = v ∈ RM(r − 1, m − 1) and wH ((v, 0)) ≥ 2m−r if v = 0. (c) if u = 0 and u + v = 0, then both u and u + v are in RM(r, m − 1) (since RM(r − 1, m − 1) is a subcode of RM(r, m − 1)), so wH ((u, u + v)) = wH (u) + wH (u + v) ≥ 2 · 2m−r−1 = 2m−r . Equality clearly holds for (0, v), (v, 0) or (u, u) if we choose v or u as a minimum-weight codeword from their respective codes. The |u|u + v| construction suggests the following tableau of RM codes: r = m, d = 1; * universe codes   32, 1) (32,    (16, 16, 1)    r = m − 1, d = 2;  * SPC codes  31, 2) (8,8, 1) (32,          (4, 4, 1) (16, 15, 2)     *       26, 4) (2,2, 1) (8,7, 2) (32,    H      H    HH 11, 4) (1, 1, 1) (4,3, 2) (16,  H   H H HH HH     HH H (2, 1, 2) (8, 4, 4) (32, 16, 8) H HH HH  HH HH (1, 0, ∞) (4,1, 4) (16, 5, 8) H HH HH H H HH HH H HH(8, 1, 8) HH(32, 6, 16) 0, ∞) H(2, H H HH HH H H HH HH(4, 0, ∞) H (16, 1, 16) HH H j HH H HH HH (8, 0, ∞) HH H(32, 1, 32) HH H H HH HH(16, 0, ∞) H j H HH HH(32, 0, ∞) H HH Hj H r = m − 2, d = 4; ext. Hamming codes k = n/2; self-dual codes r = 1, d = n/2; biorthogonal codes r = 0, d = n; repetition codes r = −1, d = ∞; trivial codes Figure 2. Tableau of Reed-Muller codes. In this tableau each RM code lies halfway between the two codes of half the length that are used to construct it in the |u|u + v| construction, from which we can immediately deduce its dimension k. Exercise 3. Compute the parameters (k, d) of the RM codes of lengths n = 64 and 128. There is a known closed-form formula for the number Nd of codewords of minimum weight d = 2m−r in RM(r, m): � 2m−i − 1 . (6.5) Nd = 2r 2m−r−i − 1 0≤i≤m−r−1 Example 4. The number of weight-8 words in the (32, 16, 8) code RM(2, 5) is 31 · 15 · 7 = 620. 7·3·1 The nominal coding gain of RM(2, 5) is γc (C) = 4 (6.02 dB); however, since Kb = N8 /k = 38.75, the effective coding gain by our rule of thumb is only about γeff (C) ≈ 5.0 dB. N8 = 4 The codes with r = m − 1 are single-parity-check (SPC) codes with d = 2. These codes have nominal coding gain 2(k/n), which goes to 2 (3.01 dB) as n → ∞; however, since Nd = 2m (2m − 1)/2, we have Kb = 2m−1 → ∞, which ultimately limits the effective coding gain. The codes with r = m − 2 are extended Hamming (EH) codes with d = 4. These codes have nominal coding gain 4(k/n), which goes to 4 (6.02 dB) as n → ∞; however, since Nd = 2m (2m − 1)(2m − 2)/24, we again have Kb → ∞. Exercise 4 (optimizing SPC and EH codes). Using the rule of thumb that a factor of two increase in Kb costs 0.2 dB in effective coding gain, find the value of n for which an (n, n − 1, 2) SPC code has maximum effective coding gain, and compute this maximum in dB. Similarly, find m such that a (2m , 2m − m − 1, 4) extended Hamming code has maximum effective coding gain, using Nd = 2m (2m − 1)(2m − 2)/24, and compute this maximum in dB. The codes with r = 1 (first-order Reed-Muller codes) are interesting, because as shown in Exercise 5 they generate biorthogonal signal sets of dimension n = 2m and size 2m+1 , with nominal coding gain (m + 1)/2 → ∞. It is known that as n → ∞ this sequence of codes can achieve arbitrarily small Pr(E) for any Eb /N0 greater than the ultimate Shannon limit, namely Eb /N0 > ln 2 (-1.59 dB). Exercise 5 (biorthogonal codes). We have shown that the first-order Reed-Muller codes RM(1, m) have parameters (2m , m + 1, 2m−1 ), and that the (2m , 1, 2m ) repetition code RM(0, m) is a subcode. (a) Show that RM(1, m) has one word of weight 0, one word of weight 2m , and 2m+1 − 2 words of weight 2m−1 . [Hint: first show that the RM(1, m) code consists of 2m complementary codeword pairs {x, x + 1}.] (b) Show that the Euclidean image of an RM(1, m) code is an M = 2m+1 biorthogonal signal set. [Hint: compute all inner products between code vectors.] (c) Show that the code C
consisting of all words in RM(1, m) with a 0 in any given coordinate position is a (2m , m, 2m−1 ) binary linear code, and that its Euclidean image is an M = 2m orthogonal signal set. [Same hint as in part (a).] (d) Show that the code C

consisting of the code words of C
with the given coordinate deleted (“punctured”) is a binary linear (2m − 1, m, 2m−1 ) code, and that its Euclidean image is an M = 2m simplex signal set. [Hint: use Exercise 7 of Chapter 5.] In Exercise 2 of Chapter 1, it was shown how a 2m -orthogonal signal set A can be constructed as the image of a 2m × 2m binary Hadamard matrix. The corresponding 2m+1 -biorthogonal signal set ±A is identical to that constructed above from the (2m , m + 1, 2m−1 ) first-order RM code. The code dual to RM(r, m) is RM(m − r − 1, m); this can be shown by recursion from the facts that the (1, 1) and (1, 0) codes are duals and that by bilinearity (u, u + v), (u
, u
+ v
) = u, u
+ u + v, u
+ v
= u, v
+ v, u
+ v, v
, since u, u
+ u, u
= 0. In particular, this confirms that the repetition and SPC codes are duals, and shows that the biorthogonal and extended Hamming codes are duals. This also shows that RM codes with k/n = 1/2 are self-dual. The nominal coding gain of a rate-1/2 RM code of length 2m (m odd) is 2(m−1)/2 , which goes to infinity as m → ∞. It seems likely that as n → ∞ this sequence of codes can achieve arbitrarily small Pr(E) for any Eb /N0 greater than the Shannon limit for ρ = 1 b/2D, namely Eb /N0 > 1 (0 dB). Exercise 6 (generator matrices for RM codes). Let square 2m × 2m matrices Um , m ≥ 1, be specified recursively as follows. The matrix U1 is the 2 × 2 matrix � � 1 0 . U1 = 1 1 The matrix Um is the 2m × 2m matrix Um = � Um−1 Um−1 0 Um−1 � . (In other words, Um is the m-fold tensor product of U1 with itself.) (a) Show that RM(r, m) is generated by the rows of Um of Hamming weight 2m−r or greater. [Hint: observe that this holds for m = 1, and prove by recursion using the |u|u+ v| construction.] For example, give a generator matrix for the (8, 4, 4) RM code. � � �m� (b) Show that the number of rows of Um of weight 2m−r is m r . [Hint: use the fact that r is the coefficient of z m−r in the integer polynomial (1 + z)m .] � � � (c) Conclude that the dimension of RM(r, m) is k(r, m) = 0≤j≤r m j . 6.4.1 Effective coding gains of RM codes We provide below a table of the nominal spectral efficiency ρ, nominal coding gain γc , number of nearest neighbors Nd , error coefficient per bit Kb , and estimated effective coding gain γeff at Pb (E) ≈ 10−5 for various Reed-Muller codes, so that the student can consider these codes as components in system design exercises. In later lectures, we will consider trellis representations and trellis decoding of RM codes. We give here two complexity parameters of the minimal trellises for these codes: the state complexity s (the binary logarithm of the maximum number of states in a minimal trellis), and the branch complexity t (the binary logarithm of the maximum number of branches per section in a minimal trellis). The latter parameter gives a more accurate estimate of decoding complexity. code (8,7,2) (8,4,4) (16,15,2) (16,11,4) (16, 5,8) (32,31, 2) (32,26, 4) (32,16, 8) (32, 6,16) (64,63, 2) (64,57, 4) (64,42, 8) (64,22,16) (64, 7,32) ρ 1.75 1.00 1.88 1.38 0.63 1.94 1.63 1.00 0.37 1.97 1.78 1.31 0.69 0.22 γc 7/4 2 15/8 11/4 5/2 31/16 13/4 4 3 63/32 57/16 21/4 11/2 7/2 (dB) 2.43 3.01 2.73 4.39 3.98 2.87 5.12 6.02 4.77 2.94 5.52 7.20 7.40 5.44 Nd 28 14 120 140 30 496 1240 620 62 2016 10416 11160 2604 126 Kb 4 4 8 13 6 16 48 39 10 32 183 266 118 18 γeff (dB) 2.0 2.6 2.1 3.7 3.5 2.1 4.0 4.9 4.2 1.9 4.0 5.6 6.0 4.6 s 1 2 1 3 3 1 4 6 4 1 5 10 10 5 Table 1. Parameters of RM codes with lengths n ≤ 64. t 2 3 2 5 4 2 7 9 5 2 9 16 14 6 6.5 Decoding of binary block codes In this section we will first show that with binary codes MD decoding reduces to “maximumreliability decoding.” We will then discuss the penalty incurred by making hard decisions and then performing classical error-correction. We show how the penalty may be partially mitigated by using erasures, or rather completely by using generalized minimum distance (GMD) decoding. 6.5.1 Maximum-reliability decoding All of our performance estimates assume minimum-distance (MD) decoding. In other words, given a received sequence r ∈ Rn , the receiver must find the signal s(x) for x ∈ C such that the squared distance r − s(x) 2 is minimum. We will show that in the case of binary codes, MD decoding reduces to maximum-reliability (MR) decoding. Since s(x) 2 = nα2 is independent of x with binary constellations s(C), MD decoding is equivalent to maximum-inner-product decoding : find the signal s(x) for x ∈ C such that the inner product � r, s(x) = rk s(xk ) k is maximum. Since s(xk ) = (−1)xk α, the inner product may be expressed as � � |rk | sgn(rk )(−1)xk r, s(x) = α rk (−1)xk = α k k The sign sgn(rk ) ∈ {±1} is often regarded as a “hard decision” based on rk , indicating which of the two possible signals {±α} is more likely in that coordinate without taking into account the remaining coordinates. The magnitude |rk | may be viewed as the reliability of the hard decision. This rule may thus be expressed as: find the codeword x ∈ C that maximizes the reliability � r(x | r) = |rk |(−1)e(xk ,rk ) , k where the “error” e(xk , rk ) is 0 if the signs of s(xk ) and rk agree, or 1 if they disagree. We call this rule maximum-reliability decoding. Any of these optimum decision rules is easy to implement for small constellations s(C). However, without special tricks they require at least one computation for every codeword x ∈ C, and therefore become impractical when the number 2k of codewords becomes large. Finding simpler decoding algorithms that give a good tradeoff of performance vs. complexity, perhaps only for special classes of codes, has therefore been the major theme of practical coding research. For example, the Wagner decoding rule, the earliest “soft-decision” decoding algorithm (circa 1955), is an optimum decoding rule for the special class of (n, n − 1, 2) SPC codes that requires many fewer than 2n−1 computations. Exercise 7 (“Wagner decoding”). Let C be an (n, n − 1, 2) SPC code. The Wagner decoding rule is as follows. Make hard decisions on every symbol rk , and check whether the resulting binary word is in C. If so, accept it. If not, change the hard decision in the symbol rk for which the reliability metric |rk | is minimum. Show that the Wagner decoding rule is an optimum decoding rule for SPC codes. [Hint: show that the Wagner rule finds the codeword x ∈ C that maximizes r(x | r).] 6.5.2 Hard decisions and error-correction Early work on decoding of binary block codes assumed hard decisions on every symbol, yielding a hard-decision n-tuple y ∈ (F2 )n . The main decoding step is then to find the codeword x ∈ C that is closest to y in Hamming space. This is called error-correction. If C is a linear (n, k, d) code, then, since the Hamming metric is a true metric, no error can occur when a codeword x is sent unless the number of hard decision errors t = dH (x, y) is at least as great as half the minimum Hamming distance, t ≥ d/2. For many classes of binary block codes, efficient algebraic error-correction algorithms exist that are guaranteed to decode correctly provided that 2t < d. This is called bounded-distance error-correction. Example 5 (Hamming codes). The first binary error-correction codes were the Hamming codes (mentioned in Shannon’s original paper). A Hamming code C is a (2m − 1, 2m − m − 1, 3) code that may be found by puncturing a (2m , 2m − m − 1, 4) extended Hamming RM(m − 2, m) code in any coordinate. Its dual C ⊥ is a (2m − 1, m, 2m−1 ) code whose Euclidean image is a 2m -simplex constellation. For example, the simplest Hamming code is the (3, 1, 3) repetition code; its dual is the (3, 2, 2) SPC code, whose image is the 4-simplex constellation of Figure 1. The generator matrix of C ⊥ is an m × (2m − 1) matrix H whose 2m − 1 columns must run through the set of all nonzero binary m-tuples in some order (else C would not be guaranteed to correct any single error; see next paragraph). Since d = 3, a Hamming code should be able to correct any single error. A simple method for doing so is to compute the “syndrome” yH T = (x + e)H T = eH T , where e = x + y. If yH T = 0, then y ∈ C and y is assumed to be correct. If yH T = 0, then the syndrome yH T is equal to one of the rows in H T , and a single error is assumed to have occurred in the corresponding position. Thus it is always possible to change any y ∈ (F2 )n into a codeword by changing at most one bit. This implies that the 2n−m “Hamming spheres” of radius 1 and size 2m centered on the 2n−m codewords x, which consist of x and the n = 2m − 1 n-tuples y within Hamming distance 1 of x, form an exhaustive partition of the set of 2n n-tuples that comprise Hamming n-space (F2 )n . In summary, Hamming codes form a “perfect” Hamming sphere-packing of (F2 )n , and have a simple single-error-correction algorithm. We now show that even if an error-correcting decoder does optimal MD decoding in Hamming space, there is a loss in coding gain of the order of 3 dB relative to MD Euclidean-space decoding. Assume an (n, k, d) binary linear code C with d odd (the situation is worse when d is even). Let x be the transmitted codeword; then there is at least one codeword at Hamming distance d from x, and thus at least one real n-tuple in s(C) at Euclidean distance 4α2 d from s(x). For any ε > 0, a hard-decision decoding error will occur if the noise exceeds α + ε in any (d + 1)/2 of the places in which that word differs from x. Thus with hard decisions the minimum squared distance to the decision boundary in Euclidean space is α2 (d + 1)/2. (For d even, it is α2 d/2.) On the other hand, with “soft decisions” (reliability weights) and MD decoding, the minimum squared distance to any decision boundary in Euclidean space is α2 d. To the accuracy of √ the union bound estimate, the argument of the Q function thus decreases with hard-decision decoding by a factor of (d + 1)/2d, or approximately 1/2 (−3 dB) when d is large. (When d is even, this factor is exactly 1/2.) Example 6 (Hard and soft decoding of antipodal codes). Let C be the (2, 1, 2) binary code; then the two signal points in s(C) are antipodal, as shown in Figure 3(a) below. With hard decisions, real 2-space R2 is partitioned into four quadrants, which must then be assigned to one or the other of the two signal points. Of course, two of the quadrants are assigned to the signal points that they contain. However, no matter how the other two quadrants are assigned, there will be at least one decision boundary at squared distance α2 from a signal point, whereas with MD decoding the decision boundary is at distance 2α2 from both signal points. The loss in the error exponent of Pb (E) is therefore a factor of 2 (3 dB).     α R0 ? 6 α t R1 α t     R1 R0      R0 R0 R0    R0  R0 α ? 6 R1 R0  � � R1 R1 α √2α � ? t� - (a) α -  R1      (b) Figure 3. Decision regions in Rn with hard decisions. (a) (2, 1, 2) code; (b) (3, 1, 3) code. Similarly, if C is the (3, 1, 3) code, then R3 is partitioned by hard decisions into 8 octants, as shown in Figure 3(b). In this case (the simplest example of a Hamming code), it is clear how best to assign four octants to each signal point. The squared distance from each signal point to the nearest decision boundary is now 2α2 , compared to 3α2 with “soft decisions” and MD decoding in Euclidean space, for a loss of 2/3 (1.76 dB) in the error exponent. 6.5.3 Erasure-and-error-correction A decoding method halfway between hard-decision and “soft-decision” (reliability-based) techniques involves the use of “erasures.” With this method, the first step of the receiver is to map each received signal rk into one of three values, say {0, 1, ?}, where for some threshold T , rk → 0 rk → 1 rk → ? if rk > T ; if rk < −T ; if −T ≤ rk ≤ T. The decoder subsequently tries to map the ternary-valued n-tuple into the closest codeword x ∈ C in Hamming space, where the erased positions are ignored in measuring Hamming distance. If there are s erased positions, then the minimum distance between codewords is at least d − s in the unerased positions, so correct decoding is guaranteed if the number t of errors in the unerased positions satisfies t < (d−s)/2, or equivalently if 2t+ s < d. For many classes of binary block codes, efficient algebraic erasure-and-error-correcting algorithms exist that are guaranteed to decode correctly if 2t + s < d. This is called bounded-distance erasure-and-error-correction. Erasure-and-error-correction may be viewed as a form of MR decoding in which all reliabilities |rk | are made equal in the unerased positions, and are set to 0 in the erased positions. The ternary-valued output allows a closer approximation to the optimum decision regions in Euclidean space than with hard decisions, and therefore reduces the loss. With an optimized threshold T , the loss is typically only about half as much (in dB). b  t � a b � � ? ? ? 6  � b a � t� - b ? Figure 4. Decision regions with hard decisions and erasures for the (2, 1, 2) code. Example 6 (cont.). Figure 4 shows the 9 decision regions for the (2, 1, 2) code that result from hard decisions and/or erasures on each symbol. Three of the resulting regions are ambiguous. The minimum squared distances to these regions are a2 = 2(α − T )2 b2 = (α + T )2 . To maximize the minimum of a2 and b2 , we make a2 = b2 by choosing T = √ √2−1 α, 2+1 which yields 8 α2 = 1.372α2 . a2 = b2 √ ( 2 + 1)2 This is about 1.38 dB better than the squared Euclidean distance α2 achieved with hard decisions only, but is still 1.63 dB worse than the 2α2 achieved with MD decoding. Exercise 8 (Optimum threshold T ). Let C be a binary code with minimum distance d, and let received symbols be mapped into hard decisions or erasures as above. Show that: (a) For any integers t and s such that 2t + s ≥ d and for any decoding rule, there exists some pattern of t errors and s erasures that will cause a decoding error; (b) The minimum squared distance from any signal point to its decoding decision boundary is equal to at least min2t+s≥d {s(α − T )2 + t(α + T )2 }; (c) The value of T that maximizes this minimum squared distance is T = case the minimum squared distance is equal to 1.63 dB relative to the squared distance α2 d √ 4 α2 d ( 2+1)2 = 0.686 α2 d. √ √2−1 α, 2+1 in which Again, this is a loss of that is achieved with MD decoding. 6.5.4 Generalized minimum distance decoding A further step in this direction that achieves almost the same performance as MD decoding, to the accuracy of the union bound estimate, yet still permits algebraic decoding algorithms, is generalized minimum distance (GMD) decoding. In GMD decoding, the decoder keeps both the hard decision sgn(rk ) and the reliability |rk | of each received symbol, and orders them in order of their reliability. The GMD decoder then performs a series of erasure-and-error decoding trials in which the s = d − 1, d − 3, . . . least reliable symbols are erased. (The intermediate trials are not necessary because if d − s is even and 2t < d − s, then also 2t < d − s − 1, so the trial with one additional erasure will find the same codeword.) The number of such trials is d/2 if d is even, or (d + 1)/2 if d is odd; i.e., the number of trials needed is d/2. Each trial may produce a candidate codeword. The set of d/2 trials may thus produce up to d/2 distinct candidate codewords. These words may finally be compared according to their reliability r(x | r) (or any equivalent optimum metric), and the best candidate chosen. Example 7. For an (n, n − 1, 2) SPC code, GMD decoding performs just one trial with the least reliable symbol erased; the resulting candidate codeword is the unique codeword that agrees with all unerased symbols. Therefore in this case the GMD decoding rule is equivalent to the Wagner decoding rule (Exercise 7), which implies that it is optimum. It can be shown that no error can occur with a GMD decoder provided that the squared norm ||n||2 of the noise vector is less than α2 d; i.e., the squared distance from any signal point to its decision boundary is α2 d, just as for MD decoding. Thus there is no loss in coding gain or error exponent compared to MD decoding. It has been shown that for the most important classes of algebraic block codes, GMD decoding can be performed with little more complexity than ordinary hard-decision or erasures-and-errors decoding. Furthermore, it has been shown that not only is the error exponent of GMD decoding equal to that of optimum MD decoding, but also the error coefficient and thus the union bound estimate are the same, provided that GMD decoding is augmented to include a d-erasurecorrection trial (a purely algebraic solution of the n − k linear parity-check equations for the d unknown erased symbols). However, GMD decoding is a bounded-distance decoding algorithm, so its decision regions are like spheres of squared radius α2 d that lie within the MD decision regions Rj . For this reason GMD decoding is inferior to MD decoding, typically improving over erasure-and-error-correction by 1 dB or less. GMD decoding has rarely been used in practice. 6.5.5 Summary In conclusion, hard decisions allow the use of efficient algebraic decoding algorithms, but incur a significant SNR penalty, of the order of 3 dB. By using erasures, about half of this penalty can be avoided. With GMD decoding, efficient algebraic decoding algorithms can in principle be used with no loss in performance, at least as estimated by the the union bound estimate.