convolutional Codes , block codes and convolutional codes , coding gain of convolutional codes

maximum likelihood decoding of convolutional codes , convolutional Codes , block codes and convolutional codes , coding gain of convolutional codes :-
Few Definitions Related to convolutional Codes

1. Code rate (r)

The code rate of the encoder of figure 10.48 is expressed as
R =                                                                                 …(10.52)
Here,                           k = Number of message bits = 1
n = Number of encoded bits per message bits = 2
Therefore,                    r =                                                                                   …(10.53)

2. Constraint length (k)

Each message bit influences a span of n (L + 1) successive output bits. The quantity n (L + 1) is called as the constraint length. It is measured in terms of encoded output bits. For the encoder of figure 10.48, the constraint length is 6 bits as n = 2 and L = 2. Here, L is the encoder’s memory measured in terms of input message bits.

3. Code Dimension

The code dimension of a convolutional code depends on n, k and L. Here k represents the number of message bits taken at a time by the encoder, n is the number of encoded bits per message bit and L is the encoder’s memory. The code dimension is therefore represented by (n, k, L)
For the encoder of figure 10.48, the code dimension is given by (2, 1, 2).
10.16.4. Time Domain Approach
The time-domain behavour of a binary convolutional encoder may be defined in terms of n-impulse responses. Let the impulse response of the adder generating x₁, in figure 10.48, be given by, the sequence { } . Similarly, let the sequence { } denote the impulse response of the adder generating x₂ in figure 10.48. These impulse responses are also called as generator sequences of the code.
Let (m₀, m₁, m₂ …) denote the message sequence entering the encoder of figure 10.48 one bit at a time (starting from m₀). The encoder generates two output sequences by performing convolutions on the message sequences will the impulse responses.
The bit sequence x₁, is given by,
equation
Similarly, the other bit sequence x₂, is given by,
equation
Then, these bit sequences are multiplexed with the help of the commutator switch to produce the following output :
X = { …}                             …(10.56)
where              x₁ =  ……
and                              x₂ =  ……
EXAMPLE 10.40. The convolutional encoder of figure 10.49 has the following two generator sequences each of length 3.
( … ) = (1, 1, 1)
            and                              { } = (1, 0, 1)
            Determine the encoded sequence for the following input message:
                                    (m₀, m_l, m₂, m₃, m₄) = (1 0 0 1 1)
diagram
FIGURE 10.49 Convolutional encoder
Solution : The given encoder can be drawn in the standard form as shown in figure 10.50.
diagram
FIGURE 10.50 Given encoder redrawn.
The output sequence may be obtained by using equations (10.54) and (10.55) stated to obtain the bit streams x₁ and x₂.
10.16.5. Transform-Domain Approach
            We know that the convolution in time domain is transformed into the multiplication of Fourier transforms in the frequency domain. We can use this principle in the transform domain approach.
In this process, the first step is to replace each path in the encoder by a polynomial whole coefficients are represented by the respective elements of the impulse response. For example, for the top-adder path in previous example, it is given that,
 
 
and
Therefore, the input top adder output path of the encoder of figure (10.50) can be expressed in terms of the polynomial as under :
G⁽¹⁾(p) = g₀⁽¹⁾ + g₁⁽¹⁾ p + g₂⁽¹⁾ p²                            …(10.57)
Substituting the values we get,
G⁽¹⁾(p) = 1 + p + p²                                              …(10.58)
 
