On the multidimensional RNS and its applications to the design of fast digital systems

In the recent past, several papers have been published on the subject of performing complex arithmetic in the Residue Number System (RNS). These papers introduced the Quadratic Residue Number System (QRNS) which is, in fact, a Multidimensional RNS of order 2. These papers demonstrated that a complexity savings of more than 50% can be achieved for the operation of a complex multiply and that higher throughputs can result. Extensions of this concept are presented and are based on polynomial rings which reduce the number of multiplies to Winograd´s lower bound. The conditions under which this can be achieved are theoretically developed and examples are given. The newly developed system which will be called Multidimensional Residue Number System is compared to the QRNS from the standpoint of speed and amount of hardware.