8.2.1 NRZ Coded PCM

The designation NRZ denotes the binary format that characterizes a mark bit as being one amplitude level and space bit as another. When the space bit is represented by a zero level, the format is called unipolar NRZ. In contrast, when the level of the space bit is the negative of the mark bit level, the designation polar NRZ is used. The designation NRZ‐L indicates that the level of the binary format is changed whenever the level of the source data changes. These two PCM data formats are shown in Figure 8.2. The bipolar NRZ‐L format is a special tri‐level code for which a space source bit corresponds to a zero output level, while the level corresponding to the mark source data is bipolar, alternating between plus and minus levels.

The designation NRZ‐M (NRZ‐S) indicates that changes in the formatted data occur when the source data is a mark (space); otherwise, the coded level remains the same. The unipolar NRZ‐M and NRZ‐S coded waveforms are depicted in Figure 8.3. This baseband coding results in differentially encoded data and is discussed in more detail in Section 8.4.

The advantage of differentially encoded data is that correct bit detection is maintained in the demodulator with a 180° error in the carrier phase as might occur in the channel or the demodulator carrier tracking loops. The penalty for using differential data coding is a degradation of the bit‐error performance with a 2 : 1 increase in the bit errors at high signal‐to‐noise ratios. Because the source data is encoded in the transitions of the PCM coded data, the absolute level is not as important; however, polar NRZ data with binary phase shift keying (BPSK) modulation results in the optimum detection performance through an additive white Gaussian noise (AWGN) channel.

The PSD of the unipolar NRZ level, mark, space NRZ‐L,‐M,‐S formatted data is evaluated using (8.2) with the underlying spectrum characterized by the unit amplitude pulse rect(t/T_b − 1/2) with the square of the spectrum magnitude expressed as

(8.4)

The sampled spectrum expressed by (8.4) results in zero magnitude at for all n except n = 0, in which case, the magnitude is . With random source data, corresponding to p = 1/2, (8.2) becomes

(8.5)

The PSD for the polar NRZ coded waveform is evaluated in a similar way using (8.3) and (8.4) and, assuming random data with p = 1/2, the result is

(8.6)

Therefore, the polar NRZ coded waveform has 6 dB more energy in the underlying spectrum, and there is no zero‐frequency impulse.

The spectrum for the bipolar NRZ‐L,‐M,‐S is evaluated by Sunde [10] as

(8.7)

The PSD in (8.4) is based on the PCM coded data having a constant amplitude over the entire bit interval, that is, the there is no pulse shaping, and, assuming random source data with p = 1/2, upon substituting |H(f)|² using (8.4) into (8.7) yields the PSD for bipolar NRZ coded PCM expressed as

(8.8)

Equations (8.5), (8.6), and (8.8) are normalized by T_b and plotted in Figure 8.4 as the PSD for the NRZ coded PCM waveforms. The spectrum of the bipolar NRZ code does not have a direct current (DC) component so transmission over lines that are not DC coupled is possible as, for example, over long‐distance lines that use repeater amplifiers.

8.2.2 Return‐to‐Zero Coded PCM

Another form of baseband coding is return‐to‐zero (RZ) coding that is characterized by the NRZ‐L coding in Figure 8.2 with the exception that the bit interval is split, that is, the coded pulse level is nonzero over the first T_b/2 data interval and returns to zero over the remaining interval.³ The RZ coded PCM waveforms are depicted in Figure 8.5. In the unipolar case, the space bit is always zero and the mark bit is split. The polar case is similar; however, the space bit is split with the opposite polarity of the mark bit. The polar RZ code allows the bit timing to be established simply by full‐wave rectifying and narrowband filtering the received bit stream.

In the bipolar case, the mark bit is split with alternating polarities and the space bit is always zero. By alternating the polarity of the mark bits, the bipolar RZ code provides for one bit‐error detection [11]. The bipolar RZ coded PCM is used in the Bell Telephone T1‐carrier system [12].

The PSD of the unipolar and polar RZ coded PCM waveforms are evaluated using (8.2) and (8.3) in a manner similar to that used for the unipolar and polar NRZ code; however, in these cases, the mark bit is split and characterized by the pulse rect(2t/T_b − 1/2) with the underlying square of the spectrum magnitude given by

(8.9)

Substituting (8.9) into (8.2) and recognizing that the spectrum is zero for all n ≠ 0, the PSD of the unipolar RZ coded waveform with random data is evaluated as

(8.10)

In a similar manner, the polar RZ PSD is evaluated using (8.3) with the result

(8.11)

The PSD of the bipolar RZ coded PCM waveform is characterized by Sunde [10] as in (8.7), with given by (8.9) so that, with random data,

(8.12)

The PSD of the bipolar RZ coded PCM waveform is plotted in Figure 8.6.

8.2.3 Biphase (Biϕ) or Manchester Coded PCM

Biphase (Biϕ), or Manchester, coded PCM is a commonly used waveform because of the robust bit timing recovery even without random data. For example, in an idle mode that uses either mark or space hold data, the demodulator timing can be maintained. The biphase‐level, ‐mark, ‐space (Biϕ‐L,‐M,‐S) coded waveforms are depicted in Figure 8.7. For the Biϕ‐L code, the mark bit is split and the space bit is the inverse of the mark bit. With the Biφ‐M code, a transition occurs at the beginning of each source data bit and the mark bit is split; however there is no change in the code‐bit level when a space source bit occurs. The Biϕ‐S code is similar to the Biϕ‐M with the role of the mark and space bits reversed.

The PSD of the biphase coded PCM waveform, using random data with p = 1/2, is evaluated by Batson [13] as

(8.13)

Equation (8.13) is normalized by T_b and plotted in Figure 8.8.

8.2.4 Delay Modulation or Miller Coded PCM

Delay modulation (DM), or Miller code, is a form of PCM where, for DM‐M coding, the code bit corresponding to each mark source bit is split, that is, the level changes in middle of each mark bit. The level of the code bit corresponding to a space source bit is unchanged unless it is followed by another space source bit in which case it is changed at the beginning of the space source bit. The DM‐S coding reverses the roles of the mark and space source bits, that is, the code bit corresponding to each space source bit is split and the level of the code bit corresponding to a mark source bit is unchanged unless it is followed by another mark source bit in which case it is changed at the beginning of the mark source bit. DM‐M,‐S coding is shown in Figure 8.9 for the source data sequence (1,0,0,1,1,0,1). To establish the correct phase of the bit timing in the demodulator an alternating mark‐space preamble must be transmitted.

The PSD of the DM coded PCM waveform is evaluated for random data by Hecht and Guida [14] as

(8.14)

Equation (8.14) is normalized by T_b and plotted Figure 8.10.

8.2.5 Bit‐Error Performance of PCM

The bit‐error performance of phase modulated⁴ (PM), PCM, and (PCM/PM) coded waveforms [15] are expressed in terms of Q(x), the complement of the probability integral, where x is a function of the signal‐to‐noise ratio measured in the bandwidth corresponding to the information bit rate R_b. The approximate functional dependencies [16] of the indicated PCM/PM coded waveforms are expressed in (8.15) and are based on ideal demodulator bit timing. The approximations improve with increasing signal‐to‐noise ratio and the bit‐error results are shown in Figure 8.11.

(8.15)

The performance of frequency modulated (FM) PCM (PCM/FM) coded waveforms is dependent on the normalized frequency deviation Δf/R_b, pre‐detection filter bandwidth B_if /R_b, and post‐detection or video bandwidth B_v/R_b, where R_b is the information bit rate. Based these parameters and the pre‐detection signal‐to‐noise ratio γ_b and constants k and k₁, the approximate bit‐error probability is expressed [16] as

(8.16)

The parameters in (8.16) are dependent on the format of the PCM/FM modulation, for example, NRZ‐L,‐M and Biϕ‐L, as indicated in Table 8.1. The signal‐to‐noise ratio, , is measured in a bandwidth corresponding to the bit rate R_b.

The peak deviation, Δf, is the modulation frequency deviation from the carrier frequency f_c with +Δf usually assigned to binary 1 (Mark) data and −Δf assigned to binary 0 (Space) data; the peak‐to‐peak deviation is 2Δf. Using a five‐pole, phase‐equalized, Butterworth intermediate frequency (IF) pre‐detection filter, the optimum peak deviation [17] for NRZ PCM/FM is and for Biφ PCM/FM . The pre‐detection filter 3‐dB bandwidth [18, 19] is denoted as B_if with the condition B_if /R_b ≥ 1. The range of the normalized video bandwidth is 0.5 ≤ B_v/R_b ≤ 1; however, the recommended range is 0.7 ≤ B_v/R_b ≤ 1. The best values of these parameters are selected by examining the bit‐error performance of hardware tests or Monte Carlo computer simulations. Typical parameters sets are shown in Table 8.1 [20] for the indicated PCM/FM coded waveforms and the approximate bit‐error results are shown in Figure 8.12 [21, 22]. The bit‐error performance results apply to bit‐by‐bit detection corresponding to a filter matched to the bit duration. Performance improvements can be achieved using a maximum‐likelihood detector spanning multiple bits in the form of a decoding trellis [23, 24].

A supportive test, used to establish best parameter values, is the evaluation of the PSD of the modulated waveform. An analytical formulation of the PSD of the NRZ PCM/FM modulated waveform is expressed as [25]

(8.17)

The parameters in (8.17) are defined in Table 8.2 and the spectrums are plotted in Figure 8.13 for peak deviations Δf/R_b = 0.25, 0.35, and 0.45. This analytical expression does not include the influence of the pre‐detection filter. The radio frequency (RF) bandwidth is defined as the occupied bandwidth corresponding to 99% spectral containment and the objective is to select a set of parameters that minimize the bit‐error performance and provide an acceptably low occupied bandwidth [26–29]. Spectral masks are discussed in Section 4.4.1 and examples of spectral containment for various modulations are given in Section 4.4.3 and following. Section 5.6 discusses binary FSK (BFSK) modulation with an emphasis on the PSD using various modulation indices.

8.9.1 Block Interleavers

Block interleavers are described in terms of an (M,N) matrix of stored symbols where consecutive input symbols are written to the matrix column by column until the matrix is filled¹⁷ and then forming the interleaved data sequence by reading the contents of the matrix row by row. A block interleaver is shown in Figure 8.26 and the following examples are specialized for a (4 × 3) matrix. In these examples, the matrix elements are initialized to zero and the input symbols are represented by a sequence of decimal integers {1,2,3,…}. Upon interleaving a block of NM symbols, if the process is repeated, the last symbol of the previous block will be followed by the first symbol of the next block resulting in zero span between these two contiguous input symbols. This problem can be circumvented by randomly reordering the addressing of rows and columns from block‐to‐block. Using two data interleaver matrices in a ping‐pong fashion is often preferred to the complications associated with clocking the data in and out of the same memory area. The deinterleaving is performed in the reverse order; in that, the received symbols are written to the deinterleaver matrix row by row and read to the output column by column. With block interleavers, bursts of contiguous channel errors longer than N symbols will result in short data bursts in the deinterleaved sequence. For example, if the interleaved sequence contains a burst of errors of length JM bits, then the errors in the deinterleaved sequence can be grouped as N bursts of length ≤J bits. However, in this characterization, some of the N deinterleaved output bursts may be contiguous. In general, block interleavers do not result in a uniform distribution of deinterleaved symbol errors.