The general expression is given by,
G⁽¹⁾(p) = g₀⁽¹⁾ + g₁⁽¹⁾ p + g₂⁽¹⁾ p²  + … + g_L⁽¹⁾ p^L                 …(10.59)
The variable p denotes a unit delay operation and the power of p defines the number of time units by which the associated bit in the impulse response has been delayd with respect to the first bit i.e., g₀⁽¹⁾.
Similarly the polynomial corresponding to the input-bottom adder-output path for the encoder shown in figure 10.50 is given by,
G⁽²⁾(p) = g₀⁽²⁾ + g₁⁽²⁾ p + g₂⁽²⁾ p²                            …(10.60)
Substituting, g₀⁽²⁾ = 1, g₁⁽²⁾ = 0 and g₂⁽²⁾ = 1 we obtain,
G⁽²⁾(p) = 1 + p²                                                    …(10.61)
The general form of polynomial is given by,
G⁽²⁾(p) = g₀⁽²⁾ + g₁⁽²⁾ p + g₂⁽²⁾ p²  + … + g_L⁽²⁾ p^L      …(10.62)
The polynomial G⁽¹⁾(p) and G(2) (p) of equations (10.58) and (10.61) are called as the generator polynomials of the code.
From the generator polynomials, we can obtain the codeword polynomials as under :
Code word polynomial corresponding to top adder is given by,
x⁽¹⁾ (p) = G⁽¹⁾ p . m(p)                          …(10.63)
where                               m(p) = Message polynomial
and the codeword polynomial corresponding to the bottom adder is given by,
x⁽²⁾ (p) = G⁽²⁾ p . m(p)                          …(10.64)
Once we get the two codeword polynomials, it is possible to obtain the corresponding output sequence by simply using the individual coefficients. This has been illustrated in the following example.
EXAMPLE 10.41. Determine the codeword for the cyclic encoder of figure 10.49 for the message signal (10011), using the transform domain approach. The impulse response of the input top adder output path is (1, 1, 1) and that of the input bottom adder output Path is (1, 0, 1).
Solution : First, let us write the generator polynomial G⁽¹⁾ (p).
The impulse response of the input top adder output path of the convolutional encoder of figure 10.49, Therefore, we have
g₀⁽¹⁾ = 1
g₁⁽¹⁾ = 1
and                                                      g₂⁽¹⁾ = 1
Therefore, the generator polynomial G⁽¹⁾ (p) is given by,
G⁽¹⁾ (p) = g₀⁽¹⁾ + g₁⁽¹⁾ p + g₂⁽¹⁾ p²
or                                 G⁽¹⁾ (p) = 1 + p + p²                                                        …(i)
The given message is (m₀ m₁ m₂ m₃ m₄ = 1 0 0 1 1). Therefore, the message polynomial is given by,
M(p) = m₀ + m₁(p) + m₂p² + m₃p³ + m₄p⁴
or                                 M(p) = 1 + p³ + p⁴                                                                     …(ii)
Now, we find the code word polynomial for the top adder.
x⁽¹⁾(p)   = G⁽¹⁾ (p) . M(P)
x⁽¹⁾ (p) = (1 + p + p²) (1 + p³ + p⁴)
= 1 + p³ + p⁴ + p + p⁴ + p⁵ + p² + p⁵ + p⁶
or                     x⁽¹⁾ (p) = 1 + p + p² + p³ + (1 + 1) p⁴ + (1 + 1) p⁵ + p⁶
or                     x⁽¹⁾ (p) = 1 + p + p² + p³ + p⁶ …. (since addition is Mod-2) …(iii)
The generator polynomial G⁽²⁾ (p)
The impulse response of the input bottom adder output path of convolutional encoder of figure 10.49 is (1, 0, 1). Therefore,
g₀⁽²⁾ = 1, g₁⁽¹⁾ = 0 and g₂⁽²⁾ = 1
Therefore the generator polynomial G⁽²⁾ is given by,
G⁽²⁾(p) = g₀⁽²⁾ + g₁⁽²⁾p + g₂⁽²⁾ p₂
or                     G⁽²⁾(p) =  1 + p²                                                                                                                …(iv)
Codeword polynomial for the bottom adder.
                                                            x⁽²⁾(p) = G⁽²⁾ (p) . M(p)
