Systematic Interpretation of Redundant Arithmetic Adders in Binary and Multiple-Valued Logic

Naofumi HOMMA  Takafumi AOKI  Tatsuo HIGUCHI  

IEICE TRANSACTIONS on Electronics   Vol.E89-C   No.11   pp.1645-1654
Publication Date: 2006/11/01
Online ISSN: 1745-1353
DOI: 10.1093/ietele/e89-c.11.1645
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Novel Device Architectures and System Integration Technologies)
datapaths,  arithmetic circuits,  addition algorithms,  number systems,  multiple-valued logic,  

Full Text: PDF(856KB)>>
Buy this Article

This paper presents an algorithm-level interpretation of fast adder structures in binary/multiple-valued logic. The key idea is to employ a unified representation of addition algorithms called Counter Tree Diagrams (CTDs). The use of CTDs makes it possible to describe and analyze addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with multiple-valued logic devices, while a low-level CTD represents a network of primitive components directly mapped onto binary logic devices. The level of abstraction in circuit representation can be changed by decomposition of CTDs. We can derive possible variations of adder structures by decomposing a high-level CTD into low-level CTDs. This paper demonstrates the interpretation of redundant arithmetic adders based on CTDs. We first introduce an extension of CTDs to represent possible redundant arithmetic adders with limited carry propagation. Using the extended version of CTDs, we can classify the conventional adder structures including those using emerging devices into three types in a systematic way.