# RNS Number Comparator Based on a Modified Diagonal Function

Mikhail Babenko, Maxim Deryabin, Stanislaw Piestrak, Piotr Patronik, Nikolay Chervyakov, Andrei Tchernykh, Arutyun Avetisyan

► To cite this version:

Mikhail Babenko, Maxim Deryabin, Stanislaw Piestrak, Piotr Patronik, Nikolay Chervyakov, et al. RNS Number Comparator Based on a Modified Diagonal Function. Electronics, 2020, 9 (11), pp.1784. 10.3390/electronics9111784. hal-05035030

HAL Id: hal-05035030

https://hal.univ-lorraine.fr/hal-05035030v1

Submitted on 15 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

Article

# RNS Number Comparator Based on a Modified Diagonal Function

Mikhail Babenko <fnref n="1" />,<fnref n="2" />,*, Maxim Deryabin <fnref n="1" />, ◙, Stanisław J. Piestrak <fnref n="3" />, Piotr Patronik <fnref n="4" />, Nikolay Chervyakov <fnref n="1" />, Andrei Tchernykh <fnref n="2" />,<fnref n="5" />, ◙ and Arutyun Avetisyan <fnref n="2" />

Received: 1 October 2020; Accepted: 23 October 2020; Published: 27 October 2020

<figure><img src="image_3.png" /></figure>

check for
updates

**Abstract:** Number comparison has long been recognized as one of the most fundamental non-modular arithmetic operations to be executed in a non-positional Residue Number System (RNS). In this paper, a new technique for designing comparators of RNS numbers represented in an arbitrary moduli set is presented. It is based on a newly introduced modified diagonal function, whose strictly monotonic properties make it possible to replace the cumbersome operations of finding the remainder of the division by a large and awkward number with significantly simpler computations involving only a power of 2 modulus. Comparators of numbers represented in sample RNSs composed of varying numbers of moduli and offering different dynamic ranges, designed using various methods, were synthesized for the 65 nm technology. The experimental results suggest that the new circuits enjoy a delay reduction ranging from over 11% to over 75% compared to the fastest circuits designed using existing methods. Moreover, it is achieved using less hardware, the reduction of which reaches over 41%, and is accompanied by significantly reduced power-consumption, which in several cases exceeds 100%. Therefore, it seems that the presented method leads to the design of the most efficient current hardware comparators of numbers represented using a general RNS moduli set.

**Keywords:** diagonal function; high-speed arithmetic; magnitude comparison; number comparison; Residue Number System (RNS)

## 1. Introduction

Parallel data processing is one of the most viable approaches to meet steadily growing needs for high-performance computations. Therefore, algorithms and data representations enjoying parallel structures, which facilitate the processing of a large amount of data efficiently, have been an area of active research for many years. One of the promising directions in this field relies on using the Residue Number System (RNS) to represent integers [1,2]. The RNS is a non-positional number system defined by the set of $n$ ($n \ge 2$) pairwise relatively prime positive integers called moduli $\{m_1, m_2, \dots, m_n\}$. Its dynamic range is equal to the product $M = \prod_{i=1}^{n} m_i$, which allows it to represent all $a$-bit numbers, where $a = [\log_2 M]$. Any non-negative integer $X$ such that $0 \le X < M$ can be uniquely represented in RNS as $X = \{x_1, x_2, \dots, x_n\}$, where the $i$th digit of $X$ in RNS $x_i = |X|_{m_i}$ is the remainder of the integer division of $X$ by the modulus $m_i$, represented in $a_i = [\log_2 m_i]$ bits.

<footnote n="1">¹ Department of Computational Mathematics and Cybernetics, North-Caucasus Federal University, 355017 Stavropol, Russia; maderiabin@ncfu.ru (M.D.); ncherviakov@ncfu.ru (N.C.)</footnote>

<footnote n="2">² Institute for System Programming of the Russian Academy of Sciences, 109004 Moscow, Russia; chernykh@cicese.edu.mx (A.T.); arut@ispras.ru (A.A.)</footnote>

<footnote n="3">³ Université de Lorraine, CNRS, IJL, F-54000 Nancy, France; stanislaw.piestrak@univ-lorraine.fr</footnote>

<footnote n="4">⁴ Department of Computer Engineering, Wroclaw University of Technology, 50370 Wrocław, Poland; piotr.patronik@pwr.wroc.pl</footnote>

<footnote n="5">⁵ Computer Science Department, CICESE Research Center, 22860 Ensenada, Mexico</footnote>

<footnote>* Correspondence: mgbabenko@ncfu.ru; Tel.: +7-906-440-0219</footnote>
Indeed, in recent years, an inherent parallelism between RNS and potentially lower power
consumption has motivated researchers to consider its use for implementation in hardware of various
classes of computations, like digital filtering [3–6], multicarrier modulation schemes with error
correction [7], and some cryptographic algorithms [8]. An excellent summary of other RNS applications
for Digital Signal Processing (DSP) systems and analysis of various design issues can be found in [9].
Coprocessors with limited sets of instructions for high-speed and low power consumption executed in
RNS have been proposed [10,11]. Besides these well-established applications, many other emerging
RNS applications have been surveyed [12].

The primary benefit of RNS is the possibility of parallel execution of basic arithmetic operations (addition, subtraction, and multiplication). Unlike positional number representation, the RNS is carry-free, which can simplify the processing of large numbers, replacing it with the execution of parallel arithmetic modular operations on numbers of significantly smaller size. Unfortunately, several non-modular operations are also indispensable, the execution of which in RNS requires interaction between different moduli due to the positional nature of these operations: residue-to-binary (reverse) conversion, magnitude comparison, sign detection, overflow detection, scaling, and division. Among them, magnitude comparison is one of the most fundamental operations, and it, besides being used directly, is also the cornerstone of division, sign detection, overflow detection, etc. Unfortunately, it is a difficult operation in RNS, because a non-positional RNS number representation does not reveal any information about the magnitude of a number, so that special methods involving handling all residue digits must be used.

Several techniques for number comparison in RNS have been studied [1,13–25]. The simplest approach to comparing numbers in RNS relies on first converting them to the positional notation, just to be compared using a simple number comparator [1]. Such a comparator is based on using any reverse (residue-to-binary) converter, which can be built on the basis of the Chinese Remainder Theorem (CRT), the Mixed Radix Conversion (MRC) method, or some variant or a combination of them [1,2,26–28]. Because the reverse converter is available anyway in any RNS-based processor, the only extra hardware cost is that of the ordinary *a*-bit comparator of numbers, which can be designed, e.g., according to [29] (pp. 45–47). Obviously, a comparison relying on traditional reverse conversion techniques inherits their major drawbacks: the multi-operand addition modulo is a large number (the dynamic range *M*) for the CRT or lengthy sequential computations for the MRC, either resulting in excessive delay and unnecessarily high power consumption.

