# US 2020/0401376 A1 · Low-discrepancy deterministic bit-stream processing using sobol sequences > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401376 A1 - Document ID: US20200401376A1 - Status: Published application - Kind: A1 - Application number: 16/906,122 - Filed: 2020-06-19 - Published: 2020-12-24 - Earliest claimed: 2019-06-21 - Assignees: Regents of the University of Minnesota - Applicants: Regents of the University of Minnesota - Inventors: Mohammadhassan Najafi; David J. Lilja; Marcus Riedel; Kiarash Bazargan; Sayed Abdolrasoul Faraji; Bingzhe Li - Web page: https://patentgrep.com/patent/US20200401376A1 ## CPC - G06F 7/582: {Pseudo-random number generators} - G06F 7/70: 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)} - H03K 3/84: Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators - H03M 7/26: Conversion to or from stochastic codes - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Example devices are described that include a computational unit configured to process first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value. The computational unit includes a bit-stream generator configured to generate bit combinations representing first and second bit sequences that 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. The first bit sequence is generated using a first Sobol sequence source, and the second bit sequence is generated using a second Sobol sequence source different from the first Sobol sequence source. The device also includes computation logic 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. ## Claims ### Claim 1 A device comprising: an integrated circuit comprising a computational unit 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 unit comprises: a bit-stream generator configured to generate bit combinations representing a first bit sequence and a second bit sequence that 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, wherein the first bit sequence is generated using a first Sobol sequence source, wherein the second bit sequence is generated using a second Sobol sequence source different from the first Sobol sequence source, and computation logic 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. ### Claim 2 (depends on 1) The device of claim 1, wherein the first Sobol sequence source is generated by reversing an order of output bits of a counter. ### Claim 3 (depends on 1) The device of claim 1, wherein the first bit sequence is generated by comparing the first set of data bits and the first Sobol sequence source, and wherein the second bit sequence is generated by comparing the second set of data bits and the second Sobol sequence source. ### Claim 4 (depends on 1) The device of claim 1, wherein the computation logic is configured to select a length of the output bit-stream, wherein the length of the output bit-stream is less than 2{circumflex over ( )}(2N) data bits, and wherein N is a length of the first bit sequence. ### Claim 5 A device configured to process a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value, the device comprising: a counter configured to generate an output; a first Sobol sequence source configured to generate a first Sobol sequence based on the output of the counter; a second Sobol sequence source configured to generate a second Sobol sequence based on the output of the counter, wherein the second Sobol sequence is different from the first Sobol sequence source, and wherein the first Sobol sequence source and the second Sobol sequence source are directly driven by the counter; a first comparator configured to generate a first bit sequence based on the first Sobol sequence and a first constant number; a second comparator configured to generate a second bit sequence based on the second Sobol sequence and a second constant number; and computation logic configured to: perform a computational operation on the first bit sequence and the second bit sequence; 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. ### Claim 6 (depends on 5) The device of claim 5, wherein the counter is configured to generate the output by generating two or more count values in parallel, wherein the first Sobol sequence source is configured to generate the first Sobol sequence by generating a first set of Sobol numbers in parallel based on the two or more count values generated by the counter, and wherein the second Sobol sequence source is configured to generate the second Sobol sequence by generating a second set of Sobol numbers in parallel based on the two or more count values generated by the counter. ### Claim 7 (depends on 6) The device of claim 6, further comprising: a first set of comparators comprising the first comparator, wherein each comparator of the first set of comparators is configured to generate a respective bit sequence based on a respective one of the first set of Sobol numbers, and a second set of comparators comprising the second comparator, wherein each comparator of the second set of comparators is configured to generate a respective bit sequence based on a respective one of the second set of Sobol numbers. ### Claim 8 (depends on 6) The device of claim 6, wherein the first set of Sobol numbers comprises two or more consecutive values of the first Sobol sequence, and wherein the second set of Sobol numbers comprises two or more consecutive values of the second Sobol sequence. ### Claim 9 (depends on 5) The device of claim 5, wherein the computation logic is a first set of computation logic, wherein the output bit-stream is a first sub-result bit-stream, wherein the first constant number is a first portion of a first input binary number, wherein the second constant number is a first portion of a second input binary number, and wherein the device further comprises: a third bit-stream generator configured to generate a third bit-stream based on a numerical value represented by a second portion of the first input binary number; a fourth bit-stream generator configured to generate a fourth bit-stream based on a numerical value represented by a second portion of the second input binary number; a second set of computation logic configured to operate on the third bit-stream and the fourth bit-stream to generate a second sub-result bit-stream; and an accumulator configured to generate a binary result based on the first sub-result bit-stream and the second sub-result bit-stream. ### Claim 10 (depends on 9) The device of claim 9, wherein the third bit-stream generator comprises a third comparator configured to generate the third bit-stream based on the first Sobol sequence and the second portion of the first input binary number, and wherein the fourth bit-stream generator comprises a fourth comparator configured to generate the fourth bit-stream based on the second Sobol sequence and the second portion of the second input binary number. ### Claim 11 (depends on 9) The device of claim 9, wherein the second portion of the first input binary number is different than the first portion of the first input binary number, and wherein the second portion of the second input binary number is different than the first portion of the second input binary number. ### Claim 12 (depends on 9) The device of claim 9, further comprising an adder tree configured to: add the first and second sub-result bit-streams to generate a summed bit-stream; and deliver the summed bit-stream to the accumulator. ### Claim 13 A device configured to process a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value, the device comprising: a first counter; a second counter configured to stall based on an output of the first counter; a first Sobol sequence source configured to generate a first Sobol sequence based on an output of the first counter; a second Sobol sequence source configured to generate a second Sobol sequence based on an output of the second counter, wherein the second Sobol sequence is different from the first Sobol sequence source; a first comparator configured to generate a first bit sequence based on the first Sobol sequence and a first constant number; a second comparator configured to generate a second bit sequence based on the second Sobol sequence and a second constant number; and computation logic configured to: perform a computational operation on the first bit sequence and the second bit sequence; 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. ### Claim 14 (depends on 13) The device of claim 13, wherein the second counter is configured to stall in response to the output of the first counter matching a particular value. ### Claim 15 (depends on 13) The device of claim 13, wherein the first counter comprises a first N-bit counter, and wherein the second counter comprises a second N-bit counter configured to stall no more than once per 2{circumflex over ( )}N counts. ### Claim 16 (depends on 13) The device of claim 13, wherein the first counter configured to generate a first set of two or more count values in parallel, wherein the first Sobol sequence source is configured to generate the first Sobol sequence by generating a first set of Sobol numbers in parallel based on the first set of two or more count values generated by the first counter, wherein the second counter configured to generate a second set of two or more count values in parallel, and wherein the second Sobol sequence source is configured to generate the second Sobol sequence by generating a second set of Sobol numbers in parallel based on the second set of two or more count values generated by the second counter. ### Claim 17 (depends on 16) The device of claim 16, further comprising: a first set of comparators comprising the first comparator, wherein each comparator of the first set of comparators is configured to generate a respective bit sequence based on a respective one of the first set of Sobol numbers, and a second set of comparators comprising the second comparator, wherein each comparator of the second set of comparators is configured to generate a respective bit sequence based on a respective one of the second set of Sobol numbers. ### Claim 18 (depends on 16) The device of claim 16, wherein the first set of Sobol numbers comprises two or more consecutive values of the first Sobol sequence, and wherein the second set of Sobol numbers comprises two or more consecutive values of the second Sobol sequence. ### Claim 19 (depends on 13) The device of claim 13, wherein the computation logic is a first set of computation logic, wherein the output bit-stream is a first sub-result bit-stream, wherein the first constant number is a first portion of a first input binary number, wherein the second constant number is a first portion of a second input binary number, and wherein the device further comprises: a third bit-stream generator configured to generate a third bit-stream based on a numerical value represented by a second portion of the first input binary number; a fourth bit-stream generator configured to generate a fourth bit-stream based on a numerical value represented by a second portion of the second input binary number; a second set of computation logic configured to operate on the third bit-stream and the fourth bit-stream to generate a second sub-result bit-stream; and an accumulator configured to generate a binary result based on the first sub-result bit-stream and the second sub-result bit-stream. ### Claim 20 (depends on 19) The device of claim 19, wherein the third bit-stream generator comprises a third comparator configured to generate the third bit-stream based on the first Sobol sequence and the second portion of the first input binary number, and wherein the fourth bit-stream generator comprises a fourth comparator configured to generate the fourth bit-stream based on the second Sobol sequence and the second portion of the second input binary number. ### Claim 21 A method comprising: receiving, at a 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 bit stream generator, bit combinations representing a first bit sequence and a second bit sequence that 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, wherein generating the bit combinations comprises generating the first bit sequence using a first Sobol sequence source and generating the second bit sequence using a second Sobol sequence source different from the first Sobol sequence source; and producing, by computation logic, 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. ### Claim 22 (depends on 21) The method of claim 21, further comprising: directly driving, by a counter, the first Sobol sequence source to generate the first Sobol sequence; and directly driving, by the counter, the second Sobol sequence source to generate the second Sobol sequence. ### Claim 23 (depends on 21) The method of claim 21, further comprising: driving, by a first counter, the first Sobol sequence source to generate the first Sobol sequence; driving, by a second counter, the second Sobol sequence source to generate the second Sobol sequence; and stalling the second counter based on an output of the first counter. ### Claim 24 A stochastic computational unit comprising: a bit-stream generator configured to generate bit combinations representing a first bit sequence and a second bit sequence that encode 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, wherein the first bit sequence is generated using a first Sobol sequence source, wherein the second bit sequence is generated using a second Sobol sequence source different from the first Sobol sequence source, and stochastic processing circuitry 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. ### Claim 25 (depends on 24) The stochastic computational unit of claim 24, further comprising a counter, wherein the first Sobol sequence source and the second Sobol sequence source are directly driven by the counter. ### Claim 26 (depends on 24) The stochastic computational unit of claim 24, further comprising a first counter and a second counter, wherein the first Sobol sequence source is driven by a first counter, and wherein the second Sobol sequence source is driven by a second counter configured to stall based on an output of the first counter. ### Claim 27 (depends on 24) The stochastic computational unit of claim 24, further comprising a counter configured to generate two or more count values in parallel, wherein the first Sobol sequence source is configured to generate the first Sobol sequence by generating a first set of Sobol numbers in parallel based on the two or more count values generated by the counter.