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

Simple item page
dc.citation.epage299
dc.citation.issue864
dc.citation.journalTitleВісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології
dc.citation.spage291
dc.contributor.affiliationНаціональний університет “Львівська політехніка”
dc.contributor.affiliationТОВ “Юнісервіс” (Львів)
dc.contributor.authorПроцько, І.
dc.contributor.authorРикмас, Р.
dc.coverage.placenameЛьвів
dc.date.accessioned2018-05-04T13:01:02Z
dc.date.available2018-05-04T13:01:02Z
dc.date.created2017-03-28
dc.date.issued2017-03-28
dc.description.abstractРозглянуто загальну методику ефективного обчислення ДПФ за допомогою циклічних згорток для обсягів, що дорівнюють цілому степеню два. Проаналізовано подальший розвиток алгоритму Вінограда перетворення Фур’є (WFTA). Застосовано твірний масив для стислого опису блочно-циклічної структури базисної матриці ДПФ. Визначено загальну блочно-циклічну структуру дискретної базисної матриці та обчислювальні затрати для ДПФ обсягів N = 2n.
dc.description.abstractThe 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.
dc.format.extent291-299
dc.format.pages9
dc.identifier.citationПроцько І. Розвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву / І. Процько, Р. Рикмас // Вісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології. — Львів : Видавництво Львівської політехніки, 2017. — № 864. — С. 291–299.
dc.identifier.citationenProtsko 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.
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/41030
dc.language.isouk
dc.publisherВидавництво Львівської політехніки
dc.relation.ispartofВісник Національного університету «Львівська політехніка». Серія: Комп’ютерні науки та інформаційні технології, 864, 2017
dc.relation.references1. 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.
dc.relation.references2. Chu Eleanor, Inside the FFT black box. Serial and Parallel Fast Fourier Transform Algorithms / Eleanor Chu, Alan George // CRC Press LLC, Boca Raton, 2000.
dc.relation.references3. Tolimiery R. Algorithms for Discrete Fourier Transform and Convolution / R. Tolimiery, M. An, C. Lu // New York, Springer–Verlag, 1997 (s.ed.).
dc.relation.references4. 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.
dc.relation.references5. 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.
dc.relation.references6. 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.
dc.relation.references7. 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.
dc.relation.references8. Rader С. М., Discrete Fourier Transforms When the Number of Data Samples is prime. / С. М. Rader // Proc. IEEE, – 1968. – 56, p. 1107–1108.
dc.relation.references9. 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.
dc.relation.references10. 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.
dc.relation.references11. 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.
dc.relation.references12. 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.
dc.relation.references13. 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.
dc.relation.references14. Blahut R. E., Fast algorithms for signal processing. / R. E. Blahut // Cambridge University Press, 2010. – 469 p.
dc.relation.references15. Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms / Henri J. Nussbaumer // Springer-Verlag, Berlin, Heidelberg, 1982.
dc.relation.references16. 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.
dc.relation.references17. Winograd S., On computing the discrete Fourier transforms. / S. Winograd // Mathematics of Computation. – 1978. – Vol. 32. – p. 175–199.
dc.relation.references18. 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.
dc.relation.references19. 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.
dc.relation.references20. Thomas W. Judson, Abstract Algebra Theory and Applications. / W. Judson Thomas // Stephen F. Austin State University, February 14, 2009. – 428 p.
dc.relation.references21. 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.
dc.relation.referencesen1. 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.
dc.relation.referencesen2. Chu Eleanor, Inside the FFT black box. Serial and Parallel Fast Fourier Transform Algorithms, Eleanor Chu, Alan George, CRC Press LLC, Boca Raton, 2000.
dc.relation.referencesen3. Tolimiery R. Algorithms for Discrete Fourier Transform and Convolution, R. Tolimiery, M. An, C. Lu, New York, Springer–Verlag, 1997 (s.ed.).
dc.relation.referencesen4. 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.
dc.relation.referencesen5. 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.
dc.relation.referencesen6. 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.
dc.relation.referencesen7. 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.
dc.relation.referencesen8. Rader S. M., Discrete Fourier Transforms When the Number of Data Samples is prime., S. M. Rader, Proc. IEEE, 1968, 56, p. 1107–1108.
dc.relation.referencesen9. 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.
dc.relation.referencesen10. 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.
dc.relation.referencesen11. 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.
dc.relation.referencesen12. 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.
dc.relation.referencesen13. 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.
dc.relation.referencesen14. Blahut R. E., Fast algorithms for signal processing., R. E. Blahut, Cambridge University Press, 2010, 469 p.
dc.relation.referencesen15. Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms, Henri J. Nussbaumer, Springer-Verlag, Berlin, Heidelberg, 1982.
dc.relation.referencesen16. 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.
dc.relation.referencesen17. Winograd S., On computing the discrete Fourier transforms., S. Winograd, Mathematics of Computation, 1978, Vol. 32, p. 175–199.
dc.relation.referencesen18. 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.
dc.relation.referencesen19. 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.
dc.relation.referencesen20. Thomas W. Judson, Abstract Algebra Theory and Applications., W. Judson Thomas, Stephen F. Austin State University, February 14, 2009, 428 p.
dc.relation.referencesen21. 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.
dc.rights.holder© Національний університет “Львівська політехніка”, 2017
dc.rights.holder© Процько І., Рикмас Р., 2017
dc.subjectшвидке перетворення Фур’є (ШПФ)
dc.subjectциклічна згортка
dc.subjectтвірний масив
dc.subjectfast Fourier transform
dc.subjectcyclic convolution
dc.subjecthashing array
dc.subject.udc004.421.2
dc.subject.udc517.443
dc.titleРозвиток алгоритму Вінограда перетворення Фур’є на базі твірного масиву
dc.typeArticle

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
2017n864_Protsko_I-Rozvytok_alhorytmu_Vinohrada_291-299.pdf
Size:
977.94 KB
Format:
Adobe Portable Document Format
Download
Thumbnail Image
Name:
2017n864_Protsko_I-Rozvytok_alhorytmu_Vinohrada_291-299__COVER.png
Size:
408.96 KB
Format:
Portable Network Graphics
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.96 KB
Format:
Plain Text
Description:
Download

Collections

Комп'ютерні науки та інформаційні технології. – 2017. – №864