Residue-to-binary arithmetic converter for the moduli set (2k, 2k-1, 2k-1-1)

This paper presents a new algorithm which converts moduli (2(k) . 2(k)-1 . 2(k-1)-1) residue numbers to their binary equivalents; it is the first converter which has been dedicated to this particular moduli set. The complexity of conversion has been greatly reduced using new compact forms for the multiplicative inverses and the properties of modular arithmetic. A hardware implementation which utilizes adders only is also proposed, with a pipelined system, the throughput rate is that of a single (2k-1)-bit binary adder. Comparison results showed that the hardware requirements and the execution time of the new converter are less than half that needed by other converters.