sonably likely Chapter 4 Coding paths at timestep i are traced backward in time, they will converge to the same path within about 5L timesteps. The decoder therefore operates with a fixed delay of 8 steps, where 8 5L; at time i it selects one of the reasonably likely paths, and the bit from that path at time i - 8 is output as the decoded output. The path stores within the decoder can therefore be implemented as 8-bit shift registers. Code Performance A decoding error occurs when the path through the trellis selected by the decoder is not the correct path. The result will almost always be a burst error; it is even possible, for some codes, for the worst error to be infinite in extent. Such codes are clearly unusable. Analysis of the exact statistics of the error bursts (their probability as a function of their duration) is very complex; approximations can, however, be derived using the minimum free distance of the code. This is obtained by considering all possible error paths-that is, incorrect paths that depart from the correct path at one symbol time and rejoin it later. The minimum free distance is the minimum number of symbol differences between any of these error paths and the correct path. Note, however, that calculation of the true error rates involves analysis of many other interacting effects. In practice, the user of a convolutional code will normally use the published graphs of output BER as a function of SNR (Eb/no). The coding gain is also often quoted, but it is important to remember that this varies with SNR. Turbo and LDPC Codes Until the 1990s, the most powerful codes for telecommunications, known as RSV codes, were created by concatenating Reed-Solomon and Viterbi-decoded convolutional codes. Two major advances came with Turbo codes (1993) and LDPC codes (1995). The huge performance benefit of these codes arises because they generate very long codewords but in a way that allows the decoder to converge rapidly to the optimum estimate of the data digits. Turbo Codes In 1993 Berrou, Glavieux, and T