Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms for Comparison in Residue Number Systems
KTH, School of Electrical Engineering (EES), Information Science and Engineering.
2016 (English)In: 2016 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2016, 2016, 7820790Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2016. 7820790
Keyword [en]
Comparison Algorithms, Residue Number System, Chinese Remainder Theorem, Parallelism, Short Wordlength Operation
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-203187DOI: 10.1109/APSIPA.2016.7820790ISI: 000393591800118Scopus ID: 2-s2.0-85013773760ISBN: 9789881476821 (print)OAI: oai:DiVA.org:kth-203187DiVA: diva2:1081279
Conference
2016 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA 2016, Jeju, South Korea, 13 December 2016 through 16 December 2016
Note

QC 20170313

Available from: 2017-03-13 Created: 2017-03-13 Last updated: 2017-06-09Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Ye, Yu
By organisation
Information Science and Engineering
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 17 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf