Module 5
Convolution Codes
Recursive Systematic Convolutional Codes
• The convolutional codes described thus far in this section have been
feedforward structures.
• There is another type of linear convolutional codes that are the exact
opposite, being recursive as well as systematic; they are called
recursive systematic convolutional (RSC) codes.
• Figure 10.17 illustrates a simple example of an RSC code, two distinguishing
features of which stand out in the figure:
• 1. The code is systematic, in that the incoming message vector mj at time-unit
j defines the systematic part of the code vector cj at the output of the encoder.
• 2. The code is recursive by virtue of the fact that the other constituent of the
code
• vector, namely the parity-check vector bj, is related to the message vector mj by
the modulo-2 recursive equation
For recursive systematic convolutional codes, the transform-domain matrix
G(D) is easier to use as the code generator than the corresponding time-
domain
matrix G whose entries contain sequences of infinite length.
The same statement applies equally well to the parity-check generator H(D)
compared with its time-domain counterpart H.
A single error in the systematic bits of an RSC code produces an infinite
number of parity-check errors due to the use of feedback in the encoder.
Optimum Decoding of Convolutional Codes
• The first algorithm is the maximum likelihood (ML) decoding
algorithm.
• A distinctive feature of this decoder is that it produces a codeword as output, the
conditional probability of which is always maximized on the assumption that each
codeword in the code is equiprobable.
• In the maximum likelihood decoding of a convolutional code, the metric to be
maximized is the likelihood function of a codeword, expressed as a function of the
noisy channel output.
• The second algorithm is the maximum a posteriori (MAP) probability
decoding algorithm; the decoder is correspondingly referred to as a MAP
decoder.
• In MAP decoding of a convolutional code, the metric to be maximized is the
posterior of a codeword, expressed as the product of the likelihood function of a
given bit and the a priori probability of that bit.
• These two decoding algorithms, optimal in accordance with their own
respective criteria, are distinguished from each other as follows:
• The ML decoding algorithm produces the most likely codeword as its output.
• On the other hand, the MAP decoding algorithm operates on the received
sequence on a bit-by-bit basis to produce the most likely symbol as output.
• The ML decoder minimizes the probability of selecting the wrong codeword,
• whereas the MAP decoder minimizes the decoded BER.
• Typically, the ML decoder is simpler to implement; hence its
popular use in practice.
• However, the MAP decoding algorithm is preferred over the ML
decoding algorithm in the following two situations:
• 1. The information bits are not equally likely.
• 2. Iterative decoding is used in the receiver, in which case the a
priori probabilities of the message bits change from one
iteration to the next;
Maximum Likelihood Decoding of Convolutional
Codes
• The description is best understood by focusing on a trellis that represents each
time step in the decoding process with a separate state graph.
• Let m denote a message vector and c denote the corresponding code
vector applied by the encoder to the input of a discrete memoryless channel.
• Let r denote the received vector, which, in practice, will invariably differ from
the transmitted code vector c due to additive channel noise.
• Given the received vector r, the decoder is required to make an estimate of
the message vector m.
• the decoder may equivalently produce an estimate of the code vector cˆ of the
code vector
• Otherwise, a decoding error is committed in the receiver.
• The decoding rule for choosing the estimate , given the received vector r, is
said to be optimum when the probability of decoding error is minimized.
• For equiprobable messages, the probability of decoding error is minimized if the
estimate is chosen to maximize the log-likelihood function.
• Let P(r|c) denote the conditional probability of receiving r, given that c was sent.
The log-likelihood function equals ln P(r|c), where ln denotes the natural
logarithm.
The maximum likelihood decoder for decision making is described as
follows:
• Choose the estimate for which the log-likelihood function ln P(r|c) is maximum.
• Consider next the special case of a binary symmetric channel. In this case, both
the transmitted code vector c and the received vector r represent binary
sequences of some length N.
• Let ci and ri denote the ith elements of c and r,
• (( (1)
• Suppose also that the received vector r differs from the transmitted code vector c
in exactly d places in the codeword, By definition, the number d is the
Hamming distance between the vectors r and c. Hence, we may rewrite the
log-likelihood function in (1)as follows:
• In general, the probability of an error occurring is low enough for us to
assume p < 1/2. We also recognize that Nln(1 – p) is a constant for all
c.
• Accordingly, we may restate the maximum-likelihood decoding rule for
the binary symmetric channel as follows:
• Choose the estimate cˆ that minimizes the Hamming distance
between the received vector r and the transmitted vector c.
• That is, for the binary symmetric channel, the maximum-likelihood
decoder for a convolutional code reduces to a minimum distance
decoder.
• In such a decoder, the received vector r is compared with each possible
transmitted code vector c, and the particular one closest to r is chosen as
the correct transmitted code vector.
Viterbi Decoding Algorithm