Method and apparatus for parallel decoding of turbo encoded data

• US 7,158,589 B2
• Filed: 09/12/2001
• Issued: 01/02/2007
• Est. Priority Date: 09/12/2000
• Status: Expired due to Fees

• Current Assignee: Broadcom Corporation (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Shen, Ba-Zhong, Jones, Christopher R., Tran, Hau Thien, Cameron, Kelly B.
• Primary Examiner(s): Bayard; Emmanuel
• Assistant Examiner(s): WILLIAMS, LAWRENCE B
• Application Number:
  US09/952,311
• Publication Number:
  US 20020071505A1
• Time in Patent Office: 1,938 Days
• Field of Search: 375/295, 375/341, 375/365, 714/755, 714/793, 714/795, 714/796
• US Class Current: 375/341
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/258 with turbo codes, e.g. Turbo Trellis Coded Modulation [TTCM]
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2757 Interleaver with an interleaving rule not provided for in the subgroups H03M13/2703 - H03M13/2753
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 13/2966 Turbo codes concatenated with another code, e.g. an outer block code
• CPC Class Codes: H03M 13/2978 Particular arrangement of the component decoders
• 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/3922 Add-Compare-Select [ACS] operation in forward or backward recursions
• CPC Class Codes: H03M 13/3927 Log-Likelihood Ratio [LLR] computation by combination of forward and backward metrics into LLRs
• CPC Class Codes: H03M 13/3972 using sliding window techniques or parallel windows
• CPC Class Codes: H03M 13/3988 for rate k/n convolutional codes, with k>1, obtained by convolutional encoders with k inputs and n outputs
• CPC Class Codes: H03M 13/4107 implementing add, compare, select [ACS] operations
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H03M 13/6561 Parallelized implementations
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/006 Trellis-coded modulation
• CPC Class Codes: H04L 1/0065 : Serial concatenated codes
• CPC Class Codes: H04L 1/0066 : Parallel concatenated codes
• CPC Class Codes: H04L 1/0068 : by puncturing
• CPC Class Codes: H04L 1/0071 : Use of interleaving interleaving per se H03M13/27

Abstract

A method and apparatus for parallel decoding of turbo encoded data. The method includes multiple Soft In Soft Out (SISO) modules arranged in parallel such that each module supplies an input to one SISO and takes an input from another SISO data encoded for multiple parallel SISOs is received by a receiver and decoded in the abovementioned parallel configuration.

Claims

1. A method for parallel decoding of modulo N turbo encoded data, where N in an integer, the method comprising:

accepting samples of modulo N turbo encoded data;

calculating metric values for each sample;

accepting the metric values into each of N soft input soft output (SISO) modules;

deinterleaving extrinsic values to form a-priori values;

accepting a-priori values into each of the N SISO modules; and

performing decoding calculations within each of the N SISO modules thereby forming the extrinsic values.

2. The method of claim 1 wherein accepting samples of modulo N turbo encoded data comprises accepting an inphase (I) value and quadrature (Q) value representing samples of the turbo encoded data.

3. The method of claim 1 wherein calculating metric values for each sample comprises calculating a distance between the sample and each possible transmitted constellation point.

4. The method of claim 1 wherein calculating metric values for each sample comprises calculating an Euclidean distance squared between the sample and each possible transmitted constellation point.

7. The method of claim 1 wherein deinterleaving extrinsic values to form a-priori values comprises performing a deinterleaving using an inverse interleaver of an interleaver used to produce a corresponding interleaving.

8. The method of claim 1 wherein performing decoding calculations within each of the N SISO modules thereby forming the extrinsic values comprises performing a maximum a posteriori (MAP) decoding.

9. The method of claim 1 wherein performing decoding calculations within each of the N SISO modules thereby forming the extrinsic values comprises performing a soft output Viterbi algorithm (SOVA) decoding.

5. A method for calculating metric values for each sample received for parallel decoding of modulo N turbo encoded data, where N is an integer, wherein calculating metric values for each sample comprises calculating a Euclidean distance squared between the sample and each possible transmitted constellation point and wherein calculating the Euclidean distance squared comprises:

determining a first distance, in an inphase direction, between the sample and a possible transmitted constellation point in the inphase direction;

squaring the first distance to form a first distance squared;

determining a second distance, in a quadrature direction, between the sample and a possible transmitted constellation point in the quadrature direction;

squaring the second distance to form a second distance squared; and

adding the first distance squared to the second distance squared to form the Euclidean distance squared.

6. A method for parallel decoding of modulo N turbo encoded data, where N is an integer, the method comprising:

accepting samples of modulo N turbo encoded data;

calculating metric values for each sample;

accepting the metric values into each of N soft input soft output (SISO) modules;

deinterleaving extrinsic values to form a-priori values;

accepting a-priori values into each of the N SISO modules; and

performing decoding calculations within each of the N SISO modules thereby forming the extrinsic values,

wherein accepting the a-priori values into each of N SISO modules further comprises accepting a value representing an equal likelihood that a corresponding one of the samples of modulo N turbo encoded data represents each possible constellation point on a first iteration of the decoder.

10. An apparatus for parallel decoding of modulo N turbo encoded data, where N in an integer, the apparatus comprising:

an input queue that accepts samples of modulo N turbo encoded data;

a metric calculator that accepts samples of modulo N turbo encoded data from the input queue and calculates metric values for each sample;

N soft input soft output (SISO) modules that accept the metric values and a-priori values and produce extrinsic values; and

N modulo N deinterleavers that accept the extrinsic values and deinterleave them to form the a-priori values.

11. The apparatus as in claim 10 wherein the input queue that accepts samples of modulo N turbo encoded data further comprises an input queue that accepts an inphase (I) value and quadrature (Q) values representing samples of the turbo encoded data.

12. The apparatus as in claim 10 wherein the metric calculator comprises a calculator that calculates a distance between the sample and each possible transmitted constellation point.

13. The apparatus as in claim 10 wherein the metric calculator is an Euclidean distance squared calculator that calculates the distance between the sample and each possible transmitted constellation point.

14. The apparatus as in claim 10 wherein the deinterleaver comprises an inverse of the modulo N interleaver used to encode the turbo encoded data.

15. The apparatus as in claim 10 wherein the N SISO modules are maximum a posteriori (MAP) decoders.

16. The apparatus as in claim 10 wherein the N SISO modules are soft output Viterbi algorithm (SOVA) decoders.

17. An apparatus for parallel decoding of modulo N turbo encoded data, where N in an integer, the apparatus comprising:

means for accepting samples of modulo N turbo encoded data representing a block of turbo encoded data;

means for calculating metric values that accepts samples of modulo N turbo encoded data from the sample accepting means and calculates the metric values for each sample;

N means for accepting a soft input and producing a soft output (SISO means) that accept the metric values and a-priori values and produce extrinsic values; and

N modulo N deinterleaving means that accept the extrinsic values and deinterleave it to form the a-priori values.

18. The apparatus as in claim 17 further comprising a conditional points processor that accepts samples of modulo N turbo encoded data representing a block of turbo encoded data and produces conditional points.

19. The apparatus as in claim 18 further comprising an output processor that accepts a-priori values from the SISO means and conditional points from the conditional processor and computes output tuples.

20. A method for decoding of modulo N turbo encoded data, where N in an integer, the method comprising:

receiving samples of modulo N turbo encoded data;

calculating metric values for each sample;

receiving the metric values by each of a plurality of N soft input soft output (SISO) modules;

receiving an a-priori value by a first of the N SISO modules;

performing decoding calculations by the first of the N SISO modules to form an extrinsic value;

deinterleaving the extrinsic value to form an a-priori value for the next of the N SISO modules; and

repeating the decoding calculations and the deinterleaving of between the extrinsic values for remaining modules of the N SISO modules.

21. An apparatus for decoding of modulo N turbo encoded data, where N in an integer, the apparatus comprising:

an input queue for receiving samples of modulo N turbo encoded data;

a metric calculator for calculating metric values for samples of modulo N turbo encoded data;

N soft input soft output (SISO) modules for receiving the metric values, receiving an a-priori value by a first of the N SISO modules, and decoding calculations within the first of the N SISO modules thereby forming an extrinsic value; and

N modulo N deinterleavers for deinterleaving of between the extrinsic values to form an a-priori value for a next of the N SISO modules,

wherein the N SISO modules and the N modulo N deinterleavers repeat the performing decoding calculations and the deinterleaving the extrinsic value for remaining modules of the N SISO modules.

22. The method of claim 21, wherein accepting samples of modulo N turbo encoded data comprises accepting samples of odd-even encoded data.

23. The apparatus of claim 21, wherein the input queue accepts samples of odd-even encoded data.