Viterbi decoder

Details Viterbi decoder Viterbi decoder

1998-06-03

2001-10-16

Pham, Chi (Department: 2631)

Pulse or digital communications

Receivers

Particular pulse demodulator or detector

C375S262000, C714S795000

Reexamination Certificate

active

06304617

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to a viterbi decoder employed for maximum likelihood decoding of convolutional codes.
Multipath phasing occurring in radio communication such as mobile communications and satellite communications caused by obstructions such as buildings results in a different code sequence received at the reception side from the code sequence transmitted by the transmission side. If such an error in code transmission occurs in, for instance, voice encoding, the quality of reproduced sound at the reception side will be greatly degraded, necessitating appropriate error correction.
Convolutional codes, which can be decoded to achieve a result that is the maximum likelihood or close to the maximum likelihood through viterbi decoding, are effective codes for use in a communication path such as a radio line, in which the error rate in transmitted code is high.
FIG. 17
presents an example of an encoder that performs convolutional encoding at an encoding rate R=½ with a constraint length of K=3.
In this convolutional encoder
101
, three bits including the most recent one bit input are stored at a buffer
103
and through convolutional encoding, an output of two bits is achieved. One of the two bits thus output represents the results of calculation performed by an exclusive OR gate (not shown) on all the bits in the buffer
103
, whereas the other one bit indicates the results of calculation performed by another exclusive OR gate (not shown) on the first and third bits in the buffer
103
.
FIG. 18
presents a trellis chart achieved by rendering the generating conventions of convolutional encoding performed by the convolutional encoder
101
into a state transition diagram. In this trellis chart
111
, time points “t” corresponding to instances of convolutional encoding are indicated in the horizontal direction and the states of the encode word are indicated in the vertical direction. In addition, the number of states, which is determined by the constraint length K=m+1, is expressed as 2
m
. Consequently, the number of states in this diagram is 4, which corresponds to states S
0
-S
3
, as shown in FIG.
18
.
In viterbi decoding, maximum likelihood decoding is performed by determining the metric for each of the states S
0
-S
3
at the individual time points “t” in the trellis chart
111
, and this decoding may be realized by employing a viterbi decoder
121
illustrated in FIG.
19
.
The following is an explanation of the operation of the viterbi decoder
121
. First, a reception sequence Y is input to a branch metric calculating unit (hereafter referred to as a “BMG”)
123
. As shown in the trellis chart
111
, there are two paths (hereafter referred to as “branches”) through which input is performed for each of the states S
0
-S
3
, and the BMG
123
calculates metrics for all the branches. A path selection unit (hereafter referred to as an “ACS”)
125
compares the sums of the accumulated totals (path metrics) of the branch metrics at the states S
0
-S
3
at the time point t−1 immediately before the branches become linked and their branch metrics for two input branches for each of the states S
0
-S
3
at a time point “t” and selects the one that is more likely, to assign it as a new path metric at each of the states S
0
-S
3
. Thus, for each branch that is to link with each of the states S
0
-S
3
, information on the path reaching each of the states S
0
-S
3
is stored in a path memory unit (hereafter referred to as a“PMEM”)
127
and a decode sequence W is output with specific timing.
Now, in order to achieve maximum likelihood decoding in the strict sense by employing the viterbi decoder
121
, it is necessary that the viterbi decoding continue until the reception sequence Y is completed. However, since the reception sequence Y is normally quite long, a tremendous memory capacity is required in the PMEM
127
and an excessive length of time is required for the decoding.
It has been learned through experience that under normal circumstances, as long as an encode sequence length that is 5-6 times the constraint length K is assured, decoding that is extremely close to maximum likelihood decoding in the strictest sense is possible with a viterbi decoder. Based upon this finding, the truncation encode sequence length of the convolutional encoder
101
with a constraint length K=3, i.e., the number of truncations T, is set at T=18 in correspondence to the time points t=0-17, as illustrated in FIG.
18
. The memory capacity of the PMEM
127
in the viterbi decoder
121
is determined in correspondence to the truncations T=18.
As illustrated in
FIG. 20
, the PMEM
127
in the prior art is constituted of unit path memories
131
, the number of which that are be connected corresponds to the product of the number of states S
0
-S
3
and the number of stages of the truncations T. In addition, the unit path memories
131
are each constituted of a selector
133
and a shift register
135
, and store in memory the results of the selections of the maximum likelihood paths at states S
0
-S
3
at the time points t=0-17.
Furthermore, the soft decision making system, in which the reception sequence Y is handled as input data having a bit-width of several bits, is often adopted in viterbi decoders in order to enhance their error correction capabilities. By adopting this method, since the input data are repeatedly added in correspondence to the encoding rate R during the branch metric calculation performed by the BMG
123
, the bit-width of the data obtained as a result of the calculation increases in correspondence to the bit-width of the input data. Since the ACS
125
repeats state metric calculation and state transition a plurality of times, based upon the data obtained through the branch metric calculation performed at the BMG
123
, the calculation bit-width at the ACS
125
will exhibit some spreading.
Since the total ratio of the areas occupied by the BMG and the ACS in the entire viterbi decoder sometimes reaches 40% under specific conditions, reducing the ACS circuit scale will directly lead to a reduction in the scale of the viterbi decoder. Thus, in the prior art, the ACS is made to perform processing such as simultaneous subtraction of state metric values in order to avoid an overflow or an underflow in the calculation, to ensure that the circuit scale does not become excessively large.
Normally, an ACS is provided with ACS circuits that perform state metric calculation for the individual states, and the ACS
125
is provided with four ACS circuits
201
, one of which is illustrated in FIG.
21
. While the number of the adders, comparators, selectors and the like constituting each ACS circuit
201
increases in correspondence to the calculation bit-width explained above, the increase in the calculation bit-width does not result in a large increase in the circuit scale of the ACS
125
as long as the number of ACS circuits
201
is kept down to four or so. However, if the constraint length is increased from K=3 to K=9 in order to improve the error code capability, the number of ACS circuits
201
increases in an exponential function from 4 to 256, resulting in an increase in the scale of the ACS
125
and, ultimately, an increase in the scale of the entire viterbi decoder
121
. In the prior art, this problem is handled by providing circuits
125
in a quantity representing 1/N of the number of states and by repeating the calculation of state metrics at the ACS circuits
125
N times, i. e., by performing the calculations using time sharing.
SUMMARY OF THE INVENTION
However, the following objects are yet to be fulfilled by the viterbi decoder
121
in the prior art, with respect to the increase in the circuit scale and with respect to the decoding processing speed.
First Object
When setting the constraint length K at a large value in order to improve the error correction capability, it is necessary to increase the number of the unit path memories
131
in corre

Affiliated with

Also associated with

Rating

Viterbi 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 Viterbi decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2592758