TY - JOUR

T1 - Logical computation on stochastic bit streams with linear finite-state machines

AU - Li, Peng

AU - Lilja, David J

AU - Qian, Weikang

AU - Riedel, Marc

AU - Bazargan, Kia

PY - 2014/6

Y1 - 2014/6

N2 - Most digital systems operate on a positional representation of data, such as binary radix. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

AB - Most digital systems operate on a positional representation of data, such as binary radix. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

KW - Stochastic computing

KW - finite-state machine (FSM)

KW - stochastic bit streams

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

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

U2 - 10.1109/TC.2012.231

DO - 10.1109/TC.2012.231

M3 - Article

AN - SCOPUS:84903167033

SN - 0018-9340

VL - 63

SP - 1474

EP - 1486

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 6

M1 - 6307798

ER -