2. Home
  3. ARCHIVE
  4. 2023
  5. VOL 45, NO 5 (2023)
  6. pp. 113-128

HARDWARE DECOMPRESSOR DESIGN

A.М. Sergiyenko, I.V. Mozghovyi

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

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

ABSTRACT

The common lossless compression algorithms were analyzed, and the LZW algorithm was selected for the hardware implementation. To express parallelism, this algorithm is represented as a cyclo-dynamic dataflow (CDDF). A hardware synthesis method for designing pipelined  datapath is proposed, which optimizes CDDF considering the features of the FPGA primitives and maps it to hardware using VHDL language description. Using this method, an LZW de­compressor is developed, which exhibits a high performance-to-hardware cost ratio. The de­com­­­pressor can be utilized in communication channels and other application-specific systems for data loading from memory, generating graphical stencils, and more.

KEYWORDS

field programable gate array, VHDL, dataflow graph, lossless compression, LZW algorithm.

REFERENCES

  1. Ritter D., Dann J., May N., Rinderle-Ma S. (2017). Hardware Accelerated Application Integration Processing. Industry Paper. DEBS ‘11. Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, June, 2017, pp. 215- 
    https://doi.org/10.1145/3093742.3093911
  2. Lafond S, Lilius J. (2004). An Energy Consumption Model for Java Virtual Machine. TUCS Technical Report. No. 597.
  3. Zervas N. (2015). Firmware Compression for Lower Energy and Faster Boot in IoT Devi­ces. Design & Reuse. October. https://www.design-reuse.com/articles/38541/firmware-compression-for-lower-energy-and-faster-boot-in-iot-devices.html. [Accessed: July, 2023].
  4. Walls F.G., MacInnis A.S. (2016). VESA Display Stream Compression for Television and Cinema Applications. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 6(4), 460- 
    https://doi.org/10.1109/JETCAS.2016.2602009
  5. Touba, N.A. (2006). Survey of Test Vector Compression Techniques. IEEE Design & Test of Computers. 23(4), 294- 
    https://doi.org/10.1109/MDT.2006.105
  6. Kovačec, D. (2012). FPGA IP Cores for Displays. Handbook of Visual Display Technology. J. Chen, W. Cranton, M. Fihn (Eds.): Springer, pp. 512- 
    https://doi.org/10.1007/978-3-540-79567-4_40
  7. Mozghovyi I., Sergiyenko A., Yershov R. (2021). GIF image hardware compressors. Information, Computing and Intelligent Systems. Vol. 2. 
    https://doi.org/10.20535/2708-4930.2.2021.244189
  8. Gallager R. (1978). Variations on a theme by Huffman. IEEE Transactions on Information Theory, 24(6), pp. 668- 
    https://doi.org/10.1109/TIT.1978.1055959
  9. Welch T. (1984). A Technique for High-Performance Data Compression. Computer, 17(6), pp. 8-
    https://doi.org/10.1109/MC.1984.1659158
  10. Salomon D., Motta G. (2010). Handbook of Data Compression. 5th Ed.: Springer, 1360 p.
    https://doi.org/10.1007/978-1-84882-903-9
  11. Ziv J., Lempel A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), pp. 337- 
    https://doi.org/10.1109/TIT.1977.1055714
  12. LZRW3 Data Compression Core for Xilinx FPGA. Full Datasheet. (2008). Helion Techno­logy. pp. 1- https://www.heliontech.com/downloads/lzrw3_xilinx_datasheet.pdf, [Acces­sed: July, 2023].
  13. Ziv J., Lempel A. (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5), pp. 530-
    https://doi.org/10.1109/TIT.1978.1055934
  14. Welch T.A. (1984). A technique for high-performance data compression. IEEE Compu­ter, 17(6), pp. 8- 
    https://doi.org/10.1109/MC.1984.1659158
  15. Navqi S., Naqvi R., Riaz R.A, Siddiqui F. (2011). Optimized RTL design and implementation of LZW algorithm for high bandwidth applications. Przeglad Electrotechniczny (Electrical Review), 87(4), pp. 279-
  16. Zhou X., Ito Y., Nakano K. (2016). An Efficient Implementation of LZW Decompression in the FPGA. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Chicago, IL, USA, pp. 599- 
    https://doi.org/10.1109/IPDPSW.2016.33
  17. Kagawa H., Ito Y., Nakano K. (2019). Throughput-Optimal Hardware Implementation of LZW Decompression on the FPGA. 2019 7th International Symposium on Computing and Networking Workshops (CANDARW), Nagasaki, Japan, 2019, pp. 78-83. 
    https://doi.org/10.1109/CANDARW.2019.00022
  18. Gajski D.D., Abdi S., Gerstlauer A., Schirner G. (2009). Embedded System Design. Mode­ling, Synthesis and Verification. Springer. 352 p.
    https://doi.org/10.1007/978-1-4419-0504-8
  19. Schaumont P.A. (2011). Practical Introduction to Hardware/Software Codesign. Springer. 396 p.
    https://doi.org/10.1007/978-1-4419-6000-9
  20. Fingeroff M. (2010). High-Level Synthesis. Blue Book. Mentor Graphics Corp. Xlibris Corp. 280 p.
  21. Bhattacharya B., Bhattacharyya S. (2001). Parameterized dataflow modeling for DSP systems. IEEE Transactions on Signal Processing. 49(10), pp. 2408-
    https://doi.org/10.1109/78.950795
  22. Keating M., Bricaud P. (1999). Reuse Methodology Manual. 2-nd ed. 286 p.
    https://doi.org/10.1007/978-1-4615-5037-2
  23. Lee Е.A., Messerschmitt D.G. (1987). Synchronous Data Flow. IEEE Proceedings, 75(9), pp. 1235- 
    https://doi.org/10.1109/PROC.1987.13876
  24. Lee E.A, Neuendorffer, S. (2005). Concurrent models of computation for embedded software. IEE-INST ELEC ENG. IEE Proceedings ― Computers and Digital Techniques, 152(2), pp. 239- 
    https://doi.org/10.1049/ip-cdt:20045065
  25. Khan S.A. (2011). Digital Design of Signal Processing Systems. A Practical Approach. UK: Wiley, 2011.
    https://doi.org/10.1002/9780470974681
  26. Sergiyenko A., Serhienko A., Simonenko A. (2017). A method for synchronous dataflow retiming. 2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), Kyiv, Ukraine, pp. 1015-1018, 
    https://doi.org/10.1109/UKRCON.2017.8100404
  27. Parks T.M., Pino J.L., Lee E.A. (1995). A comparison of synchronous and cycle-static dataflow. Conference Record of the 29th Asilomar Conference on Signals, Systems and Computers. Vol. 1, Pacific Grove, CA, USA, pp. 204- 
    https://doi.org/10.1109/ACSSC.1995.540541
  28. Wauters P., Engels M., Lauwereins R., Peperstraete J. A. (1996). Cyclo-dynamic dataflow. Proceedings of 4th Euromicro Workshop on Parallel and Distributed Processing, Braga, Portugal, 1996, pp. 319-
    https://doi.org/10.1109/EMPDP.1996.500603
  29. Fradet P., Girault A., Poplavko P. (2012). SPDF: A schedulable parametric data-flow MoC. Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 2012, pp. 769- 
    https://doi.org/10.1109/DATE.2012.6176572
  30. Sergiyenko A.M. (2004). VHDL dlya proectyrovanya vytchislytelnych ustrojstv. Kiev: Dia­soft. 205 p. (in Russian)
  31. Woods R., McAllister J., Lightbody G., Yi Y. (2017). FPGA-based Implementation of Signal Processing Systems. Wiley, 2d Ed. 447 p.
    https://doi.org/10.1002/9781119079231
  32. Romankevych V.O., Mozghovyi I.V., Serhiienko P.A., Zacharioudakis L. (2023), Decompressor for hardware applications. Applied Aspects of Information Technology. 6(1). Pp. 74-83.
    https://doi.org/10.15276/aait.06.2023.6

Full text: PDF