Kodowanie arytmetyczne

– metoda

kodowania źródłowego

dyskretnych źródeł

sygnałów

, stosowana

jako jeden z systemów w

bezstratnej kompresji

danych. Została wynaleziona przez

Petera

Eliasa

około

1960

roku.

Ideą tego

kodu

jest przedstawienie ciągu wiadomości jako podprzedziału

przedziału jednostkowego [0,1) wyznaczonego

rekursywnie

na

podstawie

prawdopodobieństw

wystąpienia tychże wiadomości generowanych przez źródło. Ciąg

kodowy reprezentujący kodowane wiadomości jest

binarnym

zapisem wartości z wyznaczonego w ten

sposób przedziału.

Dany jest zbiór symboli

oraz stowarzyszony z nim zbiór

prawdopodobieństw

. Jeden z symboli jest wyróżniony – jego wystąpienie

oznacza koniec komunikatu, co zapobiega wystąpieniu niejednoznaczności; ewentualnie zamiast
wprowadzenia dodatkowego symbolu można przesyłać długość kodowanego ciągu.

Na początku dany jest przedział

, który dzielony jest na podprzedziały o szerokościach

równych kolejnym prawdopodobieństwom

, czy

li otrzymywany jest ciąg

podprzedziałów

. Kolejnym podprzedziałom (ozn.

) odpowiadają symbole ze zbioru .

Koder arytmetyczny
1.Inicjalizacja:
Utw

órz tablicę prawdopodobieństw; rejestry: BOTTOM=0…02, TOP=1…12; licznik C=0;

2.Pobierz symbol sji modyfikuj granice przedzia

łu wg zależności:

BOTTOMi+1=BOTTOMi+(TOPi-BOTTOM i+1)bj
TOPi+1=BOTTOMi+(TOPi-BOTTOMi+1)tj

3.Korekcja rejestrów TOPi BOTTOM
a) dopóki tn-1=bn-1
wy

ślij tn-1;

je

śli C 0 wyślij zanegowany tn-1; C=C-1;

asl(TOP); t0=12; asl(BOTTOM); b0=02;
b) dopóki (tn-1tn-2=102oraz bn-1bn-2=012)
tn-1tn-2=012; bn-1bn-2=102;
asl(TOP); t0=12; asl(BOTTOM); b0=02;
C=C+1;

4.Id

ź do punktu 2 jeśli są jeszcze dane do zakodowania.

5.Wyślij wszystkie znaczące cyfry z rejestru BOTTOM

Kodowanie Shannona-Fano

– metoda

kompresji bezstratnej

autorstwa Roberta Fano. Kodowanie to

dla dyskretnego źródła danych znajduje

kod prefiksowy

, który charakteryzuje się dość dobrą

efektywnością

Algor

ytm przedstawia się następująco:

1. s

– ciąg symboli ze zbioru posortowanych wg prawdopodobieństw

2. Shannon-Fano(s):



Jeśli s zawiera dwa symbole, do słowa kodu pierwszej litery dodaj 1, do słowa kodu

drugiej litery

– 0.



W przeciwnym razie, jeśli s zawiera więcej niż dwa symbole, podziel go na dwa

podciągi s1 i s2 tak, żeby różnica między sumą prawdopodobieństw liter z s1 i s2 była

najmniejsza. Do słów kodu symboli z s1 dodaj 0, do kodów symboli z s2 – 1. Wywołaj

rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

Kodowanie Huffmana (

ang.

Huffman coding)

– jedna z najprostszych i łatwych

w

implementacji

metod

kompresji bezstratnej

. Została opracowana w

1952

roku przez

Amerykanina

Davida Huffmana

.

Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej

kompresji danych

Dany

jest alfabet źródłowy (zbiór symboli)

oraz zbiór stowarzyszonych z nim

prawdopodobieństw

. Symbolami są najczęściej

bajty

, choć nie ma żadnych

przeszkód żeby było nimi coś innego (np. pary znaków). Prawdopodobieństwa mogą zostać z góry
określone dla danego zestawu danych, np. poprzez wyznaczenie częstotliwości występowania
znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego
zestawu danych.

Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest
odwrotnie proporcjonalna do prawdopodobieństwa

. Tzn. im częściej dany symbol występuje (może

wystąpić) w ciągu danych, tym mniej zajmie bitów.

Własności kodu Huffmana są następujące:



jest

kodem prefiksowym

; oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa;



średnia długość słowa kodowego jest najmniejsza spośród kodów prefiksowych;



jeśli prawdopodobieństwa są różne, tzn.

, to długość kodu dla symbolu

jest nie

większa od kodu dla symbolu

;



słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość.

Kompresja polega na zastąpieniu symboli otrzymanymi kodami.

LZW

W pojedynczym kroku algorytmu wyszukiwany jest w słowniku najdłuższy prefiks niezakodowanych
jeszcze danych. Na wyjście wypisywany jest wówczas kod związany z tym słowem, zaś do słownika
dodawana nowa pozycja:

konkatenacja

słowa i pierwszej niedopasowanej litery.

Algorytm przebiega następująco:

1.

Wypełnij słownik alfabetem źródła informacji.

2. c :=

pierwszy symbol wejściowy

3.

Dopóki są dane na wejściu:



Wczytaj znak s.



Jeżeli ciąg c + s znajduje się w słowniku, przedłuż ciąg c, tj. c := c + s



Jeśli ciągu c + s nie ma w słowniku, wówczas:



wypisz kod dla c (c

znajduje się w słowniku)



dodaj ciąg c + s do słownika



przypisz c := s.

4.

Na końcu wypisz na wyjście kod związany c.

O efektywności kompresji w dość dużym stopniu decyduje sposób zapisu kodów (liczb).

Entropia (

średnia ilość informacji przypadająca na symbol)

Odległość Hammingad(u,v) dwóch słów kodowych —liczba elementów słów, które się różnią

Kod z minimalną odległością Dminmoże wykryć Dmin-1 błędów i poprawić (Dmin-1)/2 lub Dmin/2-1

Kody cykliczne
Algorytm systematyczny
V(x)=W(x)G(x)
Chcemy mieć postać
V(x)=xn-kM(x)+B(x)
W(x)G(x)= xn-kM(x)+B(x)
W(x)G(x)-B(x)= xn-kM(x)
W(x)-B(x)/G(x)= xn-kM(x)/G(x)

B(x) jest reszt

ą z dzielenia xn-kM(x)/G(x)

Wiadomo

ść W(x) = w0+ w1x + … + wk-1xk-1

Krok 1: Wr(x) = W(x)xn-k
Krok 2: B(x) = Wr(x) (mod(G(x))
Krok 3: V(x) = B(x) + Wr(x).
Wyjście: wielomian kodowy V(x)