Turbo decoder employing max and max* map decoding

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to decoding of encoded and transmitted data in a communication system, and, more particularly, to maximum a priori (MAP) decoding algorithms.

2. Description of the Related Art

MAP algorithms are employed for processing a channel output signal applied to a receiver. MAP algorithms may be used for both detection (to reconstruct estimates for transmitted symbols) and decoding (to reconstruct user data). A MAP algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. A MAP algorithm forms a trellis corresponding to possible states (portion of received symbols or data in the sequence) for each received output channel sample per unit increment in time (e.g., clock cycle).

A trellis diagram may represent states, and transitions between states, of the Markov process spanning an interval of time. The number of bits that a state represents is equivalent to the memory of the Markov process. Thus, probabilities (sometimes of the form of log-likelihood ratio (LLR) values) are associated with each transition within the trellis, and probabilities are also associated with each decision for a sample in the sequence. These LLR values are also referred to as reliability information.

A processor implementing a MAP algorithm computes LLR values using α values (forward state probabilities for states in the trellis and also known as a forward recursion) and, β values (reverse state probabilities in the trellis and also known as a backward recursion), as described subsequently. The α values are associated with states within the trellis, and these α values are stored in memory. The processor using a MAP algorithm computes values of β, and the α values are then retrieved from memory to compute the final output LLR values.