The following example characterizes the block interleaver for M = 4 and N = 3.

The block interleaver characteristics are summarized as follows:

(8.43)

(8.44)

(8.45)

The expression for the delay simplifies to delay ≥2[NM + 1] − (N + M). As mentioned previously, the span is defined as the minimum interleaved symbol interval between contiguous input symbols.

Block interleavers are conveniently applied to block codes of length n by choosing N = n and then selecting the number of interleaver rows M to correspond to the channel correlation time, that is, the channel burst‐error length, in view of the error correction capability of the FEC code. For example, consider a t‐error correcting M‐ary block code denoted as (n,k,t). In this case, choose the interleaver span as N = n with M ≥ 2 chosen to provide adequate decoder error correction in view of the burst‐error length of the channel errors. Large values of M, however, will result in long data throughput delays.

8.9.2 Convolutional Interleavers

The convolutional interleaver is a special case of four types of (N₁, N₂) interleavers discussed by Ramsey and denoted as types I, II, III, and IV. The major difference in the implementation between the different types is the assignment of the input and output taps and the direction of commutation of the input and output data taps. The utility of the Ramsey interleavers is that, with the proper selection of the parameters N₁ and N₂, the output error distribution resulting from a burst of input errors is nearly uniform. The convolutional interleaver is similar to the type II Ramsey interleaver that requires that N₁ + 1 and N₂ be relatively prime; however, the convolutional interleaver requires that N₂ = K (N₁ − 1) where K is a constant integer. An advantage of convolutional interleavers over Ramsey interleavers is that they are relatively easy to implement.

The characteristics of convolutional interleavers are similar to those of block interleavers; however, the amount of storage required at the modulator and demodulator is NK(N + 1)/2 or about one‐half of that required by a block interleaver with similar characteristics. The interleaver parameters N and K are defined in Figure 8.27. Also, the end‐to‐end delay, that is, the delay from the interleaver input to the deinterleaver out, is NK(N − 1). The operation of the convolutional interleaver is characterized by a commutator that switches the input bits through N positions with the first position passed to the output without delay. With the deinterleaver commutator properly synchronized the first interleaved symbol is switched into the (N − 1)K register, while the content of the last storage element is shifted to the deinterleaver output. The convolutional interleaver characteristics are summarized as follows:

(8.46)

(8.47)

(8.48)

Here, the span is defined as the interleaved symbol interval between corresponding contiguous input symbols.

An example of the convolutional interleaver operation is shown in the following data sequences. In this example, the interleaver and deinterleaver are initialized with all zeros and a sequence of symbols consisting of decimal integers {1,2,3,…}, is applied to the input. The resulting out sequences are tabulated below for the case N = 3, K = 1 and the case N = 3, K = 2.

N = 3, K = 1 Interleaver:

N = 3, K = 2 Interleaver:

An example of the burst‐error characteristics of the convolutional interleaver is shown in the following data sequences for the N = 3, K = 2 interleaver with a burst of ten (10) contiguous channel errors following the 30th source symbol. In this example, the error bits are denoted as an X and the data record begins at the 30th symbol.

N = 3, K = 2 interleaver with 10 bit‐error burst, denoted as X, beginning at bit 30:

Evaluations of the interleaver performance include the uniformity of deinterleaved error events for various channel burst‐error lengths and the probabilities associated with the span of the interleaved sequence relative to the contiguous source symbols. However, the ultimate evaluation of the interleaver performance is the bit‐error probability for a specified waveform modulation and FEC code under various channel fading conditions.

8.10.1 Wagner Code Performance Approximation

The character‐error performance of a Wagner coded block can be approximated by assuming that all single errors are corrected and that all other error conditions are uncorrected and result in a character error. In this case, the character‐error probability of the raw (N, N − 1) Wagner code is simply

(8.49)

where the probability of a correct character, under the assumption of independent error events with probability P_be, is given by

(8.50)

This result is based on the binomial distribution [53] and P_be is the bit‐error probability of the underlying waveform modulation.

For the Wagner coded 7‐bit ASCII character without differential coding, the probability of a correct character is given by

(8.51)

With differential coding, the 7‐bit ASCII character is correctly decoded if a single bit‐error occurs among the six information bits. An error in the parity bit results in an error in the following information bits so the ASCII character cannot be corrected. The resulting probability of a correct character is then

(8.52)

The approximate performance results for the raw (N, N − 1) Wagner code are shown in Figure 8.30 for antipodal waveform modulation with AWGN. Figure 8.31 shows the approximate performance when the Wagner coded is applied to the 7‐bit ASCII character as discussed before. The signal‐to‐noise ratio (γ_c) for the underlying antipodal signaling of the coded bits is expressed in term to the code‐bit bandwidth 1/T_c, where T_c is the duration of the coded bit. The performance, however, is plotted as a function of the signal‐to‐noise ratio (γ_b) measured in the information bit bandwidth 1/T_b and the relationship is given by

(8.53)

For the raw Wagner code, and for the Wagner coded 7‐bit ASCII character T_b/T_c = 7/5 (= 1.46 dB).

8.10.2 (N, N − 1) Wagner Code Performance

In this section, the relationship between the bit‐error probability at the input to the Wagner decoder and the resulting character‐error probability at the decoder output is established. The theoretical performance in the AWGN channel is examined and the results are compared to Monte Carlo simulation results. The theoretical results apply for antipodal signaling such as BPSK, QPSK, OQPSK, or minimum shift keying (MSK); however, the simulation results are based on MSK waveform modulation with ideal symbol timing and phase tracking in the demodulator.

The general expression for the probability of a correctly received Wagner coded block is given by

(8.54)

When the noise is independent and identically distributed (iid) from bit to bit, this result can be expressed as

(8.55)

In the remainder of this section, the probability of correctly locating a single‐error event is analyzed using the stored soft decisions out of the optimally sampled matched filter.

The location of a single‐error event in the j‐th bit is based upon the magnitude z_j of the j‐th decision variable v_j being less than the magnitudes z_i of all the other bit decision variables v_i, i = 1, …, N such that i ≠ j. Given the transmitted bit sequence {d_i} and the received sequence {}, the probability of correctly locating the error is given by the general expression

(8.56)

where f(−) is the conditional joint density function of the random variables . With independent source data, a memoryless channel, and ideal receiver timing, the AWGN channel decision variables, v_i, are iid with distribution N(d_i, σ_n) for which the earlier result specializes to

(8.57)

The two conditioned distributions are found from a form of Bayes rule given by

(8.58)

Conditioning on an error event, that is, , the following relationships apply

(8.59)

and

(8.60)

Upon combining these results with the normal distribution , the numerator in (8.58) becomes

(8.61)

Using this result to evaluate the denominator in (8.58) conditioned on an error, it is noted that the denominator is simply the probability of a bit error, that is,

(8.62)

Since these results apply for v_j > 0, upon substituting z_j for v_j in (8.61) the solution to (8.58) becomes

(8.63)

Evaluation of (8.58) conditioned on a correct decision, that is, , and proceeding in a similar manner leads to the conditional distribution

(8.64)

Using (8.64) to evaluate the second integral in (8.57) results in

(8.65)

where Q(x) = 1 − Φ(x) and Φ(x) is the probability integral. Substituting (8.65) and (8.63) into (8.57) and, in turn, substituting (8.57) into the expression (8.55) for P_cc gives

(8.66)

This expression is computed numerically and the result is used to compute the character‐error probability expressed as

(8.67)

The solid curves in Figures 8.32 and 8.33 show the performance as a function of E_b/N_o for the (6,5) and (13,12) Wagner codes, respectively. The numerical integration is based on a resolution of 20 samples for each standard deviation σ_n over a range of 10 standard deviations above the mean value at z_j = |d_j|. The discrete circled data points for the (6,5) Wagner code are based on Monte Carlo simulations using 500 Kbits at each signal‐to‐noise ratio. Upon comparing these results with the approximations in Figure 8.30, it is seen that the approximate results are optimistic by about 1.0 dB at P_ce = 10⁻⁵; owing to the fact that the bit‐error locations were assumed to be known.

The dotted curve in Figures 8.32 and 8.33 represent the character‐error performance if the information bits were not coded with the parity bit. These results are evaluated as

(8.68)

for N = 5 and 12, respectively, and they provide a reference for determining the coding gain of the Wagner coded characters which is about 2.0 dB at P_ce = 10⁻⁵. The dotted curve in these figures is simply the uncoded bit‐error performance of antipodal signaling and is used to compute uncoded (5,5) and (12,12) P_ce as a point of reference.

8.11.1 Binary Convolutional Coding and Trellis Decoding

The binary convolutional code is characterized by entering one source bit into the encoder memory array each code block. This corresponds to k = 1 in Figure 8.34 with the K encoder memory consisting of K bits. The widely used rate 1/2 convolutional code with constraint length K = 7 provides excellent coding gain with reasonable complexity; however, the following description of the rate 1/2, K = 3 binary convolutional encoder provides all of the essential encoding and decoding concepts necessary to implement the more involved coding structures.

The coding and decoding of the simple, and relatively easy to understand, rate 1/2, K = 3 encoder is shown in Figure 8.37. The structure follows directly for the general implementation shown in Figure 8.34 using k = 1, K = 3 and the two subgenerators g₁(x) and g₂(x).

The K = 3 encoder stores K − 1 previous bits in locations 2 and 3 and with current bit of the input source data in location 1. The K − 1 bits represent the state of the encoder so, for this binary convolution encoder, there are 2^K−1 = 4 states. The encoder memory is initialized to zero and the following example uses the input data sequence of 1011010010…. The first bit into the encoder is 1, the leftmost bit, and, in keeping the convolutional sum, the input data is time‐reversed yielding,²¹ …0100101101. Based on this description, the encoder output is developed as shown in Table 8.11. The code bits are then processed as shown in Figure 8.35 and the modulated symbols are transmitted through the channel to the receiver.

8.11.2 Trellis Decoding of Binary Convolutional Codes

The maximum‐likelihood decoding of convolutional codes was published by Viterbi [68] in 1967. This paved the way for further research in what has become known as the Viterbi algorithm [69]. Forney [70, 71], rigorously showed that the Viterbi algorithm results in maximum‐likelihood decoding, and Heller [72, 73] is credited with the discovery of efficient decoding techniques using the Viterbi algorithm.

