Modular turbo decoder for expanded code word length

Details Modular turbo decoder for expanded code word length Modular turbo decoder for expanded code word length

2000-04-28

2003-07-15

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S780000, C714S794000

Reexamination Certificate

active

06594792

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates generally to error-correction coding and, more particularly, to a decoder for parallel convolutional codes, i.e., turbo codes.
A new class of forward error control codes, referred to as turbo codes, offers significant coding gain for power limited communication channels. Turbo codes are generated using two or more recursive systematic encoders operating on different orderings of the same information bits. A subset of the code bits generated by each encoder is transmitted in order to maintain bandwidth efficiency. Turbo decoding involves an iterative algorithm in which probability estimates of the information bits that are calculated for one of the received component code words are fed back to a probability estimator comprising the decoder component code words for the other component code words. Each iteration of decoder processing generally increases the reliability of these probability estimates. This process continues, cyclically decoding the component code words until the probability estimates can be used to make reliable decisions.
The maximum a posteriori (MAP) type algorithm introduced by Bahl, Cocke, Jelinek, and Raviv in “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”,
IEEE Transactions on Information Theory
, March 1974, pp. 284-287, is particularly useful as a component decoder in decoding parallel concatenated convolutional codes, i.e., turbo codes. The MAP algorithm is used in the turbo decoder to generate a posteriori probability estimates of the information bits that have been encoded into the code word. These probability estimates are used as a priori bit probabilities for the second MAP decoder. Three fundamental terms in the MAP algorithm are the forward and backward state probability functions (the alpha and beta functions, respectively) and the a posteriori transition probabilities (the sigma functions).
A known characteristic of turbo codes is that their error correction capability increases with code word length. However, there is some practical limit on the length of a code word that can be decoded with a MAP-algorithm decoder implementation. Accordingly, it is desirable to provide a modular turbo decoder structure capable of decoding longer code word lengths. It is furthermore desirable to provide such a turbo decoder while increasing coding gain and data rate.
BRIEF SUMMARY OF THE INVENTION
A turbo decoder system utilizing a MAP decoding algorithm comprises a predetermined number M of turbo decoder modules for decoding segments of a turbo code component code word in parallel, thereby expanding the block-length and data-rate capability of the turbo decoder system. In an exemplary system, each turbo decoder module has a predetermined maximum code-word size corresponding to N information bits, and a predetermined maximum decoding rate. Input data samples from a received code word, corresponding to M·N information bits, are provided to an interleaver/de-interleaver module wherein they are divided into segments of predetermined size, each segment being provided to a respective turbo decoder module. The output of each turbo decoder module comprises a posteriori probabilities which are re-ordered in the interleaver/de-interleaver module, segmented, and provided back to the turbo decoders as a priori information bit probabilities. For the case of a turbo code comprising two component codes, the a posteriori information-bit probabilities are re-ordered according to the interleaver definition at the end of odd-numbered half iterations, while at the end of even-numbered half iterations, they are re-ordered according to the de-interleaver definition. Decoding continues until the desired number of iterations have been performed. Then, data decisions are made on the final a posteriori bit probability estimates.


