Podręcznik

Celem kodowania kompresyjnego jest zmniejszenie objętości (liczby bitów) reprezentujących sygnał lub plik. Kodowanie kompresyjne dzieli się na:
- stratne,
- bezstratne. 
Kodowanie stratne dotyczy przede wszystkim sygnałów lub plików, które odbiera człowiek za pomocą narządu słuchu lub wzroku. Ich wierne przesłanie albo zarejestrowanie nie jest możliwe w stu procentach. Zawsze w procesie przetwarzania takich sygnałów wprowadzamy jakieś zakłócenia i zniekształcenia. Ich wielkość i znaczenie percepcyjne mogą być różne. W szczególności w przypadku przesyłania takich sygnałów staramy się minimalizować ich przepływność binarną ze względu na ograniczenia przepustowości kanału transmisyjnego, czasami kosztem znacznego pogorszenia ich jakości i utraty części informacji. Tak nie możemy postąpić w wielu innych przypadkach, na przykład, gdy plik jest arkuszem Excel. Nie znaczy to wcale, że nie można zmniejszyć objętości takiego pliku w stosunku do jego objętości pierwotnej, zachowując całość informacji. Tego rodzaju kodowanie nazywa się kodowaniem bezstratnym. Czytelnik zapewne zna co najmniej kilka programów, które zmniejszają rozmiary plików bez straty informacji.

Kodowanie stratne
Szczególne znaczenie i wpływ na współczesną teleinformatykę miała cyfryzacja sygnału mowy na potrzeby przesyłania go w sieci telefonicznej. Klasyczne pasmo sygnału telefonicznego zawiera się w zakresie od 300 Hz do 3,4 kHz. Wystarczyłoby zatem próbkować ten sygnał z częstotliwością niewiele większą od 3,1 kHz. Ponieważ jednak, filtry ograniczające pasmo sygnału nie działają idealnie, a także z innych powodów, związanych z rozwiązaniami użytymi w systemach teletransmisyjnych zdecydowano się przyjąć częstotliwość próbkowania fp równą 8 kHz. Przed określeniem liczby poziomów kwantyzacji przeprowadzono badania i okazało się, że gdy użyjemy 256 poziomów kwantyzacji, to szum kwantyzacji jest wtedy na tyle mały, że nie ma istotnego wpływu na wrażenia percepcyjne po przywróceniu sygnałowi postaci analogowej. 

Ponieważ do zapisania w postaci binarnej każdego z 256 poziomów wystarczy 8 bitów (2⁸=256) zatem przepływność binarna tak przetworzonego sygnału mowy wynosi 64 kbit/s (8 kHz . 8 bitów). Wielokrotności tej przepływności, jak również jej wybrane podwielokrotności są typowymi przepływnościami stosowanymi nie tylko do transmisji sygnału mowy.  
   
