High-speed add-compare-select (ACS) circuit

• US 8,205,145 B2
• Filed: 11/05/2008
• Issued: 06/19/2012
• Est. Priority Date: 12/18/2002
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Lee, Seok-Jun, Zhu, Yuming, Goel, Manish
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US12/265,011
• Publication Number:
  US 20090089556A1
• Time in Patent Office: 1,322 Days
• Field of Search: 714786-792, 714794-799
• US Class Current: 714/796
• CPC Class Codes: G06F 7/22 Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: H03M 13/395 using a collapsed trellis, e.g. M-step algorithm, radix-n architectures with n>2
• CPC Class Codes: H03M 13/4107 implementing add, compare, select [ACS] operations

Abstract

A high speed add-compare-select (ACS) circuit for a Viterbi decoder or a turbo decoder has a lower critical path delay than that achievable using a traditional ACS circuit. According to one embodiment of the invention, the path and branch metrics are split into most-significant and least-significant portions, such portions separately added in order to reduce the propagation delay.

Claims

1. A high speed add-compare-select circuit comprising:

a plurality of path metrics;

a plurality of branch metrics, each branch metric associated with one of the plurality of path metrics;

a first plurality of adders configured to add a plurality of distinct metrics and generate a plurality of outputs therefrom, wherein the first plurality of adders are arranged in pairs, each pair of adders associating with a path metric and its associated branch metric, and each pair of adders comprising;

a first adder for generating a sum of a most significant portion of a path metric, a most significant portion of an associated branch metric, and a carry-in bit; and

a second adder for generating a sum of a least significant portion of the path metric and a least significant portion of the associated branch metric; and

comparing logic coupled to the outputs of the first plurality of adders, for generating selector control signals in response to the plurality of outputs; and

selector circuitry configured to generate the next path metric in response to the at least one path metric and further in response to the plurality of outputs.

2. The high-speed add-compare-select circuit of claim 1, wherein the carry-in bit corresponds to a carry-out value from a least-significant portion of a path metric from a previous time interval.

3. A high speed add-compare-select circuit comprising:

a first plurality of adders configured to add a plurality of distinct metrics and generate a plurality of outputs therefrom;

comparing logic coupled to the outputs of the first plurality of adders, for generating selector control signals in response to the plurality of outputs; and

selector circuitry configured to generate the next path metric in response to the at least one path metric and further in response to the plurality of outputs;

a plurality of path metrics;

a plurality of branch metrics, each branch metric associated with one of the plurality of path metrics, wherein the path metrics and branch metrics are expressed by multiple-bit values;

wherein the number of bits expressing path metrics being equal to or greater than the number of bits expressing the branch metrics;

and wherein the most significant portion and least significant portion of the path metrics differ in size from one another by at most one bit.

4. A high speed add-compare-select circuit comprising:

a first plurality of adders configured to add a plurality of distinct metrics and generate a plurality of outputs therefrom;

comparing logic coupled to the outputs of the first plurality of adders, for generating selector control signals in response to the plurality of outputs;

wherein the comparing logic comprises;

a first logic function for generating selector control signals applied to the control inputs of the first plurality of multiplexers, responsive to the outputs of the first plurality of adders; and

a second logic function for generating selector control signals applied to the control input of the second multiplexer, responsive to the outputs of the first plurality of multiplexers; and

selector circuitry configured to generate the next path metric in response to the at least one path metric and further in response to the plurality of outputs,

wherein the selector circuitry comprises;

a first plurality of multiplexers, each having inputs coupled to outputs of the first plurality of adders and having a control input; and

a second multiplexer having inputs coupled to outputs of the first plurality of multiplexers and having a control input.

5. A high speed add-compare-select circuit comprising:

a first plurality of adders configured to add a plurality of distinct metrics and generate a plurality of outputs therefrom;

comparing logic coupled to the outputs of the first plurality of adders, for generating selector control signals in response to the plurality of outputs;

wherein the comparing logic comprises;

a first logic function for generating selector control signals applied to the control inputs of the first plurality of multiplexers, responsive to the outputs of the first plurality of adders; and

a second logic function for generating selector control signals applied to the control inputs of the second plurality of multiplexers, responsive to the outputs of the first plurality of multiplexers; and

selector circuitry configured to generate the next path metric in response to the at least one path metric and further in response to the plurality of outputs,

wherein the selector circuitry comprises;

a first plurality of multiplexers, each having inputs coupled to outputs of the first plurality of adders and having a control input; and

a second plurality of multiplexers, each having inputs coupled to outputs of the first plurality of multiplexers and having a control input.

6. The high speed add-compare-select circuit of claim 5, wherein the first plurality of multiplexers comprises:

a first multiplexer having a first input coupled to the output of a first adder of a first pair of adders, and having a second input coupled to the output of a first adder of a second pair of adders;

a second multiplexer having a first input coupled to the output of a second adder of the first pair of adders, and having a second input coupled to the output of a second adder of the second pair of adders;

a third multiplexer having a first input coupled to the output of a first adder of a third pair of adders, and having a second input coupled to the output of a first adder of a fourth pair of adders; and

a second multiplexer having a first input coupled to the output of a second adder of the third pair of adders, and having a second input coupled to the output of a second adder of the fourth pair of adders;

and wherein the second plurality of multiplexers comprises;

a fifth multiplexer having a first input coupled to the output of the first multiplexer and a second input coupled to the output of the second multiplexer; and

a sixth multiplexer having a first input coupled to the output of the third multiplexer and a second input coupled to the output of the fourth multiplexer.