The variable S is defined as the possible state (from a set of possible states {s_p}_p=0^M−1) of the Markov process at time i, y, is defined as the noisy channel output sample at time i, the sample sequence y^Kis defined as the sequence of length K of noisy channel output samples

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><msubsup><mrow><mo>{</mo><msub><mi>y</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>,</mo></mrow></math></maths>&lt;br /&gt; and y_l^Kis the noisy channel output sample y_lat time i in a given sequence y^Kof length K. For a data block of length K, probability functions at time i may be defined for the Markov process as given in equations (1) through (3):

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>α</mi><mi>s</mi><mi>i</mi></msubsup><mo>=</mo><mrow><mi>p</mi><mo>(</mo><mrow><mrow><mi>S</mi><mo>=</mo><mi>s</mi></mrow><mo>;</mo><msubsup><mi>y</mi><mi>i</mi><mi>K</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>β</mi><mi>s</mi><mi>i</mi></msubsup><mo>=</mo><mrow><mi>p</mi><mo>(</mo><mrow><mrow><msubsup><mi>y</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mi>K</mi></msubsup><mo>|</mo><mi>S</mi></mrow><mo>=</mo><mi>s</mi></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>γ</mi><mrow><msup><mi>s</mi><mi>′</mi></msup><mo>,</mo><mi>s</mi></mrow><mi>i</mi></msubsup><mo>=</mo><mrow><mrow><mi>p</mi><mo>(</mo><mrow><mrow><mi>S</mi><mo>=</mo><mi>s</mi></mrow><mo>;</mo><mrow><mrow><msubsup><mi>y</mi><mi>i</mi><mi>K</mi></msubsup><mo>|</mo><msup><mi>S</mi><mi>′</mi></msup></mrow><mo>=</mo><msup><mi>s</mi><mi>′</mi></msup></mrow></mrow><mo>)</mo></mrow><mo>.</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where S is the Markov process variable at time i, S′ is the Markov process variable at time i−1, s is the observed state of S of the Markov process at time i, and s′ is the observed state of S′ of the Markov process at time i−1.

The log-likelihood ratio (LLR) value L(u_l) for a user's symbol u_lat time i may then be calculated as given in equation (4):

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>u</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mi>log</mi><mo>⁡</mo><mrow><mo>(</mo><mfrac><mrow><mi>p</mi><mo>(</mo><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><mo>+</mo><mn>1</mn></mrow><mo>|</mo><msubsup><mi>y</mi><mi>i</mi><mi>K</mi></msubsup></mrow></mrow><mo>)</mo></mrow><mrow><mi>p</mi><mo>(</mo><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><mo>-</mo><mn>1</mn></mrow><mo>|</mo><msubsup><mi>y</mi><mi>i</mi><mi>K</mi></msubsup></mrow></mrow><mo>)</mo></mrow></mfrac><mo>)</mo></mrow></mrow><mo>.</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

Defining α_l¹and β_l¹from equations (1) and (2) as the forward and backward recursions (probabilities or state metrics) at time i in state s=l, respectively, and defining

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><msubsup><mi>γ</mi><mrow><mi>m</mi><mo>,</mo><mi>l</mi></mrow><mi>i</mi></msubsup></math></maths>&lt;br /&gt; as the branch metric associated with the transition from state m at time i−1 to state l at time i, then the forward recursion for states is given in equation (5):

<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mi>α</mi><mi>l</mi><mi>i</mi></msubsup><mo>=</mo><mrow><munder><mo>∑</mo><mrow><mi>l</mi><mo>∈</mo><mi>S</mi></mrow></munder><mo>⁢</mo><mrow><msubsup><mi>α</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>γ</mi><mrow><mi>m</mi><mo>,</mo><mi>l</mi></mrow><mi>i</mi></msubsup></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where lεS is a set of states at time i−1 which have a valid transition to the state l at time i.

Similarly, the backward recursion for states is given in equation (6):

<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msubsup><mi>β</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>=</mo><mrow><munder><mo>∑</mo><mrow><mi>m</mi><mo>∈</mo><mi>S</mi></mrow></munder><mo>⁢</mo><mrow><msubsup><mi>β</mi><mi>m</mi><mi>i</mi></msubsup><mo>⁢</mo><msubsup><mi>γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where mεS is a set of states at time i which have a valid transition from the state l to the state m at time i−1.

Once the forward and backward recursions for states are calculated, equation (4) is employed to generate the log-likelihood value (also known as reliability value) L(u_l) for each user symbol u_l, Thus, equation (4) may be re-written as given in equation (7):

<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>L</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>u</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mi>log</mi><mo>⁡</mo><mrow><mo>(</mo><mfrac><mrow><munder><mo>∑</mo><mrow><mrow><mo>(</mo><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mo>)</mo></mrow><mo>∈</mo><msup><mi>S</mi><mo>+</mo></msup></mrow></munder><mo>⁢</mo><mrow><msubsup><mi>α</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup><mo>⁢</mo><msubsup><mi>β</mi><mi>l</mi><mi>i</mi></msubsup></mrow></mrow><mrow><munder><mo>∑</mo><mrow><mrow><mo>(</mo><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mo>)</mo></mrow><mo>∈</mo><msup><mi>S</mi><mo>-</mo></msup></mrow></munder><mo>⁢</mo><mrow><msubsup><mi>α</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>⁢</mo><msubsup><mi>γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup><mo>⁢</mo><msubsup><mi>β</mi><mi>m</mi><mi>i</mi></msubsup></mrow></mrow></mfrac><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>7</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where a state pair (l, m)εS⁺ is defined as a pair that has a transition from state l at time i−1 to state m at time i corresponding to the user symbol u_l=“1”, and a state pair (l, m)εS⁻ is similarly defined as a pair that has a transition from state l at time i−1 to state m at time i corresponding to the user symbol u_l=“−1”.

A MAP algorithm may be defined by substituting A_m¹=ln(α_m¹), B_m¹=ln (β_m¹), and

<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><msubsup><mi>Γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup><mo>=</mo><mrow><mi>ln</mi><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup><mo>)</mo></mrow></mrow></mrow></math></maths>&lt;br /&gt; into the equations (5), (6), and (7). Such substitution is sometimes referred to as the log-MAP algorithm. Also, with the relation that ln(e^−x+e^−y) is equivalent to max(x,y)+ln(e^−|−y|+1), the forward and backward recursions of the log MAP algorithm may be described as in equations (8) and (9):

<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mtable><mtr><mtd><mrow><msubsup><mi>A</mi><mi>m</mi><mi>i</mi></msubsup><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>l</mi><mo>∈</mo><mi>S</mi></mrow></munder><mo>⁢</mo><mrow><mo>*</mo><mrow><mo>(</mo><mrow><msubsup><mi>A</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>+</mo><msubsup><mi>Γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>8</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><msubsup><mi>B</mi><mi>l</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>m</mi><mo>∈</mo><mi>S</mi></mrow></munder><mo>⁢</mo><mrow><mo>*</mo><mrow><mo>(</mo><mrow><msubsup><mi>B</mi><mi>m</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>+</mo><msubsup><mi>Γ</mi><mrow><mi>l</mi><mo>,</mo><mi>m</mi></mrow><mi>i</mi></msubsup></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>9</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where max* (x, y) is defined as max(x, y)+ln((e^−|x−y|)+1). Note that equations (8) and (9) may include more than two terms in the max*( ) operator, so a max*(x, y, . . . , z) operation may be performed as a series of pairs of max*(•,•) calculations. Max(x, y) is defined as the “max term” and ln((e^−|x−y|)+1) is defined as the “logarithmic correction term.”

SUMMARY OF THE INVENTION

In accordance with embodiments of the present invention, a turbo decoder employs max* term or max term maximum a priori (MAP) decoding of encoded data received from a channel. Initially, MAP decoding is iterative and employs max* term computation of log-likelihood values at each iteration. Max* term computation includes computation of a max term and a logarithmic correction term. A bypass algorithm switches from max* term computation to only max term computation in later iterations with little or no degradation in decoding performance. The iteration selected for switching is based on increasing intrinsic signal-to-noise ratio (SNR) of the iterative MAP decoding process. Since, in general, fewer computations are required for max term computation than for max* term computation, switching between max* and max allows for reduced power consumption of a particular decoder implementation.

In accordance with an exemplary embodiment of the present invention, a receiver iteratively decodes channel samples to generate decoded data by (a) applying at least one maximum a priori (MAP) decoding based on a max* term for one or more initial iterations of decoding, wherein the max* term comprises a max term and a logarithmic correction term; and (b) switching, for one or more subsequent iterations, to at least one MAP decoding based on a max term.

BRIEF DESCRIPTION OF THE DRAWINGS

Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which:

<figref idref="DRAWINGS">FIG. 1</figref> shows a transmitter passing an encoded and modulated signal through a channel to a receiver employing iterative decoding in accordance with one or more embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 2</figref> shows performance of bit error rate (BER) versus signal-to-noise ratio (SNR) for max* term log-MAP decoding when compared to max term log-MAP decoding;

<figref idref="DRAWINGS">FIG. 3</figref> shows performance as BER versus SNR of max* and max term switching algorithms in accordance with exemplary embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 4</figref> shows a butterfly structure for an Add-Compare-Select (ACS) circuit that may be employed to implement embodiments of the present invention;

<figref idref="DRAWINGS">FIG. 5</figref> shows registers in an ACS butterfly structure that implement a bypass scheme for max* and max term switching in accordance with embodiments of the present invention; and

<figref idref="DRAWINGS">FIG. 6</figref> shows a register including master/slave latch pair and a latch used in the ACS butterfly structure of <figref idref="DRAWINGS">FIG. 5</figref>.

DETAILED DESCRIPTION

In accordance with exemplary embodiments of the present invention, a receiver employs iterative decoding of a received, encoded signal. Iterative decoding employs a constituent maximum a priori (MAP) decoder for each constituent encoding of information of the encoded signal. Each MAP decoder employs a log-MAP algorithm for decoding the received, encoded signal. The log-MAP algorithm employs a max* term calculation for Log Likelihood Ratio (LLR) values based on updated forward recursive, reverse recursive, and branch metrics sequences. The max* term includes a max term and a logarithmic correction term. When iterations begin, the iterative decoder is in a first mode in which both the max term and logarithmic term are employed for calculation of LLR values. Eventually, an iteration of MAP decoding occurs in which the contribution of the logarithmic correction term has relatively negligible effect on decoding with respect to a predetermined threshold. At this iteration, the MAP decoder switches to a second mode in which only the max term is employed for calculation of LLR values.

<figref idref="DRAWINGS">FIG. 1</figref> shows transmitter <b>101</b> passing an encoded and modulated signal through channel <b>102</b> to receiver <b>103</b>. Transmitter <b>101</b> includes systematic turbo encoder <b>105</b> performing parallel concatenation of two identical constituent convolutional encoders separated by an interleaver. Each constituent convolutional encoder employs a recursive systematic code (RSC). For example, the overall code rate of the turbo encoder may be ⅓ when the code rate for each constituent convolutional encoder is ½. For a block of length K, the sequence

<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><msubsup><mrow><mo>{</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>m</mi><mi>i</mi></msub></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></math></maths>&lt;br /&gt; is defined as a sequence of information bits, and the sequences

<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><msubsup><mrow><mo>{</mo><msub><mi>p</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></math></maths>&lt;br /&gt; and

<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><msubsup><mrow><mo>{</mo><msubsup><mi>p</mi><mi>i</mi><mi>′</mi></msubsup><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></math></maths>&lt;br /&gt; are defined as the parity bit sequences of the first and the second constituent encoders, respectively.

The information bits, or data, are encoded into a sequence of symbols

<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><mo>(</mo><mrow><mi>denoted</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mrow><mo>{</mo><msub><mi>u</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mrow><mo>)</mo></mrow></math></maths>&lt;br /&gt; and transmitted as a modulated signal through channel <b>102</b>, such as a magnetic recording channel or wireless communication channel. While not shown explicitly in <figref idref="DRAWINGS">FIG. 1</figref>, transmitter <b>101</b> includes components and other systems well known in the art to modulate and transfer the signal to the channel.

Receiver <b>103</b> includes sampler/detector <b>110</b> and turbo decoder <b>111</b>. Sampler/detector <b>110</b> samples and detects the signal received from channel <b>102</b> to generate output channel samples. While not shown explicitly in <figref idref="DRAWINGS">FIG. 1</figref>, receiver <b>103</b> includes components and other systems well known in the art to receive and demodulate the signal from the channel. Turbo encoder <b>111</b> employs a decoding algorithm operating in accordance with one or more embodiments of the present invention. Turbo decoder <b>111</b> employs a turbo decoding scheme based on one or more MAP decoding algorithms and is employed by receiver <b>103</b> to reconstruct the user information or data from the received output channel samples.

Turbo decoder <b>111</b> includes constituent (log−)MAP decoders <b>113</b>(<b>1</b>)–<b>113</b>(N) and MAP decoding processor <b>112</b>. Turbo decoder <b>111</b> employs iterative decoding, (i.e., repetitively decoding the sequence of output channel samples with two or more iterations) with each iteration comprising a series of constituent MAP decoding operations. Each constituent MAP decoding of an iteration corresponds to a constituent encoding of the transmitter <b>101</b>. Each of MAP decoders <b>113</b>(<b>1</b>)–<b>113</b>(N) applies the corresponding constituent MAP decoding operation.

Thus, during an iteration of decoding, the received sequence is deinterleaved and each constituent encoding is reversed. In turbo decoding, each constituent MAP decoding operation (of MAP decoders <b>113</b>(<b>1</b>)–<b>113</b>(N)) generates soft decisions for received user bits and a set of LLR values corresponding to the soft decisions. Information generated by one constituent MAP decoding may be used by the next constituent MAP decoding operation. In accordance with the present invention, turbo decoder <b>111</b> includes MAP decoding processor <b>112</b>, which generates a select signal to MAP decoders <b>113</b>(<b>1</b>)–<b>113</b>(N). Based on the select signal, MAP decoders <b>113</b>(<b>1</b>)–<b>13</b>(N) switch between max* term and max term calculation for LLR values during MAP decoding.

For an additive white Gaussian noise (AWGN) channel having noise (power) variance

<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mrow><msup><mi>σ</mi><mn>2</mn></msup><mo>=</mo><mfrac><msub><mi>N</mi><mn>0</mn></msub><mn>2</mn></mfrac></mrow><mo>,</mo></mrow></math></maths>&lt;br /&gt; the observed output channel samples have the form of

<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mrow><mrow><msubsup><mrow><mo>{</mo><msub><mi>y</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>⁢</mo><msqrt><msub><mi>E</mi><mi>s</mi></msub></msqrt></mrow><mo>+</mo><msub><mi>n</mi><mi>i</mi></msub></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mrow><mo>,</mo><mrow><msubsup><mrow><mo>{</mo><msub><mi>t</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>=</mo><msubsup><mrow><mo>{</mo><mrow><mrow><msub><mi>p</mi><mi>i</mi></msub><mo>⁢</mo><msqrt><msub><mi>E</mi><mi>s</mi></msub></msqrt></mrow><mo>+</mo><msubsup><mi>n</mi><mi>i</mi><mi>′</mi></msubsup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mrow></mrow></math></maths><maths id="MATH-US-00015-2" num="00015.2"><math overflow="scroll"><mrow><mrow><mi>and</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msubsup><mrow><mo>{</mo><msubsup><mi>s</mi><mi>i</mi><mi>′</mi></msubsup><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></mrow><mo>=</mo><mrow><msubsup><mrow><mo>{</mo><mrow><mrow><msubsup><mi>p</mi><mi>i</mi><mi>′</mi></msubsup><mo>⁢</mo><msqrt><msub><mi>E</mi><mi>s</mi></msub></msqrt></mrow><mo>+</mo><msubsup><mi>n</mi><mi>i</mi><mi>″</mi></msubsup></mrow><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>.</mo></mrow></mrow></math></maths>&lt;br /&gt; As is known in the art, decoding by each constituent MAP decoder generates the LLR value L_lfor time i from equation (7), which may be considered to have three components as given in equation (10):

<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>L</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><mfrac><mrow><mn>2</mn><mo>⁢</mo><msqrt><msub><mi>E</mi><mi>s</mi></msub></msqrt></mrow><msup><mi>σ</mi><mn>2</mn></msup></mfrac><mo>⁢</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mo>+</mo><msub><mi>z</mi><mi>i</mi></msub><mo>+</mo><msub><mi>l</mi><mi>i</mi></msub></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>10</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where

<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><msubsup><mrow><mo>{</mo><msub><mi>L</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></math></maths>&lt;br /&gt; is the sequence of LLR values for

<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mrow><msubsup><mrow><mo>{</mo><msub><mi>u</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup><mo>.</mo></mrow></math></maths>&lt;br /&gt; In equation (10), the right hand term as a function of sample y_lcorresponds to the soft decision, z_lis the input a priori extrinsic information from the previous constituent MAP decoding operation (which may be zero for the first iteration), and

<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><msubsup><mrow><mo>{</mo><msub><mi>l</mi><mi>i</mi></msub><mo>}</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></msubsup></math></maths>&lt;br /&gt; is the sequence of newly generated extrinsic information for the next constituent MAP decoding operation.

Repetitive MAP decoding exhibits increased coding gain, which may be related to an increase in intrinsic signal-to-noise ratio (SNR) with each iteration. The average intrinsic SNR per iteration (AverageSNR(iter)) for a block of length K is given in equation (11):

<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><mrow><mi>AverageSNR</mi><mo>⁡</mo><mrow><mo>(</mo><mi>iter</mi><mo>)</mo></mrow></mrow><mo>=</mo>&lt;mi /&gt;<mo>⁢</mo><mrow><mrow><mi>StartSNR</mi><mo>⁡</mo><mrow><mo>(</mo><mn>0</mn><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mfrac><mn>1</mn><mrow><mn>2</mn><mo>⁢</mo><mi>K</mi><mo>⁢</mo><msqrt><msub><mi>E</mi><mi>s</mi></msub></msqrt></mrow></mfrac><mo>⁢</mo><mrow><mi>Q</mi><mo>(</mo><mrow><mi>iter</mi><mo>,</mo><mrow><mo>{</mo><msub><mi>m</mi><mi>i</mi></msub><mo>}</mo></mrow><mo>,</mo><mi>K</mi></mrow><mo>)</mo></mrow></mrow><mo>+</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow>&lt;mi /&gt;<mo>⁢</mo><mrow><mrow><mfrac><msup><mi>σ</mi><mn>2</mn></msup><mrow><mn>4</mn><mo>⁢</mo><msub><mi>E</mi><mi>s</mi></msub></mrow></mfrac><mo>⁢</mo><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mrow><mn>2</mn><mo>⁢</mo><mi>K</mi></mrow></mfrac><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>L</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><msubsup><mi>z</mi><mi>i</mi><mn>2</mn></msubsup></mrow></mrow><mo>)</mo></mrow></mrow><mo>,</mo></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mn>11</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where StartSNR(<b>0</b>) is the initial intrinsic SNR prior to the first iteration, and Q(iter, {m_l}, K) is a quality index defined as in equation (12):

<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>Q</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>iter</mi><mo>,</mo><mrow><mo>{</mo><msub><mi>m</mi><mi>i</mi></msub><mo>}</mo></mrow><mo>,</mo><mi>K</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>K</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mrow><msub><mi>m</mi><mi>i</mi></msub><mo>⁢</mo><msub><mi>z</mi><mi>i</mi></msub></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>12</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; where iter is the iteration number. These index values grow slowly over early iterations, grow very quickly during middle iterations, and eventually reach saturation at later iterations. In general, intrinsic SNR will increase with increasing iteration number due to the impact of extrinsic information.

As discussed with respect to equations (8) and (9), the calculation of LLR values may employ the max* term relationship of max*(x,y)=log(e^−x+e^−y)=max(x, y)+log(1+e^−|x−y|) Each constituent MAP decoder thus calculates the max* term by separate calculation of a max term (max(x,y)) and a logarithmic correction term (log(1+e^−|x−y|)). The determination of the max term is easily implemented using a comparator, and the value for the logarithmic correction term may typically be generated via a look-up table.

For the example of a turbo encoder, the trellis of the MAP decoding algorithm is a two-state trellis (i.e., M=2 with S_l={s₁, s₂}). For the two-state trellis in MAP decoding, the forward recursive sequence, backward recursive sequence and branch metric are denoted α(S_l), β(S_l) and γ(S_l¹, S_m), respectively, and for log-MAP decoding the forward recursive sequence, backward recursive sequence and branch metric are denoted α(S_l)=log{α(S_l)}, b(S_l)=log{β(S_l)}, c(S_l¹, S_m)=log{γ(S_l¹, S_m)}). Here, for S_k¹, the superscript j (e.g., j=1) of Markov process variable S indicates that the state of the variable is at time i–j, and the subscript k (e.g., k=l, m) indicates that the Markov process variable S is at observed state k.

Thus, for log-MAP decoding, the forward recursive sequence and backward recursive sequence are given in equations (14) and (15): &lt;br /&gt;<i>a</i>(<i>S</i>_l)=max*{[<i>a</i>(<i>S</i>_l¹)+<i>c</i>(<i>S</i>_l¹<i>, S</i>_l)], [<i>a</i>(<i>S</i>_l²)+<i>c</i>(<i>S</i>_l²<i>, S</i>_m)]},  (14)&lt;br /&gt;<i>b</i>(<i>S</i>_l)=max*{[<i>b</i>(<i>S</i>_l¹)+<i>c</i>(<i>S</i>_l<i>,S</i>_l¹)], [<i>b</i>(<i>S</i>_l²)+<i>c</i>(<i>S</i>_m<i>, S</i>_l²)]},  (15)&lt;br /&gt; Equations (14) and (15) may be implemented with the well-known Add-Compare-Select (ACS) circuit incorporating a logarithmic correction term provided from memory. The LLR value L_lat time i in accordance with the max* term of the log-MAP decoding algorithm may be computed as in equation (16):

<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>L</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><msubsup><mi>max</mi><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>+</mo><mn>1</mn></mrow></mrow><mo>*</mo></msubsup><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>c</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>,</mo><msub><mi>S</mi><mi>l</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>S</mi><mi>l</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow></mrow><mo>-</mo><mrow><msubsup><mi>max</mi><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>+</mo><mn>1</mn></mrow></mrow><mo>*</mo></msubsup><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>c</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>,</mo><msub><mi>S</mi><mi>l</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>S</mi><mi>l</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>16</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>&lt;br /&gt; and, when the logarithmic correction term is dropped from equation (16), the max term of the log-MAP calculation for the LLR value at time i is given in equation (17):

<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>L</mi><mi>i</mi></msub><mo>=</mo><mrow><mrow><msubsup><mi>max</mi><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>+</mo><mn>1</mn></mrow></mrow><mo>*</mo></msubsup><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>c</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>,</mo><msub><mi>S</mi><mi>l</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>S</mi><mi>l</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow></mrow><mo>-</mo><mrow><msubsup><mi>max</mi><mrow><msub><mi>u</mi><mi>i</mi></msub><mo>=</mo><mrow><mo>+</mo><mn>1</mn></mrow></mrow><mo>*</mo></msubsup><mo>⁢</mo><mrow><mrow><mo>{</mo><mrow><mrow><mi>a</mi><mo>⁡</mo><mrow><mo>(</mo><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>c</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msubsup><mi>S</mi><mi>l</mi><mn>1</mn></msubsup><mo>,</mo><msub><mi>S</mi><mi>l</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>S</mi><mi>l</mi></msub><mo>)</mo></mrow></mrow></mrow><mo>}</mo></mrow><mo>.</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>17</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

When the intrinsic SNR gets higher, the noise component N₀correspondingly gets smaller. As shown in equation (18), the logarithmic correction term has asymptotic behavior when the limit of the term is taken as N_ogoes to zero:

<maths id="MATH-US-00024" num="00024"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>lim</mi><mrow><msub><mi>N</mi><mn>0</mn></msub><mo>→</mo><mn>0</mn></mrow></msub><mo>⁢</mo><mrow><mi>log</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><msup><mi>ⅇ</mi><mrow><mrow><mo>-</mo><mfrac><mrow><mn>4</mn><mo>⁢</mo><msqrt><msub><mi>b</mi><mn>3</mn></msub></msqrt></mrow><msub><mi>N</mi><mn>0</mn></msub></mfrac></mrow><mo>⁢</mo><mrow><mo></mo><mrow><mover><mi>x</mi><mi>_</mi></mover><mo>-</mo><mover><mi>y</mi><mi>_</mi></mover></mrow><mo></mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mn>0.</mn></mrow></mtd><mtd><mrow><mo>(</mo><mn>18</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

Thus, the max* term and max term are asymptotically equivalent for high SNR since the logarithmic correction term tends to zero at high SNR. <figref idref="DRAWINGS">FIG. 2</figref> shows relative difference in performance of max* term log-MAP decoding when compared to max term log-MAP decoding. The relative difference is a comparison of bit error rate (BER) versus SNR. The comparison of <figref idref="DRAWINGS">FIG. 2</figref> is based on simulation results for one decoding iteration with a UMTS W-CDMA recursive 8-state constituent MAP encoder under an AWGN channel conditions. As shown in <figref idref="DRAWINGS">FIG. 2</figref>, the performance difference decreases as SNR increases. The performance difference between max* term and max term based turbo decoding under AWGN channel also accumulates over many decoding iterations. Turbo decoder <b>111</b> of <figref idref="DRAWINGS">FIG. 1</figref> may increase intrinsic SNR with increasing iteration number.

Increasing intrinsic SNR allows turbo decoder <b>111</b> to employ max* term computations at low intrinsic SNR for better decoding performance, and then to switch from max* term to max term computations at high intrinsic SNR to reduce processing operations of a given implementation. Since the number of computations required for max term computation is less than the number for max* term computation, switching to max term computation reduces the over all number of computations performed during iterative decoding. Fewer computations reduces the circuit activity factor of a given implementation, and, thus, reduces the overall power consumption of the implementation.

Formally, if Switch_ITER is a given iteration number, the turbo decoding algorithm (1) uses max* for constituent decoding for the first Switch_ITER iterations, then (2) uses max for each subsequent constituent decoding iteration. The switching point of Switch_ITER iterations may be selected based on simulation and calibration results. One skilled in the art would realize that the switching point may also be estimated in real-time with real-time channel measurements. For some embodiments of the present invention, provision may be made to switch back to max* term computation at subsequent iterations if certain performance criteria are not met.

Since computation of the correction term occurs at every state of the constituent MAP decoding algorithm trellis, switching between max* and max term computations may result in the following reduction in computations. If Max_ITER is the maximum iteration number and each constituent encoder (of transmitter <b>101</b>) has 8 states, the total number of max* logarithmic correction computations for both forward recursion and backward recursion is given in equation (19): &lt;br /&gt;8*<i>L</i>*Max_—<i>iter,</i>  (19)&lt;br /&gt; when all iterations employ max* term computation. By switching to max term computation after Switch_ITER iterations, the number of logarithmic correction computations is reduced to that of equation (20): &lt;br /&gt;8<i>*L</i>*Switch_—<i>iter,</i>  (20)&lt;br /&gt; and the percentage of computational saving is as given in equation (21):

<maths id="MATH-US-00025" num="00025"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mfrac><mrow><mi>Max_ITER</mi><mo>-</mo><mi>Switch_ITER</mi></mrow><mi>Max_ITER</mi></mfrac><mo>⁢</mo><mrow><mo>(</mo><mn>100</mn><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><mfrac><mi>Switch_ITER</mi><mi>Max_ITER</mi></mfrac></mrow><mo>)</mo></mrow><mo>⁢</mo><mrow><mo>(</mo><mn>100</mn><mo>)</mo></mrow></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>21</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

<figref idref="DRAWINGS">FIG. 3</figref> shows performance of max* and max term switching algorithms in accordance with exemplary embodiments of the present invention as BER versus SNR. The performance of algorithms shown in <figref idref="DRAWINGS">FIG. 3</figref> was generated by numerical simulation results for UMTS W-CDMA turbo codes with 10 iterations of turbo decoding assuming received output channel samples from an AWGN channel. In <figref idref="DRAWINGS">FIG. 3</figref>, the points plotted as S<b>1</b> are equivalent to Switch_ITER=1. Similarly, the points plotted as S<b>2</b>, S<b>3</b>, and S<b>4</b> are equivalent to Switch_ITER=2, Switch_ITER=3 and Switch_ITER=4, respectively. The dashed line plots BER versus SNR for max term-only log-MAP decoding, and the solid line plots BER versus SNR for max* term-only log-MAP decoding. As shown in <figref idref="DRAWINGS">FIG. 3</figref>, the BER performance degradation is negligible (i.e., close to max* term-only log-MAP decoding) if max* term log-MAP decoding occurs for the first 4 iterations, and then switches to max term log MAP decoding. Values for Switch_ITER may be determined using simulation similar to that shown in <figref idref="DRAWINGS">FIG. 3</figref> and may be adjusted via calibration through measurements over the actual channel. Max* and max term switching algorithms may be implemented in hardware with programmable parameters so that switching may occur at any iteration stage.

Given the max* and max term switching algorithms, the following describes exemplary circuit hardware implementations including logarithmic correction term bypass. Both max* and max term calculation may be implemented with Add-Compare-Select (ACS) circuitry (with or without correction term) having a butterfly structure well known in the art to reduce complexity of branch metric computation. <figref idref="DRAWINGS">FIG. 4</figref> shows a butterfly structure <b>400</b> that may be employed to implement embodiments of the present invention.

As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the butterfly structure <b>400</b> includes compare and select circuit <b>401</b>, look-up table (LUT) <b>402</b>, and adders <b>403</b>–<b>406</b>. To perform a corresponding max* term calculation, path metric memory is accessed to get path metric values PM(0) and PM(1), and current branch metric BM is calculated during the memory access operation. Path metric values PM(0) and PM(1) correspond to either 1) the forward recursive probabilities log(α) when moving forward through the trellis or 2) backward recursive probabilities log(β) when moving backward through the trellis. BM corresponds to the accumulated branch metric log(γ). Adder <b>403</b> generates PM(0)+BM, adder <b>404</b> generates PM(1)−BM, and adder <b>405</b> generates PM(0)−PM(1)+2BM. Compare and select circuit <b>401</b> compares input values PM(0)+BM and PM(1)−BM, and then selects the maximum value of the two input values. The value PM(0)−PM(1)+2BM from adder <b>405</b> is employed to address a value in LUT 402 corresponding to the appropriate logarithmic correction term. The logarithmic correction term from LUT <b>402</b> is combined with the maximum value selected by compare and select circuit <b>401</b> to generate the updated path metric value.

When max term calculation is performed, the lower branch (LUT <b>402</b>, adder <b>405</b>, and adder <b>406</b>) of butterfly structure <b>400</b> is not required since the logarithmic correction term is not used. The lower branch may be bypassed by setting the output value of LUT <b>402</b> to zero. Alternatively, bypass circuitry may be included in butterfly structure <b>400</b>, such as shown in <figref idref="DRAWINGS">FIGS. 5 and 6</figref>.

<figref idref="DRAWINGS">FIG. 5</figref> shows registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>) and <b>500</b>(<i>c</i>) added to ACS butterfly structure <b>400</b> (<figref idref="DRAWINGS">FIG. 4</figref>) to support a bypass scheme for max* and max term switching in accordance with embodiments of the present invention. <figref idref="DRAWINGS">FIG. 6</figref> shows a register <b>500</b> including (1) master/slave latch pair <b>601</b> having latches <b>605</b> and <b>606</b>, and (2) latch <b>602</b>. Latch <b>606</b> and latch <b>602</b> each latch the value of latch <b>605</b> to its output port (Q and Q′). The output value of latch <b>602</b> may be cleared separately from that of latch <b>606</b> via reset signal R′ (CL is the system clock signal and D is the input signal to register <b>500</b>). Latches <b>602</b> and <b>606</b> allow register <b>500</b> to provide two different output values at output ports Q and Q′ from register <b>500</b> since the port values Q and Q′ may be separately cleared.

Returning to <figref idref="DRAWINGS">FIG. 5</figref>, output port Q of registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>), and <b>500</b>(<i>c</i>) provide PM(0), PM(1), and BM, respectively, to adders <b>403</b> and <b>404</b>. Output port Q′ of registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>), and <b>500</b>(<i>c</i>) provide PM(0), PM(1), and BM, respectively, to adder <b>405</b>. During max* term computation, the value of output port Q′ corresponds to the value of output port Q in registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>), and <b>500</b>(<i>c</i>). Thus, adder <b>405</b> generates the address for LUT <b>402</b> to provide the logarithmic correction term. When the value of Switch_ITER is reached, the signal R′ (related to the externally generated signal “select” as described subsequently) clears the value of output port Q′ in registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>), and <b>500</b>(<i>c</i>), setting the values of PM(0), PM(1), and BM applied to adder <b>405</b> to zero. Consequently, the output of adder <b>405</b> is set to zero, generating a zero-valued logarithmic correction term from LUT <b>402</b>.

In addition to generating a zero-valued logarithmic correction term, the lower branch of ACS butterfly structure <b>400</b> may be disabled by employing optional OR gate <b>550</b>, AND gate <b>551</b>, and mux <b>552</b>. OR gate <b>550</b> receives the latch reset signal R as well as a select signal. The output of OR gate <b>550</b> is high when either the reset signal or the select signal is high. The select signal is employed to disable the lower branch and is enabled (set high) when the value of Switch_TER is reached. Once enabled, the select signal appears at the output of OR gate <b>350</b> as R′, resetting the latch for output value Q′ of registers <b>500</b>(<i>a</i>), <b>500</b>(<i>b</i>), and (<b>500</b>(<i>c</i>) to zero. In addition, the output signal of compare and select circuit <b>401</b> is split and provided to both AND gate <b>551</b> and mux <b>552</b>. AND gate <b>551</b> also receives the negation of the select signal. AND gate <b>551</b> provides as its the output value the output value of compare and select circuit <b>401</b> when the select signal is disabled (i.e., low), and a zero when the select signal is enabled. When select is disabled, adder <b>406</b> receives the value of compare and select circuit <b>401</b> from AND gate <b>551</b> as well as the logarithmic correction term from LUT <b>402</b>, adds the values, and provides the combined value to mux <b>552</b>. When select is enabled, adder <b>406</b> also receives a zero signal from AND gate <b>551</b>. When the select signal is disabled, mux selects the output of adder <b>405</b> as the output of the ACS butterfly structure. When the select signal is enabled, mux <b>552</b> selects the output of compare and select circuit <b>401</b> as the output of the ACS butterfly structure.

Max* and max term switching in accordance with exemplary embodiments of the present invention may provide the following advantages. First, reducing the number of computations reduces the power consumption of a given implementation. Second, disabling/bypassing the generation of the logarithmic correction term may allow for faster circuit operation.

The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium or carrier, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits.

It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the scope of the invention as expressed in the following claims.