US 7,415,079 B2Granted

Decoder design adaptable to decode coded signals using min* or max* processing

AssigneeBroadcom Corporation

InventorsKelly Brian Cameron, Ba-Zhong Shen, Hau Thien Tran

Life of this patent

Estimating the term…

Loading patent…

Abstract

Decoder design adaptable to decode coded signals using min* or max* processing. A very efficient means of min* processing or max* processing may be performed within a communication device to assist in the very complex and cumbersome calculations that are employed when decoding coded signals. The types of coded signals that may be decoded using min* processing or max* processing are varied, and they include LDPC (Low Density Parity Check) coded signals, turbo coded signals, and TTCM (Turbo Trellis Coded Modulation) coded signals, among other coded signal types. Many of the calculations and/or determinations performed within min* processing or max* processing are performed simultaneously and in parallel of one another thereby ensuring very fast operation. In a finite precision digital implementation, when certain calculated bits of min* or max* processing are available, they govern selection of resultants from among multiple calculations and determinations made simultaneously and in parallel.

Claims92

Dependent claims

A min* (min star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a min* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
and
a logic OR gate that is operable to receive the output value from the min* log saturation block and an output of the log correction factor MUX;
and wherein:
an output of the input value selection MUX is a minimum input value selected from among the first input value and the second input value;
and
an output of the logic OR gate is a final log correction factor;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

14 more elements

A min* (min star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a min* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
and
a logic OR gate that is operable to receive the output value from the min* log saturation block and an output of the log correction factor MUX;
and wherein:
an output of the input value selection MUX is a minimum input value selected from among the first input value and the second input value;
an output of the logic OR gate is a final log correction factor;
during a first time period:
the subtraction block is operable to calculate the first plurality of LSBs of the difference between the first input value and the second input value;
during a second time period:
the subtraction block is operable to calculate the second plurality of LSBs of the difference between the first input value and the second input value;
the first log correction factor block is operable to determine the first log correction factor based on the first plurality of LSBs of the difference;
and
the second log correction factor block is operable to determine the second log correction factor based on the first plurality of LSBs of the difference;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min*processing, the final log correction factor is ln(1+e−|A−B|).

20 more elements

A min* (min star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a min* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
a logic OR gate that is operable to receive the output value from the min* log saturation block and an output of the log correction factor MUX, wherein:
an output of the input value selection MUX is a minimum input Value selected from among the first input value and the second input value;
and
an output of the logic OR gate is a final log correction factor;
and
a LUT (Look-Up Table) that includes a plurality of first log correction factors and a plurality of second log correction factors defined as a function of first plurality of LSBs of the difference;
and wherein:
the first log correction factor block looks up the first log correction factor from the LUT based on the first plurality of LSBs of the difference;
the second log correction factor block looks up the second log correction factor from the LUT based on the first plurality of LSBs of the difference;
each log correction factor of the plurality of first log correction factors and a plurality of second log correction factors is bit value of either a 0 or a 1 as defined by a single bit of precision;
the output value of the min* log saturation block is a 1 when each bit of the second plurality of LSBs of the difference is a 1;
the output value of the min* log saturation block is a 1 when each bit of the second plurality of LSBs of the difference is a 0;
the output value of the min* log saturation block is a 0 when at least one bit of the second plurality of LSBs of the difference is a 1 and at least one bit of the second plurality of LSBs of the difference is a 0;
and
the final log correction factor is a bit value of either a 0 or a 1 as defined by a single bit of precision;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

23 more elements

A max* (max star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a max* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
and
a logic AND gate that is operable to receive the output value from the max* log saturation block and an output of the log correction factor MUX;
and wherein:
an output of the input value selection MUX is a maximum input value selected from among the first input value and the second input value;
and
an output of the logic AND gate is a final log correction factor;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

14 more elements

A max* (max star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a max* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
and
a logic AND gate that is operable to receive the output value from the max* log saturation block and an output of the log correction factor MUX;
and wherein:
an output of the input value selection MUX is a maximum input value selected from among the first input value and the second input value;
an output of the logic AND gate is a final log correction factor;
during a first time period:
the subtraction block is operable to calculate the first plurality of LSBs of the difference between the first input value and the second input value;
during a second time period:
the subtraction block is operable to calculate the second plurality of LSBs of the difference between the first input value and the second input value;
the first log correction factor block is operable to determine the first log correction factor based on the first plurality of LSBs of the difference;
and
the second log correction factor block is operable to determine the second log correction factor based on the first plurality of LSBs of the difference;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

20 more elements

A max* (max star) circuit, the circuit comprising:

a subtraction block that is operable to calculate a difference between a first input value and a second input value;
a first log correction factor block that is operable to determine a first log correction factor based on a first plurality of LSBs (Least Significant Bits) of the difference;
a second log correction factor block that is operable to determine a second log correction factor based on the first plurality of LSBs of the difference;
a max* log saturation block whose output value is governed by a second plurality of LSBs of the difference;
a log correction factor MUX (Multiplexor) that is operable to receive the first log correction factor and the second log correction factor as inputs and whose selection is governed by an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
an input value selection MUX that is operable to receive the first input value and the second input value as inputs and whose selection is governed by an MSB of the difference;
a logic AND gate that is operable to receive the output value from the max* log saturation block and an output of the log correction factor MUX, wherein:
an output of the input value selection MUX is a maximum input value selected from among the first input value and the second input value;
and
an output of the logic AND gate is a final log correction factor;
and
a LUT (Look-Up Table) that includes a plurality of first log correction factors and a plurality of second log correction factors defined as a function of first plurality of LSBs of the difference;
the first log correction factor block looks up the first log correction factor from the LUT based on the first plurality of LSBs of the difference;
the second log correction factor block looks up the second log correction factor from the LUT based on the first plurality of LSBs of the difference;
each log correction factor of the plurality of first log correction factors and a plurality of second log correction factors is bit value of either a 0 or a 1 as defined by a single bit of precision;
the output value of the max* log saturation block is a 1 when each bit of the second plurality of LSBs of the difference is a 1;
the output value of the max* log saturation block is a 1 when each bit of the second plurality of LSBs of the difference is a 0;
and
the output value of the max* log saturation block is a 0 when at least one bit of the second plurality of LSBs of the difference is a 1 and at least one bit of the second plurality of LSBs of the difference is a 0;
and
the final log correction factor is a bit value of either a 0 or a 1 as defined by a single bit of precision;
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

23 more elements

A method for performing min* (min star) processing, the method comprising:

during a first time period:
calculating a first plurality of LSBs (Least Significant Bits) of a difference between a first input value and a second input value;
during a second time period:
calculating a second plurality of LSBs of the difference between the first input value and the second input value;
determining a first log correction factor based on the first plurality of LSBs of the difference;
determining a second log correction factor based on the first plurality of LSBs of the difference;
during a third time period:
selecting either the first log correction factor or the second log correction factor as being a final log correction value based on an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
and
selecting a minimum input value from among the first input value and the second input value based on an MSB of the difference;
and wherein:
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

13 more elements

A method for performing max* (max star) processing, the method comprising:

during a first time period:
calculating a first plurality of LSBs (Least Significant Bits) of a difference between a first input value and a second input value;
during a second time period:
calculating a second plurality of LSBs of the difference between the first input value and the second input value;
determining a first log correction factor based on the first plurality of LSBs of the difference;
determining a second log correction factor based on the first plurality of LSBs of the difference;
during a third time period:
selecting either the first log correction factor or the second log correction factor as being a final log correction value based on an MSB (Most Significant Bit) of the second plurality of LSBs of the difference;
and
selecting a maximum input value from among the first input value and the second input value based on an MSB of the difference;
and wherein:
the first input value is a finite precision number A;
the second input value is a finite precision number B;
in accordance with min* processing, the minimum input value is A or B;
and
in accordance with min* processing, the final log correction factor is ln(1+e−|A−B|).

13 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/865,456Filed 10 Jun 2004 · continuation in part
Priority: 12 Sep 2000
Published: US 2004/0034827 A12 Dec 2004
Granted: 19 Aug 2008
Term ends: Not estimatedThe source records don’t support an estimate.

Classification16 codes

H03M 13/3922
Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm,…:…
H03M 13/1102
Using multiple parity bits: codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
H03M 13/258
Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded…: with…
H03M 13/275
Using interleaving techniques: interleaver wherein the permutation pattern is obtained using a congruential operation of the type y=ax+b modulo c

Family

Application60/232,288Us provisional application · filed 12 Sep 2000
Application60/232,053Us provisional application · filed 12 Sep 2000
Application09/878,148Parent of this continuation-in-part · filed 8 Jun 2001
Application09/952,210Parent of this continuation-in-part · filed 12 Sep 2001
Application60/403,847Us provisional application · filed 15 Aug 2002
Application60/408,978Us provisional application · filed 6 Sep 2002
Application10/369,168Parent of this continuation-in-part · filed 19 Feb 2003
Application60/571,655Us provisional application · filed 15 May 2004
US 2004/0240590 A1Pre-grant publication · published 2 Dec 2004
US 7,023,934 B2Parent of this continuation-in-part
US 2002/0048329 A1Published application
US 2002/0061071 A1Published application
US 2004/0034827 A1Published application
US 7,107,511 B2Related patent
US 7,242,726 B2Related patent
US 7,415,079 B2This patent

From the US filing history. Foreign family members aren’t listed.