Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-01-10
2003-11-25
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000, C714S795000
Reexamination Certificate
active
06654927
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to decoders which decode error correction codes and more particularly to turbo-code decoders.
DISCUSSION OF THE RELATED ART
A turbo encoder produces a sequence of data elements, namely the subsequences of the source data elements and the subsequences of the redundant data elements. The redundant data elements are obtained by a convolution procedure. A part of the redundant data elements may be punctured in accordance with predetermined rules. U.S. Pat. No. 5,446,747 discloses the turbo code structure and is fully incorporated by reference herein.
The method of turbo coding source digital data elements generally comprises the steps of implementing at least two independent and parallel steps of systematic convolution coding, wherein each of the steps takes into account all of the data elements and provides parallel outputs of distinct series of coded data elements; and temporal interleaving of the source data elements to modify their order. The turbo codes may have a block structure and the size of the transmitted block depends upon the interleaver size.
The decoding of turbo codes is performed iteratively. At every iteration, at least one intermediate data element is decoded and using a decoded intermediate element, the next data element to be decoded is estimated. Thus, for each iteration, at least one intermediate data element is obtained by a combination of the received data element with the estimated data element and the obtained intermediate data element is decoded. The data elements are estimated by using a maximum likelihood algorithm such as a modification of the maximum a posteriori (MAP) algorithm or the soft-output Viterbi algorithm (SOVA). The MAP algorithm results in a better estimation than the Viterbi for data of low signal to noise ratio.
The general concepts of iterative turbo decoding utilizing the MAP and SOVA algorithms are disclosed by Bahl et al. in “
Optimal decoding of linear codes for minimizing symbol error rate
,” IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, March 1974; by Pietrobon in “
Implementation and performance of a serial MAP decoder for use in iterative turbo decoder
,” IEEE Int. Symp. Inform. Theory, p. 471. September 1995 and “
Implementation and performance of a turbo/MAP decoder
,” Int. J. Satellite Commun., vol. 16, pp. 23-46, January-February 1998; and by Hagenauer in “
A viterbi algorithm with soft
-
decision outputs and its applications
,” GLOBECOM'89, pp. 47.1.1-47.1.7, November 1989 and these references are fully incorporated by reference herein.
Typically, the iterative process includes usage of the received source data element in each iteration and subtraction of the decoded data element from the estimated data element. Also, an iterative decoder designed for channels with additive white Gauss noise does not work well for channels with correlated noise, for Rayleigh fading channels or for channels described using Gilbert-Elliot model. Mainly, the turbo decoding algorithm is not as effective for real, natural noises as it is for model Gauss noise channel.
Moreover, terminating the iterative process is a problem for the turbo decoding algorithm. Because errors begin to increase or saturate after a certain number of iteration, a greater number of iterations does not necessarily yield the best result. However, the selection of the optimal number of iteration is difficult.
OBJECTIVES OF THE INVENTION
An object of the present invention is to solve at least the problems and disadvantages of the related art.
Accordingly, an object of the present invention is to provide a digital data decoding method with a high corrective capacity.
Another object of the present invention is to improve the quality of the turbo code decoding, particularly for transmission channels with a low signal to noise ratio.
A further object of the present invention is to provide a decoder of relatively easy manufacture and of high performance. Thus, an object of the present invention is to provide a decoding that can be used in a wide variety of applications and that can be implemented based on relatively simple integrated circuits.
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.
To achieve the objects and in accordance with the purposes of the invention, as embodied and broadly described herein, the present invention includes at least two iterative decoding procedures. An output of decoded data is obtained by a combination of decoded data elements from the iterative decoding procedures. Also, weights may be applied during the combination of decoded data elements. Each of the iterative decoding procedures includes consecutive steps from which a decoded data element is estimated. The estimation is performed by one of either a maximum likelihood algorithms such as different modifications of the maximum a posteriori algorithm or the soft-output Viterbi algorithm.
According to the present invention, an intermediate block of estimated data elements to be decoded is re-normalized. At each iteration, the intermediate data elements are multiplied by a scaling factor dependent upon statistical parameters of the decoded element block. The result of this multiplication or re-normalization is a decoded data element used as an input for decoding data elements in the next iteration.
The decoder for the decoding method of the present invention may be designed with cascade of identical modules, where each module corresponds to one iteration. By varying the number of iterations or modules, the quality level of the receiver may be varied. Also, each module performs a computation of the intermediate decoded data element, a computation of the block of data element characteristics, and a calculation of the decoded data element.
The decoding method according to the present invention comprises decoding of received data elements using at least two decoding procedures; comparing the data elements decoded by different decoding procedures; and calculating a weighted sum of the decoded data elements resulting from the decoding procedures. In the decoding method, each decoding procedure includes consequent decoding of received or previously decoded data elements with redundant data elements. The selection and order of redundant data elements to be used in decoding of the received previously decoded data are characteristics of the particular decoding procedure utilized. Also, each procedure further includes temporal interleaving of the decoded data elements, identical to an interleaving in the coding; de-interleaving the data elements by a symmetrical de-interleaving method to the interleaving method; and normalizing the decoded data elements by multiplication with a scalar factor dependent upon a block of decoded element parameters.
REFERENCES:
patent: 5983385 (1999-11-01), Khayrallah et al.
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6161209 (2000-12-01), Moher
patent: 6189123 (2001-02-01), Anders Nystrom et al.
patent: 6192503 (2001-02-01), Chennakeshu et al.
patent: 6202189 (2001-03-01), Hinedi et al.
patent: 6266795 (2001-07-01), Wei
patent: 6292918 (2001-09-01), Sindhushayana et al.
patent: 6349117 (2002-02-01), Rhee
J. Hagenauer, E. Offer, and L. Papke, “Iterative Decoding of Binary Block and Convolutional Codes”, IEEE Transactions on Information Theory, vol. 42, No. 2, pp. 429-445, Mar. 1996.*
K. Gracie, S. Crozier, and A. Hunt, “Performance of a Low-Complexity Turbo Decoder with a Simple Early Stopping Criterion Implemented on a SHARC Processor”, IMSC 99, Proceedings of the Sixth International Mobile Satellite Conference, Ottawa, Ontario, Canad.*
B. Kim and H. S. Lee, “Reduction of the Number of Iterations in Turbo Decoding Using Extrinsic Information”, Procee
Redkov Victor V.
Sall Mikhail A.
Birch & Stewart Kolasch & Birch, LLP
De'cady Albert
LG Electronics Inc.
Torres Joseph D.
LandOfFree
Iterative error-correction for turbo code decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Iterative error-correction for turbo code decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative error-correction for turbo code decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3117837