Na ostatnich zajęciach była mowa o kodowaniu bezstratnym i powiedzieliśmy o trzech metodach - Huffmana, arytmetyczne, oraz słownikowe. Te dwie pierwsze metody oparte są na zliczniu częstości wystapienia pewnych danych, natomiast ostatnia metoda odbiega od tej zasady. Dziś skupimy się na metodach kodowania nadmiarowego. Metody kodowania nadmiarowego polegają na tym, że do wiadomości dodawane są dodatkowe symbole, dzięki którym można stwierdzić, czy i w którym miejscu w wiadomości wystąpił błąd. Jedna z tych metod to kontrola parzystości. Jest to metoda sprawdzania błędów powstających podczas transmisji i zapisu danych. Dla każdej grupy bitów (zwykle jest to jeden bajt) komputer sprawdza liczbę bitów o wartości 1. Efektem tego jest informacja, że w danej porcji bitów znajduje się parzysta lub nieparzysta liczba jedynek. W zależności od tego dodawany jest dodatkowy bit parzystości (sprawdzający) o wartości 0 lub 1 - tak aby liczba jedynek zawsze była nieparzysta. Gdy teraz jeden z wysyłanych bitów zostanie zmieniony (z 0 na 1 albo odwrotnie), zostanie to wykryte. Natomiast w wypadku gdy zmieni się parzysta liczba bitów (dwa lub cztery), nie zostanie to wykryte, lecz przekłamanie dwóch bitów w ośmiobitowej porcji informacji jest bardzo mało prawdopodobne. Bit parzystości jest to zatem jednostka binarna używana przy kontroli parzystości i wyszukiwaniu błędów parzystości. Jest to szczególny przypadek jednobitowego kodu CRC generowanego przez wielomian x + 1. Odwrotnością bitu parzystości jest bit nieparzystości. Bit parzystości dodaje się do słowa binarnego w ten sposób, by liczba jedynek w całym słowie (wraz z bitem parzystości) była zawsze parzysta. Innymi słowy mamy tu do czynienia z bitem dopełnienia do parzystości. Obliczanie dodatkowego bitu można zrealizować poprzez proste drzewo bramek XOR, realizujące operację:

, gdzie n - liczba bitów w słowie

Oto przykład. Słowo 101111012 ma parzystą liczbę jedynek, więc bit parzystości wynosi 0. Słowo z dołączonym bitem parzystości to 1011110102. Słowo 011100112 ma nieparzystą liczbę jedynek, więc bit parzystości wynosi 1. Słowo z dołączonym bitem parzystości to 0111001112.

Kod z pojedynczym bitem parzystości charakteryzuje się odległością Hamminga równą 2, co pozwala na detekcję wszystkich błędów pojedynczych. Obecnie odchodzi się od stosowania tego typu kodów z uwagi na ich niewielkie możliwości. Ich niekwestionowaną zaletą jest prosta budowa, z czym wiąże się niski koszt koderów i detektorów. Teraz powiemy kilka słó na temat CRC i sumy kontrolnej - czym się różnią i co to takiego. Suma kontrolna (ang. checksum) to liczba uzyskana w wyniku sumowania lub wykonania innych operacji matematycznych na przesyłanych danych, przesłana razem z danymi i służąca do sprawdzania poprawności przetwarzanych danych (operacje na binariach). Komputer wysyłający dane liczy sumę kontrolną i dołącza ją do pakietu danych. Komputer odbierający dane liczy również sumę kontrolną z odebranych danych i sprawdza, czy zgadza się suma obliczona przez niego z sumą odebraną z pakietem danych. Jeśli nie, to znaczy, że dane uległy przekłamaniu. Odmianą sumy kontrolnej jest: CRC, Adler-32, Algorytm Luhna, cyfry kontrolne w numerach PESEL, NIP, numerach kont bankowych, bit parzystości stosowany przy transmisji szeregowej łączem RS-232, taśmie dziurkowanej. W tym przypadku liczba jest 1-bitowa, suma, suma bitowa, różnica bitowa stosowana w wielu protokołach transmisji danych. Podobnie danym zapisywanym w sektorze dyskietki dysku towarzyszy suma kontrolna typu CRC. CRC jest więc matematyczną sumą kontrolną wykorzystywaną do wykrywania uszkodzonych danych binarnych. Kod CRC zwykle dodawany jest do ramki lub pakietu w celu późniejszej weryfikacji integralności danych. Jest to algorytm wykrywania błędów bardziej niezawodny niż suma kontrolna, umożliwia również określenie, czy błąd zdarzył się podczas transmisji. Wartość CRC określana jest w sposób bardziej rygorystyczny niż wartość sumy kontrolnej - otrzymuje się ją w wyniku podziału wartości otrzymanej w wyniku odczytania ciągu binarnego przez wcześniej określoną liczbę binarną.

CRC jest resztą z binarnego dzielenia ciągu danych przez relatywnie krótki dzielnik, zwany generatorem lub wielomianem CRC. W praktyce stosuje się najczęściej wielomiany o długości 17 lub 33 bitów, dające odpowiednio wyniki 16 (CRC16) i 32 bitów (CRC32).