In the following, description of the trellis decoding of convolutional codes is based on the relatively straightforward binary, rate 1/2, K = 3 code, recognizing that more powerful convolutional codes use exactly the same, albeit more involved, decoding algorithms. The decoding starts by identifying the four‐state trellis decoder and the corresponding binary representations of the four states as indicated in Figure 8.38. The parameters of the generalized k‐ary trellis decoder in Figure 8.34 are identified in Table 8.12 with the numerical values corresponding to the example decoder in Figure 8.38. In general, the trellis diagram of a rate k/n convolutional code has 2^k(K−1) states with 2^k transitions emanating from each source state and terminating on each termination state.

By way of explanation, the decoding states in Figure 8.38 are represented by the state vectors with elements α_i,j: j = 0, …, 3 denoted as the state metric corresponding to each of the trellis states. It will be seen that the state metrics α_i,j are updated with estimates of the received data at each state transition. The dark gray state transition lines are shown to indicate that these transitions are not required as the trellis is building up when starting at the known zero initial state of the encoder. For short messages or short decoding depths, the decoder E_b/N_o performance is improved somewhat by not including these transition; however, the decoder synchronization is more problematic, in that the first code‐bit word must be synchronized with the SOM preamble. On the other hand, for long messages, that can tolerate longer trellis depths, the inclusion of these transitions is not as important because, with a trellis depth in excess of four constraint lengths, the trellis processing essentially eliminates the incorrect paths through the maximum‐likelihood decisions at each state transition.²²

The self‐synchronizing characteristic of the trellis decoder allows for message decoding in random data without knowledge of the SOM. For example, after initializing the state metrics, α_0,j, to zero, if the decoding is not correctly synchronized with the received code‐bit word, the surviving metrics at each state, after about four constraint lengths, will appear as random variables. In this event, the state metric accumulators are re‐initialized, the code‐bit word timing is shifted, and the processing is repeated until a dominant metric is observed indicating code synchronization.

The dark gray state transition lines indicate the transitions that are not associated with the trellis flushing required to drive the trellis to the known all‐zero state of the encoder following the message bits. The two (in general kK) zero flushing bits are appended to the message bits as indicate in Figure 8.38.

The details of the trellis decoding are described by the transition processing shown in Figure 8.39. The state transition is depicted from the source state to the termination state denoted by the state vectors and . As a practical matter, only the two state vectors and , their respective elements α_s,j = α_i−1,j and α_t,j = α_i,j, and the detected data estimate are required for the entire trellis decoding. This simplicity results from the add–compare–select (ACS) function of the max(a,b) algorithm and, for a sufficiently long trellis depths, leads to maximum‐likelihood data decoding [68].

As indicated, the state transitions in Figure 8.39 are only shown for the source data estimate and the remaining processing for is implicit. The source states j = 0, …, 3 are represented by the binary equivalents j = (b₂,b₁)_b that are concatenated with the source data estimate denoted²³ as . The rightmost bits of the concatenation correspond, or point, to the termination state, and by convention the transitions corresponding to are denoted by the dashes state transition lines. When the source data estimate is included, two state transitions will emanate from each source state and terminate on the termination states as indicated in Table 8.12. As mentioned before, the two transitions that terminate on state j = 0 correspond to with the source states identified as (b₂,b₁) = (0,0) and (1,0) corresponding to j = 0 and 2. For each state transition, there is an associated source state metric α_s,j, metric update Δα_m, and termination state j′. Therefore, the termination state must select the maximum α_s,j + Δα_m of all source states terminating on j′. This is shown in Figure 8.39 as the ACS function corresponding to the termination states j′ = 0 and 2.

The parity bits (p₂,p₁) corresponding to each transition are determined from knowledge of the convolutional encoder and are determined in the same manner as in the encoder. Several important observations are that each state transition is characterized as having a Hamming distance²⁴ of two, the parity bits associated with transitions terminating on the same state are antipodal, and the metric updates Δα_m are associated with the parity bits with m = (p₂,p₁)_b = 0, …, 3. The parity bits form the link to the received data; in that, the received parity bits at the demodulator matched filter output are correlated with each set of transition parity bits (p₂,p₁) with the correlation equal to the state transition update Δα_m. The details in the computation of Δα_m are discussed in the following.

The link between the trellis decoder and the convolutional encoder is found in the received symbols that contain noise corrupted estimates of the modulated waveform symbols. For example, consider the BPSK modulated waveform with phase modulation , where ²⁵ represents the two unipolar consecutive code bits corresponding to a code‐bit word; these bits are referred to as the parity bits in the earlier description of the trellis decoding. The corresponding demodulator matched filter samples are denoted as {ĉ₂, ĉ₁}, where are the independent noisy estimates of . With ideal AGC and phase tracking, the receiver estimate, ĉ_ℓ, is expressed as

(8.75)

where E_s/N_o is the symbol energy‐to‐noise density ratio, held constant by the ideal gain control and n_ℓ is a zero‐mean, unit‐variance, independent Gaussian noise random variable.

The binary code bits corresponding to each state transition in Figure 8.38 are represented by their bipolar equivalents as shown in Table 8.13.

The correlation of the received code block estimates with the 2ⁿ|_n=2 = 4 possible code‐bit combinations of the trellis bipolar state code‐bits ; results in the correlations²⁶

(8.76)

As the processing continues through the trellis, the surviving metric, determined from the ACS decisions, will eventually integrate to a uniquely large metric providing reliable data decisions. The trellis integration length or depth (N_dep) of four to five constraint lengths is usually sufficient for a reliable data decision. Figure 8.40 summarizes the state transition processing described in Figures 8.38 and 8.39 and includes the storage of the data estimate that is concatenation with the data vector . After a trellis depth of N_dep transitions, the oldest data is removed from the data vector and output as the maximum‐likelihood decoded estimate of the corresponding source data.

As mentioned before, associated with each surviving state metric is a stored sequence of data estimates and, after N_dep received bits are process, the oldest bits in the stored sequence are output as the maximum‐likelihood estimate of the transmitted bits. This is referred to at the path history storage and Rader [74] discusses efficient memory management and trace‐back to the transmitted data estimate. Through the ACS decisions, made at each trellis state, all of the incorrect paths leading to the estimate of the transmitted data, N_dep‐bits earlier, tend to be eliminated so, with high probability, any of the stored data vectors associated with the surviving metrics can be used to recover the estimate of the transmitted data. However, for shorter trellis depths or short constraint lengths codes with lower throughput delays, the optimum transmitted data estimate must be taken from the stored data array associated with the maximum metric of the trellis states, that is, max(α_s,j) : j = 0, …, 3. Upon completion of transition processing, the termination metrics α_t,j are assigned to the source metrics α_s,j and the decoding continues with a minimum of trellis memory. To avoid metric accumulation overflow, the maximum metric must be examined periodically and each metric reduced by a constant value if overflow is imminent.

8.11.3 Selection of Good Convolutional Codes

In general, the code generators are selected to ensure that the codes result in the maximal free distance²⁷ and do not result in catastrophic error propagation [75] following an error event. Exhaustive computer search algorithms are run to determine the best code generator for specific code configurations [76, 77]. The search algorithms examine details of the encoding structure including those involving catastrophic error propagation and equivalent codes. Equivalent codes have properties involving the reciprocal, shifting, and ordering of subgenerators. For example, reversing the order of the subgenerators results in an equivalent code. The following convolutional codes, referred to as good codes, are based on the maximal free distance, d_free, criterion when used with Viterbi decoding of convolutional codes.

A useful characteristic of convolutional codes is the insensitivity to signal phase reversals when used with differential data coding. Convolutional codes exhibiting this feature are referred to as transparent convolutional codes in which complements of code words are also code words. A convolutional code is transparent if each subgenerator has an odd number of binary coefficients [78]. By examining the variations in the surviving metrics through the trellis decoder, an estimate of the channel quality and the received signal‐to‐noise ratio are established. These estimates take advantage of the surviving state metric that increases at a constant rate in proportion to the received signal‐to‐noise ratio through the trellis decoder [78].

Good nonsystematic rate 1/n binary convolutional code generators for use with the Viterbi decoding algorithm were investigated by Odenwalder [76], and the results for rate 1/2 convolutional codes with constraint lengths 3 through 9 are listed in Table 8.14.²⁸ Odenwalder’s results for rate 1/3 binary convolutional codes with constraint lengths 3 through 8 are listed in Table 8.15. Larsen [79] has extended Odenwalder’s results to include the respective constraint lengths 10 through 14 and 9 through 14, in these tables. The constraint length 9 codes listed in these tables are specified in the North American direct sequence CDMA (DS‐CDMA) Digital Cellular System Interim Standard (IS‐95) [80]. The rate 1/4 convolutional codes in Table 8.16 were found by Larson.²⁹ The bit‐error performance dependence on E_b/N_o for the rate 1/2 code is examined in Section 8.11.8 for constraint lengths K = 4 through 9. Duet, Modestino, and Wismer [81] have extended the binary rate 1/n convolutional codes with maximum free distances to include code generators for n = 5, 6, 7, and 8; their results are listed in Tables 8.17, 8.18, 8.19, and 8.20 for constraint lengths 3 through 8.

The code generators in Tables 8.14, 8.15, 8.16, 8.17, 8.18, 8.19, and 8.20 are based on the binary Hamming distance and, as such, represent good codes for binary signaling in which each of the coded bits is mapped into one symbol using, for example, BPSK or BFSK waveform modulation. Alternately, each pair of code bits generated by the rate 1/2 binary convolutional code can be mapped into a 4‐ary modulated symbol and consecutive groups of three code bits generated by a rate 1/3 binary convolutional code can be mapped to an 8‐ary modulated symbol. However, a nonbinary Hamming distance measure should be used when mapping the code bits to an M‐ary modulated symbol. In this regard, Trumpis [82] investigated good rate 1/2 and 1/3 binary convolutional codes based on nonbinary Hamming distances with corresponding 4‐ary and 8‐ary symbol mapping; the resulting code generators are listed in Tables 8.21 and 8.22.

The preceding codes are all binary rate 1/n convolutional codes, and Paaske [77] has evaluated nonbinary rate (n − 1)/n convolutional codes and the subgenerators are listed in Tables 8.23 and 8.24 for the codes rates 2/3 and 3/4. Paaske’s work is based on Forney’s formulation [83, 84] of high‐rate convolutional codes where the parameter ν is defined as the constraint length. The topology of the rate (n − 1)/n encoder is similar to the general encoder shown in Figure 8.34. For these convolutional codes, the number of source‐bits input to the encoder memory each code block is k = n − 1. The example code, used to clarify the following description, is shown in Figure 8.41 and corresponds to the rate 3/4, constraint length 6, convolutional encoder listed in Table 8.24.

