Single stage implementation of min*, max*, min and /or max to perform state metric calculation in SISO decoder

• US 7,137,059 B2
• Filed: 01/02/2003
• Issued: 11/14/2006
• Est. Priority Date: 11/20/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Tran, Hau Thien, Cameron, Kelly Brian, Hughes, Thomas A. Jr.
• Primary Examiner(s): Torres, Joseph D.
• Application Number:
  US10/335,702
• Publication Number:
  US 20040098662A1
• Time in Patent Office: 1,412 Days
• Field of Search: 714/794, 714/795
• US Class Current: 714/794
• 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/3911 Correction factor, e.g. approximations of the exp(1+x) function
• CPC Class Codes: H03M 13/395 using a collapsed trellis, e.g. M-step algorithm, radix-n architectures with n>2
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/0055 MAP-decoding

Abstract

Single stage implementation of min*, max*, min and/or max to perform state metric calculation in soft-in soft-out (SISO) decoder. This allows for calculation of state metrics in an extremely efficient, fast manner. When performing min or max calculations, comparisons are made using 2 element combinations of the available inputs. Subsequently, logic circuitry employs the results of the 2 element comparisons the smallest (min) or largest (max) input. The max or min implementations may be employed as part of the max* and/or min* implementations. For max* and/or min* implementations, simultaneous calculation of appropriate values is performed while determining which input is the smallest or largest. Thereafter, the determination of which input is the smallest or largest is used to select the appropriate resultant value (of the values calculated) for max* and/or min*. Various degrees of precision are employed for the log correction values within the max* and/or min* implementations.

Claims

1. An apparatus, comprising:

a preliminary calculation circuitry that is operable to;

calculate a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs;

add each 2 element log correction value of the plurality of 2 element log correction values to a first of its corresponding 2 inputs from among the plurality of inputs thereby generating at least a first value;

add each 2 element log correction value of the plurality of 2 element log correction values to its a second of its corresponding 2 inputs from among the plurality of inputs thereby generating at least a second value; and

determine a mm result or max result using the first value and the second value;

a final log correction value calculation circuitry that is operable to calculate a final log correction value that corresponds to all inputs of the plurality of inputs; and

an adder that is operable to sum the mm result or the max result and the final log correction value to calculate a min* result or a max* result that is employed when calculating a state metric for use in decoding a coded signal.

2. The apparatus of claim 1, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry; and

the min selection control circuitry or the max selection control circuitry is operable to select a min value or a max value from among a 2 element pair of inputs of the plurality of inputs.

3. The apparatus of claim 1, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

4. The apparatus of claim 1, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry;

the min selection control circuitry or the max selection control circuitry is operable to select a min value or a max value from among a 2 element pair of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

5. The apparatus of claim 1, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

6. The apparatus of claim 1, wherein:

the preliminary calculation circuitry is operable to calculate a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable to simultaneously to generate the first value and the second value.

7. The apparatus of claim 1, wherein:

the min result or the max result and the final log correction value are all kept separate for use in subsequent processing stages.

8. The apparatus of claim 1, wherein:

the apparatus is a soft-in soft-out (SISO) decoder that is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

9. An apparatus, comprising:

a preliminary calculation circuitry that is operable to;

calculate a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs;

add simultaneously each 2 element log correction value of the plurality of 2 element log correction values to each of its corresponding 2 inputs from among the plurality of inputs thereby generating at least a first value and a second value;

determine a min result or max result using the first value and the second value; and

a final log correction value calculation circuitry that is operable to calculate a final log correction value that corresponds to all inputs of the plurality of inputs; and

an adder that is operable to sum the min result or the max result and the final log correction value to calculate a min* result or a max* result that is employed when calculating a state metric for use in decoding a coded signal.

10. The apparatus of claim 9, wherein:

the min selection control circuitry or the max selection control circuitry is operable to select a min value or a max value from among a 2 element pair of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

11. The apparatus of claim 9, further comprising:

a min selection circuitry or the max selection circuitry that is operable simultaneously to generate the first value and the second value.

12. The apparatus of claim 9, wherein:

the preliminary calculation circuitry is operable to calculate a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

13. The apparatus of claim 9, wherein:

the min result or the max result and the final log correction value are all kept separate for use in subsequent processing stages.

14. The apparatus of claim 9, wherein:

the apparatus is a soft-in soft-out (SISO) decoder that is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

15. A method, comprising:

calculating a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs;

adding each 2 element log correction value to each of its corresponding 2 inputs from among the plurality of inputs thereby generating at least a first value and a second value;

determining a min result or max result using the first value and the second value;

calculating a final log correction value that corresponds to all inputs of the plurality of inputs; and

summing the min result or max result and the final log correction value to calculate a min* result or a max* result that is employed when calculating a state metric for use in decoding a coded signal.

16. The method of claim 15, further comprising selecting a min value or a max value from among a 2 element pair of inputs of the plurality of inputs.

17. The method of claim 15, further comprising simultaneously calculating the first value and the second value.

18. The method of claim 15, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs; and

simultaneously calculating the first value and the second value.

19. The method of claim 15, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs, wherein the plurality of sign bits indicate relative relationships between each 2 element pair of inputs of the plurality of inputs; and

simultaneously calculating the first value and the second value.

20. The method of claim 15, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs, wherein the plurality of sign bits indicate relative relationships between each 2 element pair of inputs of the plurality of inputs;

simultaneously calculating the first value and the second value; and

keeping the min result or max result and the final log correction value separate for use in subsequent processing stages.

21. The method of claim 15, further comprising keeping the min result or max result and the final log correction value separate for use in subsequent processing stages.

22. The method of claim 15, wherein:

