Optymalizacja sprzętowej architektury kompresji danych metodą słownikową

• Autorzy: Gwiazdoń M. , Jamro E. , Wiatr K.

Warianty tytułu

EN

FPGA implementation of Deflate standard data decompression

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł opisuje nową architekturę sprzętową kompresji słownikowej, np. LZ77, LZSS czy też Deflate. Zaproponowana architektura oparta jest na funkcji haszującej. Poprzednie publikacje były oparte na sekwencyjnym odczycie adresu wskazywanego przez pamięć hasz, niniejszy artykuł opisuje układ, w którym możliwe jest równoległe odczytywanie tego adresu z wielu pamięci hasz, w konsekwencji możliwa jest kompresja słownikowa z szybkością na poziomie 1B ciągu wejściowego na takt zegara. Duża szybkość kompresji jest okupiona nieznacznym spadkiem stopnia kompresji.

EN

This paper describes a novel parallel architecture for hardware (ASIC or FPGA) implementation of dictionary compressor, e.g. LZ77 [1], LZSS [2] or Deflate [4]. The proposed architecture allows for very fast compression – 1B of input data per clock cycle. A standard compression architecture [8, 9] is based on sequential hash address reading (see Fig. 2) and requires M clock cycles per 1B of input data, where M is the number of candidates for string matching, i.e. hashes look ups (M varies for different input data). In this paper every hash address is looked up in parallel (see Fig. 3). The drawback of the presented method is that the number of M is defined (limited), therefore the compression ratio is slightly degraded (see Fig. 4). To improve compression ratio, a different sting length may be searched independently, i.e. not only 3B, but also 4B, … N B hashes (see results in Fig. 5, 6). Every hash memory (M(N-2)) usually requires a direct look-up in the dictionary to eliminate hash false positive cases or to check whether a larger length sting was found. In order to reduce the number of dictionary reads, an additional pre-elimination algorithm is proposed, thus the number of dictionary reads does not increase rapidly with growing N (see Fig. 7).

Słowa kluczowe

PL

kompresja danych; FPGA; kodowanie Huffmana

EN

data compression; Deflate; LZ77; FPGA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 8
• Strony: 827--829
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Gwiazdoń M.

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

autor

Jamro E.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków
• ACK CYFRONET AGH, ul. Nawojki 11, 30-950 Kraków

autor

Wiatr K.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków
• ACK CYFRONET AGH, ul. Nawojki 11, 30-950 Kraków

Bibliografia

• [1] Ziv, Jacob; Lempel, Abraham (May 1977): A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 23 (3): 337-343.
• [2] Lempel–Ziv–Storer–Szymanski (LZSS) http://en.wikipedia.org/
• [3] Salomon D.: A Concise Introduction to Data Compression, Springer, 2008.
• [4] Deutsch P.: DEFLATE Compressed Data Format Specification version 1.3: RFC1951, 05/1996.
• [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] Morales-Sandoval M., Feregrino-Uribe C.: On the Design and Implementation of an FPGA based Lossless Data Compressor, Congreso Internacional de Cómputo Reconfigurable FPGAs, Colima, México, pp. 29-38, Sep. 2004.
• [7] Mehboob C., Khan S. A., Ahmed Z., Jamal H., Shahbaz M.: Multigig Lossless Data Compression Device, Consumer Electronics, IEEE Transactions on, On page(s): 1927-1932 Volume: 56, Issue: 3, Aug. 2010.
• [8] Rigler S., Bishop W., Kennings A.: FPGA-Based Lossless Data Compression using Huffman and LZ77 Algorithms, Electrical and Computer Engineering, 2007. CCECE 2007. Canadian Conference on, 22-26 April 2007, pp. 1235 – 1238.
• [9] Shcherbakov I., Weis C., Wehn N.: A High-Performance FPGA-Based Implementation of the LZSS Compression Algorithm, 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012, pp. 449-453.
• [10] Arnold R., Bell T.: A corpus for the evaluation of lossless compression algorithms, http://corpus.canterbury.ac.nz/descriptions/#calgary.