Kodowanie sygnału mowy
Techniki kodowania sygnału mowy w celu jego kompresji rozwijały się przez wiele lat ze względu na niewystarczające możliwości transmisyjne systemów telekomunikacyjnych. Po raz pierwszy z problemem oszczędnego wykorzystywania dostępnych zasobów transmisyjnych stykamy się już w analogowych systemach telefonicznych wykorzystujących kable podmorskie. Przyjęto wtedy rozwiązanie oparte na wykrywaniu przerw w mówieniu (ciszy), ich usuwaniu w nadajniku i odtwarzaniu w odbiorniku, dzięki czemu uzyskano możliwość jednoczesnego przesyłania większej liczby rozmów. Rozwiązanie to znalazło również zastosowanie w telefonii międzynarodowej, a w wersji cyfrowej, na przykład w systemach satelitarnych. Kodowanie kompresyjne to nie tylko zawężanie pasma sygnału czy eliminacja ciszy – to także techniki kodowania sygnału mowy, który wcześniej poddany został cyfryzacji, a więc techniki, które pozwalają zmniejszyć przepływność binarną sygnału. Techniki kodowania kompresyjnego sygnału mowy są możliwe do zastosowania dzięki, tak zwanej redundancji sygnału mowy. Sygnał mowy zawiera informacje mało istotne, albo zupełnie nieistotnych z punktu widzenia słuchacza i celu kompresji, które można z niego usunąć. Wiemy już, że pasmo sygnału mowy można znacząco ograniczyć, usunąć z niego ciszę, kwantować, stosując 256 poziomów kwantyzacji, a mimo to najczęściej akceptujemy jego jakość, gdy jest to sygnał telefoniczny. Na pewno jednak nie uznalibyśmy jego jakości za wystarczająco dobrą, gdyby był on nagrany na płytę CD.
Opracowano wiele różnych metod kodowania kompresyjnego cyfrowego sygnału mowy z myślą o zastosowaniach telekomunikacyjnych. Ich praktyczne implementacje nazywane kodekami (koder i dekoder) mogą być zarówno hardwareowe, jak i softwareowe. Najprostsze kodeki to zwykłe przetworniki A/C, nazywane kodekami PCM (modulacja impulsowo-kodowa). Bardziej skomplikowane rozwiązanie to, tak zwana różnicowa modulacja kodowo-impulsowa DPCM. W koderach PCM każda bieżąca próbka jest kodowana niezależnie od wcześniejszych i późniejszych próbek sygnału. Tymczasem, nawet pobieżna obserwacja przebiegi czasowego mowy pozwala zauważyć w nim pewną powtarzalność (rysunek 1.14). 

Rys.1.14. Przebiegi czasowe głoski dźwięcznej i bezdźwięcznej

Nie powinno to nas dziwić, jeżeli uzmysłowimy sobie, że wypowiadane głoski mają pewien czas trwania (najczęściej rzędu kilkudziesięciu milisekund). Z dużym przybliżeniem można powiedzieć, że cechy sygnału w trakcie trwania głoski, a przynajmniej w jej stacjonarnej części, niewiele się zmieniają. Jeżeli sygnał jest próbkowany z częstotliwością 8 kHz, to w czasie, np. 50 ms mamy 400 jego próbek. To, że przez cały czas trwania głoski słyszymy i rozpoznajemy ją jako tę właśnie głoskę oznacza, że próbki mowy są ze sobą skorelowane (zależne jedna od drugiej). Dotyczy to nie tylko głosek dźwięcznych, gdzie powtarzalność przebiegu jest spowodowana okresowością drgań strun głosowych i zauważalna w ich przebiegu czasowym, ale również głosek bezdźwięcznych, których przebiegi nie wykazują wizualnie powtarzalności (rysunek 1.14). Korelacja pomiędzy próbkami pozwala w przybliżeniu określić amplitudę bieżącej próbki na podstawie pewnej liczby próbek wcześniejszych albo próbek następujących po próbce bieżącej. Amplituda x(n) każdej bieżącej (wejściowej) próbki sygnału mowy jest porównywana z amplitudą  dla niej przewidywaną, w bloku, tak zwanego predykatora. W kwantyzatorze jest kwantowany nie sygnał wejściowy, ale błąd predykcji r(n) definiowany następująco:

 Błąd predykcji ma z reguły dużo mniejszą amplitudę niż sam sygnał, a zatem może być kodowany za pomocą mniejszej liczby bitów. Na wejście predykatora podawany jest sygnał błędu predykcji oraz przewidywana próbka sygnału mowy Rozszerzenie modulacji DPCM o techniki adaptacji skoku kwantyzacji, o których mówiliśmy wcześniej prowadzi do kodowania ADPCM (rysunek 1.15).

Rys.1.15. Koder ADPCM