One of the most promising approaches to handle non-positional arithmetic operations in RNS that has been proposed relies on computation of some positional characteristics of RNS numbers, according to which it would be possible to determine the magnitudes of numbers and hence their comparison. This idea relies on a hypothesis that computations involving such a positional characteristic can be implemented more efficiently than reverse conversion, due to using simpler arithmetic operations. One is the *core function* introduced in 1977 by Akushskii [13] and used for comparison. Its faster version, making it possible to avoid lengthy iterative computations, relied on introducing a redundant modulus and was proposed in [14]. The other approach uses the so-called *diagonal function*, which is defined as the sum of the quotients of division of the number by all system moduli, introduced in [16] and further developed in [18] and [21]. One of the methods based on the diagonal function, called the Sum of Quotients Technique (SQT), was claimed to be one of the most efficient hardware approaches [18]. Unfortunately, a more accurate performance estimation of the latter, presented recently in [23], revealed that the direct implementation of the comparator using the diagonal function according to [16,18] leads to inefficient circuitry. (Because the design method proposed here is based on some ideas of the diagonal function, while aiming to avoid its drawbacks, it will be detailed in Section 2.) Some other general approaches to RNS number comparison were presented in [15,17,22,26,27]. In [15], a comparison was proposed based on parity checking, provided that the basic moduli set consists of odd moduli only and that the redundant modulus is added. Those proposed in [26,27] make it possible to compute the positional characteristic using CRT without the expensive operation of finding
the remainder of a division. The comparison algorithm based on the new CRT-II, suggested in [17], makes it possible to reduce the maximum size of the modulo addition from M to approximately $\sqrt{M}$, where M is the dynamic range. The method of [22] relies on the approximate calculation of positional numbers according to CRT, whereas that of [24] makes it possible to compare signed numbers, but it also requires sign detection for each compared number. Finally, some comparators have been proposed for RNSs using special bases, e.g., the 4-moduli set composed of two pairs of conjugate moduli $\{2^n - 1, 2^n + 1, 2^{n+1} - 1, 2^{n+1} + 1\}$, as well as the 3-moduli sets $\{2^n - 1, 2^n, 2^n + 1\}$ [20] and $\{2^n - 1, 2^{n+x}, 2^n + 1\}$ [25].

In summary, the drawbacks of the previous magnitude comparison algorithms are: the need for using a redundant modulus, restricting the moduli set or time-consuming modulo operations involving large numbers (the size of the dynamic range or close). Here we will show how to extend the idea of diagonal function so that a high-speed and efficient comparator in RNS can be implemented in hardware. The new approach proposed here relies on integrating techniques from [16,26], and it is based on modifying the diagonal function of the numbers represented in RNS. The major advantages of this method are that, in addition to not requiring the computation of a remainder of division, it also leads to computations involving numbers of smaller sizes than in [26].

This paper is organized as follows. Section 2 presents the method of comparison using the SQT based on the diagonal function. Section 3 thoroughly details the theoretical background of the modified diagonal function proposed here, leading to significantly improved performance of the comparator. Performance estimations and comparison against existing circuits are provided in Section 4. Finally, some conclusions and suggestions for future research are given in Section 5.

## 2. Number Comparison Using the Sum of Quotients Technique (SQT)

In this section, we will present all key ideas related to the SQT method of [16], which will facilitate understanding of our method relying on a modification of the SQT method, which will be presented in Section 3. The main idea of the SQT method relies on the observation that in the finite n-dimensional space determined by the number of moduli n, the integers are ordered along straight lines, which are parallel to the main diagonal of the space. In MRC, each line represents the most significant digit of the number. However, these diagonals can be renumbered in a natural order of integers. In this case, the comparison of two numbers can be done by considering the numbers of the diagonals to which they belong. For fast determination of the diagonal to which a number belongs, a monotonically increasing function called the Sum of Quotients (SQ) was defined:

$$ SQ = \sum_{i=1}^{n} M_i \qquad (1) $$

where $M_i = M/m_i$. Let us define the following constant:

$$ k_i = \left| -\frac{1}{m_i} \right|_{SQ} \qquad (2) $$

where $h_i = |1/m_i|_{SQ}$ is the multiplicative inverse of $m_i$ mod SQ ($1 < h_i < SQ$), i.e., such an integer that $|h_i \cdot m_i|_{SQ} = 1$. (Recall that a multiplicative inverse exists provided that $m_i$ and SQ are co-prime, which is indeed the case here.) It was shown that for the set of constants $k_i$ the following congruence holds:

$$ |k_i + k_2 + \dots + k_n|_{SQ} = 0. \qquad (3) $$

These notions are essential to defining the diagonal function as

$$ D(X) = \left| \sum_{i=1}^{n} k_i \cdot x_i \right|_{SQ} \qquad (4) $$
which was shown to be monotonically increasing over a set of integers 0 ≤ X < M. This method is called the Sum of Quotients Technique (SQT), because the following important equality holds:

$$D(X) = \sum_{i=1}^{n} \left\lfloor \frac{X}{m_i} \right\rfloor \qquad (5)$$

The comparison of RNS numbers using SQT is summarized in the following algorithm, whose hardware implementation is shown in Figure 1.

**Algorithm 1:** Comparison of RNS numbers using SQT.

**Input:** X = {x₁, x₂, ..., xₙ}, Y = {y₁, y₂, ..., yₙ}

**Output:** "100" if X < Y, "010" if X = Y, and "001" if X > Y.

**Step 1.** Calculate D(X) and D(Y).

Note: These computations are independent and therefore they can be executed in parallel, provided that two circuits implementing the diagonal function are available.

**Step 2.** Compare the values of D(X) and D(Y):

1. if D(X) < D(Y) then return "100";

2. if D(X) > D(Y) then return "001";

3. if D(X) = D(Y) then:

3.1. if x₁ < y₁ then return "100";

3.2. if x₁ = y₁ then return "010";

3.3. if x₁ > y₁ then return "001".

<figure><img src="image_4.png" /><figcaption>**Figure 1.** Hardware implementation of the basic number comparison algorithm using the diagonal function [25,28].</figcaption></figure>

The main disadvantage of Algorithm 1 is that the computation of the remainder of the division over the modulus SQ, executed by the n-operand multi-operand modular adder (MOMA) mod SQ, is both hardware and time-consuming. (It will be seen later that for sample moduli sets the difference between the bit sizes of M and SQ could be from 3 to 5-bits.) In [16], it was suggested that in the case of the equality D(X) = D(Y) (the diagonal function is not strictly monotonic), an extra comparison must be executed. However, in [23], it was shown that this additional comparison can actually be done in parallel, so that the only delay penalty is two gate levels (this observation was taken into account in
Figure 1). In the following section, we will show how to modify SQT to replace the MOMA mod SQ with a significantly faster and simpler circuit modulo with a power of 2.

### 3. Comparison Using the Modified Diagonal Function

Here, we will describe the new method for comparison of RNS numbers based on introducing the modified diagonal function (MDF). It is based on the observation that if all constants $k_i$ are divided by SQ, i.e., similarly as was done for the CRT-based sign detector proposed in [26], then it is possible to move the computations from the residue class $[0, SQ - 1)$ to the computations in the interval $[0, 1)$, so that computations involving integer parts of real numbers are not really needed. In other words, the operation of finding the remainder of the division by SQ is replaced with the more efficient operation of discarding an integer part of a number. However, the major concern with such an approach is its accuracy, because in most cases the fractional numbers cannot be represented exactly using a finite number of bits. Nevertheless, the accurate passing from computations on fraction parts to computations on integers can be done as follows:

