Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Algorithms for comparison in residue number systems

Authors: Hanshen Xiao; Yu Ye 0001; Guoqiang Xiao 0001; Qin Kang;

Algorithms for comparison in residue number systems

Abstract

Residue Number Systems (RNSs) has been widely used in digital signal processing (DSP) systems and cases of fast computing, parallelism and fault tolerant because of its carry-free property. However, the comparison operation in an RNS is quite difficult and the computation cost is high, which are a significant limitation to apply it for division, scaling and overflow detection. Reverse conversions are used to the comparison operation in an RNS over last decades, where comparisons are carried out in a binary (weighted) system rather than an RNS. Chinese Remainder Theorem (CRT) and Mixed-radix Conversion (MRC) are the two main methods to perform residue-to-binary (R2B) conversion. However, the calculation of mix-radix coefficients in MRC scheme is a strictly sequential manner, while modular and multiplication operations related to large numbers are required in CRT scheme although they can be implemented in fully parallel. Especially, in order to satisfy the requirements of wide word binary operations such as public-key cryptography and modern digital signal processing (DSP), neither CRT nor MRC is a suitable solution for comparison in an RNS when the processed numbers are large enough. In the paper, novel comparison algorithms are proposed, which achieve comparison operation in an RNS directly without R2B reverse conversions. Even the average time complexity of the algorithm carried out in a sequential manner is O(1). To the best of our knowledge, the proposed algorithms first achieve all calculations for comparison in an RNS completed within each modulus channel in general cases.

Related Organizations
  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    7
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
7
Top 10%
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!