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

• US 20020061069A1
• Filed: 09/12/2001
• Published: 05/23/2002
• Est. Priority Date: 09/12/2000
• Status: Active Grant

• 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.
• Granted Patent: US 7,012,975 B2
• Time in Patent Office: Days
• US Class Current: 375/265
• 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;

(e) assigning the α

value of the selected state to be equal to the result of 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. The method of claim 1 wherein determining the transition having the most likelihood using a min* (min star) operation comprises computing a log likelihood of transitions from a previous states into the selected state using a Min* structure.

5. A method as in claim 4 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.

6. The method of claim 4 wherein using a min* structure comprise using an parallel Min* structure.

7. The method of claim 4 further comprising adding an offset to log computations in the Min* operation.

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

9. A method as in claim 4 wherein adding the a priori probability and branch metrics comprises adding the a priori probability and branch metrics prior to incorporation into Min* operation.

10. A method as in claim 4 wherein alpha values are maintained as separate Min_α

and Ln_α

values.

11. A method as in claim 4 wherein alpha values are maintained as separate Min_α

and Ln_α

values and are added together to be used in the calculation of extrinsic probability values.

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

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

15. The method of claim 12 wherein determining the transition having the most likelihood using a min* (min star) operation comprises computing a log likelihood of transitions into next states from the selected state using a Min* structure.

16. A method as in claim 15 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.

17. The method of claim 15 wherein using a min* structure comprise using an parallel Min* structure.

18. The method of claim 15 further comprising adding an offset to log computations in the Min* operation.

19. The method of claim 18 wherein the offset is 0.5.

20. A method as in claim 15 wherein adding the a priori and branch metrics are added together prior to incorporation into Min* operation.

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

and Ln_β

values.

22. A method as in claim 15 wherein log likelihoods are maintained as separate Min_β

and Ln_β

values and are added to be used in the calculation of extrinsic probability values.

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

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

26. The method of claim 23 wherein determining the transition having the most likelihood using a max* (max star) operation comprises computing a log likelihood of transitions from a previous states into the selected state using a Max* structure.

27. A method as in claim 26 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.

28. The method of claim 26 wherein using a max* structure comprise using an parallel Max* structure.

29. The method of claim 26 further comprising adding an offset to log computations in the Max* operation.

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

31. A method as in claim 26 wherein adding the a priori and branch metrics are added together prior to incorporation into Max* operation.

32. A method as in claim 26 wherein alpha values are maintained as separate Min_α

and Ln_α

values.

33. A method as in claim 26 wherein alpha values are maintained as separate Min_α

and Ln_α

values and are added together to be used in the calculation of extrinsic values.

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

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

37. The method of claim 34 wherein determining the transition having the most likelihood using a max* (max star) operation comprises computing a log likelihood of transitions into next states from the selected state using a Max* structure.

38. A method as in claim 37 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.

39. The method of claim 37 wherein using a min* structure comprise using an parallel Max* structure.

40. The method of claim 15 further comprising adding an offset to log computations in the max* operation.

41. The method of claim 40 wherein the offset is 0.5.

42. A method as in claim 37 wherein adding the a priori and branch metrics are added together prior to incorporation into Max* operation.

43. A method as in claim 37 wherein beta values are maintained as separate Min_β

and Ln_β

values.

44. A method as in claim 37 wherein log likelihoods are maintained as separate Min_β

and Ln_β

values and are added to be used in the calculation of extrinsic values.

12. 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;

(e) assigning the β

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

23. 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* (min star) operation;

(e) assigning the α

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

34. 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;

(e) assigning the β

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