Small-size algorithms for type-IV discrete cosine transform with reduced multiplicative complexity
DOI:
https://doi.org/10.3103/S0735272720090022Keywords:
digital signal processing, type-IV discrete cosine transform, fast algorithmAbstract
Discrete cosine transforms are widely used in smart radioelectronic systems for processing and analysis of incoming information. The popularity of using these transform is explained by the presence of fast algorithms that minimize the computational and hardware complexity of their implementation. Type-IV discrete cosine transform occupies a special place in the list of the specified transformations. This article proposes several algorithmic solutions for implementing the type-IV discrete cosine transform. The effectiveness of the proposed solutions is explained by the possibility of factorization of the DCT-IV matrix, which leads to a decrease in computational and implementation complexity. A set of completely parallel type-IV DCT algorithms for small lengths of signal sequences (N = 2, 3, 4, 5, 6, 7, 8, 9) is presented.References
N. Ahmed, T. Natarajan, K. R. Rao, “Discrete cosine transform,” IEEE Trans. Comput., vol. C–23, no. 1, pp. 90–93, 1974, doi: https://doi.org/10.1109/T-C.1974.223784.
N. Ahmed, K. R. Rao, Orthogonal Transforms for Digital Signal Processing. Berlin, Heidelberg: Springer Berlin Heidelberg, 1975, doi: https://doi.org/10.1007/978-3-642-45450-9.
K. R. Rao, P. Yip, Discrete Cosine Transform. Elsevier, 1990, doi: https://doi.org/10.1016/C2009-0-22279-3.
V. Britanak, P. C. Yip, K. R. Rao, Discrete Cosine and Sine Transforms. Elsevier, 2007, doi: https://doi.org/10.1016/B978-0-12-373624-6.X5000-0.
H. Ochoa-Domínguez, K. R. Rao, Discrete Cosine Transform, 2nd ed. Boca Raton, FL: CRC Press, 2019, doi: https://doi.org/10.1201/9780203729854.
D. Elliott, K. Rao, Fast Transforms Algorithms, Analyses, Applications, 1st ed. Academic Press, 1983, uri: https://www.elsevier.com/books/fast-transforms-algorithms-analyses-applications/elliott/978-0-08-091806-8.
B. Chitprasert, K. R. Rao, “Discrete cosine transform filtering,” Signal Process., vol. 19, no. 3, pp. 233–245, 1990, doi: https://doi.org/10.1016/0165-1684(90)90115-F.
E. Armas Vega, A. Sandoval Orozco, L. García Villalba, J. Hernandez-Castro, “Digital images authentication technique based on dwt, dct and local binary patterns,” Sensors, vol. 18, no. 10, p. 3372, 2018, doi: https://doi.org/10.3390/s18103372.
L. Krikor, S. Baba, T. Arif, Z. Shaaban, “Image encryption using dct and stream cipher,” Eur. J. Sci. Res., vol. 32, no. 1, pp. 48–58, 2009.
L. Jing, C. He, L. Zhang, Q. Meng, J. Huang, Q. Zhang, “Iterative block decision feedback equalizer with soft detection for underwater acoustic channels,” Dianzi Yu Xinxi Xuebao/Journal Electron. Inf. Technol., vol. 38, no. 4, pp. 885–891, 2016, doi: https://doi.org/10.11999/JEIT150669.
J. Yang, T. Jin, C. Xiao, X. Huang, “Compressed sensing radar imaging: fundamentals, challenges, and advances,” Sensors, vol. 19, no. 14, p. 3100, 2019, doi: https://doi.org/10.3390/s19143100.
C.-F. Lee, J.-J. Shen, Z.-R. Chen, S. Agrawal, “Self-embedding authentication watermarking with effective tampered location detection and high-quality image recovery,” Sensors, vol. 19, no. 10, p. 2267, 2019, doi: https://doi.org/10.3390/s19102267.
W. Lu et al., “Watermarking based on compressive sensing for digital speech detection and recovery,” Sensors, vol. 18, no. 7, p. 2390, 2018, doi: https://doi.org/10.3390/s18072390.
K. Boukhechba, H. Wu, R. Bazine, “DCT-based preprocessing approach for ica in hyperspectral data analysis,” Sensors, vol. 18, no. 4, p. 1138, 2018, doi: https://doi.org/10.3390/s18041138.
P. Xu, B. Chen, L. Xue, J. Zhang, L. Zhu, “A prediction-based spatial-spectral adaptive hyperspectral compressive sensing algorithm,” Sensors, vol. 18, no. 10, p. 3289, 2018, doi: https://doi.org/10.3390/s18103289.
B.-S. Chow, “Data compression by shape compensation for mobile video sensors,” Sensors, vol. 9, no. 4, pp. 2461–2469, 2009, doi: https://doi.org/10.3390/s90402461.
P. Christiansen, K. Steen, R. Jørgensen, H. Karstoft, “Automated detection and recognition of wildlife using thermal cameras,” Sensors, vol. 14, no. 8, pp. 13778–13793, 2014, doi: https://doi.org/10.3390/s140813778.
Z. He, L. Jin, “Activity recognition from acceleration data based on discrete consine transform and svm,” in 2009 IEEE International Conference on Systems, Man and Cybernetics, 2009, pp. 5041–5044, doi: https://doi.org/10.1109/ICSMC.2009.5346042.
D. C. Swanson, Signal Processing for Intelligent Sensor Systems with MATLAB®, 2nd ed. CRC Press, 2011, uri: https://www.routledge.com/Signal-Processing-for-Intelligent-Sensor-Systems-with-MATLAB/Swanson/p/book/9781138075450.
Y. A. Reznik, R. K. Chivukula, “Design of fast transforms for high-resolution image and video coding,” in Proceedings of SPIE - The International Society for Optical Engineering, 2009, vol. 7443, p. 744312, doi: https://doi.org/10.1117/12.831216.
V. Britanak, K. R. Rao, Cosine-/Sine-Modulated Filter Banks. Cham: Springer International Publishing, 2018, doi: https://doi.org/10.1007/978-3-319-61080-1.
T. D. Tran, J. Liang, T. Chengjie, “Lapped transform via time-domain pre- and post-filtering,” IEEE Trans. Signal Process., vol. 51, no. 6, pp. 1557–1571, 2003, doi: https://doi.org/10.1109/TSP.2003.811222.
A. K. Jain, “A sinusoidal family of unitary transforms,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-1, no. 4, pp. 356–365, 1979, doi: https://doi.org/10.1109/TPAMI.1979.4766944.
N. R. Murthy, M. N. S. Swamy, “On the on-line computation of dct-iv and dst-iv transforms,” IEEE Trans. Signal Process., vol. 43, no. 5, pp. 1249–1251, 1995, doi: https://doi.org/10.1109/78.382409.
Z. C. Li, “On computing the two-dimensional (2-d) type iv discrete cosine transform (2-d dct-iv),” IEEE Signal Process. Lett., vol. 8, no. 8, pp. 239–241, 2001, doi: https://doi.org/10.1109/97.935741.
Y. Zeng, Z. Lin, G. Bi, L. Cheng, “Fast computation of md-dct-iv/md-dst-iv by md-dwt or md-dct-ii,” SIAM J. Sci. Comput., vol. 24, no. 6, pp. 1903–1918, 2003, doi: https://doi.org/10.1137/S1064827501394830.
H.-W. Hsu, C.-M. Liu, “Fast radix-q and mixed-radix algorithms for type-iv dct,” IEEE Signal Process. Lett., vol. 15, pp. 910–913, 2008, doi: https://doi.org/10.1109/LSP.2008.2005441.
X. Dai, M. Wagh, “Bilinear algorithms and vlsi implementations of forward and inverse mdct with applications to mp3 audio,” WO/2009/100021, 13-Aug-2009.
V. Britanak, “Comments on fast radix-9 algorithm for the dct-iv computation,” IEEE Signal Process. Lett., vol. 16, no. 11, pp. 1005–1006, 2009, doi: https://doi.org/10.1109/LSP.2009.2028450.
X. Shao, S. G. Johnson, “Type-iv dct, dst, and mdct algorithms with reduced numbers of arithmetic operations,” Signal Process., vol. 88, no. 6, pp. 1313–1326, 2008, doi: https://doi.org/10.1016/j.sigpro.2007.11.024.
V. Britanak, “The fast dct-iv/dst-iv computation via the mdct,” Signal Process., vol. 83, no. 8, pp. 1803–1813, 2003, doi: https://doi.org/10.1016/S0165-1684(03)00109-9.
A. M. Grigoryan, M. M. Grigoryan, “A novel algorithm of the 4-point type-iv discrete cosine transform,” 2008.
V. S. Shaptala, M. V. Korman, “DCT-iv computation,” Pattern Recognit. Image Anal., vol. 18, no. 1, pp. 58–62, 2008, doi: https://doi.org/10.1134/S1054661808010070.
S. M. Perera, “Signal processing based on stable radix-2 dct i-iv algorithms having orthogonal factors,” Electron. J. Linear Algebr., vol. 31, no. 1, pp. 362–380, 2016, doi: https://doi.org/10.13001/1081-3810.3207.
X. Dai, M. D. Wagh, “An mdct hardware accelerator for mp3 audio,” in 2008 Symposium on Application Specific Processors, 2008, pp. 121–125, doi: https://doi.org/10.1109/SASP.2008.4570796.
D. Chiper, “A new vlsi algorithm and architecture for the hardware implementation of type iv discrete cosine transform using a pseudo-band correlation structure,” Open Comput. Sci., vol. 1, no. 2, pp. 243–250, 2011, doi: https://doi.org/10.2478/s13537-011-0015-z.
M. Garrido, O. Gustafsson, F. Qureshi, “Unified architecture for 2, 3, 4, 5, and 7-point dfts based on winograd fourier transform algorithm,” Electron. Lett., vol. 49, no. 5, pp. 348–349, 2013, doi: https://doi.org/10.1049/el.2012.0577.
H. M. de Oliveira, R. J. Cintra, R. M. C. de Souza, “A factorization scheme for some discrete hartley transform matrices,” 2015, uri: http://arxiv.org/abs/1502.01038.
A. Cariow, M. Makowska, P. Strzelec, “Small-size FDCT/IDCT algorithms with reduced multiplicative complexity,” Radioelectron. Commun. Syst., vol. 62, no. 11, pp. 559–576, 2019, doi: https://doi.org/10.3103/S0735272719110025.
A. Cariow, J. Papliński, D. Majorkowska-Mech, “Some structures of parallel vlsi-oriented processing units for implementation of small size discrete fractional fourier transforms,” Electronics, vol. 8, no. 5, p. 509, 2019, doi: https://doi.org/10.3390/electronics8050509.
A. Ţariov, D. Majorkowska-Mech, “The multilevel signal representation in discrete base of cosine functions,” Elektronika, vol. 48, no. 7, pp. 20–21, 2007.
A. Ţariov, Algorithmic Aspects of Computing Rationalization in Digital Signal Processing. Szczecin: West Pomeranian University Press, 2012.
A. Cariow, “Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products,” J. Signal Process. Theory Appl., no. 3, pp. 1–19, 2014, doi: https://doi.org/10.7726/jspta.2014.1001.
J. Granata, M. Conner, R. Tolimieri, “The tensor product: a mathematical programming language for ffts and other fast dsp operations,” IEEE Signal Process. Mag., vol. 9, no. 1, pp. 40–48, 1992, doi: https://doi.org/10.1109/79.109206.
