2. Головна
  3. АРХІВ НОМЕРІВ
  4. 2023 рік
  5. Том 45, № 5 (2023)
  6. c. 113-129

Проєктування апаратного декомпресора

А.М. Сергієнко, д-р техн. наук, І.В. Мозговий

Національний технічний університет України
«Київський політехнічний інститут ім. Ігоря Сікорського»
Україна, 03056, Київ, Берестейський пр-т, 37
тел. +38(068) 8123376, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.;
тел. +38(068) 1307910, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.

Èlektron. model. 2023, 45(5):113-129

https://doi.org/10.15407/emodel.45.05.113

АНОТАЦІЯ

Проаналізовано загальні алгоритми стиснення без втрат, і серед них обрано алгоритм LZW для апаратної реалізації. Для вираження паралелізму цей алгоритм представлено як цикло-динамічний граф потоків даних. Запропоновано метод апаратного синтезу для проектування конвеєрних блоків обробки даних, згідно з яким цикло-динамічний граф потоків даних оптимізується з урахуванням особливостей примітивів програмовних логічних інтегральних схем та відображається у апаратні засоби за допомогою опису мовою VHDL. З застосуванням цього методу розроблено LZW-декомпресор, який має ви­соке співвідношення пропускної спроможністі — апаратні витрати, і можна використо­вувати в каналах зв’язку та інших спеціалізованих системах.

КЛЮЧОВІ СЛОВА:

програмована логічна інтегральна схема, граф потоків даних, безвтратне стиснення, алгоритм LZW.

