Channel Code

Convolutional Code
• Convolutional coding
• Code tree, State and Trellis Diagram : Coding
• Viterbi algorithm and Sequential decoding
• We have studied block codes, where -------
• block of k information symbols are encoded into a block of n
coded symbols
• There is one to one correspondence between information
symbols and coded symbols.
• This method is useful for high data rate application, where
incoming data is broken into blocks , encoded and then
transmitted.
• Large block length is important as it implies smaller encoding
overhead
• BUT large block length is disadvantageous
• Unless entire block of information digits is available at transmitter,
encoding process cannot start
• Similarly at receiver , unless entire codeword is received, decoding
procedure can not start.
• This results in substantial DELAYS
Convolutional codes differ from block code
Encoding can start after obtaining small block of information digits.
the encoder contains memory and the n encoder outputs at any time
unit depend not only on the k inputs but also on K previous input
blocks
• An (n, k, K) convolutional code can be implemented with a k input,
n-output linear sequential circuit with input memory K
• Ratio k/n has the same code rate significance (information per coded
bit) that it has for block codes
n does not define a block or code word length as it does for block
codes
• A convolutional code is generated by passing the information
sequence to be transmitted through a linear finite-state shift register
The shift register consists of K (k-bit) stages and n linear algebraic
function generators
Convolutional codes
• k = number of bits shifted into
the encoder at one time
k=1 is usually used!!
• n = number of encoder output
bits corresponding to the k
information bits
• Rc = k/n = code rate
• K = constraint length, encoder
memory.
• Each encoded bit is a function of
the present input bits and their
past ones.
• Shift Register : Holds K information symbols. Each symbol is
of k digits, so shift register length is Kk digits consisting of
present k digit symbols and previous(K-1)k digit information
symbols. K is called as constraint span of code
• Modulo-2 Adder
• n digit code word given by output of Modulo-2 Adder: in
contrast to block code, code length n is not very higher than
constraint span K
Example
• Consider the binary convolutional encoder with constraint length K=3,
k=1, and n=3
• The generators are: g1=[100], g2=[101], and g3=[111]
• Draw state and trellis diagram
Example 2
• Consider a rate 1/3 convolutional encoder.
•The generators are: g1=[1011], g2=[1101], and g3=[1010]
In octal form, these generator are (13, 15, 12)
• There are three alternative methods that are often used to describe a
convolutional code:
• State diagram
• Tree diagram
• Trellis diagram
 Convolutional encoder is described by g1=[100], g2=[101], g3=[111]
• Draw encoder
• Draw State Transition Diagram, Trellis diagram
• Encoder g1= m1 g2= m1 + m3 g3= m1 + m2 + m3
V1

V2 Output
Input
m1 m2 m3

V3
State Transition Table
State Un Un-1 Input Un Un-1 Un-2 State Output
data bit m1 m2 m3 V1 V2 V3
m1 m1 + m3 m1 + m2 + m3

a 0 0
0 0 0 0 a
 a =00 b= 01 c= 10 d=11

Present Output
m1 m2 m3 State V1 V2 V3
m1 + m2 +
State m1 m2 m1 m1 + m3 m3
a 0 0
0
a-----a 0 0 0 a 0 0 0
a
1
c 1 0 0 c 1 1 1
b 0 1
0
b - ----a 0 0 1 a 0 1 1
 State Transition Table
Present Output
State m1 m2 m1 m2 m3 State V1 V2 V3
m1 m1 + m3 m1 + m2 + m3
a 0 0
0
a---a 0 0 0 a 0 0 0 m1 m3
m2
1
a---c 1 0 0 c 1 1 1

b 0 1
0
b---a 0 0 1 a 0 1 1
1
b---c 1 0 1 c 1 0 0

c 1 0
0
c----b 0 1 0 b 0 0 1
1
c---d 1 1 0 d 1 1 0

d 1 1
0
d---b 0 1 1 b 0 1 0
1
d---d 1 1 1 d 1 0 1
 000 /0

011 /0 a 111 /1
100 /1
b C
001 /0
010 /0 110 /1
db
101/1
 State Transition Diagram
Present Output

State m1 m2
m1 m2 m3 State V1 V2 V3
m1 +
000 /0
m1 +
m1 m2 +
m3
m3
a 0 0
0
a---a
1
a---c
0

