Vector comparator system for finding a peak number
View Patent ↗A comparator ( 231 ) for determining a peak number, representing a maximum or minimum of a set of numbers, includes a multi-element comparator ( 232 ) for comparing different pages of the set of numbers in a page comparison mode to output a candidate set of winning numbers, and for automatically switching to a leaf/tree search of the candidate set of winning numbers in an element comparison mode. Operating in parallel with the multi-element comparator ( 232 ), an index generation unit ( 233 ) processes flag/sign bits from the multi-element comparator in conjunction with state machine control logic ( 230 ) to keep track of the index/indices for the peak value. Upon completion of final stage, the index generation unit returns the absolute index ( 235 ) of the peak value.
1. A comparator for finding a peak value, comprising:
an N-element comparator for evaluating a plurality of up to M numbers by performing tree reductions on a candidate set of winning numbers to find the peak value in the candidate set of winning numbers, where M is greater than N; and
an index generator stage for processing index values corresponding to the plurality of up to M numbers to generate an absolute index value for the peak value.
2. The comparator of claim 1 , further comprising a memory storage device for storing the plurality of up to M numbers as an input data vector.
3. The comparator of claim 1 , where the N-element comparator compares in parallel a first page of reference numbers to successive N-element pages of the plurality of up to M numbers in a page comparison mode to generate the candidate set of winning numbers which contains the peak value.
4. The comparator of claim 3 , where the index generator stage comprises a page mode index circuit for storing page count values in an N-element page index register during the page comparison mode such that each element in the page index register stores a page count value identifying which page from the plurality of up to M numbers has a minimum or maximum value for that element.
5. The comparator of claim 1 , where the N-element comparator comprises:
a plurality of N multi-bit comparator circuits for generating an N-element comparison output from first and second comparison inputs;
a first multiplexer circuit for generating the first comparison input from successive N-element pages of the plurality of up to M numbers during a page comparison mode; and
a second multiplexer circuit for generating the second comparison input from the N-element comparison output during the page comparison mode.
6. The comparator of claim 5 , where the first and second multiplexer circuits generate the first and second comparison inputs from odd and even indexed elements in the N-element comparison output, respectively, during an element comparison mode where the plurality of N multi-bit comparator circuits generate an N/2 element comparison output from first and second comparison inputs.
7. The comparator of claim 1 , where the N-element comparator comprises:
a plurality of N multi-bit comparator circuits for generating an N/2 element comparison output from first and second comparison inputs;
an N-element comparator output register coupled to receive the N-element comparison output and to store the candidate set of winning numbers; and
first and second multiplexer circuits for generating the first and second comparison inputs from even and odd indexed elements in the N-element comparison output, respectively, during an element comparison mode, thereby enabling the N-element comparator to perform tree reductions on the candidate set of winning numbers to find the peak value in the candidate set of winning numbers.
8. The comparator of claim 1 , where the N-element comparator comprises a 128-element comparator for evaluating a plurality of D numbers, where D is selected from {2, 4, 8, 16, 32, 64, 128*I} and where I is a positive integer.
9. The comparator of claim 8 , where the index generator unit responds to an instruction call to return the absolute index value in T +L cycles, where L is a loading latency cycle count, and where T =(D/128) +7 when D >128, and where T =1 +log2(D) when D <128.
10. The comparator of claim 1 , where the index generator stage processes the index values using select bits generated at each comparison iteration of the N-element comparator to generate the absolute index value for the peak value.
11. The comparator of claim 1 , where the index generator stage comprises an element mode index circuit for storing element index values in an element index register to keep track of the peak value while tree reductions are performed on the candidate set of winning numbers.
12. The comparator of claim 1 implemented in a communication circuit, where the plurality of up to M numbers comprise a plurality of waveform signal samples that are processed by the N-element comparator and index generator stage to identify the peak value and corresponding absolute index value representing a localized waveform peak in the plurality of waveform signal samples.
13. A method for determining a maximum or minimum from an input number set in an electronic system, comprising:
initializing one or more registers in a comparator apparatus comprising an N-element comparator to find either a maximum or minimum from an input number set of up to M numbers, where M >N; and
evaluating the input number set with the N-element comparator over a plurality of clock cycles by performing tree reductions on a candidate set of input numbers to find the maximum or minimum in the candidate set of winning numbers while simultaneously processing index values corresponding to the candidate set of input numbers to generate a final index value for the maximum or minimum from the set of input numbers.
14. The method of claim 13 , where initializing one or more registers comprises:
storing a minimum N-element reference value at an output register of the N-element comparator when evaluating the input number set to find the maximum from the input number set, or
storing a maximum N-element reference value at the output register of the N-element comparator when evaluating the input number set to find the minimum from the input number set.
15. The method of claim 14 , where evaluating the input number set further comprises comparing in parallel the N-element reference value to one or more N-element pages of numbers from the input data set over K comparison cycles of a page comparison mode to generate an N-element candidate set of input numbers which contains the maximum or minimum from the input data set by loading first and second N-element comparison inputs to the N-element comparator, where the first N-element comparison input is fed back from the output register of the N-element comparator, and where the second N-element comparison input is fed in sequence the one or more N-element pages of numbers from the input data.
16. The method of claim 15 , where performing tree reductions comprises comparing adjacent numbers from the N-element candidate set of input numbers over log2(N) +1 comparison cycles of an element comparison mode to find the maximum or minimum in the N-element candidate set of input numbers.
17. The method of claim 15 , further comprising tracking over K comparison cycles of the page comparison mode which of the one or more N-element pages includes the maximum or minimum value for each element in the N-element candidate set of input numbers.
18. The method of claim 15 , further comprising storing page count values in an N-element page index register over K comparison cycles of the page comparison mode such that each element in the N-element page index register stores a page count value identifying which of the one or more N-element pages has a minimum or maximum value for that element.
19. The method of claim 18 , where performing tree reductions comprises comparing adjacent numbers from an N-element candidate set of input numbers over log2(N) +1 comparison cycles to shift the maximum or minimum in the N-element candidate set of input numbers to a right-most location of an output register at the N-element comparator, and where simultaneously processing index values comprises processing index values corresponding to the N-element candidate set of input numbers by using an element index register to track winning index values resulting from comparing adjacent numbers from the N-element candidate set of input numbers to thereby shift the index value for the maximum or minimum in the N-element candidate set of input numbers to a right-most location of the element index register.
20. The method of claim 19 , where evaluating the input number set to generate the final index value comprises computing the final index value from the winning index value stored in the right-most location of the element index register output register and from the corresponding page count value stored in the N-element page index register.
21. The method of claim 19 , where the method for determining a maximum or minimum from an input number set is implemented in a communication circuit, where the input number set of up to M numbers comprise a plurality of waveform signal samples that are processed to identify the maximum or minimum in the candidate set of winning numbers and corresponding final index value representing a localized waveform peak in the plurality of waveform signal samples.
22. An N-element vector comparator circuit for finding a peak number, comprising:
a vector register array storage device for storing an input data vector x =(x o , x 1 , . . . x M ) of up to M numbers, where M is greater than N;
a comparator circuit for generating a candidate set of winning numbers from the input data vector x during a page comparison mode and for performing tree reductions on the candidate set of winning numbers to find the peak value during an element comparison mode, where the comparator circuit comprises:
a plurality of N multi-bit comparator circuits for generating an N-element comparison output and N select signal outputs from first and second comparison inputs,
a first multiplexer circuit for generating the first comparison input from successive N-element pages of the input data vector x =(x o , x 1 , . . . x M ) during a page comparison mode, and for generating the first comparison input from odd-indexed elements of the N-element comparison output during an element comparison mode, and
a second multiplexer circuit for generating the second comparison input from the N-element comparison output during the page comparison mode, and for generating the second comparison input from even-indexed elements of the N-element comparison output during an element comparison mode; and
an index generator circuit for processing the N select signal outputs using control logic to track indices for each number in the input data vector x =(x o , x 1 , . . . x M ), where the index generator circuit comprises:
a page mode index circuit for storing page count values in an N-element page index register under control of the N select signal outputs during the page comparison mode such that each element in the page index register stores a page count value identifying which page from the input data vector x =(x o , x 1 , . . . x M ) has a minimum or maximum value for that element, and
an element mode index circuit for storing element index values in an element index register under control of the N select signal outputs during the element comparison mode to keep track of the element index value for the peak value in the candidate set of winning numbers while tree reductions are performed on the candidate set of winning numbers.