6.2.1 The Fundamentals of Binary Block Codes

The very simple code described in the introduction—in which “1” is transmitted as “111” and “0” as “000”—is called a block code. It is given this name because a block of data—in this case, one bit—is represented with another (longer) block of transmitted bits—in this case, three bits. The two valid 3-bit sequences—“000” and “111”—are called the codewords of this code, and its blocklength is n = 3. We refer to this as a rate-1/3 code because there is one data bit for every three encoded (or transmitted) bits.

Generalizing, an (n, k) binary block code is one in which k data bits are represented with an n-bit codeword; thus, there are 2^k different codewords, each n bits long, where n > k. The rate of the resulting code is R = k/n data bits per encoded bit.

As noted above, error control codes make it easier to differentiate between different “valid” transmitted signals. With regard to block codes, this property is captured (to first order) by the code's minimum distance, which is defined as the fewest number of coordinates in which two codewords differ. (So the trivial code in the introduction is a (3,1) code with a minimum distance of d_min = 3, because every pair of codewords—and there are only two codewords—differ in at least three coordinates.) The Hamming distance between any two n-tuples is defined as the number of coordinates in which they differ, and the Hamming weight of a particular vector is the number of its nonzero components.

As a slightly less simple example, consider the (n = 7, k = 4) Hamming code below.

Here, “0010 → 0010011” (for instance) means that the data 4-tuple “0010” is represented with the 7-bit codeword “0010011.” There are 2⁴ = 16 codewords, each of length n = 7, and the rate of this code is R = 4/7 data bits per encoded bit. Moreover, careful inspection reveals that every pair of codeword differs in at least d_min = 3 places, so this is a code with a minimum distance of three.

The significance of a block code's minimum distance is most clear if we think in terms of the decoder. Suppose that a codeword is transmitted and that each bit has independent probability p of being “flipped”—that is, of being sufficiently corrupted that a transmitted “1” is misinterpreted by the receiver as a “0” or vice versa. Then, assuming that p < 1/2, most bits should be received correctly, and so the most likely transmitted codeword is the one that disagrees with the received signal in the fewest coordinates—that is, the “closest” codeword in terms of Hamming distance. A decoder that estimates data based on this principle is called a minimum distance—or maximum-likelihood (ML)—decoder. ML decoding is optimal, assuming that the data are a sequence of independent, identically distributed bits, each equally likely to be a “1” or a “0.”

As an example, suppose that the codeword c = [1011010] is transmitted but y = [1010010] is received, with a single error in the fourth coordinate. If you compare y to every codeword, you find that the codeword closest to y is, in fact, c = [1011010]; thus, the ML decoder's estimate of the transmitted codeword (and the associated data) is, in fact, correct. In contrast, if c = [1011010] is transmitted but y′ = [1011001] is received—the last two bits are “flipped”—then the closest codeword to y′ is c′ = [1001001], which means that the ML decoder will assume that c′ was transmitted and will estimate the associated data to be (the incorrect) “1001” rather than (the correct) “1011”—that is, there will be a decoding error.

A t-error correcting binary block code is one for which minimum distance decoding will yield a correct estimate of the transmitted codeword provided no more than t errors have occurred; thus, a t-error correcting code must have the property that, if you “flip” any set of t or fewer bits in any codeword c, the resulting vector is still “closer” to c—that is, disagrees in fewer places—than to any other codeword. This leads to the relationship: A t-error correcting code must have a minimum distance d_min that satisfies

Equivalently, a code with minimum distance d_min can correct up to t = ⌊(d_min − 1)/2⌋ errors, where “⌊·⌋” indicates the floor function.

A close examination of the 16 codewords in the above (7,4) Hamming code reveals at least two more properties worth noting:

• If you add any two codewords together—here, “add” means component-wise XOR—then you get another codeword. In the language of mathematics, the code forms a linear vector space over the binary field {0,1}, and so we say this is a linear code. One consequence of linearity is that the code's minimum distance is equal to its minimum nonzero codeword weight.

