High quality down-sampling for deterministic bit-stream computing

Patent metadata

Field	Value
Publication number	US-10996929-B2
Application number	US-201916352933-A
Country	US
Kind code	B2
Filing date	Mar 14, 2019
Priority date	Mar 15, 2018
Publication date	May 4, 2021
Grant date	May 4, 2021

Abstract

This disclosure describes techniques for processing data bits using pseudo-random deterministic bit-streams. In some examples, a device includes a pseudo-random bit-stream generator configured to generate bit combinations encoding first and second numerical values based on a proportion of the data bits in the sequence that are high relative to the total data bits in the sequence. The device also includes a stochastic computational unit configured to perform a computational operation on the bit combinations and produce an output bit-stream having a set of data bits indicating a result of the computational operation, wherein the data bits of the output bit-stream represent the result based on a probability that any data bit in the set of data bits of the output bit-stream is high.

First claim

The invention claimed is:

1. A device comprising:
an integrated circuit comprising a computational circuit configured to process at least a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value,
wherein the computational circuit comprises:
a deterministic pseudo-random bit-stream generator configured to generate bit combinations representing a first bit sequence and a second bit sequence that deterministically encode the first and second numerical values, respectively, based on a proportion of the data bits in the sequence that are high relative to the total data bits in the sequence, wherein a subset of the bit combinations pairs a data bit of the first bit sequence with multiple different data bits of the second bit sequence, and wherein the bit combinations are generated such that high data bits of the first and second bit sequence are pseudo-randomly distributed throughout the first and second bit sequences, and
a stochastic computational circuit configured to:
perform a computational operation on the bit combinations; and
produce an output bit-stream having a set of data bits indicating a result of the computational operation, wherein the data bits of the output bit-stream represent the result based on a probability that any data bit in the set of data bits of the output bit-stream is high.

2. The device of claim 1 , wherein, prior to performing the computational operation on the bit combinations, the stochastic computational circuit is configured to down sample the first bit sequence and the second bit sequence represented by the bit combinations generated by the deterministic pseudo-random bit-stream generator.

3. The device of claim 1 ,
wherein the high data bits are pseudo-randomly distributed throughout the first bit sequence based on a first function comparing two or more data bits of the first bit sequence to generate a next bit of the first bit sequence, and
wherein the high data bits are pseudo-randomly distributed throughout the second bit sequence based on a second function comparing two or more data bits of the second bit sequence to generate a next bit of the second bit sequence, the second function being different from the first function.

4. The device of claim 1 ,
wherein the high data bits are pseudo-randomly distributed throughout the first bit sequence based on a first function and based on a first seed, and
wherein the high data bits are pseudo-randomly distributed throughout the second bit sequence based on a second function based on a second seed, wherein:
the second seed is different from the first seed; or
the second function is different from the first function.

5. The device of claim 1 , wherein the deterministic pseudo-random bit-stream generator comprises:
a first pseudo-random number generator configured to generate a first pseudo-random number;
a second pseudo-random number generator configured to generate a second pseudo-random number;
a first comparator configured to generate the first bit sequence based on the first pseudo-random number and a first constant number; and
a second comparator configured to generate the second bit sequence based on the second pseudo-random number and a second constant number.

6. The device of claim 5 ,
wherein each of the first pseudo-random number, the second pseudo-random number, the first constant number, and the second constant number comprises an N-bit binary number, and
wherein each of the first comparator and the second comparator comprises an N-bit comparator configured to generate the respective bit sequence based on whether the respective pseudo-random number is greater than the respective constant number.

7. The device of claim 5 ,
wherein the first pseudo-random number generator comprises a first linear-feedback shift register (LFSR) configured to generate the first pseudo-random number based on a first function, and
wherein the second pseudo-random number generator comprises a second LFSR configured to generate the second pseudo-random number based on a second function that is different from the first function.

8. The device of claim 5 ,
wherein the first pseudo-random number generator comprises a first linear-feedback shift register (LFSR) is configured to receive a clock signal and generate new pseudo-random numbers based on the clock signal, and
wherein the second pseudo-random number generator comprises a second LFSR configured to receive the clock signal and generate new pseudo-random numbers based on the clock signal.

9. The device of claim 8 , wherein the second LFSR is configured to receive a reset signal and restart the pseudo-random numbers based on the reset signal.

10. The device of claim 5 ,
wherein the first pseudo-random number generator comprises a first linear-feedback shift register (LFSR) comprising an N-bit LFSR,
wherein the first LFSR is configured to receive a first clock signal and generate new pseudo-random numbers based on the first clock signal, and
wherein the second pseudo-random number generator comprises a second LFSR configured to:
receive a second clock signal including no more than one active edge per N active edges of the first clock signal; and
generate new pseudo-random numbers based on the active edge of the second clock signal.

11. The device of claim 5 ,
wherein the first pseudo-random number generator comprises a first linear-feedback shift register (LFSR) configured to receive a clock signal and generate new pseudo-random numbers based on the clock signal, and
wherein the second pseudo-random number generator comprises a second LFSR configured to:
receive the clock signal;
receive an inhibit signal; and
generate new pseudo-random numbers based on the clock signal and the inhibit signal.

12. The device of claim 1 ,
wherein the first set of data bits encodes the first numerical value in N data bits, and
wherein a length of the first bit sequence is greater than or equal to N data bits.

13. The device of claim 12 , wherein a length of the output bit-stream is less than 2{circumflex over ( )}(2N) data bits.

14. A method for performing a digital computational operation, the method comprising:
receiving, at a deterministic pseudo-random bit-stream generator, a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value;
generating, at the deterministic pseudo-random bit-stream generator, bit combinations representing a first bit sequence and a second bit sequence that deterministically encode the first and second numerical values, respectively, based on a proportion of the data bits in the sequence that are high relative to the total data bits in the sequence, wherein a subset of the bit combinations pairs a data bit of the first bit sequence with multiple different data bits of the second bit sequence, and wherein the bit combinations are generated such that high data bits of the first and second bit sequence are pseudo-randomly distributed throughout the first and second bit sequences; and
producing, by a stochastic computational circuit, an output bit-stream by performing a computational operation on the bit combinations, wherein the data bits of the output bit-stream represent a result of the computational operation based on a probability that any data bit in the output bit-stream is high.

15. The method of claim 14 , further comprising down sampling, by the stochastic computational circuit and prior to performing the computational operation on the bit combinations, the first bit sequence and the second bit sequence rep

Assignees

• Univ Minnesota

Inventors

• Najafi Mohammadhassan
• Lilja David J

Classifications

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06F7/58 Primary

  Random or pseudo-random number generators · CPC title

• G06F7/584

  using finite field arithmetic, e.g. using a linear feedback shift register · CPC title

• G06F7/70 Primary

  using stochastic pulse trains, i.e. randomly occurring pulses the average pulse rates of which represent numbers {(conversion of analogue signals into stochastic pulse trains and vice versa H03M1/04)} · CPC title

• G06N3/063

  using electronic means · CPC title