1. Multiply each real constant by $2^N$, where N is the number of bits of the fraction part, which guarantees sufficient accuracy.

2. For each real number, say Z, calculate $[Z]$, i.e., the smallest integer not less than Z.

3. Execute all computations modulo $2^N$ (it is sufficient to ignore all carries generated from the $(N-1)$-th position).

Note: The only limitation for the above conversion could occur when SQ divides $2^N$ (i.e., SQ is a power of two), because in this case, the method suggested reduces to the original one. Nevertheless, because in most cases SQ does not divide $2^N$, we will therefore henceforth consider only this case. To determine the smallest N which guarantees sufficient accuracy, we proceed as follows.

First, notice that the constants can be recalculated as

$$ \bar{k}_i = \left\lfloor \frac{k_i \cdot 2^N}{SQ} \right\rfloor = \frac{k_i \cdot 2^N}{SQ} + R_i, \quad 1 \le i \le n \qquad (6) $$

where $R_i = \left\lfloor \frac{k_i 2^N}{SQ} \right\rfloor - \frac{k_i 2^N}{SQ}$ and $R_i \in [0, 1)$. Because according to Equality (3) the sum $\sum_{i=1}^n k_i$ is divisible by SQ, it implies that $R = \sum_{i=1}^n R_i$ is an integer. Furthermore, because $0 < R_i < 1$ then $1 \le R < n$.

Now we can define the following positional characteristic of a number, which will be called the modified diagonal function (MDF):

$$ \bar{D}(X) = \left\lfloor \sum_{i=1}^{n} \bar{k}_i \cdot x_i \right\rfloor_{2^N} \qquad (7) $$

**Theorem 1.** Let $m_n$ be the largest modulus of the moduli set. If $N \ge [\log_2(SQ \cdot (m_n - 1))]$ then the MDF $\bar{D}(X)$ is strictly increasing for any $0 \le X < M$, i.e., for any $0 \le X_i < X_j \le M - 1$ we have $\bar{D}(X_i) < \bar{D}(X_j)$.

**Proof.** First, we find the value of $D(X - 1)$ for any $0 < X < M$. Because for any $1 \le i \le n$

$$ \left\lfloor \frac{X-1}{m_i} \right\rfloor = \begin{cases} \left\lfloor \frac{X}{m_i} \right\rfloor & \text{if } x_i \neq 0 \\ \left\lfloor \frac{X}{m_i} \right\rfloor - 1 & \text{if } x_i = 0 \end{cases} \qquad (8) $$

therefore, according to Equality (5), we have

$$ D(X-1) = \sum_{i=1}^{n} \left\lfloor \frac{X}{m_i} \right\rfloor - \sum_{i=1}^{n} z(x_i) = D(X) - \sum_{i=1}^{n} z(x_i) \qquad (9) $$
where

$$z(x_i) = \begin{cases} 0 & \text{if } x_i \neq 0 \\ 1 & \text{if } x_i = 0 \end{cases}$$

Consider

$$\tilde{D}(X) = \frac{D(X)}{SQ} = \left| \sum_{i=1}^{n} \frac{k_i}{SQ} \cdot x_i \right|_{1} \quad (10)$$

where $|Z|_1$ denotes discarding of an integer part of Z. Obviously, because $\tilde{D}(X) \ge \tilde{D}(X-1)$, $\tilde{D}(X-1)$ can be determined using Equality (10):

$$\tilde{D}(X-1) = \frac{D(X)}{SQ} - \frac{1}{SQ} \cdot \sum_{i=1}^{n} z(x_i) = \tilde{D}(X) - \frac{1}{SQ} \cdot \sum_{i=1}^{n} z(x_i) \quad (11)$$

Now we will determine the properties of the functions $\tilde{D}(X)$ and $\tilde{D}(X-1)$. By applying the notation introduced earlier, we obtain

$$\bar{D}(X) = \left| \sum_{i=1}^{n} \left( \frac{k_i \cdot 2^N}{SQ} + R_i \right) \cdot x_i \right|_{2^N} = \left| \sum_{i=1}^{n} \frac{k_i \cdot 2^N}{SQ} x_i + \sum_{i=1}^{n} R_i \cdot x_i \right|_{2^N} = \left| 2^N \cdot \sum_{i=1}^{n} \frac{k_i}{SQ} x_i + 2^N \cdot \left| \sum_{i=1}^{n} \frac{k_i}{SQ} x_i \right|_1 + \sum_{i=1}^{n} R_i \cdot x_i \right|_{2^N} \quad (12)$$

which leads to

$$\bar{D}(X) = \left| 2^N \cdot \tilde{D}(X) + \sum_{i=1}^{n} R_i \cdot x_i \right|_{2^N} \quad (13)$$

Now according to Equality (11) and by taking into account that in RNS $X-1 = \{|x_1-1|_{m_1}, |x_2-1|_{m_2}, \dots, |x_n-1|_{m_n}\}$, we obtain

$$\bar{D}(X-1) = \left| 2^N \cdot \tilde{D}(X-1) + \sum_{i=1}^{n} R_i \cdot |x_i - 1|_{m_i} \right|_{2^N} = \left| 2^N \bar{D}(X) - \frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) + \sum_{i=1}^{n} R_i \cdot |x_i - 1|_{m_i} \right|_{2^N} \quad (14)$$

Because for any $0 \le i \le n$

$$|x_i - 1|_{m_i} = \begin{cases} x_i - 1 & \text{if } x_i \neq 0 \\ m_i - 1 & \text{if } x_i = 0 \end{cases}$$

in Equality (14) we have

$$\sum_{i=1}^{n} R_i \cdot |x_i - 1|_{m_i} = \sum_{i=1}^{n} R_i \cdot x_i - R + \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i \quad (15)$$

which hence becomes

$$\bar{D}(X-1) = \left| 2^N \cdot \tilde{D}(X) + \sum_{i=1}^{n} R_i \cdot x_i - \frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) - R + \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i \right|_{2^N} \quad (16)$$

From the formulas derived above, it is obvious that $\bar{D}(X) - \bar{D}(X-1)$ is the additional term of the expression equal to

$$\bar{D}(X) - \bar{D}(X-1) = \left| -\frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) - R + \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i \right|_{2^N} \quad (17)$$
By considering that

$$2^N \cdot \bar{D}(X) + \sum_{i=1}^{n} R_i \cdot x_i - \frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) - R + \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i = 2^N \cdot \bar{D}(X-1) + \sum_{i=1}^{n} R_i \cdot |x_i - 1|_{m_i} > 0, \quad (18)$$

we obtain

$$2^N \cdot \bar{D}(X) + \sum_{i=1}^{n} R_i \cdot x_i > \frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) + R - \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i \quad (19)$$

For the function $\bar{D}(X)$ to be strictly increasing, it is necessary to satisfy the two following conditions.