• The first k = 4 bits of every codeword are identical to the associated k data bits. In the language of coding, the encoder is systematic on the first k positions.

Linear codes are useful because their algebraic structure enables simpler decoding and simpler analysis. Moreover, there are matrices associated with a linear block code that facilitate the encoding and decoding procedures. The generator matrix for an (n, k) binary block code is a k × n matrix G with binary entries such that its rows form a basis for the code—that is, the code is equal to the set of all sums (or “linear combinations”) of the rows of G. This is expressed mathematically as C = {c: c = xG for some x ∈ {0,1}^k}. A generator for the above (7,4) code is given by

Similarly, a parity check matrix for an (n,k) binary code is an (n – k) × n binary matrix whose rows form a basis for the null space of the code—that is, H is a parity check matrix for a code C if and only if C = {c: c ∈ {0,1}ⁿ, cH^T = 0}, where 0 is the (n – k)-tuple with all zero entries. The parity check matrix for the (7,4) code above is given by

Note that the rows of the parity check matrix describe the parity constraints that must be satisfied by every codeword. For example, the first row of H above indicates that the first, second, fourth, and fifth bits in every codeword must have even parity—that is, must contain an even number of 1’s; the other two rows of H indicate two other parity constraints that must be satisfied by every codeword. More generally, the (n – k) rows of a parity check matrix describe (n − k) parity constraints that characterize the code.

The generator and parity check matrices are used in the encoding and decoding operations, respectively. With regard to encoding, the data vector x ∈ {0,1}^k is mapped onto the associated codeword c = xG. With regard to decoding, let y ∈ {0,1}ⁿ denote a (possibly corrupted) received binary n-tuple—that is, assume that codeword c was transmitted but y = x + e was received, where e ∈ {0,1}ⁿ is the a noise vector. Then, a typical “first step” in the decoding process is to compute the syndrome s associated with the received vector:

The syndrome s is computed from the received vector y but depends only on the error e—not on the transmitted codeword. The syndrome for a binary code is a binary (n – k)-tuple—that is, s ∈ {0,1}^n−k—and in syndrome decoding the syndrome s is first computed, and from s an estimate of the error vector e is formed. (Of course, once the error vector is estimated it is trivial to estimate the transmitted codeword by subtracting the error estimate from the received vector.)

There is a one-to-one relationship between correctable error patterns and syndromes; for every syndrome s, there are many possible choices of e satisfying s = eH^T, but the decoder is capable of correcting exactly one of them. This observation—coupled with the observation that a t-error correcting code can correct (at least) every error pattern affecting t or fewer bits—leads to the following bound, called the Hamming bound:

Any binary (n,k) t-error correcting linear code must have parameters that satisfy the Hamming bound; codes that satisfy the Hamming bound with equality are called perfect codes. Similarly, the Singleton bound states that any (n,k) code with minimum distance d_min must have parameters that satisfy

Codes that satisfy the Singleton bound with equality are called maximum distance separable codes.

The advantage of syndrome decoding lies in how it reduces the dimensionality of the decoding problem. The job of the decoder is to find the codeword c that is closest to the received vector y; without using the code's structure, this could be done (in theory, if not in practice) with a table containing 2ⁿ entries: the received vector y is used as an index into the table, and the associated entry contains the codeword closest to y. However, if we first compute s = yH^T we can now use s as an index into a table containing the 2^n−k correctable error patterns. For a (63,57) Hamming code, this reduces the required table from one containing 2⁶³ = 9.22 × 10¹⁸ entries to one containing only 2⁶ = 64 entries. Of course, for many practical codes this reduction in dimensionality still leaves a formidable problem: A (1023,923) 10-error correcting code produces a 100-bit syndrome, still far too large for a brute-force approach.

