TABLE OF CONTENTS Convolutional codes were discovered by Peter Elias in 1954 (Elias, 1954) and since then many researchers have dedicated time tounderstand the properties and the structure of such codes (Lin and Palais, 1986, Johannesson and Zigangirov, 1999, Heegard and Wicker, 1999). Convolutional codes offer an alternative for error control which is substantially different from that offered by block codes.
Wozencraft and Reiffen (1961) described the first practical decoding algorithm for convolutional codes. In 1967, Viterbi (1985) discovered another way of decoding convolutional codes which he thought to be asymptotically optimum. In 1973, Forney showed that the Viterbi algorithm was a maximum likelihood decoding algorithm for convolutional codes (Forney, 1973). More recently, Berrou et al. (1993) introduced a turbo decoding algorithm for a code construction employing convolutional codes. This is by far the most remarkable result in coding theory since Shannon s papers. A turbo decoder allows performance very close to the Shannon limit (channel capacity) (Berrou and Glavieux, 1996), in the presence of additive white Gaussian noise. Turbo decoding was also shown to work equally well with block codes (Pyndiah et al., 1994). Convolutional codes have championed the code race in space research in combination with RS codes. In the following, the basic theory of convolutional codes is revisited.
A ( n, k, m) binary convolutional encoder (BCE) is a linear device with memory that accepts blocks of k binary digits or message bits as input, and outputs blocks of
