DocumentCode :
923022
Title :
The use of finite fields to compute convolutions
Author :
Reed, Irving S. ; Truong, T.K.
Volume :
21
Issue :
2
fYear :
1975
fDate :
3/1/1975 12:00:00 AM
Firstpage :
208
Lastpage :
213
Abstract :
A transform is defined in the Galois field of 
elements 
, a finite field analogous to the field of complex numbers, when 
is a prime such that (--1) is not a quadratic residue. It is shown that the action of this transform over is equivalent to the discrete Fourier transform of a sequence of complex integers of finite dynamic range. If is a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers.
elements , a finite field analogous to the field of complex numbers, when is a prime such that (--1) is not a quadratic residue. It is shown that the action of this transform over is equivalent to the discrete Fourier transform of a sequence of complex integers of finite dynamic range. If is a Mersenne prime, one can utilize the fast Fourier transform (FFT) algorithm to yield a fast convolution without the usual roundoff problem of complex numbers.Keywords :
Convolution; Galois fields; Number-theoretic transforms; Arithmetic; Discrete Fourier transforms; Discrete transforms; Dynamic range; Fast Fourier transforms; Filtering; Fourier transforms; Galois fields; Helium; Roundoff errors;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.1975.1055352
Filename :
1055352
Link To Document :
