The VLSI design of a single chip for the multiplication of integers modulo a Fermat number
- 1 December 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Acoustics, Speech, and Signal Processing
- Vol. 33 (6) , 1599-1602
- https://doi.org/10.1109/tassp.1985.1164761
Abstract
Multiplication is central in the implementation of Fermat number transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier is regular, simple, expandable, and therefore, suitable for VLSI implementation.Keywords
This publication has 4 references indexed in Scilit:
- The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)IEEE Transactions on Information Theory, 1978
- A simplified binary arithmetic for the Fermat number transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1976
- Fast Convolution using fermat number transforms with applications to digital filteringIEEE Transactions on Acoustics, Speech, and Signal Processing, 1974
- Discrete Convolutions via Mersenne TransformsIEEE Transactions on Computers, 1972