A Generic Modulo- $(2^{n}\pm\delta)$ Addition Algorithm via Two-Valued Digit Encoding

Modular adders are essential arithmetic components in Residue Number System (RNS)-based applications, including digital signal processing, cryptography, and machine learning. These applications consistently push the boundaries of dynamic range (DR) and operating frequency, making the design of efficient generic modular adders a critical and evolving challenge. This paper presents a novel algorithm for modulo <tex>$-(2^{n}\pm \delta)$</tex> addition, where <tex>$\delta$</tex> is an integer within the range <tex>$0\leq\delta\leq 2^{n-1}-1$</tex>. The proposed approach leverages a two-valued digit (twit) for encoding the value of <tex>$\pm\delta$</tex> and uses a faithful representation of operands. In this representation, each operand is encoded as an n-bit unsigned number augmented by a twit value <tex>$\{0,\pm\delta\}$</tex>. The algorithm efficiently performs modular addition by speculating and adjusting the twit value in the addition result. When the result exceeds the modulus, it subtracts <tex>$\mathrm{z}^{n}\pm\delta$</tex> by ignoring the carry-out and adjusting the speculated twit value. This adjustment is achieved through an XOR operation between the carry-out and the speculated twit value, simplifying the modular reduction process. The proposed design has been synthesized for practical n <tex>$(4\leq n\leq 16$</tex> using a FreePDK 45 nm process. The results demonstrate superior performance across key metrics such as delay, area, and power consumption compared to previous designs, highlighting the efficacy and scalability of the approach.