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 , czyli 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ą 

Algorytm 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)