Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures

Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

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.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Residue number systems (RNS) are non-weighted systems that allow to perform addition, subtraction and multiplication operations concurrently and independently on each residue. The triple moduli set {2n−1, 2n, 2n+1} and its respective extensions have gained unprecedent importance in RNS, mainly because of the simplicity of the arithmetic units for the individual channels and also of the converters to and from RNS. However, there is neither a perfect balance between the various elements of this moduli set nor an exact equivalence in the complexity of the individual arithmetic units for each individual residue. Two complementary approaches have been proposed to improve the efficiency of RNS based on this type of moduli sets: enhancing multipliers modulo 2n+1, which perform the most complex arithmetic operation, and overloading the binary channel in order to obtain a more balanced moduli set. Experimental results show that, when applied together, these techniques can improve the efficiency of the multipliers up to 32%.

References

    1. 1)
      • L. Sousa , R. Chaves . A universal architecture for designing efficient modulo 2n+1 multipliers. IEEE Trans. Circuits Syst. I , 1166 - 1178
    2. 2)
      • A.S. Ashur , M.K. Ibrahim , A. Aggoun . Novel RNS structures for the moduli set (2n−1, 2n, 2n+1) and their application to digital filter implementation. Signal Process. , 3 , 331 - 343
    3. 3)
      • E.D.D. Claudio , F. Piazza , G. Orlandi . Fast combinatorial RNS processors for DSP applications. IEEE Trans. Comput. , 5 , 624 - 633
    4. 4)
      • A. Hiasat , A. Sweidan . Residue-to-binary decoder for an enhanced moduli set. IEE Proc., Comput. Digit. Technol , 127 - 130
    5. 5)
      • T. Toivonen , J. Heikkil̈a . Video filtering with Fermat number theoretic transforms using residue number system. IEEE Trans. Circuits Syst. Video Technol. , 1 , 92 - 101
    6. 6)
      • Virtual Silicon Technology, Inc.: UMC high density standard cells library – 0.13 µm CMOS process v2.3 ed December 1999.
    7. 7)
      • S. Nakamura , K.-Y. Chu . A single chip parallel multiplier by MOS technology. IEEE Trans. Comput. , 274 - 282
    8. 8)
      • J.-C. Bajard , L. Imbert . A full RNS implementation of RSA. IEEE Trans. Comput. , 6 , 769 - 774
    9. 9)
      • M. Soderstrand , W. Jenkins , G. Jullien , F. Taylor . (1986) Residue number system arithmetic: modem applications in digital signal processing.
    10. 10)
      • S. Andraos , H. Ahmad . A new efficient memoryless residue to binary converter. IEEE Trans. Circuits and Syst. , 1441 - 1444
    11. 11)
      • S.J. Piestrak . A high-speed realization of a residue to binary number system converter. IEEE Trans. Circuits Syst. , 661 - 663
    12. 12)
      • I. Koren . (1993) Computer arithmetic algorithms.
    13. 13)
      • H. Nozaki , M. Motoyama , A. Shimbo , S.-I. Kawamura , D. Çetin Kaya Koç, Naccache , C. Paar . (2001) Implementation of RSA algorithm based on RNS montgomery multiplication, CHES’ vol. 2162 of Lecture Notes in Computer Science.
    14. 14)
      • R. Chaves , L. Sousa . Faster modulo 2n+1 multipliers without Booth recoding.
    15. 15)
      • Chaves, R., Sousa, L.: `{2', Symp. on Digital System Design: Architectures, Methods and Tools, September 2004, p. 210–217.
    16. 16)
      • R. Conway , J. Nelson . Fast converter for 3 moduli RNS using new property of CRT. IEEE Trans. Comput. , 852 - 859
    17. 17)
      • L. Leibowitz . A simplified binary arithmetic for the Fermat number transform. IEEE Trans. Acoust. Speech Signal Process. , 356 - 359
    18. 18)
      • Bhardwaj, M., Srikanthann, T., Clarke, C.: `A reverse converter for the 4-moduli superset {2', Proc. 14th IEEE Symp. on Computer Arithmetic, April 1999, p. 168–175.
    19. 19)
      • Chaves, R., Sousa, L.: `RDSP: a RISC DSP based on residue number system', Symp. on Digital System Design: Architectures, Methods and Tools, September 2003, p. 128–135.
    20. 20)
      • Lai, X.J., Massey, L.: `A proposal for a new block encryption standard', EUROCRYPT, 1990, p. 389–404.
    21. 21)
      • Zimmermann, R.: `Efficient VLSI implementation of modulo (2', Proc. IEEE Symp. on Computer Arithmetic, April 1999, p. 158–167.
    22. 22)
      • E.D. Claudio , F. Piazza , G. Orlandi . Fast combinatorial RNS processors for DSP applications. IEEE Trans. Comput. , 624 - 633
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20060059
Loading

Related content

content/journals/10.1049/iet-cdt_20060059
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address