Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-12-17
2003-11-18
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06651215
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a Viterbi decoding apparatus and a Viterbi decoding method which is used in a maximum likelihood decoding method of a convolution code that is used in, for example, a satellite broadcasting or the like.
2. Description of the Related Art
As a method of decoding a convolution code, a Viterbi decoding method has been known. The Viterbi decoding method is a maximum likelihood decoding method for the convolution code, and by selecting a series that is the closest to a received code series (hereinafter, such a series is referred to as a maximum likelihood path) among a code series which can be formed from an encoder on the transmission side, an error correction is performed. That is, a transition diagram (hereinafter, referred to as a trellis) which is formed on the basis of an encoding method by the encoder on the transmission side is used as a prerequisite and, for example, a path whose Hamming distance from the received code series is the shortest is selected as a maximum likelihood path from transitions which can occur on the transition diagram.
A Viterbi decoding apparatus for performing a Viterbi decoding method comprises: a branch metric calculating circuit for calculating a branch metric, namely, a Hamming distance between a path which reaches each state on the trellis and the received code series in accordance with a clock; an ACS circuit for calculating state metrics on the basis of the branch metric, comparing values of the state metrics, and selecting a maximum likelihood path; a normalizing circuit for normalizing the values of the state metrics; a state metric storing circuit for storing the values of the state metrics; and a path memory circuit for forming decoding data in accordance with a selection result by the ACS.
As a path memory circuit, there are two kinds of circuits: namely, a circuit for performing a register exchange method for transferring the path selection contents by using a register train; and a circuit for performing a method of storing the path selection contents by using RAMs, tracing the stored contents, and decoding. Those two kinds of methods will now be described hereinbelow.
In the register exchange method which is generally used in a Viterbi decoding apparatus, memory cells each comprising a selector and a register are arranged on the trellis in the path memory circuit and the contents in the register are transferred on the basis of the path selection information that is outputted from the ACS circuit. An example of a construction of the memory cell is shown in FIG.
1
. An example of an arrangement of memory cells in the case where a restriction length=3 is shown in
FIG. 2
(in
FIG. 2
, the memory cell is shown as MS). With such a construction, information corresponding to a survival path from each state is preserved in the register of each memory cell. The registers of the number of stages corresponding to a traceback depth are arranged using the memory cells. Among outputs at the final stages, the output of the maximum likelihood state is selected, thereby selecting the information for the maximum likelihood path and outputting decoding data.
Although such a register exchange method has an advantage such that the high speed operation can be performed, there is a drawback such that a circuit scale is extremely large as the trace back depth becomes long. Particularly, since an application such that the traceback depth exceeds 100 also has appeared in recent years, the enlargement of the circuit scale becomes a serious problem.
In recent years, the method of decoding by storing path information by using RAMS (Random Access Memories) as many as the traceback depth and tracing the stored information has actively been studied. Such a method is called a trace-back method hereinbelow.
According to the trace-back method, a path memory circuit whose circuit scale is fairly smaller than that of the register exchange method can be constructed. However, in the conventional apparatus for performing the trace-back method, the path memory circuit still has a large circuit scale.
The invention has been proposed in consideration of such a situation. It is, therefore, an object of the invention to provide a Viterbi decoding apparatus and a Viterbi decoding method in which a circuit scale is small and a high speed operation can be performed.
SUMMARY OF THE INVENTION
The invention is a Viterbi decoding apparatus which has a path memory for storing selection information of a path in each transition state of a convolution code by using a rewritable memory and traces the information held in the path memory by an amount corresponding to a trace-back depth, thereby performing a Viterbi decoding, wherein a plurality of rewritable memories and memory control means for controlling accesses to the plurality of rewritable memories are comprised, and tracing operations as many as a plurality of times for a period of time of one clock and decoding are performed.
Further the invention is a Viterbi decoding method of storing selection information of a path in each transition state of a convolution code and tracing the stored information by an amount corresponding to a traceback depth, thereby performing a Viterbi decoding, comprising a tracing step of performing tracing operations as many as a plurality of times for a period of time of one clock, using a plurality of rewritable memories provided in a path memory.
According to the invention as mentioned above, by performing the decoding by executing the tracing operation as many as a plurality of times for the period of time of one clock, the total number of words in the RAM can be reduced.
When the path selection information is written, it is sequentially written into a plurality of rewritable memories. Upon tracing, by sequentially reading out the information from the plurality of memories and performing the tracing operation as many as the plurality of times, the tracing operation as many as the plurality of times can be performed while setting the number of times of access to each memory for each clock to one time.
Further, among the outputs of the plurality of memories, the information of the state having a possibility such that it is traced is preliminarily selected on the basis of the trace starting state and the tracing operation is executed with regard to the selected information of the state. Thus, even if the tracing operation as many as the plurality of times is executed, an increase in delay can be minimized.
The above, and other, objects, features and advantage of the present invention will become readily apparent from the following detailed description thereof which is to be read in connection with the accompanying drawings.
REFERENCES:
patent: 4905317 (1990-02-01), Suzuki et al.
patent: 5712880 (1998-01-01), Rim et al.
patent: 5822341 (1998-10-01), Winterrowd et al.
patent: 0 798 867 (1997-10-01), None
Feygin et al., “Architectural Tradeoffs for Survivor Sequence Memory Management in Viterbi Decoders”, IEEE Transactions on Communications, vol. 41, No. 3, Mar. 1993, pp. 425-429.*
Feygin et al., “A VLSI Implementation of a Cascade Viterbi with Traceback”, ISCAS '93, pp. 1945-1948, May 1993.*
Rim et al., “Memory Mangement in High-Speed Viterbi Decoders”, Workshop on VLSI Signal Processing, VIII, pp. 511-520, Sep. 1995.*
Joeressen et al., “Viterbi Decoding with Dual Timescale Traceback Processing”, PIMRC '95, pp. 213-217, Sep. 1995.*
Horwitz et al., “A Generalized Design Technique for Traceback Survivor Memory Management in Viterbi Decoders”, COMSIG '97, pp. 63-68, Sep. 1997.*
“Architectural Tradeoffs for Survivor Sequence Memory Management in Viterbi Decoders”, 8089 IEEE Transactions on Communications 41(Mar.1993), No. 3, New York, by Gennady Feygin and P.G. Gulak, Jul. 26, 1993, p. 425-429.
“An Area-Efficient Path Memory Structure for VLSI Implementation of High Speed Viterbi Decoders”, 8220 Integration, the VLSI Journal 12(Nov.1991), No. 1, Amsterdam, NL, p. 79-91.
Hattori Masayuki
Miyauchi Toshiyuki
Baker Stephen M.
Sonnenschein Nath & Rosenthal LLP
Sony Corporation
LandOfFree
Viterbi decoding apparatus and viterbi decoding method 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 decoding apparatus and viterbi decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding apparatus and viterbi decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158325