• 1
  • 2
  • 5
  • 6
  • 3
  • 4

“School of Computer Science”

Back to Papers Home
Back to Papers of School of Computer Science

Paper   IPM / Computer Science / 10890
School of Computer Science
  Title:   Constant-time addition with hybrid-redundant numbers: Theory and implementations
1.  G. Jaberipur
2.  B. Parhami
  Status:   Published
  Journal: Integration, the VLSI Journal
  No.:  1
  Vol.:  41
  Year:  2008
  Pages:   49-64
  Publisher(s):   Elsevier Science
  Supported by:  IPM
Hybrid-redundant number representation has provided a flexible framework for digit-parallel addition in a manner that facilitates area-time tradeoffs for VLSI implementations via arbitrary spacing of redundant digit positions within an otherwise nonredundant representation. We revisit the hybrid redundancy scheme, pointing out limitations such as representational asymmetry, lack of representational closure in certain adder implementations, and difficulties in subtraction and carry acceleration. Given the intuitiveness of the hybrid redundancy concept and its potential for describing practically useful redundant number systems, we are motivated to extend it within the framework of weighted bit-set encodings to circumvent the aforementioned problems. The extension is based mainly on allowing negatively weighted bits (negabits), as well as standard posibits, to appear in nonredundant positions. Our extended hybrid redundancy scheme provides for arbitrary spacing of redundant positions in symmetric digit sets, without any degradation in arithmetic efficiency, while at the same time allowing low-latency subtraction by means of the same circuitry that is used for addition. Finally, we describe how inverted encoding of negabits leads to the exclusive use of unmodified standard full/half-adder, counter, and compressor cells, with no extra inverters, and to the direct applicability of conventional carry acceleration techniques in constant-time addition.

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right