Realizacja kompresji danych metodą Huffmana z ograniczeniem długości słów kodowych

• Autorzy: Rybak K. , Jamro E. , Wiatr K.

Warianty tytułu

EN

Implementation of Huffman compression with limited codeword length

• Języki publikacji: PL

Abstrakty

PL

Praca opisuje zmodyfikowany sposób budowania książki kodowej kodu Huffmana. Książka kodowa została zoptymalizowana pod kątem implementacji sprzętowej kodera i dekodera Huffmana w układach programowalnych FPGA. Opisano dynamiczną metodę kodowania - książka kodowa może się zmieniać w zależności od zmiennego formatu kompresowanych danych, ponadto musi być przesłana z kodera do dekodera. Sprzętowa implementacja kodeka Huffmana wymusza ograniczenie maksymalnej długości słowa, w przyjętym założeniu do 12 bitów, co pociąga za sobą konieczność modyfikacji algorytmu budowy drzewa Huffmana.

EN

This paper presents a modified algorithm for constructing Huffman codeword book. Huffman coder, decoder and histogram calculations are implemented in FPGA similarly like in [2, 3]. In order to reduce the hardware resources the maximum codeword is limited to 12 bit. It reduces insignificantly the compression ratio [2, 3]. The key problem solved in this paper is how to reduce the maximum codeword length while constructing the Huffman tree [1]. A standard solution is to use a prefix coding, like in the JPEG standard. In this paper alternative solutions are presented: modification of the histogram or modification of the Huffman tree. Modification of the histogram is based on incrementing (disrupting) the histogram values for an input codeword for which the codeword length is greater than 12 bit and then constructing the Huffman tree from the very beginning. Unfortunately, this algorithm is not deterministic, i.e. it is not known how much the histogram should be disrupted in order to obtain the maximum codeword length limited by 12 bit. Therefore several iterations might be required. Another solution is to modify the Huffman tree (see Fig. 2). This algorithm is more complicated (when designing), but its execution time is more deterministic. Implementation results (see Tab. 1) show that modifi-cation of the Huffman tree results in a slightly better compression ratio.

Słowa kluczowe

PL

kompresja danych; FPGA; kodowanie Huffmana

EN

data compression; FPGA; Huffman coding

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 7
• Strony: 662--664
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Rybak K.

autor

Jamro E.

autor

Wiatr K.

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

Bibliografia

• [1] 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.
• [2] Jamro E., Wielgosz M., Wiatr K.: Implementacja Adaptacyjnego Kodera Huffmana w Układach FPGA, Materiały Krajowej Konferencji „Reprogramowalne Układy Cyfrowe”, Szczecin 12-13 Maj 2005, pp. 207-214.
• [3] 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.
• [4] Przelaskowski A.: Kompresja danych. Wydawnictwo BTC, Warszawa 2005.
• [5] Drozdek A.: Wprowadzenie do kompresji danych, Wydawnictwa Naukowo-Techniczne, Warszawa 1999.
• [6] Aspar Z., Mohd Yusof Z., Suleiman I.: Parallel Huffman decoder with an optimized look up table option on FPGA, Proc. TENCON 2000, vol. 1, pp. 73-76.
• [7] DEFLATE Compressed Data Format Specification version 1.3: RFC1951, 05/1996.
• [8] Aspar, Z., Mohd Yusof, Z., Suleiman, I.: Parallel Huffman decoder with an optimized look up table option on FPGA, ENCON 2000. Proceedings , vol. 1, no. 1, 2000, pp. 73-76.