Turbo decoder control for use with a programmable interleaver, variable block length, and multiple code rates

• US 6,516,437 B1
• Filed: 03/07/2000
• Issued: 02/04/2003
• Est. Priority Date: 03/07/2000
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Van Stralen, Nick Andrew, Ross, John Anderson Fergus, Wodnicki, Robert Gideon, Hladik, Stephen Michael, Itani, Abdallah Mahmoud
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/519,903
• Time in Patent Office: 1,064 Days
• Field of Search: 714/755, 714/786
• US Class Current: 714/755
• CPC Class Codes: H03M 13/2789 Interleaver providing variable interleaving, e.g. variable block sizes
• CPC Class Codes: H03M 13/2957 Turbo codes and decoding
• CPC Class Codes: H03M 13/3905 Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding
• CPC Class Codes: H03M 13/3933 Decoding in probability domain
• CPC Class Codes: H03M 13/3961 Arrangements of methods for branch or transition metric calculation
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A turbo decoder control comprises an address generator for addressing systematic data, parity data, and systematic likelihood ratios according to a pre-determined memory mapping. The systematic data samples are accessed in the order required by 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. Such memory-mapping in combination with data handling functions (e.g., multiplexing and combinatorial logic) minimizes memory requirements for the turbo decoder and allows for use of programmable interleavers, variable block lengths, and multiple code rates.

Claims

1. A control for a turbo decoder for decoding turbo codes comprising two recursive systematic code words concatenated in parallel, each code word comprising systematic data and parity data, the turbo decoder comprising a MAP decoding algorithm, the turbo decoder comprising a gamma block for calculating unconditioned symbol transition probabilities, each unconditioned symbol transition probability representing a gamma value, the gamma block receiving as inputs channel transition probabilities and a priori bit probabilities, alpha and beta blocks for receiving the gamma values from the gamma block and for recursively calculating forward and backward state probabilities, respectively, the forward state probabilities representing alpha values and the backward state probabilities representing beta values, a sigma block for receiving the alpha and beta values, respectively, from the alpha and beta blocks, respectively, and for calculating a posteriori transition probabilities therefrom, the a posteriori transition probabilities representing sigma values, the sigma block performing a summation function of the sigma values to provide a posteriori probability estimates of the systematic symbols of the component code words as outputs of the turbo decoder, the turbo decoder control comprising:

an address generator for addressing the systematic data, the parity data, and systematic likelihood ratios according to a pre-determined memory mapping such that the systematic data samples are accessed in the order required by the MAP decoding algorithm such that interleaving and de-interleaving functions in the MAP decoding algorithm are performed in real-time;

a de-interleaver definition block for receiving the address from the address generator and providing a de-interleaver definition address;

a multiplexer, which is controlled by a top/bottom code select block, for selecting the address from the address generator or the address from the de-interleaver definition block and for providing the selected address directly and through a delay to a systematic likelihood ratio circuit and directly to a systematic data block, the systematic likelihood ratio circuit providing the systematic likelihood ratios to a component decoder, the systematic data block providing systematic data to the component decoder in parallel with the systematic likelihood ratio circuit, the output of the component decoder comprising the a posteriori probability estimates which are fed back through the systematic likelihood ratio circuit;

bottom and top code parity data blocks for receiving the address from the address generator and for providing the parity data via a multiplexer controlled by the top/bottom code select block to the component decoder.

2. The control of claim 1 wherein the channel transition probabilities, comprising the channel transition probability values P1 and P0, are provided in a look-up table.

3. The control of claim 2 wherein the address generator accesses the channel transition probabilities P0 and P1 with a single address.

4. The control of claim 2 wherein the systematic data and parity data are stored in parallel memory tables for simultaneous access.

5. The control of claim 1 wherein the memory mapping comprises a sequence represented as [012345 . . . τ

−

1 τ

−

1 τ

−

2 . . . 3210] for the systematic data, the parity data and the likelihood ratios, where τ

is programmable and supports variable block lengths.

6. The control of claim 5 wherein the memory mapping sequence [012345 . . . τ

−

1 τ

−

1 τ

−

2 . . . 3210] is applied to the alpha and beta blocks.

7. The control of claim 1 wherein the gamma block comprises a puncturing function to support multiple code rates.

8. A turbo decoder for decoding turbo codes comprising two recursive systematic code words concatenated in parallel, each code word comprising systematic data and parity data, comprising:

a MAP decoding algorithm;

a gamma block for calculating unconditioned symbol transition probabilities, each unconditioned symbol transition probability representing a gamma value, the gamma block receiving as inputs channel transition probabilities and a priori bit probabilities;

alpha and beta blocks for receiving the gamma values from the gamma block and for recursively calculating forward and backward state probabilities, respectively, the forward state probabilities representing alpha values and the backward state probabilities representing beta values;

a sigma block for receiving the alpha and beta values, respectively, from the alpha and beta blocks, respectively, and for calculating a posteriori transition probabilities therefrom, the a posteriori transition probabilities representing sigma values, the sigma block performing a summation function of the sigma values to provide a posteriori probability estimates of the systematic symbols of the component code words as outputs of the turbo decoder;

an address generator for addressing the systematic data, the parity data, and systematic likelihood ratios according to a pre-determined memory mapping such that the systematic data samples are accessed in the order required by the MAP decoding algorithm such that interleaving and de-interleaving functions in the MAP decoding algorithm are performed in real-time;

a de-interleaver definition block for receiving the address from the address generator and providing a de-interleaver definition address;

a multiplexer, which is controlled by a top/bottom code select block, for selecting the address from the address generator or the address from the de-interleaver definition block and for providing the selected address directly and through a delay to a systematic likelihood ratio circuit and directly to a systematic data block, the systematic likelihood ratio circuit providing the systematic likelihood ratios to a component decoder, the systematic data block providing systematic data to the component decoder in parallel with the systematic likelihood ratio circuit, the output of the component decoder comprising the a posteriori probability estimates which are fed back through the systematic likelihood ratio circuit;

bottom and top code parity data blocks for receiving the address from the address generator and for providing the parity data via a multiplexer controlled by the top/bottom code select block to the component decoder.

9. The turbo decoder of claim 8 wherein the channel transition probabilities, comprising the channel transition probability values P1 and P0, are provided in a look-up table.

10. The turbo decoder of claim 9 wherein the address generator accesses the channel transition probabilities P0 and P1 with a single address.

11. The turbo decoder of claim 9 wherein the systematic data and parity data are stored in parallel memory tables for simultaneous access.

12. The turbo decoder of claim 8 wherein the memory mapping comprises a sequence represented as [012345 . . . τ

−

1 τ

−

1 τ

−

2 . . . 3210] for the systematic data, the parity data and the likelihood ratios, where τ

is programmable and supports variable block lengths.

13. The turbo decoder of claim 12 wherein the memory mapping sequence [012345 . . . τ

−

1 τ

−

1 τ

−

2 . . . 3210] is applied to the alpha and beta blocks.

14. The turbo decoder of claim 8 wherein the gamma block comprises a puncturing function to support multiple code rates.