Method and apparatus for soft-in soft-out turbo code decoder

• US 6,940,928 B2
• Filed: 09/12/2001
• Issued: 09/06/2005
• Est. Priority Date: 09/12/2000
• Status: Expired due to Fees

• Current Assignee: Broadcom Corporation (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Cameron, Kelly B.
• Primary Examiner(s): Liu, Shuwang
• Assistant Examiner(s): WANG, TED M
• Application Number:
  US09/952,312
• Publication Number:
  US 20020061078A1
• Time in Patent Office: 1,455 Days
• Field of Search: 714/792, 714/796, 714/755, 714/86, 714/746, 714/780, 714/795, 714/788, 714/786, 714/758, 375/341, 375/265, 375/295, 375/340, 375/262, 375/232, 375/298, 375/261, 375/259, 375/222, 341/50
• 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

Method and apparatus for Soft In Soft Out Turbo Code Decoder. Metrics are received by a decoder having SISO unit(s). The SISO unit computes all the alpha values corresponding to a block of data. Of the alpha values computed some alpha values, for example alpha values selected at regular intervals, corresponding to checkpoint values are pushed on a checkpoint stack. Alpha values are computed with some being saved as checkpoint values and some being discarded are computed until the computation reaches a predetermined distance from the end of the block of data. Once the predetermined distance is reached all alpha values are pushed on a computation stack. Once all the values corresponding to the values between the predetermined end of the block and the end of the block have been computed and placed in the computation stack they may be combined with beta values to produce extrinsic values. Once all the values have been used from the computation stack the next checkpoint value can be used to compute another computation stack of alpha values. The alpha values can then be combined with beta values to form extrinsic values and the process continued.

Claims

1. A method for computing extrinsic likelihood values in a soft in soft out (SISO) decoder the method comprising:

accepting a block of channel metrics and a priori values;

dividing the block of channel metrics and a priori values into sub blocks accepting an nth channel metric and an nth a priori value into an alpha (α

) computer;

computing an nth α

value from the nth channel metric and the nth a priori value using the nth α

value to compute the (n+1)th a value;

pushing α

values corresponding to the beginning of a sub block on a checkpoint stack until a beginning of the last sub block is reached;

pushing each of the α

values of the final sub block on the checkpoint stack;

popping each of the α

values of the last sub block from the checkpoint stack and combining them with beta (β

) values to form extrinsic likelihood values.

2. The method of claim 1 wherein pushing α

values corresponding to the beginning of a sub block on a checkpoint stack further comprises;

using each α

value to compute a subsequent α

value; and

discarding each α

value when it is no longer needed to compute the subsequent α

value.

3. The method of claim 2 further comprising:

(a) popping a value, representing a first α

value of a next sub block off the checkpoint stack;

(b) computing all the α

values of the next sub block and pushing them onto the checkpoint stack;

(c) popping each of the α

values of the next sub block from the checkpoint stack and combining them with β

values to form extrinsic likelihood values; and

(d) repeating a, b, and c until all of the α

values of the next sub block have been used in computing extrinsic values.

4. A method for computing extrinsic likelihood values in a soft in soft out (SISO) decoder the method comprising:

accepting a block of channel metrics and a priori values;

dividing the block of channel metrics and a priori values into sub blocks accepting an nth channel metric and an nth a priori value into an alpha (α

) computer;

computing a nth α

value from the nth channel metric and the nth a priori value using the nth α

value to compute the (n+1)th a value;

pushing α

values corresponding to the beginning of a sub block on checkpoint stack until a beginning of the last sub block is reached;

pushing each of the α

values, once the beginning of the last sub block has been reached, on a first computation stack to form a first set of α

values;

popping α

values of the first set of α

values from the first computation stack once the last value of α

of the sub block has been computed and combining α

values from the first set of α

values with beta (β

) values to form extrinsic likelihood values.

5. The method of claim 4 wherein popping the α

values from the first computation stack proceeds essentially simultaneously with pushing α

values on a second computation stack.

6. The method of claim 4 further comprising:

using the first computational stack to receive newly computed α

values; and

using the values in the second computational stack to combine with β

values to form extrinsic likelihood values thereby switching the use of the first computational stack and the second computational stack.

7. The method of claim 6 further comprising using the first computational stack and the second computational stack essentially simultaneously.

8. The method of claim 6 further comprising providing latencies between a computation stack and an extrinsic calculator so that α

values and corresponding β

values arrive essentially simultaneously for use in extrinsic calculations.

9. An apparatus for computing extrinsic likelihood values in a soft in soft out (SISO) decoder the apparatus comprising:

an α

computer that receives a priori values and channel metrics and computes α

values;

a checkpoint stack, for receiving α

checkpoint values from the α

computer;

a β

computer that receives a priori values and channel metrics and computes β

values; and

an extrinsic calculator that accepts the α

values provided by the α

computer and the β

values provided by the β

computer and produces extrinsic likelihood values;

a first computational stack that receives the α

values when a second computational stack is providing computational the α

values; and

the second computational stack that receives the α

values when the first computational stack is providing computational the α

values.

10. The apparatus as in claim 9 wherein the checkpoint stack for receiving α

checkpoint values from the α

computer further comprises;

means for determining a beginning of a sub block; and

means for selecting only a first α

value to be pushed on the computational stacks.

11. The apparatus as in claim 9 further comprising:

a latency block that accepts the α

values and delays them to correspond to the arrival of the β

values into the extrinsic calculator.

12. The apparatus of claim 9 wherein the first and second computational stacks comprise a stack of entries, which store a priori values, α

values and channel metrics.

13. The apparatus of claim 12 wherein the β

computer further comprises;

an input for accepting channel metrics from one of the first and second computational stacks; and

an input for accepting a priori values from another of the first and second computational stacks.

14. The apparatus of claim 9 wherein the first computational stack further comprises:

storage elements for storing the α

values;

storage elements for storing a priori values; and

storage elements for storing channel metric values.

15. The apparatus of claim 9 wherein the second computational stack further comprises:

storage elements for storing the α

values;

storage elements for storing a priori values; and

storage elements for storing channel metric values.

16. A method of computing extrinsic values for a block of metrics and corresponding a priori values the method comprising:

computing α

values for the block of metrics and saving only values corresponding to the beginning of a sub block as checkpoint values on a checkpoint stack;

computing α

values between checkpoint values when such α

values are required wherein computing α

values and saving only checkpoint values on the checkpoint stack comprises;

computing all α

values;

selecting the values corresponding to the beginning of the sub block as the checkpoint values; and

pushing the selected values on the checkpoint stack.

17. A method of computing extrinsic values for a block of metrics and corresponding a priori values the method comprising:

computing α

values for the block of metrics and saving only values corresponding to the beginning of a sub block as checkpoint values on a checkpoint stack;

computing α

values between checkpoint values when such α

values are required, wherein computing α

values between checkpoint values when such α

values are required further comprises computing α

values and pushing them on a first stack such that the first stack is full when a second stack, which is providing α

values, is empty.

18. The method of claim 17 further comprising switch functions of the first and the second stack such that one stack is essentially providing α

values at the same time the other stack is receiving values.