Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
Pojęcie bitu
|
Podrozdziały |
Kod korekcyjny (ang. ECC - Error Correction Code) ma za zadanie odtworzenie, naprawę informacji w przypadku wystąpienia błędu (lub błędów) spowodowanych zakłóceniami sygnału w kanale transmisyjnym. Kody ECC stosujemy zwykle tam, gdzie:
powtórzenie transmisji nie usuwa błędu, np. zarysowany nośnik CD lub DVD. Powtórne odtworzenie ścieżki nic nie daje, ponieważ zawsze wystąpi ubytek odczytanych danych.
Najprymitywniejszym kodem ECC jest po prostu trzykrotne przesyłanie każdego bitu danych. Jeśli w trakcie transmisji nastąpi przekłamanie jednego bitu, to dwa pozostałe pozwolą odtworzyć właściwy bit danych.
Nadajnik | Kanał transmisyjny |
Odbiornik | ||
1 | ... | 111 ... 011 | ... | 011 → 1 |
0 | ... | 000 ... 001 | ... | 001 → 0 |
1 | ... | 111 ... 101 | ... | 101 → 1 |
1 | ... | 111 ... 110 | ... | 110 → 1 |
W powyższym przykładzie występuje błąd w trakcie każdej transmisji trójek bitów. Dlatego po stronie odbiornika odebrane trójki zawierają różne bity. Za bit nadany odbiornik przyjmuje bit powtarzający się najczęściej. Oczywiście system ten zawiedzie, gdy przekłamane zostaną dwa bity w trójce.
Potrójne przesyłanie danych nie jest stosowane w praktyce - przepustowość kanału transmisyjnego spada trzykrotnie, na co nikt nie mógłby sobie pozwolić ze względów ekonomicznych. Jeśli błędy pojawiają się rzadko w kanale transmisyjnym, to przesyłaną informację można zabezpieczyć kodem Hamminga. Kod ten, wynaleziony przez Richarda Hamminga w 1950 roku, pozwala naprawić pojedyncze przekłamania bitów w odebranym słowie binarnym. Poniżej przedstawiamy konstrukcję słówek kodu Hamminga dla wiadomości 4-bitowych.
Na początek będzie nam potrzebna tablica liczb binarnych o wartościach od 0 do 7:
dziesiętnie | binarnie |
0 | 000 |
1 | 001 |
2 | 010 |
3 | 011 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
Słówko danych składa się z 4 bitów b4b3b2b1. Bity te umieszczamy w słówku kodu Hamminga w sposób następujący:
Numer pozycji : | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Słowo kodu Hamminga: | b4 | b3 | b2 | x4 | b1 | x2 | x1 |
Pozycje o numerach będących kolejnymi potęgami liczby 2 (1, 2, 4, 8, 16, ...) są tzw. pozycjami kontrolnymi. Oznaczyliśmy je literką x. Pozycje kontrolne musimy obliczyć na podstawie słowa danych. Zróbmy to na konkretnym przykładzie. Niech nasze słowo informacyjne ma wartość:
b4b3b2b1 = 1011 |
Bity informacyjne wpisujemy na odpowiednie pozycje w słowie kodu Hamminga:
Numer pozycji : | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Słowo kodu Hamminga: | 1 | 0 | 1 | x4 | 1 | x2 | x1 |
Zapiszmy wszystkie numery pozycji, na których występują bity o stanie 1. Są to pozycje 7, 5 i 3. Wykorzystując tabelkę konwersji dziesiętno-dwójkowej zapiszmy wyznaczone numery pozycji binarnie:
7 = 111, 5 = 101 i 3 = 011. |
Teraz otrzymane liczby binarne wpisujemy do poniższej tabelki:
x4 | x2 | x1 |
1 | 1 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
Aby wyznaczyć kolejne pozycje kontrolne x4, x2 i x1, pionowo w kolumnach uzupełniamy bity bitem parzystości (w danej kolumnie liczba bitów 1 musi być parzysta). Otrzymane w ten sposób bity parzystości są wartościami dla pozycji kontrolnych:
x4 | x2 | x1 |
1 | 1 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 1 |
Bity parzystości kolumn przepisujemy do odpowiednich pozycji kontrolnych w słowie kodowym Hamminga:
Numer pozycji : | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Słowo kodu Hamminga: | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Gotowe, utworzyliśmy słowo kodu Hamminga dla danej informacji: 1011 → 1010101.
Przesyłamy wyznaczone powyżej słowo kodu Hamminga 1010101 przez kanał transmisyjny. Występuje przekłamanie na pozycji nr 6 i w efekcie odbiornik odbiera słowo 1110101.
Numer pozycji : | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Odebrane słowo kodu Hamminga: | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
Odbiornik wyznacza pozycje wszystkich bitów 1 w odebranym słowie: 7, 6, 5, 3 i 1. Numery pozycji przekształca na kod binarny zgodnie z podaną wcześniej tabelą konwersji:
7 = 111, 6 = 110, 5 = 101, 3 = 011 i 1 = 001. |
Binarne numery pozycji odbiornik umieszcza w tabeli i każdą kolumnę uzupełnia bitem parzystości:
7 | 1 | 1 | 1 |
6 | 1 | 1 | 0 |
5 | 1 | 0 | 1 |
3 | 0 | 1 | 1 |
1 | 0 | 0 | 1 |
bit parzystości | 1 | 1 | 0 |
Otrzymaliśmy wartość 110. Wg tabeli konwersji jest to liczba 6, która oznacza pozycję w słowie kodowym Hamminga, na której wystąpiło przekłamanie. Ponieważ przekłamanie w transmisji cyfrowej polega na odebraniu bitu o stanie przeciwnym do nadanego, zatem wystarczy zanegować (zmienić stan na przeciwny) bit na pozycji 6, aby otrzymać nadane słowo Hamminga:
Numer pozycji : | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Naprawione słowo kodu Hamminga: | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Teraz usuwamy bity kontrolne i otrzymujemy informację nadaną: 1011. Jeśli w trakcie transmisji błąd nie wystąpi, to odbiornik otrzyma w wyniku dekodowania pozycję 000 = 0. W takim przypadku usuwa jedynie bity kontrolne.
Poniższy program tworzy kody Hamminga dla 8-bitowych słówek b8b7b6b5b4b3b2b1. W przypadku słówek 8-bitowych słówko kodowe Hamminga posiada 4 pozycje kontrolne x8, x4, x2 i x1:
Numer pozycji : | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Słowo kodu Hamminga: | b8 | b7 | b6 | b5 | x8 | b4 | b3 | b2 | x4 | b1 | x2 | x1 |
C++// Kodowanie Hamminga // (C)2020 mgr Jerzy Wałaszek // I LO w Tarnowie #include <iostream> using namespace std; int main( ) { char s [ 10 ]; int h,w,x,mw,mh,i; cout << " dane = "; cin.getline ( s,9 ); // odczytane słówko przekształcamy na wartość for( w = i = 0; ( s [ i ] ) && (( s [ i ] == '0' ) || ( s [ i ] == '1' )); i++ ) w = w + w + ( s [ i ] == '1' ); // bity w umieszczamy na odpowiednich pozycjach h // i wyznaczamy bity kontrolne x x = h = 0; for( i = 12, mh = 0x800, mw = 0x80; mw; mh >>= 1, mw >>= 1, i-- ) { if(( mh == 0x80 ) || ( mh == 0x08 )) { mh >>= 1; i--; } if( w & mw ) { h |= mh; x ^= i; } } // bity kontrolne x wstawiamy na odpowiednie pozycje w h for( mh = 0x80, mw = 0x8; mw; mw >>= 1 ) { if( x & mw ) h |= mh; switch ( mh ) { case 0x80 : mh = 0x08; break; case 0x08 : mh = 0x02; break; case 0x02 : mh = 0x01; break; } } // wyświetlamy gotowe słówko kodu Hamminga cout << "kod Hamminga = "; for( mh = 0x800; mh; mh >>= 1 ) cout << (( h & mh ) ? "1" : "0" ); cout << endl; return 0; } |
Wynik: |
dane = 11001110 kod Hamminga = 110001110011 |
Podane w tym artykule informacje nie wyczerpują zagadnienia kodów korekcyjnych. Zainteresowanych tym tematem czytelników odsyłamy do źródeł w Internecie dotyczących kodów Golay'a, Reeda-Mullera i Reeda-Salomona. Wymagają one zaawansowanej arytmetyki binarnej, wykraczającej poza zakres materiału dla szkoły średniej i dlatego zostały tutaj pominięte. Z drugiej strony kody te są stosowane w popularnym sprzęcie Audio-CD oraz DVD do korekcji błędów odczytu z nośników cyfrowych. Kody ECC Reeda-Salomona pozwalają odtworzyć informację przy wystąpieniu tzw. błędów seryjnych, czyli ciągu kolejnych przekłamanych bitów (powstających np. przy zarysowaniu nośnika CD/DVD). Dzięki nim odtwarzacze CD i DVD mogą poprawnie odczytywać zarysowane i poplamione płyty cyfrowe (oczywiście tylko do pewnego stopnia). Inteligentne urządzenia odtwarzające nawet radzą sobie w sytuacji, gdy fragment danych jest niemożliwy do odtworzenia. W takim przypadku, aby zapobiec nieuniknionym trzaskom w odtwarzanym nagraniu, w miejsce uszkodzonego fragmentu utworu wstawiany jest fragment bezpośrednio poprzedzający uszkodzenie. Niewprawne ucho nawet nie zauważy tego oszustwa w odtwarzanym utworze muzycznym. Podobnie postępuje się w przypadku filmów DVD.
Obraz telewizyjny składa się z linii obrazowych wyświetlanych kolejno na ekranie kineskopu. Treść poszczególnych linii jest zapisana cyfrowo na płycie DVD. Jeśli w wyniku błędów nośnika nie daje się odtworzyć jednej lub kilku sąsiednich linii, to odtwarzacz DVD po prostu kopiuje w ich miejsce ostatnią dobrze odebraną linię obrazową. Uzyskany efekt jest zwykle niewidoczny lub mniej irytujący niż w przypadku błędnego wyświetlenia uszkodzonego fragmentu obrazu.
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.