The general technique of efficient computation DFT using of cyclic convolutions for sizes of integer power of two is considered. Further development of Winograd Fourier transform algorithm (WFTA) is analyzed. The hashing array for the compacting definition of the block-cyclic structure the basis matrix of DFT is proposed. The general block-cyclic structure of discrete basis matrix for the computation of DFT of sizes N=2n is determined.
1. Duhamel P., Fast Fourier Transform: A tutorial Review and a State of the Art / P. Duhamel, M. Vitterli // Signal Processing. –1990. – Vol.19, – p. 259–299.
2. Chu Eleanor, Inside the FFT black box. Serial and Parallel Fast Fourier Transform Algorithms / Eleanor Chu, Alan George // CRC Press LLC, Boca Raton, 2000.
3. Tolimiery R. Algorithms for Discrete Fourier Transform and Convolution /R. Tolimiery, M. An, C. Lu // New York, Springer–Verlag, 1997 (s.ed.).
4. Prots’ko I., Becoming of Discrete Harmonic Transform Using Cyclic Convolutions / Ihor Prots’ko, Roman Rykmas // American Journal of Circuits, Systems and Signal Processing. – 2015. – August 2006. – Vol. 1, No. 3. – P. 114–119.
5. Chen H.-C., Distributed arithmetic realization of cyclic convolution and its DFT application. / H.-C. Chen, J.-I. Guo, C.-W. Jen and T.-S. Chang // IEE Proc.-Circuits Devices Syst. – December 2005. – Vol. 152, No.
6. – p. 615–629. 6. Meher P. K., Efficient Systolic Implementation of DFT using a Low-Complexity Convolution-like Formulation. / P. K. Meher // IEEE Transactions on Circuits & Systems-II: Express Briefs. – August 2006. – Vol. 53, No.8. – p. 702–706.
7. Cheng C., Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform. / Chao Cheng, Keshab K. Parhi // IEEE Transactions on circuits and systems - I: regular papers. – April 2007. – Vol. 54, No. 4, – p. 791–806.
8. Rader С. М., Discrete Fourier Transforms When the Number of Data Samples is prime. / С. М. Rader // Proc. IEEE, – 1968. –56, p. 1107–1108.
9. Winograd S., On computing the discrete Fourier transform. / S. Winograd // in Proc. Nat. Acad. Sci. USA. – April 1976, Mathematics. – Vol. 73, No. 4, – p. 1005–1006.
10. Lu C., Extension of Winograd Multiplicative Algorithm to Transform Size N = p2q, p2qr and Their Implementation. / C. Lu, and R. Tolimieri // Proc. ICASSP 89. – Scotland, May 22-26, 1989.
11. Silverman H. F., An introduction to Programming the Winograd Fourier Transform algorithm (WFTA) / H. F. Silverman // IEEE Trans ASSSP. – 1977. – Vol. ASSSP- 25, No.2, – p.152–165.
12. Patterson R. W., Fixed Point Error Analysis of Winograd Fourier Transform Algorithms. / R. W. Patterson, J. H. McClellan // IEEE Trans. ASSP. –October 1978. – p.447–455.
13. Lavoie P., A high-speed CMOS implementation of the Winograd Fourier transform algorithm. / P. Lavoie // IEEE Trans. Signal Process. – Aug. 1996. – Vol. 44, No. 8. –p. 2121–2126.
14. Blahut R. E., Fast algorithms for signal processing. / R. E. Blahut // Cambridge University Press, 2010. – 469 p.
15. Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms / Henri J. Nussbaumer // Springer-Verlag, Berlin, Heidelberg, 1982.
16. Zohar S., Faster Fourier Transformation: The Algorithm of S. Winograd. / Shalhav Zohar // Jet Propulsion Laboratory JPL Publication 78–104, under NASA Contract No. NAS7-100, – February 15, 1979. – p. 1–93.
17. Winograd S., On computing the discrete Fourier transforms. / S. Winograd // Mathematics of Computation. – 1978. – Vol. 32. – p. 175–199.
18. Zohar S., Winograd’s discrete Fourier transform algorithm. /Two-dimensional Digital Signal Processing. Transforms and Median Filters. Edited by T. S. Huang. Springer-Verlag, Berlin, Heidelberg, – New York, 1981. – 222 p.
19. Prots’ko I., The generalized technique of computation the discrete harmonic transforms / I. Prots’ko // Proceedings of the IVth International Conference (MEMSTECH’2008), Polyana, 21–24 may, 2008. – p. 101–102.
20. Thomas W. Judson, Abstract Algebra Theory and Applications. / W. Judson Thomas // Stephen F. Austin State University, February 14, 2009. – 428 p.
21. Duhamel P., Implementation of “Split-Radix” FFT Algorithms for Complex, Real, and Real-Symmetric Data. / P. Duhamel // IEEE Trans. on Acoustic, Speech, and Signal Processing, – April 1986, – Vol. ASSP-34, No. 2, – p. 285–295.