**Condition 1.** $2^N \cdot \bar{D}(X) + \sum_{i=1}^{n} R_i \cdot x_i < 2^N$

This inequality makes it possible to pass from computation of the remainder of the division to the computation mod $2^N$ for $\bar{D}(X)$ in Equality (13), and hence in Equality (16) as well.

**Condition 2.** $\frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) + R - \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i > 0$

If this inequality holds and both Condition 1 and Inequality (19) are satisfied, it implies that the value of $\bar{D}(X)$ calculated by Equality (13) is larger than the value of $\bar{D}(X-1)$ calculated by Equality (16).

Whether any of these two conditions is satisfied, it depends on $N$. Now we will show how to determine the smallest $N$, for which both Conditions 1 and 2 hold. As the function $\bar{D}(X)$ is monotonic, hence $\bar{D}(X) \le \bar{D}(X-1)$. Thus, according to Equality (2)

$$\bar{D}(M-1) = \left| \sum_{i=1}^{n} \frac{k_1}{SQ} \cdot (m_i - 1) \right|_1 = 1 - \frac{n}{SQ} \quad (20)$$

Additionally, because $0 < R_i < 1$ and $\max_{1 \le i \le n} m_i = m_n$, therefore

$$\sum_{i=1}^{n} z(x_i) \cdot R_i \cdot x_i < n \cdot (m_n - 1) \quad (21)$$

Because Condition 1 leads to the inequality

$$2^N \cdot \left(1 - \frac{n}{SQ}\right) + n \cdot (m_n - 1) < 2^N \quad (22)$$

therefore

$$1 - \frac{n}{SQ} + \frac{n \cdot (m_n - 1)}{2^N} < 1 \quad (23)$$

which in turn leads to $2^N > SQ \cdot (m_n - 1)$, and finally to

$$N > \log_2(SQ \cdot (m_n - 1)) \quad (24)$$

From Condition 1, and assuming that Inequality (24) holds, we have

$$\bar{D}(X) - \bar{D}(X-1) = \frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) + R - \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i \quad (25)$$

Now consider the inequality

$$\frac{2^N}{SQ} \cdot \sum_{i=1}^{n} z(x_i) + R - \sum_{i=1}^{n} z(x_i) \cdot R_i \cdot m_i > 0 \quad (26)$$
If the inequality

$$ \frac{2^N}{\mathrm{SQ}} > m_i \cdot R_i - R \qquad (27) $$

holds for $1 \le i \le n$, then Inequality (26) is true for X with any number of zeros in its RNS representation. Therefore, we can estimate N from Inequality (27). Recalling that $0 \le R_i < 1$, $1 \le R < n$, and $\max_{1 \le i \le n} m_i = m_n$, therefore

$$ m_i \cdot R_i - R < m_n - 1, \qquad (28) $$

which implies that Inequality (27) holds if

$$ \frac{2^N}{\mathrm{SQ}} > m_n - 1, \qquad (29) $$

To estimate N, we calculate the logarithm of the last inequality

$$ N > \log_2(\mathrm{SQ} \cdot (m_n - 1)), \qquad (30) $$

which is identical to Inequality (24). Therefore, if Inequality (24) holds, then both Conditions 1 and 2 are satisfied, which concludes the proof. □

Inequality (24) can be considered as the condition that guarantees strict monotonicity of the MDF $\bar{D}(X)$: if it holds, to compare two RNS numbers X and Y, it suffices to compare the values of $\bar{D}(X)$ and $\bar{D}(Y)$. The above considerations can be formally summarized as the following algorithm.

**Algorithm 2:** Comparison of RNS numbers using MDF.

Input: $X = \{x_1, x_2, \dots, x_n\}$, $Y = \{y_1, y_2, \dots, y_n\}$

Output: "100" if $X < Y$, "010" if $X = Y$, and "001" if $X > Y$.

**Step 1.** Calculate $\bar{D}(X)$ and $\bar{D}(Y)$.

Note: These computations are independent and therefore they can be executed in parallel, provided that two circuits implementing the MDF are available.

**Step 2.** Compare the values of $\bar{D}(X)$ and $\bar{D}(Y)$.

1. if $\bar{D}(X) < \bar{D}(Y)$ then return "100"

2. if $\bar{D}(X) > \bar{D}(Y)$ then return "001"

3. if $\bar{D}(X) = \bar{D}(Y)$ then return "010"

In summary, the diagonal function $D(X)$ of [16,18] is monotonic for $0 \le X < M$, whereas the MDF $\bar{D}(X)$ proposed here is strictly monotonic over this set (which makes it possible to compare numbers directly).

The differences between $D(X)$ and $\bar{D}(X)$ are illustrated for a sample 3-moduli RNS $\{5, 11, 17\}$. Figure 2 shows the diagrams of the values of the functions $D(X)$ and $\bar{D}(X)$ for the first 15 values of X, which clearly reflect their monotonic properties and demonstrate their differences.

**Example 1.** Consider a sample set of $n = 3$ moduli $m_1 = 13$, $m_2 = 15$, and $m_3 = 17$ whose dynamic range is $M = 3315$. Here, we have $M_1 = \frac{M}{m_1} = 255$, $M_2 = \frac{M}{m_2} = 221$, $M_3 = \frac{M}{m_3} = 195$, which implies $SQ = M_1 + M_2 + M_3 = 255 + 221 + 195 = 671$, so that $N = [\log_2((m_n - 1) \cdot SQ)] = 14$ and the four constants

$$ \bar{k}_1 = 2^{14} \cdot \frac{|-1/13|_{671}}{671} = 6300, \quad \bar{k}_2 = 2^{14} \cdot \frac{|-1/15|_{671}}{671} = 12,014, \quad \bar{k}_3 = 2^{14} \cdot \frac{|-1/17|_{671}}{671} = 14,456 $$
<figure><img src="image_5.png" /><figcaption>Figure 2. Values of the functions for $0 \le X \le 14$: (a) $D(X)$ and (b) $\bar{D}(X)$.</figcaption></figure>

Let us compare three integers

$$X = 950 \xrightarrow{\text{RNS}} \{1, 5, 15\} \quad Y = 951 \xrightarrow{\text{RNS}} \{2, 6, 16\} \quad Z = 952 \xrightarrow{\text{RNS}} \{3, 7, 0\}$$

for which we have

$$\bar{D}(X) = |1 \cdot 6300 + 5 \cdot 12,014 + 15 \cdot 14,456|_{214} = 4682$$

$$\bar{D}(Y) = |2 \cdot 6300 + 6 \cdot 12,014 + 16 \cdot 14,456|_{214} = 4684$$

$$\bar{D}(Z) = |3 \cdot 6300 + 7 \cdot 12,014 + 0 \cdot 14,456|_{214} = 4694$$

Recall that according to Theorem 1, the function $\bar{D}(X)$ is strictly monotonic for any $0 \le X < M$. Indeed, it is seen that: (i) $\bar{D}(X) < \bar{D}(Y)$ implies $X < Y$ and (ii) $\bar{D}(Z) > \bar{D}(Y)$ implies $Z > Y$.

