| Summary: | In this paper, we deal with the critical problems in residue arithmetic. The reverse conversion from a Residue Number System (RNS) to positional notation is a main non-modular operation, and it constitutes a basis of other non-modular procedures used to implement various computational algorithms. We present a novel approach to the parallel reverse conversion from the residue code into a weighted number representation in the Mixed-Radix System (MRS). In our proposed method, the calculation of mixed-radix digits reduces to a parallel summation of the small word-length residues in the independent modular channels corresponding to the primary RNS moduli. The computational complexity of the developed method concerning both required modular addition operations and one-input lookup tables is estimated as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><msup><mi>k</mi><mn>2</mn></msup><mo>/</mo><mn>2</mn></mfenced></mrow></semantics></math></inline-formula>, where <i>k</i> equals the number of used moduli. The time complexity is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mfenced separators="" open="(" close=")"><mfenced separators="" open="⌈" close="⌉"><msub><mi>log</mi><mn>2</mn></msub><mi>k</mi></mfenced></mfenced></mrow></semantics></math></inline-formula> modular clock cycles. In pipeline mode, the throughput rate of the proposed algorithm is one reverse conversion in one modular clock cycle.
|
|---|