Na początek wykładu powiemy sobie o dwóch podstawowych pojęciach - kod i kodowanie. Kodem nazywamy wiadomość tekstową, lub cyfrową przekształconą za pomocą określonego algorytmu do innej postaci. Kodowanie to czynność polegająca na przekształceniu tekstu za pomocą jakiegoś algorytmu do innej postaci. Odczyt tej informacji nazywamy dekodowaniem. Aby informacja była zrozumiała, odbiorca musi znać algorytm, w jakim nadawca zaszyfrował daną wiadomość. Bardzo często uzywa się kodów i kodowania, by zataić jakąś informację w taki sposób, by była ona dostepna dla odbiorcy i nadawcy i nie była dostepna dla osób trzecich. Postać pierwotna zawsze składać się musi z liter alfabetu łacińskiego, oraz ewentualnie cyfr. I teraz przykłady kodów. Pierwszym takim najbardziej znanym kodem jest alfabet Morse'a widoczny na ilustracji poniżej:

Kod ten został stworzony w 1832 przez wynalazcę telegrafu Samuela Morse'a. Jest to kod naśladujący alfabet (sposób reprezentacji znaków alfabetu łacińskiego za pomocą impulsów elektrycznych). Wszystkie znaki reprezentowane są przez kilkuelementowe serie sygnałów - krótkich (kropek) i długich (kresek). Kreska powinna trwać co najmniej tyle czasu, co trzy kropki. Odstęp pomiędzy elementami znaku powinien trwać jedną kropkę. Odstęp pomiędzy poszczególnymi znakami - jedną kreskę. Odstęp pomiędzy grupami znaków - trzy kreski. Służy on najczęściej do korespondencji wojskowej i jest przesyłany i odbierany telegraficznie. Kolejny z kodów to kod flagowy zwany inaczej kodem. Do sygnalizacji w żegludze stosuje się Międzynarodowy Kod Sygnałowy (MKS) zatwierdzony przez Międzynarodową Morską Organizację Doradczą (IMCO) w Londynie 1 kwietnia 1969. MKS jest zbiorem podstawowych komunikatów zakodowanych w sygnałach jedno, dwu i trzyliterowych, umożliwia również przekazywanie wiadomości litera po literze.

• Sygnały jednoliterowe służą do przekazywania wiadomości pilnych, ważnych, często używanych.

• Sygnały dwuliterowe dotyczą typowych (w żegludze) sytuacji dotyczących bezpieczeństwa ludzi i statków.

• Sygnały trzyliterowe zarezerwowane są dla spraw medycznych i pomocy lekarskiej.

Ustalone, znane powszechnie kody umożliwiają precyzyjną komunikację niezależnie od umiejętności językowych rozmówców. Krótkie kody umożliwiają szybkie przekazywanie wiadomości za pomocą najprostszych metod. Sygnalizację można prowadzić przy pomocy ruchów rąk (semaforem), głosu, światła, radia, telegrafu lub flag sygnałowych. Obecnie, ze względu na upowszechnienie komunikacji radiotelefonicznej UKF, używany bardzo rzadko. Oto flagowe odpowiedniki liter i cyfr:

Kolejny z kodów to kod Baudot. Jest to zestaw znaków używanych w dalekopisach, pierwowzór kodów EBCDIC oraz ASCII. Oryginalny kod Baudot powstał około roku 1874 i znany jest jako International Telegraph Alphabet No 1 (ITA1), i nie był już więcej używany. Około roku 1901 kod Baudot został zmodyfikowany przez Donalda Murraya. Kolejne modyfikacje zrobił Western Union. Od tego czasu kod Baudot nosi nazwę International Telegraph Alphabet No 2 (ITA2). ITA2 jest wciąż używany między innymi w telekomunikacyjnych urządzeniach dla głuchoniemych TDD i w krótkofalarstwie jako RTTY. Oto jego postać:

Kolejny z kodów (chyba najpopularniejszy) to kod ASCII. Jest to siedmiobitowy kod przyporządkowujący liczby z zakresu 0 - 127 literom (alfabetu angielskiego), cyfrom, znakom przestankowym i innym symbolom oraz poleceniom sterującym. Przykładowo litera a jest kodowana liczbą 97, a polecenie powrót karetki - liczbą 13. Litery, cyfry oraz inne znaki drukowane tworzą zbiór znaków ASCII. Jest to 95 znaków o kodach 32-126. Pozostałe 33 kody (0-31 i 127) to tzw. kody sterujące służące do sterowania urządzeniem odbierającym komunikat, np. drukarką czy terminalem. Ponieważ kod ASCII jest siedmiobitowy, a większość komputerów operuje na ośmiobitowych bajtach, dodatkowy bit można wykorzystać na powiększenie zbioru kodowanych znaków. Powstało wiele różnych rozszerzeń ASCII wykorzystujących ósmy bit (np. norma ISO 8859, rozszerzenia firm IBM lub Microsoft), nazywanych stronami kodowymi. Również kodowanie UTF-8 można uważać za rozszerzenie ASCII, tutaj jednak dodatkowe znaki są kodowane na 2 i więcej bajtach. Oto jak wygląda tablica tych znaków podstawowych:

