© The Institution of Electrical Engineers
Consideration is given to the suitability of microprocessor systems for the fast implementation of number theoretic transforms (n.t.t.s). Fast-multiply instructions available on some microprocessors, or the use of external multipliers, relax the basic constraints on the choice of a particular n.t.t. A search was made for suitable moduli which allow fast computation of n.t.t.s using Winograd's algorithm. The search was extended for other moduli which allow increased dynamic range when combined using the Chinese remainder theorem. Finally, a description is given of how modular arithmetic may efficiently be performed using microprocessors
References
-
-
1)
-
R.C. Agarwal ,
S.C. Burrus
.
Number theoretic transforms to implement fast digital convolution.
Proc. IEEE
,
550 -
560
-
2)
-
J.H. McClellan
.
Hardware realisation of a Fermat number transform.
IEEE Trans.
,
216 -
225
-
3)
-
A.C. Davies ,
Y.T. Fung
.
Interfacing a hardware multiplier to a general purpose microprocessor.
Microprocessors
,
425 -
432
-
4)
-
D. Bailey
.
Winograds algorithm applied to number theoretic transforms.
Electron.Lett.
,
548 -
549
-
5)
-
H.F. Silverman
.
Corrections and an addendum to An introduction to the Winograd Fourier transform algorithm (WFTA).
IEEE Trans.
-
6)
-
N. Sridhar Reddy ,
V. Umpathi Reddy
.
Complex convolutions using rectangular transforms.
Electron. Lett.
,
458 -
459
-
7)
-
H.J. Nussbaumer
.
Complex convolutions via Fermat number transforms.
IBM J. Res. & Dev.
,
282 -
284
-
8)
-
C.M. Rader
.
Discrete convolution via Mersenne transforms.
IEEE Trans.
,
1269 -
1273
-
9)
-
R.C Agarwal ,
J.W. Cooley
.
New algorithms for digital convolution.
IEEE Trans.
,
392 -
410
-
10)
-
R.C. Agarwal ,
C.S. Burrus
.
Fast convolution using Fermat number transforms with applications to digital filtering.
IEEE Trans.
,
87 -
99
-
11)
-
C.H. Moore
.
FORTH: A new way to program a minicomputer.
Astron. and Astrophys.
,
497 -
511
-
12)
-
H.F. Silverman
.
An introduction to programming the Winograd Fourier transform algorithm (WFTA).
IEEE Trans.
,
152 -
165
-
13)
-
P.J. Nicholson
.
Algebraic theory of finite Fourier transforms.
J. Comput. and Syst. Sci.
,
524 -
547
-
14)
-
S. Winograd
.
On computing the discrete Fourier transform.
Prod. Nat. Acad. Sci.
,
1005 -
1006
-
15)
-
N. Sridhar Reddy ,
V. Umpathi Reddy
.
Implementation of Winograds algorithm in modular arithmetic for digital convolutions.
Electron. Lett.
,
228 -
229
-
16)
-
M.C. Vanwormhoudt
.
Structural properties of complex residue rings applied to number theoretic Fourier transforms.
IEEE Trans.
,
99 -
104
-
17)
-
P. Melhuish
.
Fermat transform implementation by a minicomputer.
Electron. Lett.
,
109 -
111
http://iet.metastore.ingenta.com/content/journals/10.1049/ij-ecs.1979.0004
Related content
content/journals/10.1049/ij-ecs.1979.0004
pub_keyword,iet_inspecKeyword,pub_concept
6
6