Area-efficient convolutional decoder

Details Area-efficient convolutional decoder Area-efficient convolutional decoder

1998-06-26

2002-11-05

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S796000

Reexamination Certificate

active

06477680

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to digital communication systems, and more particularly to Viterbi decoders and other convolutional decoders for use in such systems.
BACKGROUND OF THE INVENTION
Channel coding is a conventional technique commonly used to increase the robustness of a digital communication system. The principle underlying channel coding is to introduce redundancy and memory into the transmitted bit stream so as to facilitate error detection and correction at the decoder. Two general classes of channel codes are block codes and trellis codes. Block codes operate on a block-by-block basis, such that output code words depend only on the current input block message. Trellis codes, in contrast, may be viewed as mapping one arbitrarily long bit stream into another, with no assumed block structure. A commonly-used linear class of trellis codes are known as convolutional codes. In such codes, output codewords result from the convolution of an input message stream with the impulse response of an encoder which includes a v-stage shift register. A given n-bit code word is generated as a function of m input bits and v bits stored in the shift register. The constraint length K of the encoder is defined as m+v, and the rate of the code is given by m
, where n>m.
A convolutional encoder operates as a finite state machine with a maximum of N=2
v
=2
K−m
possible states. The m input bits cause a transition from a present state, defined by v bits, to the next state, and the number of output bits, i.e., code bits, produced depends on the rate of the code. The transitions from one state to another when viewed as a function of time result in a graph commonly known as a “trellis.”
FIG. 1
shows a trellis diagram for a rate 1/2 convolutional code with a constraint length K=4. This code includes N=2
K−m
or 8 possible states, each corresponding to a group of v=3 bits and designated by one of eight dots in each of an “old state” and “new state” column. The diagram shows all of the possible transitions between a given one of the old states and the new states that can be reached from the given old state. Since m=1 in this example, the encoding process dictates that there can be only two transitions out of a state and two transitions into a state. In general, for m input bits, there are 2
m
transitions out of and into a state. For a code with m=2, there would be four such transitions.
It should be noted that the state assignment shown in
FIG. 1
is arbitrary to some degree. The convention adopted in this example is that the input bit shifts into the least significant bit (LSB) of the shift register while the most significant bit (MSB) shifts out of the register. According to this convention, two states differing in the MSB converge onto the same state when an input is shifted into the LSB. For example, the 0 and 4 states both converge to the 0 state when a 0 is shifted into the register. More generally, two states differing by N/2 in their state assignment converge to the same state under the same input condition. In addition, if a 0 is shifted into the LSB of the register, the new state will be an even state, and conversely, a 1 shifted into the LSB leads to an odd state. Since an upshifting operation is equivalent to multiplication by 2, the process can be generalized by the following transitions: an input 0 causes state j to go to state
2
j
, while an input 1 causes state j to go to
2
j+
1; similarly, an input 0 causes state j+N/2 to go to
2
j
, while an input 1 causes state j+N/2 to go to
2
j+
1. These transitions are illustrated in
FIG. 2
for a rate 1/2 code, and the resulting computational structure is commonly known as a “butterfly.”
The convolutional encoding process can be viewed as tracing a path through the trellis diagram.
FIG. 3
shows one such path traced through an 8-state trellis as a function of time. The vertical axis denotes the state numbers in ascending order, and the horizontal axis represents time. Each stage of the trellis represents a period of time T. Typically, the shift register is initialized to start at the 0 state. For each of the transitions shown in
FIG. 3
, n code bits are generated. Thus, the objective of the corresponding decoding process is to retrace this path through the trellis based on the received code symbols.
FIG. 4
shows all of the possible paths for an 8-stage trellis over a period of 7T. At time T, there are 8 possible paths, at time 2T, there are 16, and so on. Thus, the number of possible paths grows exponentially with time. Note that each path is a particular sequence of transitions from one trellis stage to the next. Hence, a “path metric” for a given path is given by the sum of the individual transition metrics, i.e, “branch metrics.” The decoding process therefore generally involves the steps of: (1) computing branch metrics based on the received code symbols; (2) computing path metrics by summing branch metrics; (3) selecting an optimal path after a certain time; and (4) performing a “traceback” operation along the optimal path to extract the corresponding input bits. In Viterbi decoding, the problem of exponential growth in the number of paths is solved by selecting, at each time step, one of two converging paths. As a result, the number of paths under consideration remains constant with time. This elimination of paths at each time step, i.e., at each trellis stage, is referred to as an add-compare-select (ACS) operation.
FIG. 5
shows the general structure of a conventional Viterbi decoder
10
. The decoder
10
includes a branch metric calculator
12
, a recursive ACS engine
14
, and a traceback unit
16
. Soft symbols are applied via an input buffer
18
to the calculator
12
. The calculator
12
computes the branch metrics associated with all possible transitions for a given stage of the trellis. Regardless of the number of states in the trellis, the number of unique branch metrics for a rate 1
convolutional code is given by 2
n
. That is because for a rate 1
code, there are only 2
n
unique code n-tuples. While there are 2
m
. N branches in the trellis, and with each branch there is associated a particular n-tuple of code bits, there can only be as many unique branch metrics as there are n-tuples. The ACS engine
14
is recursive since the new path metrics depend on the path metrics computed for the previous stage and the branch metrics corresponding to the transitions from the previous stage to the next stage. The output of the ACS engine
14
is supplied to the traceback unit
16
, and the resulting output is buffered in output buffer
20
. A finite-state-machine controller
22
controls the operation of the various elements of the Viterbi decoder
10
.
FIG. 6A
illustrates an exemplary add-compare-select operation in greater detail. Two initial stages, j and J, separated by N/2, converge to a state
2
j
. The accumulated path metric associated with j is given by &Ggr;
j
and that associated with J is given by &Ggr;
j
. The respective branch metrics &lgr;
j0
and &lgr;
j0
, where 0 represents the transition caused by a 0 input, are added to the path metrics &Ggr;
j
and &Ggr;
J
, respectively, and depending on the branch metric calculation process, either the minimum or maximum metric path is selected. For example, the maximum is chosen when the branch metric is proportional to the inner product between a received symbol and the corresponding code symbol. Conversely, the minimum is chosen when the branch metric is proportional to the Euclidean distance between the received and code symbols.
FIG. 6B
shows circuitry for implementing this add-compare-select operation, including adders
30
, a compare unit
32
and a select unit
34
.
FIGS. 7A
,
7
B and
7
C illustrate various conventional architectures for the ACS engine
14
of FIG.
5
.
FIG. 7A
shows a state-serial architecture which includes an ACS unit
40
and a state metric (i.e., path metric) random access memory (RAM)
42
. An ACS

Affiliated with

Also associated with

Rating

Area-efficient convolutional decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Area-efficient convolutional decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Area-efficient convolutional decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2915440