Pulse or digital communications – Receivers – Particular pulse demodulator or detector
Reexamination Certificate
1998-12-02
2002-11-19
Tse, Young T. (Department: 2634)
Pulse or digital communications
Receivers
Particular pulse demodulator or detector
C714S795000
Reexamination Certificate
active
06483881
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method of reducing complexity in a trellis decoder which uses trellis decoding that can easily reduce the complexity of the decoder as much as required by reducing the paths itself using the statistics of path metric values and the reliability of the received signal.
2. Art Background
In decoding schemes which use the trellis decoding such as Viterbi decoding, as the complexity of the trellis increases the performance of the decoder increases, but computational complexity of the decoder also increases.
Many studies have revealed that in these schemes almost the same performance can be obtained as the maximum likelihood decoder even though less paths are taken into account than the number of paths which are required in the maximum likelihood decoder.
In these schemes the best A paths are chosen out of total S paths. It takes lot of time, however, to carry out the algorithm of choosing A paths if S gets large. Thus, they may become less effective algorithm than the maximum likelihood decoding scheme.
Prior schemes of reducing complexity are to select a part of paths that exist in the trellis of the code. Reliability of the received bits is usually used to select the part of paths. Alternatively they select arbitrary number of paths having a good path metric value. But no prominent method has been suggested for selecting the part of paths.
Method of sorting values like path metric values has been generally used in the prior schemes. However, as the number of paths to be selected increases, it takes lot of time to carry out the sorting algorithm itself, so it is meaningless to reduce the complexity.
Thus, in the trellis decoding algorithm new scheme is essentially required which can reduce the complexity of the decoder without increase of amount of computations and which can reduce decoding time by setting aside paths almost without chance of being selected, using the statistics of path metric values and the reliability of the received signal.
SUMMARY OF THE INVENTION
It is thus an object of the present invention to provide a method of easily reducing, as much as required, the complexity of a decoder which utilizes trellis decoding without increasing the amount of computations. This is accomplished by reducing the number of paths using the reliability information of the received signal and the statistics (the mean and the standard deviation) of path metric values in a trellis decoder.
The method according to the present invention to achieve the above-mentioned purpose can be applied to a decoder using trellis decoding for reducing complexity and comprises a first step of determining the reliability of bits received at the current level (time stage) after initializing the level of the trellis and a flag, a second step of determining the paths to be taken into account according to the reliability of received bits and computing and storing information about the determined paths, and a third step of obtaining the statistics of path metric value a reference path metric. The third step is performed by utilizing the determined path information at the current level, reducing the number of paths, and moving to the next level when the total number of paths is larger than the maximum number of paths to be maintained.
REFERENCES:
patent: 5151904 (1992-09-01), Reiner et al.
patent: 5208816 (1993-05-01), Seshardi et al.
patent: 5502735 (1996-03-01), Cooper
patent: 5586128 (1996-12-01), Chen
patent: 5588028 (1996-12-01), Parizhsky
patent: 5651032 (1997-07-01), Okita
patent: 5774500 (1998-06-01), Zogakis et al.
patent: 5781569 (1998-07-01), Fossorier et al.
patent: 5944850 (1999-08-01), Chouly et al.
patent: 5970104 (1999-10-01), Zhong et al.
patent: 6199191 (2001-03-01), Iwata
patent: 6205186 (2001-03-01), Butler et al.
patent: 6222889 (2001-04-01), Lee
patent: 6334201 (2001-12-01), Sawaguchi et al.
patent: 6353640 (2002-03-01), Hessel et al.
Stanley J. Simmons, “Breadth-First Trellis Decoding with Adaptive Effort”, IEEE Transactions on Communications, vol. 38, No. 1 Jan. 1990 pp. 3-12.
S.K. Shin et al. “Soft decision decoding of Reed-Solon on codes using trellis methods”, IEE Proc.-Commun., vol. 141, No. 5, Oct. 1994, pp303-308.
K.R. Matis et al. “Reduced-Search Soft-Decision Trellis Decoding of Linear Block Codes”, IEEE Transactions on Information Theory, vol. 11-28, No. 2 Mar. 1982, pp. 349-355.
Kim Soo Young
Lee Soo In
Cohen & Pontani, Lieberman & Pavane
Electronics and Telecommunications Research Institute
Tse Young T.
LandOfFree
Method of reducing complexity using statistics of path... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of reducing complexity using statistics of path..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of reducing complexity using statistics of path... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2933904