СПИСОК ЛІТЕРАТУРИ

  1. Ritter D., Dann J., May N., Rinderle-Ma S. Hardware Accelerated Application Integration Processing. Industry Paper. DEBS ‘11: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, June, 2017, 2017, рр. 215-226. URL: https://doi.org/10.1145/3093742.3093911.
  2. Lafond S, Lilius J. An Energy Consumption Model for Java Virtual Machine. TUCS Technical Report, 2004, no. 597.
  3. Zervas N. Firmware Compression for Lower Energy and Faster Boot in IoT Devices. Design & Reuse. October. 2015. https://www.design-reuse.com/articles/38541/firmware-compression-for-lower-energy-and-faster-boot-in-iot-devices.html. (date of access: 01.07.2023).
  4. Walls F.G., MacInnis A.S. VESA Display Stream Compression for Television and Cinema Applications, IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016. Vol. 6, no. 4, p. 460- URL: https://doi.org/10.1109/JETCAS.2016.2602009.
  5. Touba, N.A. Survey of Test Vector Compression Techniques. IEEE Design & Test of Computers. Vol. 23, no. 4. Pр. 294-303. URL: https://doi.org/10.1109/MDT.2006. 105.
  6. Kovačec, D. FPGA IP Cores for Displays. Handbook of Visual Display Technology / ed. by J. Chen, W. Cranton, M. Fihn: Springer, 2012, рр. 512-530. URL: https://doi.org/10.1007/ 978-3-540-79567-4_40
  7. Mozghovyi I., Sergiyenko A., Yershov R. GIF image hardware compressors. Information, Computing and Intelligent Systems, 2021, Vol. 2. URL: https://doi.org/10.20535/2708-4930.2.2021.244189
  8. Gallager R. Variations on a theme by Huffman. IEEE Transactions on Information Theory, 1978. Vol. 24, no. 6, pр. 668- URL: https://doi.org/10.1109/TIT.1978.1055959.
  9. Welch T. A Technique for High-Performance Data Compression. Computer. Vol. 17, no. 6, р. 8-19. URL: https://doi.org/10.1109/MC.1984.1659158.
  10. Salomon D., Motta G. Handbook of Data Compression. 5th Ed.: Springer, 2010, 1360 p.
  11. Ziv J., Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977. Vol. 23, no. 3, рр. 337-343. URL: https://doi.org/ 1109/TIT.1977.1055714
  12. LZRW3 Data Compression Core for Xilinx FPGA. Full Datasheet. Helion Technology. 2008, pр. 1-3. URL: https://www.heliontech.com/downloads/lzrw3_xilinx_datasheet.pdf, (accessed: 01.06.2023).
  13. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 1978. Vol. 24, no. 5, рр. 530-536. URL: https:// org/10.1109/TIT.1978.1055934.
  14. Welch T.A. A technique for high-performance data compression. IEEE Computer, 1984. Vol. 17, no. 6, рр. 8-19. URL: https://doi.org/10.1109/MC.1984.1659158
  15. Navqi S., Naqvi R., Riaz R.A., Siddiqui F. Optimized RTL design and implementation of LZW algorithm for high bandwidth applications. Przeglad Electrotechniczny (Electrical Review), 2011, Vol. 87, no. 4, рр. 279-
  16. Zhou X., Ito Y., Nakano K. An Efficient Implementation of LZW Decompression in the FPGA. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). Chicago, IL, USA, 2016, рр. 599-607, URL: https://doi.org/10.1109/IPDPSW. 33.
  17. Kagawa H., Ito Y., Nakano K. Throughput-Optimal Hardware Implementation of LZW Decompression on the FPGA. 2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW), Nagasaki, Japan, 2019, рр. 78-83. URL: https://doi.org/10.1109/CANDARW.2019.00022.
  18. Gajski D.D., Abdi S., Gerstlauer A., Schirner G. Embedded System Design. Modeling, Synthesis and Verification: Springer, 2009, 352 p.
  19. Schaumont P.A. Practical Introduction to Hardware/Software Codesign. Springer, 2011, 396 p.
  20. Fingeroff M. High-Level Synthesis. Blue Book: Mentor Graphics Corp. Xlibris Corp, 2010, 280 p.
  21. Bhattacharya B., Bhattacharyya S. “Parameterized dataflow modeling for DSP systems”. IEEE Transactions on Signal Processing, 2001. Vol. 49, no. 10, рр. 2408-
  22. Keating M., Bricaud P. Reuse Methodology Manual. 2-nd ed.: Kluwer, 1999, 286 p.
  23. Ли Е.А., Мессершмитт Д.Г. Вычисления с синхронными потоками данных. Труды ТИИЭР, 1987. Т. 75. № 9, с. 107—119. /перекл. Е.A. Lee and D.G. Messerschmitt. Synchronous Data Flow. IEEE Proceedings, Sept. 1987.
  24. Lee, E. A, & Neuendorffer, S. Concurrent models of computation for embedded software. IEE-INST ELEC ENG. IEE Proceedings-Computers and Digital Techniques, 2005. Vol. 152, no. 2, рр. 239-
  25. Khan S.A. Digital Design of Signal Processing Systems. A Practical Approach. UK: Wiley, 2011.
  26. Sergiyenko A., Serhienko A., Simonenko A. A method for synchronous dataflow retiming. 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). Kyiv, Ukraine, 2017, рр. 1015-1018, URL: https://doi.org/10.2017.8100404.
  27. Parks T.M., Pino J.L., Lee E.A. A comparison of synchronous and cycle-static dataflow. Conference Record of The Twenty-Ninth Asilomar Conference on Signals, Systems and Computers. 1995. Vol. 1: Pacific Grove, CA, USA, рр. 204-210, URL: https://doi.org/ 1109/ACSSC.1995.540541
  28. Wauters P., Engels M., Lauwereins R., Peperstraete J.A. Cyclo-dynamic dataflow. Proceedings of 4th Euromicro Workshop on Parallel and Distributed Processing, Braga, Portugal, 1996, pр. 319-326, URL: https://doi.org/10.1109/EMPDP.1996.500603.
  29. Fradet P., Girault A., Poplavko P. SPDF: A schedulable parametric data-flow MoC. Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 2012, рр. 769- URL: https://doi.org/10.1109/DATE.2012.6176572.
  30. Сергиенко А.М. VHDL для проектирования вычислительных устройств. Киев: Диа­софт. 2004, 205 с.
  31. Woods R., McAllister J., Lightbody G., Yi Y. FPGA-based Implementation of Signal Processing Systems. Wiley, 2d Ed. 2017. 447 p.
  32. Romankevych V.O., Mozghovyi I.V., Serhiienko P.A., Zacharioudakis L. Decompressor for hardware applications. Applied Aspects of Information Technology, 2023. Vol. 6, no. 1, рр. 74-83. URL: https://doi.org/10.15276/aait.06.2023.6

СЕРГІЄНКО Анатолій Михайлович, д-р техн. наук, ст. наук. співробітник, професор кафедри обчислювальної техніки Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського». В 1975 р. закінчив Київський політехнічний ін-т. Область наукових досліджень — архітектура ком’ютерів, високо­рівневий синтез обчислювальних пристроїв, програмування ПЛІС, цифрова обробка сиг­налів, штучний інтелект.

Мозговий Іван Владиславович, аспірант кафедри обчислювальної техніки Національ­ного технічного університету України «Київський політехнічний інститут ім. Ігоря Сі­корського», який закінчив у 2019 р. Область наукових досліджень — вбудовані комп’ю­терні системи, програмування ПЛІС, цифрова обробка сигналів.

Повний текст: PDF