Counter Tree Diagrams: A Unified Framework for Analyzing Fast Addition Algorithms

Jun SAKIYAMA  Naofumi HOMMA  Takafumi AOKI  Tatsuo HIGUCHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.12   pp.3009-3019
Publication Date: 2003/12/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: IP Design
computer arithmetic algorithms,  parallel counters,  multipliers,  datapath,  VLSI,  circuit synthesis,  

Full Text: PDF>>
Buy this Article

This paper presents a unified representation of fast addition algorithms based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe and analyze various adder architectures in a systematic way without using specific knowledge about underlying arithmetic algorithms. Examples of adder architectures that can be handled by CTDs include Redundant-Binary (RB) adders, Signed-Digit (SD) adders, Positive-Digit (PD) adders, carry-save adders, parallel counters (e.g., 3-2 counters and 4-2 counters) and networks of such basic adders/counters. This paper also discusses the CTD-based analysis of carry-propagation-free adders using various number representations.