Processing of state histories in Viterbi decoding

Details Processing of state histories in Viterbi decoding Processing of state histories in Viterbi decoding

1999-06-01

2002-10-01

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06460161

ABSTRACT:

FIELD OF THE INVENTION
The invention generally relates to error-correction coding or more particularly, the invention relates to history handling for Viterbi decoding.
BACKGROUND
Viterbi decoding of convolutionally encoded messages is a common error-control method in the field of digital communications systems, and is well known in the art as described in U.S. Pat. No. 5,742,621, and Motorola Application Report APR40/D, revision 0, May 1998. Software based Viterbi decodes are commonly used in digital communication systems due to the availability of low cost, high performance digital signal processors (DSPs). In conventional software implementations the handling of the history, associated with the decoding path, amounts to a substantial potential of the Viterbi decoder processing time. It is common in the art to have a collection of history bits associated with each state, and a comparison/selection operation, which includes the setting of history bit, for each state, as a method of handling the history.
FIG. 1
depicts a common rate ½, constraint length K=7, binary convolutional encoder, using a shift register with K−1=6 memory elements. This encoder has N=2
K−1
=2
6
=64 states. For every input data bit, d(i) two coded bits, c
1
(i) and c
2
(i), are generated. The encoder is a state machine whose state is [d(i−(k−2)), . . . , d(i−1), d(i)] at time i, and has generator polynomials g
1
=[1011011]
2
and g
2
=[1111001]
2
. The generator polynomials specify how delayed versions of the input are added up (modulo-2) to produce each output. Each binary digit (bit) of the generator polynomial corresponds to a tap on the shift register, or a tap on the input data bit. The output of the encoder is determined by the generator polynomials (as well as the state of the encoder and the input data bit), but the state transitions are independent of the polynomials, and depend only on the current state and the input data bit.
In the Viterbi algorithm (VA), both a state history H
n
(i) and a state metric M
n
(i) are associated with each state n, at time i. There is an associated branch metric B
nm
(i) for each valid transition from state m to state n. In the particular example where K=7, states
0
(000000) and
32
(100000) can both go to either state
0
(000000) or state
1
(000001), depending on the input data bit. No other state transitions from states
0
and
32
are possible. The state metrics and the state histories are updated as follows:
M
n
(f)=max/m[M
m
(i−1)+B
nm
(i)]  (1)
H
n
(i)=[H
n
(i−1), LSB(n)], m=best old state   (2)
These two equations referred to as the add-compare-select (ACS) operation, and the application of the add-compare select operation to all states at a given time is considered as one Viterbi advance.
The application of one Viterbi advance is represented in FIG.
3
. In this case the memory of the convolutional encoder is 2, and hence there are 4 states. In conventional software VA implementations, two buffers are required. Each buffer must be capable of holding a full set of state metrics and histories: one for the previous, or “old” data, and one for the updated, or “new” data. After new data is obtained the new data is used as the old data for a subsequent Viterbi advance.
In determining the new state history for a state, as in equation (2), the prior are method of history handling inserts the least significant bit of the state number of the new state into the state history. This is a critical aspect of prior art history handling, where a history bit has to be inserted each time a new history is generated.
History handling consumes a considerable portion of the processing resources in a typical Viterbi decoder implementation. There is, therefore, a need to reduce the complexity of the history handling to permit more practical and economical implementation of a Viterbi decoder.
SUMMARY OF THE INVENTION
An object of this invention is to provide an improved method of history handling for Viterbi decoders that reduces the processing time required to decode a convolutionally encoded message relative to conventional methods.
Therefore, in accordance with an aspect of the present invention, there is provided a method of processing the state histories within a Viterbi decoder, which receives a sequence of samples, representing a sequence of encoded data bits from a convolutional encoder having N states, and a memory size of K−1 bits, where K≦2, N=2
K−1
, and each state is uniquely identified by a sequence of K−1 state bits, which corresponds to K−1 data bits entered into the encoder. The method provided by the invention comprises the following steps. The first step is to define an initial state metric and an initial state history for each state. The second step is, for each state, insert, into the initial state history, L contiguous state bits that correspond to the L data bits first entered into the encoder, where 1≦L≦K−1. The third step is to designate the initial state metrics and the initial state histories as previous state metrics and previous state histories respectively. The fourth step is to determine at least one branch metric, using no less than one of the samples received by the decoder. The fifth step in the process is to use the branch metric, or metrics, determined in the fourth step, to determine N new state metrics and N new state histories from the previous state metrics and the previous state histories, where each new state history is a copy of a previous state history. Upon reaching this point the decoding continues by repeating the fourth and fifth steps L−1 times, wherein the new state metrics and the new state histories become previous state metrics and the previous state histories, respectively, for subsequent repetitions of the fourth and fifth steps. Preferably L=K−1. In an embodiment of the invention, at least one bit of the state history is present in at least one bit of the least significant bits of a storage word storing the state metric.
In accordance with another aspect of the present invention there is provided a state history processor within a Viterbi decoder that receives and decodes a sequence of samples representing a sequence of encoded bits obtained from encoding a sequence of data bits with a convolutional encoder having N states and a memory size of K−1 bits, where K≧2, N=2
K−1
, and each state is uniquely identified by a sequence of K−1 state bits corresponding to K−1 data bits entered into the encoder, the previously mentioned processing being comprised of five elements. The first element is a set of N first buffers corresponding to the N states, where each first buffer is used for storing a previous history and a previous metric. The second element is a set of N second buffers corresponding to the N states, where each second buffer is used for storing a new history and a new metric. The third element is a means for determining an initial state metric and an initial state, for each state, that is to be stored in the corresponding second buffer. The fourth element is a means for inserting into each new history L contiguous state bits that correspond to L data bits first entered into the encoder, where L is at least one and at most K−1. The fifth element is a means for performing L advances, with each advance consisting of the following steps. Firstly, the first and second buffers' designations are interchanged. Secondly, at least one branch metric is determined using at least one of the samples received by the decoder. Thirdly, N new state metrics and N new state histories are determined from the previous state metrics and the previous state histories, by using the at least one branch metric, wherein each new state history is a copy of one previous state history. Fourth, and finally, the N new state metrics and the N

Affiliated with

Also associated with

Rating

Processing of state histories in Viterbi decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Processing of state histories in Viterbi decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing of state histories in Viterbi decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2968034