Convolutional Codes
Module 5
Block Coding vs. Convolutional Coding
Block Coding:
•Encodes a k-bit message block into an n-bit codeword.
•n−k: Parity-check bits added for redundancy.
•Operates on a block-by-block basis.
•Requires a buffer to store the entire message block before encoding.
When Buffering is Undesirable:
•For serial message inputs (bits arrive one at a time), buffering may not
be practical.
Block Coding vs. Convolutional Coding
Convolutional Coding:
•Preferred for serial message inputs.
•Generates redundant bits through modulo-2 convolutions, eliminating the
need for full-block buffering.
•More suitable for real-time data streams.
Key Difference:
•Block Coding: Processes complete blocks.
•Convolutional Coding: Works with continuous, serial input streams.
Encoder for Binary Convolutional Codes
Key Features of the Encoder:
• Code Rate: 1/n (bits per symbol).
• Operates as a finite-state machine.
• Components:
• M-stage shift register: Stores and shifts bits.
• n modulo-2 adders: Generate redundant bits based on prescribed connections.
• Multiplexer: Serializes the outputs of the adders into a single stream.
Output Characteristics:
• Input: A sequence of L message bits.
• Output: A coded sequence of length n(L+M) bits.
Takeaway:
• The encoder transforms input messages into a structured, redundant output
suitable for error detection and correction.
Encoder for Binary Convolutional Codes
• The code rate is therefore given by
An important characteristic of a convolutional code is its constraint length,
which we define as follows:
The constraint length of a convolutional code, expressed in terms of message
bits, is the number of shifts over which a single incoming message bit can
influence the encoder output.
Convolutional Encoder
• In an encoder with an M-stage shift register, the encoder's memory is
equal to M message bits.
• The constraint length, denoted as K, is M+1, representing the number
of shifts needed for a message bit to pass through the shift register and
influence the output.
• For instance, Figure 10.13 illustrates a convolutional encoder with n =
2 output bits and a constraint length of v=3.
• In this case, the encoder has a code rate of 1/2, meaning each input bit
generates two output bits.
• The encoder processes the message sequence one bit at a time using a
convolution process and is classified as a nonsystematic code because
the original message bits do not directly appear in the output.
Convolutional Encoder
Convolutional Encoder
Each path connecting the output to the input of a convolutional encoder
may be characterized in terms of its impulse response, defined as
follows:
• The impulse response of a particular path in the convolutional encoder
is the response of that path in the encoder to symbol 1 applied to its
input, with each flip-flop in the encoder set initially to the zero state.
Code Tree, Trellis Graph, and State Graph
Graphical Representations of Convolutional Encoders
• Three Equivalent Methods:
• Code Tree
• Trellis Graph
• State Graph
• Graphical Rule:
• Solid Line: Code branch for input bit = 0.
• Dashed Line: Code branch for input bit = 1.
Code Tree
Trellis Graph
State table
• The trellis depicts the evolution of the convolutional encoder’s state
across time.
The Viterbi Algorithm
• The metric for a particular path is defined as the Hamming distance
between the coded sequence represented by that path and the
received sequence.
• The Viterbi algorithm is a maximum-likelihood decoder, which is
optimum for an AWGN channel as well as a binary symmetric channel