Hibajavítás és hibajelzés Informatikai rendszerek alapjai
Horváth Árpád 2015. november 12.
Tartalomjegyzék 1. Hibákról
Információátvitel diagrammja csatorna
forrás
vev®
zaj Példák: Beszélgetés forrás: száj, csatorna: leveg®, vev®: fül Földfelszíni rádióadás forrás: a rádióadó vagy az átjátszó antennája, csatorna: az éter, vev®: a rádió antennája Internet forrás: router1, csatorna: üvegszál, vev®: router2
Hibák el®fordulása •
Üvegszálakon ritkán
•
Sodrott érpáron (pl. UTP kábel) gyakrabban
•
Vezeték nélküli hálózatokban gyakran
•
Egyes közegekben (pl. rádió) általában csoportosan
El®ny: kevesebb adatcsomagot érint Hátrány: nehezebb jelezni ill. javítani a hibát
2. Hibajavító és -jelz® kódok
Hibajavítás és -jelzés Két lehet®ség:
•
Annyi redundanciát adunk minden elküldött adatblokkhoz, hogy visszaállítható legyen az eredeti.
1
•
hibajavító kód error-correcting code
•
Annyi redundanciát adunk minden elküldött adatblokkhoz, hogy kiderüljön, hogy hibás adatot kaptunk-e.
•
Ha hibás, újraküldjük.
•
hibajelz® kód error-detecting code
•
Az els® akkor ha nem küldhet® újra az adat (CD, DVD), illetve adatszórásnál (digitális rádió, TV).
Alapfogalmak m n = m + r.
Kódszavak (codeword): A teljes hossz
üzenetbitb®l (message bit) és
r
redundáns ellen®rz® bitb®l állnak.
De níció Az olyan helyek számát, ahol két kódszóban különböz® bitek állnak, a két kódszó
Hamming-
távolságának nevezzük. (Hamming, 1950)
Alapfogalmak Példa
a kódszó
1
1
0
1
1
0
1
0
1
b kódszó
0
1
1
1
0
1
1
0
1
d(ab) = 4 a Hamming-távolsága a két kódszónak. Ha két kódszó Hamming-távolsága 4, akkor 4 hiba kell ahhoz, hogy az egyik a másikba menjen. Általában mind a
2m
üzenetbit-sorozat érvényes, de nem mind a
2n
bitsorozat kódszó.
Ismerve az redundáns bitek kiszámításának módját, meghatározható a legális kódszavak listája (üzenetenként egy). Ezek közül kikereshet® az a kódszópár, amelynek Hamming-távolsága minimális.
Kód és kódszó De níció Az érvényes
n
bites bitsorozatokat kódszavaknak nevezzük.
A kódszavak összességét kódnak nevezzük.
Alapfogalmak De níció Egy
kód Hamming-távolságán a minimális távolságot értjük, amelyet két kódszava között találunk.
Példa Az alábbi kód Hamming-távolsága 4 .
a 01010101 b 00001111 c 00110010 2
d(ab) = 4 d(bc) = 5 d(ac) = 5
Egy kód Hamming-távolsága 4.
•
Legfeljebb 3 hiba lehet, hogy biztosan ne kapjunk másik kódszót az eredeti helyett.
•
Legfeljebb 1 hiba lehet, hogy biztosan ki tudjuk találni, melyik volt az eredeti kódszó.
kódszó1
kódszó2
•
Feladat Maximum
e
hibára számítunk.
Mennyi legyen a Hamming-kód
d
távolsága, hogy ki tudjuk mutatni a hibát?
d
távolsága, hogy javítani tudjuk a hibát?
d≥e+1 Mennyi legyen a Hamming-kód
d ≥ 2e + 1
Gondolkozzunk! Biztosan sikerül megoldani. Hogyan lehetne olyan kódot el®állítani, hogy egy hibát ki tudjunk mutatni?
Azaz jönnek adott hosszúságú üzenetek (bitsorozatok), és mindegyik helyett egy másik bitsorozatot küldünk, úgy, hogy meg tudjuk mondani, hogy
hibásan ment-e át az üzenet, és ha nem, meg
tudjuk határozni az üzenetet.
Több bit kell? Elég ugyanannyi? Vagy kevesebb is?
Na és ezt sikerül? Hogyan lehetne olyan kódot el®állítani, hogy egy hibát ki tudjunk javítani?
Egyel®re nem érdekel, hogy milyen hosszúak a kódszavak.
3
Paritásbit De níció Ha a kódszóhoz egy olyan bitet f¶zünk, hogy a kódszóban lev® 1-esek száma páros (illetve páratlan)
paritásbitnek.
legyen. Ezt a bitet nevezzük páros (páratlan)
Továbbiakban páros paritásbitet használunk. Pl. 11011 Pl. 10000
⇒ ⇒
110110 100001
A paritásbit hozzáf¶zésével kapott kód Hamming-távolsága:
2
Alkalmas-e hibajavításra, jelzésre? 1 bithiba jelzésére alkalmas (SEDsingle error detection) Onnan tudjuk, hogy a paritásbittel kiegészített üzenet, mint kód Hamming-távolsága legalább kett®, mert ha két kódszó csak egy bitben térne el, akkor az egyikben páros, másikban páratlan 1-es lenne. Nem lehet, mindegyik kódszó. És a távolság nem több, mint kett®, mert ha két bitet megváltoztatunk, akkor újra kódszót kapunk, ugyanúgy páros lesz az 1-esek száma.
Egy bithiba javítása (SECsingle error correction) Hány bites kódszó kell, ha
m
bites az üzenetünk?
•
Egy kódszó és 1 bithibás szomszédai együtt
•
A
•
Ha
2m n
2m (n + 1)
üzenethez legalább
n+1
bitsorozatot adnak.
különböz® bitsorozat kell.
bites kódszavakat küldünk, akkor a
2n ≥ 2m (n + 1)
egyenl®tlenségnek kell teljesülnie,
hogy egy bithiba javítása lehetséges legyen.
• •
Mivel
n = r + m, 2r ≥ m + r + 1
egyenl®tlenségnek kell teljesülnie.
Az egyenl®tlenséget teljesít® minimális egész
r
bittel tényleg létrehozható egy bithibát javító
kódolás: a Hamming-kód.
A Hamming-kód •
A biteket 1-t®l sorszámozzuk balról jobbra.
•
Minden kett®-hatvány (2 ) helyen paritásbit van.
•
Az egyes paritásbitek nem az összes bitet ellen®rzik.
•
i
A paritásbit ellen®rzi a teljes kulcsszó szerepel a
•
2i
i.
bitjét, ha az
i
kettes számrendszerbeli alakjában
helyiérték.
Például a 6. bitet ellen®rzi a 4-es és 2-es paritásbit, a többi nem. 6=4+2=1102 bit
P1 P2 P4
1.
2.
3.
P1
P2
1
10
+
4.
5.
6.
7.
2+1
P4
4+1
4+2
4+2+1
11
100
101
110
111
+ +
+
+ +
+
+ +
+
+
+
4
Példa Az 100111 üzenet kódolása, és visszaállítása a kód 7. bitjének meghibásodása esetén. bit
P1 P2 P4 P8
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
P1
P2
11
P4
101
110
111
P8
1001
1010
?
1 ?
1
0
1
1
1
1
0
1
?
0
0
1
1
0
0
1
1 1 ?
1
1
0
1
1
A keresett Hamming-kódszó 1111001011, a
Pi
jel¶ oszlopok a paritásbiteket, a többi az üzenet
(message) bitjek helye.
Példa folytatása A keresett Hamming-kódszó 1111001011, a kódot a csatornán átküldve a 7. bitjének meghibásodása esetén a vev®nél kapott kód 1111000011.
P1 P2 P4 P8
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
P1
P2
11
P4
101
110
111
P8
1001
1010
1
1 1
0
1 1
1
1
0
1
1
0 0
0
0
0
0
0
0
1
Helyes? (egyesek száma) hibás (3)
1
hibás (3) hibás (1)
0
1
1
helyes (2)
0
1
1
Hibás 1+2+4= 7. bit
Írjuk fel, milyen bitek tartoznak az egyes paritásbitek fennhatósága alá és vizsgáljuk meg páros 1-es van-e bennük:
• P1 :
1, 1, 0, 0, 1, hibás
• P2 :
1, 1, 0, 0, 1, hibás
• P4 :
1, 0, 0, 0, hibás
• P8 :
0, 1, 1, jó
A biteket ellen®rizve a
P1 , P2 , P4
paritásbitek hibásak, tehát a sérülés helye az
volt. Ezután a helyes kódszó visszaállítható a 7. bit megváltoztatásával:
¯1¯11¯1001¯011 A felülvont karaktereket eltávolítva visszakapjuk az eredeti kódszót:
100111. (Miért biztos, hogy két hiba esetén a javítás után hibás kódszót kapunk?)
5
1 + 2 + 4 = 7.
bitnél
Csoportos hibák elleni védekezés •
Soronként felírjuk az átküldend® Hamming-kódolt kódszavakat (k darabot).
•
Oszloponként küldjük át a jeleket.
•
A vev®nél visszaállítjuk a sorokat, és úgy ellen®rzünk.
•
Ha egy
k
hosszúságú csoportos hiba lép fel, akkor az minden sorban egy bitet ront el, amit a
Hamming-kód javítani képes.
• km
méret¶ adatblokkokhoz
kr
ellen®rz® bit.
Csoportos hibák elleni védekezés jel
7 bites ASCII-kód
Hamming-kódszó
O
1001111
0011001001011
E
1000101
1110000101101
-
0101101
0100101101101
A
1000001
1110000010101
R
1010010
1011010100110
E
1000101
1110000101101
K
1001011
0011001110011
Függ®legesen küldjük el 01011100111010. . . 1111011. A fenti táblázat kimondottan alkalmas otthoni gyakorláshoz.
A második oszlop bitsorozatait
kódolva a harmadik oszlopot kell hogy kapjuk. Ha a harmadik oszlop bármelyik bitjét elrontjuk, azt ki kell tudnunk javítani, és a második oszlop bitsorozatát kapjuk.
Egy bithiba javítása (SECsingle error correction) m
Miért nem lehet a gyakorlatban akármennyire növelni
m-et?
Mert növekszik a valószín¶sége, hogy két hiba forduljon el®, amit nem tudunk javítani.
CRC-kód
r + 1-gyel, akkor a maradék legfeljebb r lesz. (r+1)-ed fokszámú polinommal, akkor a maradék r-ed fokszámú
Hasonlat: Ha egy számot elosztunk
Ha egy polinomot elosztunk egy lesz.
Például az 10011 bitsorozathoz a
1x4 + 0x3 + 0x2 + 1x1 + 1x0 = x4 + x + 1
polinomot rendeljük.
A CRC kód (cyclic redundancy code) esetén az üzenet bitjeit egy polinom együtthatóinak tekintjük, el®re meghatározott polinommal, az úgynevezett generátor-polinommal, végezzük el az
6
osztást, a maradékot az üzenethez f¶zzük.
A vev®nél (ismerve a generátor-polinomot) ugyanígy
ellen®rizni tudjuk a redundáns részt, és ha az hibás, akkor újraküldjük az üzenetet. A vev®nél a generátorpolinomot végigvive a kódolt üzeneten, ha nem sérült kód, akkor csupa nulla marad. Hardveresen hatékonyan elvégezhet®. Rézvezetéken, optikai szálakon és merevlemezeken a bithibaarány kicsi (<
10−6 ),
ott alkalmazzuk. El®nye, hogy a csoportos hibákat, amikor
r
egymás utáni
bit sérül, hatékonyan kimutatja. Tipikusan ezeknél a csatornáknál ugyanis ilyen hiba fordul el®.
Polinomosztás elvégzése
Minden lépésben a következ® 1-es alá írom a generátorpolinomot els®
1-sét, és ha két egyforma érték van egymás alatt, nullát írok alá, különben 1-et. Adott r-edfokú generátorpolinom (r+1 bit) Legyen a generátorpolinom
G(x) = x3 + x + 1 = 1x3 + 0x2 + 1x1 + 1x0 azaz
r = 3,
az együtthatók
1011.
11010011100 <--- eredeti üzenet 11010011100000 <--- r darab 0-val kiegészítem 1011 <--- generátor polinommal osztok 01100011100000 <--- eredmény 1011 <--- osztás ... 00111011100000 1011 00010111100000 1011 00000001100000 1011 00000000111000 1011 00000000010100 1011 00000000000010 Az utolsó r bitet f¶zöm az eredeti üzenethez: 11010011100010 bitsorozatot küldöm el. Ellen®rzés a vev®nél:
