Computing polynomials using unipolar stochastic logic

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

This article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic-based circuits are inherently fault tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. It is well known that an AND gate and a multiplexer can be used to implement stochastic unipolar multiplier and adder, respectively. Although it is easy to realize multiplication and scaled addition, implementation of subtraction is nontrivial using unipolar stochastic logic. Additionally, an accurate computation of subtraction is critical for the implementation of polynomials with negative coefficients in stochastic unipolar representation. This work, for the first time, demonstrates that instead of using well-known Bernstein polynomials, stochastic computation of polynomials can be implemented by using a stochastic subtractor and factorization. Three major contributions are given in this article. First, two approaches are proposed to compute subtraction in stochastic unipolar representation. In the first approach, the subtraction operation is approximated by cascading multilevels of OR and AND gates. The accuracy of the approximation is improved with the increase in the number of stages. In the second approach, the stochastic subtraction is implemented using a multiplexer and a stochastic divider. This approach requires more hardware complexity due to the use of a linear-feedback shift register and a counter for division. Second, computation of polynomials in stochastic unipolar format is presented using scaled addition and proposed stochastic subtraction. Third, we propose stochastic computation of polynomials using factorization. Stochastic implementations of first- and second-order factors are presented for different locations of polynomial roots. From experimental results, it is shown that the proposed stochastic logic circuits require less hardware complexity than the previous stochastic polynomial implementation using Bernstein polynomials.

Original languageEnglish (US)
Article number42
JournalACM Journal on Emerging Technologies in Computing Systems
Volume13
Issue number3
DOIs
StatePublished - Apr 1 2017

Fingerprint

Polynomials
Factorization
Hardware
Shift registers
Logic gates
Logic circuits
Adders
Feedback
Networks (circuits)

Keywords

  • Complex arithmetic functions
  • Factorization
  • Polynomial computation
  • Stochastic logic
  • Stochastic subtraction
  • Unipolar representation

Cite this

Computing polynomials using unipolar stochastic logic. / Liu, Yin; Parhi, Keshab K.

In: ACM Journal on Emerging Technologies in Computing Systems, Vol. 13, No. 3, 42, 01.04.2017.

Research output: Contribution to journalArticle