1
0

0
0

0
a

c
0

1
0

1
0

1 011 /0 a 111 /1
b 0 1
0 100 /1
b---a
1
0 0 1 a

c
0 1 1
b C
001 /0
b---c 1 0 1 1 0 0

c 1 0
0
c----b
1
0 1 0 b 0 0 1
010 /0 110 /1
c---d 1 1 0 d 1 1 0 db
d 1 1
0
d---b
1
0 1 1 b 0 1 0
101/1
d---d 1 1 1 d 1 0 1
 Trellis Diagram
• Trellis diagram shows how each possible input to the encoder
influences both output and state transition of encoder
• Each solid arrow shows how the encoder changes its state if current
input is zero
• Each dashed arrow shows how the encoder changes its state if
current input is one
 000 /0

011 /0 a 111 /1
100 /1
b C
001 /0
010 /0 110 /1
db
101/1
solid arrow 1 current input is zero
Dashed Arrow 2 Current input is 1 Trellis Diagram

000 000 000 000 000

• a = 00 011 011
011

• b = 01 001 001 001 001

111 111 111
010 010 010
111 111
• c =10 100 100 100

• d = 11 110 110 110 110

101 101 101
t t+1 t+2 t+3 t+4
solid arrow 1 current input is zero
Dashed Arrow 2 Current input is 1 Trellis Diagram
Present State Next State
000
• a = 00 011
• a = 00

• b = 01 001 • b = 01
010
111
• c =10 100
• c =10

• d = 11 101 110 • d = 11
Show state transition Table and Resulting output code word sequence for
input bit pattern 101011, followed by two 0s to flush the register.
Assume initial content of register are all 0s.
 CONVOLUTIONAL DECODING :
Maximum Likelihood Decoding
• If all input message sequences are equally likely, a decoder that
achieves the minimum probability of error is one that compares the
conditional probabilities, also called the likelihood functions
• P(Z | U(m)),
• where Z is the received sequence and
• U(m) is one of the possible transmitted sequences, and chooses the maximum.
• The decoder chooses U(m’) if P(Z | U(m’)) = max P(Z | U(m)) over all U(m)
• In binary demodulation, only two equally likely possible signals, s1(t)
or s2(t), that might have been transmitted. Therefore, to make the
binary maximum likelihood decision, given a received signal, meant
only to decide that
• s1(t) was transmitted if P(Z | S1) > P(Z | S2) otherwise, to decide that s2(t) was
transmitted
• When applying maximum likelihood to the convolutional decoding
problem, we observe that the convolutional code has memory.
• There are typically a multitude of possible code word sequences that
might have been transmitted.
• To be specific, for a binary code, a sequence of L branch words is a
member of a set of 2L possible sequences.
• Therefore, in the maximum likelihood context, we can say that the
decoder chooses a particular U(m’) as the transmitted sequence if the
likelihood P(Z | U(m’)), is greater than the likelihoods of all the other
possible transmitted sequences. Such an optimal decoder, which
minimizes the error probability (for the case where all transmitted
sequences are equally likely), is known as a maximum likelihood
decoder.
• The channel over which the waveform is transmitted is assumed to
corrupt the signal with Gaussian noise. When the corrupted signal is
received, it is first processed by the demodulator and then by the
decoder.
• maximum likelihood decoder will choose, in the tree or trellis
diagram, the path whose corresponding sequence U(m’) is at the
minimum Hamming distance to the received sequence Z.
 The Viterbi Convolutional Decoding Algorithm
• Performs maximum likelihood decoding; however, it reduces the
computational load by taking advantage of the special structure in the code
trellis.
• The algorithm involves calculating a measure of similarity, or distance,
between the received signal, at time ti , and all the trellis paths entering
each state at time ti .
• When two paths enter the same state, the one having the best metric is
chosen; this path is called the surviving path.
• This selection of surviving paths is performed for all the states. The
decoder continues in this way to advance deeper into the trellis, making
decisions by eliminating the least likely paths. The early rejection of the
unlikely paths reduces the decoding complexity.
• maximum likelihood metric = minimum distance metric
• at each time interval, to label each branch with the Hamming
distance between the received code symbols and the branch word
corresponding to the same branch from the encoder trellis.
• received sequence Z 11 01 01 10 01
• each branch of the decoder trellis is labeled with a metric of similarity
(Hamming distance) between the received code symbols and each of
the branch words for that time interval. From
Input data sequence m: 1 1 0 1 1

