An efficient universal addition scheme for all hybrid-redundant representations with weighted bit-set encoding. (English) Zbl 1104.94067
Summary: 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.
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 94A29 | Source coding |
| 11A63 | Radix representation; digital problems |
Keywords:
\((4,2)\)-compressor; carry-free addition; computer arithmetic; digit set; redundant number system; signed digitReferences:
| [1] | A. Avizienis, ”Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electronic Computers, vol. 10, 1961, pp. 389–400. · doi:10.1109/TEC.1961.5219227 |
| [2] | B. Parhami, ”Generalized Signed-Digit Number Systems: A Unifying Framework for Redundant Number Representations,” IEEE Trans. Computers, vol. 39, no. 1, 1990, pp. 89–98. · doi:10.1109/12.46283 |
| [3] | G. Jaberipur, B. Parhami, and M. Ghodsi, ”Weighted Bit-Set Encodings for Redundant Digit Sets: Theory and Applications,” in Proc. 36th Asilomar Conf. Signals Systems and Computers, Nov. 2002, pp. 1629–1633. |
| [4] | C.R. Baugh and B.A. Wooley, ”A Two’s Complement Parallel Array Multiplication Algorithm,” IEEE Trans. Computers, vol. 22, 1973, pp. 1045–1047. · Zbl 0269.94017 · doi:10.1109/T-C.1973.223648 |
| [5] | H. Kobayashi, ”A Mutioperand Two’s Complement Addition Algorithm,” in Proc. 7th IEEE Symp. Computer Arithmetic, June 1985, pp. 16–19. |
| [6] | D.S. Phatak and I. Koren, ”Constant-Time Addition and Simultaneous Format Conversion Based on Redundant Binary Representations,” IEEE Trans. Computers, vol. 50, no. 11, 2001, pp. 1267–1278. · doi:10.1109/12.966499 |
| [7] | M.D. Ercegovac, ”Effective Coding for Fast Redundant Adders Using the Radix-2 Digit Set 0, 1, 2, 3,” in Proc. 31st Asilomar Conf. Signals Systems and Computers, Nov. 1997, pp. 1163–1167. |
| [8] | B. Parhami, ”Comments on ’High-Speed Area-Efficient Multiplier Design Using Multiple-Valued Current-Mode Circuits’,” IEEE Trans. Computers, vol. 45, no. 5, 1996, pp. 637–638. · doi:10.1109/12.509918 |
| [9] | G. Jaberipur, B. Parhami, and M. Ghodsi, ”A Class of Stored-Transfer Representations for Redundant Number Systems,” in Proc. 35th Asilomar Conf. Signals Systems and Computers, Nov. 2001, pp. 1304–1308. |
| [10] | D.S. Phatak and I. Koren, ”Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains,” IEEE Trans. Computers, vol. 43, no. 8, 1994, pp. 880–891. · Zbl 1066.68505 · doi:10.1109/12.295850 |
| [11] | M.I. Ferguson and M.D. Ercegovac, ”A Multiplier with Redundant Operands,” in Proc. 33rd Asilomar Conf. Signals Systems and Computers, Oct. 1999, pp. 1322–1326. |
| [12] | B. Parhami, Computer Arithmetic: Algorithms and Hardware Designs, Oxford, 2000. |
| [13] | A. Mignotte, J.M. Muller, and O. Peyran, ”Synthesis for Mixed Arithmetic,” Design Automation for Embedded Systems, vol. 5, no. 1, 2000, pp. 29–60. · doi:10.1023/A:1008939516542 |
| [14] | M. Daumas and D.W. Matula, ”Further Reducing the Redundancy of a Notation Over a Minimally Redundant Digit Set,” J. VLSI Signal Processing, vol. 33, 2003, pp. 7–18. · Zbl 1039.68005 · doi:10.1023/A:1021133616373 |
| [15] | G. Jaberipur, ”Frameworks for the Exploration and Implementation of Generalized Carry-Free Redundant Number Systems,” PhD Dissertation, Sharif Univ. Tech., Tehran, Iran, Dec. 2004. |
| [16] | P. Kornerup, ”Necessary and Sufficient Conditions for Parallel, Constant Time Conversion and Addition,” in Proc. 14th IEEE Symp. Computer Arithmetic, April 1999, pp. 152–155. |
| [17] | I. Koren, Computer Arithmetic Algorithms, 2nd edition, A.K. Peters, 2002. · Zbl 0994.68186 |
| [18] | G. Jaberipur, B. Parhami, and M. Ghodsi, ”Weighted Two-Valued Digit-Set Encodings: Unifying Efficient Hardware Representation Schemes for Redundant Number Systems,” IEEE Trans. Circuits and Systems–I: Regular Papers, vol. 52, no. 7, July 2005, pp. 1348–1357. · Zbl 1374.68014 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