The (7,4) code used throughout this section is a Hamming code—one of a class of codes presented by Richard Hamming in 1950. More generally, a Hamming code is an (n = 2^r − 1, k = 2^r − 1 − r) binary linear block code for any choice of r = 2,3,4, … . Hamming codes are single-error correcting codes with minimum distance d_min = 3. The Hamming code with blocklength n = 2^r − 1 is constructed using a parity check matrix with columns that are the 2^r − 1 distinct non-all-zero binary r-tuples.

It is possible to extend a Hamming code by adding one additional redundant bit to every codeword to guarantee that every codeword has even parity—that is, an even number of ones. This converts the (2^r − 1, 2^r − 1 − r) code into a (2^r, 2^r − 1 − r) extended code—for example, the (7,4) Hamming code becomes the (8,4) extended Hamming code. Extending the code in this way increases the minimum distance of the code from d_free = 3 to d_free = 4. This additional minimum distance can be exploited to add a new capability—to not only correct any single error but also simultaneously detect (without miscorrecting) any double error. More generally, a block code is capable of correcting t errors and simultaneously detecting e ≥ t errors provided its minimum distance satisfies d_min ≥ t + e + 1.

6.2.2 Reed–Solomon Codes

The single-error correcting Hamming codes used to illustrate coding basics in the last section were the first practical “error correcting codes.” The development of a general technique for constructing t-error correcting codes for t > 1 took another decade—until the unveiling of BCH codes [4,5] and Reed–Solomon codes [6] in 1959 and 1960. Reed–Solomon codes continue to be used today in a wide array of wireless (and other) applications, so we briefly describe their structure.

A Reed–Solomon code is a nonbinary code, meaning that each codeword from a Reed–Solomon code with blocklength n consists of n nonbinary symbols. An (n,k) Reed–Solomon code with minimum distance d_min protects k data symbols by adding n − k redundant symbols such that every pair of codewords differs in at least d_min symbols. Moreover, the symbols are drawn from a nonbinary field, briefly explained below.

A “field” is a set with two operations—addition and multiplication—that satisfy the “usual” commutative, associative, and distributive properties and also contain additive and multiplicative identities as well as additive inverses and (for nonzero elements) multiplicative inverses. (The set of real numbers form a field under the usual notions of addition and multiplication, as do the set of complex numbers; the set of all integers do not because there are no multiplicative inverses.) A finite field (or Galois field) is a field with a finite number of elements; for instance, the binary field—containing just the elements {0,1}, with addition and multiplication performed modulo two—is a finite field.

Let GF(q) denote a field with q elements; then it is possible to construct the field GF(p^m) for any prime number p and any positive integer m, and it is impossible to construct a field with q elements if q is not a power of a prime. To construct the field GF(p) for prime p, the field consists of the integers {0,1,2, …, p − 1} and both addition and multiplication are performed modulo p. To construct the field GF(p^m) for m > 1 requires more subtlety; the field elements of GF(p^m) are the polynomials of degree at most m − 1, with coefficients drawn from GF(p). There are p^m such polynomials, and if addition and multiplication are defined appropriately, then the resulting structure is a field. Here, “appropriately” means that addition is performed in the “usual” polynomial fashion, component-wise modulo p, while multiplication is performed in polynomial fashion, but the result is reduced modulo π(x), where π(x) is an irreducible polynomial with coefficients in GF(p) of degree exactly m. An irreducible polynomial is one that cannot be factored; it is analogous among polynomials to a prime number among integers.

For details on the construction of finite fields, the reader is referred to any textbook on error control coding or modern algebra. What is important to understand now is that each field element of GF(p^m) can be represented as a symbol made up of m digits drawn from {0,1,2,…, p − 1}—that is, the m coefficients of the field element polynomial.

