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 decompressor is developed, which exhibits a high performance-to-hardware cost ratio. The decompressor 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
- 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 - Lafond S, Lilius J. (2004). An Energy Consumption Model for Java Virtual Machine. TUCS Technical Report. No. 597.
- Zervas N. (2015). Firmware Compression for Lower Energy and Faster Boot in IoT Devices. 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].
- 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 - 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 - 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 - 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 - 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 - Welch T. (1984). A Technique for High-Performance Data Compression. Computer, 17(6), pp. 8-
https://doi.org/10.1109/MC.1984.1659158 - Salomon D., Motta G. (2010). Handbook of Data Compression. 5th Ed.: Springer, 1360 p.
https://doi.org/10.1007/978-1-84882-903-9 - 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 - LZRW3 Data Compression Core for Xilinx FPGA. Full Datasheet. (2008). Helion Technology. pp. 1- https://www.heliontech.com/downloads/lzrw3_xilinx_datasheet.pdf, [Accessed: July, 2023].
- 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 - Welch T.A. (1984). A technique for high-performance data compression. IEEE Computer, 17(6), pp. 8-
https://doi.org/10.1109/MC.1984.1659158 - 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-
- 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 - 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 - Gajski D.D., Abdi S., Gerstlauer A., Schirner G. (2009). Embedded System Design. Modeling, Synthesis and Verification. Springer. 352 p.
https://doi.org/10.1007/978-1-4419-0504-8 - Schaumont P.A. (2011). Practical Introduction to Hardware/Software Codesign. Springer. 396 p.
https://doi.org/10.1007/978-1-4419-6000-9 - Fingeroff M. (2010). High-Level Synthesis. Blue Book. Mentor Graphics Corp. Xlibris Corp. 280 p.
- 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 - Keating M., Bricaud P. (1999). Reuse Methodology Manual. 2-nd ed. 286 p.
https://doi.org/10.1007/978-1-4615-5037-2 - Lee Е.A., Messerschmitt D.G. (1987). Synchronous Data Flow. IEEE Proceedings, 75(9), pp. 1235-
https://doi.org/10.1109/PROC.1987.13876 - 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 - Khan S.A. (2011). Digital Design of Signal Processing Systems. A Practical Approach. UK: Wiley, 2011.
https://doi.org/10.1002/9780470974681 - 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 - 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 - 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 - 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 - Sergiyenko A.M. (2004). VHDL dlya proectyrovanya vytchislytelnych ustrojstv. Kiev: Diasoft. 205 p. (in Russian)
- 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 - 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