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

Автор(и)

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.

##submission.downloads##

Опубліковано

2020-09-22

Як цитувати

Царёв, А. П., & Лесецки, Л. (2020). Алгоритмы малоразмерного дискретного косинус-преобразования четвертого типа с уменьшенной мультипликативной сложностью. Вісті вищих учбових закладів. Радіоелектроніка, 63(9), 549–569. https://doi.org/10.20535/S0021347020090022

Номер

Том 63 № 9 (2020)

Розділ

Оригінальні статті

Ліцензія

Авторське право (c) 2020 Известия высших учебных заведений. Радиоэлектроника

Издатель журнала Известия высших учебных заведений. Радиоэлектроника (сокр. "Известия вузов. Радиоэлектроника"), Национальный технический университет Украины "Киевский политехнический институт", учитывает, что доступ автора к его статье является важным как для самого автора, так и для спонсоров его исследований. Мы представлены в базе издателей SHERPA/RoMEO как зеленый издатель (green publisher), что позволяет автору выполнять самоархивирование своей статьи. Однако важно, чтобы каждая из сторон четко понимала свои права. Просьба более детально ознакомиться с Политикой самоархивирования нашего журнала.

Политика оплаченного открытого доступа POA (paid open access), принятая в журнале, позволяет автору выполнить все необходимые требования по открытому доступу к своей статье, которые выдвигаются институтом, правительством или фондом при выделении финансирования. Просьба более детально ознакомиться с политикой оплаченного открытого доступа нашего журнала (см. отдельно).

Варианты доступа к статье:

1. Статья в открытом доступе POA (paid open access)

В этом случае права автора определяются лицензией CC BY (Creative Commons Attribution).

2. Статья с последующим доступом по подписке

В этом случае права автора определяются авторским договором, приведенным далее.

  • Автор (каждый соавтор) уступает Издателю журнала «Известия высших учебных заведений. Радиоэлектроника» НТУУ «КПИ» на срок действия авторского права эксклюзивные права на материалы статьи, в том числе право на публикацию данной статьи издательством Аллертон Пресс, США (Allerton Press) на английском языке в журнале «Radioelectronics and Communications Systems». Передача авторского права охватывает исключительное право на воспроизведение и распространение статьи, включая оттиски, переводы, фото воспроизведения, микроформы, электронные формы (он- и оффлайн), или любые иные подобные формы воспроизведения, а также право издателя на сублицензирование третьим лицам по своему усмотрению без дополнительных консультаций с автором. При этом журнал придерживается Политики конфиденциальности.
  • Передача прав включает право на обработку формы представления материалов с помощью компьютерных программам и систем (баз данных) для их использования и воспроизводства, публикации и распространения в электронном формате и внедрения в системы поиска (базы данных).
  • Воспроизведение, размещение, передача или иное распространение или использование материалов, содержащихся в статье должно сопровождаться ссылкой на Журнал и упоминанием Издателя, а именно: название статьи, имя автора (соавторов), название журнала, номер тома, номер выпуска, копирайт авторов и издателя "© Национальный технический университет Украины "Киевский политехнический институт"; © автор(ы)".
  • Автор (каждый соавтор) материалов сохраняет все права собственника материалов, включая патентные права на любые процессы, способы или методы и др., а также права на товарные знаки.
  • Издатель разрешает автору (каждому соавтору) материалов следующее:
  1. Право пользоваться печатными или электронными вариантами материалов статьи в форме и содержании, принятыми Издателем для публикации в Журнале. Подробнее см. политики Оплаченного открытого доступа, подписки и самоархивирования.
  2. Право бесплатно копировать или передавать коллегам копию напечатанной статьи целиком или частично для их личного или профессионального использования, для продвижения академических или научных исследований или для учебного процесса или других информационных целей, не связанных с коммерческими целями.
  3. Право использовать материалы из опубликованной статьи в написанной автором (соавторами) книге, монографии, учебнике, учебном пособии и других научных и научно-популярных изданиях.
  4. Право использовать отдельные рисунки или таблицы и отрывки текста из материалов в собственных целях обучения или для включения их в другую работу, которая печатается (в печатном или электронном формате) третьей стороной, или для представления в электронном формате во внутренние компьютерные сети или на внешние сайты автора (соавторов).
  • Автор (соавторы) соглашаются, что каждая копия материалов или любая ее часть, распространенная или размещенная ими в печатном или электронном формате, будет содержать указание на авторское право, предусмотренное в Журнале и полную ссылку на Журнал Издателя.
  • Автор (соавторы) гарантирует, что материалы являются оригинальной работой и представлены впервые на рассмотрение только в этом Журнале и ранее не публиковались. Если материалы написаны совместно с соавторами, автор гарантирует, что проинформировал их относительно условий публикации материалов и получил их подписи или письменное разрешение подписываться от их имени.
  • Если в материалы включаются отрывки из работ или имеются указания на работы, которые охраняются авторским правом и принадлежат третьей стороне, то автору необходимо получить разрешение владельца авторских прав на использование таких материалов в первом случае и сделать ссылку на первоисточник во втором.
  • Автор гарантирует, что материалы не содержат клеветнических высказываний и не посягают на права (включая без ограничений авторское право, права на патент или торговую марку) других лиц и не содержат материалы или инструкции, которые могут причинить вред или ущерб третьим лицам. Автор (каждый соавтор) гарантирует, что их публикация не приведет к разглашению секретных или конфиденциальных сведений (включая государственную тайну). Подтверждением этого является Экспертное заключение (см. перечень документов в Правила для авторов).
  • Издатель обязуется опубликовать материалы в случае получения статьей положительного решения редколлегии о публикации на основании внешнего рецензирования (см. Политика рецензирования).
  • В случае публикации статьи на английском языке в журнале «Radioelectronics and Communications Systems» (Издатель: Аллертон Пресс, США, распространитель Springer) автору (соавторам) выплачивается гонорар после выхода последнего номера журнала года, в котором опубликована данная статья.
  • Документ Согласие на публикацию, который подают русскоязычные авторы при подаче статьи в редакцию, является краткой формой данного договора, в котором изложены все ключевые моменты настоящего договора и наличие которого подтверждает согласие автора (соавторов) с ним. Аналогичным документом для англоязычных авторов является Copyright Transfer Agreement (CTA), предоставляемый издательством Allerton Press.
  • Настоящий Договор вступает в силу в момент принятия статьи к публикации. Если материалы не принимаются к публикации или до публикации в журнале автор (авторы) отозвал работу, настоящий Договор не приобретает (теряет) силу.