I to były podstawowe kody. Teraz natomiast nieco formalizmów. Zaczniemy od kodowania binarnego. Przypuśćmy, że mamy alfabet wejściowy A składający się z samych małych liter alfabetu łacińskiego, oraz alfabet wyjściowy B składający się z cyfr 0 i 1. Przyporządkujmy każdej z liter alfabetu A cyfrę wyznaczającą pozycję danej litery w tym alfabecie, czyli niech a będzie 1, b - 2, c - 3 i tak dalej . Załóżmy, że mamy zakodować słowo ala binarnie. Litera a będzie na pozycji pierwszej, a litera l na pozycji 12 (oczywiście nie liczymy polskich znaków). Słowo kodowe, czyli nasze słowo w postaci zakodowanej będzie miało postać: 0001 1100 0001, bo najpierw znaleźliśmy pozycje liter naszego słowa w alfabecie A, a następnie te pozycje przekonwertowaliśmy do postaci kodu binarnego. Kolejna rzecz to kodowanie blokowe. Kod blokowy to kod korekcyjny, najczęściej symetryczny, który potrafi zaszyfrować blok danych o określonej długości. Kody blokowe najczęściej określa się symbolem (n, k) - gdzie n określa długość słowa kodowego, a k długość części informacyjnej. Kody te służą do szybkiego wykrycia i korekcji błędów występujących podczas przesyłu danych cyfrowych. Informacje dzielone są w tych kodach na bloki, do których dołączana jest nadmiarowa część kodowa pozwalająca na detekcję błędów występujących w blokach oraz korekcję - w zależności od sposobu zaprojektowania kanału transmisji ponowne pobranie całego bloku lub dokonanie automatycznej korekcji.

Szyfr określa para funkcji pobierających 2 argumenty:

• Funkcja szyfrująca pobierająca klucz i wiadomość, a zwracająca szyfrogram C = E_K(M)

• Funkcja deszyfrująca pobierająca klucz i szyfrogram, a zwracająca wiadomość M = D_K(C)

