**Convolutional code** is another type of error-correcting code where the output bits are obtained by performing a desired logical operation on a present bitstream along with considering some bits of the previous stream. This coding technique rather than depending on the block of bits shows dependency on bitstream.

It is also a linear code that consists of the shift register, used for temporarily storing the bits, shifting operation of bits along with X-OR logic circuits to give rise to an output code.

This was proposed by Elias in **1955** and further, in **1973**, Viterbi introduced an algorithm for decoding it which was named the Viterbi scheme.

## Content: Convolutional Code

- Error-Correcting Codes
- Introduction to Convolutional Code
- Block Diagram
- Example
- State Diagram Representation
- Trellis Diagram

### What are Error-Correcting Codes?

Error-correcting codes are the way to deal with the errors introduced in the actual message signal at the time of transmission in data communication. It is regarded as error detection and correction technique by which the information signal is encoded using redundant bits. These are categorized as:

- Block Code
- Convolutional Code

This content is subjected to convolutional coding.

## Introduction to Convolutional Code

Convolutional coding is known to be one of the most frequently used error correction techniques relative to digital wireless communication.

Previously, we have discussed block codes where the data stream is divided into blocks of bits having a specific length and is encoded using parity bits. However, block code and convolutional code are different from each other as the two are based on different encoding principles.

While discussing block codes, we have seen that there is a linear combination of information bits with parity bits in multiple blocks that are decoded by the receiver.

However, the major difference which is noticed in convolutional code is that, unlike block code, in convolutional code, only the parity bits with possible errors are received by the receiver. The receiver decodes to have the best possible bit sequence (which is nothing other than the message bits) from the obtained bitstream.

This seems quite confusing but it is interesting. We will understand the approach followed by considering an example later.

For convolutional code, it is said that the message has data streams of arbitrary length which undergoes encoding into a sequence of bits by the application of a Boolean function to the data stream.

## Block Diagram for Convolutional Code

The major elements of the convolutional coding technique include the shift register that acts as temporary storage and whose stored bits undergo shifting using a sliding window, a logic circuit that performs modulo-2 addition incorporating X-OR function. Before discussing the approach used in convolutional coding let us understand some important parameters.

Basically, there are mainly **two parameters** that define the convolutional coding which are as follows:

**Constraint length**: The constraint length corresponds to the length of the convolutional encoder i.e., the overall window size in bits, within the shift register. It is denoted by K (uppercase). Sometimes also denoted by L as it might cause confusion with k (lowercase). There is another parameter ‘m’ which corresponds to the number of input bits retained within the shift register once it is entered in the encoder.**Code rate**: Code rate is the ratio of a number of bits shifted at once within the shift register (denoted by k) to the total number of bits in an encoded (generated) bitstream (denoted by n). Thus, it is given as:

*The figure below represents the block diagram showing the convolutional coding technique:*

Basically, x[n-i] is the encoding state. Here we have shown two blocks x[n-1] and x[n-2], denoting there are 2 states of the encoder which is nothing but the previous bits. Input bit x[n] is fed to the encoder in order to obtain the parity bits.

Now, the question arises – **how parity bits (i.e., the output bits) are calculated?**

So, the parity bits are calculated using the states of the encoder and the input bit. In the above-given block diagram, we have considered 2 states with a single input bit. Thus, the overall constraint length i.e., **K** will be** 3**. Thus, for the convolutional code, it is said that the output stream shows dependency on previously-stored bits in memory along with the present input bits.

It is to be noted here that as the obtained output contains the parity bits thus, it will be wrong to assume that a longer constraint length will offer faster decoding. This is so because even a longer constraint will hold parity bits and a large number of parity bits will not make the decoding process quick.

### Example for Convolutional Code

To understand how convolutional encoding takes place. Consider the convolutional encoder shown below:

Here, there are 2 states p_{1} and p_{2,} and input bit (i.e., k) is represented by m. The two outputs of the encoder are X_{1} and X_{2} which are obtained by using the **X-OR** logic function. Thus, for the above configuration,

**X _{1} = m Ꚛ p_{1} Ꚛ p_{2}**

**X _{2} = m Ꚛ p_{2}**

Now, as we can see that there are 2 states thus, the various combinations of the two states can be represented as:

p_{1} | p_{2} | State |
---|---|---|

0 | 0 | S_{a} |

0 | 1 | S_{b} |

1 | 0 | S_{c} |

1 | 1 | S_{d} |

It can be clearly analyzed that here input bit k = 1, the encoded output bits n = 2, and the constraint length K = 3. So, in such case the code dimension (n,k) = (2,1). Hence code rate will be 1/2.

There will be a positional switching between X_{1} and X_{2}, thus the overall output will be in a manner:

**X = X _{1}.X_{2}.X_{1}.X_{2} —-**

Let us now tabulate the encoder operation by considering the current state (CS) and the next state (NS).

