Method and apparatus for performing calculations for forward (alpha) and reverse (beta) metrics in a map decoder

• US 7,012,975 B2
• Filed: 09/12/2001
• Issued: 03/14/2006
• 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): Chin, Stephen
• Assistant Examiner(s): ODOM, CURTIS B
• Application Number:
  US09/952,309
• Publication Number:
  US 20020061069A1
• Time in Patent Office: 1,644 Days
• Field of Search: 375/340, 375/341, 714/786, 714/795
• 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 performing calculations for forward (alpha) and reverse (beta) metrics in a map decoder. The method includes using a min star (min*) operation to receive the metrics and a priori values as well as forming min star structures from individual min star operations. Two separate outputs from the min star operation may be maintained separately throughout all calculations and combined only when a final value is required. In addition input to the min star operators that are available prior to a particular decoder iteration may be combined separately to allow an increase in speed within decoding iterations. The same principals apply to the more popular max star operation.

Claims

1. A method of calculating alpha (α

) values in a map decoder, the method comprising;

(a) selecting a state to calculate an α

value for;

(b) determining which previous states may result in a transition into the selected state;

(c) determining a likelihood for each transition from a previous state into the selected state;

(d) determining the transition having the most likelihood using a min* (min star) operation by computing a log likelihood of transitions from a previous states into the selected state using a Min* structure;

(e) assigning the α

value of the selected state to be equal to the result of the min* operation; and

(f) adding an offset to log computations in the Min* operation.

2. The method of claim 1 further comprising repeating steps (a) through (e) for all permissible trellis states.

3. The method of claim 1 further comprising repeating steps (a) through (e) simultaneously for all permissible trellis states.

4. A method as in claim 1, further comprising computing simultaneously log likelihoods for all transitions from previous states into the selected state by performing a min* to predict the likelihood of all possible transitions from a previous state into the selected state.

5. The method of claim 1, wherein using a Min* structure comprises using a parallel Min* structure.

6. The method of claim 1 wherein the offset is 0.5.

7. A method as in claim 1, further comprising adding an a priori probability and branch metrics prior to incorporation into Min* operation.

8. A method of calculating beta (β

) values in a map decoder, the method comprising;

(a) selecting a state to calculate an β

value for;

(b) determining which next states may result in a transition from the selected state;

(c) determining a likelihood for each transition to a next state from the selected state;

(d) determining the transition having the most likelihood using a min* (min star) operation by computing a log likelihood of transitions into next states from the selected state using a Min* structure;

(e) assigning the β

value of the selected state to be equal to the result of the min* operation; and

(f) adding an offset to log computations in the Min* operation.

9. The method of claim 8 further comprising repeating steps (a) through (e) for all permissible trellis states.

10. The method of claim 8 further comprising repeating steps (a) through (e) simultaneously for all permissible trellis states.

11. A method as in claim 8, further comprising computing simultaneously log likelihoods for all transitions into next states from the selected state by performing a min* simultaneously of all possible transitions into a next state from the selected state.

12. The method of claim 8, wherein using a Min* structure comprises using a parallel Min* structure.

13. The method of claim 8 wherein the offset is 0.5.

14. A method as in claim 8, wherein an a priori probability and branch metrics are added together prior to incorporation into Min* operation.

15. A method as in claim 8 wherein beta values are maintained as separate Min_β

and Ln_β

values, wherein Min β

is minimum of the operands comparing a first input (A) and a second input (B) to the decoder, A comprises an β

metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β

metric, a priori values and a transition metric for a second previous state of the decoder, and ln β

=−

log(1+e<sup>−

|A−

B|</sup>).

16. A method as in claim 8 wherein log likelihoods are maintained as separate Min_β

and Ln_β

values and are added to be used in the calculation of extrinsic probability values, wherein Min β

is minimum of the operands comparing a first input (A) and a second input (B) to the decoder, A comprises an β

metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β

metric, a priori values and a transition metric for a second previous state of the decoder, and ln β

=−

log(1+e<sup>−

|A−

B|</sup>).

17. A method of calculating alpha (α

) values in a map decoder, the method comprising;

(a) selecting a state to calculate an α

value for;

(b) determining which previous states may result in a transition into the selected state;

(c) determining a likelihood for each transition from a previous state into the selected state;

(d) determining the transition having the most likelihood using a max* (max star) operation by computing a log likelihood of transitions from a previous states into the selected state using a Max* structure;

(e) assigning the α

value of the selected state to be equal to the result of the max* operation; and

(f) adding an offset to log computations in the Max* operation.

18. The method of claim 17 further comprising repeating steps (a) through (e) for all permissible trellis states.

19. The method of claim 17 further comprising repeating steps (a) through (e) simultaneously for all permissible trellis states.

20. A method as in claim 17, further comprising computing simultaneously log likelihoods for all transitions from previous states into the selected state by performing a max* to predict the likelihood of all possible transitions from a previous state into the selected state.

21. The method of claim 17, wherein using a Max* structure comprises using a parallel Max* structure.

22. The method of claim 17 wherein the offset is 0.5.

23. A method as in claim 17, wherein an a priori probability and branch metrics are added together prior to incorporation into Max* operation.

24. A method of calculating beta (β

) values in a map decoder, the method comprising;

(a) selecting a state to calculate an β

value for;

(b) determining which next states may result in a transition from the selected state;

(c) determining a likelihood for each transition to a next state from the selected state;

(d) determining the transition having the most likelihood using a max* (max star) operation by computing a log likelihood of transitions into next states from the selected state using a Max* structure;

(e) assigning the β

value of the selected state to be equal to the result of the max* operation; and

(f) adding an offset to log computations in the max* operation.

25. The method of claim 24 further comprising repeating steps (a) through (e) for all permissible trellis states.

26. The method of claim 24 further comprising repeating steps (a) through (e) simultaneously for all permissible trellis states.

27. A method as in claim 24, further comprising computing simultaneously log likelihoods for all transitions into next states from the selected state by performing a max* simultaneously of all possible transitions into a next state from the selected state.

28. The method of claim 24, wherein using a Max* structure comprises using a parallel Max* structure.

29. The method of claim 24 wherein the offset is 0.5.

30. A method as in claim 24, wherein an a priori probability and branch metrics are added together prior to incorporation into Max* operation.

31. A method as in claim 24 wherein beta values are maintained as separate Max β

and Ln_β

values, wherein Max β

is maximum of the operands comparing a first input (A) and a second input (B) to the decoder, A comprises an β

metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β

metric, a priori values and a transition metric for a second previous state of the decoder, and ln β

=−

log(1+e<sup>−

|A−

B|</sup>).

32. A method as in claim 24 wherein log likelihoods are maintained as separate Max β

and Ln₁₃ β

values and are added to be used in the calculations of extrinsic values, wherein Max β

is maximum of the operands comparing a first input (A) and a second input (B) to the decoder, A comprises an β

metric, a priori values and a transition metric for a first previous state of the decoder and B comprises an β

metric, a priori values and a transition metric for a second previous state of the decoder, and ln β

=−

log(1+e<sup>−

|A−

B|</sup>).