A systematic approach for analyzing fast addition algorithms using counter tree diagrams

Naofumi Homma; Jun Sakiyama; Taihei Wakamatsu; Takafumi Aoki; Tatsuo Higuchi

A systematic approach for analyzing fast addition algorithms using counter tree diagrams

Naofumi Homma, Jun Sakiyama, Taihei Wakamatsu, Takafumi Aoki, Tatsuo Higuchi

Research output: Contribution to journal › Conference article › peer-review

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 (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. In this paper, we focus on an application of CTDs to the analysis of two-operand RB adders with limited carry propagation. The analysis result shows that there exists possible two types of 3-stage CTDs for the RB adders. From this result, we can confirm that well-known RB adders are classified into one of the two types.

Original language	English
Pages (from-to)	V-197-V-200
Journal	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	5
Publication status	Published - 2004 Sept 6
Event	2004 IEEE International Symposium on Cirquits and Systems - Proceedings - Vancouver, BC, Canada Duration: 2004 May 23 → 2004 May 26

ASJC Scopus subject areas

Electrical and Electronic Engineering

Cite this

@article{bfd8af90ab8943bcb8c52f73e48e6c93,

title = "A systematic approach for analyzing fast addition algorithms using counter tree diagrams",

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 (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. In this paper, we focus on an application of CTDs to the analysis of two-operand RB adders with limited carry propagation. The analysis result shows that there exists possible two types of 3-stage CTDs for the RB adders. From this result, we can confirm that well-known RB adders are classified into one of the two types.",

author = "Naofumi Homma and Jun Sakiyama and Taihei Wakamatsu and Takafumi Aoki and Tatsuo Higuchi",

year = "2004",

month = sep,

day = "6",

language = "English",

volume = "5",

pages = "V--197--V--200",

journal = "Proceedings - IEEE International Symposium on Circuits and Systems",

issn = "0271-4310",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "2004 IEEE International Symposium on Cirquits and Systems - Proceedings ; Conference date: 23-05-2004 Through 26-05-2004",

}

TY - JOUR

T1 - A systematic approach for analyzing fast addition algorithms using counter tree diagrams

AU - Homma, Naofumi

AU - Sakiyama, Jun

AU - Wakamatsu, Taihei

AU - Aoki, Takafumi

AU - Higuchi, Tatsuo

PY - 2004/9/6

Y1 - 2004/9/6

N2 - 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. In this paper, we focus on an application of CTDs to the analysis of two-operand RB adders with limited carry propagation. The analysis result shows that there exists possible two types of 3-stage CTDs for the RB adders. From this result, we can confirm that well-known RB adders are classified into one of the two types.

AB - 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. In this paper, we focus on an application of CTDs to the analysis of two-operand RB adders with limited carry propagation. The analysis result shows that there exists possible two types of 3-stage CTDs for the RB adders. From this result, we can confirm that well-known RB adders are classified into one of the two types.

UR - http://www.scopus.com/inward/record.url?scp=4344624015&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4344624015&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:4344624015

SN - 0271-4310

VL - 5

SP - V-197-V-200

JO - Proceedings - IEEE International Symposium on Circuits and Systems

JF - Proceedings - IEEE International Symposium on Circuits and Systems

T2 - 2004 IEEE International Symposium on Cirquits and Systems - Proceedings

Y2 - 23 May 2004 through 26 May 2004

ER -

A systematic approach for analyzing fast addition algorithms using counter tree diagrams

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this