Modulo-(2²ⁿ+1) Arithmetic via Two Parallel n-bit Residue Channels

Augmenting the balanced residue number system moduli-set ₁=2ⁿ,m₂=2ⁿ-1,m₃=2ⁿ+1\, with the co-prime modulo m₄=2²ⁿ+1, increases the dynamic range (DR) by around 70%. The Mersenne form of product m₂ m₃ m₄=2⁴ⁿ-1, in the moduli-set ₁,m₂,m₃,m₄\, leads to a very efficient reverse convertor, based on the New Chinese remainder theorem. However, the double bit-width of the m_4 residue channel is counter-productive and jeopardizes the speed balance in ₁,m₂,m₃\. Therefore, we decompose m₄ to two complex-number n-bit moduli 2ⁿ±√-1, which preserves the DR and the co-primality across the augmented moduli set. The required forward modulo-(2²ⁿ+1) to moduli-(2ⁿ±√-1)conversion, and the reverse are immediate and cost-free. The proposed unified moduli-(2ⁿ±√-1) adder and multiplier, are tested and synthesized using Spartan 7S100 FPGA. The 6-bit look-up tables (LUT), therein, promote the LUT realizations of adders and multipliers, for $n=5$, where the DR equals 2²⁵-2⁵. However, the undertaken experiments show that to cover all the 32-bit numbers, the power-of-two channel m₁ can be as wide as 12 bits with no harm to the speed balance across the five moduli. The results also show that the moduli-(2⁵±√-1) add and multiply operations are advantageous vs. moduli-(2⁵±1) in speed, cost, and energy measures and collectively better than those of modulo-(2¹⁰+1).