Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-05-08
2004-09-14
Dildine, R. Stephen (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S262000, C704S242000
Reexamination Certificate
active
06792570
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Viterbi decoder which has a high speed processing function and low power consumption.
2. Description of the Related Art
A Viterbi decoder has been conventionally used to efficiently carry out the most likely decoding using the repetitive structure of convolution codes. A conventional Viterbi decoder carries out an ACS (add compare select) process in which branch metric data outputted from a branch metric generating section and path metric data read out from a path metric memory section are added to each other, and the addition results are compared with each other so as to select the smaller one as the path metric data. Then, the conventional Viterbi decoder carries out for the number of states, a process in which the path metric data is stored in the path metric memory and path selection data for the selected path metric data is stored in the path memory.
In the above conventional Viterbi decoder, when the ACS process is carried out, it is necessary to read out the path metric data from the path metric memory and to write the calculated path metric data in the path metric memory after the ACS process. Therefore, each of the read operation from the path metric memory and the write operation after the ACS process is carried out twice for one ACS process. In other words, the time sufficient to read two data from the path metric memory is required at the minimum for the one ACS process. Thus, there is a problem that it is not possible to speed up the ACS process any more.
Also, when a RAM is used as the path metric memory for the ACS process, the read operation from the path metric memory is carried out twice and the write operation is carried out twice after the process. Therefore, the number of times of access to the RAM is much so that power consumption is much compared with the processing amount.
In conjunction with the above description, a Viterbi decoding method is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 10-209882). In this reference, a branch metric calculation step, the branch metrics of the branches showing state transition from time n-1 to time n which are discrete are calculated over all of possible combinations of a transfer origin and a transfer destination. In an ACS step, the path metrics remaining at the time n-1 are read out from a path metric memory. The addition values of the read out path metric and the branch metric calculated in the branch metric calculation step are compared between paths to the transition destination for every transition destination. The minimum addition value obtained through the comparison is written into the path metric memory as a remaining path metric at the time n. The above ACS step is carried out in parallel for a plurality of paths to the different states at the time n-1 through the same state at the time n-1. Moreover, the above branch metric calculation step is carried out in parallel for a plurality of branches in which the transition origin is identical and the transition destination is different.
Also, a Viterbi decoder is disclosed in Japanese Laid Open Patent Application (JP-A-Heisei 11-186918). In this reference, a branch metric calculation section stores code words of a trellis chart of convolution coding previously, and inputs demodulation data in units of the coding blocks and calculates a distance between the inputted demodulation data and the code word of the trellis chart to determine a branch metric, and outputs the branch metric corresponding to path data which is branched from each state. The path metric memory section stores the path metric of a remaining path in each state at the time of a decoding operation in the last time, and outputs the path metric in synchronism with the output from the branch metric calculation section. The ACS section adds the branch metric outputted from the branch metric calculation section to the path metric outputted from the path metric memory section to determine updated path metric, compares the path metrics of the two paths which join at an optional state, and selects the path having a higher likelihood as the remaining path, and outputs the path metric and path data for the selected remaining path. A most likely path determining section selects a path having the highest likelihood from among the path metrics for remaining paths outputted from said ACS section in each state as the most likelihood path, and outputs a path number and the path metric of the most likelihood path. The normalizing operation section subtracts the path metric of the most likelihood path outputted from said most likelihood path determining section from the path metric in the remaining path in each state outputted from said ACS section for normalization, and outputs to a path metric memory section. The path memory section sequentially stores the path data of remaining path in each state outputted from said ACS section, and outputs the path data with the oldest path number as the decode data in accordance with the path number of the most likelihood path from said most likelihood path determining section. The ACS section divides the path metrics in each state outputted from the path metric memory section and the branch metrics of each branch outputted from the branch metric calculation section into a plurality of specific groups, converts the path metrics and the branch metrics into a serial sequence for every group, and adds the path metric and the branch metric for two paths which join at an optional state at time division timing to determine updated path metrics, respectively. The two updated path metrics are compared and the path having a higher likelihood is selected as the remaining path. The path metric and the path data for selected remaining path are converted into a parallel sequence for every group and outputted in an identical timing.
Also, a Viterbi decoding apparatus is disclosed in Japanese Patent No. 2,798,123. In this reference, the Viterbi decoding apparatus decodes a reception sequence which is subjected to convolution coding in the most likely manner based on a Viterbi algorithm. The branch metric calculation and normalization section calculates branch metrics and normalizes the calculated branch metrics such that the most likely value becomes the smallest. A branch metric memory section stores the normalized branch metrics outputted from the branch metric calculation and normalization section as a pair. A state metric memory section stores a state metric. An addition, comparison and selection section adds the branch metric pair read out from the branch metric memory section and the state metrics corresponding to the branch metric pair read out from the state metric memory section, respectively, and compares the addition results with each other. Moreover, the addition, comparison and selection section carries out the process for determining the most likely path based on the comparison result in parallel and collectively, and gets a new state metric to update the memory contents of the state metric memory section. The path memory section stores contents of the path obtained by the addition, comparison and selection section. The most likely decode judgment section carries out the decoding operation based on the memory contents of the path memory section. The branch metric memory section is composed of a write address generation section, a read address generation section, a switch and a branch metric output destination switching section. The writing address generation section is composed of a pair of memory sections for previously storing the branch metrics used by the addition, comparison and selection section for the calculation, and previously stores a pair of branch metrics in the same address of the pair of memory section. The read address generation section reads out the pair of branch metrics stored in the same address of the pair of memory sections in parallel. The switch is connected between the write address generation section, the read address generation section and the
Takahashi Hideaki
Yagi Yoshiharu
Dildine R. Stephen
Foley & Lardner LLP
NEC Corporation
LandOfFree
Viterbi decoder with high speed processing function 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 with high speed processing function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoder with high speed processing function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222238