Inverse function of min*:min*- (inverse function of max*:max*-)

• US 7,360,146 B1
• Filed: 01/21/2003
• Issued: 04/15/2008
• Est. Priority Date: 08/15/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Shen, Ba-Zhong, Tran, Hau Thien, Cameron, Kelly Brian, Hughes, Thomas A. Jr.
• Primary Examiner(s): Lamarre; Guy
• Assistant Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US10/347,732
• Time in Patent Office: 1,911 Days
• Field of Search: 714/786, 714/819, 714/780, 714/794
• 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/3922 Add-Compare-Select [ACS] operation in forward or backward recursions
• CPC Class Codes: H03M 13/395 using a collapsed trellis, e.g. M-step algorithm, radix-n architectures with n>2

Abstract

Inverse function of min*:min*− (inverse function of max*:max*−). Two new parameters are employed to provide for much improved decoding processing for codes that involve the determination of a log corrected minimal and/or a log corrected maximal value from among a number of possible values. Examples of some of the codes that may benefit from the improved decoding processing provided by the inverse function of min*:min*− (and/or inverse function of max*:max*−) include turbo coding, parallel concatenated trellis coded modulated (PC-TCM) code, turbo trellis coded modulated (TTCM) code, and low density parity check (LDPC) code among other types of codes. The total number of processing steps employed within the decoding of a signal is significantly reduced be employing the inverse function of min*:min*− (and/or inverse function of max*:max*−) processing.

Claims

1. A decoder that is operable to perform min* processing by employing min*−

and min*+ processing, comprising;

a min*+ functional block that performs min*+ processing on a plurality of min* inputs thereby generating an intermediate variable, wherein the plurality of min* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel; and

a min*−

functional block that performs min*−

processing on each min* input of the plurality of min* inputs and the intermediate variable thereby generating a plurality of min* outputs, wherein the plurality of min* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal and at least one min* output of the plurality of min* outputs is employed when making a best estimate of the at least one bit encoded within the coded signal.

2. The decoder of claim 1, wherein the min*+ processing operates on two elements, the two elements comprising two min* inputs of the plurality of min* inputs.

3. The decoder of claim 1, wherein the min*−

processing operates on two elements, the two elements comprising one min* input of the plurality of min* inputs and the intermediate variable.

4. The decoder of claim 1, wherein the min*+ functional block performs a number of min*+ processes, the number of min*+ processes being less than a number of min* inputs of the plurality of min* inputs.

5. The decoder of claim 1, wherein the min*−

functional block performs a number of min*−

processes, the number of min*−

processes being equal to a number of min* inputs of the plurality of min* inputs.

6. The decoder of claim 1, wherein the min*+ processing comprises an inverse function of the min*−

processing on the plurality of min* inputs.

7. The decoder of claim 1, wherein the decoder is operable to perform straightforward min* processing on the plurality of min* inputs.

8. The decoder of claim 1, wherein the decoder is operable to perform intermediate result sharing min* processing.

9. The decoder of claim 1, wherein the decoder is contained within at least one of a satellite receiver, a high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

10. The decoder of claim 1, wherein the 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.

11. The decoder of claim 1, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.

12. A decoder that is operable to perform min* processing by employing min*−

and min*+ processing, comprising;

a min*+ functional block that sequentially performs min*+ processing on two min* input elements, the two min* input elements selected from a plurality of min* inputs, thereby generating an intermediate variable, wherein the plurality of min* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel; and

a min*−

functional block that sequentially performs min*−

processing on two elements, the two elements comprising one of the min* inputs of the plurality of min* inputs and the intermediate variable, thereby generating a plurality of min* outputs; and

wherein;

the plurality of min* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal and at least one min* output of the plurality of min* outputs is employed when making a best estimate of the at least one bit encoded within the coded signal;

the min*+ functional block performs a number of min*+ processes, the number of min*+ processes being less than a number of min* inputs of the plurality of min* inputs;

the min*−

functional block performs a number of min*−

processes, the number of min*−

