Weighted two-valued digit-set encodings: unifying efficient hardware representation schemes for redundant number systems

We introduce the notion of two-valued digit (twit) as a binary variable that can assume one of two different integer values. Posibits, or simply bits, in {0,1} and negabits in {-1,0}, commonly used in two's-complement representations and (n,p) encoding of binary signed digits, are special cases of twits. A weighted bit-set (WBS) encoding, which generalizes the two's-complement encoding by allowing one or more posibits and/or negabits in each radix-2 position, has been shown to unify many efficient implementations of redundant number systems. A collection of equally weighted twits, including ones with noncontiguous values (e.g., {-1,1} or {0,2}), can lead to wider representation range without the added storage and interconnection costs associated with multivalued digit sets. We present weighted twit-set (WTS) encodings as a generalization of WBS encodings, examine key properties of this new class of encodings, and show that any redundant number system (e.g., generalized signed-digit and hybrid-redundant systems), including those that are based on noncontiguous and/or zero-excluded digit sets, is faithfully representable by WTS encoding. We highlight this broad coverage by a tree chart having WTS representations at its root and various useful redundant representations at its many internal nodes and leaves. We further examine how highly optimized conventional components such as standard full/half-adders and compressors may be used for arithmetic on WTS-encoded operands, thus allowing highly efficient and VLSI-friendly circuit implementations. For example, focusing on the WBS-like subclass of WTS encodings, we describe a twit-based implementation of a particular stored-transfer representation which offers area and speed advantages over other similar designs based on WBS and hybrid-redundant representations.     

Stored-transfer representations with weighted digit-set encodings for ultrahigh-speed arithmetic

Redundant representations play an important role in high-speed computer arithmetic. One key reason is that such representations support carry-free addition, that is, addition in a small, constant time, independent of operand widths. The implications of stored-transfer representation of digit sets and the associated addition schemes, as an extension of the stored-carry concept to redundant number systems, on the speed and cost of arithmetic algorithms, are explored. Two's-complement digits as the main part and any two-valued digit (twit) in place of a stored carry are allowed, leading to further broadening of the generalised signed-digit representations. The characteristics of the digit sets, possibly not having zero as a member, that allow for most efficient carry-free addition, are investigated. Circuit speed is gained from storing or saving, instead of combining through addition, the interdigit transfers generated during the carry-free addition process. Encoding efficiency is gained from using a twit-transfer set encoded by one logical bit, where more bits would otherwise be needed to represent a transfer value     

Improved CMOS (4; 2) compressor designs for parallel multipliers

We propose three new (4; 2) compressors via improving best previous designs by replacing an integral portion of relevant logical circuits by an optimized CMOS full-adder. Two other new (4; 2) compressors are also proposed based on new interpretation of logical equations that describe the corresponding functionality. The key design point is to use an available signal, in the sum path, for carry generation. All the proposed and referenced designs are evaluated by exhaustive HSPICE simulations at various temperatures, voltage scaling situations, load capacitances, and presence of process variation using the post-layout CMOS library of standard cell. These experiences show performance improvements, compared to the best of reference designs, in terms of delay (5%), power (16%), and PDP (26%), respectively. To evaluate the studied and new (4; 2) compressors in a more practical environment, we utilized them for implementation of 54 × 54-bit parallel multipliers. Experimental results via MAGMA design tools confirmed the results that we achieved for isolated single (4; 2) compressors.     

Low area/power decimal addition with carry-select correction and carry-select sum-digits

We improve a carry-select technique for decimal adders, where pairs of corrective carry-out bits for all decimal positions are computed in parallel. Selection is based on the corresponding positional carry-in bits, which are produced by a quaternary parallel prefix carry network. Carry-out bits select pairs of corrected or intact sum-digits to be later selected by actual carry-in bits at the end of addition process. Analytical evaluation and synthesis results for various hardware sharing architectures on binary, decimal, adders, and subtractors show lower area consumption and less power dissipation of the proposed designs at no additional latency, compared to previous works.     

Constant-time addition with hybrid-redundant numbers: Theory and implementations

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.     

An Efficient Universal Addition Scheme for All Hybrid-Redundant Representations with Weighted Bit-Set Encoding

