Sorting networks using unary processing

Patent metadata

Field	Value
Publication number	US-11475288-B2
Application number	US-201916674488-A
Country	US
Kind code	B2
Filing date	Nov 5, 2019
Priority date	Nov 5, 2018
Publication date	Oct 18, 2022
Grant date	Oct 18, 2022

Abstract

Various implementations of sorting networks are described that utilize time-encoded data signals having encoded values. In some examples, an electrical circuit device includes a sorting network configured to receive a plurality of time-encoded signals. Each time-encoded signal of the plurality of time-encoded signals encodes a data value based on a duty cycle of the respective time-encoded signal or based on a proportion of data bits in the respective time-encoded signal that are high relative to the total data bits in the respective time-encoded signal. The sorting network is also configured to sort the plurality of time-encoded signals based on the encoded data values of the plurality of time-encoded signals.

First claim

The invention claimed is:

1. A device including:
a sorting network implemented in a hardware circuit configured to:
receive a plurality of time-encoded signals, wherein each time-encoded signal of the plurality of time-encoded signals encodes a data value based on a duty cycle of the respective time-encoded signal or based on a proportion of data bits in the respective time-encoded signal that are high relative to the total data bits in the respective time-encoded signal; and
sort the plurality of time-encoded signals based on the encoded data values of the plurality of time-encoded signals.

2. The device of claim 1 ,
wherein the sorting network comprises a plurality of compare-and-swap blocks, and
wherein each compare-and-swap block of the plurality of compare-and-swap blocks is configured to receive and sort two time-encoded signals of the plurality of time-encoded signals based on values encoded by the two time-encoded signals.

3. The device of claim 2 , wherein each compare-and-swap block of the plurality of compare-and-swap blocks is configured to:
compare the two time-encoded signals; and
swap the two time-encoded signals based on comparing the two time-encoded signals.

4. The device of claim 2 , wherein each compare-and-swap block of the plurality of compare-and-swap blocks comprises:
a first circuit configured to output a first time-encoded signal of the two time-encoded signals that represents a larger data value; and
a second circuit configured to output a second time-encoded signal of the two time-encoded signals that represents a smaller data value.

5. The device of claim 4 ,
wherein the first circuit includes an OR gate, and
wherein the second circuit includes an AND gate.

6. The device of claim 1 , further comprising an analog-to-time converter configured to convert a first plurality of analog signals generated by a sensor to the plurality of time-encoded signals.

7. The device of claim 6 , wherein the analog-to-time converter comprises:
a ramp generator configured to convert an analog signal to a sawtooth signal or a triangle signal; and
an analog comparator configured to convert the sawtooth signal or the triangle signal to a time-encoded signal.

8. The device of claim 1 , further comprising a time-to-analog converter configured to convert time-encoded signals outputted by the sorting network to a second plurality of analog signals.

9. The device of claim 1 , wherein each time-encoded signal of the plurality of time-encoded signals comprises a time-encoded pulse signal or a pulse-width modulated signal.

10. The device of claim 1 ,
wherein each time-encoded signal of the plurality of time-encoded signals encodes a respective data value as a function of the duty cycle of a clock cycle, and
wherein each time-encoded signal includes a high phase and a low phase during each clock cycle.

11. The device of claim 1 , wherein the sorting network is part of an artificial neural network.

12. The device of claim 1 , further comprising a thresholding circuit configured to:
receive a single time-encoded signal of the plurality of time-encoded signals outputted by the sorting network;
output a first result in response to determining that encoded data value of the single time-encoded signal is greater than or equal to a threshold value; and
output a second result in response to determining that the encoded data value is less than the threshold value.

13. A method comprising:
receiving, with circuitry, a plurality of time-encoded signals, wherein each time-encoded signal of the plurality of time-encoded signals encodes a data value based on a duty cycle of the respective time-encoded signal or based on a proportion of data bits in the respective time-encoded signal that are high relative to the total data bits in the respective time-encoded signal; and
sorting, with the circuitry, the plurality of time-encoded signals based on the encoded data values of the plurality of time-encoded signals.

14. The method of claim 13 , wherein sorting the plurality of time-encoded signals includes:
comparing two time-encoded signals of the plurality of time-encoded signals; and
swapping the two time-encoded signals based on comparing the two time-encoded signals.

15. The method of claim 13 , further comprising outputting the plurality of time-encoded signals in a sorted order.

16. An electrical circuit device comprising:
a sorting network circuit configured to receive a set of input bits, wherein the data bits of the set of input bits represent a numerical value based on a probability that any data bit in the set of input bits is high,
wherein the sorting network circuit is further configured to sort the set of input bits to produce a set of sorted bits, wherein the data bits of the set of sorted bits deterministically encode the numerical value based on a proportion of the data bits in the set of sorted bits that are high relative to the total data bits in the set of sorted bits; and
a thresholding circuit configured to:
receive a single data bit of the set of sorted bits;
output a first result in response to determining that the numerical value is greater than or equal to a threshold value; and
output a second result in response to determining that the numerical value is less than the threshold value.

17. The electrical circuit device of claim 16 ,
wherein the sorting network comprises a plurality of compare-and-swap blocks to sort the set of input bits, and
wherein each compare-and-swap block of the plurality of compare-and-swap blocks is configured to receive two data bits of the set of input sets and sort the two data bits based on values of the two data bits.

18. The electrical circuit device of claim 17 , wherein each compare-and-swap block of the plurality of compare-and-swap blocks comprises:
a first circuit configured to output a first data bit of the two data bits that represents a larger data value; and
a second circuit configured to output a second data bit of the two data bits that represents a smaller data value.

19. The electrical circuit device of claim 18 ,
wherein the first circuit includes an OR gate, and
wherein the second circuit includes an AND gate.

20. The electrical circuit device of claim 16 , wherein the sorting network and thresholding circuit are part of an artificial neural network.

Assignees

• Univ Minnesota

Inventors

• Najafi Mohammadhassan
• Lilja David J
• Riedel Marcus
• Bazargan Kiarash

Classifications

• G06N3/065 Primary

  Analogue means · CPC title

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F7/20

  Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets · CPC title

• G06F2207/4824

  Neural networks · CPC title

• G06N20/20

  Ensemble learning · CPC title