The [n, k] codes that we have studied to this point are called block codes because we encode a message of k information symbols into a block of length n. On the other hand convolutional codes use an encoding scheme that depends not only upon the current message being transmitted but upon a certain number of preceding messages. Thus “memory” is an important feature of an encoder of a convolutional code. For example, if x(1), x(2), … is a sequence of messages each from to be transmitted at time 1, 2, …, then an (n, k) convolutional code with memory M will transmit codewords c(1), c(2), … where depends upon x(i), x(i − 1), …, x(i − M). In our study of linear block codes we have discovered that it is not unusual to consider codes of fairly high lengths n and dimensions k. In contrast, the study and application of convolutional codes has dealt primarily with (n, k) codes with n and k very small and a variety of values of M.

Convolutional codes were developed by Elias in 1955. In this chapter we will only introduce the subject and restrict ourselves to binary codes. While there are a number of decoding algorithms for convolutional codes, the main one is due to Viterbi; we will examine his algorithm in Section 14.2.