Design of accurate arithmetic operation blocks via bit stream computing as an alternative to stochastic computing

Stochastic computing is a computing paradigm that process serial bit streams probabilistically. It uses randomly generated streams and stores the information in them as probability of 1s. Despite its initial emergence at 1950s, it loses favor since it got behind in still-used binary computing in terms of accuracy. Recently, mostly because integrated circuit design has been approaching its physical limits, stochastic computing, providing substantial amount of area savings, has been brought to agenda. It started to be used frequently especially on the applications not requiring perfect accuracy like signal processing, artificial neural networks, etc. Nevertheless, accuracy problem still continues to limit stochastic computing. In this work, a new computing paradigm ``Bit Stream Computing" that is constructed on the logic used in stochastic computing has been proposed. Bit Stream Computing can be considered as a generalized version of stochastic computing. It mainly combines the area advantage of stochastic computing with accuracy advantage of conventional binary computing. It does not need to employ randomly generated or Binomially distributed streams. It decreases the area cost of the circuits by processing the information with serial bits instead of using parallel bits as in conventional binary computing. As a result, the circuits produced via this paradigm has the potential to satisfy the current needs such as low cost and high accuracy. A computing paradigm primarily needs arithmetic operations. The main arithmetic operation blocks of conventional computing are addition and multiplication circuits. Likewise, this work proposes addition and multiplication circuits with bit stream computing to lay a foundation. However, as a beginning, it is preferred to determine the limits of stochastic or bit stream computing in terms of the metrics like input/output stream length, accuracy, circuit complexity. This determination facilitates to check any proposed design whether its results are close to optimum ones. The determination of the limits of stochastic/bit stream computing also reveals some interesting outcomes: - Randomly generated or binomially distributed streams are not be able to produce 100\% accurate results, i.e. perfect accuracy needs deterministic streams. - Addition and multiplication operations also require longer output streams than of inputs for perfect accuracy. - 100\% accurate stochastic/bit stream computing circuits are not compatible with successive stream processing. These outcomes have given reasons to branch the circuits proposed with bit stream computing. Both synchronous and asynchronous designs are proposed to satisfy various requirements. For instance, generally asynchronous designs are more cost effective than synchronous ones in cases of shorter bit streams. Synchronous designs are also classified as two subgroups named constant stream and increased stream designs. The former group is suitable for successive stream processing while the latter has \%100 accuracy. The proposed asynchronous designs are also perfectly accurate, therefore they are not suitable for successive stream processing. The reason why any asynchronous design that suitable for successive stream processing is not proposed has also been explained. The accuracy and area complexity results of all proposed designs are quite close to the optimum limits which can be achieved via stochastic/bit stream computing. Adder and multiplier circuits proposed with bit stream computing are compared with their conventional binary and stochastic predecessors in the literature in terms of area, delay, and accuracy. One of the distinctive features of this work is its that simulations carried out for comparisons are in transistor level. Nearly all previous works in stochastic computing do not have any transistor level simulations which results in to overlook some drawbacks that can be only noticed in this simulations such as time alignment problems. On the other hand, the proposed circuits and their predecessors are also examined in this simulations and they are tried to be optimized to get rid of this unnoticed problems. Simulations are carried out in both transistor and gate level with AMS \SI{}{0.35\micro m} CMOS technology in Cadence environments. Accuracy comparisons with transistor level simulations are made with two novel metrics suitable for stochastic/bit stream computing: integrity and correctness. These metrics pave the way to examine any stochastic/bit stream computing design with regards to the drawbacks coming to existence in transistor level simulations. Delay comparisons are also made by dividing the delay results into two metrics: inherent circuit delay and stream delay. The results have shown that the proposed circuits outperform any former stochastic design. Another outcome of these comparisons is that the delay amounts stochastic/bit stream computing designs are mainly comes from stream delay instead of inherent circuit delay so that considering only stream delay for these designs is a quite rational simplification. Area comparisons prove that our proposed designs are most area-efficient ones among all compared designs. One of them (Synchronous Constant Stream Adder) has even $ O(1) $ complexity with respect to bit lengths, i.e. it is completely scalable. With zero or tiny sacrifice from accuracy, proposed designs provide substantial amount of area savings. Out of these designs, asynchronous ones have low cost for smaller bit lengths, while synchronous ones are more area-friendly for longer. Lastly, a simple neural network is implemented with all compared designs to show our designs' supremacy in an application. Comparisons are also classified with regard to input/output signal format (analog, binary and bit stream). The implementations are compared in terms of area (number of transistors) and accuracy (misclassification rate). Our perfectly accurate designs generally have better area performance than other binary or stochastic designs. On the other hand, the area results of our semi-accurate (constant stream/suitable for successive processing) designs have the lowest area cost in exchange for an insignificant accuracy lost. To sum up, this work proposes a novel computing paradigm ``Bit Stream Computing" which has the ability to realize the main arithmetic operations more efficiently than previous computing paradigms. It is believed that this work opens up new horizons for computing paradigms that is capable of realizing much smaller and more accurate arithmetic operations than conventional binary or stochastic computing.