Skip navigation
DSpace logo
  1. Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
  2. Електронний архів Науково-технічної бібліотеки
  3. Вісники та науково-технічні збірники, журнали
  4. Комп'ютерні науки та інформаційні технології
  5. Комп'ютерні науки та інформаційні технології. – 2017. – №864

putin IS MURDERER

Please use this identifier to cite or link to this item: https://oldena.lpnu.ua/handle/ntb/41030
Title: Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву
Authors: Процько, І.
Рикмас, Р.
Affiliation: Національний університет “Львівська політехніка”
ТОВ “Юнісервіс” (Львів)
Bibliographic description (Ukraine): Процько І. Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву / І. Процько, Р. Рикмас // Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології. — Львів : Видавництво Львівської політехніки, 2017. — № 864. — С. 291–299.
Bibliographic description (International): 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.
Is part of: Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології, 864, 2017
Journal/Collection: Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології
Issue: 864
Issue Date: 28-Mar-2017
Publisher: Видавництво Львівської політехніки
Place of the edition/event: Львів
UDC: 004.421.2
517.443
Keywords: швидке перетворення Фур’є (ШПФ)
циклічна згортка
твірний масив
fast Fourier transform
cyclic convolution
hashing array
Number of pages: 9
Page range: 291-299
Start page: 291
End page: 299
Abstract: Розглянуто загальну методику ефективного обчислення ДПФ за допомогою циклічних згорток для обсягів, що дорівнюють цілому степеню два. Проаналізовано подальший розвиток алгоритму Вінограда перетворення Фур’є (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.
URI: https://ena.lpnu.ua/handle/ntb/41030
Copyright owner: © Національний університет “Львівська політехніка”, 2017
© Процько І., Рикмас Р., 2017
References (Ukraine): 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.
References (International): 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.
Content type: Article
Appears in Collections:Комп'ютерні науки та інформаційні технології. – 2017. – №864

Files in This Item:
File Description SizeFormat 
2017n864_Protsko_I-Rozvytok_alhorytmu_Vinohrada_291-299.pdf977.94 kBAdobe PDFView/Open
2017n864_Protsko_I-Rozvytok_alhorytmu_Vinohrada_291-299__COVER.png408.96 kBimage/pngView/Open
Show full item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.