processes being equal to the number of min* inputs of the plurality of min* inputs; and

the min*+ processing comprises an inverse function of the min*−

processing.

13. The decoder of claim 12, wherein the decoder is operable to perform straightforward min* processing on the plurality of min* inputs.

14. The decoder of claim 12, wherein the decoder is operable to perform intermediate result sharing min* processing on the plurality of min* inputs.

15. The decoder of claim 12, wherein the decoder is contained within at least one of a satellite receiver, at high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

16. The decoder of claim 12, wherein the 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.

17. The decoder of claim 12, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.

18. A decoder that is operable to perform max* processing by employing max*−

and max*+ processing, comprising;

a max*+ functional block that performs max*+ processing on a plurality of max* inputs thereby generating an intermediate variable, wherein the plurality of max* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel; and

a max*−

functional block that performs max*−

processing on each max* input of the plurality of max* inputs and the intermediate variable thereby generating a plurality of max* outputs, wherein the plurality of max* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal and at least one max* output of the plurality of max* outputs is employed when making a best estimate of the at least one bit encoded within the coded signal.

19. The decoder of claim 18, wherein the max*+ processing operates on two elements, the two elements comprising two max* inputs of the plurality of max* inputs.

20. The decoder of claim 18, wherein the max*−

processing operates on two elements, the two elements comprising one max* input of the plurality of max* inputs and the intermediate variable.

21. The decoder of claim 18, wherein the max*+ functional block performs a number of max*+ processes, the number of max*+ processes being less than a number of max* inputs of the plurality of max* inputs.

22. The decoder of claim 18, wherein the max*−

functional block performs a number of max*−

processes, the number of max*−

processes being equal to a number of max* inputs of the plurality of max* inputs.

23. The decoder of claim 18, wherein the max*+ processing comprises an inverse function of the max*−

processing.

24. The decoder of claim 18, wherein the decoder is operable to perform straightforward max* processing on the plurality of max* inputs.

25. The decoder of claim 18, wherein the decoder is operable to perform intermediate result sharing max* processing on the plurality of max* inputs.

26. The decoder of claim 18, wherein the decoder is contained within at least one of a satellite receiver, a high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

27. The decoder of claim 18, wherein the 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.

28. The decoder of claim 18, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.

29. A decoder that is operable to perform max* processing by employing max*−

and max*+ processing, comprising;

a max*+ functional block that sequentially performs max*+ processing on two max* input elements, the two max* input elements selected from a plurality of max* inputs, thereby generating an intermediate variable, wherein the plurality of max* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel; and

a max*−

functional block that sequentially performs max*−

processing on two elements, the two elements comprising one of the max* inputs of the plurality of max* inputs and the intermediate variable, thereby generating a plurality of max* outputs; and

wherein;

the plurality of max* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal and at least one max* output of the plurality of max* outputs is employed when making a best estimate of the at least one bit encoded within the coded signal;

the max*+ functional block performs a number of max*+ processes, the number of max*+ processes being less than a number of max* inputs of the plurality of max* inputs;

the max*−

functional block performs a number of max*−

processes, the number of max*−

processes being equal to the number of max* inputs of the plurality of max* inputs; and

the max*+ processing comprises an inverse function of the max*−

processing.

30. The decoder of claim 29, wherein the decoder is operable to perform straightforward max* processing.

31. The decoder of claim 29, wherein the decoder is operable to perform intermediate result sharing max* processing.

32. The decoder of claim 29, wherein the decoder is contained within at least one of a satellite receiver, a high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

33. The decoder of claim 29, wherein the 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.

34. The decoder of claim 29, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.

35. A min* processing method that employs min*−

and min*+ processing, the method comprising;

performing min*+ processing on a plurality of min* inputs thereby generating an intermediate variable, wherein the plurality of min* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel;

performing min*−

processing on each min* input of the plurality of min* inputs and the intermediate variable thereby generating a plurality of min* outputs, wherein the plurality of min* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal; and

