# A Division Algorithm in a Redundant Residue Number System Using Fractions
## 3 Simulation of the Proposed Algorithm  
It follows from the analysis of the modular division scheme that the comparison and sign detection unit is the main component determining its computational complexity. This unit can be implemented based on the CRT, MRNS, or CRT with fractions. We have considered the models of all three types. The experimental simulation has been performed using ISE Design Suite 14.7. Kintex-7 KC705 XC7K70T-2 FBG676 without DSP48E1B blocks has been chosen as the goal of compilation. This FPGA contains 10,250 slices and 300 input-output blocks. During the simulation, we varied the digit capacity of the moduli under a fixed number of bases. For each type of the model, same prime bases of a given capacity have been selected; in particular, four bases with module bits 5, 9, 13, 17, 21, and 25. The dynamic range of the system is approximately the product of the number of bases and their digit capacities. Only the bottleneck of the RNS division algorithm was implemented in hardware. The remaining parts of the division algorithm are very similar to the division operation in the standard IEEE library \"ieee.numeric_std.all\" and require approximately the same amount of resources in hardware implementation. Figure 4 shows the resource usage graph of this FPGA with different capacity moduli for each type of the model. Table 1 shows detailed resource utilization for all approaches considered. Figure 3: The scheme of positional characteristics calculation based on CRTf. All the considered algorithms were implemented on the corresponding FPGA. The architectures for CRT and MRC from [4] were simulated for comparison. In addition, the results for the division algorithm in the weighted numeric system (WNS) are also presented. For division in the WNS, an algorithm from standard IEEE library \"ieee.numeric_std.all\" was implemented. The pipeline in the binary division is implemented like in [26]. These results clearly show the fact that the additional circuit logic for the proposed method using CRT with fractions does not exceed 25% of the WNS division algorithm costs. We will comprehend the scheme latency as the maximum time spent by an arbitrary signal to run over the whole scheme from a certain input to a certain output. Latency estimation allows describing the performance of the suggested algorithm, including the working frequency of the scheme. For each type of model, Figure 5 presents the working frequency of the scheme for the base systems with different digit capacities of the moduli. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multirow{2}{*}{**Utilization**} & \multicolumn{6}{c}{**Dynamic Range of RNS, Count of Bits**} \\ \cline{3-8}  & & **18** & **33** & **49** & **65** & **81** & **97** \\ \hline \multirow{3}{*}{CRT with fractions} & LUTs & 253 & 843 & 1700 & 2684 & 4454 & 6367 \\  & Slices & 71 & 219 & 438 & 689 & 1135 & 1618 \\  & Delay, ns & 11.3 & 12.361 & 14.331 & 15.992 & 17.983 & 18.962 \\ \hline \multirow{3}{*}{CRT} & LUTs & 473 & 1571 & 3064 & 5105 & 7743 & 11643 \\  & Slices & 138 & 467 & 896 & 1457 & 2165 & 3160 \\  & Delay, ns & 37.607 & 62.5 & 96.633 & 123.116 & 158.002 & 189.999 \\ \hline \multirow{3}{*}{MRC} & LUTs & 325 & 1005 & 2073 & 3214 & 5507 & 7907 \\  & Slices & 113 & 321 & 662 & 865 & 1444 & 2117 \\  & Delay, ns & 37.412 & 70.032 & 117.226 & 161.908 & 196.296 & 285.723 \\ \hline \multirow{3}{*}{WNS division} & LUTs & 865 & 2936 & 6474 & 11,395 & 17,703 & 25,389 \\  & Slices & 319 & 840 & 2093 & 3614 & 4526 & 6512 \\ \cline{1-1}  & Delay, ns & 47.626 & 98.089 & 169.874 & 227.468 & 375.987 & 485.976 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Resources utilization and total delay. Figure 4: FPGA Kintex-7 KC705 XC7K70T-2 FB676 resource usage by selected calculation basis: (**a**) number of occupied Slices, (**b**) number of LUTs. As an example, consider a 64-bit capacity as the most widespread in modern computer systems.