A systematic approach for designing redundant arithmetic adders based on counter tree diagrams

Naofumi Homma, Takafumi Aoki, Tatsuo Higuchi

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


This paper introduces a systematic approach to designing high-performance parallel adders based on Counter Tree Diagrams (CTDs). By using CTDs, we can describe addition algorithms at various levels of abstraction. A high-level CTD represents a network of coarse-grained components associated with word-level operands, whereas a low-level CTD represents a network of primitive components that can be directly mapped onto physical 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 in a formal manner. In this paper, we focus on an application of CTDs to the design of redundant arithmetic adders with limited carry propagation. For any redundant number representation, we can obtain the optimal adder structure by trying every possible CTD decomposition and CTD-variable encoding. The potential of the proposed approach is demonstrated through an experimental synthesis of Redundant-Binary (RB) adders with CMOS standard cell libraries. We can successfully obtain RB adders that achieve an about 30-40 percent improvement in terms of power-delay product compared with conventional designs.

Original languageEnglish
Pages (from-to)1633-1646
Number of pages14
JournalIEEE Transactions on Computers
Issue number12
Publication statusPublished - 2008


  • Addition algorithms
  • Arithmetic and logic structures
  • Circuit optimization
  • High-speed arithmetic
  • Performance analysis and design aids
  • Redundant number systems

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'A systematic approach for designing redundant arithmetic adders based on counter tree diagrams'. Together they form a unique fingerprint.

Cite this