Алгоритмы малоразмерного дискретного косинус-преобразования четвертого типа с уменьшенной мультипликативной сложностью

Александр Павлович Царёв; Л. Лесецки

doi:10.20535/S0021347020090022

Автор(и)

Александр Павлович Царёв Западно-поморский технологический университет, Польща https://orcid.org/0000-0002-4513-4593
Л. Лесецки Западно-поморский технологический университет, Польща https://orcid.org/0000-0002-4305-0687

DOI:

https://doi.org/10.20535/S0021347020090022

Ключові слова:

цифровая обработка сигналов, дискретное косинус-преобразование четвертого типа, быстрый алгоритм

Анотація

Дискретные косинус-преобразования ДКП широко применяются в интеллектуальных радиоэлектронных системах для обработки и анализа поступающей информации. Популярность использования этих преобразований объясняется наличием быстрых алгоритмов, которые минимизируют вычислительную и аппаратную сложность их реализации. Особое место в перечне преобразований занимает дискретное косинусное преобразование четвертого типа ДКП-IV. В статье предложено несколько алгоритмов реализации ДКП-IV. Эффективность предлагаемых решений обусловлена возможностью факторизации матрицы ДКП-IV, что при реализации ведет к снижению сложности вычислений. В статье также представлен ряд полностью параллельных алгоритмов ДКП-IV для небольших длин N = 2, 3, 4, 5, 6, 7, 8, 9 сигнальных последовательностей.

Посилання

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, doi: http://doi.org/10.1201/b18621.
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.
А. П. Царёв, М. Маковска, П. Стшелец, “Алгоритмы прямого и обратного ДКП малых порядков с уменьшенной мультипликативной сложностью,” Известия вузов. Радиоэлектроника, vol. 62, no. 11, pp. 662–677, 2019, doi: https://doi.org/10.20535/S0021347019110025.
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.