Fast metric calculation for Viterbi decoder implementation

Details Fast metric calculation for Viterbi decoder implementation Fast metric calculation for Viterbi decoder implementation

1998-07-22

2001-12-25

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S794000, C714S796000, C708S550000

Reexamination Certificate

active

06334202

ABSTRACT:

BACKGROUND
1. Field of the Invention
This invention relates to an apparatus and method for efficiently calculating metrical distances in a Viterbi soft decoder in a communication system, such as a wideband CDMA system in which Viterbi decoding in a base station is used to decode convolutional coded information which is transferred from mobile stations.
2. Discussion of Related Art
The Viterbi algorithm is a well known technique for decoding convolutional codes in communication systems.
FIG. 1
provides an overview of the application of this algorithm in a communications system. As shown there, an input sequence is transformed into a codeword sequence using convolutional encoder
10
. This encoder
10
accepts k-bit blocks of the input sequence and produces a codeword sequence of n-symbol blocks at the same time unit. The ratio R of k
is referred to as the code rate. For instance, in wideband CDMA, two code rates R=1/2 and R=1/3 are typically used. As is well understood in the art, the encoder may be implemented using a shift register, modulo-2 adders and a multiplexer.
The codeword sequence is then modulated by modulator
20
(e.g., using phase, frequency or amplitude modulation), and then transmitted on a communication channel
30
. The channel
30
is subject to noise
40
, such as additive white Gaussian noise (AWGN), causing possible corruption of the transmitted information. The demodulator
50
receives the transmitted information and produces an output r, which may be a discrete (quantized) signal. A hard-decision demodulator makes a firm decision whether a 0 or 1 was transmitted. Alternatively, a soft-decision demodulator demodulates the received information and also provides additional information regarding the confidence level of the demodulated information. This supplements the information provided to the decoder
60
, and thereby improves the performance of the decoder
60
.
The decoder
60
and associated memory
70
implement the Viterbi algorithm. The algorithm itself may be described as a recursive optimal solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process observed in memoryless noise. See, for instance, Forney, “The Viterbi Algorithm,” Proc. IEEE, Vol. 6, March 1973, pp. 268-278. The algorithm finds the shortest path through a trellis given a set of observations. The trellis is a time-indexed state diagram, with each node corresponding to a state at a given discrete time. The lines connecting the nodes in the trellis are called branches, which correspond to transitions from one state to another.
Costs are assigned to the branches connecting the nodes in the trellis. These costs, or metrics, are given by a negative log likelihood function, which is approximated by ∥z−y∥
2
, where z is a signal representative of observed outputs and y is a signal representative of actual outputs for a transition between states. Furthermore, noisy outputs may be quantized into three or four bits, and the branch metrics may be approximated by an absolute difference measure. Note Heller et al., “Viterbi decoding for Satellite and Space Communications,” IEEE Trans. Communication Technology, Vol. CPMM-19, No. 5, October 1971, pp. 835-848. More specifically, the log likelihood function used to determine the metrics can be reduced to a minimum distance measure, such as the Hamming distance. The Hamming distance provides a measure of the number of bits that are different between the symbol that the algorithm observes and the symbol that the encoder should have produced had it followed a given input sequence.
A portion of the trellis for Viterbi decoding is shown in
FIG. 2
for illustration purposes. The two nodes at the left represent two states at a time t, while the two nodes at the right represent two states at a time t+1. As shown there, there are two paths which lead to state 0 at time t+1, e.g., a first path which connects state 0 at time t to state 0 at time t+1, and a second path which connects state 1 at time t to state 0 at time t+1. The paths are associated with codewords of the convolutional encoder. Also, both paths have a metric (or path length) associated therewith, e.g., pd
0
and pd
1
, respectively.
The actual Viterbi algorithm involves recursively performing an add-compare-select procedure, as best understood with reference to FIG.
3
. In the add operation, an accumulated metric m
0
associated with state 0 at time t is added (using adder
80
) to the metric pd
0
associated with the transition from state 0 at time t to state 0 at time t+1. The accumulated metric m
1
associated with state 1 at time t is added (using adder
90
) to the metric pd
1
associated with the transition from state 1 at time t to state 0 at time t+1. The compare module
100
determines whether the output of adder
80
is greater than the output of adder
90
, or vice versa, and the selector
110
selects the smaller accumulated metric. Also, this add-compare-select module outputs an indication of the input path which yielded the smallest accumulated metric.
This procedure is repeated for all states in each trellis step (not shown). Further, the output of the trellis step shown is used as an input for a subsequent trellis step (not shown). For any time t, there are M survivor paths (e.g., paths that are retained for the next trellis stage). When state sequences are very long, it may be necessary to truncate survivors to some manageable length &dgr;, as described in the above-referenced Forney paper. By recursively selecting the shortest paths, the algorithm reconstructs the most likely path through the trellis, which should correspond to the actual transmitted sequence before the signal was corrupted by the noise.
In actual practice, when implementing Viterbi soft decoding, soft input values may be used which comprise 4-bit words. This is because 4 bits are enough to improve the decoder performance by approximately 2 dB in SNR in comparison with hard decision Viterbi decoding. For instance, for a convolutional code rate R=1/3, three soft input words of 4 bits each represent one information bit. The three input words are denoted by r
0
, r
1
and r
2
.
With reference to
FIG. 2
, the metric pd
0
for the 3-word soft input example described above is pd
0
=d(r
0
; 0)+d(r
1
; 0)+d(r
2
;0), and the metric pd
1
=d(r
0
; 1)+d(r
1
; 1)+d(r
2
; 1). The individual operands in these two equations represent the distance between a soft input 4-bit word and two possible codewords. Each codeword relates to a path in the trellis diagram relating to a state out of 2
L
, where L is the constraint length of the code (e.g., here L=9).
The known state of the art is to perform the distance calculations d(r
0
,1), d(r
1
,1), d(r
2
, 1), etc., separately. Further, it is known to perform these computations on 16-bit hardware, such as a signal processor which employs 16-bit arithmetic. This means that, for every calculation using a 4-bit operand, there is a significant portion of the 16-bit digital processor word which is not used, and hence “wasted.” This inefficient use of the 16-bit hardware negatively affects the performance of the decoder because the decoder is not fully exploiting its resources.
One known solution to improve the speed of the algorithm is to perform certain parts of the algorithm in parallel using plural digital signal processing cores. This, however, has the negative consequence of requiring additional hardware, while still not making efficient use of the hardware that is employed.
Accordingly, it is one objective of the present invention to more efficiently employ 16-bit hardware to perform Viterbi processing so as to improve the speed and resource utilization of the Viterbi decoder.
SUMMARY
These and other objectives of the present invention are achieved by packing (i.e., assembling) plural soft input words into an n-bit composite soft input word, and processing this composite soft input word en bloc.
More specifically, the invention

Affiliated with

Also associated with

Rating

Fast metric calculation for Viterbi decoder implementation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast metric calculation for Viterbi decoder implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast metric calculation for Viterbi decoder implementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2576154