High-speed turbo decoder

Details High-speed turbo decoder High-speed turbo decoder

1999-03-08

2001-10-16

Decady, Albert (Department: 2784)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S794000

Reexamination Certificate

active

06304996

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates generally to error-correction coding and, more particularly, to a decoder for parallel concatenated codes, e.g., 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 permutations 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 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 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 systematic bits in the code word. These probability estimates are used as a priori symbol probability estimates 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 probability estimates (the sigma function).
It is desirable to provide a turbo decoder which efficiently uses memory and combinatorial logic such that the structure thereof is highly streamlined with parallel signal processing. It is further desirable to provide such a structure which is amenable to implementation on an application specific integrated circuit (ASIC).
BRIEF SUMMARY OF THE INVENTION
A high-speed turbo decoder utilizes a MAP decoding algorithm and comprises a streamlined construction of functional units, or blocks, amenable to ASIC implementation. The turbo decoder comprises a gamma block, alpha and beta blocks, and a sigma block. The gamma block provides symbol-by-symbol a posteriori state transition probability estimates (values of the gamma probability function), only four non-zero gamma probability function values being possible at any particular trellis level. Two gamma probability function values are provided via selection switches to the alpha and beta blocks for calculating the alpha and beta probability function values, i.e., performing the alpha and beta recursions, respectively, in parallel, thus significantly increasing decoding speed. The alpha and beta blocks have as many state update circuits as there are states in the trellis. A scaling or normalization circuit monitors the values of the alpha and beta probability functions and prescribes a scale factor such that all such values at a trellis level remain within the precision limits of the system. Previously calculated values of these probability functions are used for the normalization calculation in order to remove the normalization calculation from the critical path in the alpha and beta blocks and thus increase decoding speed. The outputs of the alpha and beta blocks are buffered and provided as inputs to the sigma block. The sigma block determines the a posteriori state transition probability estimates (sigma values) and uses the sigma values to provide the a posteriori bit probability estimates, i.e., the soft-decision outputs of the turbo decoder.


REFERENCES:
patent: Re. 32905 (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: 6000054 (1999-12-01), Bahr et al.
patent: 6014411 (2000-01-01), Wang
patent: 6023783 (2000-02-01), Divsalar et al.
patent: 6028897 (2000-03-01), Wang
patent: 6044116 (2000-02-01), Wang
patent: 0 735 696 (1996-10-01), None
patent: 2 675 970 (1992-10-01), None
D. Divsalar and F. Pollara, “Hybrid Concatenated Codes and Iterative Decoding”, TDA Progress Report 42-130, Jet Propulsion Laboratory, NASA, Aug. 15, 1997.*
S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “A Soft-Input Soft-Output Maximum A Posteriori MAP Module to Decode Parallel and Serial Concatenated Codes”, TDA Progress Report 42-127, Jet Propulsion Laboratory, NASA, Nov. 15, 1996.*
Patrick Robertson, Emmanuelle Villebrun and Peter Hoecher, “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain”, IEEE 1995.*
Patrick Robertson, “Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic Turbo Codes”, IEEE 1994.*
Patrick Robertson, “Improving Decoder and Code Structure of Parallel Concatenated Recursive Systematic Turbo Codes”, IEEE 1994.*
Sven Riedel, “MAP Decoding of Convolutional Codes Using Reciprocal Dual Codes”, IEEE Transactions on Information Theory, vol. 44, No. 3, May 1998.*
S. Benedetto, D. Divsalar, G. Montorsi and F. Pollara; “Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes”; TDA Progress Report 42-124, Jet Propulsion Laboratory, NASA, Feb. 15, 19.*
Jakob Dahl Andersen, “The Turbo Coding Scheme”, Report IT-146, ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, Dec. 1994.*
Claude Berrou and Alain Glavieux, “Near Optimum Error Correcting Coding And Decoding: Turbo-Codes”, IEEE Transactions on Communications, vol. 44, No. 10, Oct. 1996.*
Sven Riedel, “Symbol-by-Symbol MAP Decoding Algorithm for High-Rate Convolutional Codes That Use Reciprocal Dual Codes”, IEEE Journal on Selected Areas in Communications, vol. 16, No. 2, Feb. 1998.*
“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, 199

Affiliated with

Also associated with

Rating

High-speed turbo decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-speed turbo decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed turbo decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2596624