employing at least one min* output of the plurality of min* outputs when decoding the coded signal, that is received by a communication device, to make a best estimate of the at least one bit encoded within the signal.

36. The method of claim 35, wherein the min*+ processing operates on two elements, the two elements comprising two min* inputs of the plurality of min* inputs.

37. The method of claim 35, wherein the min*−

processing operates on two elements, the two elements comprising one min* input of the plurality of min* inputs and the intermediate variable.

38. The method of claim 35, wherein the min*+ processing performs a number of min*+ processes, the number of min*+ processes being less than a number of min* inputs of the plurality of min* inputs.

39. The method of claim 35, wherein the min*−

processing performs a number of min*−

processes, the number of min*−

processes being equal to a number of min* inputs of the plurality of min* inputs.

40. The method of claim 35, wherein the min*+ processing comprises an inverse function of the min*−

processing.

41. The method of claim 35, further comprising performing straightforward min* processing on the plurality of min* inputs.

42. The method of claim 35, further comprising performing intermediate result sharing min* processing on the plurality of min* inputs.

43. The method of claim 35, wherein the method is performed within a decoder;

and

the decoder is contained within at least one of a satellite receiver, a high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

44. The method of claim 35, wherein the method is performed within a decoder;

the decoder is implemented within the communication device; and

the communication device 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.

45. The method of claim 35, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.

46. A max* processing method that employs max*−

and max*+ processing, the method comprising;

performing max*+ processing on a plurality of max* inputs thereby generating an intermediate variable, wherein the plurality of max* inputs is a first plurality of possible values that corresponds to at least one bit encoded within a coded signal that is received from a communication channel;

performing max*−

processing on each max* input of the plurality of max* inputs and the intermediate variable thereby generating a plurality of max* outputs, wherein the plurality of max* outputs is a second plurality of possible values that corresponds to the at least one bit encoded within the coded signal; and

employing at least one max* output of the plurality of max* outputs when decoding the coded signal, that is received by a communication device, to make a best estimate of the at least one bit encoded within the signal.

47. The method of claim 46, wherein the max*+ processing operates on two elements, the two elements comprising two max* inputs of the plurality of max* inputs.

48. The method of claim 46, wherein the max*−

processing operates on two elements, the two elements comprising one max* input of the plurality of max* inputs and the intermediate variable.

49. The method of claim 46, wherein the max*+ processing performs a number of max*+ processes, the number of max*+ processes being less than a number of max* inputs of the plurality of max* inputs.

50. The method of claim 46, wherein the max*−

processing performs a number of max*−

processes, the number of max*−

processes being equal to a number of max* inputs of the plurality of max* inputs.

51. The method of claim 46, wherein the max*+ processing comprises an inverse function of the max*−

processing.

52. The method of claim 46, further comprising performing straightforward max* processing on the plurality of max* inputs.

53. The method of claim 46, further comprising performing intermediate result sharing max* processing on the plurality of max* inputs.

54. The method of claim 46, wherein the method is performed within a decoder;

and

the decoder is contained within at least one of a satellite receiver, a high definition television (HDTV) set top box receiver, a base station receiver, a mobile receiver, a receiver, a mobile unit, a transceiver, and an advanced modulation satellite receiver.

55. The method of claim 46, wherein the method is performed within a decoder;

the decoder is implemented within the communication device; and

the communication device 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.

56. The method of claim 46, wherein:

the coded signal is a turbo coded signal, a parallel concatenated trellis coded modulated (PC-TCM) coded signal, a turbo trellis coded modulated (TTCM) coded signal, or a LDPC (Low Density Parity Check) coded signal;

if the coded signal is the turbo coded signal, the PC-TCM coded signal, or the TTCM coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of forward metrics (alphas), a plurality of backward metrics (betas), or a plurality of extrinsic values corresponding to the at least one bit encoded within the coded signal; and

if the coded signal is the LDPC coded signal, the first plurality of possible values or the second plurality of possible values is a plurality of check edge messages employed during LDPC decoding of the coded signal.