In terms of the code‐block parity generator matrix G, Paaske defines as set of (n − 1 by n) generator matrices G_i: i = 0, …, K − 1 expressed as

(8.77)

where are n − 1‐dimensional column vectors with binary elements {1,0}. The subgenerators g_ℓ(x), defined by (8.73) and shown in Figure 8.34, are evaluated, in terms of the transpose of the k = n − 1 column vectors , as

(8.78)

In words, g_ℓ(x) is the sum of the transpose of the ℓ‐th column vector in G_i with the significance of the bits in descending order from right to left. For example, Paaske’s generator matrices for the rate 3/4, constraint length v = 6, convolutional code, shown in Figure 8.41, are listed in Table 8.25; the corresponding subgenerators g_ℓ(x) are listed in Table 8.26 using binary and octal notation.

G 0				G 1				G 2
1	0	0	1	1	0	0	1	0	1	0	1
0	1	0	1	1	0	0	1	1	0	1	0
0	0	1	1	1	1	1	0	0	1	1	0

Referring to the state transitions in the trellis diagram as emanating from a source state and converging on a termination state, the code bits associated with each of the transitions to a given termination state are important; in that, they influence the selection of the survivor at the termination states and ultimately the trellis decoding performance. For the rate 1/2, K = 3 binary trellis decoder, shown in Figure 8.38, there are only two transitions converging on each termination state and the corresponding Hamming distances between any two code words is: h_d = {0,1,2}. However, with the unipolar‐to‐bipolar mapping d_i = 1 − 2b_i, such that b_i = {0,1} and d_i = {1,−1}, the, noise‐free, correlation response between any two code words is, from (8.76), . The maximum cross‐correlation, , corresponds to the received code‐word matching the transition code word leading to a correct survivor decision in the noise‐free case. Therefore, the matched filter or correlation detector responses dissimilar to the receive code word are either orthogonal or antipodal.

For a trellis decoder with a large number of trellis states with multiple source states converging on each termination state, it is processing efficient to store pointers to each source state and the corresponding transition code words. Using the rate 3/4, constraint length 6, K = 3 convolutional code in Figure 8.41 as an example, the 2^k=3 = 8 source states (S_i), converging on the selected termination state (S_i+1), are depicted in Figure 8.42. The selected termination state identifies the binary source data in the k = 3‐bit encoder memory B_−1,n and B and the eight different source states is determined by indexing the 3‐bit encoder memory B_−2,m from 0 to 7. For each source state, the unique 4‐bit code word (CW_m) is determine by applying the subgenerators g_ℓ(x) as expressed in (8.73) and identified in Table 8.24.

It is relatively easy to write a computer program to evaluate the encoder binary memory that identifies the source states, the input source data B, and the corresponding transition code words given the termination state as described earlier. In this evaluation, it is useful to write a procedure to convert from binary to integer and vice versa using the convention that the LSB is on the right. Computer simulations indicate that, for all 2⁶ = 64 possible states, h_d = {0,1,4} and the noise‐free cross‐correlation response between the received and transition code‐words is . Using the binomial coefficient, the number of combinations of the eight code words taken two at a time is and of these 28 combinations, 4 have cross‐correlations of +4 and 24 have cross‐correlations of zero.

8.11.4 Dual‐k Nonbinary Convolutional Codes

The dual‐k code is a nonbinary class of convolutional codes that are designed to be used with M‐ary symbol modulation. The dual‐k encoder shifts k input bits through dual (two) k‐bit registers and outputs dual (two) k‐bit symbols. Proakis [85] expresses the subgenerators g_i(x) : i = 1, …, 2k for the dual‐k codes as follows:

(8.79)

(8.80)

Here, I_k is the k × k identity matrix. The dual‐3 code provides robust communications in a Rayleigh fading stressed environment using 8‐ary FSK symbol modulation and noncoherent detection [86, 87]. The dual‐3, ‐4, and ‐5 encoder subgenerators are tabulated in Table 8.27 and the dual‐3 encoder is shown in Figure 8.43.

8.11.5 Convolutional Code Transfer Function and Upper Bound on Performance

An important technique in the performance analysis of a convolutional code is the transfer function described by Odenwalder [76] and in a tutorial paper by Viterbi [88]. The convolutional code transfer function is derived from a state diagram [89] that highlights the Hamming distance properties of the code for various states through the trellis decoder. The transfer function properties are characterized as the ratio of the output to input states over a prescribed code sequence; however, since the convolution code is linear, the Hamming distance is independent of the selected output to input states so the all‐zero sequence is chosen because of its relative simplicity in interpreting the transfer function of the code.

The convolutional code transfer function is described using, as an example, the binary rate 1/2, constraint length K = 3 code shown in Figure 8.37 and the corresponding trellis diagram shown in Figure 8.38. The state diagram for this code is shown in Figure 8.44 and is based on an all‐zero data sequence with the data error branches converging on successive states and reemerging with the correct zero state at different points through the trellis. The distance between the correct code word 00 and the code word corresponding to the transition path is labeled D^d where d denotes the Hamming distance, so the distance from the state 00 to 01 labeled D². In a like manner, the number of bit errors and the path length corresponding to the transition path are labeled N and L, respectively. These labels are easily determined from the trellis diagram of the code, as shown for this example code in Figure 8.38 where, for the assumed zero source data, a single bit error is indicated by the solid transition lines. In the state diagram description, the path length L is included with each transition path; however, when expressed in terms of the code transfer function, L will take on an integer exponent indicating the path length for a divergent path reemerging with the all‐zero path.

The state diagram is used to compute the convolutional code transfer function by following the few simple rules shown in Figure 8.45.

Defining the transfer function as T(N,L,D) = y₀/x₀ and applying the appropriate rules in Figure 8.45 results in the expression

(8.81)

Referring to the last equality in (8.81), the exponents of the parameters N, L, and D indicate, respectively, the number of decoded bit errors that occurred before reemerging with the all‐zero path, the number of path lengths prior to reemerging with the all‐zero path, and the Hamming distance of the code words over the path before reemerging with the all‐zero path. Therefore, the minimum distance for this example convolutional code is d_min = 5 and occurred over one path of 3 trellis transitions resulting in one bit error. The next smallest Hamming distance of 6 and occurred over two path lengths of 4 and 5 resulting in two bit errors per path for a total 4 bit‐errors, and so on. The number of bit errors corresponding to each Hamming distance is determined by differentiating (8.81) with respect to N and then setting N and L equal to one; the result is expressed as

(8.82)

For ideal BPSK waveform modulation and the AWGN channel, the probability of error for each incorrect path prior to reemerging with the all zero path is given by

(8.83)

where r_c is the code rate, γ_b is the energy‐to‐noise‐density ratio measured in the data rate bandwidth, h_d and n_p are the Hamming distance and number of bit errors for all paths associated with the Hamming distance. The overall bit‐error probability can be upper bounded by applying the union bound and, for the binary, rate r_c = 1/2, K = 3 example code being considered, the bit‐error probability is upper bounded by

(8.84)

As stated previously, the decoding path length is important with short messages, and (8.84) and the last equality in (8.81) provide some insight on the impact of the trellis decoding length on the decoder performance. However, for long messages the trellis depth of four or five constraint lengths is not a performance limiting issue, aside from the message throughput delay.

Odenwalder [76] provides a convenient closed‐form solution for the upper bound on the bit‐error probability by using the inequality

(8.85)

Using this result, (8.84) is expressed as

(8.86)

The derivative of the convolutional code transfer functions for the binary rate 1/2 and 1/3 convolutional codes, listed in Tables 8.14 and 8.15, are shown in Tables 8.28 and 8.29 where

(8.87)

Constraint Length, K
3	D5 + 4D6 + 12D7 + 32D8 + 80D9 + 192D10 + 448D11 + 1024D12 + 2304D13 + 5120D14 + ⋯
4	2D6 + 7D7 + 18D8 + 49D9 + 130D10 + 333D11 + 836D12 + 2069D13 + 5060D14 + 12255D15 + ⋯
5	4D7 + 12D8 + 20D9 + 72D10 + 225D11 + 500D12 + 1324D13 + 3680D14 + 8967D15 + 22270D16 + ⋯
6	2D8 + 36D9 + 32D10 + 62D11 + 332D12 + 701D13 + 2342D14 + 5503D15 + 12506D16 + 36234D17 + ⋯
7	36D10 + 211D12 + 1404D14 + 11633D16 + 77433D18 + 502690D20+ ⋯

^aMichelson and Levesque [63]. Reproduced by permission of John Wiley & Sons.

Constraint Length, K
3	3D8 + 15D10 + 58D12 + 201D14 + 655D16 + 2052D18+ ⋯
4	6D10 + 6D12 + 58D14 + 118D16 + 507D18 + 1284D20 + 4323D22+ ⋯
5	12D12 + 12D14 + 56D16 + 320D18 + 693D20 + 2324D22 + 8380D24+ ⋯
6	D13 + 8D14 + 26D15 + 20D16 + 19D17 + 62D18 + 86D19 + 204D20 + 420D21 + 710D22 + 1345D23 + ⋯
7	7D15 + 8D16 + 22D17 + 44D18 + 22D19 + 94D20 + 219D21 + 282D22 + 531D23 + 1104D24 + 1939D25 + ⋯

^aMichelson and Levesque [63]. Reproduced by permission of John Wiley & Sons.

Similarly, the derivative of the convolutional code transfer functions for the rate 1/2 and 1/3 convolutional codes with 4‐ary and 8‐ary symbol modulations are listed in Tables 8.30 and 8.31. The subgenerators for these codes correspond to those listed in Tables 8.21 and 8.22 for 4‐ary and 8‐ary symbol modulations, respectively. The performance of these codes can be compared, without the need for detailed computer simulations, using (8.84), (8.85), and (8.87) with the appropriate polynomials in D given in the following tables.

Constraint Length, K
3	D3 + 4D4 + 12D5 + 32D6 + 80D7 + 192D8 + 448D9 + 1024D10 + 2304D11 + 5120D12 + ⋯
4	D4 + 14D5 + 21D6 + 94D7 + 261D8 + 818D9 + 2173D10 + 6335D11 + 17220D12 +47518D13 + ⋯
5	3D5 + 15D6 + 22D7 + 196D8 + 398D9 + 1737D10 + 4728D11 + 15832D12 + 47491D13 +144170D14 + ⋯
6	9D6 + 14D7 + 62D8 + 212D9 + 874D10 + 2612D11 + 9032D12 + 28234D13 + 93511D14 +288974D15 + ⋯
7	7D7 + 39D8 + 104D9 + 352D10 + 1348D11 + 4540D12 + 14862D13 + 48120D14 +156480D15 + 505016D16 + ⋯

^aMichelson and Levesque [63]. Reproduced by permission of John Wiley & Sons.