Na zakończenie krótko scharakteryzujemy technikę kodowania sygnałów dźwiękowych znaną pod nazwą MP3. Zaznaczmy, że koder MP3 nie  działa w czasie rzeczywistym, a więc nie ma on zastosowania w systemach, w których sygnał musi być kodowany na bieżąco, w możliwie jak najkrótszym czasie.  Koder MP3 koduje sygnał zapisany w formacie wave, w taki sposób by znacząco zredukować rozmiar pliku zajmowanego przez sygnał, nie powodując istotnej utraty jakości sygnału. W formacie wave sygnał jest próbkowany z częstotliwością 44,1 kHz , każda jego próbka reprezentowana za pomocą sekwencji 16 bitowej, a więc plik z  jednosekudowym  sygnałem stereofonicznym zajmuje aż 1,4112 Mbita.  Redukcja objętości sygnału jest możliwa tylko dlatego, że słuch człowieka nie jest doskonały. Najogólniej można powiedzieć, że człowiek nie słyszy pewnych dźwięków w obecności innych. Jest to tak zwany efekt maskowania (rysunek 1.16). 

Rys.1.16. Maskowanie dźwięków w dziedzinie czasu (a) i w dziedzinie częstotliwości (b

Maskowanie w przód jest szczególnie zauważalne, gdy sygnał maskowany pojawi się w czasie Δt₁ < 10 ms, a jest zupełnie niezauważalny, gdy Δt₁ > 200 ms. Maskowanie w tył  dotyczy sytuacji, gdy sygnał maskujący pojawi się po sygnale maskowanym. Maskowanie w tył jest do pominięcia, gdy Δt2 > 20 ms.  Niesłyszalne są dźwięki słabe, występujące w sąsiedztwie dźwięków mocnych o zbliżonych częstotliwościach – maskowanie w dziedzinie częstotliwości. Wrażliwość na dźwięki zależy również od ich częstotliwości i natężenia. Dźwięki o zbyt małym natężeniu nie są w ogóle słyszalne.  Koder MP3 wykorzystuje wspomniane cechy słuchu. Dzieli sygnał na interwały czasowe, a ponadto pasmo zajmowane przez sygnał dzieli na 32 podpasma. W każdym interwale eliminuje dźwięki o bardzo dużych i bardzo małych częstotliwościach. Ponadto eliminuje dźwięki maskowane (niesłyszalne, albo słabo słyszalne). Dodatkowo dla sygnałów stereofonicznych  koduje się ich różnicę i sumę, a nie każdy kanał osobno. Dzięki temu  uzyskuje się przeciętnie 10-12 krotne zmniejszenie objętości pliku w stosunku do pliku wave.

Kodowanie obrazów nieruchomych
Najpopularniejszym standardem kompresji obrazów nieruchomych (np. zdjęć fotograficznych, rysunków, obrazów graficznych) jest standard JPEG. Jego nazwa pochodzi od akronimu nazwy międzynarodowego zespołu ekspertów (Joint Photographics Experts Group) powołanego przez kilka organizacji międzynarodowych. Wynikiem prac zespołu jest opublikowany w 1991 roku standard JPEG. 
Standard JPEG wyróżnia dwa tryby kodowania: bezstratny i stratny. Tryb bezstratny polega na kodowaniu predykcyjnym DPCM oraz wykorzystywaniu kodu Huffmana albo kodu arytmetycznego. W trybie bezstratnym uzyskuje się średnio stopień kompresji 2. Tryb stratny pozwala osiągnąć dużo wyższy średni stopień kompresji 10÷20 razy. Opiera się on na wykorzystaniu dyskretnej transformaty kosinusowej DCT (Discrate Cosinus Transform), zróżnicowanym kodowaniu jej współczynników, a następnie, tak jak w trybie bezstratnym, użyciu jednej z metod kodowania bezstratnego. 
Obraz źródłowy to zbiór, tak zwanych pikseli równomiernie rozmieszczonych w przestrzeni dwuwymiarowej Piksel to najmniejszy element cząstkowy obrazu. Każdy piksel jest określany za pomocą zestawu komponentów. Mogą to być różne komponenty. Najczęściej stosuje się dwa następujące zestawy komponentów:

• zestaw kolorów podstawowych RGB (czerwony-Red, zielony-Green i niebieski-Blue);
• Jasność, barwa i nasycenie (luminancja i chrominancja).

W koderze JPEG obraz źródłowy jest dzielony na bloki o wymiarze 8x8 pikseli, które podlegają kodowaniu kompresyjnemu. Dla każdego bloku i każdego komponentu osobno jest obliczana 64 punktowa transformata DCT. W wyniku wykonanych obliczeń dla każdego bloku i każdego komponentu otrzymujemy 64 współczynniki transformaty (liczby rzeczywiste). Współczynniki DCT są następnie kwantowane. Najczęściej po kwantowaniu wiele współczynników ma wartość zerową, dzięki czemu stosując jedną z metod kodowania bezstratnego uzyskuje się duży stopień kompresji. W koderze JPEG obraz źródłowy jest dzielony na bloki o wymiarze 8x8 pikseli, które podlegają kodowaniu. W koderze JPEG obraz źródłowy jest dzielony na bloki o wymiarze 8x8 pikseli, które podlegają kodowaniu kompresyjnemu. Dla każdego bloku i każdego komponentu osobno jest obliczana 64 punktowa transformata DCT. W wyniku wykonanych obliczeń dla każdego bloku i każdego komponentu otrzymujemy 64 współczynniki transformaty (liczby rzeczywiste). Współczynniki DCT są następnie kwantowane. Najczęściej po kwantowaniu wiele współczynników ma wartość zerową, dzięki czemu stosując jedną z metod kodowania bezstratnego uzyskuje się duży stopień kompresji.

Kodowanie obrazów ruchomych
Kompresja obrazów ruchomych opiera się na:

• zmniejszeniu rozdzielczości obrazu: format CIF (4:1), format QCIF (16:1).
• zmniejszeniu częstotliwości próbkowania;
• zmniejszeniu liczby poziomów kwantyzacji;
• zmniejszeniu częstotliwości ramkowania (zmniejszeniu liczby klatek w czasie);
• kompresji obrazu w ramce;
• redukcji informacji z ramki na ramkę;
• estymacji ruchu.

Jedną z najczęściej stosowanych metod kompresji obrazów ruchomych jest metoda opisana w standardzie MPEG. Podobnie, jak w przypadku standardu JPEG nazwa standardu wywodzi się od akronimu nazwy grupy ekspertów (Moving Picture Experts Group) powołanych do opracowania standardu kompresji obrazów ruchomych. Owocem pracy tej grupy był standard MPEG-1, opracowany już w 1990 roku, a następnie standardy: MPEG-2 (1991), MPEG-4 (1998) i MPEG-7 (2006?). 
Strumień danych MPEG można podzielić na dwie grupy;

• Grupa danych systemowych zawierająca informacje o synchronizacji czasu w celu odpowiedniego ich połączenia w procesie dekodowania.
• Dane skompresowanego obrazu i dźwięku.

Sekwencja wideo składa się z nagłówka, grupy obrazów i znacznika końca sekwencji wideo. Każdy obraz to trzy macierze opisujące składowe luminancji i chrominancji. W procesie kodowania obraz dzieli się na plastry zawierające kolejne makrobloki ułożone z lewej strony na prawą i z góry na dół (rysunek 1.17). Makroblok to macierz 16x16 współczynników luminancji i macierze 8x8 współczynników chrominancji. 

Rys.1.17. Podział obrazu na bloki i makrobloki

W przypadku sekwencji wideo kolejne obrazy najczęściej niewiele się między sobą różnią. Zatem nie ma potrzeby pełnego kodowania każdej klatki (obrazu). Różnice pomiędzy obrazami dotyczą zwykle występujących na nich obiektach ruchomych. Chcąc zminimalizować ilość informacji należy wyznaczyć kierunek ruchu obiektów w obrazie, skompensować ten ruch, a następnie zakodować różnicę między obrazami punkt po punkcie. Wyznaczanie ruchu obiektów jest dokonywane na bazie makrobloków. Dla każdego makrobloku w obrazie aktualnym jest poszukiwany najbardziej podobny do niego makroblok w obrazie poprzednim. Informacja o kierunku ruchu makrobloku (wektor ruchu) jest przesyłana do dekodera. W koderze makrobloki koduje się korzystają z metod predykcyjnych. Jeżeli kierunek ruchu jest poprawnie określony to kodowanie błędu predykcji wymaga mniejszej liczby bitów niż kodowanie oryginalnego obrazu. Wyróżnia się trzy typy obrazów: 

•     obrazy wewnętrzne (I) zakodowane z wykorzystaniem informacji zawartych tylko w nich samych;
•     obrazy prognozowane (P), zakodowane z wykorzystaniem informacji o najbliższym poprzednim obrazie I albo P. Jest to, tak zwane przewidywanie wprzód (obrazuje je rysunek 1.18);
•     obrazy dwukierunkowo prognozowane (B), to znaczy takie, których kodowanie wykorzystuje obrazy będące zarówno poprzedzające jak i następujące po obrazie B (rysunek 1.18). Obrazów B nie używa się nigdy jako obrazy odniesienia. Takie dwukierunkowe przewidywanie umożliwia bardzo wydajną kompresję bez powielania (propagacji) błędów, które może mieć miejsce w przypadku wykorzystywania obrazów P. Obrazy B odtwarza się poprzez interpolację danych z dwóch sąsiednich obrazów typu I lub P (jednego poprzedzającego i jednego następującego).

Średni stopień kompresji w standardach MPEG wynosi od kilkudziesięciu do stu razy. Oprócz kodeków MPEG stosowane są inne standardy, np. H.263.  

Rys.1.18. Prognozowanie obrazów

Kodowanie bezstratne
W cyfrowych systemach telekomunikacyjnych, a także w systemach gromadzenia danych z oczywistych powodów zależy nam na tym, by dane miały jak najmniejszą „objętość”. Każde zdarzenie elementarne (wiadomość elementarna) należące do pewnego zbioru zdarzeń elementarnych (np. cyfry od 0 do 9, litery alfabetu polskiego) przed wysłaniem albo zapisaniem w pamięci jest przedstawiane w postaci dokładnie określonej sekwencji bitów, nazywanej słowem kodowym. Operacja ta nazywana jest kodowaniem. Słowo kodowe może składać się z mniejszej bądź większej liczby bitów. Zależy nam na tym, by wiadomość składająca się z sekwencji zdarzeń elementarnych liczyła jak najmniej bitów (miała jak najmniejszą objętość), ale także na tym, by odbierana albo odczytana wiadomość była dokładnie taka sam, jak wiadomość nadana. Różnica może być spowodowana dwiema przyczynami. Pierwsza przyczyna to przekłamania strumienia bitów, np. przekłamania spowodowane zakłóceniami, zaś druga to niewłaściwe wybranie słów kodowych. Sposobami zabezpieczania się przed błędami spowodowanymi przekłamaniami bitów zajmiemy się dalej. Tu przyjmijmy, że tego typu błędy nie występują. Zatem skąd mogą brać się niezgodności między wiadomościami odebranymi a nadanymi? Wyjaśnimy to na prostym przykładzie. Załóżmy, że zbiór wiadomości elementarnych składa się z cyfr od 0 do 3. Następnie przyjmijmy, że wiadomości elementarne są kodowane następująco: 0, 00, 01 i 10. Tego typu kod jest nazywany kodem nieosobliwym, ponieważ każdej wiadomości jest w sposób jednoznaczny przypisane słowo kodowe. Jeżeli byłaby nadawana następująca wiadomość: 0132 to reprezentujący ją strumień bitów miałby postać: 0001001. Odbiornik nie zna przesyłanej mu wiadomości, a jedynie przesłany strumień bitów, który jest w nim konwertowany (dekodowany) na wiadomości elementarne. Dekodowanie może dać jednak kilka różnych rezultatów - wiadomość odebrana to 00032, 0132, 1202, 1032 albo 00202, podczas gdy wiadomość nadana odpowiada drugiemu z wyników dekodowania. Widzimy, że zastosowanie kodu nieosobliwego nie jest warunkiem wystarczającym by jednoznacznie i poprawnie zdekodować odebraną sekwencję bitów. Jeżeli jednak dobralibyśmy słowa kodowe w taki sposób, by początek żadnego z nich nie stanowił innego słowa kodowego, to błędne dekodowanie nie występowałoby. Kody mające tę właściwość należą do klasy kodów prefiksowych. W podanym przykładzie warunek ten nie był spełniony, ponieważ słowo kodowe 0 występowało na początku dwóch innych słów kodowych (00 i 01), a więc ten kod nie był kodem prefiksowym, ale był kodem nieosobliwym. Przyjęcie następujących słów kodowych 00, 01, 10 i 11, odpowiednio dla wiadomości elementarnych 0, 1, 2 i 3 nie spowoduje wieloznaczności przy dekodowaniu wiadomości, ponieważ zaproponowany kod jest nie tylko kodem nieosobliwym, ale także kodem prefiksowym. Kod prefiksowy nie musi charakteryzować się słowami kodowymi o jednakowej długości. 
Powróćmy do zagadnienia minimalizacji liczby bitów reprezentujących wiadomość. Przypomnijmy, że entropia określa graniczną minimalną średnią liczbę bitów słów kodowych wiadomości elementarnych należących do pewnego zbioru wiadomości elementarnych. Kod, dla którego średnia długość słowa kodowego jest równa entropii nazywa się kodem optymalnym. W tym miejscu zdefiniujmy pojęcie efektywności kodu. Jeżeli przez Lśr oznaczymy średnią długość słowa kodowego danego kodu, to efektywność kodu E wyraża się następującą zależnością:
                              $E=\frac{H}{L_{śr}}$

Kod optymalny to kod cechujący się efektywnością równą 100 %. Problem znalezienia kodu optymalnego a zarazem prefiksowego został rozwiązany i od nazwiska autora nazywany jest kodem Huffmana. Aby znaleźć kod Huffmana dla danego zbioru wiadomości elementarnych niezbędna jest wiedza o prawdopodobieństwach występowania tych zdarzeń w wiadomości, którą mamy przesłać. Prawdopodobieństwa te można wyznaczyć na podstawie samej wiadomości. Na przykład, gdy chcielibyśmy przesłać tekst Trylogii H. Sienkiewicza należałoby najpierw obliczyć częstość występowania w niej każdego ze znaków alfabetu, a następnie przystąpić do znalezienia kodu Huffmana. Takie postępowanie jest możliwe, ale niepraktyczne, szczególnie w przypadku systemów teletransmisyjnych. W przypadku przesyłania plików tekstowych napisanych w danym języku można posłużyć się prawdopodobieństwami występowania znaków alfabetu obliczonymi dla danego języka, a nie obliczonymi na podstawie wiadomości. Jeżeli przesyłany tekst jest długi to różnica pomiędzy prawdopodobieństwami obliczonymi dwiema metodami nie będzie duża. Jako ciekawostkę podajmy, że średnia autoinformacja na literę w języku polskim wynosi 1,5 bita. Niestety kod Huffmana zastosowany do tekstów nie będzie dobry w przypadku innych plików. Aby prawidłowo zdekodować odebraną wiadomość dekoder musi znać używany w koderze kod Huffmana. Najogólniej możliwe są trzy sposoby postępowania. Pierwszy, polega na ustaleniu jednego kodu znanego koderowi i dekoderowi. Drugi sposób wymaga przesłaniu na początku transmisji każdej nowej wiadomości, tak zwanej tabeli kodów. Drugie rozwiązanie daje większe możliwości kompresji, ale tylko wtedy, gdy przesyłany plik jest długi. Jeżeli plik jest krótki to zysk z użycia kodu jest znacznie zmniejszany, ponieważ tabela kodów stanowi relatywnie dużą część przesyłanych bitów. Trzeci sposób opiera się na dynamicznym określaniu tabeli kodów. Mianowicie nadajnik po wysłaniu pewnej porcji bitów, a odbiornik po ich odebraniu, na podstawie informacji zawartych w wiadomości reprezentowanej za pomocą tych bitów, określają według tych samych zasad tabelę kodów, które jest stosowana do przesyłania kolejnej porcji wiadomości. Sposób ten jest najodpowiedniejszy w przypadku przesyłania plików o nieznanych cechach. 
Na zakończenie przedstawimy kolejne kroki algorytmu, według którego wyznacza się słowa kodu Huffmana.

•     Określ prawdopodobieństwa występowania poszczególnych wiadomości elementarnych.
•     Uszereguj wiadomości elementarne według rosnącego prawdopodobieństwa. Każdemu prawdopodobieństwu przypisz punkt nazywany węzłem.
•     Dodaj dwa najmniejsze prawdopodobieństwa i utwórz nowy węzeł. Przypisz mu wynik sumowania. Połącz każdy z dwóch węzłów linią z nowym węzłem. W dalszych rozważaniach pomiń te dwa węzły.
•     Z pozostających węzłów i węzła nowoutworzonego wybierz dwa węzły o najmniejszych prawdopodobieństwach. Utwórz nowy węzeł, przypisz mu prawdopodobieństwo będące wynikiem sumowania prawdopodobieństw tych  dwóch węzłów. Połącz liniami te węzły z nowoutworzonym węzłem. W dalszych rozważaniach pomiń te dwa węzły.
•     Jeżeli pozostał Ci tylko jeden węzeł przejdź dalej, jeżeli więcej to powróć do punktu 4 algorytmu.
•     Wszystkim liniom dolnym odchodzącym od węzła przypisz cyfrę 1 a liniom górnym 0, albo odwrotnie.
•     Słowo kodowe odpowiadające danej wiadomości elementarnej składa z sekwencji bitów przypisanych kolejnym liniom, poczynając od ostatnio utworzonego węzła, a kończąc na węźle odpowiadającym wiadomości elementarnej, albo odwrotnie.

Z przedstawionego przykładu wynika, że algorytm tworzenia słów kodowych nie prowadzi do jednoznacznego rezultatu. Możliwe jest otrzymanie różnych wyników. Oznacza to, że kod Huffmana nie jest deterministyczny. Jednak posługując się algorytmem zawsze otrzymamy taką samą średnią liczbę bitów na wiadomość elementarną, niezależnie od wyniku kodowania. 
Warto jednak wiedzieć, że zbiór wiadomości elementarnych może być tworzony w różny sposób. W przykładzie  za wiadomość elementarną przyjęliśmy pojedyncze litery. Jednak nic nie stoi na przeszkodzie, by za wiadomość elementarną przyjmować, np. sekwencje dwuliterowe (ogólniej wieloliterowe), utworzone z zbioru jednoliterowych wiadomości elementarnych. Jeżeli dla nowego zbioru takich wiadomości elementarnych zastosujemy kod Huffmana to może okazać się, że przesłanie wiadomości wymagać będzie mniejszej liczby bitów, niż gdy wiadomości elementarne są jednoliterowe. Zysk jest jednak okupiony znaczną komplikacją drzewa kodowego i koniecznością wyznaczenia prawdopodobieństw wiadomości elementarnych.