Figure 3 shows the general scheme of the new comparator that implements Algorithm 2 (here $b_i = \min\{\lfloor \log_2(m_i \cdot k_i) \rfloor, N\}$). Obviously, it is necessary to add more extra hardware than its simple counterpart using any reverse converter followed by the a-bit comparator, because only the latter small circuit must be added to the RNS-based processor. In our circuit, both the circuit computing $\bar{D}(X)$ and the N-bit comparator must be added. Nevertheless, the new comparator has two potential major advantages over the latter: (i) higher speed, because of the delay of the n-operand MOMA mod $2^N$ is certainly significantly smaller than of the n-operand MOMA mod $M$ [30,31] in the CRT-based version of the reverse converter or of its MRC-based version (a slightly larger size of the operands handled by the final N-bit comparator ($N = a + \lfloor \log_2 n \rfloor$ vs. $a$) has little impact on the area or delay of the final N-bit comparator); and (ii) lower power consumption, because of the significantly smaller circuitry involved in performing the comparison. Either claim will be confirmed by performance estimations obtained for ASIC implementations of various basic general RNS number comparators, presented in the next section.
<figure><img src="image_6.png" /><figcaption>**Figure 3.** Hardware implementation of the new comparator built using the MDF.</figcaption></figure>

## 4. Performance Estimations

In this section, we first present an approximate evaluation of the performance of hardware implementations of the new general RNS comparators and their three best-known counterparts, and then we provide more accurate estimations for ASIC implementations of all circuits considered.

Suppose that all *n* RNS moduli are *l*-bit numbers. Then, the basic parameters of operands involved in modulo operations handled by four general RNS number comparators can be summarized as listed in Table 1. First, recall that all these circuits have a number of steps growing logarithmically in the function of the number of moduli *n*, i.e., they all have O(log *n*) delay. Second, notice that the following inequalities hold: $\sqrt{M} < SQ < M < 2^N$ and $a_{\sqrt{M}} < a_{SQ} < a < N$. The three circuits based on the CRT, SQT, and MDF have a similar structure, composed of the *n*-operand modulo adder, with the major difference made by the modulus. Because neither *M* nor *SQ* is a power of 2 and *a* > $a_{SQ}$, then it seems that the SQT-based circuit should involve less hardware and be faster than the CRT-based one. On the other hand, because the MDF-based circuit proposed here uses the *n*-operand adder modulo a power of 2 ($2^N$), it enjoys the major advantage of all arithmetic circuits mod $2^N$: significantly smaller delay and exceptional hardware efficiency compared to all its counterparts modulo any odd modulus involving cumbersome and lengthy operations of finding the remainder of the division by a large and awkward number *M* or *SQ*. The simplicity and the speed gained by the latter outweighs the minor delay/area differences due to a slightly larger final comparator of *N*-bit vs. *a*-bit and $a_{SQ}$-bit numbers. As for the comparator based on the CRT-II of [17] it executes $[\log_2 n]$ iterative steps on operands of growing size and involving computations modulo a size growing up to about $\sqrt{M}$. On one hand, $\sqrt{M}$ is not only the smallest of the moduli involved in computations by all comparators considered, but it is also involved only in the final stage of iterative computations, which suggests that it would result in some advantages. On the other hand, the estimation of delay/area performance of this circuit is difficult, because each iterative step involves modulo computations which, despite being executed on relatively small size moduli are nevertheless time-consuming and executed serially.
<table><caption>**Table 1.** Summary of basic parameters of four RNS comparison methods for general moduli sets.</caption><thead><tr><th rowspan="2">Method</th><th colspan="2">Operands</th><th rowspan="2">Modulus</th></tr><tr><th>Size [bits]</th><th>Number</th></tr></thead><tbody><tr><td>CRT</td><td>a ≤ n·l</td><td>n</td><td>M</td></tr><tr><td>SQT</td><td>a<sub>SQ</sub> ≤ (n − 1)·l + [log<sub>2</sub> n]</td><td>n</td><td>SQ</td></tr><tr><td>CRT-II<sup>†</sup></td><td>a ≤ [(n·l)/2]</td><td>[n/2]</td><td>√M</td></tr><tr><td>MDF</td><td>N ≤ n·l + [log<sub>2</sub> n]</td><td>n</td><td>2<sup>N</sup></td></tr></tbody></table>

CRT—the direct method based on CRT; SQT—the method by Dimauro et al. [16]; CRT II—the method by Wang et al. [17]; MDF—the new method proposed here; † only the largest sizes of operands and moduli are indicated.

To obtain more accurate complexity estimations, we synthesized all four comparators described above for various RNS moduli sets, which are grouped into two classes, listed in Table 2. Class 1 consists of 4-moduli sets; each set composed of moduli of the same size *p*. Varying the size of moduli *p* ∈ {5, 7, 9, 11, 13} makes it possible to observe comparators' performance in the function of the dynamic range *M*, which grows only with the size of the moduli but not with their number (which remains constant). Class 2 consists of moduli of the same size (we chose *p* = 7 bits), whose number *n* varies from 3 to 8, allowing to observe comparators' performance in the function of the number of moduli. All sets of selected moduli consist of the largest existing pairwise prime moduli for a given *n*.

<table><caption>**Table 2.** Sample sets of moduli and their characteristics.</caption><thead><tr><th>Class</th><th>n</th><th>Moduli Set</th><th>Size of Moduli [Bits]</th><th>Size of M [Bits]</th><th>Size of SQ [Bits]</th><th>N</th></tr></thead><tbody><tr><td rowspan="5">1</td><td rowspan="5">4</td><td>27, 29, 31, 32</td><td>5</td><td>20</td><td>17</td><td>22</td></tr><tr><td>123, 125, 127, 128</td><td>7</td><td>28</td><td>23</td><td>30</td></tr><tr><td>507, 509, 511, 512</td><td>9</td><td>36</td><td>29</td><td>38</td></tr><tr><td>2043, 2045, 2047, 2048</td><td>11</td><td>44</td><td>35</td><td>46</td></tr><tr><td>8187, 8189, 8191, 8192</td><td>13</td><td>52</td><td>41</td><td>54</td></tr><tr><td rowspan="8">2</td><td>3</td><td>125, 127, 128</td><td>7</td><td>21</td><td>16</td><td>23</td></tr><tr><td>4</td><td>123, 125, 127, 128</td><td>7</td><td>28</td><td>23</td><td>30</td></tr><tr><td>5</td><td>121, 123, 125, 127, 128</td><td>7</td><td>35</td><td>31</td><td>38</td></tr><tr><td>6</td><td>119, 121, 123, 125, 127, 128</td><td>7</td><td>42</td><td>38</td><td>45</td></tr><tr><td>7</td><td>113, 119, 121, 123, 125, 127, 128</td><td>7</td><td>49</td><td>45</td><td>52</td></tr><tr><td>8</td><td>109, 113, 119, 121, 123, 125, 127, 128</td><td>7</td><td>56</td><td>52</td><td>59</td></tr></tbody></table>

