Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: positional characteristics

Sortuj według:

Ogranicz wyniki do:

Efficient implementation of Chinese remainder theorem in minimally redundant residue number system

Selianinau Mikhail

Computer Science

2020

T. 21 (2)

237--252

The Chinese remainder theorem is 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 that is used in the residue number system. The proposed method does not use large modulo addition operations as compared to a straightforward implementation of the Chinese remainder theorem algorithm. The rank of a number is equal to the sum of an inexact rank and a two-valued correction factor that only takes on values of 0 or 1. We propose a minimally redundant residue number system that provides a low computational complexity of the rank calculation. The effectiveness of the novel method is analyzed regarding a conventional non-redundant residue number system. Owing to the extension of the residue code, the complexity of the rank calculation goes down from O(k2) to O(k) by adding the extra residue modulo 2 (where k equals the number of non-redundant residues).