Implementacja w układach FPGA dekompresji danych zgodnie ze standardem Deflate

• Autorzy: Jamro E. , Wiatr K.

Warianty tytułu

EN

FPGA Implementation of Deflate standard data decompression

• Języki publikacji: PL

Abstrakty

PL

Otwarty standard kompresji danych, Deflate, jest szeroko stosowanym standardem w plikach .gz / .zip i stanowi kombinację kompresji metodą LZ77 / LZSS oraz kodowania Huffmana. Niniejszy artykuł opisuje implementację w układach FPGA dekompresji danych według tego standardu. Niniejszy moduł jest w stanie dokonać dekompresji co najmniej 1B na takt zegara, co przy zegarze 100MHz daje 100MB/s. Aby zwiększyć szybkość, możliwa jest praca wielu równoległych modułów dla różnych strumieni danych wejściowych.

EN

This paper describes FPGA implementation of the Deflate standard decoder. Deflate [1] is a commonly used compression standard employed e.g. in zip and gz files. It is based on dictionary compression (LZ77 / LZSS) [4] and Huffman coding [5]. The proposed Huffman decoded is similar to [9], nevertheless several improvements are proposed. Instead of employing barrel shifter a different translation function is proposed (see Tab. 1). This is a very important modification as the barrel shifter is a part of the time-critical feedback loop (see Fig. 1). Besides, the Deflate standard specifies extra bits, which causes that a single input word might be up to 15+13=28 bits wide, but this width is very rare. Consequently, as the input buffer might not feed the decoder width such wide input date, a conditional decoding is proposed, for which the validity of the input data is checked after decoding the input symbol, thus when the actual input symbol bit widths is known. The implementation results (Tab. 2) show that the occupied hardware resources are mostly defined by the number of BRAM modules, which are mostly required by the 32kB dictionary memory. For example, comparable logic (LUT / FF) resources to the Deflate standard decoder are required by the AXI DMA module which transfers data to / from the decoder.

Słowa kluczowe

PL

kompresja danych; FPGA; kodowanie Huffmana

EN

data compression; Deflate; Huffman; FPGA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 8
• Strony: 739--741
• Opis fizyczny: Bibliogr. 11 poz., rys., schem., tab.

Twórcy

autor

Jamro E.

• AGH - Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków

autor

Wiatr K.

• ACK Cyfronet AGH, ul. Nawojki 11, 30-950 Kraków

Bibliografia

• [1] Deutsch P.: DEFLATE Compressed Data Format Specification version 1.3: RFC1951, 05/1996.
• [2] Ziv, Jacob; Lempel, Abraham (May 1977). "A Universal Algorithm for Sequential Data Compression". IEEE Transactions on Information Theory 23 (3): 337-343.
• [3] Lempel–Ziv–Storer–Szymanski (LZSS) http://en.wikipedia.org/
• [4] Salomon D.: A Concise Introduction to Data Compression, Springer, 2008.
• [5] Huffman D. A.: A method for the construction of minimum-redundancy codes, Proc. Inst. Radio Eng, Vol. 40, No. 9, pp. 1098-1101, Sep. 1952.
• [6] AHA, www.aha.com
• [7] Indra, http://www.indranetworks.com
• [8] Jamro E., Russek P., Dąbrowska-Boruch A., Wielgosz M., Wiatr K.: The implementation of the customized, parallel architecture for a fast word-match program, Computer Systems Science and Engineering, 2011, vol. 26, iss. 4, s. 285–292.
• [9] Aspar Z., Yusof Z. M., Suleiman I.: Parallel Huffman Decoder with an Optimize Look Up Table Option on FPGA, TENCON 2000, Proceedings , 1, pp. 73-76.
• [10] Jamro E., Wielgosz M., Wiatr K.: FPGA Implementation of the Dynamic Huffman Encoder, Proc. IFAC Workshop on Programmable Devices and Embedded Systems, Brno, Feb. 14-16, 2006, pp. 60-65.
• [11] Xilinx Inc. LogiCORE IP AXI Master Burst (axi_master_burst) (v1.00.a), DS844 June 22, 2011.