the method is performed within a soft-in soft-out (SISO) decoder that is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

23. An apparatus, comprising:

a preliminary calculation circuitry that is operable to determine a min result or max result using a first value and a second value, wherein;

the first value is a sum of a first input of a plurality of inputs and a first 2 element log correction value that corresponds to the first input and a second input of the plurality of inputs; and

the second value is a sum of the second input and the 2 element first log correction value that corresponds to the first input and the second input;

a final log correction value calculation circuitry that is operable to calculate a final log correction value that corresponds to all inputs of the plurality of inputs; and

an adder that is operable to sum the min result or the max result and the final log correction value to calculate a min* result or a max* result that is employed when calculating a state metric for use in decoding a coded signal.

24. The apparatus of claim 23, wherein:

the preliminary calculation circuitry is operable to;

calculate a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs; and

add each 2 element log correction value to its corresponding input from among the plurality of inputs thereby generating at least the first value and the second value.

25. The apparatus of claim 24, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

26. The apparatus of claim 24, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

27. The apparatus of claim 24, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

28. The apparatus of claim 24, wherein:

the preliminary calculation circuitry is operable to calculate a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

29. The apparatus of claim 23, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry; and

the min selection control circuitry or the max selection control circuitry is operable to select a min value or a max value from among a 2 element pair of inputs of the plurality of inputs.

30. The apparatus of claim 23, wherein:

the min result or the max result and the final log correction value are all kept separate for use in subsequent processing stages.

31. The apparatus of claim 23, wherein:

the apparatus is a soft-in soft-out (SISO) decoder is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

32. A method, comprising:

determining a min result or max result using a first value and a second value, wherein;

the first value is a sum of a first input of a plurality of inputs and a first 2 element log correction value that corresponds to the first input and a second input of the plurality of inputs; and

the second value is a sum of the second input and the 2 element first log correction value that corresponds to the first input and a second input;

calculating a final log correction value that corresponds to all inputs of the plurality of inputs; and

summing the min result or max result and the final log correction value to calculate a min* result or a max* result that is employed when calculating a state metric for use in decoding a coded signal.

33. The method of claim 32, further comprising:

calculating a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs; and

adding each 2 element log correction value to its corresponding input from among the plurality of inputs thereby generating at least the first value and the second value.

34. The method of claim 33, further comprising simultaneously calculating the first value and the second value.

35. The method of claim 33, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs; and

simultaneously calculating the first value and the second value.

36. The method of claim 33, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs, wherein the plurality of sign bits indicate relative relationships between each 2 element pair of inputs of the plurality of inputs; and

simultaneously calculating the first value and the second value.

37. The method of claim 33, further comprising:

calculating a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs, wherein the plurality of sign bits indicate relative relationships, between each 2 element pair of inputs of the plurality of inputs;

simultaneously calculating the first value and the second value; and

keeping the min result or max result and the final log correction value separate for use in subsequent processing stages.

38. The method of claim 32, further comprising selecting a min value or a max value from among a 2 element pair of inputs of the plurality of inputs.

39. The method of claim 32, further comprising keeping the min result or max result and the final log correction value separate for use in subsequent processing stages.

40. The method of claim 32, wherein:

the method is performed within a soft-in soft-out (SISO) decoder that is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.

41. An apparatus, comprising:

a preliminary calculation circuitry that is operable to;

calculate a plurality of 2 element log correction values, each 2 element log correction value of the plurality of 2 element log correction values corresponds to 2 inputs of a plurality of inputs;

add each 2 element log correction value to each of its corresponding input from among the plurality of inputs thereby generating at least a first value and a second value; and

determine a min result or max result using at least the first value and the second value; and

a final log correction value calculation circuitry that is operable to calculate a final log correction value that corresponds to all inputs of the plurality of inputs, wherein the final log correction value is employed when calculating a state metric for use in decoding a coded signal.

42. The apparatus of claim 41, further comprising:

an adder that is operable to sum the min result or the max result and the final log correction value to calculate a min* result or a max* result.

43. The apparatus of claim 41, wherein:

the first value is a sum of a first input of a plurality of inputs and a first 2 element log correction value that corresponds to the first input and a second input of the plurality of inputs; and

the second value is a sum of the second input and the 2 element first log correction value that corresponds to the first input and a second input.

44. The apparatus of claim 41, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry; and

the min selection control circuitry or the max selection control circuitry is operable to select a min value or a max value from among a 2 element pair of inputs of the plurality of inputs.

45. The apparatus of claim 41, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

46. The apparatus of claim 41, wherein:

the preliminary calculation circuitry includes a min selection control circuitry or a max selection control circuitry;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

47. The apparatus of claim 41, wherein:

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry;

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value; and

the min result or the max result and the final log correction value are all kept separate for use in subsequent processing stages.

48. The apparatus of claim 41, wherein:

the preliminary calculation circuitry is operable to calculate a plurality of sign bits that corresponds to differences between 2 element pairs of inputs of the plurality of inputs;

the preliminary calculation circuitry includes a min selection circuitry or a max selection circuitry; and

the min selection circuitry or the max selection circuitry is operable simultaneously to generate the first value and the second value.

49. The apparatus of claim 41, wherein:

the min result or the max result and the final log correction value are all kept separate for use in subsequent processing stages.

50. The apparatus of claim 41, wherein:

the apparatus is a soft-in soft-out (SISO) decoder is implemented within a communication receiver; and

the communication receiver is contained within at least one of a satellite communication system, a High Definition Television (HDTV) communication system, a cellular communication system, a microwave communication system, a point-to-point communication system, a uni-directional communication system, a bi-directional communication system, a one to many communication system, and a fiber-optic communication system.