Az Informatika Elméleti Alapjai dr. Kutor László
A csatornakódolás elve „A hibatűrés záloga: a redundancia” http://mobil.nik.bmf.hu/tantargyak/iea.html Felhasználónév: iea 2007. ősz
BMF NIK
Jelszó: IEA07 dr. Kutor László
IEA 9/1
Az információ redundanciája 1. Redundancia köznapi értelmezése: terjengősség A redundancia információ elméleti értelmezése: n HS = - ∑ p{ xi}* log2p{xi} (Shannon) i=1 n
Hmax = - ∑ 1/n * log (1/n)= - log (1/n) = log (n) i=1
Hrelatív = 2007. ősz
HS Hmax
(Hartley)
= az információ forrás „jósága” BMF NIK
dr. Kutor László
IEA 9/2
Az információ redundanciája 2. HS = a hírforrás entrópiája (információ tartalma) Hmax = a hírforrás maximális entrópiája HS
Hrelatív =
Hmax
RS = 1 -
HS Hmax
= az információ forrás „jósága”
*
A hírforrás által közölt információ 100 hány százaléka „felesleges”
1.684 = 0.842 2 = (1 – 0.842) * 100 = 15.8 ~~ 16%
Példa: HS = 1.684 Hmax = 2
RS 2007. ősz
BMF NIK
Hr =
dr. Kutor László
IEA 9/3
Az Informatika Elméleti Alapjai
2007. ősz
BMF NIK
dr. Kutor László
IEA 9/4
Képek információ tartalma
Bled, (Szlovénia)
PCX grafikai formátum (Zsoft Co.) 1
1
számláló 2007. ősz
BMF NIK
ismétlődő bájt dr. Kutor László
IEA 9/5
Minőség jellemzők
1. Minőség: (Quality) a rendszer jellemzői felhasználás előtt 2. Megbízhatóság: (Reliability) a rendszer viselkedése a használat során
idő tényező !!!
2007. ősz
BMF NIK
dr. Kutor László
IEA 9/6
„sarki fény”
Hibafajták 1.) Állandó hibák (hard errors) 2.) Múló hibák (soft errors) a.) „hagyományos” múló hibák hőmérséklet okozta hibák rendszerzaj okozta hibák bitminta érzékenység
Pekka Parviainen
Napkitörés
b.) Sugárzás okozta hibák
2b.) > 2a.) 2007. ősz
2.) > 1.) BMF NIK
dr. Kutor László
IEA 9/7
λ
Tipikus meghibásodási görbe (kád görbe) Kezdeti hibák szakasza hasznos élettartam
MTBF
elöregedés
λ
t http://en.wikipedia.org/wiki/Image:Bathtub_curve.jpg
2007. ősz
BMF NIK
dr. Kutor László
IEA 9/8
t
A meghibásodási arány értelmezése λ= hiba/ 106 óra A hiba arány átszámolása alacsonyabb hőmérsékletre Arrhenius egyenlet:
λ2= λ1 * e ahol
ξa/K*(1/T2-1/T1)
λ2 = a T2 hőmérsékleten tapasztalt meghibásodási arány λ1 = a T1 hőmérsékleten tapasztalt meghibásodási arány ξa = aktivációs energia [eV] (hibafajtáknál más és más!!!) K = Boltzmann állandó: 8.61*10-5 [ eV/K°]
2007. ősz
BMF NIK
dr. Kutor László
IEA 9/9
Hibák érzékelése és javítása A hiba érzékelés és javítás alapja: a módszeresen megnövelt redundancia n
Csatorna k
Kiegészítő kód előállítás
n + k
n
Hiba érzékelés és javítás
Példa: egy hiba érzékelésére
10110100 0 10110100 1 2007. ősz
páros paritás páratlan paritás BMF NIK
dr. Kutor László
IEA 9/10
Hibajavítás kommunikációs hálózatokban Elterjedt gyakorlat: a hiba érzékelése adatblokkonként, szükség esetén a blokk újraküldése Tipikus megoldás a hiba érzékelésre: ciklikus redundanciakód (CRC) hozzáfűzése az adatblokkokhoz Az ellenőrző bitek létrehozása polinomokkal: Nemzetközi szabvány polinomok: CRC-12, = X12+X11+X3+X2+X+1 CRC-16 = X16+X15+X2+1 CRC-CCITT = X16+X12+X5+1 2007. ősz
BMF NIK
dr. Kutor László
IEA 9/11
Hiba érzékelhetőség és javíthatóság feltétele: a megfelelő Hamming távolság
XOR !
Hamming távolság h = eltérő bitek száma Példa:
1011010 001101110 1010101 001101010
h=5
Szükséges Hamming távolság:
2007. ősz
k hiba jelzéséhez:
h = k+1
k hiba javításához
h = 2k+1
BMF NIK
dr. Kutor László
IEA 9/12
Egy hiba javítása (Single Error Correction) Szükséges kiegészítő bitek száma:
2k ≥ n + k + 1 ahol:
n = a kódszó hossza, k = a kiegészítő kód hossza Példa:
n
k
2–4 5 – 11 12 – 26 27 – 57 58 – 120 2007. ősz
redundancia (%)
3 4 5 6 7
100 45 23 12 6
BMF NIK
dr. Kutor László
IEA 9/13
A kiegészítő kódszó előállítása Paritás elv alapján:
X1 * * *
X2 * *
X3 * *
X4 * *
S1 = X1+X2+X3+P1 S2 = X1+X2+X4+P2 S3 = X1+X3+X4+P3 2007. ősz
BMF NIK
P1 *
P2
P3 S1 S2 S3
* *
S1= 0 P1 S1 és S2= 0 S2= 0 P2 S1 és S3= 0 S3= 0 P3 S2 és S3= 0 S1 és S2 és S3= 0 X1 dr. Kutor László
X2 X3 X4
IEA 9/14
A kiegészítő kódos hibajavítás blokksémája javítás
n
Csatorna par. k
n
n
k Hiba érzékelés
Kiegészítő kód előállítás
2007. ősz
BMF NIK
dr. Kutor László
IEA 9/15
Hibajavítás ROM-ban tárolt kóddal A hiba érzékelés és javítás alapja: a módszeresen megnövelt redundancia
n
Csatorna ROM 1
n c + í k m
ROM 2
a d a t
n
k
Példa: egy hiba érzékelésére Hiba érzékelés és javítás
10110100 1 2007. ősz
páratlan paritás BMF NIK
dr. Kutor László
IEA 9/16
Példa a ROM-ban tárolt hibajavító kódra ROM 1 cím: X1 X2 X3 X4
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
2007. ősz
adat: P1 P2 P3 ROM 2 cím:X1 X2 X3 X4 P1 P2 P3
000 011 101 110 110 101 011 000 111 100 010 011 001 010 100 111
BMF NIK
0 0000000 0000001 0000010 0000011 0000100 0000101 0000110 0000111 0001000 0001001 0001010 127 dr. Kutor László
adat: X1 X2 X3 X4
0000 0000 0000 0001 0000 0010 0100 1000 0000 0001 0001 IEA 9/17
Hibaérzékelés és hibajavítás értékelése Előnyök: Növekszik a megbízhatóság A rendszer állapota ellenőrizhető Nem csökkenti jelentősen a teljesítményt Hátrányok: Több alkatrészre van szükség (kártya méret, fogyasztás nő) Többlet kiadással jár 2007. ősz
BMF NIK
dr. Kutor László
IEA 9/18
