Korekcja błędów

Alicja i Bob wymyślili świetną sztuczkę. Wymieniają wiadomości, trącając przewód mocno lub lekko, by przekazać zero lub jedynkę. Jednak wskutek porywów wiatru w przekazie mogą pojawić się fałszywe zera lub jedynki, co powoduje błędy. Wymyślili sposób, by komunikować się bez błędów, nawet gdy występuje szum. Jak to możliwe? W latach 40. XX wieku Richard Hamming miał podobny problem, pracując w Laboratoriach Bella. W Laboratoriach Telefonicznych Bella robimy 10% doświadczeń w komputerze i około 90% w laboratorium. Z czasem będziemy robić 90% w komputerze i 10% w laboratorium. Szybkość, koszt i wygoda dają komputerowi przewagę nad laboratorium. Wówczas komputery wykorzystywały informacje przechowywane na kartach perforowanych, gdzie symbolami jedynek i zer były dziury lub ich brak. System był podatny na błędy, bo karty często wyginały się i były dziurkowane w złych miejscach. Otwory były pomijane lub przypadkowo pojawiały się tam, gdzie nie trzeba, tworząc odwrotne bity. Przez to cały system stał, póki nie znaleziono błędu i nie naprawiono go ręcznie. Hamming podjął się wymyślenia metody automatycznego wykrywania i korekty błędów w pojedynczych bitach, bez przerywania obliczeń. Jego rozwiązanie wynikało z intuicyjnej skłonności do powtórzeń. Wszyscy to robimy, gdy są sakłócenia albo gdy zachodzi obawa, że część naszego przekazu nie dotrze. Metoda opierała się o prostą koncepcję bitu parzystości. Bit parzystości to pojedynczy bit dodany na końcu wiadomości, wskazujący, czy liczba jedynek jest parzysta czy nie. Jeśli pojawi się jeden błąd, odbiorca go wykryje, bo nie będzie się zgadzał bit parzystości. Żeby jednak wykrywać i naprawiać pojedyncze błędy, Hamming musiał dodawać więcej bitów parzystości, aby znaleźć miejsce błędu. A to prowadzi do jego kodu (7,4), który dodaje 3 bity parzystości do każdego bloku 4 bitów danych. Właśnie tak. Zaczynamy od trzech bitów parzystości, które przedstawiamy tu jako koła. Koła pokrywają się, tworząc cztery obszary. W tych regionach umieszczone zostają cztery bity danych, w wyznaczonym porządku. Aby określić bity parzystości, patrzymy po kolei na każde kółko, zawierające trzy bity danych. Bit parzystości wyznaczamy jak wcześniej. Dodajemy bity danych i jeśli uzyskamy 0 albo 2… Bit parzystości wynosi 0. a jeśli uzyskamy 1 lub 3… bit parzystości ma wartość 1. Robimy to dla wszystkich kółek. Mamy trzy bity parzystości z czterema bitami danych. Zostają uszeregowane w standardowy ciąg. Zauważcie, że ten system może automatyczne korygować pojedyncze błędy za pomocą prostej zasady. Jeśli wystąpi jeden błąd, co najmniej dwa bity parzystości będą nieprawidłowe, a obszar ich nakładania się to lokalizacja błędu. Bit danych w tym miejscu zostaje automatycznie odwrócony i wszystkie bity parzystości znów są prawidłowe. To jest sztuczka Alicji i Boba. Dodatkowe bity parzystości są znane jako bity redundantne, bo nie zawierają nowej informacji. Wszystkie kody korekcyjne działają w ten sposób. Wszystkie lekko zwiększają rozmiar wiadomości źródłowej, za to automatycznie poprawiają błędy. Kodów korekcyjnych używa się też przy przechowywaniu danych. Na płycie CD informacje są kodowane przy użyciu specjalnych kodów. Naprawiają one segmenty z błędami spowodowanymi przez brud i zarysowania, które niszczą dłuższe ciągi zer i jedynek na powierzchni. To dlatego zarysowana płyta często nadal będzie grała bez zarzutu. Claude Shannon, włączając redundancję, przedefiniował pojemność kanału komunikacyjnego. Ponieważ gdy w kanale nasila się szum, trzeba zwiększyć ilość redundancji, by porozumiewać się bez błędów. A to musi zmniejszyć ilość informacji przesyłanych w jednostce czasu.