d to be nonrecursive. For relatively small values of m, decoding is performed through the Viterbi algorithm, which is based on a principle of optimal decision for block error correction. It is beyond the scope of this introduction to enter the complexities of decoding algorithms for convolutional codes. Suffice it here to state that their error-correction capabilities can be tabulated according to their code rate k/n. 8 For 1/n codes with constraint length m, an upper bound for the See, for instance: http://en.wikipedia.org/wiki/Viterbi_algorithm. J.G. Proakis, Digital Communications (New York: McGraw Hill, 2001), pp. 492-6. Error correction Input Outputs Systematic Encoder 1 Output / Interleaver Encoder 2 Output // Figure 11.4 Generic layout of turbo encoder. minimum Hamming distance dmin is given by the following formula: (11.25) It is easily checked that with n = 2 and m = 3, for instance, the distance is bounded according to dmin < 5, corresponding to a maximum of two-bit-error correction. Con- volutional codes are commonly used in mobile-radio and satellite communications, and in particular in the wireless-connection standard called Bluetooth. Turbo codes These high-performance codes represent a relatively recent (1993) and significant advance in the field of ECC. The principle is that the turbo encoder generates three sub-blocks, as illustrated in Fig. 11.4. As the figure shows, the first sub-block is the k-bit block of payload data that is output as uncoded and, thus, representing the systematic output. The second sub-block (output I) contains m/2 parity bits for the payload, com- puted using a convolutional code. The third sub-block (output II), also computed through a convolutional code, contains m/2 parity bits for a known or fixed pseudo-random per- mutation of the input payload bits. Such a permutation is effected through an interleaver, as seen in the figure. This pseudo-random interleaving makes the output I and output II sub-blocks substantially different from each other, at least in a large majori