(7 votes, average: 3.86 out of 5)

# Convolutional code

by on January 4, 2009

Coding is a technique where redundancy is added to original bit sequence to increase the reliability of the communication. In this article, lets discuss a simple binary convolutional coding scheme at the transmitter and the associated Viterbi (maximum likelihood) decoding scheme at the receiver.

Update: For some reason, the blog is unable to display the article which discuss both Convolutional coding and Viterbi decoding. As a work around, the article was broken upto into two posts. This post descrbes a simple Binary Convolutional Coding scheme. For details on the Viterbi decoding algorithm, please refer to the post – Viterbi decoder.

Chapter 8, Table 8.2-1 of Digital Communications by John Proakis lists the various rate 1/2 convolutional coding schemes. The simplest among them has constraint length $K=3$ with generator polynomial $\left[ 7, 5\right]_8$. There are three parameters which define the convolotional code:

(a) Rate : Ratio of the number of input bits to the number of output bits. In this example, rate is 1/2 which means there are two output bits for each input bit.

(b) Constraint length : The number of delay elements in the convolutional coding. In this example, with $K=3$ there are two delay elements.

(c) Generator polynomial : Wiring of the input sequence with the delay elements to form the output. In this example, generator polynomial is $\left[ 7, 5\right]_8 = \left[111,101\right]_2$. The output from the $7_8 = 111_2$ arm uses the XOR of the current input, previous input and the previous to previous input. The output from the $5_8 = 101_2$uses the XOR of the current input and the previous to previous input.

Figure 1: Convolutional code with Rate 1/2, K=3, Generator Polynomial [7,5] octal

From the Figure 1, it can be seen that the operation on each arm is like a FIR filtering (aka convolution) with modulo-2 sum at the end (instead of a normal sum). Hence the name Convolutional code.

## State transition

For understanding the Viterbi way of decoding the convolutional coded sequence, lets understand the relation between the input and output bits and the state transition.

 if ip = 0 if ip = 1 current state next state (op) next state (op) 00 00 (00) 10 (11) 01 00 (11) 10 (00) 10 01 (10) 11 (01) 11 01 (01) 11 (10)

Table 1: State transition table and the output values

State transition for K=3, rate = 1/2 convolutional code

Figure 2: State transition for K=3, rate = 1/2 convolutional code

For details on the Viterbi decoding algorithm, please refer to the post – Viterbi decoder.

## References

Tutorial on Convolutional Coding with Viterbi Decoding – Mr. Chip Fleming

Digital Communications by John Proakis

D id you like this article? Make sure that you do not miss a new article by subscribing to RSS feed OR subscribing to e-mail newsletter. Note: Subscribing via e-mail entitles you to download the free e-Book on BER of BPSK/QPSK/16QAM/16PSK in AWGN.

{ 37 comments… read them below or add one }

marwa January 28, 2013 at 9:56 pm

salut, please Krishna I have to do a script to simulate QAM16 with convolutional code and viterbi decoder !

Krishna Sankar February 1, 2013 at 5:36 am

@marwa: Hope the post on Viterbi decoder and 16QAM bit error rate will be of help
http://www.dsplog.com/2009/01/04/viterbi/
http://www.dsplog.com/2008/06/05/16qam-bit-error-gray-mapping/

sirisha January 24, 2013 at 12:11 pm

please provide the vhdl code for convolution encoder

Krishna Sankar January 24, 2013 at 1:40 pm

@sirisha: sorry, i do not have it

arnab October 4, 2012 at 12:49 pm

sir pls give me suggestion regarding this how to implement in matlab:

MATLAB: Simulate the performance of a Viterbi decoder for the en-
coder
[
1 + D2 1 + D + D2
]
over an additive Gaussian noise channel
for BPSK modulated symbols. In your simulations assume the initial
state is the all-zero state, and run blocks of 1000 information bits per
block, terminating each block with two 0′s to drive the encoder into
the all-zero state. Plot the BER vs SNR.

Krishna Sankar October 5, 2012 at 5:07 am

@arnab: For some posts on Viterbi decoding with convolutional encoder, please check out
http://www.dsplog.com/2009/01/04/viterbi/
http://www.dsplog.com/tag/viterbi/

mepal September 28, 2012 at 4:47 am

Hi

An ISI channel can be viewed as a convolutional encoder. when MMSE LE is used at the receiver the cascade of Channel and Equalizer is still not ISI free .
How can we apply viterbi decoder after the equalizer in this case.

Regards
mepal

Krishna Sankar October 1, 2012 at 6:40 am

@mepal: We can use the state transitions caused by the channel and use that to build a Viterbi decoder.

gopinath September 3, 2012 at 8:57 am

sir im doing project on error detection and correction using convolution code in fpga,,, can u pls help me … thanking u

Krishna Sankar September 4, 2012 at 4:57 am

@gopinath: I have not discussed anything about FPGA coding, but you can read up about Viterbi decoder at
http://www.dsplog.com/tag/viterbi

Arpita July 22, 2012 at 6:35 pm

Hi Krishna;
I want to know how to prepare logic tables for a 1/3 convolution coder.

Krishna Sankar July 23, 2012 at 4:38 am

@Arpita: I believe you will be knowing the generator polynomial. From that one should be able to prepare the state transition table

Ronak May 12, 2012 at 4:09 am

Hi Krishna,

I’m totally messed up with Convolutional code.

I want to implement convo. encoder using K=3 with (7 , 5) generator. What is the rate of my problem. I have no idea what is my n an k.

I have refered many books and ended up being confused among symbols.

Kindly make me clear with K,k,n,M symbols.

