rs and cosets of 4Z. For example, the coset 4Z+ 1 corresponds to the bit label 10. Now, if we allow the output of a rate-1 convolutional code to index the labeling of the partition tree for each time instant, then a trellis code may be formed from Z/4Z by searching all rate-12 convolutional codes of a given Figure 3.4-9 Cross interleaver with four shift registers. The constraint length to find the convolutional code that memory sizes of the shift registers are 0, m, 2m, and 3m, maximizes the minimum Euclidean distance between respectively. At time unit i, a symbol is inserted into shift register i, codewords. Note that in the aforementioned, a finite which outputs its right-most symbol. Suppose that m = 1 and the subset of the lattice points must be used to form the input symbols are 0, 1, 2, 3, 4, 5, 6, 7, 8, After interleaving, the symbols are sent in the order 0, 4, 1, 8, 5 trellis code to ensure that there is no ambiguity in decoding a sequence of lattice points to a bit sequence. codewords before transmission. When a long burst error The performance of a TCM code is measured by the occurs, the erroneous symbols are distributed among signal-to-noise ratio (SNR) that is needed to achieve many codewords where they appear as short burst errors. a given probability of error. For high SNRs, it has been In block interleaving (Table 3.4-2), the channel shown that the probability of error for a TCM code can codewords are placed in the rows of an array, and the be approximated as codeword symbols are sent columnwise. In cross (or convolutional) interleaving, as shown in Figure 3.4-9, a set of ordered shift registers with linearly increasing (3.4.14) memory size is used to separate the output symbols of the channel encoder. where Q is the Q function, dmin represents the minimum distance of the TCM code and Kmin represents the 3.4.3.4 Turbo codes number of codewords that have a distance of dmin from a given codeword. We use to represent the variance of In 1993, Berrou et al. [9,10] amazed the coding com- the channel noi