@article{55021e9fc9e746e88024f3b6c77d20d5,
title = "Computing polynomials using unipolar stochastic logic",
abstract = "This article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic-based circuits are inherently fault tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. It is well known that an AND gate and a multiplexer can be used to implement stochastic unipolar multiplier and adder, respectively. Although it is easy to realize multiplication and scaled addition, implementation of subtraction is nontrivial using unipolar stochastic logic. Additionally, an accurate computation of subtraction is critical for the implementation of polynomials with negative coefficients in stochastic unipolar representation. This work, for the first time, demonstrates that instead of using well-known Bernstein polynomials, stochastic computation of polynomials can be implemented by using a stochastic subtractor and factorization. Three major contributions are given in this article. First, two approaches are proposed to compute subtraction in stochastic unipolar representation. In the first approach, the subtraction operation is approximated by cascading multilevels of OR and AND gates. The accuracy of the approximation is improved with the increase in the number of stages. In the second approach, the stochastic subtraction is implemented using a multiplexer and a stochastic divider. This approach requires more hardware complexity due to the use of a linear-feedback shift register and a counter for division. Second, computation of polynomials in stochastic unipolar format is presented using scaled addition and proposed stochastic subtraction. Third, we propose stochastic computation of polynomials using factorization. Stochastic implementations of first- and second-order factors are presented for different locations of polynomial roots. From experimental results, it is shown that the proposed stochastic logic circuits require less hardware complexity than the previous stochastic polynomial implementation using Bernstein polynomials.",
keywords = "Complex arithmetic functions, Factorization, Polynomial computation, Stochastic logic, Stochastic subtraction, Unipolar representation",
author = "Yin Liu and Parhi, {Keshab K}",
year = "2017",
month = "4",
day = "1",
doi = "10.1145/3007648",
language = "English (US)",
volume = "13",
journal = "ACM Journal on Emerging Technologies in Computing Systems",
issn = "1550-4832",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

T1 - Computing polynomials using unipolar stochastic logic

AU - Liu, Yin

AU - Parhi, Keshab K

PY - 2017/4/1

Y1 - 2017/4/1

N2 - This article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic-based circuits are inherently fault tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. It is well known that an AND gate and a multiplexer can be used to implement stochastic unipolar multiplier and adder, respectively. Although it is easy to realize multiplication and scaled addition, implementation of subtraction is nontrivial using unipolar stochastic logic. Additionally, an accurate computation of subtraction is critical for the implementation of polynomials with negative coefficients in stochastic unipolar representation. This work, for the first time, demonstrates that instead of using well-known Bernstein polynomials, stochastic computation of polynomials can be implemented by using a stochastic subtractor and factorization. Three major contributions are given in this article. First, two approaches are proposed to compute subtraction in stochastic unipolar representation. In the first approach, the subtraction operation is approximated by cascading multilevels of OR and AND gates. The accuracy of the approximation is improved with the increase in the number of stages. In the second approach, the stochastic subtraction is implemented using a multiplexer and a stochastic divider. This approach requires more hardware complexity due to the use of a linear-feedback shift register and a counter for division. Second, computation of polynomials in stochastic unipolar format is presented using scaled addition and proposed stochastic subtraction. Third, we propose stochastic computation of polynomials using factorization. Stochastic implementations of first- and second-order factors are presented for different locations of polynomial roots. From experimental results, it is shown that the proposed stochastic logic circuits require less hardware complexity than the previous stochastic polynomial implementation using Bernstein polynomials.

AB - This article addresses subtraction and polynomial computations using unipolar stochastic logic. Stochastic computing requires simple logic gates, and stochastic logic-based circuits are inherently fault tolerant. Thus, these structures are well suited for nanoscale CMOS technologies. It is well known that an AND gate and a multiplexer can be used to implement stochastic unipolar multiplier and adder, respectively. Although it is easy to realize multiplication and scaled addition, implementation of subtraction is nontrivial using unipolar stochastic logic. Additionally, an accurate computation of subtraction is critical for the implementation of polynomials with negative coefficients in stochastic unipolar representation. This work, for the first time, demonstrates that instead of using well-known Bernstein polynomials, stochastic computation of polynomials can be implemented by using a stochastic subtractor and factorization. Three major contributions are given in this article. First, two approaches are proposed to compute subtraction in stochastic unipolar representation. In the first approach, the subtraction operation is approximated by cascading multilevels of OR and AND gates. The accuracy of the approximation is improved with the increase in the number of stages. In the second approach, the stochastic subtraction is implemented using a multiplexer and a stochastic divider. This approach requires more hardware complexity due to the use of a linear-feedback shift register and a counter for division. Second, computation of polynomials in stochastic unipolar format is presented using scaled addition and proposed stochastic subtraction. Third, we propose stochastic computation of polynomials using factorization. Stochastic implementations of first- and second-order factors are presented for different locations of polynomial roots. From experimental results, it is shown that the proposed stochastic logic circuits require less hardware complexity than the previous stochastic polynomial implementation using Bernstein polynomials.

KW - Complex arithmetic functions

KW - Factorization

KW - Polynomial computation

KW - Stochastic logic

KW - Stochastic subtraction

KW - Unipolar representation

UR - http://www.scopus.com/inward/record.url?scp=85018465321&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85018465321&partnerID=8YFLogxK

U2 - 10.1145/3007648

DO - 10.1145/3007648

M3 - Article

VL - 13

JO - ACM Journal on Emerging Technologies in Computing Systems

JF - ACM Journal on Emerging Technologies in Computing Systems

SN - 1550-4832

IS - 3

M1 - 42

ER -