In practice, Reed–Solomon codes are designed over GF(2^m), so each symbol in a Reed–Solomon codeword can take one of 2^m values and is represented as an m-bit symbol. Of particular interest are Reed–Solomon codes over GF(256), because 256 = 2⁸ and therefore each codeword from an (n,k) Reed–Solomon code over GF(256) is n bytes long—with k data bytes and n – k redundant bytes and each byte consisting of eight bits. Such a code has 256^k codewords, and the rate is R = k/n data bytes per encoded byte.

An (n,k) Reed–Solomon code over GF(q) has blocklength n = q − 1 and minimum distance d_min = n – k + 1. (So Reed–Solomon codes are maximum distance separable codes as defined in Section 6.3.) Such a code is specified by its parity check matrix:

Here, α is a primitive element of the field GF(q). That means that all of the nonzero elements of GF(q) can be written as powers of α—that is, GF(q) = {0, α⁰ = 1, α¹, α², α³, …, α^q−2}. As with binary linear codes, the parity check matrix for an (n,k) Reed–Solomon code is an (n – k) × n array, so in H above, we have r = n – k.

The integer j in the above description of H is often (but not always) set to j = 1. If we think of the components of a codeword c = [c₀, c₁, c₂, …, c_n−1] as representing the coefficients of a polynomial c(x) = c₀ + c₁x + c₂x² + … + c_n−1xⁿ⁻¹, then the relationship cH^T = 0 is equivalent to the relationship c(α^j) = c(α^j+1) = c(α^j+2) = … = c(α^j+r−1) = 0. This suggests an equivalent definition for Reed–Solomon codes: For a fixed integer j and a fixed redundancy r = n – k, an (n = q − 1, k = n – r) Reed–Solomon code over GF(q) consists of all polynomials over GF(q) of degree n − 1 or less that have r consecutive powers of a primitive element α as roots: α^j, α^j+1, α^j+2, …, α^j+r−1. Such a code has a minimum distance d_min = r + 1 and so is capable of correcting all error patterns affecting not more than ⌊ r/2⌋ symbols.

A few observations complete our discussion on Reed–Solomon codes:

• While, strictly speaking, a Reed–Solomon code over GF(q) has a blocklength n = q − 1, it is possible to shorten a Reed–Solomon code—or any other code, for that matter—by arbitrarily setting some (say s) of the k information symbols to zero and then simply not transmitting them; as a result, an (n,k) code with minimum distance d_min is transformed into an (n – s, k – s) code with minimum distance at most d_min. (For Reed–Solomon codes, the minimum distance of the shortened code is unchanged.) For example, the advanced television systems committee (ATSC) standard for terrestrial digital television broadcast employs a (207,187) shortened Reed–Solomon code over GF(256). It is obtained by shortening the (255,235) Reed–Solomon code; the resulting code adds r = 20 bytes of redundancy to k = 187 bytes of data in a way that guarantees the correction of up to t = 10 byte errors in any codeword.

• Because Reed–Solomon codes are organized on a symbol (rather than bit) basis, they are well suited to correcting bursty errors—that is, errors highly correlated in time. To illustrate: A burst of (say) 15 corrupted bits can affect no more than three 8-bit symbols and so can be corrected with a relatively modest 3-error correcting Reed–Solomon code over GF(256). This effectiveness with regard to bursty noise can be enhanced through the use of interleaving—that is, by interspersing the symbols from different codewords among each other, thereby spreading out the effect of the error burst over multiple codewords. (Example: If a code over GF(256) is interleaved to depth three, then that same 15-bit error burst would affect at most one symbol in each of three different codewords, and therefore it would be ameliorated by an even simpler 1-error correcting code.)

6.2.3 Coding Gain, Hard Decisions, and Soft Decisions

The benefits of channel coding are typically expressed in terms of a coding gain—an indication of how much the transmitted power can be reduced in a coded system without a loss in performance, relative to an uncoded system. Coding gain depends not only on the code that is used but also on whether hard-decision decoding or soft-decision decoding is employed.