m | p_{1} | p_{2} | X_{1} | X_{2} | CS | NS |
---|---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | S_{a} | S_{a} |

1 | 0 | 0 | 1 | 1 | S_{a} | S_{c} |

0 | 0 | 1 | 1 | 1 | S_{b} | S_{a} |

1 | 0 | 1 | 0 | 0 | S_{b} | S_{c} |

0 | 1 | 0 | 1 | 0 | S_{c} | S_{b} |

1 | 1 | 0 | 0 | 1 | S_{c} | S_{d} |

0 | 1 | 1 | 0 | 1 | S_{d} | S_{b} |

1 | 1 | 1 | 1 | 0 | S_{d} | S_{d} |

First, consider the various combinations of two given states p_{1} and p_{2} for bits 0 and 1 in order to understand the operation. We have considered 8 combinations over here so that we can see the operation with binary input 0 and 1 individually.

Initially, all three bits within the register are set at 0 if message bit 0 is inserted then the current state will be S_{a}. Also, the X-OR logic operation will result in X_{1} and X_{2} as 0 and 0 respectively. When any other message bit is inserted then earlier values of m and p_{1} bits will undergo the right shift but as the state combination is still 0 and 0 and so, the next state will be S_{a}.

Now, if p_{1} = 0; p_{2} = 0 and input i.e., m is 1, in this case, the current state will be S_{a} and the values of X_{1} and X_{2} will be 1 and 1 respectively. However, when a next bit is inserted for input then all the 3 earlier bits will undergo the right shift and this will result in a new state combination as 10 therefore, the next state as S_{c}.

For p_{1 }= 0; p_{2 }= 1, and m = 0 the current state is S_{b} and resultantly the value of X_{1} and X_{2} will be 1 and 1 respectively. But when any other message bit will be provided as input then due to the right shift in present bits the new state combination will be 00 hence the next state will become S_{a}.

For p_{1} = 0; p_{2} = 1, and m = 1 the current state will S_{b} this will provide the value of X_{1} and X_{2} as 0 and 0 respectively. However, when another message bit will be inserted then due to the right shift within the encoder, the next state will become S_{c}.

For p_{1} = 1; p_{2} = 0, the current state will be S_{c} and if the message bit is 0 then the X_{1} and X_{2} will be 1 and 0 respectively. But when another input bit is inserted then the right shift in the present bits causes the next state to become S_{b}.

For p_{1} = 1; p_{2} = 0, the current state due to a combination of 1 and 0 will be S_{c} and for present message bit m =1, the values of X_{1} and X_{2} will be 0 and 1 respectively. However, whenever there will be another bit present at the input then the right shift within the encoder will result in the next state as S_{d}.

For p_{1} = 1; p_{2} = 1, the current state will be S_{d} and if the message bit is 0 then X-OR logic will provide X_{1} and X_{2} as 0 and 1 respectively. Whenever any next bit is required to be inserted then the right shift will cause the next state combination to be 0 and 1 thus next state will be S_{b}.

For p_{1} = 1; p_{2} = 1, the current state is S_{d} and for message bit 1 the logical function will give X_{1} and X_{2} as 1 and 0 respectively. As another input bit is required to be inserted then this will cause a right shift and the bit combination for the next state will be 1 and 1 and so the next state here will be S_{d}.

Thus, an input sequence of (01010101) produces an output sequence (0011110010010110).

### State Diagram Representation for Encoder

The state diagram representation of the above-described convolutional encoder is shown below:

This state diagram shows the transition from one state to another of the encoder according to the input bit. In the above figure, the input bits 0 and 1 are represented by blue and red lines, respectively.

All the 4 states S_{a} to S_{d} are considered here. The path information from one state to another is given in the fashion input/output. This can be understood in a way that a path from state S_{a} to S_{a} is obtained for input/output as 0/00. Similarly, the path from state S_{a} to S_{c} corresponds to input/output as 1/11. Likewise, the path from state S_{b} to S_{a} shows an input/output relation of 0/11.

### Trellis Diagram for Decoder

The trellis diagram is obtained by the state diagram representation which is shown above. By using a trellis diagram one can efficiently decode the obtained code sequence.

Here we have marked the four current states and next states, in the two columns. Each state of the current state column forms connections with 2 other states of the next state column according to the path in the state diagram representation.

For input 0 the CS and NS both are S_{a} resulting in output 00. Likewise, when input is 1, then CS and NS are S_{a} and S_{c} respectively. This combination provides output 11. In a similar way, when input is 0, CS and NS will be S_{b} and S_{a} respectively, with the current state combinational output as 11.

Basically, for decoding operation, the decoder needs to determine the sequence of stream which actually generates the parity bit sequence which is received at the receiver. This is achieved by observing the best path through the trellis that provides the sequence of parity bits received.