Finite state machine-based bit-stream generator for low-discrepancy stochastic computing
Inventors
Najafi, Mohammadhassan • Imani, Mohsen • Asadi, Sina
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12602202-B2
Publication Date
2026-04-14
Expiration Date
Abstract
Disclosed herein is a finite state machine-based low-discrepancy bit-stream generator that support generation of any number of independent low-discrepancy bit-streams. Here, the order of bit selection by the FSM of the bit-stream generator is determined based on the distribution of numbers in the Sobol sequences. An independent LD bit-stream is generated by setting up the FSM using a different Sobol sequence. The available space can then be used to improve fault tolerance.
Core Innovation
The invention relates to a finite state machine for generating bit streams for a stochastic computing system. The finite state machine is set up using an inputting of a Sobol sequence that comprises one or more Sobol numbers and a representation of each Sk as a kth number of the inputted Sobol sequence. Based on a specified inequality involving m and n, where m is an integer number between 1 to n and n is the Sobol sequence’s data precision, the finite state machine selects an mth bit or an (n−m)th bit of a binary input X for output generation.
The generation of the bit stream is implemented in hardware as part of the stochastic computing system. The output of the finite state machine is processed by a one-hot encoder, and the outputs of the one-hot encoder are received as inputs by a probability conversion circuit. The probability conversion circuit comprises at least two AND gates and at least one OR gate to convert the encoder outputs into probability-related inputs for the stochastic computing system.
A low-discrepancy stochastic computing bit-stream generator is described that produces multiple independent low-discrepancy patterns by assigning an FSM bit-selection order using ranges of Sobol sequence values. The generator converts n-bit binary input into 2^n-length low-discrepancy bit-streams via an (n+1)-to-1 MUX controlled by a 2^n-state FSM, and independence is achieved by using different Sobol sequences. The document further describes rotation-based generation for high precision, M× parallel FSM variants, and fault tolerance evaluation using N-modular redundancy.
Claims Coverage
The provided partial content includes one independent claim. The claim covers a 2^n-state finite state machine generating a stochastic computing bit stream using Sobol-sequence-driven bit selection, followed by one-hot encoding and probability conversion using AND/OR logic.
Sobol-sequence-driven 2^n-state FSM bit selection
A finite state machine set up by inputting a Sobol sequence and using Sk as a kth number of the inputted Sobol sequence to select an mth bit or an (n−m)th bit of a binary input X based on the condition (2^m−1)/2^m−1 ≤ S_k < (2^m−1)/2^m, where m is an integer number between 1 to n and n comprises the Sobol sequence’s data precision.
Hardware implementation with one-hot encoding and probability conversion
The finite state machine is implemented in hardware as part of a stochastic computing system, where the output of the finite state machine is processed by a one-hot encoder and the outputs of the one-hot encoder are received as inputs by a probability conversion circuit.
Probability conversion using AND/OR gate logic
The probability conversion circuit comprises at least two AND gates and at least one OR gate.
Across the independent claim, the inventive coverage centers on a 2^n-state FSM that uses a Sobol sequence and an m/n-based inequality to select bits of an input X, with the FSM output converted through a one-hot encoder into inputs for a probability conversion circuit implemented with AND and OR gates.
Stated Advantages
Up to ~80% area savings compared with comparator-based LD generators.
Accuracy results for stochastic multiplication are reported, including zero error at full cycle length for 8-bit.
Fault tolerance is evaluated using N-modular redundancy, with reported MAE reduction by orders of magnitude at low injection rates for 5-MR.
Documented Applications
Use in stochastic multiplication and stochastic convolution engines, including SC convolution case studies.
Integration into a convolution (k×k) and an SC convolution engine implementation that includes an FSM+one-hot encoder with a probability conversion circuit (PCC) using AND/OR gates.
Evaluation use cases include hardware cost comparisons, critical path/latency/power advantages discussion, parallel FSM variants (M× parallelism), and fault tolerance evaluation with soft error injection using N-modular redundancy.
Interested in licensing this patent?