In hard-decision decoding, the demodulator makes a “hard decision” about each transmitted bit; those decisions are then conveyed to the FEC decoder which corrects any errors made by the demodulator. In soft-decision decoding, the FEC decoder is provided not with hard decisions it must accept or correct, but rather with “soft” information that reflects the “confidence” with which the demodulator would make such a decision.

As an example, consider binary phase shift keying (BPSK) modulation in the presence of additive white Gaussian noise (AWGN). For each transmitted bit, the receiver observes a matched filter output Y of the form $Y=\pm \sqrt{E}+Z$, where the sign of $\sqrt{E}$ indicates whether the transmitted bit is a “0” or “1,” E is the energy of the transmitted pulse, and Z is a 0-mean Gaussian random variable with variance N₀/2. In a hard-decision system, the demodulator estimates the transmitted bit based on whether Y is positive or negative, and it then passes that estimate to the decoder. When soft-decision decoding is employed, the FEC decoder gets direct access to the “soft information” contained in the unquantized (or very finely quantized) Y. More generally, in soft-decision decoding, the channel decoder is given access to the demodulator's matched filter outputs—typically quantized to several bits of precision.

To compare coded and uncoded transmission, the signal-to-noise ratio is typically expressed as E_b/N₀, where E_b is the average energy per data bit. If the (average) energy of each transmitted pulse is E, and each pulse conveys (on average) R data bits, then E_b = E/R. Displaying performance as a function of E_b/N₀ facilitates a fair(er) comparison because it includes the energy penalty that FEC codes pay to transmit their redundancy. However, these comparisons are not wholly fair because they do not address the bandwidth penalty that FEC can incur for a fixed modulation scheme; for instance, in transmitting data over a BPSK-modulated channel, using a (7,4) Hamming code requires 75% more bandwidth than uncoded transmission, because the transmitted bits (including redundancy) must be sent 75% faster after encoding if the data are to be delivered just as fast as in the uncoded case. The question of how to design codes without bandwidth expansion is addressed in Section 6.6.

Figure 6.2 shows the performance of the simple (7,4) Hamming code assuming BPSK modulation and an AWGN channel. It includes the performance with both hard-decision and soft-decision decoding, and uncoded transmission is included for comparison. Observe that hard-decision decoding of the Hamming code provides approximately 0.45 dB of coding gain over uncoded transmission at a bit error rate of 10⁻⁵, while soft-decision decoding offers an additional 1.4 dB of gain. These coding gains mean that coded transmission requires only 90% (resp., 65%) of the transmitted power required for uncoded transmission to obtain a bit error rate (BER) of 10⁻⁵ when hard-decision (resp., soft-decision) decoding is used.

As a rule of thumb, at high signal-to-noise ratio (SNR), there is approximately a 2 dB gain associated with soft-decision decoding, compared to hard-decision decoding [7]. However, soft-decision decoding of algebraically constructed block codes is computationally complex; indeed, it was shown in Reference 8 that optimal (ML) soft-decision decoding of Reed–Solomon codes is NP-hard, although suboptimal algorithms that exploit soft information remain a subject of considerable research interest [9]. (ML soft-decision decoding selects as its estimate of the transmitted codeword the one that minimizes the Euclidean distance between the received signal and the modulated codeword.)

The formidable challenge of exploiting soft information in the decoding of block codes is one reason why other FEC techniques have evolved—techniques that are more accommodating to soft-decision decoding. One of the most fundamental of those other techniques is convolutional coding.

6.3.1 The Fundamentals of Convolutional Codes

While an (n,k) binary block code assigns a discrete n-bit codeword to every discrete k-bit data block, an (n,k) binary convolutional code is one in which a “sliding block encoder” is used to generate n encoded sequences based on k data sequences. As a simple, illustrative example, consider the convolutional encoder in Figure 6.3. Here, the binary data sequence {x₁, x₂, x₃, …} is used to generate the encoded sequences $\{y_1^{(0)},y_2^{(0)},y_3^{(0)},\dots \}$ and $\{y_1^{(1)},y_2^{(1)},y_3^{(1)}\text{,}\dots \}$ according to these rules:

