УДК 681.391
І.О. ПРОЦЬКО,
Національний університет «Львівська політехніка», Львів, Україна,
ihor.o.protsko@lpnu.ua
М.В. МІЩУК,
Національний університет «Львівська політехніка», Львів, Україна,
myroslav.mishchuk.knm.2019@lpnu.ua
БЛОЧНО-ЦИКЛІЧНА СТРУКТУРИЗАЦІЯ БАЗИСУ ПЕРЕТВОРЕННЯ
КЛАСУ ФУР’Є НА ОСНОВІ ЦИКЛІЧНОЇ ПІДСТАНОВКИ
Анотація. Розглянуто використання підстановки як примітивного елемента для форму-вання
циклічної базисної матриці перетворення класу Фур’є. Застосовано циклічну підстановку
для блочно-циклічної структуризації гармонічного базису, що надає змогу синтезувати
алгоритми швидких дискретних перетворень класу Фур’є довільних обсягів на основі циклічних згорток.
Показано, що внаслідок зміни порядку циклів та їхніх пер-ших елементів у циклічних підстановках зменшується кількість
обчислень циклічних згорток у швидких алгоритмах дискретних перетворень класу Фур’є.
Ключові слова: циклічна підстановка, дискретне косинусне перетворення, синтез алго-ритму, блочно-циклічна структура базису, циклічні згортки.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: Методи дослідження та розв’язання. Київ: Наук. думка, 2009. 266 с.
- Stoyan Yu.G., Grebennik I.V. Description and generation of combinatorial sets having special characteristics. International Journal of Biomedical Soft Computing and Human Sciences, Special volume “Bilevel Programming, Optimization Methods, and Applications to Economics”. 2013. Vol. 18, N 1. P. 83–88.
- Bona M. Combinatorics of permutations. Boca Raton; London; New York: Chapman & Hall/CRC, 2004. 337 p. https://doi.org/10.1201/b18255.
- Brualdi R.A. Introductory combinatorics. Upper Saddle River, NJ: Pearson Prentice Hall, 2010. 605 p.
- Rader C.M. Discrete Fourier transform when the number of data samples is prime. Proc. IEEE. 1968. Vol. 56. P. 1107–1108.
- Blahut R.E. Fast algorithms for signal processing. Cambridge: Cambridge University, 2010. 466 p.
- Teixeira M., RodrЗguez Y.I. Parallel cyclic convolution based on recursive formulations of block pseudocirculant matrices. IEEE Trans. Signal Processing. 2008. Vol. 56, N 7. P. 27–55.
- Терещенко А.Н. Оптимизация метода Питасси вычисления свертки. Исскуственный интеллект. 2009. № 1. C. 204–212.
- Maher J., Meher P.K. Scalable approximate DCT architectures for efficient HEVC-compliant video coding. IEEE Trans. Circuits Syst. Video Technol. 2017. Vol. 27, N 8. P. 1815–1825.
- Cotorobai L.-T., Chiper D.F. A new VLSI algorithm for type IV DCT for an efficient implementation of obfuscation technique. Proc. 43rd International Conference on Telecommunications and Signal Processing (TSP) (7–9 July 2020, Milan, Italy). Milan, 2020. https://doi.org/10.1109/TSP49548. 2020.9163537.
- Chan Y.-H., Siu W.-C. Generalized approach for the realization of discrete cosine transform using cyclic convolutions. Proc. IEEE Int. Conference Acoust., Speech, Signal Process.: Digit. Speech Processing (27–30 April 1993, Minneapolis, USA). Minneapolis, 1993. Vol. III. P. 277–280. https://doi.org/10.1109/ICASSP.1993.319489.
- Meher P.K., Swamy M.N.S., New systolic algorithm and array architecture for prime-length discrete sine transform. IEEE Transactions on Circuits and Systems II: Express Briefs. 2007. Vol. 54, Iss. 3. P. 262–266. https://doi.org/10.1109/TCSII.2006.889453.
- Prots’ko I. Generalized approach for synthesis and computation DST using cyclic convolutions. Proc. VIII International Conference MEMSTECH’2012 (18–21 April 2012, Lviv, Poljana). Lviv, 2012. P. 66–67.
- Пат. 96540 Україна, G06F 17/16 (2006.01), H03M 7/30 (2006.01). Процько І.О. Спосіб приведення дискретних гармонічних складових цифрових сигналів до циклічних згорток. Опубл. 10.11.2011, Бюл. № 21.
- Knuth D. The art of computer programming. Vol. 4. Fascicle 2: Generating all tuples and permutations. Boston: Addison-Wesley, 2005. 144 p.
- Kreher D.L., Stinson D.R. Combinatorial algorithms: Generation, enumeration and search. Boca Raton, FL: CRC Press, 1999. 329 p.
- Permutation cycle. URL: https://mathworld.wolfram.com/PermutationCycle.html.
- Процько І.О. Особливості обчислення твірних масивів для синтезу швидких алгоритмів ДКП I–IV. Радіоелектроніка, інформатика, управління. 2020. № 2. C. 149–157. https://doi.org/10.15588/1607 -3274-2020-2-15.
- Гнатив Л.А. Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео. Кибернетика и системный анализ. 2016. Т. 52, № 5. С. 161–176.
- Процько І.О., Кузьмінський Р.Д., Теслюк В.М. Ефективне обчислення цілочисельного ДКП-ІІ для стиснення зображень. Радіоелектроніка, інформатика, управління. 2019. № 2. C. 151–157. https://doi.org/10.15588/1607-3274-2019-2-16.
- Prots’ko I., Rykmas R. The runtime benchmarking of DCT-II based on cyclic convolutions. International Journal of Condition Monitoring and Diagnostic Engineering Management. 2018. Vol. 21, N 2. P. 11–16.