Constraint Length, K
3	D3 + 2D4 + 5D5 + 10D6 + 20D7 + 38D8 + 71D9 + 130D10 + 235D11 + 420D12 + ⋯
4	D4 + 2D5 + 7D6 + 16D7 + 41D8 + 94D9 + 219D10 + 492D11 + 1101D12 + 2426D13 + ⋯
5	D5 + 5D6 + 8D7 + 25D8 + 64D9 + 170D10 + 392D11 + 958D12 + 2270D13 + 5406D14 + ⋯
6	D6 + 5D7 + 7D8 + 34D9 + 76D10 + 200D11 + 557D12 + 1280D13 + 3399D14 + 8202D15 + ⋯
7	D7 + 4D8 + 8D9 + 49D10 + 92D11 + 186D12 + 764D13 + 1507D14 + 4198D15 + 10744D16 + ⋯

^aMichelson and Levesque [63]. Reproduced by permission of John Wiley & Sons.

8.11.6 The Dual‐k Convolutional Code Transfer Function

The transfer function of a rate r_c = 1/n dual‐k convolutional code, with ℓ transmissions of the code, is expressed as [64, 90],

(8.88)

Upon differentiating (8.88) with respect to N and evaluating the result for N, L = 1 results in the expression

(8.89)

Equation (8.89) is evaluated for n = 2, corresponding to the code rate r_c = 1/2, and the resulting polynomial expressions in terms of D are summarized in Table 8.32 for ℓ = 1 through 4 with

(8.90)

ℓ
1	D4F(D)
2	D8F(D2)
3	D12F(D3)
4	D16F(D4)

^aWith F(D) = C₀ + C₁D + C₂D² + ⋯, the notation F(D^m) = C₀ + C₁D^m + C₂D^2m + ⋯.

In this case, the exponent of D is the Hamming distance of the q‐ary symbol with q = 8 corresponding to the transmissions of two 8‐ary FSK symbols‐per‐code. The underlying code, corresponding to ℓ = 1, has a minimum free distance of d_free = 4.

8.11.7 Code Puncturing and Concatenation

Code puncturing is a technique that involves deleting specified parity bits from an underlying convolutional code, with rate r_c, to provide codes rates greater than r_c, with a commensurate decrease in the coding gain. The puncturing is accomplished by the rate and symbol mapping functions shown in Figure 8.35 and, if the puncturing is performed judiciously, the decoding can be accomplished with very little change in decoding complexity. Cain et al. [91] identify subgenerators for the best codes, derived by periodically puncturing an underlying rate 1/2 convolutional code, to obtain code rates 2/3 and 3/4 with constraint lengths³⁰ v = 2, …, 8. Yasuda et al. [67], identify subgenerators (see Appendix 8A) derived from the underlying rate 1/2 convolutional code, to obtain punctured codes rates (n − 1)/n for n = 3 through 14 with constraint length v = 2, …, 8. High‐rate codes that are generated in this manner and decoded using a trellis decoder are referred to as pragmatic trellis codes. Wolf and Zehavi [92] discuss punctured convolutional codes used to generate high‐rate codes in the generation of pragmatic punctured [93] (P²) trellis codes [94], for PSK and quadrature amplitude modulation (QAM) waveforms.

When the punctured codes are derived from an underlying lower rate code, the trellis decoding is essentially the same as that of the underlying code; however, there is an increase in complexity associated with synchronization and tracking of the puncturing location in the decoding trellis. The ability to select the code rate by simply selecting the puncturing configuration has many advantages. For example, by altering the puncturing configuration, a single convolutional decoding chip [95] can be configured to accommodate more efficient modulation waveforms or to adjust the code rate to maintain the message reliability under varying channel conditions.

Code concatenation is a technique in which two codes are operated in a serial configuration to increase the overall coding gain relative to that of a single code. This configuration consists of an outer and inner code that may be identical codes; however, a common configuration is to use an RS outer code with a convolutional inner code. Typically, the codes are separated by an interleaver to ensure that error bursts are randomly distributed between the codes. Forney [96] has proposed the concatenation of a 2^K‐ary RS outer code with a constraint length K convolutional inner code separated by an L‐by‐M row‐column block interleaver. The RS symbol contains K bits and the block interleaver is filled row by row with L RS symbols and emptied column by column with M = 2^K − 1 symbols. Odenwalder [97] examines the performance this concatenated code configuration. Proakis and Rahman [87] examine the performance of concatenated dual‐k codes.

Other applications of code concatenation involve the design of turbo and turbo‐like codes. These configurations may involve two or more convolutional codes with each code separated by block interleavers that are instrumental in the overall decoding performance. Concatenated convolutional coding is discussed in more detail in Section 8.12 with references to original research and additional reading.

8.11.8 Convolutional Code Performance Using the Viterbi Algorithm

The performance results using the Viterbi algorithm are shown in Figure 8.46 for rate 1/2 binary convolutional coding with constraint lengths of 4 through 9. The decoding trellis depth is four constraint lengths. The results are shown using hard limiting and virtually infinite quantization of the matched filtered symbol samples. The hard‐limiting performance is equivalent to 1‐bit quantization. For comparison, the ideal or theoretical performance of antipodal signaling with AWGN is shown as the dashed curve. The Monte Carlo simulation results are based on 5M bits for each signal‐to‐noise ratio less than 4 dB. To preserve the simulated performance measurement accuracies for larger signal‐to‐noise ratios, the number is increased 10 fold. Under these conditions, the 90% confidence limit for bit‐error probabilities on the order of 5 × 10⁻⁷ is ±1.6 × 10⁻⁷ or within ±32%. For the hard‐limited performance evaluation, the 4.5M bit Monte Carlo simulation is increased 10 fold for signal‐to‐noise ratios ≥6 dB.

An important consideration, regarding the demodulator processing, is the quantization of the matched filter output sample that directly impacts the performance of the convolutional decoder [72]. For example, with the received signal level held constant by the AGC, the two‐level hard‐limiting simulation performance in Figure 8.46, results in about 2.1 dB loss in E_b/N_o performance at P_be = 10⁻⁵ compared to the infinitely quantized performance. By contrast, the simulation performance results shown in Figure 8.47 indicates that the performance loss with 4‐ and 8‐level (2‐ and 3‐bit) quantization results in a, respective, performance loss of less than 0.2 and 0.1 dB compared to the performance with essentially infinite quantization.

The results indicate that the improvement in signal‐to‐noise ratio at P_be = 10⁻⁷, relative to the uncoded performance, is about 4.2 dB for K = 4 with 8‐level quantization and about 2.0 dB with hard limiting. By way of contrast, with P_be = 10⁻⁷ and K = 9, the performance with infinite quantization and hard limiting is 7.3 and 4.4 dB respectively. Furthermore, for large signal‐to‐noise ratios, there is about 0.5 dB of improvement in the signal‐to‐noise ratio with each unit increase in the constraint length.

Figure 8.48 shows the sensitivity of the performance to receiver AGC gain variations. The 3‐bit quantizer includes a sign bit and two magnitude bits with saturation occurring at 1.0 V so the magnitude bits are assigned as b₁2⁻¹ + b₀2⁻². It is important to note that under‐flow rounding is used in all of the simulation results. In the simulation program, the nominal baseband signal voltage at the quantizer input of is set to 0.707 V or 3 dB below the 1.0 V saturation level.

The results of the simulated performance show that the loss in E_b/N_o performance is within ±0.2 dB over a receiver gain variation of about ±12 dB. Furthermore, the results indicate that symmetrical performance with respect to the receiver gain variation is obtained by setting the nominal baseband signal to 0.707 V below the quantizer saturation; this is not a surprising result since the nominal receiver level was adjusted based on this analysis.

8.11.9 Performance of the Dual‐3 Convolutional Code Using 8‐ary FSK Modulation

The dual‐3 convolutional coded 8‐ary noncoherent FSK performance with AWGN is evaluated using the uncoded bit‐error probability expressed in (7.21) as

(8.91)

where . Equation (8.91) is labeled as the uncoded curve in Figure 8.49 and is used as the underlying bit‐error probability in the evaluation of the dual‐3 convolutional coded performance with AWGN. The signal‐to‐noise ratio γ is measured in the symbol rate bandwidth and is related to the bandwidth of the bit rate as γ = kγ_b. The performance of the dual‐3 coded noncoherent 8‐ary FSK waveform is evaluated using (8.89) with n = 2, corresponding to the code rate r_c = 1/2, and diversity values of ℓ = 1 through 4.³¹ In the evaluation of (8.89), the terms D^x are replaced by P_be(xγ) and the results are shown as the dashed curves in Figure 8.49 for the indicated diversities; these curves represent upper bounds on the performance as indicate by the first inequality in (8.86).

The dashed curves in Figure 8.50 show the performance of the dual‐3 coded noncoherent 8‐ary FSK in a Rayleigh fading channel for the indicated diversities; the solid curve represents the uncoded performance with Rayleigh fading. The theoretical expressions for these results are based on the work of Odenwalder [98]. In this case, the bit‐error probability is evaluated by summing the coefficients (C_i) of the polynomial

(8.92)

where n = 2 corresponds to the rate 1/2 dual‐3 encoder. The coefficients C_i are those of F(D) expressed in (8.90) and the bit‐error probability is expressed as

(8.93)

where the factor involving k = 3 is used to convert from symbol errors to bit errors. Typically, only a few coefficient terms are required to obtain a good bound on P_be and four are used to obtain the results in Figure 8.50. In (8.93), the probability P_i is the probability of an error in comparing two sequences that differ in i symbols and is evaluated as

(8.94)

where p is given by [99]

(8.95)

An easier evaluation of P_i, which applies for i ≥ 6, is [64, 90]

(8.96)

Equation (8.95) is plotted as the solid curve in Figure 8.50 and, using (8.94), (8.95), and (8.96), Equation (8.93) is plotted as the dashed curves. The notation <s> denotes the average value of s corresponding to the fading channel. The performance of the dual‐3 convolutional code in combating Raleigh fading is impressive and, referring to the performance with diversity applied to uncoded 8‐ary FSK in Section 20.9.5, the dual‐3 code without diversity, that is, with ℓ = 1, requires about 3 dB less E_b/N_o than the uncoded 8‐ary FSK modulation with ℓ = 4.

8.12.1 Interleavers

Interleavers play such a prominent role in the coding gain of turbo‐like codes that considerable attention has been focused on their design [107]. Typically, random block interleavers are employed and a number of algorithms have been examined for implementation. In addition to the interleavers impact of the coding gain, other key interleaver characteristics are delay, memory, spreading factor—a measure of the interleavers ability to spread, or distribute, channel burst errors to appear as independent errors over a specified interval at the deinterleaver output, and dispersion—a measure of the “randomness” of the interleaver. Interleavers are discussed in Section 8.12.1 and the selection of an appropriate turbo‐like code interleaver is based on the communication channel considerations and the trade‐off between interleaver coding gain and delay [108]. Unfortunately, high interleaver gains are associated with long interleavers resulting in long delays. The decoding memory for very long interleavers can be reduced by using overlapping sliding windows [109].

