28-11-2012, 05:33 PM
Sequential Decoding of Convolutional Codes
Sequential Decoding of Convolutional.pdf (Size: 437.01 KB / Downloads: 108)
Abstract
This article surveys many variants of sequential decoding in literature. Rather than introducing
them chronologically, this article ¯rst presents the Algorithm A, a general sequential search algorithm.
The stack algorithm and the Fano algorithm are then described in details. Next, trellis variants of se-
quential decoding, including the recently proposed maximum-likelihood sequential decoding algorithm,
are discussed. Additionally, decoding complexity and error performance of sequential decoding are
investigated, followed by a discussion on the implementation of sequential decoding from various prac-
tical aspects. Moreover, classes of convolutional codes that are particularly appropriate for sequential
decoding are outlined.
Introduction
The convolutional coding technique is designed to reduce the probability of erroneous
transmission over noisy communication channels. The most popular decoding algorithm
for convolutional codes is perhaps the Viterbi algorithm. Although widely adopted in
practice, the Viterbi algorithm su®ers from a high decoding complexity for convolutional
codes with long constraint lengths. While the attainable decoding failure probability of
convolutional codes generally decays exponentially with the code constraint length, the
high complexity of the Viterbi decoder for codes with a long constraint length to some
extent limits the achievable system performance. Nowadays, the Viterbi algorithm is
usually applied to codes with a constraint length no greater than nine.
Convolutional code and its graphical representation
Denote a binary convolutional code by a three-tuple (n; k;m), which corresponds to
an encoder for which n output bits are generated whenever k input bits are received,
and for which the current n outputs are linear combinations of the present k input bits
and the previous m £ k input bits. Because m designates the number of previous k-bit
input blocks that must be memorized in the encoder, m is called the memory order of
the convolutional code. A binary convolutional encoder is conveniently structured as a
mechanism of shift registers and modulo-2 adders, where the output bits are modular-
2 additions of selective shift register contents and present input bits. Then n in the
three-tuple notation is exactly the number of output sequences in the encoder, k is the
number of input sequences (and hence, the encoder consists of k shift registers), and m
is the maximum length of the k shift registers (i.e., if the number of stages of the jth
shift register is Kj , then m = max1·j·k Kj). Figures 1 and 2 exemplify the encoders of
binary (2; 1; 2) and (3; 2; 2) convolutional codes, respectively.
Stack algorithm and its variants
The stack algorithm or the ZJ algorithm was discovered by Zigangirov [5] and later
independently by Jelinek [6] to search a code tree for the optimal codeword. It is exactly
the Algorithm A with g-function equal to the Fano metric and zero h-function. Because
a stack is involved in searching for the optimal codeword, the algorithm is called the
stack algorithm. An example is provided blow to clarify the °ow of the stack algorithm.