2-1 addition and related arithmetic operations with threshold logic

Abstract

In this paper we investigate the reduction of the size for small depth feed-forward linear threshold networks performing binary addition and related functions. For n bit operands we propose a depth-3 O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /log n) asymptotic size network for the binary addition with O polynomially bounded weights. We propose also a depth-3 addition of optimal O(n) asymptotic sits network and a depth-2 comparison of O(√n) asymptotic size network, both with O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">√n</sup> ) asymptotic size of weight values. For existing architectural formats we show that our schemes, with equal or smaller depth networks, substantially outperform existing schemes in terms of size and fan-in requirements and on occasions in weight requirements.