Title :
Counter Tree Diagrams for design and analysis of fast addition algorithms
Author :
Sakiyama, Jun ; Aoki, Toyohiro ; Higuchi, Tatsuo
Author_Institution :
Graduate Sch. of Inf. Sci., Tohoku Univ., Sendai, Japan
Abstract :
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 (R-B) adders, Signed-Digit (SD) adders, Positive-Digit (PD) or 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 design and analysis of carry-propagation-free adders using redundant number representation.
Keywords :
adders; algorithm theory; counting circuits; directed graphs; redundant number systems; trees (mathematics); 3-2 counter; 4-2 counter; CTD-based analysis; CTD-based design; PD adder; R-B adder; SD adder; adder architecture; arithmetic algorithm; carry-propagation-free adder; carry-save adder; counter tree diagram; fast addition algorithm; parallel counter; positive-digit; redundant number representation; redundant-binary; signed-digit; Algorithm design and analysis; Counting circuits; Logic design;
Conference_Titel :
Multiple-Valued Logic, 2003. Proceedings. 33rd International Symposium on
Print_ISBN :
0-7695-1918-0
DOI :
10.1109/ISMVL.2003.1201390
