The Discrete Fourier Transform Over Finite Rings with Application to Fast Convolution
- 1 July 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (7), 586-593
- https://doi.org/10.1109/tc.1978.1675158
Abstract
Necessary and sufficient conditions for a direct sum of local rings to support a generalized discrete Fourier transform are derived. In particular, these conditions can be applied to any finite ring. The function O(N) defined by Agarwal and Burrus for transforms over ZN is extended to any finite ring R as O(R) and it is shown that R supports a length m discrete Fourier transform if and only if m is a divisor of O(R) This result is applied to the homomorphic images of rings-of algebraic integers.Keywords
This publication has 11 references indexed in Scilit:
- Convolution using a conjugate symmetry property for the generalized discrete Fourier transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978
- Fast complex convolution in finite ringsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1976
- Convolutions over residue classes of quadratic integersIEEE Transactions on Information Theory, 1976
- Implementation of number-theoretic transformsElectronics Letters, 1976
- The fast Fourier transform its role as an algebraic algorithmPublished by Association for Computing Machinery (ACM) ,1976
- Complex integer convolutions over a direct sum of Galois fieldsIEEE Transactions on Information Theory, 1975
- Orthogonal Transforms for Digital Signal ProcessingPublished by Springer Nature ,1975
- 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
- The Fast Fourier Transform in a Finite FieldMathematics of Computation, 1971