High Quality Down-sampling for Deterministic Approaches to Stochastic Computing

Technology No. 20180134
IP Status: US Patent Issued; Application #: 16/352,933

Accurate Stochastic Bit Streams

This concept uses pseudo-random number generators (e.g., linear feedback shift registers, or LFSR) to generate input bit-streams for deterministic approaches of stochastic computing (SC). This high-quality down-sampling method generates pseudo-random—but accurate—stochastic bit streams, resulting in much better accuracy for a given number of input bits. The new techniques offer technical advantages by randomizing deterministically generated bit-streams. As with processing unary streams, which can be deterministically generated, the computations are completely accurate when executing the operations for the required number of cycles. However, by pseudo-randomizing the streams, the computation has good progressive precision property, and truncating the output streams by running for fewer clock cycles still produces high quality outputs. For some inputs (e.g., image processing and neural network applications) decision making does not require high precision, and therefore a low-precision estimate of the output value is sufficient.

Down-sampling Method Reduces Operation Time

While recently proposed deterministic approaches to SC that rely on unary-style bit-streams (i.e., streams with a sequence of 1s followed by a sequence 0s) produce completely accurate results, they also suffer from poor progressive precision (e.g., the output converges to the expected correct value very slowly). Furthermore, to produce completely accurate results, the operation must run for an exact number of clock cycles. Running the operation for fewer cycles leads to a poor result with an error out of the acceptable error bound. These drawbacks can limit using unary-style bit-streams approaches in different applications. This new down-sampling method improves the progressive precision property of the three main previously proposed deterministic stochastic computing approaches. By modifying the structure of the stream generators, the enhanced deterministic methods produce not only completely accurate results, but also acceptable results in a much shorter time and with a much lower energy consumption compared to current architectures that generate and process unary streams. Results show that, for the same operation time, deterministic down-sampling produces results with a lower average error rate than that of processing unary-style deterministic bit-streams and also the conventional random stochastic streams. When some inaccuracy is acceptable, using these high-quality down-sampling methods can reduce long operation times and the high energy consumption.


  • High-quality down-sampling method
  • Pseudo-random number generators generate deterministic accurate input bit-streams
  • Improved accuracy for a given number of input bits
  • Good progressive precision property
  • Truncating output streams (by running fewer clock cycles) produces high quality outputs
  • Generates acceptable results in less time and with much lower energy consumption
  • Lower average error rate
  • Reduces long operation times and high energy consumption


  • Sensor-based circuitry
  • Image processing circuitry
  • Specialized circuitry for neural networks
  • Machine learning applications
  • Digital chips (i.e., image and signal processing, machine learning applications)
  • Approximate computing
  • Applications that tolerate some degree of uncertainty (such as video processing, image tagging, neural networks)

Phase of Development - Proof of Concept

David Lilja, PhD
Professor, Electrical and Computer Engineering
External Link (ece.umn.edu)
Mohammadhassan Najafi
PhD Candidate, Electrical and Computer Engineering
External Link (najafi.ece.umn.edu)

High Quality Down-Sampling for Deterministic Approaches to Stochastic Computing
IEEE Transactions on Emerging Topics in Computing, 03 Jan 2018

Interested in Licensing?
The University relies on industry partners to scale up technologies to large enough production capacity for commercial purposes. The license is available for this technology and would be for the sale, manufacture or use of products claimed by the issued patents. Please contact us to share your business needs and technical interest in this technology and if you are interested in licensing the technology for further research and development.

  • swap_vertical_circlecloud_downloadSupporting documents (0)
Questions about this technology?