(As before, “ + ” indicates the binary XOR operation.) Thus, this is a (2,1) convolutional encoder because it accepts k = 1 binary sequence as an input and produces n = 2 binary-encoded sequences. More generally, an (n,k) convolutional encoder is a k-input, n-output, time-invariant, linear, causal, finite-state binary sequential circuit.

Just as linear block codes have generator and parity check matrices, so do convolutional codes. These representations employ the D-transform of a binary sequence: The D-transform of the binary sequence {b₀, b₁, b₂, …} is given by B(D) = b₀ + b₁D + b₂D² + …. Then, a convolutional encoder takes k data sequences—represented by x = [x₁(D), x₂(D), …, x_k(D)], where x_i(D) is the D-transform of the ith data sequence—and produces n encoded sequences, represented by y = [y₁(D), y₂(D), …, y_n(D)]; the generator matrix G for such an encoder is a k × n matrix with entries that are rational functions in D such that y = xG. For example, the generator of the convolutional encoder shown in Figure 6.3 is given by G = [1 + D² 1 + D + D²].

Convolutional encoders are finite-state machines. At any point in time, a convolutional encoder is in a particular “state” determined by its memory values; the encoder then accepts k input bits (one from each of the k data sequences) and produces an n-bit output while transitioning to a new state. This behavior is captured by a state diagram; the state diagram associated with the encoder in Figure 6.3 is shown in Figure 6.4a. The state of this particular encoder is determined by the previous two input bits—that is, when the encoder accepts input bit x_i, it is in the state determined by x_i−1 and x_i−2, because there are ν = 2 memory elements in the encoder; thus, this is a 4-state encoder. In general, a convolutional encoder with ν bits of memory has 2^ν states, and ν is referred to as the code's constraint length, an indicator of the code's complexity. In Figure 6.4a, each of the four states is represented by a node in a directed graph; the branches between the nodes indicate the possible transitions, and the label “x/y⁽¹⁾ y⁽²⁾” denotes the input (x) that causes the transition along with the two-bit output (y⁽¹⁾ y⁽²⁾) that results.

An alternative representation of a convolutional encoder is the trellis diagram—a graph that includes the same state and transition information as the state diagram but also includes a time dimension. The trellis diagram for the (2,1) convolutional encoder under consideration is shown in Figure 6.4b; it shows, for instance, that when the encoder is in state 1 (corresponding to x_i−1 = 1, x_i−2 = 0) then an input of “0” (resp., “1”) will cause a transition to state 2 (resp., 3) and produce an output of “01” (resp., “10”).

The free distance of a convolutional code is the minimum Hamming distance between any two valid encoded sequences; like the minimum distance of a block code, the free distance of a convolutional code indicates how “far apart” two distinct encoded sequences are guaranteed to be. Moreover, because of the assumed linearity of convolutional codes, the free distance of a code is equal to the minimum Hamming weight of any sequence that diverges from the all-zero sequence and then remerges. This is seen in Figure 6.5, where it is shown that the convolutional code with generator G = [1 + D² 1 + D + D²] has a minimum distance of d_free = 5.

6.3.2 The Viterbi Algorithm

In 1967, Dr. Andrew Viterbi published a paper [11] in which he presented an “asymptotically optimum decoding algorithm” for convolutional codes—an algorithm that transformed how digital communication systems were designed.

The Viterbi algorithm as applied to the decoding of convolutional codes is best understood as finding the “best path” through the code trellis. Referring to Figures 6.4b and 6.5, every branch in the trellis corresponds to the encoding of k data bits and the transmission of n channel bits; thus, there are 2^kL paths of length L through the trellis—that is, 2^kL paths made up of L branches—that start in a particular state at a particular point in time. Finding the “best path” through a brute force approach would quickly become unwieldy for even moderate values of L, since it would require comparing an observed signal of length L with 2^kL candidate paths.