Several interleaver configurations that have been used with turbo‐like codes are described in the following sections. In the description of the interleavers and in the general description of the turbo‐like code processing to follow, the interleavers are denoted by the symbol π, and the following algorithms describe how the interleavers are filled and read. The turbo‐like code performance simulations, discussed in Section 8.12.7.1, use the Jet Propulsion Laboratory (JPL) spread interleaver with various interleaver lengths to demonstrate the dependence on the coding gain.

8.12.1.1 Turbo Interleaver

The turbo interleaver is used with the original description of the TC described by Berrou et al. [1]. It is characterized as a square L × L block interleaver and is filled, or written, row by row and emptied, or read, in a random manner described as follows. The respective row and column indices are i and j, indexed as 0, 1, …, L − 1. When the matrix is full, the data is interleaved by randomly reading from location (i_r, j_r) computed as permutations of the row–column indices i and j according to the following rules. The row index is computed as

(8.100)

where

(8.101)

and the column index computed as

(8.102)

where P(k), k = 0, 1, …, M − 1 is a set of prime numbers. The value of M is dependent on L; typically, M = 8 for L < = 256. The original set of prime numbers used by Berrou, Glavieux, and Thitimajshima are (7, 17, 11, 23, 29, 13, 21, 19); however, other sets have also been used, for example, (17, 37, 19, 29, 41, 23, 13, 7) [110].

The factor (L/2 + 1) in (8.100) ensures that two neighboring input bits written on two consecutive rows will not remain neighbors in the interleaved output. The factor (i + j) performs a diagonal reading that tends to eliminate regular input low‐weight patterns at the input from appearing in the interleaved output.

8.12.1.4 JPL Interleaver

The JPL interleaver [112] is a block interleaver characterized as having a low dispersion a = 0.0686 and spreading factors (3,1021), (6,39), (11,38), and (19,37). With M an even integer, the vector of eight prime numbers p = (31, 37, 43, 47, 53, 59, 61, 67) are used to fill the interleaver using the following algorithm. For each 0 ≤ i < L,

(8.103)

where the parameters m(i), r(i), and c(i) are computed as

(8.104)

(8.105)

and

(8.106)

The related parameters c_o, r_o, and ℓ are computed as

(8.107)

(8.108)

and

(8.109)

8.12.1.5 Welch–Costas Interleavers

The Welch–Costas interleaver [113] is a column vector interleaver characterized as having unit dispersion. The interleaver is filled using the following algorithm:

(8.110)

Here, L = p − 1, where p is a prime number and α is a primitive element [114] of the field .

8.12.2 Code Rate Matching

The rate matching of PCCCs is different from that described in Section 8.11 for the convolutional code, in that, the PCCC rate matching must ensure that the number of bits‐per‐block (N_o) after puncturing is commensurate with an integer number of transmitted symbols. This rate matching criteria is based on the number of information bits‐per‐block N, the desired modulation efficiency r_s with units of bits/second/Hz, and the modulation efficiency with units of bits‐per‐symbol. The parameter N is also equal to the interleaver length. To satisfy the requirement of an integer number of transmitted symbols‐per‐information block, the parameter N_o is evaluated as

(8.111)

The puncturing ratio is defined as

(8.112)

where L is the total number of parity bits prior to the rate matching. The puncturing ratio for the nonsystematic code uses all of the party bits; whereas, for the systematic code only the party‐check bits are used.

An example of the rate matching processing, involving the evaluation of (8.111) and (8.112), is considered using the following design parameters: code rate r_c = 1/2, constraint length K = 4, PCCC with interleaver length N = 2048, and 8PSK symbol modulation. The modulation efficiency is r_m = log₂(8) = 3 bits‐per‐symbol and the desired modulation or spectral efficiency is r_s = 2 bits/s/Hz. In this case, there are 2(K − 1) = 6 flush bits, so there are L = 2N + 2(K − 1) = 4102 total bits before the rate matching. Under these conditions, the total bits out of the rate matching is N_o = 3072 and using N and L the puncturing ratio for the systematic code is evaluated as p = 0.50146. Therefore, of the original L − N = 2054 parity‐check bits only N_o − N = 1024 remain after the puncturing and the number of 8PSK symbols required to transmit the punctured block of data is N_o/r_m = 1024 symbols.

The block interleaver columns and rows are (r_m, N_o/r_m) and the N_o bits are entered into the interleaver column by column with the highest priority systematic bits assigned to the leftmost columns. As the interleaver is filled, the punctured bits are identified as those bits for which (i − 1)p ≥ ⌊ip⌋ : i = 1, …, L − N with the surviving parity‐check bits entered into the rightmost columns of the interleaver.

The remaining functions, involving gray coding the interleaver rows and bit mapping of the interleaver row by row to the modulation symbols, are identical to those described in Section 8.11. As discussed in Section 8.12.3, rate matching is provided between each of the SCCC concatenated CCs.

8.12.3 PCCC and SCCC Configurations

As mentioned previously, convolutional code concatenation falls into two generic configurations [65]: turbo or turbo‐like codes. The HCCC and the SCC configurations are variants of the PCCC and SCCC configurations. These code configurations have been analyzed and the bit‐error performance dependence on E_b/N_o (dB) evaluated using computer simulations [103, 105]. This section focuses on the parallel [1, 100, 115–117] and serial [103, 115, 117, 118] configurations, implemented as shown in Figures 8.51 and 8.52, respectively. The codes are implemented as linear block codes composed of a block of input data bits plus tail‐bits that are used to ensure that the decoding trellis terminates on the all‐zero state at the end of each block. For nonrecursive convolutional encoders,³⁴ the tail‐bits are input as a series of zero bits; whereas, for recursive convolutional encoders, the tail‐bits are dependent on the encoder feedback taps.³⁵ The length of the data interleavers is equal to the number of input data bits and, based on coding theory, long random data sequences or interleaved data sequences are required to approach the channel capacity. Therefore, the interleavers provide the necessary random properties and the concatenated convolutional codes provide the coding structure necessary to approach Shannon’s theoretical performance limit. The interleavers are filled with the block of source code‐bits as described in Section 8.12.1. The code‐bits to symbol mapping is similar to that of the convolutional code shown in Figure 8.35. The PCCC encoder configuration is shown in Figure 8.51a for an arbitrary number (M) of code concatenations and, for simplicity, the PCCC decoder is shown in Figure 8.51b for M = 3; this configuration is referred to as a DPCCC decoder [105].

For an arbitrary number of code concatenations, the basic functions of the PCCC decoder involve the input‐adder, interleaver (π), SISO, and inverse interleaver (π⁻¹). The SISO newly formed extrinsic information outputs are fed forward through the interleavers and inverse interleavers with feedback connections forming the SISO input reliabilities. These functions are executed for each decoding iteration and repeated in the process of performing multiple iteration data decoding. Upon the last iteration through the decoder, the received data estimates are formed by summing the newly formed extrinsic information from each of the inverse interleavers. The received data block from the demodulator is interleaved data and is applied directly to SISO1 and to subsequent SISOs with the indicated block delays. The four port SISO is described in Section 8.12.4; however, the upper output, λ(c;O), is not used in the parallel configurations.

The generalized SCCC encoder is shown in Figure 8.52a for M concatenated convolutional encoders and M − 1 interleavers. The number of source data bits entered into the outer encoder for each sample is k and the number of code bits at the output of the inner encoder is n, so the overall code rate is r_c = k/n. The individual encoder rates are defined as³⁶ k/p₁, p₁/p₂, …, p_M−1/p_M, and p_M/n. Furthermore, requiring the interleaver length (L_i) to be integerly related to p_i, such that, k_i = L_i/p_i : k_i ∈ integer > 0, then, with equal values k_i = N: i = 1, …, M − 1, the input source‐bit block size is kN and the interleaver lengths are determined as

(8.113)

The n inner code code‐bits are mapped onto the modulation symbol using rate matching and interleaving to associate the MSB code‐bit mapping with the least vulnerable channel error condition. The SCCC decoder is depicted in Figure 8.52b for M = 3 corresponding to the DSCCC [105] configuration. Table 8.33 provides some CC generators used by Benedetto, Divsalar, Montorsi, and Pollara to evaluate rate 1/3, 1/4, and 1/6 SCCC implementations. Their theoretical analysis shows that the DPCCC performs somewhat better than the rate 1/4 SCCC implementation.

Code Rate	Code Type	Generator G(D)
1/2	Recursiveb
	Nonrecursive
2/3	Recursive
	Nonrecursive
3/4	Recursive
	Nonrecursive

^aBenedetto et al. [119]. Reproduced by permission of the IEEE.

^bNot in referenced table; included here for completeness.

8.12.4 SISO Module

The SISO module³⁷ decoding structures have been characterized in considerable detail by Benedetto et al. [115, 120]. These modules perform maximum a posteriori (MAP) detection processing using a finite‐state trellis decoder and are used in either configuration by appropriately connecting the input and output ports. Figure 8.53 shows an isolated SISO module as a four‐port device with two inputs and outputs denoted, respectively, as λ(c : I), λ(u : I) and λ(c : O), λ(u : O). In the following descriptions of the decoding, the number of iterations is established based on the diminishing improvement in the bit‐error or code block‐error performance and typically 8–20 iterations are used.

Depending upon the requirements of the channel coding, the processing complexity can be reduced if M = 2 constituent encoders and SISO decoding modules are used. These simplified implantations follow directly from the M = 2 PCCC and SCCC configurations that are shown in Figures 8.54 and 8.55, respectively. Similarly, the encoding with an arbitrary number (M) of CCs is shown in Figures 8.51 and 8.52, and the corresponding decoding configurations can be inferred from the M = 3 decoding implementations.

The TC configuration involves two constituent convolutional encoders and one interleaver and the decoder consists of two SISO modules and one interleaver and deinterleaver as shown in Figure 8.54. In this configuration, there is only one source of received code words available for use by the SISO external observations or inputs λ(c : I). These inputs are obtained directly from the demodulator matched filter; consequently, with PCCC decoding the decoded outputs λ(c : O) is not used. In this case, the SISO1 output λ(u : O) represents the newly formed extrinsic information that is interleaved to form the reliability input λ(u : I) to SISO2. With subsequent iterations, the deinterleaved output from SISO2 is used as the reliability input to SISO1 and the decoding proceeds as described before. Upon completion of the last iteration, the received data is output as shown in Figure 8.54.

