Referat. Architektura Systemów Komputerowych
Opracował: Dariusz Zagórski
Warszawa, Uczelnia Vistula 2012
Referat. Architektura Systemów Komputerowych
Opracował: Dariusz Zagórski
Warszawa, Uczelnia Vistula 2012
W systemach pamięci mogą występować dwa rodzaje błędów: błędy stałe i
przypadkowe.
Błąd stały (czyli uszkodzenie sprzętowe) jest trwałym defektem fizycznym
nośnika powodującym, że uszkodzona komórka pamięci nie jest w stanie
przechowywać danych – pozostają one trwale w stanie 0 lub 1, ewentualnie
zmieniają swój stan przeskakując chaotycznie pomiędzy 0 i 1.
Błąd przypadkowy jest zjawiskiem losowym i nieniszczącym, które zmienia
zawartość komórek pamięciowych bez ich fizycznego uszkodzenia. Błąd taki
może być spowodowany przez problemy z zasilaniem lub naturalnie i
powszechnie występujące zjawiska emisji cząsteczki alfa w procesie
promieniotwórczości
.
Bitem parzystości nazywamy bit kontrolny, który przyjmuje wartość 1, gdy
liczba jedynek w przesyłanej wiadomości jest nieparzysta lub 0, gdy
odwrotnie. Innymi słowy – bit parzystości sprawia, że wiadomość ma
zawsze parzystą liczbę jedynek. W tym wariancie bit parzystości możemy
obliczyć wykonując
na wszystkich bitach wiadomości:
gdzie n to liczba bitów wiadomości.
Przykłady
Wiadomość 10111101
2
ma parzystą liczbę jedynek, więc bit parzystości
wynosi 0. Wiadomość z dołączonym bitem parzystości to 101111010
2
.
Wiadomość 01110011
2
ma nieparzystą liczbę jedynek, więc bit parzystości
wynosi 1. Wiadomość z dołączonym bitem parzystości to 011100111
2
.
W wielu systemach kodowania (kody kreskowe, numery ISBN, numery
rachunków bankowych, numery NIP) stosuje się sumy kontrolne. Są to
specjalne kody, które pozwalają szybko ustalić, czy któryś z
poprzedzających je znaków nie został przypadkiem błędnie odczytana.
CRC (cykliczna kontrola nadmiarowa) to technika opierająca się na sumach
kontrolnych, którą stosuje się głównie przy przesyłaniu danych w celu
sprawdzenia , czy w jakimś bloku lub strumieniu bajtów nie wkradł się błąd.
Istnieje tutaj prosta zależność, że im większy blok danych jest do
sprawdzenia, tym większa musi być suma kontrolna. Sumy kontrolne i
techniki CRC zaliczamy do grupy regularnych systemów detekcji błędów.
Bity kontrolne są doklejane do bajtów danych nie powodując ich zmiany.
Grupę takich bitów nazywamy syndromem. Techniki CRC są oparte na
arytmetyce modulo 2.
W momencie, gdy dane mają być wczytane do pamięci przeprowadza się na
tych danych obliczenia, określane jako funkcja f, w celu utworzenia kodu, przy
czym dane i kod zostają przechowywane i w efekcie powstaje M+K bitowe
słowo (M-bitów danych i K-bitów kodu).
W trakcie odczytu uprzednio zmagazynowanego słowa kod korekcyjny jest
wykorzystywany do wykrycia i ewentualnej korekty błędów. Najpierw
generowany jest nowy zestaw K-bitów kodowych z M-bitów danych, po czym
następuje porównanie go z pobranymi bitami kodowymi. W wyniku porównania
następuje jeden z 3 stanów:
- nie wykryto żadnych błędów więc przesyłamy pobrane bity
- wykryto błąd i jest możliwa jego korekta – bity danych i bity korekty błędu sa
przesyłane do układu korektora, gdzie jest tworzony poprawiony zestaw M-
bitów przeznaczonych do wysłania
- wykryto błąd niemożliwy do poprawienia – zgłaszamy alarm
Wszystkie kody działające na tej zasadzie nazywamy kodami korekcyjnymi.
Kod korekcyjny jest opisywany przez liczbę błędnych bitów w danym słowie.
Jednym z najstarszych, a zarazem jednym z najwydajniejszych kodów
zapewniających możliwość korygowania błędów jest kod Hamminga. Został on
opracowany przez Richarda Hamminga z Bell Laboratories. Kody Hamminga
stosuje się wszędzie tam, gdzie zachodzi duże prawdopodobieństwo pojawienia
się losowych błędów, tj. takich, dla których prawdopodobieństwo wystąpienia
błędu na pozycji danego bitu jest takie samo, jak na wszystkich pozostałych
pozycjach, niezależnie od liczby błędów, które już wystąpiły w danym bajcie.
Tego typu błędy pojawiają się w pamięciach komputerów.
Kod Hamminga wykorzystuje kontrolę parzystości, w której zdolność do
wykrywania i korygowania błędów rośnie proporcjonalnie do bitów parzystości
dodawanych do każdego słowa właściwej informacji. Samo słowo maszynowe
składa się z m bitów, ale dodaje się do niego r bitów kontrolnych(bitów
parzystości), które pozwalają na stosowanie mechanizmów kontroli i korekcji
błędów. Otrzymujemy w ten sposób tzw. słowo kodowe.
Działanie Kodu Hamminga najlepiej zrozumieć na podstawie Diagramu Venna.,
czyli schematu ilustrującego zależność pomiędzy zbiorami, co znacznie ułatwia
dostrzeżenie relacji pomiędzy zbiorami.
Odległością Hamminga będziemy nazywać liczbę bitów, którymi różnią się
dwa słowa. Np.
10001001
10110001
- - ***- - -
różnią się trzema bitami, więc ich odległość Hamminga jest równa 3.
Odległość Hamminga między dwoma słowami kodowymi ma istotne znaczenie
dla wykrywania błędów. Jeżeli dla dwóch różnych słów kodowych wynosi ona d,
to wystarczy d jednobitowych błędów, aby z jednego z nich zrobiło się drugie i
aby błąd pozostał niezauważony. W związku z tym, jeżeli chcemy tworzyć kod,
który zagwarantuje nam wykrycie wszystkich jednobitowych błędów, dla
wszystkich par słów kodowych odległość musi wynosić przynajmniej 2. Jeżeli
dane n-bitowe słowo nie zostanie rozpoznane jako dozwolone słowo kodowe,
będzie ono uznane za błędne.
W celu wyjaśnienia wykorzystanej koncepcji opracujemy kod, który może
posłużyć do wykrycia i skorygowania 1-bitowego błędu w słowach 8-
bitowych. Zaczniemy od określenia wymaganej długości kodu. Zgodnie z
ogólnym schematem działania kodów korekcyjnych (rys. 5.7) układy
porównujące otrzymują na wejściu dwie wartości k-bitowe. Porównanie jest
dokonywane przez bramki XOR. Otrzymany wynik nosi nazwę syndromu, a
każdy jego bit przyjmuje wartość 0 lub 1 w zależności od wyniku
porównania zgodności bitów na 2 wejściach.
Słowo syndrom ma więc k bitów i zakres wartości pomiędzy 0 a 2
k
-1.
Wartość 0 wskazuje, że nie został wykryty żaden błąd, natomiast wartości
2
k
-1 wskazują na zaistnienie błędu i jego lokalizację bitową. Ponieważ błąd
może wystąpić w dowolnym z m bitów danych lub k bitów kontrolnych musi
być spełniona nierówność 2
k
-1 >=m+k, określająca ilośc bitów
wymaganych do skorygowania błędu 1-bitowego w słowie zawierającym m
bitów danych.
W naszym przypadku k=4: bo
2
4
>8+4
- 8 bitów danych wymaga 4 bitów kontrolnych.
Chcemy aby utworzony prze nas 4-bitowy syndrom miał następujące
właściwości:
Jeżeli syndrom zawiera same 0 to znaczy że nie został wykryty żaden
błąd
Jeżeli syndrom zawiera jedną i tylko jedną 1, błąd wystąpił w jednym z
bitów kontrolnych – korekta nie jest potrzebna
Jeżeli syndrom zawiera więcej niż jedną 1, to wartość numeryczna
syndromu wskazuje pozycję błędnego bitu danych. Korekta polega na
zamianie wskazanego bitu
Aby uzyskać zamierzony efekt bity danych i bity kontrolne są aranżowane
jako słowa 12-bitowe. Pozycje bitowe są ponumerowane od 1 do 12. Bity
na pozycjach będących potęgą 2 są bitami kontrolnymi.
Pozycja
bitowa
12
11
10
9
8
7
6
5
4
3
2
1
Numer
pozycji
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
Bit
danych
D8
D7
D6
D5
D4
D3
D2
D1
Bit
kontrolny
C8
C4
C2
C1
Pozycj
a
bitowa
12
11
10
9
8
7
6
5
4
3
2
1
Numer
pozycji
1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
Bit
danych
D8
D7
D6
D5
D4
D3
D2
D1
Bit
kontrol
ny
C8
C4
C2
C1
Słowo
zapisa
ne
0
0
1
1
0
1
0
0
1
1
1
1
Słowo
pobran
e
0
0
1
1
0
1
1
0
1
1
1
1
Bit
kontrol
ny
0
0
0
1
Tabela. Wzrost długości słowa po uwzględnieniu korekty błędów.
Liczba
bitów
danych
Poprawianie
pojedynczego błędu
Poprawianie
pojedynczego błędu
Wykrywanie błedu
podwójnego
Bity
kontrolne
% wzrostu
Bity
kontrolne
% wzrostu
8
4
50
5
62,5
16
5
31,25
6
37,5
32
6
18,75
7
21,875
64
7
10,94
8
12,5
128
8
6,25
9
7,03
256
9
3,52
10
3,91
Kody Hamminga sprawdzają się w sytuacjach w których błędy występują stosunkowo
rzadko. We współczesnych dyskach twardych błąd pojawia się średnio raz na 100
milionów bitów a 3-bitowy kod Hemminga pozwoliłby na jego bezproblemowe usunięcie.
Jednakże kody te są bezużyteczne w sytuacji gdy istnieje prawdopodobieństwo, że
uszkodzonych będzie kilka kolejnych bitów (powstanie tzw. błąd sekwencyjny. Błędy te są
charakterystyczne dla przenośnych nośników pamięci, o których użytkonik nie dba tak
jak powinien. Gdy przewidujemy, że błędy będą występowały całymi blokami, należałoby
zastosować kod korekcji błędów, który operuje na poziomie bloków, nie zaś pojedynczych
bitów. Przykładem takiego kodu jest kod Reeda-Solomana (RS), który można traktować
tak, jak gdyby był on właśnie kodem CEC odnoszącym się do większej grupy znaków.
Kody RS, podobnie jak CRC, są symetryczne. Bity parzystości są doklejane do bloków
zawierających bity danych.
Kody RS (n,k) definiowane są za pomocą następujących parametrów:
S = liczba bitów w znaku (zwanym też symbolem)
K = liczba k-bitowych znaków składających się na blok danych
n = liczba bitów w słowie kodowym
RS (n,k) jest w stanie skorygować (n-k)/2 błędów w k bajtach informacji.
Najbardziej popularny kod RS (255,223) wykorzystuje więc 223 8-bitowe bajty informacji i
32 bajty kontrolne, które składają się na 255-bajtowe słowa kodowe. Jest on w stanie
skorygować do 16 błędnych bajtów występujących w danym bloku informacji.
BIBLIOGRAFIA
William Stallings, Orgaizacja i Architektura Systemu Komputerowego
Wikipedia
Inne źródła