Redundant and hybrid-redundant number representations are used extensively to speed up arithmetic operations within general-purpose and special-purpose digital systems, with the latter (containing both redundant and nonredundant digits) offering cost advantages over fully redundant systems. We use weighted bit-set (WBS) encoding as a paradigm for uniform treatment of five previously studied variants of hybrid-redundant systems. We then extend the class of hybrid-redundant numbers to coincide with the entire set of canonical WBS numbers by allowing an arbitrary nonredundant position, heretofore restricted to ordinary bits (posibits), to hold a negatively weighted bit (negabit). This flexibility leads to interesting and useful symmetric variants of hybrid-redundant representations. We provide a high-level circuit design, based solely on binary full-adders, for a constant-time universal hybrid-redundant adder capable of producing a canonical WBS-encoded sum of two canonical WBS (or extended hybrid) numbers. This is made possible by the use of conventional binary full-adders for reducing any collection of three posibits and negabits, where negabits use an inverted encoding. We compare our adder to previous designs, showing advantages in speed, cost, and regularity. Furthermore we explore representationally closed addition schemes, holding the benefit of greater regularity and reusability, and provide high-level representationally closed designs for all the previously studied variants of hybrid redundancy and for the new symmetric variants introduced here. Finally, we present a new functionality for a conventional (4; 2) compressor in combining any collection of five equally weighted negabits and posibits, and show its utility in the design of multipliers for extended hybrid-redundant numbers. Ghassem Jaberipur received BS in electrical engineering and PhD in computer engineering from Sharif University of Technology in 1974 and 2004, respectively, MS in engineering (majoring in computer hardware) from University of California, Los Angeles, in 1976, and MS in computer science from University of Wisconsin, Madison, in 1979. Since 1979, he has been with the Department of Electrical and Computer Engineering, Shahid Beheshti University, in Tehran, Iran, teaching courses in compiler construction, automata theory, design and implementation of programming languages, and computer arithmetic. Behrooz Parhami (PhD, University of California, Los Angeles, 1973) is Professor of Electrical and Computer Engineering at University of California, Santa Barbara. He has research interests in computer arithmetic, parallel processing, and dependable computing. In his previous position with Sharif University of Technology in Tehran, Iran (1974--88), he was also involved in educational planning, curriculum development, standardization efforts, technology transfer, and various editorial responsibilities, including a five-year term as Editor of Computer Report, a Persian-language computing periodical. His technical publications include over 200 papers in peer-reviewed journals and international conferences, a Persian-language textbook, and an English/Persian glossary of computing terms. Among his publications are three textbooks on parallel processing (Plenum, 1999), computer arithmetic (Oxford, 2000), and computer architecture (Oxford, 2005). Dr. Parhami is a Fellow of both the IEEE and the British Computer Society, a member of the Association for Computing Machinery, and a Distinguished Member of the Informatics Society of Iran for which he served as a founding member and President during 1979-84. He also served as Chairman of IEEE Iran Section (1977-86) and received the IEEE Centennial Medal in 1984. Mohammad Ghodsi Mohammad Ghodsi received BS in electrical engineering from Sharif University of Technology (SUT, Tehran, Iran) in 1975, MS in electrical engineering and computer science from University of California at Berkeley in 1978, and PhD in computer science from the Pennsylvania State University in 1989. He has been affiliated with SUT as a faculty member since 1979. Presently, he is a Professor in SUT's Computer Engineering Department. His research interests include design of efficient algorithms, parallel and systolic algorithms, and computational geometry.     

Decimal Square Root: Algorithm and Hardware Implementation

We propose a new digit recurrence decimal square root (DSR) design and provide its ASIC implementation. The interim square root digits are in \([ {-5,5} ]\). The proposed architecture generally follows that of a previous radix-10 divider. However, it provides novel solutions with regard to few DSR-specific challenges. For example, complex error analysis shows that only four (out of sixteen) digits of partial square root is sufficient to estimate partial remainders that are required for the more complicated square root digit selection. This design performs about 10 % faster and consumes 28 % less area than the previously reported ASIC digit recurrence decimal square rooter.