The decoding of the SCCC is described in terms of Figure 8.55 using two serially concatenated encoders. In this case, the decoding involves two SISO modules with the input λ(c : I) to the inner SISO corresponding to the demodulator matched filter samples and represents the interleaved symbols received from the channel. The input λ(c : I) to the outer SISO corresponds to the deinterleaved output of the newly formed extrinsic information λ(u : O) from the inner SISO. The newly formed decoded output λ(c : O) of the outer SISO is then interleaved forming the new observations λ(u : I) to the inner SISO. In this case, there is no successive SISO from which to obtain extrinsic information, so the outer SISO input λ(u : I) is set to zero and is not used. At this point, the first iteration is completed and following the last iteration the received data corresponds to the extrinsic information λ(u : O) of outer SISO.

Although the configurations of the PCCC and SCCC implementations are quite different, the processing within the SISO module is very structured with many common algorithms for both codes. The internal processing is based on optimal decoding algorithms for concatenated convolutional codes using the trellis decoding structure. The processing is described in broad terms in the remainder of this section and in detail in Sections 8.12.5 and 8.12.6.

The Bahl–Cocke–Jelinek–Raviv (BCJR) algorithm [122] provides for the MAP decoding of binary convolutional codes using the trellis decoding structure and the SISO processing is a variant of the BCJR algorithm. The MAP algorithm makes symbol‐by‐symbol decisions and, with equal a priori source symbol probabilities, corresponds to the a posteriori probability (APP) algorithm. However, because the SISO module processes a block of information and parity symbols before outputting the symbol decisions, the SISO module uses an additive APP algorithm rather than the MAP algorithm. Divsalar [105] has developed step‐by‐step derivations of the generalized additive APP SISO algorithms for the decoding of turbo, serial, hybrid, and self‐concatenated codes. These derivations compare the multiplicative and additive APP processing within the SISO module for symbol and bit‐level processing. The multiplicative APP forms the product of APPs at each trellis transition and is more computationally complex than the additive APP algorithm, that is based the monotonic property of the logarithm and involves the natural logarithm of the summation of APPs.

The relative computational simplicity in forming the logarithm of the sum of the APPs, however, involves some degree of complexity. The issue is related to the ACS algorithm used to choose the surviving metric at each of the termination states when using the Viterbi algorithm. With the additive APP algorithm, the comparable processing is referred to as an ACS plus correction, or simply the max* (max‐star) operation, defined as

(8.114)

where a_ji : j = 1, 2 are the exponents of the APPs at state i, L is the number of trellis states, and δ(Δ_i) is the additive correction term that is stored in a lookup table. The last approximation simply chooses the maximum exponent and results in near‐optimum performance for medium‐to‐high signal‐to‐noise ratios; however, for very low signal‐to‐noise ratios an E_b/N_o performance loss [123] of 0.5–0.7 dB is encountered; this loss is not insignificant given the overall coding complexity required to approach the channel coding limit. The first approximation in (8.114) involves a table look, based on the additive term in the second equality, and results in nearly the optimum performance when only eight values are stored.

The demodulator matched filter samples (y_k,i) represent sufficient statistics that contain all the information required to optimally detect the received information. However, the SISO processing requires that the receiver AGC establish a constant signal level satisfying one of the two following conditions. If the AGC normalizes the signal‐to‐noise ratio so that the additive noise samples () represents a zero‐mean, unit‐variance random variables, the sufficient statistics is evaluated as

(8.115)

where with c_k,i = {0,1} and d_k,i = {−1,1}. The external observations from the channel are denoted as

(8.116)

On the other hand, if the AGC holds the signal level constant at A, such that the signal‐to‐noise ratio is , then the sufficient statistic is

(8.117)

where and the external observations from the channel are denoted as

(8.118)

These results apply for BPSK; however, QPSK modulation can be used by considering two independent channels of PSK, each with unit noise variance and this requires dividing (8.116) and (8.118) by two.

Sections 8.12.5 and 8.12.6 describe the iterative decoding details for the parallel and serially concatenated codes involving two SISO modules based on the work of Divsalar [105] and Benedetto and Divsalar [65].

8.12.5 Iterative Decoding of Parallel Concatenated Codes

The computational complexity of the additive APP algorithm is lower than that of the multiplicative APP algorithm; so, for this reason, the additive APP algorithm [117] is described in this section. The description of the PCCC processing is based on Figure 8.54 and the focus is on the bit‐level processing within the SISO module that is commensurate with BPSK and QPSK waveform modulations. To simplify the description of the SISO algorithms, the state metric computation examples are based on a rate 1/2, four‐state binary convolutional encoder; however, the decoding algorithms are expressed in general terms. For example, the code rate³⁸ is r_c = p/q where p is the number of information bits; q is the total number of coded bits, including the parity bits; and N is the number of trellis states. For clarity, these parameters are included in the following description. Two major assumptions are made regarding the SISO processing: the channel is memoryless and maps the encoded symbols c_k into the matched filter samples y_k according to the channel probability density function ; the encoder is time‐invariant and corresponds to a fixed block code of length K symbols. In this case, with k = 1, …, K, the trellis‐state decoding is completely characterized by each trellis section from state S_k−1(ℓ) to . Based on the encoder convention, the decoding starts at state S₀(0) and ends at state S₀(K) and includes the flush bits required to return the trellis to the known termination state.

The SISO processing is based on the forward and backward recursions through the trellis structure corresponding to the convolutional encoder implementation. The encoder can be implemented as a systematic or nonsystematic code and use recursive encoders, nonrecursive encoders, or both configurations. The recursions take place over the entire code block length of K‐symbols corresponding to the interleaver length;³⁹ however, as mentioned earlier, the SISO processing is based on each trellis section associated with the q‐bit received code symbol. The forward and backward recursions for a trellis section are shown in Figure 8.56. The trellis processing is described using the nomenclature of the referenced authors. The trellis segment for the k‐th input code bit is described in terms of the starting edge S^S(e), ending edge S^E(e), and the branch metric, , for edge “e.” These three terms correspond, respectively, to the: source metric, termination metric, and metric update used in Section 8.11.1. To begin the description of the block decoding, the trellis states are initialized as α₀(ℓ = 0), β₀(ℓ = 0) = 0 and α₀(ℓ ≠ 0), β₀(ℓ ≠ 0) = −∞ with and initialized to zero.

8.12.5.1 Forward and Backward Recursions

The forward recursion processing is very similar to that described in Section 8.11.2, with the inclusion of the reliability input λ(u : I). For example, the metric update Δα_m in (8.76) is expressed as

(8.119)

and, with the inclusion of the reliability input λ(u : I), the forward recursion branch metric for edge “e” is expressed as

(8.120)

For the forward recursion, the SISO processing computes α_k(s) from where S^S(e) points to the starting states that terminate on the ending state . In Figure 8.56a, for each ending state there are two starting states, for example, the ending state points to the starting states and . As in the Viterbi decoding algorithm, a selection algorithm, similar to the ACS algorithm, must be used to determine the surviving metric at each ending state. For the additive APP algorithm, the max^*(a_i) selection algorithm is used and the surviving metric is computed as

(8.121)

The backward recursion computes β_k(s) from where S^S(e) points to the starting states that terminate on the ending state . In Figure 8.56b for each ending state, there are two starting states, for example, the ending state points to the starting states and . In this case, the surviving metric is computed as

(8.122)

The demodulator matched filter observations λ(c, I) are given by (8.116) and the constants and are adjusted as required upon completion of each iteration to prevent accumulation overflow. Overflow in path metric computations using fixed‐point processing internal to the SISO must also be considered [124]. The PCCC performance evaluations in this chapter use 32‐bit floating point SISO processing and, to avoid computational overflow, the metric adjustments are made at the completion of each iteration.

For the PCCC implementation, the extrinsic bit information output λ(u : O) for U_k,j ; j = 1, …, p is computed as in (8.123) and the output λ(c : O) is not used.

(8.123)

The data storage requirements involve the forward and backward branch metrics α_k, β_k, the SISO input data, the interleaver and deinterleaver data, the transition code bits u_k,i, and matched filter code‐bit estimates c_k,i associated with each branch transition.

8.12.6 Iterative Decoding of Serially Concatenated Convolutional Codes

The serially concatenated code configuration is depicted in Figure 8.55 and the details of the SISO processing and iterative decoding between the two concatenated codes is the subject of this section [118]. Unlike the PCCC decoding algorithm, which only accepts the input bit reliabilities λ(c : I) from the demodulator matched filter, the SCCC decoding algorithm uses the matched filter samples on the first iteration; however, on subsequent iterations the input data reliabilities λ(c : I) are obtained from the deinterleaved extrinsic bit information λ(u : O) from the inner SISO. The outer SISO then computes the extrinsic bit information λ(c : O). In describing the decoding algorithms, the respective inner and outer code rates are p₁/q₁ and p₂/q₂, c_k(e) represents c_k,i(e): i = 1, 2, …, q_m for the inner code (m = 1), and u_k(e) represents u_k,i(e): i = 1, 2, …, p_m for the outer code (m = 2). Considering that the p and q input and output bits are binary, represented by {0,1}, the bit‐by‐bit decoding for the M = 2 SCCC code is described as follows.

The max* operation is identical to that defined by (8.114) and the intrinsic input λ_k(c_k,i; I) from the demodulator matched filter samples are identical those described by (8.116). The inner and outer trellises are initialized as described for the PCCC decoding, that is, with α₀(ℓ = 0), β₀(ℓ = 0) = 0 and α₀(ℓ ≠ 0), β₀(ℓ ≠ 0) = −∞ with the constants and initialized to zero. Under these conditions, the inner and outer trellis recursions are computed as follows:

8.12.6.1 Inner Code Forward and Backward Recursions

(8.124)

and

(8.125)

with the extrinsic bit information for U_k,j: j = 1, 2, … p₁ is computed as

(8.126)

8.12.6.2 Outer Code Forward and Backward Recursions

(8.127)

and

(8.128)

with the extrinsic bit information for C_k,j: j = 1, 2, … q₂ is computed as

(8.129)

where λ_k(C_k,j; O) is interleaved and provided to the inner SISO as the input reliabilities λ(c_k; I). Upon the final iteration, the output bit reliability U_k,j: j = 1, 2, …, p₂ is computed as

(8.130)

8.12.7 PCCC and SCCC Performance

In this section, the bit‐error performance of the PCCCs and SCCCs are examined and compared.⁴⁰ In the following performance evaluation, the rate 1/3 TC, included in the Consultative Committee for Space Data Systems (CCSDS) multi‐rate TC standard for space telemetry [125], is examined using Monte Carlo simulations. The bit‐error performance is evaluated for various interleaver lengths with four iterations and then with various iterations using an interleaver lengths of 1024 bits. The performance is also evaluated for short messages with interleaver lengths of 296 and 128 bits using 10 iterations. These results highlight the importance of the interleaver length as discussed in Section 8.12.1. In Section 8.12.7.2, the bit‐error performance comparisons between the PCCCs and SCCCs are based on the work of Benedetto, Divsalar, Montorsi, and Pollara. All of the following Monte Carlo performance evaluations correspond to an AWGN channel.