Substituting equations (ii) and (iv) we get,
x⁽²⁾(p) = (1 + p²) (1 + p³ + p⁴)
or                                             x⁽²⁾(p) = 1 + p² + p³ + p⁴ + p⁵ + p⁶                     …(v)
To obtain the code sequences
The output sequence at the output of the top-adder can be obtained from the corresponding generator polynomial x⁽¹⁾ (p),
x⁽¹⁾(p) = 1 + p + p² + p³ + p⁶ = 1 + p + p² + p³ + 0p⁴ + 0p⁵ + p⁶
Therefore the corresponding code seqeunce is (1 1 1 1 0 0 1)
Similarly the code sequence for the bottom adder can be obtained from its generator polynomial.
x⁽²⁾(p) = 1 + p + p² + p³ + p⁴ + p5 + p6
or                                 x⁽²⁾(p) = 1 + 0p + p² + p³ + p⁴ + p5 + p6
Thus, corresponding code sequence is (1 0 1 1 1 1 1)
Hence, the final code word at the output of the encoder is obtained by multiplexing (interleaving) the two code sequences.
Codeword = 11 10 11 11 01 01 11
Advantage of Transform Domain Approach
Note that the codeword obtained using the time domain approach and the frequency domain approach. It may be observed that we got the same result. But, the computation using transforts domain approach demands less efforts than the time-domain approach.
10.16.6. Graphical Representation for Convolutional Encoding
For the convolutional encoding, there an three different graphical representations that are widely used. They are related to each other. The graphical representations are as under :
(i)         The code tree
(ii)        The code trellis
(iii)       The state diagram.
Let us discuss them one by one.
10.16.7. The code Tree
In this subsection, let us draw the code tree for the (2, 1, 2) cyclic encoder of figure 10.48. We assume that the register has been cleared so that it contains all zeros, when the first message bit m₀ arrives. Therefore, the initial state is m_-2 m_-1 = 00. Now, if m₀ = 0, then, the encoder output are as under :
x₁ = m₀ Å m₁ Å m₂ ….. According to equation 10.50)
If         m₀ = 0, we have
x₁ = 0 Å 0 Å 0 = 0 …..
Also                 x₂ = m₀ Å m₂ = 0 Å 0 = 0
Therefore,        x₁ x₂ = 0 0 ……if m₀ = 0
But, if m₀ = 1, then we have
x₁ = 1 Å 0 Å 0 = 1
and                  x₂ = 1  Å 0 = 1
Therefore         x₁ x₂ = 11 … if m₀ = 1
The code tree has been drawn in figure 10.51. It begins at a branch point on node a which represents the initial state. So, if m₀ = 0 we should take the upper branch from node a to obtain the output 00 and the next state m_-1 m₀ = 00.
diagram
figure 10.51 Code tree for (2, 1, 2) encoder.

Therefore, even this state is labeled as a. But, if m₀ = 1, then we should take the lower branch from a to obtain the output 11 and the next state m₁ m₀ = 01. This state has been labelled as b. The code tree progresses in this manner for each new message bit.
The nodes are labeled with letters a, b, c or d denoting the current state m₂, m₁, and we go up or down from a node depending on the value of m₀. Each branch shows the resulting encoded output x₁ x₂ calculated using equation (10.50). Each branch will terminate at another node which is labelled with the next state. There are 2^j possible branches for the jth massage bit, but the branch pattern begins to repeat at j = 3 since the register length is L + 1 = 3.
The procedure of drawing the code tree has been illustrated in figure 10.52.
diagram
diagram
diagram
FIGURE 10.52 Operation of the (2, 1, 2) encoder and development of code tree.
10.16.8. Code Trellis
Figure 10.53 shows a more compact graphical representation which is popularly known as code trellis. Here, the nodes on the left denote the four possible current states and the nodes on the right are the resulting next state.
diagram
FIGURE 10.53 Code trellis for the (2, 1, 2) convolutional encoder.
A solid line represents the state transition or branch for m₀ = 0 and the dotted line represents the branch for m₀ = 1. Each branch is labelled with the resulting output bits x₁ x_2.
10.16.9. State Diagram
Figure 10.54 shows a state diagram for the encoder of figure 10.50. We can obtain this state diagram from the code trellis, by coalencing the left and right sides of trellis. The self loops at the nodes a and d represent the state transition a-a and d-d.
diagram
FIGURE 10.54 State diagram for the (2, 1, 2) convolutional encoder of figure 10.50.
A solid line represents the state transition for m₀ = 1 and the dotted line represents the state transition for m₀ = 1. Each branch is labelled with the resulting output bits x₁, x₂. If the sequence of Message bits and the initial state is given to us then we can use either the code trellis or state diagram to find the resulting state sequence and output bits. This procedure has been illustrated in figure 10.55 starting at initial state a.
STATE                        a          b          d          c          b          d          d          c
OUTPUT                    11        01        01        00        01        10        01        11
FIGURE 10.55 Procedure to draw the trellis or state diagram.