Digital Communications 1

4Convolutional Codes

4.1. Introduction

Convolutional codes are the second main class of error correcting codes. They were introduced by Elias in 1955 [ELI 55] and were first used for spatial communications. After the discovery of Viterbi’s algorithm in 1967, they were applied in almost all communication systems.

In this chapter, we will first study the convolutional codes and their encoders. Then, we will introduce Viterbi’s algorithm currently used for the decoding of these codes.

For a deeper development of convolutional codes, we recommend the books [PIR 88] and [JOH 99]. In this chapter, we will restrict ourselves to binary codes.

4.2. Mathematical representations and hardware structures

4.2.1. Definitions

A convolutional code is a code that transforms a semi-infinite sequence of information words into another semi-infinite sequence of codewords.

Let u be the input sequence or sequence of information words of dimension k of a binary convolutional encoder of rate , u = u₀, u₁, u₂, … where u_i = is the i^th information word of the sequence, and let c be the output sequence or sequence of codewords of dimension n, c = c₀, c₁, c₂, … where is the i^th codeword of the sequence as shown ...