Fast Sign Detection Algorithm for the RNS Moduli Set ${2^{n+1}-1, 2^{n}-1, 2^{n}}$

Author

Minghe Xu ; Zhenpeng Bian ; Ruohe Yao

Author_Institution

Sch. of Electron. & Inf. Eng., South China Univ. of Technol., Guangzhou, China

Volume

23

Issue

2

fYear

2015

fDate

Feb. 2015

Firstpage

379

Lastpage

383

Abstract

This brief presents a fast sign detection algorithm for the residue number system moduli set {2ⁿ⁺¹ - 1, 2ⁿ - 1, 2ⁿ}. First, a sign detection algorithm for the restricted moduli set is described. The new algorithm allows for parallel implementation and consists exclusively of modulo 2ⁿ additions. Then, a sign detection unit for the moduli set {2ⁿ⁺¹ - 1, 2ⁿ - 1, 2ⁿ} is proposed based on the new sign detection algorithm. The unit can be implemented using one carry save adder, one comparator and one prefix adder. The experimental results demonstrate that the proposed circuit unit offers 63.8%, 44.9%, and 67.6% savings on average in area, delay and power, respectively, compared with a unit based on one of the best sign detection algorithms.

Keywords

adders; carry logic; comparators (circuits); residue number systems; set theory; RNS moduli set; carry save adder; comparator; fast sign detection algorithm; parallel implementation; prefix adder; residue number system; {2ⁿ⁺¹ - 1, 2ⁿ - 1, 2ⁿ}; Adders; Delays; Detection algorithms; Hardware; Optimization; Standards; Very large scale integration; Computer arithmetic; residue number system (RNS); restricted moduli set; sign detection; sign detection.;

fLanguage

English

Journal_Title

Very Large Scale Integration (VLSI) Systems, IEEE Transactions on

Publisher

ieee

ISSN

1063-8210

Type

jour

DOI

10.1109/TVLSI.2014.2308014

Filename

6763096