Convolutional Codes

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.

What is 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

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:
1. 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.
2. 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:
𝑘
𝑟𝑐 = 𝑛

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.
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 p1 and p2, and input bit (i.e., k) is represented by m. The two
outputs of the encoder are X1 and X2 which are obtained by using the X-OR logic function.
Thus, for the above configuration,

X1 = m Ꚛ p1 Ꚛ p2

X2 = m Ꚛ p2
Now, as we can see that there are 2 states thus, the various combinations of the two
states can be represented as:
p1 p2 State
0 0 Sa
0 1 Sb
 1 0 Sc
1 1 Sd
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 X1 and X2, thus the overall output will be in
a manner:
X = X1.X2.X1.X2 —-
Let us now tabulate the encoder operation by considering the current state (CS) and the
next state (NS).
m p1 p2 X1 X2 CS NS
0 0 0 0 0 Sa Sa
1 0 0 1 1 Sa Sc
0 0 1 1 1 Sb Sa
1 0 1 0 0 Sb Sc
0 1 0 1 0 Sc Sb
1 1 0 0 1 Sc Sd
0 1 1 0 1 Sd Sb
1 1 1 1 0 Sd Sd

Now, if p1 = 0; p2 = 0 and input i.e., m is 1, in this case, the current state will be Sa and
the values of X1 and X2 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 Sc.

For p1 = 0; p2 = 1, and m = 0 the current state is Sb and resultantly the value of X1 and
X2 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 Sa.

For p1 = 0; p2 = 1, and m = 1 the current state will Sb this will provide the value of X1 and
X2 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 Sc.
For p1 = 1; p2 = 0, the current state will be Sc and if the message bit is 0 then the X1 and
X2 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 Sb.

For p1 = 1; p2 = 0, the current state due to a combination of 1 and 0 will be Sc and for
present message bit m =1, the values of X1 and X2 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 Sd.

For p1 = 1; p2 = 1, the current state will be Sd and if the message bit is 0 then X-OR logic
will provide X1 and X2 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 Sb.
For p1 = 1; p2 = 1, the current state is Sd and for message bit 1 the logical function will
give X1 and X2 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 Sd.

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

(0011110010010110).
State Diagram Representation for Encoder

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 Sa to Sd 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 Sa to Sa is obtained for input/output as 0/00. Similarly, the path from state Sa
to Sc corresponds to input/output as 1/11. Likewise, the path from state Sb to Sa 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 Sa resulting in output 00. Likewise, when input is 1,
then CS and NS are Sa and Sc respectively. This combination provides output 11. In a
similar way, when input is 0, CS and NS will be Sb and Sa 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.