.png){kind=icon}
.png){kind=icon}
Return
Constant-time addition and simultaneous format conversion based on redundant binary representations
.png){kind=icon}
PRE
AI
DOI：10.1109/12.966499.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
It is well-known that constant-time addition, in which the execution delay is independent of operand lengths, is feasible only if the output is expressed in a redundant representation. There are many ways of introducing redundancy and the specifics of the redundant format employed can have a major impact on the performance of constant-time addition and digit set conversion. This paper presents a comprehensive analysis of constant-time addition and simultaneous format conversion. We consider full as well as partially redundant representations, where not all digit positions are redundant. The number of redundant digits and their positions can be arbitrary, yielding many possible redundant representations. Format conversion refers to changing the number and/or position of redundant digits in a representation. It is shown that such a format conversion is feasible during (i.e., simultaneous with) constant time addition, even if all three operands (the two inputs and single output) are represented in distinct redundant formats. We exploit equal-weight grouping (EWG), wherein bits having the same weight are grouped together to achieve the constant-time addition and possible simultaneous format conversion. The analysis and data show that EWG leads to efficient implementations. We compare VLSI implementations of various constant-time addition cells and demonstrate that the conventional 4:2 compressor is the most efficient way to execute constant time-addition. We show interesting connections to prior results and indicate possible directions for further extensions.
Keywords:
redundant representations
constant-time addition
simultaneous format conversion
redundant adders
carry-save addition
signed-digit addition
4 : 2 compressor
Journal
IF:
3.8
Papers:
5.3K
Citations:
9.8K
Organization
No organization information available