Viterbi decoder

Details Viterbi decoder Viterbi decoder

1999-12-15

2002-10-15

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

06467064

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Viterbi decoder for decoding the receive signal series encoded with an error correcting code by the operation of a processor in the method for decoding the error correcting code.
2. Description of the Prior Art
In the fields of communication and information processing, the reliability of communication and information processing, as the case may be, is required to be improved. For this purpose, a technique using “error correcting code” has been proposed to assure correct receipt at the receiving end of the signals transmitted from the transmitting end. In recent years, a high-performance decoding method for the error correcting code has been required. One of the most effective method of decoding the error correcting code is the Viterbi decoding method which is a maximum likelihood decoding method for the receive signal series containing the error correcting code. This method has an especially superior ability of error correction, and therefore has been widely used.
An example of the Viterbi decoding method will be described.
FIG. 22
is a diagram showing an example of the trellis used in the Viterbi decoding method. In the Viterbi decoding method, the maximum likelihood decoding is executed using the trellis shown in FIG.
22
.
In
FIG. 22
, two branches entering each status Sk (k=0, 1, 2, . . . ) each have a value called a branch output. Also, the numerical value described under each status Sk is called a path metric which is the minimum sum of the branch metrics leading to the status Sk.
Assume, for example, that the current time is T
1
. First, in the status S
0
, the branch metric (humming distance) between each of the two branches (branch
0
and branch
1
) entering the status S
0
on the one hand and the receive signal series on the other is calculated.
Once the branch metrics (branch
0
=1, branch
1
=1) of branches
0
,
1
are determined, the path metric of the status S
0
with the branch
0
connected to the time point T
0
one unit time before is used (which is conventionally preserved in a memory equipment), and added to the branch metric of the branch
0
as a value P
1
. Specifically, P
1
=branch metric of branch
0
(=1)+path metric of status S
0
(=2)=3 is determined. In similar fashion, the sum P
2
of the path metric of the status S
2
with the branch
1
connected to T
0
one unit time before and the branch metric of the branch
1
is determined. Specifically, P
2
=branch metric of branch
0
(=1)+path metric of status S
2
(=101)=102 is determined.
Then,
21
and P
2
are compared with each other, the smaller one of them (P
1
=3) is stored as a path metric for the status S
0
at time point T
1
. Also, in
FIG. 22
, the selected branch
0
transfers from the status S
0
one time unit before, and therefore the information bit “0” is input and stored. In the trellis shown in
FIG. 22
, thick solid lines indicate the path selected by the technique mentioned above.
After the forgoing processing has been executed for all the status Sk (k=0, 1, 2, . . . ) and all the time points, assume that the trellis is known to end at the status S
3
at time point T
2
by the negotiation beforehand between the transmitting and receiving ends. The thick surviving path of the trellis traced (called the back trace) toward time point T
0
from the status S
3
at the final time point T
2
. The decoded signal series can be output in the direction reverse to the input, if the bit “0” is output for a thick solid line and “1” for a thick dashed line.
As described above, in the Viterbi decoding method, the code series considered most likely to have been transmitted from the transmitting end is estimated thereby to eliminate the error in the transmission path.
The Viterbi decoder for realizing the Viterbi decoding method described above has already been proposed. The recent trend is toward the Viterbi decoder being configured not simply with hardware but with software (firmware) and a processor. In the case where the Viterbi decoder is realized using software, the processing speed is unavoidably reduced than in hardware, and therefore the amount of operation (processing amount) is required to be reduced. Especially, the maximum likelihood decoding method such as the Viterbi decoding method involves a comparatively large amount of operation, which must be reduced as far as possible.
Fujitsu Ltd. has proposed a Viterbi decoder for realizing the Viterbi decoding scheme with the operation using the processor (Japanese Patent Application Laid-Open No. 7-30438, hereinafter referred to as the prior art). In the prior art, in order to calculate the branch metric, branch metrics corresponding to the receive signal series are held as a table, and upon receipt of the receive signal series, an address is calculated from the receive signal series for accessing the table of the branch metrics. Then the branch metric corresponding to the address is read from the table, thereby reducing the operation amount required for calculating the branch metric.
In the prior art which is configured to read the branch metric from the table by random access, however, the operation for generating an address is required each time the branch metric is read, thereby posing the problem of the long time required for calculation of the branch metric.
Also, the branch metrics held in the table beforehand is so vast in amount that the storage capacity of the memory for storing the table is unavoidably increased.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a Viterbi decoder in which the time required for calculating the branch metric can be shortened and the memory capacity required for the table used to calculate the branch metric can be reduced.
According to a first aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded with an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared in beforehand accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. Each table holds the branch metrics in such a manner that the branch metrics of the two branches entering each status are read by the control unit in the order of the branches constituting the trellis.
According to a second aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for storing a plurality of branch metrics, and a control unit for selecting a surviving path for each status using the branch metrics stored in the storage unit upon receipt of the receive signal series, wherein the storage unit is prepared beforehand in accordance with the pattern of the receive signal series and stores a plurality of tables holding the branch metrics corresponding to each status. In the case where the branch metric of one of the two branches entering a given status can be calculated by the branch metric of the other branch, each table holds only one of the branch metrics. In the case where the branch metric of only one of the two branches entering a given status is read from the table corresponding to the receive signal series, the control unit determines the other branch metric from the particular one branch metric.
For example, assuming that the output values of the two branches entering a given status are codes with bits of inverted signs, each table holds the branch metric of only one of the branches.
According to a third aspect of the invention, there is provided a Viterbi decoder for decoding the receive signal series encoded by an error correcting code, comprising a storage unit for

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-2967318