Запис Детальніше

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

Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"

Переглянути архів Інформація
 
 
Поле Співвідношення
 
Title Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву
 
Creator Процько, І.
Рикмас, Р.
 
Contributor Національний університет “Львівська політехніка”
ТОВ “Юнісервіс” (Львів)
 
Subject швидке перетворення Фур’є (ШПФ)
циклічна згортка
твірний масив
fast Fourier transform
cyclic convolution
hashing array
004.421.2
517.443
 
Description Розглянуто загальну методику ефективного обчислення ДПФ за допомогою
циклічних згорток для обсягів, що дорівнюють цілому степеню два. Проаналізовано
подальший розвиток алгоритму Вінограда перетворення Фур’є (WFTA). Застосовано
твірний масив для стислого опису блочно-циклічної структури базисної матриці ДПФ.
Визначено загальну блочно-циклічну структуру дискретної базисної матриці та
обчислювальні затрати для ДПФ обсягів N = 2n.
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 blockcyclic
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.
 
Date 2018-05-04T13:01:02Z
2018-05-04T13:01:02Z
2017-03-28
2017-03-28
 
Type Article
 
Identifier Процько І. Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву / І. Процько, Р. Рикмас // Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології. — Львів : Видавництво Львівської політехніки, 2017. — № 864. — С. 291–299.
http://ena.lp.edu.ua:8080/handle/ntb/41030
Protsko I. Rozvytok alhorytmu Vinohrada peretvorennia Furie na bazi tvirnoho masyvu / I. Protsko, R. Rykmas // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Serie: Kompiuterni nauky ta informatsiini tekhnolohii. — Lviv : Vydavnytstvo Lvivskoi politekhniky, 2017. — No 864. — P. 291–299.
 
Language uk
 
Relation Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології, 864, 2017
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.
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 S. M., Discrete Fourier Transforms When the Number of Data Samples is prime., S. M. 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.
 
Rights © Національний університет “Львівська політехніка”, 2017
© Процько І., Рикмас Р., 2017
 
Format 291-299
9
application/pdf
image/png
 
Coverage Львів
 
Publisher Видавництво Львівської політехніки