Transmitted codeword U: 11 01 01 00 01

Received sequence Z: 11 01 01 10 01

2 1 1 1 1

1
0 1 1
1
1
1 1 1
1
2 0
0
2
0
0
0 2 0
2

2
0 2
T1 T2 T3 T4 T5 T6 TOTAL METRIC
a a 2 a 3 a 4 a 5 a 6
a a 2 a 3 a 4 a 5 b 6
a a 2 a 3 a 4 b 5 c 7
a a 2 a 3 a 4 b 0 d 5
a a 2 a 3 b 4 c a 5
a a 2 a 3 b 4 c b 5
a a 2 a 3 b 4 d c 6
a a 2 a 3 b 4 d d 8
a a 2 b 3 c 3 a a
a a 2 b 3 c 3 a b
a a 2 b 3 c 3 b c
a a 2 b 3 c 3 b d
a a 2 b 3 d 3 c a
a a 2 b 3 d 3 c b
a a 2 b 3 d 3 d c
a a 2 b 3 d 3 d d
T1 T2 T3 T4 T5 T6 TOTAL
METRIC
a b 0 c 2 a 3 a 4 a 5
a b 0 c 2 a 3 a 4 b 5
a b 0 c 2 a 3 b 4 c 6
a b 0 c 2 a 3 b 4 d 4
a b 0 c 2 b 3 c 3 a 4
a b 0 c 2 b 3 c 3 b 4
a b 0 c 2 b 3 d 3 c 5
a b 0 c 2 b 3 d 3 d 7
a b 0 d 0 c 0 a 1 a 2
a b 0 d 0 c 0 a 1 b 2
a b 0 d 0 c 0 b 1 c 3
a b 0 d 0 c 0 b 1 d 1
a b 0 d 0 d 2 c 4 a 5
a b 0 d 0 d 2 c 4 b 5
a b 0 d 0 d 2 d 2 c 2
a b 0 d 0 d 2 d 2 d 4
 a a a a b c a a
a a a a b a b c a b
a b a b c a b c b c
a b d a b c b d

a a a a 4
a a a b 4
a a b c 5
a b d c a
a a b d 3
a b c a 3 a b d c b
a b c a 3
a b c b 3 a b d d c
a b c b 3
a b d c 0 a b d c 0 a b d d d
a b d d 2 a b d d 2
Input data sequence m: 1 1 0 1 1
 Turbo Codes
• The first practical codes to closely approach the maximum channel
capacity or Shannon limit, a theoretical maximum for the code rate at
which reliable communication is still possible given a specific noise level.
• Turbo codes are used in 3G/4G mobile communications (e.g.,
in UMTS and LTE) and in (deep space) satellite communications as well
as other applications where designers seek to achieve reliable
information transfer over bandwidth- or latency-constrained
communication links in the presence of data-corrupting noise.
• Turbo codes compete with LDPC codes ("low-density parity-check"),
which provide similar performance.
An example encoder
• This encoder implementation sends three sub-blocks of bits.
• The first sub-block is the m-bit block of payload data.
• The second sub-block is n/2 parity bits for the payload data,
computed using a recursive systematic convolutional code (RSC
code).
• The third sub-block is n/2 parity bits for a known permutation of
the payload data, again computed using an RSC code.
• Thus, two redundant but different sub-blocks of parity bits are
sent with the payload.
• The complete block has m + n bits of data with a code rate
of m/(m + n).
• The permutation of the payload data is carried out by a device
called an interleaver.
Hardware-wise, this turbo code encoder consists of two identical
RSC coders, С1 and C2, as depicted in the figure, which are
connected to each other using a concatenation scheme,
called parallel concatenation:
• In the figure, M is a memory register.
• The delay line and interleaver force input bits dk to
appear in different sequences.
• At first iteration, the input sequence dk appears at
both outputs of the encoder xk and y1k or y2k due
to the encoder's systematic nature.
• If the encoders C1 and C2 are used in n1 and n2
iterations, their rates are respectively equal to