Computational complexity of Fourier transforms over finite fields
HTML articles powered by AMS MathViewer
- by F. P. Preparata and D. V. Sarwate PDF
- Math. Comp. 31 (1977), 740-751 Request permission
Abstract:
In this paper we describe a method for computing the Discrete Fourier Transform (DFT) of a sequence of n elements over a finite field ${\text {GF}}({p^m})$ with a number of bit operations $O(nm \log (nm) \cdot P(q))$ where $P(q)$ is the number of bit operations required to multiply two q-bit integers and $q \cong 2 {\log _2}n + 4 {\log _2}m + 4 {\log _2}p$. This method is uniformly applicable to all instances and its order of complexity is not inferior to that of methods whose success depends upon the existence of certain primes. Our algorithm is a combination of known and novel techniques. In particular, the finite-field DFT is at first converted into a finite field convolution; the latter is then implemented as a two-dimensional Fourier transform over the complex field. The key feature of the method is the fusion of these two basic operations into a single integrated procedure centered on the Fast Fourier Transform algorithm.References
- Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597 F. J. MacWILLIAMS & N. J. A. SLOANE, Theory of Error-Correcting Codes, American Elsevier, New York. (To appear.)
- J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 301966, DOI 10.1090/S0025-5718-1971-0301966-0
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- Allan Borodin and Ian Munro, The computational complexity of algebraic and numeric problems, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. MR 0468309
- Charles M. Rader, Discrete convolutions via Mersenne transforms, IEEE Trans. Comput. C-21 (1972), 1269–1273. MR 438672, DOI 10.1109/t-c.1972.223497
- Ramesh C. Agarwal and C. Sidney Burrus, Number theoretic transforms to implement fast digital convolution, Proc. IEEE 63 (1975), no. 4, 550–560. MR 0451632
- Irving S. Reed and T. K. Truong, The use of finite fields to compute convolutions, IEEE Trans. Inform. Theory IT-21 (1975), 208–213. MR 406677, DOI 10.1109/tit.1975.1055352
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355 L. I. BLUESTEIN, "A linear filtering approach to the computation of discrete Fourier transform," IEEE Trans. Audio & Electroacoustics, v. AU-18, 1970, pp. 451-455. C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE (Letters), v. 56, No. 6, 1968, pp. 1107-1108.
- James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1 S. W. GOLOMB, "Properties of the sequence $3 \cdot {2^n} + 1,$" Math. Comp., v. 30, 1976, pp. 657-663.
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Ramesh C. Agarwal and Charles S. Burrus, Fast one-dimensional digital convolution by multidimensional techniques, IEEE Trans. Acoust. Speech Signal Process. ASSP- (1974), no. 1, 1–10. MR 401340
Additional Information
- © Copyright 1977 American Mathematical Society
- Journal: Math. Comp. 31 (1977), 740-751
- MSC: Primary 68A20; Secondary 65DXX
- DOI: https://doi.org/10.1090/S0025-5718-1977-0436662-8
- MathSciNet review: 0436662