Convolutional code

A convolutional code is a special kind of error-correcting code used in telecommunication. It works by adding extra bits to a stream of data to help detect and fix mistakes that might happen when the data is sent over a noisy or imperfect channel, like a radio wave or a computer network.

This type of code uses a sliding method to create the extra bits. Imagine a window that moves along the data, applying a simple rule to decide which extra bits to add. This sliding process is what gives convolutional codes their name—"convolution." Because of this method, convolutional codes can be decoded efficiently using something called a trellis, which makes it easier and faster to correct errors.

One big advantage of convolutional codes is that they can be decoded in a way that gives very good results without being too complicated. They are described by two main features: their code rate and their memory. The code rate, written as n/k, tells us how many bits come out for each bit that goes in. For example, a rate of 1/2 means two bits come out for every one bit sent. The memory tells us how many past bits the encoder needs to look at to decide what extra bits to add.

Convolutional codes are very useful in real-world communications because their code rate can be changed by skipping some bits, a process called symbol puncturing. This makes them flexible and popular for things like satellite communication, mobile phones, and wireless networks, where keeping data clear and reliable is very important.

History

Convolutional codes were introduced in 1955 by Peter Elias. People thought these codes could be decoded very well if they were willing to use a lot of computation and wait a little longer.

In 1967, Andrew Viterbi discovered a smart way to decode these codes using something called the Viterbi algorithm. Later, other decoding methods were created too, like the BCJR algorithm. Around 1991, Claude Berrou invented recursive systematic convolutional codes, which became very helpful for processing complex codes such as turbo codes.

Where convolutional codes are used

Convolutional codes help make sure data gets through clearly in many things we use every day, like digital video, radio, and mobile communications. They are used in systems such as GSM, GPRS, EDGE, and older 3G networks up until 3GPP Release 7, as well as in satellite communications. These codes are often combined with another type of code called Reed–Solomon to work even better. Before a newer kind of code called turbo codes came along, convolutional codes were the best way to get data close to the Shannon limit, which is a way to measure how much information can be sent reliably.

Convolutional encoding

To encode data using convolutional coding, we start with some memory registers, each holding one bit. These registers begin at zero. The encoder uses special rules called generator polynomials and adders that follow modulo-2 arithmetic (where 1 + 1 equals 0). As each new bit enters the leftmost register, the encoder creates new output symbols based on the current register values and the generator polynomials. Then, all bits shift one place to the right, making space for the next input bit. This process continues until all registers return to zero.

Convolutional codes can be systematic, meaning they include the original message bits in the output, or non-systematic, meaning they change the message bits during encoding. Non-systematic codes are often used because they handle noise better.

Recursive and non-recursive codes

A non-recursive encoder does not use feedback, while a recursive encoder does. In the example given, the encoder is systematic because it includes the original input data in its output. Codes that do not include the input data in the output are called non-systematic.

Recursive systematic convolutional codes are popular because they are used in Turbo Codes. They are also known as pseudo-systematic codes. The example encoder shown has 8 possible states because it uses 3 registers, which can each be in one of two states (0 or 1). This leads to 2³ = 8 total states. These codes are useful in many applications, such as in LDPC codes, serial concatenated convolutional codes (SCCC's), and satellite links.

Impulse response, transfer function, and constraint length

A convolutional encoder works by combining the input data with special patterns called impulse responses. This process is like sliding a pattern over the data, which helps in checking and correcting errors later.

Each encoder can be described using a transfer function, which is linked to its impulse responses. The constraint length tells us how many past inputs affect the current output. For example, in one case the constraint length is 3, and in another it is 4. These details help engineers design better systems for sending data clearly and safely.

convolution linear time-invariant system transfer function Z-transform rational function polynomial degrees

Trellis diagram

See also: Trellis (graph) and Trellis coded modulation

A convolutional encoder works like a special kind of machine with a set number of memory cells. If there are n binary cells, the encoder can be in one of 2<sup>n</sup> different states. For example, if the left memory cell has a 1 and the right one has a 0, we call this state "10". Depending on the next input bit, the encoder can change to different states, but not all changes are possible.

We can draw all possible changes between states in a diagram. This helps us understand how to fix errors when we receive a message. If the received message does not match the diagram, we know there were errors and can try to find the closest matching sequence that does fit the diagram. This idea is used in real decoding methods.

Free distance and error distribution

The free distance (d) is the smallest difference between different encoded sequences. It helps determine how many errors a convolutional code can fix, called its correcting capability (t). This number is calculated using a simple formula.

Because convolutional codes work with a continuous flow of data, they can fix multiple small groups of errors, as long as these groups are not too close together. To improve performance, data is often rearranged before encoding, allowing other error-correcting methods to handle most mistakes.

Main articles: Hamming distance, concatenated code, Reed–Solomon
Further information: interleave

Decoding convolutional codes

See also: Viterbi algorithm

Different methods help computers figure out the correct message when using convolutional codes. One common way is the Viterbi algorithm, which works well for shorter messages and can be easily built using special computer chips or programs.

For longer messages, another method called sequential decoding is used. This includes the Fano algorithm, which helps handle more complex codes. These methods were once used in space missions but are now often paired with other error-correcting techniques to make sure messages are received clearly.

Popular convolutional codes

Predefined convolutional codes created through scientific research are commonly used in technology and space missions. One well-known example is a code with a constraint length of 7 and a rate of 1/2, which has been used since the Voyager program.

Space missions like Mars Pathfinder, Mars Exploration Rover, and the Cassini probe to Saturn use a more complex code with a constraint length of 15 and a rate of 1/6. This code works better than the simpler one but is also more difficult to decode. Similarly, the code with a constraint length of 2 and a rate of 1/2 is used in GSM to correct errors in mobile phone signals.

Punctured convolutional codes

See also: Punctured code

Convolutional codes can be adjusted to work at different speeds by using a method called puncturing. This means some bits are left out of the final code to make it faster. This is done by following specific patterns, called puncturing matrices.

These adjusted codes are used in satellite communications, like in systems from Intelsat and for Digital Video Broadcasting. They are sometimes called perforated codes.

Turbo codes: replacing convolutional codes

Main article: Turbo code

Simple convolutional codes are being replaced by turbo codes. Turbo codes are a new type of error-correcting code that come very close to the best possible performance, as described by Shannon's theorem. They do this with less complexity than older methods. When combined with another type of code, like Reed–Solomon codes, turbo codes can overcome some of their own limitations.