Co to jest kod natychmiastowy? Podaj przykłady.
Mówiąc krotko kod natychmiastowy to taki kod który możemy odczytać znak po znaku I mamy pewność, że do tego momentu do którego odczytaliśmy treść nie ma żadnych dwuznacznych możliwości tekstów zdekodowanych.
Link do wykładu 7 z Teorii Informacji - http://fol.cba.pl/w7.html , w wykładzie znajduje się sporo informacji na temat kodu natychmiastowego. Patrz na:
Warunek konieczny I dostateczny na istnienie kodu natychmiastowego
Konstruowanie kodu natychmiastowego:
Zajmiemy się teraz konstrukcjami dwójkowymi kodów natychmiastowych. W tym celu ustalmy alfabet A={a1, a2, a3, …, an}. Chcemy zeby kod miał jak najkrótsze słowa kodowe. Będziemy też szukać zależności poiędzy długościami słów kodowych. Dla litery ai, długość jej kodu oznaczymy przez di. Możemy założyć, że d1 < d2 < d3 < … < dn. Nasza konstrukcja przebiega nastepująco:
1) Za K(a1) wybieramy jakiekolwiek słowo dwójkowe długości d1. Jest to możliwe jeśli d1 >= 1. Mamy wówczas możliwośc wyboru spośród 2^d1 słów. Dodatkowo zachodzi nierównośc 2^(-d) <= 1.
2) Wśród wszystkich słów, które nie zaczynają się od K(a1), wybieramy słowo K(a2) długości d2. Zauważmy, że wybór jest możliwy ponieważ mamy 2^d2 wszystkich słów długości d2 I 2^(d2-d1) słów długości d2, których początkiem jest K(a1). Jeśli więc 2^d2 > 2^(d2 – d1), to mamy przynajmniej jeden wybów K(a2). Nierównośc ta zachodzi, ponieważ d1 > 0. Dodatkowo mamy jeszcze 2^(-d1) + 2^(-d2) <= 1.
3) Pobodnie jak w 2) sposód wszystkich słów, które się nie zaczynają od K(a1) ani od K(a2) wybieramy słowo K(a3) długości d3. Aby wybór był możliwy musi być spełniona nierówność 2^d3 > 2^(d3 - d1) > 2^(d3 – d2), która jest równoważna dla nierówności:
2^(-d1) + 2^(-d2) + 2^(-d3) <= 1
4) Postępujemy jak w punkcie 3) wybierając kolejno K(a4), K(a5), …. , K(an). Aby wybór słowa K(ai) był możliwy musi zachodzić nierówność
2^(-d1) + 2^(-d2) + … + 2^(-di) <= 1
Zatem aby można było wybrać słowa K(a1), K(a2), … , K(an), ich długości muszą spełniać warunek :
2^(-d1) + 2^(-d2) + … + 2^(-di) <= 1
Otrzymaną nierównośc nazywamy nierównością Krafta dla kodu dwójkowgo.
Źróło: http://wmf.univ.szczecin.pl/~szkibiel/kody/2kraft.pdf , Rozdział 2.1 Konstruowanie kodów natychmiastowych.