Implementation of the comparison in the Residue Numeral System

Residue Number Systems, RNSs, have been considered a potential tool to parallelize the arithmetic breaking the long carry-propagation chain by bounding the RNS inside smaller modulo channels that work in parallel with each other. This parallelism is quite profitable for addition and multiplication and has made possible the usage of RNS in a range of application from embedded and digital signal processing systems to cryptography. However, some operations are difficult to perform using RNS: its non-positional representation makes hard to implement the comparison, indeed the existing comparison methods compare the RNS numbers by converting them in positional numeral system. The Positional Attribute Non-positional Code, PANC, method is a mathematical algorithm that allows the comparison in RNS without converting the numbers under consideration. It associates the RNS number to an index that identifies the interval in which the number falls and then performs the comparison between the two indexes associated to both inputs. Nowadays this mathematical method has never been implemented, but this work aims to create a digital design to transpose this method and analyse its performances. The considered moduli set is [2^n-1,2^n,2^n+1] since it is the most used set in RNS’ datapaths, while the n values considered are the n=5 and n=8 ones, together with n=3 even if it is not usually adopted for RNS datapaths. The implemented structures are three: the Golden model architecture that parallelize all the operations is the fastest and widest one, the resource sharing design is the smallest but the slowest and finally the Unfolded resource sharing design which is a trade-off between the previous structures thanks to the unfolding technique’s application that makes the structure both wider and faster with respect of the resource sharing one. Those three designs have been analysed in terms of delay, area occupied and power consumption and then compared with the existing comparator in order to classify them.