Typowe rozmiary bloku oraz kluczy (te dwa rozmiary nie muszą być identyczne) to 64, 128, 192 lub 256 bitów, przy czym klucze mniejsze od 128 bitów nie zapewniają współcześnie bezpieczeństwa. Ponieważ wiadomości jakie chcemy zakodować są zwykle znacznie większe od rozmiaru bloku, musimy używać jakiegoś trybu kodowania. Nastepne pojęcia to kodowanie o stałej długości słowa, o zmiennej długości słowa i kodowanie jednoznaczne. To pierwsze pojęcie oznacza, że każde słowo kodowe ma tę samą długość. Przykładowo binarnie słowo A to 0001, a słowo B to 0010. Kolejne słowo musi mieć zatem cztery bity i nie może być ani dłuższe ani krótsze. W kodowaniu o zmiennej długości słowa jest inaczej. Tu jedno słowo może mieć postać binarną 0001, a drugie na przykład 100. O kodowaniu jednoznacznym mówimy, gdy po zakodowaniu słowa x do postaci y można je odkodować tylko na jeden sposób, uzyskując x. Warunek jednoznaczności kodu o stałej długości brzmi, że dla każdych dwóch liter a Ⴙ b wystarczy K(a) Ⴙ K(b(. Z kolei warunek jednoznaczność kodu o zmiennej długości brzmi nastepująco. Niech:

Znak	K(znak)
a	0
b	00
c	11

Wówczas ciąg 00 można odkodować jako aa lub b, mimo, że wszystkie słowa kodowe są różne. Skąd wynika problem: Słowo kodowe K(a) = 0 jest prefiksem słowa kodowego K(b) = 00. O kodzie prefiksowym mówimy wtedy, gdy dla każdych a Ⴙ b zachodzi, że K(a) nie jest prefiksem K(b). Teraz czy dla jednoznaczności wystarczy, że kod jest prefiksowy? Owszem, ponieważ:

• Kod prefiksowy można reprezentować w postaci drzewa, z krawędziami etykietowanymi 0 lub 1, a liście odpowiadają literom alfabetu.

• Gdy dekodujemy, przechodzimy przez drzewo od korzenia do liścia, a po odkodowaniu litery znowu przechodzimy do korzenia. I tak dalej.

Popatrzmy na przykładzie, jak wygląda takie kodowanie prefiksowe. Niech:

znak	K(znak)
A	0
B	10
C	110
D	111

Zdekodujmy ciąg 100110101101110. Z powyższego schematu będziemy mieli ciąg BACBCDA. Kolejne pytanie, jakie się nasuwa, to czy dla jednoznaczności jest konieczne, aby kod był prefiksowy (przedrostkowy)? Otóż nie. Załóżmy, że mamy taki przykład:

znak	K(znak)
A	0
B	01

Ten kod jest jednoznaczny (a nie jest prefiksowy), ponieważ:

• Pojawienie się jedynki zawsze oznacza koniec słowa kodowego kodującego B!

• 0 na końcu lub przed innym zerem oznacza literę A.

Przy okazji kodu prefiksowego bardzo często mówi się o nierówności Krafta. Ta nierównośc pozwala nam obliczyć długości słów kodowych. Nierówność ta jest warunkiem, który musi spełniać kod, aby był jednoznacznie dekodowalny bez opóźnienia. Jest to warunek konieczny, ale nie wystarczający, tak więc istnieją kody które spełniają tą nierówność, lecz nie są jednoznacznie dekodowalne bez opóźnienia. Oto wzór tej nierówności:

gdzie: r - wartościowość kodu, K - liczba sygnałów elementarnych, l_i - długość i-tego sygnału elementarnego. Oto przykład.

	kod	kod	kod
a1	00	0	0
a2	01	100	10
a3	10	110	110
a4	11	11	11

Mamy w naszym przypadku dla wszystkich kodów r = 2, gdyż zastosowaliśmy wszędzie kod binarny, natomiast K = 4, gdyż nasze kody mają czteroelementowy alfabet wiadomość a₁, a₂, a₃, a₄. Obliczając lewą stronę nierówności dla kodu
, otrzymujemy 1, więc nierówność jest spełniona. Dodatkowo widzimy, że ma on wszystkie ciągi kodowe o stałej długości i do tego każdy z nich jest inny. Na tej podstawie wnioskujemy, że jest to kod jednoznacznie dekodowalny, bez opóźnienia. Dla kodu
lewa strona wynosi 1, więc ponownie spełniona jest nierówność Krafta-McMillana, lecz widzimy, że czwarte słowo kodowe jest przedrostkiem słowa trzeciego, co eliminuje go z naszych rozważań.Natomiast dla kodu
lewa strona wynosi 9/8, czyli nierówność nie jest spełniona, możemy więc jednoznacznie określić, że nie jest to kod jednoznacznie dekodowalny bez opóźnienia.

Teraz przejdźmy natomiast do kolejnego tematu, a mianowicie do kompresji. Kompresja danych polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru, nie zmieniając przenoszonych informacji. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów. Działaniem przeciwnym do kompresji jest dekompresja. Kompresja dzieli się na bezstratną - w której z postaci skompresowanej można odzyskać identyczną postać pierwotną, oraz stratną - w której takie odzyskanie jest niemożliwe. Do kompresji najczęściej wykorzystuje się metodę Shannona i metodę Eliasa. Natomiast my na koniec wykładów omówimy jedynie metodę Eliasa. Najbardziej znany jest algorytm gamma. Ma stosunkowo dobry współczynnik kompresji dla danych, w których prawdopodobieństwo wystąpienia jest coraz mniejsze dla kolejnych symboli alfabety. Jest nieco trudniejszy w obliczaniu niż kody unarny czy binarny, a także dla rozkładu równomiernego otrzymujemy ekspansję danych. Stosuje się go gdy prawdopodobieństwo wystąpienia symboli maleje wraz z kolejnością w alfabecie. Służy on do kodowania dodatnich liczb całkowitych. Ponadto ich zaletą jest to, że nie wymagają oznaczenia końca kodu. Wiele liczb możemy zakodować i połączyć w jeden ciąg. Jest on zawsze jednoznaczny. Algorytm ten przedstawia się nastepująco:

1. Zapisz kodowaną liczbę binarnie. Policz ile ma bitów. Oznacz tę      liczbę jako N.
2. Przed liczbą zapisaną binarnie dopisz N-1 zer.

        Jest to bardzo prosty algorytm. A oto początek kodu: 

1	1	7	00111	13	0001101
2	010	8	0001000	14	0001110
3	011	9	0001001	15	0001111
4	00100	10	0001010	16	000010000
5	00101	11	0001011	17	000010001
6	00110	12	0001100	18	000010010

        Algorytm dekodowania jest również bardzo prosty:

1. Policz wszystkie zera aż do znalezienia pierwszej jedynki. Liczba zer niech równa się N.
2. Odczytaj N+1 pozostałych bitów kodu. Jest to zdekodowana liczba.

       Kod ten jest bardzo dobry dla niewielkich liczb. Koduje on liczbę x na [2log2x+1] bitach. Używany jest w aplikacjach, w których największa z kodowanych liczb nie jest znana, aż do zakończenia procesu, a także do kompresji danych, w których małe wartości znacznie częściej występują niż duże. Gdy zwiększa sią częstotliwość występowania dużych liczb, lepszym okazuje się kodowanie typu delta.

D

C

B

A

1

1

1

0

0

0

---