Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву

І. О. Процько; Р. В. Рикмас

Розглянуто загальну методику ефективного обчислення ДПФ за допомогою циклічних згорток для обсягів, що дорівнюють цілому степеню два. Проаналізовано подальший розвиток алгоритму Вінограда перетворення Фур’є (WFTA). Застосовано твірний масив для стислого опису блочно-циклічної структури базисної матриці ДПФ. Визначено загальну блочно-циклічну структуру дискретної базисної матриці та обчислювальні затрати для ДПФ обсягів N = 2n.

швидке перетворення Фур’є

циклічна згортка

твірний масив

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.