The circuits were described in parametrized structural VHDL following identical coding guidelines and synthesized following the similar layout of module hierarchy and primitive components like adders. The additions and multiplications were implemented with register-transfer level (RTL) operators and selection of their architectures was left to be done by the synthesis tool. We performed logic synthesis of the comparators for a range of target moduli sets using Cadence RTL Compiler v. 8.1 and an industrial 65 nm low-power library (STM CMOS065LP). For each design and moduli set, the minimum delay was found, which we assumed to be the smallest delay target when the synthesis was still able to achieve a non-negative timing slack. The cell area and total power (including dynamic and leakage components) reported by the synthesis tool were given an area and power figures.

The complexity characteristics obtained are detailed in Tables 3–8 and visualized in Figures 4 and 5. It can be seen that the delay of the new comparator proposed here grows equally slowly (almost linearly) while increasing the dynamic range *DR* or the number of moduli *n*. It seems that it results directly from the possibility of replacing cumbersome operations of finding the remainder of the division by a large and awkward number with significantly simpler multi-operand additions mod 2^N. The synthesis results suggest that the new comparator proposed here is faster than all known similar circuits for all sample moduli sets considered, with delay reduction ranging from over 11% to
over 75% compared to the fastest circuit designed using existing methods. Only the basic CRT-based implementation introduces delay slightly larger but only in a few cases. The largest delay comes with the introduction of the comparator based on the CRT-II of [17].

<table><caption>**Table 3.** Delay [ps] for 4-moduli sets composed of *p*] for 4-moduli sets composed of *p*-bit moduli, 5 ≤ *p* ≤ 13, *p* odd (Class 1).</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>5</td><td>20</td><td>3187</td><td>2954</td><td>5401</td><td>2100</td><td>51.76</td><td>40.67</td><td>157.19</td></tr><tr><td>7</td><td>28</td><td>3993</td><td>3626</td><td>5903</td><td>2427</td><td>64.52</td><td>49.40</td><td>143.22</td></tr><tr><td>9</td><td>36</td><td>3132</td><td>4209</td><td>6624</td><td>2583</td><td>21.25</td><td>62.95</td><td>156.45</td></tr><tr><td>11</td><td>44</td><td>3430</td><td>5371</td><td>6844</td><td>2698</td><td>27.13</td><td>99.07</td><td>153.67</td></tr><tr><td>13</td><td>52</td><td>4099</td><td>5719</td><td>7248</td><td>2810</td><td>45.87</td><td>103.52</td><td>157.94</td></tr></tbody></table>

<table><caption>**Table 4.** Area [µm²] for 4-moduli sets composed of *p*-bit moduli, 5 ≤ *p* ≤ 13, *p* odd (Class 1).</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>5</td><td>20</td><td>11537</td><td>16193</td><td>14398</td><td>11109</td><td>3.85</td><td>45.76</td><td>29.61</td></tr><tr><td>7</td><td>28</td><td>21732</td><td>23159</td><td>20827</td><td>15213</td><td>42.85</td><td>52.23</td><td>36.90</td></tr><tr><td>9</td><td>36</td><td>23073</td><td>31970</td><td>28910</td><td>21036</td><td>9.68</td><td>51.98</td><td>37.43</td></tr><tr><td>11</td><td>44</td><td>29733</td><td>54727</td><td>36486</td><td>26901</td><td>10.53</td><td>103.44</td><td>35.63</td></tr><tr><td>13</td><td>52</td><td>47798</td><td>67636</td><td>46237</td><td>32197</td><td>48.45</td><td>110.07</td><td>43.61</td></tr></tbody></table>

<table><caption>**Table 5.** Power [µW] for 4-moduli sets composed of *p*-bit moduli, 5 ≤ *p* ≤ 13, *p* odd (Class 1).</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>5</td><td>20</td><td>3108</td><td>3939</td><td>5784</td><td>2015</td><td>52.24</td><td>95.48</td><td>187.05</td></tr><tr><td>7</td><td>28</td><td>6850</td><td>6915</td><td>10068</td><td>3011</td><td>127.50</td><td>129.66</td><td>234.37</td></tr><tr><td>9</td><td>36</td><td>7721</td><td>11950</td><td>16371</td><td>4352</td><td>77.41</td><td>174.59</td><td>276.17</td></tr><tr><td>11</td><td>44</td><td>11338</td><td>25169</td><td>22576</td><td>6150</td><td>84.36</td><td>309.25</td><td>267.09</td></tr><tr><td>13</td><td>52</td><td>20588</td><td>32301</td><td>30468</td><td>7380</td><td>178.97</td><td>337.68</td><td>312.85</td></tr></tbody></table>

<table><caption>**Table 6.** Delay [ps] for various n-moduli sets, 3 ≤ *n* ≤ 8] for various n-moduli sets, 3 ≤ *n* ≤ 8 (Class 2).</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>3</td><td>21</td><td>2465</td><td>3388</td><td>3831</td><td>1972</td><td>25.00</td><td>71.81</td><td>94.27</td></tr><tr><td>4</td><td>28</td><td>3993</td><td>3626</td><td>5903</td><td>2427</td><td>64.52</td><td>49.40</td><td>143.22</td></tr><tr><td>5</td><td>35</td><td>3479</td><td>5099</td><td>7861</td><td>3127</td><td>11.26</td><td>63.06</td><td>151.39</td></tr><tr><td>6</td><td>42</td><td>3682</td><td>6102</td><td>10950</td><td>3289</td><td>11.95</td><td>85.53</td><td>232.93</td></tr><tr><td>7</td><td>49</td><td>5941</td><td>6210</td><td>11243</td><td>3377</td><td>75.93</td><td>83.89</td><td>232.93</td></tr><tr><td>8</td><td>56</td><td>6115</td><td>5877</td><td>13521</td><td>3623</td><td>68.78</td><td>62.21</td><td>273.20</td></tr></tbody></table>
<table><caption>**Table 7.** Area [$\mu m^2$] for various n-moduli sets, $3 \le n \le 8$ (Class 2).</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>3</td><td>21</td><td>9814</td><td>11281</td><td>7370</td><td>9690</td><td>1.28</td><td>16.42</td><td>-23.94</td></tr><tr><td>4</td><td>28</td><td>21732</td><td>23159</td><td>20827</td><td>15213</td><td>42.85</td><td>52.23</td><td>36.90</td></tr><tr><td>5</td><td>35</td><td>26130</td><td>36701</td><td>31836</td><td>28150</td><td>-7.18</td><td>30.38</td><td>13.09</td></tr><tr><td>6</td><td>42</td><td>43209</td><td>68508</td><td>51542</td><td>41463</td><td>4.21</td><td>65.23</td><td>24.31</td></tr><tr><td>7</td><td>49</td><td>93113</td><td>98583</td><td>72575</td><td>63926</td><td>45.66</td><td>54.21</td><td>13.53</td></tr><tr><td>8</td><td>56</td><td>107450</td><td>129063</td><td>103950</td><td>76654</td><td>40.18</td><td>68.37</td><td>35.61</td></tr></tbody></table>