Metoda ta jest szeroko wykorzystywana do wykrywania błędów przypadkowych, ale nie nadaje się do ochrony integralności w zastosowaniach kryptograficznych. CRC jest relatywnie łatwe do sfałszowania, a więc jest możliwe takie poprawienie ciągu bitów by dawał on w wyniku poprawne CRC. Przejdźmy teraz do kodów liniowych. Jest to specjalna grupa kodów liniowych umożliwiająca konwersję sygnałów cyfrowych do innej postaci, bardziej przystosowanej do ich przesyłania przez szeregowe łącza cyfrowe, uwzględniającej fizyczne aspekty transmisji. Istnieje wiele liniowych kodów transmisyjnych, takich jak: AMI (styk S-ISDN), 4B/5B i pochodne, Manchester z wieloma modyfikacjami oraz NRZ, NRZI, 2B1Q. Na początek jednak nieco wprowadzenia. Załóżmy, że mamy dane wektory binarne o odległości n na przykład: X = 1101, Y = 0101. Zobaczmy, jak się dodaje modulo 2 wektory binarne:
. Kolejna rzecz to obliczanie wagi wektora binarnego. Jest to nic innego, jak okreslenie liczby jedynek w wektorze. Zatem dla wektora X będzie to liczba 2, a dla Y - 2. No i teraz możemy przejść do kodowania Hamminga, w którym te obliczenia zostaną wykorzystane. Kod Hamminga jest jednym z najprostszych metod detekcji błędów, która umożliwia również ustalenie pozycji błędnych bitów. Metoda kodowania polega na wysyłaniu nadmiarowych informacji zakodowanych tak, że może być ona wykorzystana do zidentyfikowania błędnego bitu. Ma on małe zastosowanie, ponieważ jest dość prymitywny i jego działanie jest dość wąskie. Kod Hamminga (korygujący błąd pojedynczy) wykrywa dowolny błąd pojedynczy oraz wskazuje jego pozycję, co umożliwia stosowną korekcję przez zmianę bitu na przeciwny. Jest to kod korygujący błąd pojedynczy i jest przykładem kodowania FEC (ang. Forward Error Correction). Główna zasada kodowania polega na umieszczaniu bitów nadmiarowych w tych pozycjach wiadomości, których numery wyrażają się przez potęgę liczby 2. Bity nadmiarowe: 2n

Zakodowana informacja jest kombinacją 'I' bitów z bitami informacyjnymi i K bitami nadmiarowymi. Całkowita długość ciągu zakodowanego w kodzie Hamminga wynosi :

K + I przy założeniu że: (2 do potęgi K) - 1 >= K + 1. Bity w kodzie Hamminga numerowane są kolejno zaczynając od prawej strony: I7 I6 I5 K4 I3 K2 K1. Kod korekcyjny Hamminga jest stosowany w tablicach, macierzach dyskowych typu RAID 2 (ang. Redundant Array of Inexpensive Disks). Idea tego urządzenia opiera się na połączeniu maksymalnie pięciu dysków w jeden system, w którym dane zapisywane są na wszystkich dyskach. W swej podstawowej postaci służy do wykrywania i korygowania pojedynczych błędów w ciągach kodowych. Działa w ten sposób, że informacja jest dzielona między kolejne dyski matrycy dyskowej bit po bicie. Towarzyszące bitom danych bity kodu Hamminga pozwalają na poprawianie nie tylko pojedynczych błędów, ale i ich grup, jednak kod Hamminga został uznany jako algorytm zbyt kosztowny w zastosowaniach sieciowych (tańsze okazały się algorytmy zapisu bajt po bajcie na kolejnych dyskach), technika ta jest jeszcze używana jedynie w dużych komputerach. Przy okazji kodu Hamminga mówi się o odległości Hamminga. W teorii informacji jest to wprowadzona przez Richarda Hamminga miara odmienności dwóch ciągów o takiej samej długości, wyrażająca liczbę miejsc (pozycji), na których te dwa ciągi się różnią. Innymi słowy jest to najmniejsza liczba zmian (operacji zastępowania elementu innym), jakie pozwalają przeprowadzić jeden ciąg na drugi.

Ścisła implementacja zależy oczywiście od definicji użytych ciągów. Na przykład dwa ciągi bajtów zapisanych w pamięci komputera można, zależnie od potrzeb, potraktować jako ciągi binarne lub ciągi literowe zakodowane w ASCII; odpowiednio odległość Hamminga będziemy definiować jako liczbę różnych bitów lub różnych bajtów. Odległość Hamminga pozwala określić pewne właściwości kodowania:

Możliwa liczba korekcji błędów jest mniejsza niż
.

Możliwa liczba detekcji błędów jest mniejsza niż DH.

Następnie można określić, że dla:

DH = 1 - nie jest możliwe wykrycie błędów.

DH = 2 - jest możliwe wykrycie błędu, jednak niemożliwa jest korekcja.

DH = 3 - możliwa jest korekcja.

Przykłady:

Odległość pomiędzy ciągami 10011101 i 10111001 wynosi 2.

Odległość pomiędzy ciągami zagrabić i zatrąbił wynosi 3.

---