Coding on a trellis: Convolutional codes

In the previous chapter we have seen how a given block code can be represented by using a trellis. We now examine the problem of designing a binary code directly on a trellis. This can be done by first choosing a trellis with a preassigned complexity, then labeling its brunches. The trellis is generated by using one or more binary shift registers. The choice of a periodic trellis, which simplifies the Viterbi algorithm, and of symbols generated as linear combinations of the contents of the shift registers, leads to the definition of convolutional codes. Invented in 1954. these codes have been very successful because they can be decoded in a simple way. have a good performance, and are well adapted to the transmission of continuous streams of data. In this chapter, we present the rudiments of an algebraic theory of convolutional codes, and show how code performance can be evaluated.