The key insight of the Viterbi algorithm is this: The relevant metrics—that is, the relevant measures of what constitutes the “best path”—are additive over the length of the received sequence, and so when two paths “merge” into the same state, only one path—the best one entering that state—can remain a candidate for the title of “best path.” So, instead of keeping track of 2^kL candidate paths of length L, we need to retain only 2^ν—one for each of the 2^ν states, because only the best path entering each state is a “survivor.”

The ML metric is the log-likelihood function; if x is transmitted and y is received, then log[p(y|x)] reflects how likely y is to have been produced by x. Note that if the channel is “memoryless”—that is, each successive transmission is affected independently by the channel noise—then p(y|x) = Π p(y_i|x_i) and the metric log[p(y|x)] = Σ log[p(y_i|x_i)] is indeed additive. For additive Gaussian noise, maximizing this metric is equivalent to minimizing the cumulative squared Euclidean distance between x and y.

6.6.1 Trellis-Coded Modulation

TCM is best explained via a (now classic) example. Suppose one wishes to convey two information bits per transmitted symbol—a goal that is realizable with uncoded transmission using QPSK modulation. TCM teaches that, to apply coding to such a system, one doubles the constellation size—to 8-PSK—and then uses the structure of a convolutional encoder to ensure that only certain sequences are valid and can thus be transmitted.

This approach is illustrated in Figure 6.15. Two information bits are passed through a rate-2/3 convolutional encoder to produce the three bits [y₂y₁y₀]. This convolutional encoder is not “good” in the sense that it has a large free distance; indeed, its free distance is trivially one. Rather, the output of the encoder is interpreted as the label of the transmitted symbol, and the combination of the encoder with the “natural” (rather than Gray) mapping produces an encoder-plus-modulator with better Euclidean distance properties than uncoded QPSK. Specifically, this scheme provides an asymptotic (high-SNR) coding gain of approximately 3 dB in AWGN compared to uncoded QPSK, meaning that the coded system need transmit only half as much power as the uncoded system and still have the same performance.

To understand the TCM encoder in Figure 6.15, it is informative to look at the state transition diagram. Because the encoder has ν = 2 memory elements, this is a four-state encoder. Moreover, because only one of the two input bits is passed through the encoder—the other is uncoded—there are parallel transitions between states. For example, if the encoder is in state “00” then an input of either “01” or “11” will cause a transition to state “10”; because the first bit is uncoded, it has no effect on the state transition. Finally, observe that the two transmitted symbols corresponding to these two parallel transitions—symbols S₂ and S₆—are maximally far apart.

These observations lead to an illuminating interpretation of the encoder in Figure 6.15: The encoded bits [y₁y₀] select a sequence of subsets of the symbol constellation—in this example, there are four such subsets: {s₀,s₄}, {s₁,s₅}, {s₂,s₆}, and {s₃,s₇}—and then the uncoded bit is used to select one of the symbols from the subset. Thereby, the sequence of two-bit inputs selects a sequence of 8-PSK symbols that are transmitted.

*In Gray mapping, labels are assigned to two-dimensional symbols so that adjacent symbols have labels that differ in a single bit. In this way, the most common symbol detection errors result in a single bit error.

This approach is generalized in Figure 6.16 to describe a system in which k information bits are conveyed with every transmission of a symbol from a constellation with 2^k+1 elements—i.e., the constellation size is doubled over what is required for uncoded transmission. In this figure, k data bits enter the encoder during each symbol period; m of them are coded while k–m of them are uncoded. The m coded bits are passed through a rate-m/(m + 1) convolutional encoder to produce m + 1 bits that form part of the label of the transmitted codeword; the k–m uncoded bits form the rest of the k + 1-bit label. In this way, the output of the convolutional encoder selects a sequence of constellation subsets—there are 2^m+1 such subsets, and they each contain k–m symbols—while the uncoded bits select the transmitted symbol from each subset thus selected. (Applying this notation to the example in Figure 6.15, we have k = 2 and m = 1.)