<table><caption>**Table 8.** Power [$\mu W$] for various n-moduli sets, $3 \le n \le 8$ (Class 2).</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">DR<br>[bits]</th><th colspan="4">3</th><th colspan="3">Reduction [%]</th></tr><tr><th>CRT</th><th>SQT</th><th>CRT-II</th><th>New</th><th><sup>3-6</sup>&frasl;<sub>6</sub></th><th><sup>4-6</sup>&frasl;<sub>6</sub></th><th><sup>5-6</sup>&frasl;<sub>6</sub></th></tr></thead><tbody><tr><td>3</td><td>21</td><td>2750</td><td>3474</td><td>2063</td><td>1688</td><td>62.91</td><td>105.81</td><td>22.22</td></tr><tr><td>4</td><td>28</td><td>6850</td><td>6915</td><td>10068</td><td>3011</td><td>127.50</td><td>129.66</td><td>234.37</td></tr><tr><td>5</td><td>35</td><td>8523</td><td>14188</td><td>18247</td><td>7748</td><td>10.00</td><td>83.12</td><td>135.51</td></tr><tr><td>6</td><td>42</td><td>15461</td><td>31885</td><td>36415</td><td>12584</td><td>22.86</td><td>153.38</td><td>189.38</td></tr><tr><td>7</td><td>49</td><td>45114</td><td>43488</td><td>56798</td><td>19053</td><td>136.78</td><td>128.25</td><td>198.11</td></tr><tr><td>8</td><td>56</td><td>43278</td><td>54785</td><td>90474</td><td>26095</td><td>65.85</td><td>109.94</td><td>246.71</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Figure 4.** Complexity characteristics of RNS comparators for Class 1 moduli sets.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Figure 5.** Complexity characteristics of RNS comparators for Class 2 moduli sets.</figcaption></figure>

Moreover, the speed advantage of the new comparators was achieved using less hardware resources, with only two exceptions. For large dynamic ranges, hardware reduction is significant, as it can exceed 40% compared to the least complex existing designs. For all cases considered, the SQT-based method of [25] consumes more hardware resources than any other method. Hardware complexity of the basic CRT-based comparator deserves some special comments, because most of it is the reverse
converter, which is used anyway as a stand-alone circuit. Therefore, it should not be considered a contributor to the overall hardware complexity.

Finally, power-consumption seems the major advantage of the new comparators, as its reduction ranges from over 50% to over 178% for Class 1 moduli sets and from over 10% to over 130% for Class 2 moduli sets. Moreover, it was achieved using circuits which are faster for all cases considered. In this context, using specifically designed comparators instead of the CRT-based comparators (which actually require including the least amount of extra hardware: only the final comparator of a-bit numbers), could be of some practical interest. This is because once the reverse converter is activated just for the purpose of comparing numbers, it could be extremely power-consuming, as can be seen from the data listed in Tables 5 and 8, as well as shown in Figures 4c and 5c.

## 5. Conclusions

This paper proposes a new general approach to the comparison of the numbers represented in Residue Number System (RNS). It is based on a newly introduced concept of the modified diagonal function, which serves as a theoretical basis to develop a significantly faster and more efficient comparison algorithm. It made it possible to introduce a new positional characteristic of an RNS number which is strictly monotonic so that it makes it possible to precisely reflect a relative positioning of numbers. Now, unlike in existing algorithms, computations involving cumbersome operations of finding the remainder of the division by a large and awkward number are replaced with significantly simpler computations involving only a power of 2 modulus. The newly proposed comparator and its most efficient known counterparts applicable for arbitrary RNS moduli sets, designed using various methods for several sample moduli sets, were synthesized for the 65 nm technology. Performance estimations obtained suggest that the new circuits enjoy delay reduction ranging from over 11% to over 75%, compared to the fastest circuits designed using existing methods. Moreover, it is achieved using less hardware, the reduction can even reach over 41%, and accompanied by significantly reduced power-consumption which in several cases exceeds 100%. Therefore, it seems that the presented method leads to the design of what is currently the most efficient hardware comparators of numbers represented using a general RNS moduli set. The magnitude comparison of RNS numbers, besides being used directly (like in some implementations of recent cryptographic algorithms using RNS), is also essential for the implementation of other RNS non-modular operations like division, sign detection, and overflow detection. Future research will include extensions of the approach proposed to handle other difficult non-modular RNS operations like sign and overflow detection.

**Author Contributions:** Formal analysis, M.B., M.D. and S.J.P.; Funding acquisition, M.B. and M.D.; Investigation, M.B., M.D. and S.J.P.; Methodology, S.J.P. and A.T.; Project administration, M.B. and A.A.; Software, M.D. and P.P.; Supervision, N.C. and A.A.; Validation, M.B. and A.T.; Writing—Original draft, M.D., S.J.P. and A.T.; Writing—Review & editing, M.B., S.J.P. and A.T. All authors have read and agreed to the published version of the manuscript.

**Funding:** The reported study was funded by RFBR, project number 20-37-70023 and project NCFU.

**Conflicts of Interest:** The authors declare no conflict of interest.

## Abbreviations and Symbols

<table><tr><td>CRT</td><td>Chinese Remainder Theorem</td></tr><tr><td>DR</td><td>Dynamic Range</td></tr><tr><td>MDF</td><td>Modified Diagonal Function</td></tr><tr><td>MOMA</td><td>Multi-Operand Modular Adder</td></tr><tr><td>MRC</td><td>Mixed Radix Conversion</td></tr><tr><td>RNS</td><td>Residue Number System</td></tr><tr><td>SQ</td><td>Sum of Quotients</td></tr><tr><td>SQT</td><td>Sum of Quotients Technique</td></tr><tr><td>a</td><td>the number of bits to represent M</td></tr></table>
<table><tr><td>a<sub>i</sub></td><td>the number of bits to represent x<sub>i</sub></td></tr><tr><td>a<sub>SQ</sub></td><td>the number of bits to represent SQ</td></tr><tr><td>D(X)</td><td>the diagonal function</td></tr><tr><td>D&#773;(X)</td><td>the modified diagonal function</td></tr><tr><td>h<sub>i</sub> = [1/m<sub>i</sub>]<sub>SQ</sub></td><td>the multiplicative inverse of m<sub>i</sub> mod SQ</td></tr><tr><td>{m<sub>1</sub>, m<sub>2</sub>, ..., m<sub>n</sub>}</td><td>RNS moduli set</td></tr><tr><td>n</td><td>the number of moduli</td></tr><tr><td>N</td><td>the number of bits of the fraction part</td></tr><tr><td>x<sub>i</sub></td><td>the residue modulo (mod) m<sub>i</sub></td></tr><tr><td>{x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>}</td><td>RNS representation of an integer X</td></tr></table>

References

1. Szabo, N.; Tanaka, R. Residue Arithmetic and Its Applications to Computer Technology; McGraw Hill: New York, NY, USA, 1967.

2. Mohan, P.V.A. Residue Number Systems; Birkhauser: Basel, Switzerland, 2016; ISBN 978-3-319-41383-9.

