Elementy kompresji danych – kodowanie nienadmiarowe


Konstrukcje kodów metodą Huffmana. Kody zwarte



Pobieranie 2.53 Mb.
Strona11/32
Data28.10.2017
Rozmiar2.53 Mb.
1   ...   7   8   9   10   11   12   13   14   ...   32
4. Konstrukcje kodów metodą Huffmana. Kody zwarte

Metoda Huffmana jest ogólną metodą konstrukcji kodów zwartych. Kodem zwartym nazywany jest kod chwilowy, którego średnia długość ciągów kodowych jest najmniejsza z możliwych.

Kodowanie metodą Huffmana realizowane jest w dwóch etapach. W etapie pierwszym dokonuje się redukcji zbioru kodowanych informacji, przy czym redukcja ta składa się z ciągu redukcji elementarnych. W wyniku wykonania każdej redukcji elementarnej otrzymuje się zbiór informacji o liczności zmniejszonej o q-1 w stosunku do zbioru redukowanego. Redukcję prowadzi się aż do otrzymania zbioru informacji o liczności równej q. Uzyskanie takiego zbioru rozpoczyna drugi etap kodowania. Jeżeli w wyniku redukcji elementarnych nie uzyska się zbioru zredukowanego o liczności q należy do podstawowego zbioru informacji dodać nowe informacje (rozszerzyć zbiór podstawowy) występujące z prawdopodobieństwem równym zero. Etap drugi metody Huffmana składa się z ciągu tzw. kodowań elementarnych, realizowanych dla poszczególnych zbiorów informacji, które zostały otrzymane w wyniku kolejnych redukcji elementarnych. Należy zaznaczyć, że dla zakodowania zbioru otrzymanego w m-tym kroku redukcji, wykorzystuje się kod określony w m+1 kroku redukcji. Zakodowanie zbioru otrzymanego po zakończeniu redukcji (pierwsze kodowanie elementarne) jest bardzo proste, ponieważ zbiór ten zawiera tylko q informacji. Proces kodowania prowadzi się aż do momentu uzyskania ciągów kodowych wszystkich informacji.

Z powyższego wynika, że wyjaśnienie procedury Huffmana sprowadza się do sprecyzowania sposobu wykonywania redukcji elementarnej i kodowania elementarnego.

Redukcja elementarna

Rozważa się zbiór informacji otrzymany w kolejnym m-tym kroku redukcji



Prawdopodobieństwa występowania poszczególnych informacji wynoszą



Przyjmuje się, że informacje składowe zbioru wejściowego są uporządkowane według malejących prawdopodobieństw, tzn.





Redukcja elementarna sprowadza się do zrezygnowania z rozróżniania dwóch najmniej prawdopodobnych informacji oraz przez wprowadzenie zamiast nich nowej informacji . Prawdopodobieństwo występowania tej informacji wynosi


Pobieranie 2.53 Mb.

Share with your friends:
1   ...   7   8   9   10   11   12   13   14   ...   32




©operacji.org 2020
wyślij wiadomość

    Strona główna
warunków zamówienia
istotnych warunków
przedmiotu zamówienia
wyboru operacji
Specyfikacja istotnych
produktu leczniczego
oceny operacji
rozwoju lokalnego
strategii rozwoju
kierowanego przez
specyfikacja istotnych
Nazwa przedmiotu
Karta oceny
ramach działania
przez społeczno
obszary wiejskie
dofinansowanie projektu
lokalnego kierowanego
Europa inwestująca
Regulamin organizacyjny
przetargu nieograniczonego
kryteria wyboru
Kryteria wyboru
Lokalne kryteria
Zapytanie ofertowe
Informacja prasowa
nazwa produktu
Program nauczania
Instrukcja obsługi
zamówienia publicznego
Komunikat prasowy
programu operacyjnego
udzielenie zamówienia
realizacji operacji
opieki zdrowotnej
przyznanie pomocy
ramach strategii
Karta kwalifikacyjna
oceny zgodno
Specyfikacja techniczna
Instrukcja wypełniania
Wymagania edukacyjne
Regulamin konkursu
lokalnych kryteriów
strategia rozwoju
sprawozdania finansowego
ramach programu
ramach poddziałania
kryteriów wyboru
operacji przez
trybie przetargu