REFERENCES:
patent: RE32905 (1989-04-01), Baran
patent: 5349589 (1994-09-01), Chennakeshu et al.
patent: 5406570 (1995-04-01), Berrou et al.
patent: 5446747 (1995-08-01), Berrou
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5721746 (1998-02-01), Hladik et al.
patent: 5734962 (1998-03-01), Hladik et al.
patent: 6252917 (2001-06-01), Freeman
patent: 6271772 (2001-08-01), Luschi et al.
patent: 6484283 (2002-11-01), Stephen et al.
patent: 0 735 696 (1996-10-01), None
patent: 2 675 970 (1992-10-01), None
“Turbo Code Decoder with Controlled Probability Estimate Feedback,” JAF Ross; SM Hladik; NA VanStralen, JB Anderson, Ser. No. 09/137,257, filed Aug. 20, 1998.
“Turbo Code Decoder with Modified Systematic Symbol Transition Probabilities,” SM Hladik; JAF Ross; NA VanStralen; Ser. No. 09/137,256, filed Aug. 20, 1998.
“A Maximum a Posteriori Estimator with a Fast Sigma Calculator,” JAF Ross; AM Itani; NA VanStralen; SM Hladik; Ser. No. 09/137,260, filed Aug. 20, 1998.
“High-Data Rate Maximum a Posteriori Decoder for Segmented Trellis Code Words,” SM Hladik; NA VanStralen; JAF Ross; Ser. No. 09/137,181, filed Aug. 20, 1998.
“Turbo Decoder Control for Use with a Programmable Interleaver, Variable Block Length, and Multiple Code Rates,” NA VanStralen; SM Hladik; AM Itani; RG Wodnicki; JAF Ross; Ser. No. 09/519,903, filed Mar. 7, 2000.
“Turbo Decoder with Modified Input for Increased Code Word Length And Data Rate,” SM Hladik; AM Itani; NA VanStralen; RG Wodnicki; JAF Ross; Ser. No. 09/561,334, filed Apr. 28, 2000.
“The Turbo Coding Scheme,” Jakob Dahl Anderson, Report IT-146 ISSN 0105-854, Jun. 1994, Revised Dec. 1994, pp. 1-48.
“An Efficient Adaptive Circular Viterbi Algorithm for Decoding Generalized Tailbiting Convolutional Codes,” Richard V. Cox, Car-Erik W. Sundberg; IEEE Transactions on Vehicular Technology, vol. 43, No. 1, Feb. 1994, pp. 57-68.
“On Tail Biting Convolutional Codes,” Howard H. Ma; Jack K. Wolf, IEEE Transactions on Communications, vol. Com-34, No. 2, Feb., 1990, pp. 104-111.
“An Efficient Maximum Likelihood Decoding Algorithm For Generalized Tailbiting Convolutional Codes Including Quasicyclic Codes,” Qiang Wang and Vijay K. Bhargava, IEEE Transactions on Communications, vol. 37, No. 8, Aug. 1989, pp. 875-879.
“Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes,” Patrick Robertson, IEEE, 1994, pp. 1298-1303.
“Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes (1),” Claude Berrou, Alain Glavieux, Punya Thitimajshima, IEEE, 1993, pp. 1064-1070.
“Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” LR Bahl; J Cocke; F. Jelinek; J. Raviv; IEEE Transactions on Information Theory, Mar. 1974, pp. 284-287.
“Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,” Claude Berrou; IEEE Transactions on Communications, vol. 44, No. 10, Oct. 1996, pp. 1261-1271.
“A Comparison of Optimal and Sub-Optimal Map Decoding Algorithms Operating in the Log Domain,” Patrick Robertson; Emmanuelle Villebrun; Peter Hoeher; IEEE 1995, pp. 1009-1013.
“Terminating the Trellis of Turbo-Codes in the Same State,” AS Barbulescu; SS Pietrobon, Electronics Letters Jan. 5, 1995 vol. 31, No. 1, pp. 22-23.
“Terminating the Trellis of Tubo-Codes,” O. Joerssen; H. Meyr; Electronics Letters Aug. 4, 1994 vol. 30, No. 16, pp. 1285-1286.
“A Viterbi Algorithm with Soft-Decision Outputs and its Applications,” Joachim Hagenauer; Peter Hoeher; IEEE 1989, pp. 1680-1686.
“Decision Depths of Convolutional Codes,” John B. Anderson; Kumar Balachandran; IEEE Transactions on Information Theory, vol. 35, No. 2, Mar. 1989, pp. 455-459.
“Source and Channel Coding, an Algorithmic Approach,” John B. Anderson; Seshadri Mohan, pp. 216, 336-342.

Affiliated with

Also associated with

Rating

Modular turbo decoder for expanded code word length does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Modular turbo decoder for expanded code word length, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular turbo decoder for expanded code word length will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3084168