Maximally redundant unsigned digit systems speed up arithmetic units
MRUD: Maximally Redundant Unsigned Digit Number Systems for High-Performance Arithmetic Units
Hardware Architecture
Summary
Performing addition without waiting for carries can make computers faster, but this usually makes multiplication harder. The authors show a new number system called MRUD that extends unsigned digit redundancy to bigger digit sizes, keeping addition fast and multiplication easier. MRUD supports both signed and unsigned numbers, unlike older methods, and can make hardware for multiplication and multiply-accumulate operations run faster, smaller, and with less power. This approach offers a new way to build faster arithmetic units inside computers.
What this means in practice
- •For hardware designers: Design faster and more power-efficient arithmetic units using MRUD-based addition and multiplication in processors and accelerators.
- •For embedded system developers: Integrate MRUD arithmetic units to reduce power consumption and improve throughput in resource-constrained embedded applications.
Authors
Samaneh Rahimi, Ali Azarpeyvand
Abstract
Signed digit redundant number systems such as Maximally Redundant Signed Digit (MRSD) enable carry-free addition but introduce significant overhead in multiplication due to the presence of both positive and negative bits. While Unsigned Digit Redundant (UDR) systems have shown promise in radix-2, their extension to higher radices remains unexplored. This work presents the first generalized Maximally Redundant Unsigned Digit (MRUD) number systems for high-radix arithmetic, extending UDR representations from radix-2 to radix-$2^h$ while preserving carry-free addition. The proposed framework includes digit encoding, digit extension, arithmetic operations (addition, subtraction, and multiplication), sign inversion, forward/reverse conversion algorithms, overflow/underflow detection, and hardware architectures for both signed and unsigned MRUD representations. Unlike MRSD, which is inherently limited to signed arithmetic, MRUD supports both signed and unsigned representations, similar to conventional binary systems. Evaluations across three multiplier modes---RRR (Redundant inputs, Redundant output), BBR (Binary inputs, Redundant output), and BBB (Binary inputs, Binary output)---as well as Multiply-Accumulate (MAC) units, using the FreePDK 45nm library, demonstrate that MRUD achieves up to 30\% lower delay, 26\% smaller area, and 87\% lower power than MRSD. In BBR mode, MRUD achieves up to 43\% delay reduction over the best conventional architecture for 32$\times$32 operands, while in Multiply-Accumulate (MAC) units, performing reverse conversion only once at the end yields up to 64\% higher throughput than DesignWare and over 150\% higher than Wallace. These results demonstrate that MRUD enables high-radix redundant arithmetic with significantly improved multiplier and MAC performance, making it an efficient alternative to conventional signed digit redundant number systems.