INTRODUCTION
▪ Convolutional codes were first discovered by P. Elias in 1955.
▪ The structure of convolutional codes is quite different from that
of block codes.
▪ During each unit of time, the input to a convolutional code
encoder is also a k-bit message block and the corresponding
output is also an n-bit coded block with k < n.
▪ Each coded n-bit output block depends not only on the
corresponding k-bit input message block at the same time unit
but also on the m previous message blocks.
▪ Thus the encoder has k input lines, n output lines and a memory
of order m.
1
EXAMPLE: CONVOLUTIONAL ENCODER, K = 1,
N= 2 x' = m m m j j−2 j−1 j
x '' = m m
j j−2 j
memory
depth L
= number
of states
(n,k,L) = (2,1,2) encoder
x = x ' x '' x ' x '' x ' x '' ...
out 1 1 2 2 3 3
Convolutional encoder is a finite state machine (FSM) processing
information bits in a serial manner
Thus the generated code is a function of input and the state of the FSM
In this (n,k) = (2,1) encoder each message bit influences a span of
Thus, for generation of n-bit output, we require in this example n shift
registers in k = 1 convolutional encoder
2
EXAMPLE: (N,K)=(3,2) CONVOLUTIONAL
ENCODER
• After each new block of k input bits
x' = m m m
j j−3 j−2 j
follows a transition into new state
• Hence, from each input state
x'' = m m m
j j−3 j−1 j
transition, 2k different output states
may follow
x''' = m m
j j−2 j
• Each message bit influences a span
of C = n(L+1) = 3(1+1) = 6
successive output bits
3
REPRESENTING CONVOLUTIONAL CODES: CODE TREE
Number of braches
deviating from each node
equals 2k
x' j = 1 0 0
x '' = 1 0
j
(n,k,L) = (2,1,2) encoder x ' j = 0 1 0
x '' = 0 0
x ' j = m j−2 m j−1 m j j
x '' = m m
j j−2 j
xout = x '1 x ''1 x '2 x ''2 x '3 x ''3 ...
m j−2 mj−1 = 01
This tells how one input bit
is transformed into two output bits
(initially register is all zero) x' j = 0 11
x '' = 0 1
Timo O. Korhonen, HUT Communication Laboratory j 4
10
REPRESENTING CONVOLUTIONAL CODES
COMPACTLY: CODE TRELLIS AND STATE
DIAGRAM
Input state ‘1’
indicated by dashed line
State diagram
Code trellis
Shift register states
5
The Viterbi algorithm
Problem of optimum decoding is to find the minimum distance path from the
initial state back to the initial state (below from S0 to S0). The minimum
distance is one of the sums of all path metrics from S0 to S0
Exhaustive maximum likelihood method
must search all the paths in phase trellis
(2k paths emerging/ entering from 2 L+1
states for
an (n,k,L) code)
The Viterbi algorithm gets improvement
in computational efficiency via
concentrating into survivor paths of the
trellis
6
THE SURVIVOR PATH
Assume for simplicity a convolutional code with k=1, and thus up to 2k =
2 branches can enter each state in trellis diagram
Assume optimal path passes S. Metric comparison is done by adding the
metric of S1 and S2 to S. At the survivor path the accumulated metric is
naturally smaller (otherwise it could not be the optimum path)
For this reason the non-survived path can
be discarded -> all path alternatives need not
to be further considered
Note that in principle the whole transmitted
sequence must be received before decision.
However, in practice storing of states for
input length of 5L is quite adequate 2by memory
nodes, determined
L
depth
2k branches enter each node branch of larger
metric discarded7
Timo O. Korhonen, HUT Communication Laboratory
EXAMPLE
Assume the received sequence is
y = 01101111010001
and the (n,k,L)=(2,1,2) encoder shown below. Determine the Viterbi
decoded output sequence!
(Note that for this encoder code rate is 1/2 and memory depth equals L = 2)
8
THE MAXIMUM LIKELIHOOD PATH
Smaller accumulated
After register length L+1=3
metric selected
branch pattern begins to repeat
(1) (1)
1
(1)
(1)
(2)
1
(0)
(Branch Hamming distances
in parenthesis) First depth with two entries to the node