UDC 681.391
BLOCK-CYCLIC STRUCTURING OF THE BASIS OF FOURIER CLASS
TRANSFORMS BASED ON CYCLIC SUBSTITUTION
Abstract. A cyclic substitution is used for block-cyclic structuring of the harmonic basis, which allows synthesizing the algorithms
for fast discrete transforms of Fourier class of arbitrary size based on cyclic convolutions. The peculiarities of the form of recording
of cyclic substitution for formation of block-cyclic structure of the basis are investigated. A special form of cyclic substitution notation
is shown to reduce the amount of computation of cyclic convolutions in fast algorithms of discrete Fourier transforms.
Keywords: cyclic substitution, discrete cosine transform, synthesis of algorithm, block-cyclic structure, cyclic convolutions.
FULL TEXT
REFERENCES
- Semenova N.V., Kolechkina L.M. Vector problems of discrete optimization on combinatorial sets: Research methods and solutions [in Ukrainian]. Kyiv: Nauk. Dumka, 2009. 266 p.
- 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.
- Tereshchenko A.N. Optimization of the Pitassi method for calculating the convolution. Isskustvennyy intellekt. 2009. N 1. P. 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.
- Pat. 96540 Ukraine, G06F 17/16 (2006.01), H03M 7/30 (2006.01). Protsko I.O. Method of converting discrete harmonic components of digital signals to cyclic convolutions. Publ. 10.11.2011, Bull. N 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.
- Protsko I.O. Features of calculation of generating arrays for synthesis of fast algorithms of DKP I – IV. Radioelektronika, informatyka, upravlinnya. 2020. N 2. P. 149–157. https://doi.org/10.15588/1607 -3274-2020-2-15.
- Hnativ L.A. Integer cosine transforms for highly efficient image and video encoding. Kibernetika i sistemnyj analiz. 2016. Vol. 52, N 5. P. 161–176.
- Protsko I.O., Kuzminsky R.D., Teslyuk V.M. Effective calculation of integer DCP-II for image compression. Radioelektronika, informatyka, upravlinnya. 2019. N 2. P. 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.
