Charan Langton, Editor
SIGNAL
PROCESSING & SIMULATION NEWSLETTER
Tutorial 12
Coding and decoding with
Convolutional Codes
Convolutional
codes are commonly specified by three parameters; (n,k,m).
n = number of output bits
k = number of input bits
m = number of memory
registers
The
quantity k/n called the code rate, is
a measure of the efficiency of the code. Commonly k and n parameters range
from 1 to 8, m from 2 to 10 and the
code rate from 1/8 to 7/8 except for deep space applications where code rates
as low as 1/100 or even longer have been employed.
Often
the manufacturers of convolutional code chips specify the code by parameters (n,k,L), The quantity L is called the
constraint length of the code and is defined by
Constraint Length, L = k (m-1)
The
constraint length L represents the number of bits in the encoder memory that
affect the generation of the n output
bits. The constraint length L is also referred to by the capital letter K,
which can be confusing with the lower case k,
which represents the number of input bits. In some books K is defined as equal
to product the of k and m. Often in
commercial spec, the codes are specified by (r, K), where r = the code rate k/n and K is the constraint length. The
constraint length K however is equal to L – 1, as defined in this paper. I will
be referring to convolutional codes as (n,k,m)
and not as (r,K).
Code parameters and the structure of the
convolutional code
The
convolutional code structure is easy to draw from its parameters. First draw m boxes representing the m memory registers. Then draw n modulo-2 adders to represent the n output bits. Now connect the memory
registers to the adders using the generator polynomial as shown in the Fig. 1.
Figure 1 - This (3,1,3) convolutional code has 3 memory registers, 1 input bit and 3 output bits.
This
is a rate 1/3 code. Each input bit is coded into 3 output bits. The constraint
length of the code is 2. The 3 output bits are produced by the 3 modulo-2
adders by adding up certain bits in the memory registers. The selection of
which bits are to be added to produce the output bit is called the generator
polynomial (g) for that output bit. For example, the first output bit has a
generator polynomial of (1,1,1). The output bit 2 has a generator polynomial of
(0,1,1) and the third output bit has a polynomial of (1,0,1). The output bits
just the sum of these bits.
v1 = mod2 (u1 + u0 + u-1)
v2 = mod2 ( u0 + u-1)
v3 = mod2 (u1 + u-1)
The
polynomials give the code its unique error protection quality. One (3,1,4) code
can have completely different properties from an another one depending on the
polynomials chosen.
How polynomials are selected
There
are many choices for polynomials for any m
order code. They do not all result in output sequences that have good error
protection properties. Petersen and Weldon’s book contains a complete list of
these polynomials. Good polynomials are found from this list usually by
computer simulation. A list of good polynomials for rate ½ codes is given
below.
Table 1-Generator Polynomials found by Busgang for good rate ½ codes
|
Constraint Length |
G1 |
G2 |
|
3 4 5 6 7 8 9 10 |
110 1101 11010 110101 110101 110111 110111 110111001 |
111 1110 11101 111011 110101 1110011 111001101 1110011001 |
States of a code
We
have states of mind and so do encoders. We are depressed one day, and perhaps
happy the next from the many different states we can be in. Our output depends
on our states of mind and tongue-in-cheek we can say that encoders too act this
way. What they output depends on what is their state of mind. Our states are
complex but encoder states are just a sequence of bits. Sophisticated encoders
have long constraint lengths and simple ones have short in dicating the number
of states they can be in.
The
(2,1,4) code in Fig. 2 has a constraint length of 3. The shaded registers below
hold these bits. The unshaded register holds the incoming bit. This means that
3 bits or 8 different combination of these bits can be present in these memory
registers. These 8 different combinations determine what output we will get for
v1 and v2, the coded sequence.
The
number of combinations of bits in the shaded registers are called the states of
the code and are defined by
Number of states = 2L
where
L = the constraint length of the code and is equal to k (m - 1).
Figure 2 – The states of a code indicate what is in the memory registers
Think
of states as sort of an initial condition. The output bit depends on this
initial condition which changes at each time tick.
Let’s
examine the states of the code (2,1,4) shown above. This code outputs 2 bits
for every 1 input bit. It is a rate ½ code. Its constraint length is 3. The
total number of states is equal to 8.
The
eight states of this (2,1,4) code are: 000, 001, 010, 011, 100, 101, 110, 111.
Punctured Codes
For
the special case of k = 1, the codes
of rates ½, 1/3, ¼, 1/5, 1/7 are sometimes called
mother codes. We can combine these single bit input codes to produce
punctured codes which give us code rates other than 1/n.
By
using two rate ½ codes together as shown in Fig. 3 , and then just not
transmitting one of the output bits we can convert this rate ½ implementation
into a 2/3 rate code. 2 bits come and 3 go out. This concept is called puncturing. On the receive side, dummy
bits that do not affect the decoding metric are inserted in the appropriate
places before decoding.
Figure 3 - Two (2,1,3) convolutional codes
produce 4 output bits. Bit number 3 is “punctured” so the combination is
effectively a (3,2,3) code.
This
technique allows us to produce codes of many different rates using just one
simple hardware. Although we can also directly construct a code of rate 2/3 as
we shall see later, the advantage of a punctured code is that the rates can be
changed dynamically (through software) depending on the channel condition such
as rain, etc. A fixed implementation, although easier, does not allow this
flexibility.
Structure of a code for k > 1
Alternately
we can create codes where k is more
than 1 bit such as the (4,3,3) code. This code takes in 3 bits and outputs 4
bits. The number of registers is 3. The constraint length is 3 x 2 = 6. The
code has 64 states. And this code
requires polynomials of 9th order. The shaded boxes represent the
constraint length.
The
procedure for drawing the structure of a (n,k,m)
code where k is greater than 1 is as
follows. First draw k sets of m boxes. Then draw n adders. Now connect n
adders to the memory registers using the coefficients of the nth (km) degree polynomial. What you will get
is a structure like the one in Fig. 4 for code (4,3,3).
Figure 4 - This
(4,3,3) convolutional code has 9 memory registers, 3 input bit and 4 output
bits. The shaded registers contain “old” bits representing the current state.
Systematic vs. non-systematic CC
A
special form of convolutional code in which the output bits contain an easily
recognizable sequence of the input bits is called the systematic form. The
systematic version of the above (4,3,3) code is shown below. Of the 4 output bits, 3 are exactly the same as
the 3 input bits. The 4th bit is kind of a parity bit produced from
a combination of 3 bits using a single polynomial.
Figure 5 - The systematic version of the
(4,3,3) convolutional code. It has the same number of memory registers, and 3
input bits and 4 output bits. The output bits consist of the original 3 bits
and a 4th “parity” bit.
Systematic
codes are often preferred over the non-systematic codes because they allow
quick look. They also require less hardware for encoding. Another important
property of systematic codes is that they are non “catastrophic”, which means that errors can not propogate
catastrophically. All these properties make them very desirable. Systematic
codes are also used in Trellis Coded Modulation (TCM). The error protection
properties of systematic codes however are the same as those non-systematic
codes.
Coding an incoming sequence
The
output sequence v, can be computed by convolving the input sequence u with the
impulse response g. we can express this as
v
= u * g
or
in a more generic form
where
is the output bit l
from the encoder j, and 
is the input bit, and
is the ith term in the polynomial j.
Let’s encode a two bit sequence of 10 with the (2,1,4) code and see how the
process works.
Figure 6 - A sequence consisting of a solo 1 bit as it
goes through the encoder. The single bit produces 8 bit of output.
First
we will pass a single bit 1 through this encoder as shown in Fig 6.
a)
At time t = 0, we see that the initial state of the encoder is all zeros (the
bits in the right most L register positions). The input bit 1 causes two bits
11 to be output. How did we compute that? By a mod2 sum of all bits in the
registers for the first bit and a mod2 sum of three bits for second output bit
per the polynomial coefficients.
b)
At t = 1, the input bit 1 moves forward one register. The input register is now
empty and is filled with a flush bit of 0. The encoder is now in state 100. The
output bits are now again 11 by the same math.
c)
the input bit 1 moves forward again. Now the encoder state is 010 and an
another flush bit is moved into the input register. The output bits are now 10.
d)
At time 3, the input bit moves to the last register and the input state is 001.
The output bits are now 11. At time 4, the input bit 1 has passed completely
thorough the encoder and the encoder has been flushed to an all zero state,
ready for the next sequence.
Note
that a single bit has produced an 8-bit output although nominally the code rate
is ½. This shows that for small sequences the overhead is much higher than the
nominal rate, which only applies to long sequences.
If
we did the same thing with a 0 bit, we would get an 8 bit all zero sequence.
What
we just produced is called the impulse response of this encoder. The 1 bit has
a response of
11
11 10 11 which is called the impulse
response. The 0-bit similarly has an impulse response of
00 00 00 00 (not shown but this is obvious)
Convolving
the input sequence with the code polynomials produced these two output
sequences, which is why these codes are called convolutional codes. From the
principle of linear superposition, we can now produce a coded sequence from the
above two impulse responses as follows.
Let’s
say that we have a input sequence of 1011 and we want to know what the coded
sequence would be. We can calculate the output by just adding the shifted
versions of the individual impulse responses.
Input Bit Its
impulse response
1 11
11 10 11
0 00
00 00 00
1 11 11 10 11
1 11 11 10 11
Add to obtain response
1011 11
11 01 11 01 01 11
We
obtained the response to sequence 1011 by adding the shifted version of the
responses for 1, and 0.
In
Figure 7, we manually put the sequence 1011 through the encoder to verify the
above and amazingly enough, we will get the same answer. This shows that that
the convolution model is correct.
The
result of the above encoding at each time interval is shown in Table 2.
Table 2 - Output Bits and the Encoder Bits through the (2,1,4 Code)
Input bits: 1011000
|
Time |
Input Bit |
Output Bits |
Encoder Bits
|
|
0 |
1 |
11 |
000 |
|
1 |
0 |
11 |
100 |
|
2 |
1 |
01 |
010 |
|
3 |
1 |
11 |
101 |
|
4 |
0 |
01 |
110 |
|
5 |
0 |
01 |
011 |
|
6 |
0 |
11 |
001 |
The
coded sequence is 11 11 01 11 01 01 11.
The encoder design
The
two methods in the previous section show mathematically what happens in an
encoder. The encoding hardware is much
simpler because the encoder does no math. The encoder for convolutional code
uses a table look up to do the encoding. The look up table consists of four
items.
1.
Input
bit
2.
The
State of the encoder, which is one of the 8 possible states for the example
(2,14) code
3.
The
output bits. For the code (2,1,4), since 2 bits are output, the choices are 00,
01, 10, 11.
4.
The
output state which will be the input state for the next bit.
For
the code (2,1,4) given the polynomials of Figure 7, I created the following
look up table in an Excel worksheet.
Table 3 – Look-up Table for the encoder of code (2,1,4)
|
Input Bit |
Input State |
|
Output Bits |
Output State |
||||||
|
I1 |
s1 |
s2 |
s3 |
|
O1 |
O2 |
|
s1 |
s2 |
s3 |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
|
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
|
1 |
1 |
|
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
|
0 |
0 |
|
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
1 |
0 |
|
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
0 |
1 |
|
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
|
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
1 |
1 |
|
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
0 |
0 |
|
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
0 |
|
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
|
1 |
1 |
0 |