Efficient new approach for modulo 2n−1 addition in RNS
Efficient new approach for modulo 2n−1 addition in RNS
- Author(s): R.A. Patel ; M. Benaissa ; S. Boussakta
- DOI: 10.1049/ip-cdt:20050166
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): R.A. Patel 1 ; M. Benaissa 1 ; S. Boussakta 2
-
-
View affiliations
-
Affiliations:
1: Department of Electronic & Electrical Engineering, University of Sheffield, Sheffield, UK
2: Department of Electronic & Electrical Engineering, University of Leeds, Leeds, UK
-
Affiliations:
1: Department of Electronic & Electrical Engineering, University of Sheffield, Sheffield, UK
- Source:
Volume 153, Issue 6,
November 2006,
p.
399 – 405
DOI: 10.1049/ip-cdt:20050166 , Print ISSN 1350-2387, Online ISSN 1359-7027
- « Previous Article
- Table of contents
- Next Article »
A new modulo 2n−1 addition algorithm is presented, which is applicable in the residue number system. In contrast to previous work, the input carry in the first stage of the addition is set to one. The associated output carry is then used to conditionally modify the sum to produce the correct modulo 2n−1 result. Moreover, unlike recent adders in the literature, the result never exceeds the dynamic range of the modulus. Actual VLSI implementations using 130 nm standard-cell technology show that the corresponding architectures provide improved trade-offs in the power–delay–area space when compared against existing designs.
Inspec keywords: residue number systems; VLSI; number theory
Other keywords:
Subjects: Digital circuit design, modelling and testing; Combinatorial mathematics; Digital arithmetic methods; Semiconductor integrated circuits; Combinatorial mathematics
References
-
-
1)
- C. Efstathiou , D. Nikolos , J. Kalamatianos . Area-time efficient modulo 2n−1 adder design. IEEE Trans. Circuits Syst.-II , 7 , 463 - 467
-
2)
- M.-H. Sheu , S.-H. Lin , C. Chen , S.-W. Yang . An efficient VLSI design for a residue to binary converter for general balance moduli (2n−3, 2n+1, 2n−1, 2n+3). IEEE Trans. Circuits Syst. II , 3 , 152 - 155
-
3)
- C. Efstathiou , H.T. Vergos , D. Nikolos . Modulo 2n±1 adder design using select-prefix blocks. IEEE Trans. Comput. , 11 , 1399 - 1406
-
4)
- Mahesh, M.N., Mehendale, M.: `Improving performance of high precision signal processing algorithms on programmable DSPs', Proc. IEEE Int. Symp. on Circuits and Systems (ISCAS 1999), May–June 1999, Orlando, FL, USA, 3, p. 488–491.
-
5)
- J. Ramírez , A. García , U. Meyer-Bäse , F. Taylor , A.J. Lloris . Implementation of RNS-based distributed arithmetic discrete wavelet transform architectures using field-programmable logic. J. VLSI Signal Process. , 1 , 171 - 190
-
6)
- D. Nikolos , M. Paschalis , G. Philokyprou . Efficient design of totally self-checking checkers for all low cost arithmetic codes. IEEE Trans. Comput. , 807 - 814
-
7)
- A.A. Hiasat . Efficient residue to binary converter. IEE Proc. Comput. Digital Tech. , 1 , 11 - 16
-
8)
- Dimitrakopoulos, G., Vergos, H.T., Nikolos, D., Efstathiou, C.: `A systematic methodology for designing area-time efficient parallel-prefix modulo 2', Proc. IEEE Int. Symp. on Circuits and Systems (ISCAS 2003), May 2003, Bangkok, Thailand, 5, p. 225–228.
-
9)
- N.S. Szabo , R.I. Tanaka . (1967) Residue arithmetic and its applications to computer technology.
-
10)
- Chaves, R., Sousa, L.: `RDSP: a RISC DSP based on residue number system', Proc. Euromicro Symp. on Digital System Design, September 2003, p. 128–135, Turkey.
-
11)
- B. Cao , C.H. Chang , T. Srikanthan . An efficient reverse converter for the 4-moduli set {2n−1, 2n, 2n+1, 22n+1} based on the New Chinese Remainder Theorem. IEEE Trans. Circuits Syst. I , 10 , 1296 - 1303
-
12)
- Knowles, S.: `A family of adders', Proc. 15th IEEE Symp. on Computer Arithmetic (ARITH-15 2001), June 2001, CO, USA, Vail, p. 277–281.
-
13)
- A.A. Hiasat . VLSI implementation of new arithmetic residue to binary decoders. IEEE Trans. VLSI Syst. , 1 , 153 - 158
-
14)
- P.M. Kogge , H.S. Stone . A parallel algorithm for the efficient solution of a general class of recurrence equations. IEEE Trans. Comput. , 786 - 792
-
15)
- T. Stouraitis , V. Paliouras . Considering the alternatives in low-power design. IEEE Circuits Devices Mag. , 4 , 22 - 29
-
16)
- C. Efstathiou , H.T. Vergos , D. Nikolos . Modified Booth modulo 2n−1 multipliers. IEEE Trans. Comput. , 370 - 374
-
17)
- R. Conway , J. Nelson . Improved RNS FIR filter architectures. IEEE Trans. Circuits Syst. II , 1 , 26 - 28
-
18)
- Cardarilli, G.C., Del Re, A., Nannarelli, A., Re, M.: `Low-power implementation of polyphase filters in quadratic residue number system', Proc. IEEE Int. Symp. on Circuits and Systems (ISCAS 2004), May 2004, Vavcouver, BC, Canada, 2, p. 725–728.
-
19)
- Wei, W., Swamy, M.N.S., Ahmad, M.O.: `RNS application for digital image processing', 4thIEEE Int. Workshop System on Chip for Real Time Applications, July 2004, Banff, Alta, Canada, p. 77–80.
-
20)
- Dimitrakopoulos, G., Vergos, H.T., Nikolos, D., Efstathiou, C.: `A family of parallel-prefix modulo 2', Proc. IEEE Int. Conf. on Application-Specific Systems, Architectures, Processors (ASAP 2003), June 2003, The Hague, Netherlands, p. 315–325.
-
21)
- N. Burgess . The flagged prefix adder and its applications in integer arithmetic. J. VLSI Signal Process. , 3 , 263 - 271
-
22)
- R.E. Ladner , M.J. Fisher . Parallel prefix computation. J. ACM , 4 , 831 - 838
-
23)
- M.A. Soderstrand , W.K. Jenkins , G.A. Jullien , F.J. Taylor . (1986) Residue number system arithmetic: modern applications in digital signal processing.
-
24)
- R. Burch . A Monte Carlo approach for power estimation. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. , 1 , 63 - 71
-
25)
- M. Bayoumi , G. Jullien , W.C. Miller . A VLSI implementation of residue adders. IEEE Trans. Circuits Syst. , 3 , 284 - 288
-
26)
- S.J. Piestrak . Design of residue generators and multioperand modular adders using carry-save adders. IEEE Trans. Comput. , 68 - 77
-
27)
- B. Parhami . (2000) Computer arithmetic: algorithms and hardware designs.
-
28)
- B. Cao , T. Srikanthan , C.H. Chang . Efficient reverse converters for four-moduli sets {2n−1, 2n, 2n+1, 2n+1−1} and {2n−1, 2n, 2n+1, 2n−1−1}. IEE Proc. Comput. Digital Tech. , 5 , 687 - 696
-
29)
- E.D.D. Claudio , F. Piazza , G. Orlandi . Fast combinatorial RNS processors for DSP applications. IEEE Trans. Comput. , 5 , 624 - 633
-
30)
- L. Kalampoukas , D. Nikolos , C. Efstathiou , H. Vergos , J. Kalamatianos . High-speed parallel-prefix modulo 2n−1 adders. IEEE Trans Comput. , 673 - 680
-
31)
- Zimmermann, R.: `Efficient VLSI implementation of modulo (2', Proc. 14th Symp. on Computer Arithmetic (ARITH-14 1999), April 1999, Adelaide, SA, Australia, p. 158–167.
-
1)