Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-07
2003-02-04
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S786000
Reexamination Certificate
active
06516437
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 recursive systematic encoders operating on different orderings of the same information bits. A subset of the code bits of 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 derived for one of the codes are fed back to a probability estimator for the other code. Each iteration of processing generally increases the reliability of the probability estimates. This process continues, alternately decoding the two 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 Infonnation 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 systematic bits in the code word. These probability estimates are used as a priori symbol 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 function).
It is desirable to provide a control and data handling structure for a turbo decoder which allows for a programmable interleaver, variable block length, and multiple code rates.
BRIEF SUMMARY OF THE INVENTION
A control for a turbo decoder utilizing a MAP decoding algorithm comprises an address generator for addressing systematic data symbols, parity data symbols, and systematic likelihood ratios according to a pre-determined memory mapping. A control signal indicates which of a plurality of component code words comprising a turbo code word is being decoded, each employing the same memory mapping. The systematic data symbol values are accessed in the order required by the alpha, beta and gamma functions of the MAP decoding algorithm such that interleaving and de-interleaving functions in the MAP decoding algorithm are performed in real-time, i.e., without delay. The systematic symbol and parity symbol contributions to the gamma function of the MAP decoding algorithm are computed in parallel using parallel channel transition probability look-up tables, such that the channel transition probabilities required in the gamma calculations are accessed at the same rate as the likelihood ratios. This memory-mapping in combination with other data handling functions (e.g., multiplexing, combinatorial logic and parallel processing) minimizes memory requirements for the turbo decoder and enables the use of programmable interleavers, variable block lengths, and multiple code rates.
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: 6381728 (2002-04-01), Kang
patent: 6434203 (2002-08-01), Halter
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 (GE docket RD-25781), filed Aug. 20, 1998.
“Turbo Code Decoder with Modified Systematic Symbol Transition Probabilities,” SM Hladik; JAF Ross; NA VanStralen; Ser. NO. 09/137,256 (GE docket RD-26016), 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 (GE docket RD-26035), 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 (GE docket RD-26064), filed Aug. 20, 1998.
“Source and Channel Coding, an Algorithmic Approach,” John B. Anderson; Seshadri Mohan, pp. 216, 336-342.
“Decision Depths of Convolutional Codes,” John B. Anderson; Kumar Balachandran; IEEE Transactions on Information Theory, vol. 35, No. 2, Mar. 1989, pp. 455-459.
“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.
Fergus Ross John Anderson
Hladik Stephen Michael
Itani Abdallah Mahmoud
Van Stralen Nick Andrew
Wodnicki Robert Gideon
Baker Stephen M.
General Electric Company
Patnode Patrick K.
Thompson John
LandOfFree
Turbo decoder control for use with a programmable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Turbo decoder control for use with a programmable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Turbo decoder control for use with a programmable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3162269