Abstract
An algebraic method for synthesizing fast algorithms of the discrete cosine transform (DCT) of arbitrary size is proposed. The method is based on the polynomial algebra \(\mathbb{F}{{[x]} \mathord{\left/ {\vphantom {{[x]} {p(x)}}} \right. \kern-\nulldelimiterspace} {p(x)}}\) associated with the DCT. The fast DCT algorithm comes as a result of the step-by-step decomposition of this algebra. In turn, the decomposition requires step-by-step factorization of the polynomial p(x). This problem is solved using Galois’s theory, which allows finding all the subfields of the splitting field of the polynomial p(x) where p(x) can be factorized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ifeachor, E. and Jervis, B., Digital Signal Processing. A Practical Approach, Pearson, 2002.
Britanak, V., Yip, P., and Rao, K., Discrete Cosine and Sine Transforms: General Properties, Fast Algorithms and Integer Approximations, London: Academic, 2007.
Miano, J., Compressed Image File Formats, Reading, MA: Addison Wesley, 1999.
Püschel, M., Moura, J.M.F., Johnson, J., et al., SPIRAL: Code Generation for DSP Transforms, Proc. IEEE, Special Issue: Program Generation, Optimization, and Adaptation: 2005, vol. 93, no. 2, pp. 232–275
Bartholoma, R., Greiner, T., Kesel, F., and Rosenstiel, W., A Systematic Approach for Synthesizing VLSI Architecture of Lifting-Based Filter Bank and Transforms, IEEE Trans. Circuits Syst. I: Regular Papers, 2008, vol. 55, pp. 1939–1952.
Püschel, M. and Moura, J.M.F., The Algebraic Approach to the Discrete Cosine and Sine Transform, SIAM J. Comp., 2003, vol. 32, pp. 1280–1316.
Vairadyan, A.S., Pchelintsev, I.P., and Chelyshev, M.M., Algorithms for Computation of Digital Convolutions, Zarubezh. Radioelektron., 1982, no. 3, pp. 3–34.
Labunets, V.G., Algebraicheskaya teoriya signalov i sistem: tsifrovaya obrabotka signalov (Algebraic Theory of Signals and Systems: Digital Signal Processing), Krasnoyarsk: Krasnoyarsk. Univ., 1984.
Krot, A.M., Diskretnye modeli dinamicheskikh sistem na osnove polinomial’noi algebry (Polynomial Algebra-Based Discrete Models of Dynamical Systems), Minsk: Nauka Tekhnika, 1990.
Püschel, M. and Moura, J.M.F., Algebraic Signal Processing Theory: Coole-Tukey Type Algorithms for DCTs and DSTs, IEEE Trans. Signal Proc., 2008, vol. 54, no. 4, pp. 1502–1521.
van der Waerden, B.L., Algebra, London: Springer-Verlag, 2003.
Vashkevich, M.I. and Petrovsky, A.A., Use of Polynomial Algebras and Galois Theory for Synthesis of Fast Algorithms of Discrete Cosine Transformations, Tsifrovaya Obrabotka Signalov, 2011, no. 3, pp. 2–10.
Petrovsky, Al.A., Stankevich, A.V., and Petrovsky, A.A., Bystroe proektirovanie sistem mul’timedia ot prototipa (Fast Design of Multimedia Systems from Prototype), Minsk: Bestprint, 2011.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © M.I. Vashkevich, A.A. Petrovsky, 2012, published in Avtomatika i Vychislitel’naya Tekhnika, 2012, No. 5, pp. 36–45.
About this article
Cite this article
Vashkevich, M.I., Petrovsky, A.A. An algebraic method for synthesizing fast algorithms of discrete cosine transform of arbitrary size. Aut. Control Comp. Sci. 46, 207–213 (2012). https://doi.org/10.3103/S0146411612050082
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S0146411612050082