8.12.7.1 Rate 1/3 Turbo Code Performance

The CCSDS [126, 127], recommended TC has selectable code rates of 1/2, 1/3, 1/4, and 1/6 and uses two 16‐state convolutional encoders. The interleaver lengths are also selectable among the following options: 1,784, 3,568, 7,136, 8,920, and 16,384. The encoder including the full complement of code rates is shown in Figure 8.57. The source bits are randomly assigned to the interleaver according to the selected interleaver algorithm. This code is a systematic convolutional encoder with one information‐bit for each output symbol interval, so the delay registers D correspond to the bit interval T_b. The registers are initialized to zero and, following the last of L information bits, the code input switches are changed and four additional clock cycles are executed to terminate the trellis in the zero state. The four additional bits are transmitted and used in the decoder to terminate the decoding trellis in the zero state; consequently, (L + 4)/r_c code bits are transmitted to recover the L information bits.

The generator for the turbo code is G = (g₀, g_1, g₂, g₃)^T and subgenerators (g_i) are listed in Table 8.34 using octal and binary notations. The code consists of recursive generators. The rate 1/2 code is generated by alternately puncturing the connections indicated by the open circles, starting with the encoder b connection, that is, the output of generator g_1b is punctured first. The filled circles are fixed connections so there is no puncturing for the code rates 1/3, 1/4, and 1/6. The subgenerator g_2b (indicated by the x) is not used in encoder b. The bits in a code symbol are transmitted in the order of the connections (top to bottom) indicated by the circles in Figure 8.57. For example, the information bit is always transmitted first; so, for the rate 1/3 code, the bits associated with the generators (g_1a, g_1b) are transmitted following the information bit. For the punctured rate 1/2 code, the bit following the information bit in the first symbol is g_1a, and in the second symbol is g_1b with successive symbols alternating between g_1a and g_1b. The information and parity bits are sequentially applied to the BPSK waveform modulator and transmitted over the AWGN channel.

Subgenerators	Octala	Binary	Connection
g0	13	100110	Recursive
g1	33	110110	Nonrecursive
g2	52	101010	Nonrecursive
g3	73	111110	Nonrecursive

^aOctal notation with LSB on the left.

The Monte Carlo simulated performance shown in Figure 8.59 is based on the JPL spread interleaver; the length 2048 JPL spread interleaver data was provided by Divsalar⁴¹ as a reference to validate the simulations. The performance of the JPL spread interleaver was also compared to the turbo and random interleavers, discussed in Section 8.12.1, and found to result in slightly improved bit‐error performance. The Monte Carlo bit‐error performance evaluations of the PCCC require considerably longer simulation runs compared to the performance evaluations of convolutional codes using the Viterbi decoding algorithm; this is not surprising in view of the much lower input signal‐to‐noise ratios and the steepness of the bit‐error performance curve. For example, a change in the signal‐to‐noise ratio of one‐tenth of a decibel can result in several orders of magnitude change in the bit‐error performance. In this regard, the signal‐to‐noise ratio (γ_b) in the simulation is established using (8.115), such that, the peak signal level is

(8.131)

where γ_b is measure in the bandwidth equal to the bit rate. Using (8.131) results in a zero‐mean, unit‐variance additive noise random variable. As a rule of thumb, the number of frames (N_sim) in the Monte Carlo simulations is given by

(8.132)

where ρ is the error in P_fe; Equation (8.132) is plotted in Figure 8.58 as a function of P_fe for various values of ρ in percent. Based on this rule, a frame‐error probability of P_fe = 10⁻⁴ with an 80% accuracy requires a Monte Carlo simulation of 20K frames or code blocks. This rule of thumb is somewhat pessimistic; however, it is useful in establishing a minimum upper limit while monitoring the frame‐error performance to terminate the simulation when the performance improvement appears to saturate. Unless save guards are available to restart the code, it is time‐consuming to underestimate the simulation run times. The following simulations for the 4096‐bit interleaver used about 40M bits for each signal‐to‐noise ratio.

Figure 8.59a shows the performance using four iterations with interleaver lengths [128] ranging from 256 to 4096 bits. The performance gain, between P_be = 10⁻⁵ and 10⁻⁶, in doubling the interleaver length is about 0.1 dB. Figure 8.59b shows the performance for a fixed interleaver length of 1024 bits with iterations ranging from 1 to 10. The diminishing performance gain with additional iterations above 10 is evident in these plots. For example, at P_be = 10⁻⁶ the performance gain between 5 and 10 iteration is about 0.09 dB.

An application involving short‐message durations must use commensurately short interleavers, and Figure 8.60 shows the simulated performance using short‐message blocks of 296 and 128 bits. The message bits included a CRC code to reduce the false message acceptance probability. The error floor between P_be = 10⁻⁵ and 10⁻⁶ is evident in both codes and, although the 296‐bit interleaver results in a significant coding gain improvement of about 0.6 dB, the error floor is considerably higher than that of the 128‐bit code block. These results highlight the importance of selecting good interleavers that are sufficiently random to provide independent estimates of the a posteriori probabilities for an information symbol given the encoder constraint length and channel memory.

8.12.7.2 Comparison of PCCC and SCCC Performance

The PCCC bit‐error performance examined in this section is based on the work of Benedetto et al. [100], Benedetto and Montorsi [116], and Benedetto et al. [121]. The performance evaluation involves the rate 1/2, 1/3, 1/4, and 1/15 PCCC implementations corresponding to iterations of 18, 11, 13, and 12 and a common a data block length of 16K bits with 16‐state encoders. The 2/4 rate code is unique, in that it represents the CCs used in the generation of a trellis‐coded modulation (TCM) waveform. For a discussion of the design, implementation, and performance of TCM, refer to Sections 9.4 and 9.5. With TCM the parity‐check redundancy is achieved through additional modulation states so there is no bandwidth expansion. The generator polynomials for the rate 2/4 TCM CCs (denoted as Code A) are listed in Table 8.35.

Code	CC	h2	h1	h0	Comments
A	CC1	33	35	31	16‐state TCM encoders
	CC2	35	33	31

Referring to Section 9.4, the two input bits d₂ and d₁ of the rate 2/4 code are sequentially selected from the input source data block of N bits. These bits correspond to the systematic output bits and of the constituent code CC1. The two CCs are evaluated using

(8.133)

where are sequentially taken from the independently interleaved block of source data bits. The resulting rate 2/4 systematic encoder results in the four output bits that are mapped to the selected waveform symbol(s) resulting in the rate 1/2 encoder. The generators for the SCCCs denoted as B through E are listed in Table 8.36 using octal notations.

Code	Rate	Generatorsa
		CC1	CC2	CC3
B	1/2
C	1/3
D	1/4
Eb	1/15

^aOctal notation with the LSB on the left.

^bThese generators must be verified (an alternate CC3 parity generator polynomial to 72/13 is 12/13).

The SCCC implementations are based on the encoder and decoder configurations in Figure 8.61 with the CCs obtained from Table 8.33. The output connections of the inner SCCC CC in Figure 8.61b, indicated by the open circles, require puncturing in the order (a,b), starting with connection a and alternating between a and b at the coded symbol rate. The following comparison of the theory, implementation, and bit‐error performance of these codes⁴² is based on the work of Benedetto et al. [103, 119, 121, 127] and Dolinar et al. [129].

The performance of the PCCC implementations is shown in Figure 8.62. The performance comparison between the codes is based on comparable complexity in that the codes correspond to 16‐state trellis decoders and the interleaver lengths are identical. Under the indicated conditions, the selection of the code rate is a major decision in achieving a specified signal‐to‐noise condition. However, the performance with longer interleaver block lengths will also result in lower E_b/N_o operating conditions. These simulation results do not show any P_be flaring that is customarily associated with a reduction of the slope in the P_be vs. E_b/N_o curve. With 16‐state encoders, the flaring usually becomes evident for P_be below about 10⁻⁵ or 10⁻⁶ and results in P_be = 10⁻¹⁵ at E_b/N_o values of 6 or 7 dB. These determinations are made using theoretical performance bounds based on the number of error events and the weight information sequence [116, 130]. It is noteworthy that SCCCs are less prone to severe flaring. The performance of the rate 2/4 (or 1/2) TCM waveform is somewhat limited to that shown in Figure 8.62 since bandwidth expansion is not an option and the inclusion of additional redundant modulation states has a rapidly diminishing advantage.

The performance of the SCCC implementations is shown in Figure 8.63. The performance assessments are based on the identical complexity of the codes in that they each have four‐state trellis decoders with identical the interleaver lengths and iterations. An advantage of the SCCCs is that the SISO processing can run considerably faster than the PCCCs due to the 4 : 1 reduction in the number of states. The SCCC implementations do not show evidence of any P_be flaring, as seen with four‐state PCCC performance. In comparing the rate 1/4, four‐state PCCC with the rate 1/4, 16‐state PCCC in Figure 8.62, there is a significant advantage in the coding gain using the 16‐state encoder. Furthermore, even though there is no evidence of P_be flaring in the 16‐state encoder, it is predicted (see Reference 130, figure 15) that flaring is on the verge of occurring at a signal‐to‐noise ratios dB. In the performance critique of Figure 8.62, it was mentioned that the SCCCs are less prone to severe flaring; however, flaring occurs (see Reference 103, figure 5) with a rate 1/3, four‐state, and 2K interleaver SCCC for P_be below about 10⁻⁸ at dB and results in P_be = 10⁻¹⁵ at . For the PCCC and SCCC implementations the flaring conditions improve with increasing interleaver lengths.

8.14.1 Binary BCH Codes

This section briefly reviews binary BCH codes as an introduction to RS codes discussed in Section 8.14.2. To this end, the following introduces the GF(2) involving binary data d_i ∈ {0,1}. The set of elements α forms a field [157] with respect to addition and multiplication, if the set is closed with respect to addition and multiplication, the distributive law applies, and it contains a zero and unit element. The key to the generation of the field elements over GF(2) is that the generator, or primitive polynomial p(x), has binary coefficients⁴⁷ {0,1}. The field element for which p(α) = 0 is referred to as the primitive element. Furthermore, the primitive polynomials for which p(α) = 0 are irreducible polynomials, that is, p(x) of degree m are not divisible by any other polynomial of degree m′: 0 < m′ < m ; this ensures that the field is closed.

Construction of the elements over GF(2) is best described by the following example using m = 3 and the known primitive polynomial p(x) = x³ + x + 1. Using the primitive polynomial, all of the distinct 2³ symbols of the code are generated in terms of the primitive element α as shown in Table 8.39.