The 2^m+1 subsets (each with 2^k–m symbols) should be designed to be as “sparse” as possible; the minimum Euclidean distance between symbols in each subset should be maximized. This is because two information sequences that differ in a single uncoded bit will be encoded to symbol sequences that are at least d_min,uncoded apart, where d_min,uncoded is the minimum Euclidean distance within a (sparse) subset. On the other hand, two information sequences that differ in coded bit(s) will benefit from the structure of the convolutional encoder; the convolutional encoder guarantees that the sequence of (partial) labels it produces will yield a sequence of subsets that are sufficiently different to guarantee a cumulative Euclidean distance of d_min,coded. Thus, the overall scheme produces a guaranteed minimum Euclidean difference of d_min = min{d_min,coded, d_min,uncoded} in the two sequences of transmitted symbols associated with two different information sequences.

TCM has been widely extended beyond the simple approach outlined here [15,16]. Examples of those extensions include:

• The design of multidimensional trellis codes, in which the symbol constellation is not two-dimensional but rather 2M-dimensional for some integer M > 1. The 2M-dimensional space is obtained by concatenating M successive two-dimensional spaces created by the in-phase/quadrature representation of M symbol intervals. The advantage of higher-dimensional codes comes from the fact that it is possible to more efficiently “pack” symbols in higher dimensions.

• The design of rotationally invariant trellis codes, which enable the receiver to recover the transmitted data even when the symbol constellation is rotated—a phenomenon that occurs when the receiver loses carrier synchronization and is unable to acquire an absolute phase reference.

6.6.2 Bit-Interleaved Coded Modulation

While TCM employs an integrated approach to coding and modulation, BICM takes a partitioned approach—but with the addition of a bit-interleaver between the encoder and the modulator.

In an early paper by Zehavi [22], BICM was motivated by the fading present in mobile communication channels. In the fully interleaved Rayleigh fading channel, it is assumed that each transmitted symbol is affected independently by Raleigh fading; this is quite different from the block Rayleigh fading channel in which the fading is assumed to be (approximately) constant over some specified blocklength, typically determined by vehicle speed and carrier frequency.^* The performance of a coded digital communication system over the fully interleaved Rayleigh fading channel is affected most strongly by its diversity order—that is, by the minimum number of distinct modulation symbols between two valid transmitted sequences; this is quite different from the cumulative squared Euclidean distance metric that determines performance over a nonfading AWGN channel—and which motivated TCM. Zehavi's approach, illustrated in Figure 6.17 with a rate-2/3 convolutional code, was to carry out “bit-interleaving” between the encoder and the decoder to “spread out” the bits so that every bit-difference in the convolutional encoder's output produced exactly one corresponding symbol-difference in the transmitted sequence; this leads to a diversity order equal to the minimum Hamming distance of the convolutional encoder—the optimal value.

Subsequent research on BICM [23] indicated that very little capacity is lost (for both fading and AWGN channels) by restricting the encoder to one of the type from [22]—that is, by using bit interleaving to create independent, binary-input equivalent channels and then applying capacity-approaching codes to those channels. This realization, coupled with the concurrent development of capacity-approaching binary codes such as LDPC and turbo codes, has led to the widespread adoption of the BICM architecture—a binary encoder followed by a bit interleaver followed by a dense Gray-mapped symbol constellation—for bandwidth-efficient communication.

*The fully interleaved Rayleigh fading channel can be realized by symbol-interleaving a block-wise (or correlated) fading channel to sufficient depth that the fades from one symbol to the next appear independent.