High speed add-compare-select for Viterbi decoder
View Patent ↗System and method of comparing-selecting state metric values for high speed Viterbi decoding. In an Add-Compare-Select (ACS) unit, a select control signal is produced by Boolean operations on comparator decision signals and used to control a multiplexer structure. The comparator decision signals can be generated in parallel by an array of comparators comparing all possible pairs of a set of state metrics values. The Boolean operations are predefined through Boolean algebra that uses the decision signals as variables and complies with restriction imposed by the selection criteria, e.g., to select an minimum or maximum value of the set of state metrics values. The Boolean operations are performed by a logic module implemented using basic logic gates, such as AND, OR and NOT. As a result, the multiplexer structure that receives the set of input values can output the optimum value responsive to the select control signal.
1. A method of using an Add-Compare Select (ACS) unit to select a state metric value from a plurality of state metric values in Viterbi decoding, said method comprising:
comparing said plurality of state metric values in all possible pairs by using comparators to produce a plurality of first decision signals, wherein a respective first decision signal is generated by a comparator and indicates a selected state metric value from a corresponding pair of state metric values;
generating a first select signal by using a logic circuit to perform Boolean operations on said plurality of first decision signals, wherein said logic circuit is coupled to said comparators; and
selecting a resultant state metric value from said plurality of state metric values by using a multiplexing structure based on said first select signal.
2. The method as described in claim 1 , wherein: the respective first decision signal indicates a smaller value between said corresponding pair of state metric values, and wherein said resultant state metric value is a minimum value among said plurality of state metric values.
3. The method as described in claim 1 , wherein said first select signal comprises a plurality of bits, wherein said generating comprises said logic circuit generating a respective bit of said first select signal by performing said Boolean operations on said plurality of first decision signals, and wherein said selecting comprises:
providing said first select signal to select lines of said multiplexer structure, wherein said multiplexer structure receives said plurality of state metric values as input; and
outputting said resultant state metric value from said multiplexer structure.
4. The method as described in claim 1 further comprising:
feeding selected pairs of said plurality of state metric values to input of a first plurality of 2:1 multiplexers;
in parallel with said generating said first select signal, sending first decision signals that are resulted from said comparing and are associated with said selected pairs to select lines of said first plurality of 2:1 multiplexers; and
outputting first candidate state metric values from said first plurality of 2:1 multiplexers.
5. The method as described in claim 4 , wherein said selecting said resultant state metric value comprises:
feeding said first candidate state metric values to input of said multiplexer structure;
sending said first select signal to select lines of said multiplexer structure; and
outputting said resultant metric value from said multiplexer structure.
6. The method as described in claim 5 , wherein said multiplexer structure comprises a hierarchy of 2:1 multiplexers, and wherein each select line in said multiplexer structure corresponds to a respective bit of said first select signal.
7. The method as described in claim 4 , wherein said selecting said resultant state metric value comprises:
feeding said first candidate state metric values to input of a second plurality of 2:1 multiplexers;
sending said first select signal to select lines of said second plurality of 2:1 multiplexers;
outputting second candidate state metric values from said second plurality of multiplexers;
comparing said second candidate state metric values in pairs to generate second decision signals; and
selecting said resultant state metric value from said second candidate metric values based on Boolean operations applied on said second decision signals.
8. An Add-Compare Select (ACS) unit for a high speed Viterbi decoder, said ACS unit comprises:
a plurality of first comparators configured to: compare a plurality of state metric values in all possible pairs; and produce a plurality of first decision signals, each resulting from comparing a respective pair of said all possible pairs;
a logic circuit coupled to said plurality of first comparators and configured to: perform Boolean operations on said plurality of first decision signals; and produce a first select signal; and
a multiplexer structure configured to: receive said plurality of state metric values as input; and output a resultant state metric value, wherein a select line of said multiplexer structure is controlled by said first select signal.
9. The ACS unit as described in claim 8 , wherein: said plurality of state metric values comprise N values; said plurality of first comparators comprise
N
(
N
-
1
)
2
comparators; said multiplexer structure comprises a N:1 multiplexer; and each bit of said first select signal is generated from said Boolean operations on said plurality of first decision signals.
10. The ACS unit as described in claim 8 , wherein said multiplexer structure comprises a hierarchy of multiplexers, wherein said hierarchy comprises:
first 2:1 multiplexers at a root level and configured to:
receive said plurality of state metric values as input; and
output first candidate state metric values responsive to select control by said first plurality of decision signals; and
an upper level multiplexer configured to output said resultant state metric value responsive to select control by said first select signal.
11. The ACS unit as described in claim 10 , wherein said Boolean operations are performed in parallel with said first 2:1 multiplexers outputting said first candidate state metric values.
12. The ACS unit as described in claim 10 , wherein said upper level multiplexer comprises multiple layers of second 2:1 multiplexers, and wherein further a select line of each second 2:1 multiplexer is coupled to an output of said Boolean operation.
13. The ACS unit as described in claim 8 , wherein said multiplexer structure comprises:
first level multiplexers configured to:
receive said plurality of state metric values as input; and
output first candidate state metric values responsive to select control by said first plurality of decision signals; and
second level multiplexers configured to:
receive said first candidate state metric values as input; and
output second first candidate state metric values responsive to select control by said first select signal, and
further comprising:
a plurality of second comparators configured to: compare said second candidate state metric values in pairs; and produce a plurality of second decision signals; and
third level multiplexers configured to:
receive said second candidate state metric values as input; and
output third candidate state metric values responsive to select control by said plurality of second decision signals.
14. The ACS unit as described in claim 13 , wherein said logic circuit is further configured to:
perform Boolean operations on said plurality of second decision signals; and
produce a second select signal,
and further comprising fourth level multiplexers configured to:
receive said third candidate state metric values as input; and
output said resultant state metric value responsive to select control by said second select signal.
15. A system for decoding convolution-coded data, said system comprising:
an Add-Compare Select (ACS) unit comprising:
a plurality of first comparators configured to compare a plurality of state metric values in all possible pairs; and produce a plurality of first decision signals, each resulting from comparing a respective pair of said all possible pairs;
a logic circuit coupled to said plurality of first comparators and configured to: perform Boolean operations on said plurality of first decision signals; and produce a first select signal; and
a multiplexer structure configured to: receive said plurality of state metric values as input; and output a resultant state metric value, wherein a select line of said multiplexer structure is controlled by said first select signal.
16. The system as described in claim 15 , further comprising:
a branch metric unit coupled to said ACS and configured to generate branch metric values, wherein said state metrics values are generated at said ACS unit based on said branch metric values according to a Viterbi algorithm; and
a survivor path decoder coupled to said ACS unit and configured to generate decoded bits according to said resultant state metric value.
17. The system as described in claim 15 , wherein said multiplexer structure comprises a hierarchy of multiplexers, wherein said hierarchy comprises:
first 2:1 multiplexers at a root level and configured to:
receive said plurality of state metric values as input; and
output first candidate state metric values responsive to select control by said first plurality of decision signals; and
an upper level multiplexer configured to output said resultant state metric value responsive to select control by said first select signal,
wherein said Boolean operations are performed concurrently with said first 2:1 multiplexers outputting said first candidate state metric values.
18. The system as described in claim 15 , wherein said multiplexer structure comprises:
a first level of multiplexers configured to:
receive said plurality of state metric values as input; and
output first candidate state metric values responsive to select control by said first plurality of decision signals; and
a second level of multiplexers configured to:
receive said first candidate state metric values as input; and
output second first candidate state metric values responsive to select control by said first select signal, and further comprising:
a plurality of second comparators configured to: compare said second candidate state metric values in pairs; and produce a plurality of second decision signals;
a third level of multiplexers configured to:
receive said second candidate state metric values as input; and
output third candidate state metric values responsive to select control by said plurality of second decision signals.
19. The system as described in claim 18 , wherein said logic circuit is further configured to:
perform Boolean operations on said plurality of second decision signals; and
produce a second select signal,
and further comprising a fourth level of multiplexers configured to:
receive said third candidate state metric values as input; and
output said resultant state metric value responsive to select control by said second select signal.