Computing arithmetic functions using stochastic logic by series expansion

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Stochastic logic implementations of complex arithmetic functions, such as trigonometric, exponential, and sigmoid, are derived based on truncated versions of their Maclaurin series expansions. This paper makes three contributions. First, it is shown that a polynomial can be implemented using multiple levels of NAND gates based on Horner's rule, if the coefficients are alternately positive and negative and their magnitudes are monotonically decreasing. Truncated Maclaurin series expansions of arithmetic functions are used to generate polynomials which satisfy these constraints. The input and output in these functions are represented by unipolar representation. Functions including sine, cosine, tangent hyperbolic, logarithm and exponential can be implemented using this method. Second, for a polynomial that does not satisfy these constraints, it still can be implemented based on Horner's rule if each factor of the polynomial satisfies these constraints. It is shown that functions such as sin π x/π, e-ax, tanh ax and sigmoid(ax3) (for values of a>1) can be implemented using stochastic logic using factorization in combination with Horner's rule. Third, format conversion is proposed for arithmetic functions with input and output represented in different formats, such as cos, π x given x [0,1] and sigmoid(x) given x [-1,1]. Polynomials are transformed to equivalent forms that naturally exploit format conversions. The proposed stochastic logic circuits outperform the well-known Bernstein polynomial based and finite-state-machine (FSM) based implementations. Furthermore, the hardware complexity and the critical path of the proposed implementations are less than the well-known Bernstein polynomial based and FSM based implementations for most cases.

Original languageEnglish (US)
Article number7593286
Pages (from-to)44-59
Number of pages16
JournalIEEE Transactions on Emerging Topics in Computing
Volume7
Issue number1
DOIs
StatePublished - Jan 1 2019

Fingerprint

Polynomials
Finite automata
Logic circuits
Factorization
Hardware

Keywords

  • Horner's rule
  • Maclaurin series expansion
  • Stochastic logic
  • bipolar-to-unipolar conversion
  • decorrelation
  • factor-combining
  • factorization
  • unipolar-to-bipolar conversion

Cite this

Computing arithmetic functions using stochastic logic by series expansion. / Parhi, Keshab K; Liu, Yin.

In: IEEE Transactions on Emerging Topics in Computing, Vol. 7, No. 1, 7593286, 01.01.2019, p. 44-59.

Research output: Contribution to journalArticle

@article{6c559b4c6db14ddcbacf24924ac4f8fc,
title = "Computing arithmetic functions using stochastic logic by series expansion",
abstract = "Stochastic logic implementations of complex arithmetic functions, such as trigonometric, exponential, and sigmoid, are derived based on truncated versions of their Maclaurin series expansions. This paper makes three contributions. First, it is shown that a polynomial can be implemented using multiple levels of NAND gates based on Horner's rule, if the coefficients are alternately positive and negative and their magnitudes are monotonically decreasing. Truncated Maclaurin series expansions of arithmetic functions are used to generate polynomials which satisfy these constraints. The input and output in these functions are represented by unipolar representation. Functions including sine, cosine, tangent hyperbolic, logarithm and exponential can be implemented using this method. Second, for a polynomial that does not satisfy these constraints, it still can be implemented based on Horner's rule if each factor of the polynomial satisfies these constraints. It is shown that functions such as sin π x/π, e-ax, tanh ax and sigmoid(ax3) (for values of a>1) can be implemented using stochastic logic using factorization in combination with Horner's rule. Third, format conversion is proposed for arithmetic functions with input and output represented in different formats, such as cos, π x given x [0,1] and sigmoid(x) given x [-1,1]. Polynomials are transformed to equivalent forms that naturally exploit format conversions. The proposed stochastic logic circuits outperform the well-known Bernstein polynomial based and finite-state-machine (FSM) based implementations. Furthermore, the hardware complexity and the critical path of the proposed implementations are less than the well-known Bernstein polynomial based and FSM based implementations for most cases.",
keywords = "Horner's rule, Maclaurin series expansion, Stochastic logic, bipolar-to-unipolar conversion, decorrelation, factor-combining, factorization, unipolar-to-bipolar conversion",
author = "Parhi, {Keshab K} and Yin Liu",
year = "2019",
month = "1",
day = "1",
doi = "10.1109/TETC.2016.2618750",
language = "English (US)",
volume = "7",
pages = "44--59",
journal = "IEEE Transactions on Emerging Topics in Computing",
issn = "2168-6750",
publisher = "IEEE Computer Society",
number = "1",

}

