Low-cost ANS encoder for lossless data compression in FPGAs

• Autorzy: Pastuła Magdalena , Russek Paweł , Wiatr Kazimierz

Identyfikatory

DOI

10.24425/ijet.2024.149534

• Języki publikacji: EN

Abstrakty

EN

We present the implementation of the hardware ANS compressor in FPGAs. The main goal of the design was to propose a solution suitable to low-cost, low-energy embedded systems. We propose the streaming-rANS algorithm of the ANS family as a target for the implementation. Also, we propose a set of algorithm parameters that substantially reduce the use of FPGA resources, and we examine what is the influence of the chosen parameters on compression performance. Further, we compare our design to the lossless codecs found in literature, and to the streaming-rANS codecs with arbitrary parameters.

Słowa kluczowe

EN

lossless compression; Asymmetric Numeral Systems(ANS); Hardware codec; FPGA

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 1
• Strony: 219--228
• Opis fizyczny: Bibliogr. 18 poz., tab., wykr.

Twórcy

autor

Pastuła Magdalena

• AGH University of Krakow, Krakow, Poland

autor

Russek Paweł

• AGH University of Krakow, Krakow, Poland

autor

Wiatr Kazimierz

• AGH University of Krakow, Krakow, Poland

Bibliografia

• [1] D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the Institute of Radio Engineers, vol. 40, no. 9, pp. 1098-1101, September 1952.
• [2] I. H. Witten, R. M. Neal, and J. G. Cleary, “Arithmetic coding for data compression,” Commun. ACM, vol. 30, no. 6, p. 520-540, jun 1987. [Online]. Available: doi:10.1145/214762.214771
• [3] J. Duda, “Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding,” 2014.
• [4] J. Duda, “List of asymmetric numeral systems implementations,” URL: https://encode.su/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations, accessed: [2023-08-12].
• [5] “Documentation of Facebook’s ZSTD,” URL: https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#entropy-encoding, accessed: [2023-08-13].
• [6] “Repository of Finite State Entropy,” URL: https://github.com/Cyan4973/FiniteStateEntropy, accessed: [2023-08-13].
• [7] “Specification of draco - googl’s 3d graphic compressor,” URL: https://google.github.io/draco/spec/, accessed: [2023-08-12].
• [8] J. Duda, “Asymmetric numeral systems,” 2009.
• [9] K. Tatwawadi, “What is asymmetric numeral systems? understanding the new entropy coder family,” URL: https://kedartatwawadi.github.io/post--ANS/, ac-cessed: [2023-06-05].
• [10] P. A. Hsieh and J.-L. Wu, “A review of the asymmetric numeral system and its applications to digital images,” entropy.
• [11] M. A. S. Hernández, O. Alvarado-Nava, and F. J. Z. Martínez, “Huffman coding-based compression unit for embedded systems,” in 2010 International Conference on Reconfigurable Computing and FPGAs, 2010, pp. 238-243. [Online]. Available: doi:10.1109/ReConFig.2010.65
• [12] Y. Chen, G. C. Wan, Z. W. Xia, and M. S. Tong, “A hardware design method for canonical huffman code,” in 2017 Progress in Electromagnetics Research Symposium - Fall (PIERS - FALL), 2017, pp. 2212-2215. [Online].Available: doi:10.1109/PIERS-FALL.2017.8293507
• [13] S. Mahapatra and K. Singh, “An fpga-based implementation of multi-alphabet arithmetic coding,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 54, no. 8, pp. 1678-1686, 2007. [Online]. Available: doi:10.1109/TCSI.2007.902527
• [14] S. M. Najmabadi, Z. Wang, Y. Baroud, and S. Simon, “High throughput hardware architectures for asymmetric numeral systems entropy coding,” in 2015 9th International Symposium on Image and Signal Processing and Analysis (ISPA), 2015, pp. 256-259. [Online]. Available: doi:10.1109/ISPA.2015.7306068
• [15] T. Alonso, G. Sutter, and J. López de Vergara Méndez, “An fpga-based loco-ans implementation for lossless and near-lossless image compression using high-level synthesis,” Electronics, vol. 10, p. 2934, 11 2021. [Online]. Available: doi:10.3390/electronics10232934
• [16] N. Wang, C. Wang, and S.-J. Lin, “A simplified variant of tabled asymmetric numeral systems with a smaller look-up table,” Distributed and Parallel Databases, vol. 39, pp. 711-732, 2020.
• [17] “Repository with source code of ans encoder and python scripts,” URL: https://github.com/Sharon131/masters project, accessed: [2023-08-24].
• [18] L. Kozlowski, “Shannon entropy calculator,” URL: https://www.shannonentropy.netmark.pl, accessed: [2023-08-02].

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).