Miscellaneous active electrical nonlinear devices – circuits – and – Specific input to output function – By integrating
Reexamination Certificate
1999-11-05
2001-07-24
Tran, Toan (Department: 2816)
Miscellaneous active electrical nonlinear devices, circuits, and
Specific input to output function
By integrating
C327S336000, C375S262000
Reexamination Certificate
active
06265927
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention is related in general to the field of digital signal processing, and more particularly, to an anti-saturation integrator and method.
BACKGROUND OF THE INVENTION
The Viterbi decoder or the Viterbi decoding algorithm are widely used for efficient coding in digital communication systems. The Viterbi decoder performs maximum likelihood decoding and involves calculating a measure of similarity or distance between the received signal and all the code trellis paths entering each state. The Viterbi algorithm removes trellis paths that are not likely to be candidates for the maximum likelihood choices. Therefore, the Viterbi aims to choose the code word with the maximum likelihood metric or stated another way, the code word with the minimum distance metric. The computation involves accumulating the distance metrics along a path using a perfect integrator.
Referring to
FIG. 1
, a Viterbi decoder circuit or algorithm portion
10
includes distance calculators
12
-
1
,
12
-
2
, to
12
-N which compute the distance or difference of the received symbol from expected symbols
1
through N. The resultant computed distance from each calculator is then summed with the previous sum. The perfect integrator essentially implements an infinite accumulation for an infinite number of bits. Because a realistic implementation has a finite amount of memory and resources, the resultant accumulated sum inevitably overflows which is a condition know as saturation. When saturation occurs, the solution becomes corrupted and useless. Therefore, it is a requirement of every Viterbi decoder or decoding algorithm to protect against saturation.
Conventional anti-saturation solutions check each accumulated sum at each iteration (blocks
20
-
1
,
20
-
2
, and
20
-N) to determine whether the accumulated sum is about to overflow. If yes, the metrics are scaled down by the same value to avoid saturation (blocks
26
-
1
,
26
-
2
, and
26
-N). An alternative conventional method involves scaling or normalizing all metrics for every input symbol so that the most likely metric is always zero. Yet a third conventional method uses floating point implementation rather than fixed point implementation.
All the above-mentioned anti-saturation techniques suffer from several undesirable disadvantages. These conventional methods slow down the computation speed, use more hardware in the implementation, are more costly, and use more power to operate. Further, the floating point implementation is still at risk for saturation albeit at a decrease rate than the fixed point implementation.
SUMMARY OF THE INVENTION
It has been recognized that it is desirable to protect a Viterbi decoder or algorithm from overflow, since such anti-saturation conditions are inevitable in the normal course of operation and would lead to a corrupted output.
In one embodiment of the invention, a perfect integrator emulator includes a first multiplier for multiplying an input with a first constant, K
NEW
, and generating a scaled input, a summer for summing the scaled input with a scaled previous output and generating an accumulated output, a delay adding a predetermined amount of delay to the accumulated output and generating a delayed output, a second multiplier for multiplying the delayed output with a second constant, K
OLD
, and generating the scaled previous output. The constants K
NEW
and K
OLD
are chosen such that the accumulated output does not overflow and the integrity of the viterbi decode function is not compromised.
In another embodiment of the invention, a method for emulating a perfect integrator includes the steps of multiplying an input with a first constant, K
NEW
, and generating a scaled input, summing the scaled input with a previously generated scaled output and generating an accumulated output, adding a predetermined amount of delay to the accumulated output and generating a delayed output, multiplying the delayed output with a second constant, K
OLD
, and generating the scaled previous output, and whereby the constants K
NEW
and K
OLD
are chosen such that the accumulated output does not overflow and the integrity of the viterbi decode function is not compromised.
In yet another embodiment of the invention, an anti-saturation Viterbi decoder having an integrator that includes a first multiplier for multiplying a distance input with a first constant, K
NEW
, and generating a scaled distance input, a summer for summing the scaled distance input with a scaled previous distance output and generating an accumulated distance output, a delay adding a predetermined amount of delay to the accumulated distance output and generating a delayed distance output, a second multiplier for multiplying the delayed distance output with a second constant, K
OLD
, and generating the scaled previous distance output. The constants K
NEW
and K
OLD
are chosen such that the accumulated distance output does not overflow and the integrity of the viterbi decode function is not compromised.
REFERENCES:
patent: 5173924 (1992-12-01), Hiraiwa et al.
patent: 5619154 (1997-04-01), Strolle et al.
patent: 5867531 (1999-02-01), Shiino et al.
Andrew J. Viterbi, Senior Member, IEEE, Convolutional Codes and Their Performance In Communication Systems, IEEE Transactions on Communications Technology, vol. Com-19, No. 5, Oct. 1971, pp. 751-771.
Jerrold A. Heller, Member, IEEE, Irwin Mark Jacobs, Member, IEEE, Viterbi Decoding for Satellite and Space Communication, IEEE Transactions on Communications Technology, vol. Com-19, No. 5, Oct. 1971, pp. 835-848.
Bernard Sklar,Digital Communications Fundamentals and Applications, pp. 333-347.
Baker & Botts L.L.P.
Raytheon Company
Tran Toan
LandOfFree
Anti-saturation integrator and 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 Anti-saturation integrator and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anti-saturation integrator and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558312