3. Nannarelli, A.; Cardarilli, G.C.; Re, M. Power-delay tradeoffs in residue number system. In Proceedings of the 2003 International Symposium on Circuits and Systems, 2003, ISCAS '03, Bangkok, Thailand, 25-28 May 2003; Volume 5, pp. V-413-V-416.

4. Cardarilli, G.C.; Del Re, A.; Nannarelli, A.; Re, M. Low-power implementation of polyphase filters in Quadratic Residue Number System. In Proceedings of the 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No.04CH37512), Vancouver, BC, Canada, 23-26 May 2004; p. II-725.

5. Patronik, P.; Berezowski, K.; Piestrak, S.J.; Biernat, J.; Shrivastava, A. Fast and energy-efficient constant-coefficient FIR filters using residue number system. In Proceedings of the IEEE/ACM International Symposium on Low Power Electronics and Design, Fukuoka, Japan, 1-3 August 2011; pp. 385-390.

6. Chervyakov, N.I.; Lyakhov, P.A.; Babenko, M.G. Digital filtering of images in a residue number system using finite-field wavelets. Autom. Control Comput. Sci. **2014**, *48*, 180-189. [CrossRef]

7. Keller, T.; Liew, T.H. Lajos Hanzo Adaptive redundant residue number system coded multicarrier modulation. IEEE J. Sel. Areas Commun. **2000**, *18*, 2292-2301. [CrossRef]

8. Posch, K.C.; Posch, R. Residue number systems: A key to parallelism in public key cryptography. In Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing, Arlington, TX, USA, 1-4 December 1992; pp. 432-435.

9. Albicocco, P.; Cardarilli, G.C.; Nannarelli, A.; Re, M. Twenty years of research on RNS for DSP: Lessons learned and future perspectives. In Proceedings of the 2014 International Symposium on Integrated Circuits (ISIC), Singapore, 10-12 December 2014; pp. 436-439.

10. Chokshi, R.; Berezowski, K.S.; Shrivastava, A.; Piestrak, S.J. Exploiting residue number system for power-efficient digital signal processing in embedded processors. In Proceedings of the 2009 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems—CASES '09; ACM Press: New York, NY, USA, 2009; p. 19.

11. Patronik, P.; Piestrak, S.J. Hardware/software approach to designing low-power RNS-enhanced arithmetic units. IEEE Trans. Circuits Syst. I Regul. Pap. **2017**, *64*, 1031-1039. [CrossRef]

12. Chang, C.-H.; Molahosseini, A.S.; Zarandi, A.A.E.; Tay, T.F. Residue number systems: A paradigm to datapath optimization for low-power and high-performance digital signal processing applications. IEEE Circuits Syst. Mag. **2015**, *15*, 26-44. [CrossRef]

13. Akushskii, I.J.; Burcev, V.M.; Pak, I.T. A new positional characteristic of non-positional codes and its application. In Coding Theory and the Optimization of Complex Systems; Nauka: Alma-Ata, Russia, 1977.

14. Miller, D.D.; Altschul, R.E.; King, J.R.; Polky, J.N. Analysis of the residue class core function of Akushskii, Burcev, and Pak. In Residue Number System Arithmetic: Modern Applications in Digital Signal Processing; IEEE Press: New York, NY, USA, 1986; pp. 390-401.

15. Lu, M.; Chiang, J.-S. A novel division algorithm for the residue number system. IEEE Trans. Comput. **1992**, *41*, 1026-1032. [CrossRef]

16. Dimauro, G.; Impedovo, S.; Pirlo, G. A new technique for fast number comparison in the residue number system. IEEE Trans. Comput. **1993**, *42*, 608-612. [CrossRef]
17. Wang, Y.; Song, X.; Aboulhamid, M. A new algorithm for RNS magnitude comparison based on New Chinese Remainder Theorem II. In Proceedings of the Proceedings Ninth Great Lakes Symposium on VLSI, Ypsilanti, MI, USA, 4–6 March 1999; pp. 362–365.

18. Dimauro, G.; Impedovo, S.; Pirlo, G.; Salzo, A. RNS architectures for the implementation of the 'diagonal function'. *Inf. Process. Lett.* **2000**, *73*, 189–198. [CrossRef]

19. Sousa, L. Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli. In Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH'07), Montpellier, France, 25–27 June 2007; pp. 240–250.

20. Bi, S.; Gross, W.J. The Mixed-Radix Chinese Remainder Theorem and Its Applications to Residue Comparison. *IEEE Trans. Comput.* **2008**, *57*, 1624–1632. [CrossRef]

21. Pirlo, G.; Impedovo, D. A new class of monotone functions of the residue number system. *Int. J. Math. Model. Methods Appl. Sci.* **2013**, *7*, 803–809.

22. Chervyakov, N.I.; Babenko, M.G.; Lyakhov, P.A.; Lavrinenko, I.N. An Approximate Method for Comparing Modular Numbers and its Application to the Division of Numbers in Residue Number Systems. *Cybern. Syst. Anal.* **2014**, *50*, 977–984. [CrossRef]

23. Piestrak, S.J. A note on RNS architectures for the implementation of the diagonal function. *Inf. Process. Lett.* **2015**, *115*, 453–457. [CrossRef]

24. Chervyakov, N.I.; Molahosseini, A.S.; Lyakhov, P.A.; Babenko, M.G.; Lavrinenko, I.N.; Lavrinenko, A.V. Comparison of modular numbers based on the Chinese remainder theorem with fractional values. *Autom. Control Comput. Sci.* **2015**, *49*, 354–365. [CrossRef]

25. Sousa, L.; Martins, P. Sign Detection and Number Comparison on RNS 3-Moduli Sets {2ⁿ - 1, 2ⁿ⁺ᵏ, 2ⁿ + 1}. *Circuits Syst. Signal Process.* **2017**, *36*, 1224–1246. [CrossRef]

26. Vu, T.V. Efficient Implementations of the Chinese Remainder Theorem for Sign Detection and Residue Decoding. *IEEE Trans. Comput.* **1985**, *C*-34, 646–651. [CrossRef]

27. Hung, C.Y.; Parhami, B. Error analysis of approximate Chinese-remainder-theorem decoding. *IEEE Trans. Comput.* **1995**, *44*, 1344–1348. [CrossRef]

28. Akkal, M.; Siy, P. A new Mixed Radix Conversion algorithm MRC-II. *J. Syst. Archit.* **2007**, *53*, 577–586. [CrossRef]

29. Hwang, K. *Computer Arithmetic Principles, Architecture, and Design*; Wiley: New York, NY, USA, 1979.

30. Piestrak, S.J. Design of residue generators and multioperand modular adders using carry-save adders. *IEEE Trans. Comput.* **1994**, *43*, 68–77. [CrossRef]

31. Piestrak, S.J. Design of high-speed residue-to-binary number system converter based on Chinese Remainder Theorem. In Proceedings of the 1994 IEEE International Conference on Computer Design: VLSI in Computers and Processors, Cambridge, MA, USA, 10–12 October 1994; pp. 508–511.

**Publisher's Note:** MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

<figure><img src="image_9.png" /></figure>

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).