A Generic Modulo 2^n –1 Adder Based on Stored Negabit Representation of Residues

A Generic Modulo 2^n –1 Adder Based on Stored Negabit Representation of Residues

Abstract

Abstract studies in computer arithmetic, often lead to generic frameworks for concrete implementations. Computer arithmetic algorithms show variant performance potentials on alternative input and output encodings. Standard computer arithmetic components (e.g., full/half adder cells, carry look-ahead blocks) are once in a while enhanced in performance. Therefore any computer arithmetic unit (e.g., n-bit adders and multipliers, carry-save adders (CSA), etc), generic in design, can be implemented by replacing its generic parts by the best available, standard and functionally equivalent, components meeting specific design goals in time, area and power. Up-grading is easily possible via using new technologic advances. In this paper, we study abstract algorithms and generic implementations for modulo 2^n–1 addition. The latter is popular in many application domains of residue number systems (e.g., digital signal processing) and other applications such as fault tolerant computing. We propose a novel representation for modulo 2^n–1 residues. This is composed of an unsigned n-bit number and a stored negabit as a second least significant bit (lsb). A supporting algorithm, computing sum+1, stores a (–1)-valued negabit as the second lsb of the sum in case of no carryout. This simple trick allows for a generic delay-optimized modulo 2^n–1 adder composed of an n-bit CSA and a generic n-bit adder. In concrete implementations, each designer can use the best available CSA and n-bit adder that meet the prescribed design goals. Given that CSAs show less switching activity than n-bit adders, savings in power dissipation is expected in comparison with the best previous generic design which uses two n-bit adders.

References