Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-04-11
2004-01-06
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000, C714S819000
Reexamination Certificate
active
06675342
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention This invention relates generally to iterative turbo decoding, and more particularly to adaptive halting algorithms that reduce computational complexity of iterative turbo decoders.
2. Description of the Prior Art
Turbo code is well known computational tool that was proposed in 1993 and that attracted the attention of researchers and developers, especially in the art of communication engineering. C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon Limit Error-correcting Coding and Decoding: Turbo Codes (I), Proc.ICC '93, pp. 1064-1070, May 1993. The Berrou et al. reference is incorporated by reference herein. A turbo encoder is composed of two recursive systematic convolutional (RSC) encoders and an interleaver to generate the interleaved version of an input information sequence. The interleaved sequence is also encoded using one of the RSC encoders. The resultant turbo code, using parallel concatenation of the two RSC codes, has a substantially large free Hamming distance and therefore provides a powerful error correcting code. The aforesaid Hamming distance can be further improved by employing long interleavers a the expense of larger memory capacity.
FIG. 4
is a simplified block diagram of a parallel-concatenated rate 1/3 turbo encoder. A parallel-concatenated turbo encoder has two or more component encoders in conjunction with one or more interleavers. A component encoder C
1
to create a parity sequence X
1
encodes an input information sequence. The input information sequence is interleaved and then encoded by C
2
to create a second parity sequence X
2
. The information sequence and the two parity sequences are then multiplexed to create a coded sequence.
The foregoing two RSC codes are alternately MAP-decoded in the turbo decoder, and the reliability of the soft output of the MAP decoder is iteratively updated. The sign of the soft output is improved as a decoded output following a sufficient number of iteration steps. The amplitude of the soft output gradually increases during the iteration process. However, the sign generally remains constant after several iteration steps. Thus, it is easy to recognize a decoded output can become error-free in just a few iteration steps for low-noise channels having a channel-decoded bit error rate (BER) as low as 10
−6
. Detection of an error-free decoded sequence can significantly reduce computational complexity since the iteration process can then be halted without requiring further iteration computations.
A transmitted sequence is generally encoded with an error detection code such as the familiar cyclic redundancy check (CRC) code disclosed by S. Lin and D. J. Costello Jr.,
Error Control Coding: Fundamentals and Applications
, Prentice Hall, N.J., 1983, and incorporated herein by reference. The above error-free decoding can then be checked for accuracy at the receiver side using the CRC code; and when error-free decoding is detected during an iteration, the remaining portion of the iteration can either be ignored or completely halted. A. Shibutani, H. Suda, and F. Adachi,
Decoding
-
complexity Reduction On Turbo
-
CRC Concatenated Code in W
-
CDMA Mobile Radio
, Proc IEICE General Conf., B-5-109, vol. 1, pp. 541, March 1999 (in Japanese), and incorporated by reference herein, have shown the effectiveness of the foregoing iterative turbo decoding process.
If a transmitted sequence is not encoded with the CRC code, the foregoing technique of Shibutani et al. cannot be applied however. Even if the transmitted sequence is encoded with the CRC code, the associated receiver decoder must a priori know the generator polynomial of the CRC code and the position of its redundancy check words in the received sequence. This limitation makes the design of the decoder complicated for variable rate data communications.
In J. Hagenauer, E. Offer, and L. Papke, Iterative Decoding of Binary Block and Convolutional Codes, IEEE Trans. Inf. Theory, vol. 42, pp. 429-445, March 1996 and in U.S. Pat. No. 5,761,248, entitled Method and Arrangement for Determining an Adaptive Abort Criterion in Iterative Decoding of Multi-dimensionally Coded Information, by J. Hagenauer and F. Burkert, issued June 1998, both references incorporated herein by reference, Hagenauer et al. have shown implementation of the adaptive halting algorithm without resorting to use of the transmitted CRC code. The adaptive halting algorithm of Hagenauer et al. makes use of the difference sequence between two soft output sequences determined at the iteration step as well as the preceding iteration step and derived at each iteration step. Then the L
2
norm of the difference sequence (cross entropy of the two soft output sequences) is calculated at each iteration step. Once the cross entropy of the two soft output sequences becomes less than a predetermined threshold value, the iteration process is halted. Although the techniques developed by Hagenauer et al. do not require use of the transmitted CRC code, the technique otherwise requires an extra large memory capacity to store the soft output sequence data at each preceding iteration step. This is so since the soft output sequence of a typical turbo decoder is very long and therefore has soft output symbols with long word lengths. Further, the aforementioned cross entropy needs to be computed using high accuracy in order to accurately detect the convergence of iterative decoding, which significantly increases the hardware size of the multiplier used for the calculation of the L
2
norm.
P. Robertson, Illuminating the Structure of Parallel Concatenated Recursive Systematic (TURBO) Codes, Proc. GLOBECOM'94, pp. 1298-1303, November 1994, incorporated by reference herein, proposes application of the adaptive halting algorithm using the variance of the soft output sequence as the halting criterion. Although the Robertson technique does not require an extra large memory capacity or a large multiplier such as required when using the foregoing cross entropy computation methods, the technique of Robertson nonetheless requires additional multiplier hardware to calculate the variance. The requirement for a multiplier is disadvantageous for low power and low-cost silicon implementations since the additional hardware will increase both the size and power requirements necessary to implement the adaptive halting algorithm.
In view of the foregoing, a need exists in the communication art for an adaptive halting structure and method that does not require use of the passively embedded CRC code and that does not require surplusage multipliers or memory capacity.
SUMMARY OF THE INVENTION
The present invention is directed to a structure and method of implementing a direct comparison adaptive halting algorithm and decoder associated with iterative turbo decoding without resorting to use of a passively included CRC code. The soft output sequence observed at each iteration step contains information on three L-valued sequences; the channel information, the a priori information and the extrinsic information. The channel information sequence is constant during the iteration and thus does not have any information on the state of the convergence necessary to halt the iteration process. Thus, the change of the sum of the a priori information and the extrinsic information sequences is observed during each iteration step. The soft output sequence containing the channel information sequence is, however, referred to in order to estimate the state of the convergence, such as disclosed by Hagenauer et al. above. The sum of the a priori information sequence and the extrinsic information sequence contains accurate information on the state of the convergence and thus is quantized into a binary sequence. During an iteration, any changes of the binary sequence are detected. The iteration process is halted once this change can no longer be detected. The foregoing detection at each iteration step can be easily implemented by storing the reference sequence generated by a MAP decoder in each stage of
Baker Stephen M.
Brady W. James
Hoel Carlton H.
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Direct comparison adaptive halting decoder and method of use does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Direct comparison adaptive halting decoder and method of use, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Direct comparison adaptive halting decoder and method of use will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234383