Method of normalization of forward metric (alpha) and reverse metric (beta) in a map decoder

• US 7,440,521 B2
• Filed: 09/12/2001
• Issued: 10/21/2008
• Est. Priority Date: 09/12/2000
• Status: Expired due to Fees

• Current Assignee: Broadcom Corporation (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Tran, Hau Thien, Cameron, Kelly B.
• Primary Examiner(s): Ghayour; Mohammed
• Assistant Examiner(s): TORRES, JUAN A
• Application Number:
  US09/952,212
• Publication Number:
  US 20020048331A1
• Time in Patent Office: 2,596 Days
• Field of Search: 375/316, 375/341
• 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

In a normalization process, overflow occurring in limited size registers, holding the alpha or beta values in a map decoder, may be overcome by subtracting a constant value from all of the alpha or beta values when they reach a limit. Because subtracting a constant value may slow down the computation, detection of a constant value may occur on one decoding cycle and normalization on the succeeding decoding cycle. A multiplexor type circuit can be used to direct either zeros, in the normalization case, or a most significant bit(s), in computations without normalization, into the register holding the alpha or beta values. To minimize the impact on the computation by the normalization process, the multiplexor circuit can be set by the previous decoder cycle so that the computation does not have to wait for the multiplexor to be set to normalization or normal computation.

Claims

1. A method of normalizing alpha (α

) values (forward metrics) in a map decoder that is operable to decode a signal, the method comprising;

storing the α

values for a current decoder cycle, in a register;

feeding back the stored α

values for use in α

update calculation for the current decoder cycle;

performing detection of a normalization condition that is indicated when all the stored α

values have reached a certain value for the current decoder cycle, wherein the α

update calculation and the performing detection of the normalization condition are performed in parallel with one another such that the detection of the normalization condition is performed during a same time period as the α

update calculation for the current decoder cycle;

subtracting a constant value from all the α

values on a next decoder cycle; and

employing soft information that is generated, at least in part, from the α

values of a most recent decoder cycle, when decoding the signal to make an estimate of an information bit within the signal.

2. The method of claim 1 wherein detecting when all α

values have reached a certain value comprises determining when a most significant bit (MSB) of all the α

values is set.

3. The method of claim 2 wherein determining when the MSB of all the α

values is set comprises ANDing the MSBs of all the α

values.

4. The method of claim 1 wherein subtracting a constant value from all the α

values on a next decoder cycle comprises subtracting a value equal to a most significant bit (MSB) of the α

values.

5. The method of claim 4 wherein subtracting a value equal to the MSB of the α

values comprises resetting the MSB of all the α

values.

6. The method of claim 5 wherein resetting the MSB of all the α

values comprises;

using a detection of all the MSBs of all the α

values being equal to one to set a path of a multiplexer on a first decoding cycle; and

accepting a zero value as the MSB of all the α

values on a next decoding cycle.

7. An apparatus for normalizing alpha (α

) values (forward metrics) in a map decoder that is operable to decode a signal, the apparatus comprising;

a register for storing the α

values for a current decoder cycle;

a feedback path that is operable to provide the stored α

values to a plurality of α

update calculation blocks;

an AND gate coupled to the output of the register for detecting when all the stored α

values have reached a certain value for the current decoder cycle, wherein the AND gate operates in parallel with the plurality of α

update calculation blocks such that the AND gate performs normalization during a same time period in which the plurality of α

update calculation blocks updates the α

values during the current decoder cycle;

a multiplexor coupled to the output of the AND gate for subtracting a constant value from all the α

values on a next decoder cycle and outputting the subtracted α

values to the register; and

an output processor that is operable to employ soft information that is generated, at least in part, from the α

values of a most recent decoder cycle, when decoding the signal to make an estimate of an information bit within the signal.

8. The apparatus of claim 7 wherein the AND gate receives as an input most significant bits (MSBs) of all the α

values.

9. The apparatus of claim 7 wherein:

the multiplexer receives a signal on a first decoding cycle to direct either a zero or a most significant bit (MSB) through the multiplexer to an output of the multiplexer; and

further comprising;

an α

register that accepts the output of the multiplexer as the MSB on a next decoding cycle.

10. A method of normalizing beta (β

) values (reverse metrics) in a map decoder that is operable to decode a signal, the method comprising;

storing the β

values for a current decoder cycle, in a register;

feeding back the stored β

values for use in β

update calculation for the current decoder cycle;

performing detection of a normalization condition that is indicated when all the stored β

values have reached a certain value for the current decoder cycle, wherein the β

update calculation and the performing detection of the normalization condition are performed in parallel with one another such that the detection of the normalization condition is performed during a same time period as the β

update calculation for the current decoder cycle;

subtracting a constant value from all the β

values on a next decoder cycle; and

employing soft information that is generated, at least in part, from the β

values of a most recent decoder cycle, when decoding the signal to make an estimate of an information bit within the signal.

11. The method of claim 10 wherein detecting when all β

values have reached a certain value comprises determining when a most significant bit (MSB) of all the β

values is set.

12. The method of claim 11 wherein determining when the MSB of all the β

values is set comprises ANDing the MSBs of all the β

values.

13. The method of claim 10 wherein subtracting a constant value from all the β

values on a next decoder cycle comprises subtracting a value equal to a most significant bit (MSB) of the β

values.

14. The method of claim 13 wherein subtracting a value equal to the MSB of the β

values comprises reselling the MSB of all the β

values.

15. The method of claim 14 wherein resetting the MSB of all the β

values comprises;

using a detection of all the MSBs of all the β

values being equal to one to set a path of a multiplexer on a first decoding cycle; and

accepting a zero value as the MSB of all the β

values on a next decoding cycle.

16. An apparatus for normalizing beta (β

) values (reverse metrics) in a map decoder that is operable to decode a signal, the apparatus comprising;

a register for storing the β

values for a current decoder cycle;

a feedback path that is operable to provide the stored β

values to a plurality of β

update calculation blocks;

an AND gate coupled to the output of the register for detecting when all the stored β

values have reached a certain value for the current decoder cycle, wherein the AND gate operates in parallel with the plurality of α

update calculation blocks such that the AND gate performs normalization during a same time period in which the plurality of β

update calculation blocks updates the β

values during the current decoder cycle;

a multiplexor coupled to the output of the AND gate for subtracting a constant value from all the β

values on a next decoder cycle and outputting the subtracted β

values to the register; and

an output processor that is operable to employ soft information that is generated, at least in part, from the β

values of a most recent decoder cycle, when decoding the signal to make an estimate of an information bit within the signal.

17. The apparatus of claim 16 wherein the AND gate receives as an input most significant bits (MSBs) of all the β

values.

18. The apparatus of claim 16 wherein:

the multiplexer receives a signal on a first decoding cycle to direct either a zero or a most significant bit (MS B) through the multiplexer to an output of the multiplexer; and

further comprising;

a β

register that accepts the output of the multiplexer as the MSB on a next decoding cycle.