Krishna Sankar May 15, 2012 at 5:53 am

@Ronak: Please refer Digital Communications by John Proakis

Also the post on Viterbi decoder also might be of help
http://www.dsplog.com/2009/01/04/viterbi/

sundar kharvi February 8, 2012 at 10:15 am

hi,
I m doing project on implementation of turbo encoder using VHDL . Can i get information about turbo encoder?

Gheorghe M.Panaitescu January 8, 2012 at 11:04 pm

I found in various places a table containing generator polynomials for convolutional encoding, specifically Table 1-”Generator Polynomials found by Busgang for good rate ½ codes” posted at http://www.complextoreal.com/convo.htm.
That table contains on the line Constraint length = 7 two identical polynomials, G1 = 110101 and G2 = 110101.
I guess this is not possible. The two polynomials must be different.
Does anybody knows the correct polynomials?

Krishna Sankar January 9, 2012 at 6:09 am

@Gheorge: I think that might be a typo. From Digital Communications by John Proakis, Table 8.2.1 , the generator polynomial in octal for constraint length 7, rate1/2 codes are:
a) 133_octal = 10000101_binary
b) 171_octal = 10101011_binary

kingshit August 2, 2012 at 5:41 pm

Octal, not decimal, so
133 -> 1011011
171 -> 1111001

Citra May 8, 2011 at 2:29 pm

Hi Krishna
I’ve seen the program about the convolutional code. What if the rate is replaced 2 / 3 with constraint length 3, kira2x parameters which must be changed? listings that you make there is the theory of maximum likelihood or not? If there is where do? Why should use the AWGN in the form of the complex?
Thank you for your attention.
I look forward to your assistance.

Krishna Sankar May 24, 2011 at 5:22 am

@Citra: How are you converting to 2/3 code – by puncturing?

arun showry March 20, 2010 at 4:09 am

Hi Dr.Krishna
I am trying to implement you paper “A novel Arq technique using the turbo coding principle”

I got the turbo decoder working , but in your paper you mention: when a retransmission takes place the LLR’s are used as a priori information.
before the LLR’s of the previous iteration are used in the current iteration what changes are to be done to the previous LLR;s.

I am doing this:
deinterleave to get original sequence and then interleave according to the interleaver pattern of second turbo enocder .

Is there anything wrong in what i am doing to the LLR’s.

thank you,
Arun

Krishna Sankar March 28, 2010 at 2:11 pm

@arun showry: Firstly, am not a Dr.
Secondly, the paper which you mention is written by Krishna R Narayan and not me
Thirdly, I have not studied Turbo code in much detail. Hence unable to answer

arun showry March 20, 2010 at 3:59 am

Hello All,
I am working on recursive convolution codes and viterbi decoding.

I am able to implement viterbi decoding with convolution encoder.
what changes do i need to make in the decoding section when i use recursive encoder.

I am doing this for viterbi decoding with a convolution encoder.

i/p=x
systematic part: Xs
Parity: Xp
tx_sig=[Xs Xp]

viterbi decoing

Krishna Sankar March 28, 2010 at 2:12 pm

@Arun Showry; Sorry, I have not tried to simulate decoder of recursive convolutional codes

manisha March 6, 2010 at 12:22 pm

what arethe convolutional codes for four bit dat 0000 to 1111

Krishna Sankar March 30, 2010 at 4:25 am

@manisha: Sorry, did not understand your query

hina January 29, 2010 at 2:59 am

how to solve this
A convolutional code is described by the generator polynomials g1, g2, g3 givenas
g1 = 1
g2 = 1+z inverse-2
g3 = 1+z inverse-1+z inverse-2

a)What is the code rate of this code?
b)Draw the encoder corresponding to this code
c)Draw the state diagram corresponding to this code
d)Find the minimum distance dmin of this code

Krishna Sankar April 4, 2010 at 4:48 am

@hina: Plz refer Digital Communications by Proakis

gana November 24, 2009 at 10:38 pm

I am doing a project on fpga implementataion of convolutional encoder and viterbi decoder.i am new to vhdl.can you give the the code for encoder.

Krishna Sankar December 7, 2009 at 4:21 am

@gana: Sorry, I do not have the vhdl code

manisha March 6, 2010 at 12:20 pm

cam we use convolutional codes for papr reduction in ofdm

Krishna Sankar March 30, 2010 at 4:26 am

@manisha: Convolutional coding is an error correction technique… Am not sure how it can be applied for PAPR reduction in OFDM

Communication February 4, 2009 at 7:51 pm

Hey Krishna, its me again. You have given simple and concise description of the convolutional code, that easy to understand.

However, can you talk about how to “BUILD” our code so that it can correct a specified number of errors.

Krishna Sankar February 10, 2009 at 7:45 pm

@communication: Thanks. I think its a block coding scheme which can be tuned to correct a maximum number of errors. I will try to discuss block coding in a future post.

manisha March 6, 2010 at 12:19 pm

sir i am doing project on ofdmpapr reduction
can u give me please mail me some codes for papr reduction

Krishna Sankar March 30, 2010 at 4:26 am

@manisha: Some relevant links which I picked up from a quick Googling.
(a) Tone reservation : where some of the unused subcarriers in an OFDM system is modulated to reduce the PAPR.
(b) MERL has a paper on PAPR reduction by oversampling, soft clipping and filtering.
PAPR Reduction for WiMAX OFDM Systems
http://www.merl.com/projects/papr/
(c) Nice comp.dsp thread on this topic
Has The peak-to-average ratio problem of OFDM been solved?
http://tinyurl.com/6jn9ql