- Tytuł:
- An efficient implementation of the Chinese Remainder Theorem in minimally redundant Residue Number System
- Autorzy:
- Selianinau, Mikhail
- Powiązania:
- https://bibliotekanauki.pl/articles/1839284.pdf
- Data publikacji:
- 2020
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
residue number system
Chinese remainder theorem
residue code
rank of a number
positional characteristics - Opis:
- The Chinese Remainder Theorem (CRT) widely used in many modern computer applications. This paper presents an efficient approach to the calculation of the rank of a number, a principal positional characteristic used in the Residue Number System (RNS). The proposed method does not use large modulo addition operations compared to a straightforward implementation of the CRT algorithm. The rank of a number is equal to a sum of an inexact rank and a two-valued correction factor that only takes on the values 0 or 1. We propose a minimally redundant RNS, which provides low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed concerning conventional non-redundant RNS. Owing to the extension of the residue code, by adding the extra residue modulo 2, the complexity of rank calculation goes down from \(O(k^2)\) to \(O(k)\), where \(k\) equals the number of residues in non-redundant RNS.
- Źródło:
-
Computer Science; 2020, 21 (2); 225-240
1508-2806
2300-7036 - Pojawia się w:
- Computer Science
- Dostawca treści:
- Biblioteka Nauki
Artykuł