Convolutional code

A convolutional code is a special kind of error-correcting code used in telecommunication. It adds extra bits to data to help find and fix mistakes when the data travels over a noisy 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 moving along the data, using a simple rule to decide which extra bits to add. This sliding process is called "convolution." Because of this method, convolutional codes can be decoded efficiently using something called a trellis, which helps correct errors faster.

One big advantage of convolutional codes is that they can be decoded well 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 first introduced in 1955 by Peter Elias. People believed these codes could be decoded very well if they used a lot of computation and waited a bit longer.

In 1967, Andrew Viterbi found a smart way to decode these codes using the Viterbi algorithm. After that, other decoding methods were developed, such as the BCJR algorithm. In about 1991, Claude Berrou created recursive systematic convolutional codes. These became very useful for handling complex codes like turbo codes.

Where convolutional codes are used

Stages of channel coding in GSM. Block encoder and Parity check – error detection part. Convolutional encoder and Viterbi decoder – error correction part. Interleaving and Deinterleaving – code words separation increasing in time domain and to avoid bursty distortions.

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, 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 one of the best ways to send data reliably, close to the Shannon limit.

Convolutional encoding

Img.1. Rate 1/3 non-recursive, non-systematic convolutional encoder with constraint length 3

To encode data using convolutional coding, we start with memory registers that hold bits. These registers start at zero. The encoder uses special rules and adders that follow simple math rules. As each new bit enters the register, the encoder creates new output symbols. Then, all bits shift to make space for the next 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. Non-systematic codes are often used because they work better with noise.

Recursive and non-recursive codes

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

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

Impulse response, transfer function, and constraint length

A convolutional encoder works by mixing the input data with special patterns called impulse responses. This is like sliding a pattern over the data to help find and fix errors later.

Each encoder can be described using a transfer function, which links to its impulse responses. The constraint length shows how many past inputs affect the current output. For example, sometimes the constraint length is 3, and other times it is 4. These details help engineers make systems that send data clearly and safely.

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

Trellis diagram

A convolutional encoder is like a special machine with 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.

Free distance and error distribution

The free distance (d) is the smallest difference between different encoded sequences. It helps show how many errors a convolutional code can fix. This number is found using a simple formula.

Theoretical bit-error rate curves of encoded QPSK (recursive and non-recursive, soft decision), additive white Gaussian noise channel. Curves are small distinguished due to approximately the same free distances and weights.

Convolutional codes work with a steady flow of data. They can fix many small groups of errors if the groups are not too close together. To make them better, data is sometimes rearranged before encoding. This lets other error-correcting methods fix most mistakes.

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

Decoding convolutional codes

Popular convolutional codes

Shift-register for the (7, [171, 133]) convolutional code polynomial. Branches: h 1 = 171 o = [ 1111001 ] b {\displaystyle h^{1}=171_{o}=_{b}} , h 2 = 133 o = [ 1011011 ] b {\displaystyle h^{2}=133_{o}=_{b}} . All of the math operations should be done by modulo 2.

Predefined convolutional codes are 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 harder to decode. 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

Turbo codes: replacing convolutional codes

A turbo code with component codes 13, 15. Turbo codes get their name because the decoder uses feedback, like a turbo engine. Permutation means the same as the interleaving. C1 and C2 are recursive convolutional codes. Recursive and non-recursive convolutional codes are not so much different in BER performance, however, recursive type of is implemented in Turbo convolutional codes due to better interleaving properties.

Main article: Turbo code

Simple convolutional codes are now often replaced by turbo codes. Turbo codes are a newer kind of error-correcting code. They work very well, coming close to the best possible performance. They do this without needing very complicated steps. When used with other codes, like Reed–Solomon codes, turbo codes can fix some of their own problems.