TY - JOUR

T1 - Computing arithmetic functions using stochastic logic by series expansion

AU - Parhi, Keshab K

AU - Liu, Yin

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Stochastic logic implementations of complex arithmetic functions, such as trigonometric, exponential, and sigmoid, are derived based on truncated versions of their Maclaurin series expansions. This paper makes three contributions. First, it is shown that a polynomial can be implemented using multiple levels of NAND gates based on Horner's rule, if the coefficients are alternately positive and negative and their magnitudes are monotonically decreasing. Truncated Maclaurin series expansions of arithmetic functions are used to generate polynomials which satisfy these constraints. The input and output in these functions are represented by unipolar representation. Functions including sine, cosine, tangent hyperbolic, logarithm and exponential can be implemented using this method. Second, for a polynomial that does not satisfy these constraints, it still can be implemented based on Horner's rule if each factor of the polynomial satisfies these constraints. It is shown that functions such as sin π x/π, e-ax, tanh ax and sigmoid(ax3) (for values of a>1) can be implemented using stochastic logic using factorization in combination with Horner's rule. Third, format conversion is proposed for arithmetic functions with input and output represented in different formats, such as cos, π x given x [0,1] and sigmoid(x) given x [-1,1]. Polynomials are transformed to equivalent forms that naturally exploit format conversions. The proposed stochastic logic circuits outperform the well-known Bernstein polynomial based and finite-state-machine (FSM) based implementations. Furthermore, the hardware complexity and the critical path of the proposed implementations are less than the well-known Bernstein polynomial based and FSM based implementations for most cases.

AB - Stochastic logic implementations of complex arithmetic functions, such as trigonometric, exponential, and sigmoid, are derived based on truncated versions of their Maclaurin series expansions. This paper makes three contributions. First, it is shown that a polynomial can be implemented using multiple levels of NAND gates based on Horner's rule, if the coefficients are alternately positive and negative and their magnitudes are monotonically decreasing. Truncated Maclaurin series expansions of arithmetic functions are used to generate polynomials which satisfy these constraints. The input and output in these functions are represented by unipolar representation. Functions including sine, cosine, tangent hyperbolic, logarithm and exponential can be implemented using this method. Second, for a polynomial that does not satisfy these constraints, it still can be implemented based on Horner's rule if each factor of the polynomial satisfies these constraints. It is shown that functions such as sin π x/π, e-ax, tanh ax and sigmoid(ax3) (for values of a>1) can be implemented using stochastic logic using factorization in combination with Horner's rule. Third, format conversion is proposed for arithmetic functions with input and output represented in different formats, such as cos, π x given x [0,1] and sigmoid(x) given x [-1,1]. Polynomials are transformed to equivalent forms that naturally exploit format conversions. The proposed stochastic logic circuits outperform the well-known Bernstein polynomial based and finite-state-machine (FSM) based implementations. Furthermore, the hardware complexity and the critical path of the proposed implementations are less than the well-known Bernstein polynomial based and FSM based implementations for most cases.

KW - Horner's rule

KW - Maclaurin series expansion

KW - Stochastic logic

KW - bipolar-to-unipolar conversion

KW - decorrelation

KW - factor-combining

KW - factorization

KW - unipolar-to-bipolar conversion

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

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

U2 - 10.1109/TETC.2016.2618750

DO - 10.1109/TETC.2016.2618750

M3 - Article

VL - 7

SP - 44

EP - 59

JO - IEEE Transactions on Emerging Topics in Computing

JF - IEEE Transactions on Emerging Topics in Computing

SN - 2168-6750

IS - 1

M1 - 7593286

ER -