26.B
26.B
26.B
Digitális alapáramkörök – Logikai alapfogalmak
Definiálja a digitális és az analóg jelek fogalmát és jellemzıit! Ismertesse a kettes és a tizenhatos számrendszer jellemzıit és az átszámítási algoritmusokat! Mutassa be az információ kódolásának elvét és a leggyakrabban alkalmazott numerikus és alfanumerikus kódokat! Ismertesse a hibafeltáró kódokat és a hibajavítás elvét! Analóg és digitális mennyiségek jellemzıi Analóg leképezés Egy fizikai mennyiség (pl. feszültség vagy áram) másik fizikai mennyiséggel való leképezése két módon történhet, ezek közül az egyik az analóg leképzés, melynek jellemzıi:
• •
a leképzendı és a leképzı mennyiség idıbeni lefolyása függvénykapcsolattal megadható, a leképzı mennyiség változása folyamatos, tehát bármilyen értéket felvehet.
Digitális leképezés Egy fizikai mennyiség (pl. feszültség vagy áram) másik fizikai mennyiséggel való leképezése két módon történhet, ezek közül az egyik az digitális leképzés, melynek jellemzıi:
• •
a leképzendı és a leképzı mennyiség idıbeni lefolyása függvénykapcsolattal megadható, a leképzı mennyiség változása nem folyamatos, hanem ugrásszerő, tehát csak diszkrét értéket vehet fel.
A digitális szó az angol digit (számjegy) szóból származtatható.
A digitális technika kialakulása Az impulzustechnika gyors fejlıdése alapozta meg egy új tudományág, a digitális technika kialakulását. A félvezetı alapú technológiák gyors fejlesztése és ezen belül az integrált áramkörök megjelenése nagy lendületet adott a digitális technika fejlıdésének.
A digitális technika szerepe a számítástechnikában A digitális technika az információ digitális feldolgozásával, elıállításával és továbbításával foglalkozik. A digitális technika tette lehetıvé a számítástechnika dinamikus fejlıdését.
Az integrált áramkör kifejlesztése Az integrált áramkört1960-ban fejlesztették ki a Fairchild és a Texas Instruments cégek szakemberei: R. Noice, valamint J. St. Clair Kilby. G. Moore 1965-ben megállapítja, hogy évenként megduplázódik az egy félvezetı (szilícium) lapkán levı integrált tranzisztorok száma. Ez a tendencia bizonyos mértékben napjainkban is tart.
A digitális rendszerek és a digitális áramkörök tervezése A digitális technikán belül - egymással szoros kölcsönhatásban - fejlıdött ki a digitális rendszerek és a digitális áramkörök tervezése. A digitális technika tette lehetıvé a számítástechnika dinamikus fejlıdését is.
A digitális technika fejlıdése A félvezetı alapú technológiák gyors fejlesztése és ezen belül az integrált áramkörök megjelenése nagy lendületet adott a digitális technika fejlıdésének.
Az integrált áramkör Az integrált áramkörben a különbözı rendeltetéső aktív és passzív áramkör építıelemeket, valamint a hozzájuk tartozó összekötéseket egyetlen gyártási folyamatban közös félvezetı alapon állítják elı.
Az integrált áramkörök elterjedése Az integrált áramkörök olcsósága, nagy megbízhatósága és kis mérete széleskörő elterjedési eredményezett.
Digitális technika A digitális technika az információ digitális • • •
feldolgozásával, elıállításával és továbbításával foglalkozik.
1
26.B
26.B
Integrált áramkör Az integrált áramkörben a különbözı rendeltetéső aktív és passzív áramkör építıelemeket, valamint a hozzájuk tartozó összekötéseket egyetlen gyártási folyamatban közös félvezetı alapon állítják elı.
Számrendszerek (decimális, bináris, hexadecimális) A súlyozás k
A súlyozást az alapszám hatványa adja: a k helyértékő számjegy súlyozása r . A legnagyobb helyiértékő szám a bal, legkisebb helyiértékő pedig a jobb oldalon van.
Egészrész A vesszı a szám egészrészét és törtrészét választja el. A szám törtrésze, amely a vesszıtıl jobbra található, és sohasem nagyobb 1-nél. A szám értékét úgy is lehet tekinteni, mint számjegyeinek súlyozott összegét.
Együttható 0 és r-1 közötti értékeket felvevı szám.
Helyiértékek A negatív helyiértékek száma, ez a szám adja meg a legkisebb helyiértéket. A pozitív helyiértékek száma, ez a szám adja meg a legnagyobb helyiértéket.
Kitevı n, n-1, … 1, 0, -1; …-(m-l), -m egész valós számok.
Számok megadása A matematika szabályai szerint egy N számot az r az alábbi fogyó hatványai szerint rendezett többtagú kifejezés (polinom) ad meg:
N = ± Σ +k =j − m a k ⋅ r k vagyis,
N = a n ⋅ r n + a n −1 ⋅ r n −1 + ... + a1 ⋅ r 1 + a 0 ⋅ r 0 + a −1 ⋅ r −1 + a −(m−1) ⋅ r − (m −1) + a − m ⋅ r − m ahol: r: (radix) a számrendszer alapja vagy alapszáma, egy természetes szám, ak: együttható: 0 és r-1 közötti értékeket felvevı számok, k: kitevı: n, n-1, … 1, 0, -1; …-(m-l), -m egész valós számok, m: a negatív helyiértékek száma, ez a szám adja meg a legkisebb helyiértéket, j: a pozitív helyiértékek száma, ez a szám adja meg a legnagyobb helyiértéket. Az N számot szimbolikusan a következıképpen szokás írni:
N = a n , a n −1 ...a1 , a 0 , a −1 ...a − m , a −(m −1) , a − m . Számrendszer A hétköznapi életben a tízes (decimális) számrendszert használjuk. A számábrázoláshoz a 0-tól 9-ig terjedı tíz számjegyet használjuk. A kettes vagy bináris számrendszer alapja r = 2, és csak két elemet használ a számok ábrázolásához. A kettes számrendszer számjegyei (bitjei) 0 és 1. Legegyszerőbben a kétállapotú áramkörökkel felépített elektronikus számítógépekben alkalmazható. A hexadecimális (tizenhatos) számrendszer alkalmazása leginkább a digitális technikában és a mikroszámítógépeknél elterjedt. A hexadecimális számrendszernek az alapszáma 16. A számábrázoláshoz szükséges 16 számjegy közül az elsı 10 a decimális számrendszer 0-tól 9-ig terjedı számjegye. A következı 6 számjegyet (10-tıl 15-ig) A, B, C, D, E és F betőszimbólumok jelölik.
A decimális számrendszer A hétköznapi életben a tízes (decimális) számrendszert használjuk. A számábrázoláshoz a 0-tól 9-ig terjedı tíz számjegyet használjuk.
2
26.B
26.B
A tízes számrendszer A tízes számrendszer alapja, amint az elnevezése is mutatja, r = 10. A számábrázoláshoz a 0-tól 9-ig terjedı tíz számjegyet használjuk.
N = ± Σ +k =j − m a k ⋅ 10 k Számábrázolás A szám ábrázolása a tízes (decimális) számrendszerben:
N = a n ⋅ 10 n + a n −1 ⋅ 10 n −1 + ... + a1 ⋅ 101 + a 0 ⋅ 10 0 + a −1 ⋅ 10 −1 + a −(m −1) ⋅ 10 − (m −1) + a − m ⋅ 10 − m Szimbolikus ábrázolás Az N = 3167,5928 szám szimbolikus ábrázolása a tízes (decimális) számrendszerben:
N = 3 ⋅ 10 3 + 1 ⋅ 10 2 + 6 ⋅ 101 + 7 ⋅ 10 0 + 5 ⋅ 10 −1 + 9 ⋅ 10 −2 + 2 ⋅ 10 −3 + 8 ⋅ 10 −4 A bináris számrendszer Ez a számrendszer alkalmazható legegyszerőbben a kétállapotú áramkörökkel felépített elektronikus számítógépekben. Egy adott bináris szám értékét a
N = ±Σ +k =j − m a k ⋅ 2 k kifejezés adja meg, ahol a = 0 vagy 1.
A bit elnevezés A bit elnevezés a bináris számjegy angol megfelelıjének - binary digit – rövidítése.
A kettes számrendszer A kettes számrendszer számjegyei (bitjei) 0 és 1. A kettes vagy bináris számrendszer alapja r = 2, és csak két elemet használ a számok ábrázolásához.
Számábrázolás Egy adott bináris szám értékét a
N = ±Σ +k =j − m a k ⋅ 2 k kifejezés adja meg, ahol a = 0 vagy 1. Jelölése:
N = a n ⋅ 2 n + a n −1 ⋅ 2 n −1 + ... + a1 ⋅ 21 + a 0 ⋅ 2 0 + a −1 ⋅ 2 −1 + a −(m −1) ⋅ 2 − (m −1) + a − m ⋅ 2 − m Számok átváltása A decimális szám kettes alapszámmal való sorozatos osztása után keletkezı maradékok adják az adott szám bináris megfelelıjét. Az eljárást az alábbi példa szemlélteti: Legyen az átalakítandó decimális szám 27. A bináris számot a lentrıl felfelé olvasott maradékok képezik. Tehát 2710 = 110112. Ezzel a módszerrel azonban csak az egész decimális számokat lehet binárissá átalakítani.
Számok átváltása A bináris számrendszerbıl a decimálisba való átalakítás: 10011,0112 = 19,37510 ahol az indexben szereplı szám a számrendszer alapját jelzi.
Szimbolikus ábrázolás N = 10011,011 esetén a szimbolikusan felírt bináris szám értéke:
N = 1 ⋅ 2 4 + 0 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 21 + 1 ⋅ 2 0 + 0 ⋅ 2 −1 + 1 ⋅ 2 − 2 + 1 ⋅ 2 −3 = 16 + 2 + 1 +
1 1 + = 19,375 4 8
Törtek A tizedes törtek bináris törtekké való átalakítása a kettes alapszámmal történı sorozatos szorzáson alapul. Az eredmény átvitt mennyisége, vagyis az egész rész képezi a bináris törtet. Legyen például az átalakítandó tizedes tört 0,3125. A bináris törtet az átviendı mennyiségek nyíl irányában való felírása fejezi ki, vagyis 0,312510 = 0,10012.
3
26.B
26.B
Elıjel Egy pozitív bináris szám lehet pozitív vagy negatív éppen úgy, mint egy decimális szám. A számítógépekben az elıjel (+ plusz, - mínusz) ábrázolása is csak 0 és 1 szimbólumokkal valósulhat meg, úgy, hogy a plusznak 0, a mínusznak 1 felel meg. Ez az úgynevezett elıjelbit, amely után következik a szám abszolút értéke. A táblázat szemlélteti a 4-bites, elıjel és abszolút érték ábrázolású bináris számokat, valamint azok decimális megfelelıjét. Például ha egy n bites pozitív egész szám szimbolikus jelölése: N=0an-2an-3...a1a0, akkor az azonos abszolút értékő negatív számé: -N=1an-2an-3...a1a0.
Pozitív és negatív négybites bináris számok Kiegészítıs számábrázolás A pozitív és negatív bináris számok egy másik fontos ábrázolása az 1-es kiegészítıs számábrázolás vagy más nevén az 1-es komplemens. Ennek a legfontosabb jellemzıi: • •
A pozitív számok ábrázolása megegyezik az elıjeles abszolút érték számábrázolásával. Egy negatív szám az azonos abszolút értékő pozitív szám komplemense (1-es kiegészítıje).
Nézzünk meg egy példát az 1-es komplemens képzésére! Ha egy n bites pozitív egész szám
N P = 0a n − 2 a n −3 ..a1 a 0 , akkor az azonos abszolút értékő negatív szám
N Q = 1a n − 2 a n −3 ..a 1 a 0 Az elıjelbit
(
)
− 2 n −1 − 1
súlyozásával megkaphatjuk az 1-es komplemenső bináris szám valós értékét. A számítógép mőködése leegyszerősödik, ha az elıjelbit súlyozása megfelel az elıjel nélküli n-bites bináris szám legnagyobb helyértékő bitjének kijáró
2 n −1 − 1 súlyozásával. (1)
(1)
Az NP pozitív szám, valamint az NQ negatív szám értéke ezzel a súlyozással legyen Np , illetve NQ . A pozitív szám esetén, ha összevetjük a szimbolikus alakokat, valamint a számrendszerek leírására használt polinomot, akkor a kétféle kifejezés megegyezik:
4
26.B
26.B
(1)
Np = NP. A negatív szám meghatározásához használjuk fel, hogy
a k + a k = 1 , ahol k = n - 1, n - 2, n - 3, …1, 0. Ebbıl (1)
Np
+ NQ
(1)
Ez alapján és az (1)
NQ
n
n
=111…11 = 100…00-1 = 2 -1 (1) Np
= NP összefüggést figyelembe véve felírhatjuk a negatív számot is:
= 2 -1-NP.
Kiegészítıs számábrázolás A pozitív és negatív bináris számok legelterjedtebb ábrázolása a 2-es kiegészítıs számábrázolás vagy más nevén a 2-es komplemens. A pozitív számok ábrázolása azonos az elıjeles abszolút érték és az 1-es komplemens számábrázolásával. A negatív számok ábrázolása 1-es komplemensbıl származik 1 hozzáadásával. Nézzünk meg egy példát a 2-es komplemens képzésére is! Ha egy n bites pozitív egész szám
M P = 0a n − 2 a n −3 ..a1 a 0 akkor az azonos abszolút értékő negatív szám kiszámítható az
M Q = 1a n − 2 a n −3 ..a 1 a 0 A 2-es komplemenső szám valós értéke az elıjelbit –(2n-1) súlyozásával kapható meg. Ha a számítógép az elıjelbit (2)
(2)
–(2n-1) súlyozását alkalmazza, akkor legyen az Mp és MQ számok értéke Mp valamint MQ . A pozitív szám esetén, ha összevetjük a szimbolikus alakokat, valamint a számrendszerek leírására használt polinomot, akkor a kétféle kifejezés megegyezik: (2) Mp = Mp. Negatív szám esetén az 1-es komplemens képzéséhez hasonlóan levezethetı, hogy: (2) MQ = 2n-Mp.
A hexadecimális számrendszer Gyakori a hexadecimális (tizenhatos) számrendszer alkalmazása például a digitális technikában és a mikroszámítógépeknél. A hexadecimális számrendszernek az alapszáma 16.
A hexadecimális számjegyek és bináris megfelelıik
5
26.B
26.B
A tizenhatos számrendszer A hexadecimális számrendszernek az alapszáma 16. A számábrázoláshoz szükséges 16 számjegy közül az elsı 10 a decimális számrendszer számjegye, a következı 6 számjegyet pedig betőszimbólumok jelölik.
Számábrázolás A számábrázoláshoz szükséges 16 számjegy közül az elsı 10 a decimális számrendszer 0-tól 9-ig terjedı számjegye. A következı 6 számjegyet (10-tıl 15-ig) A, B, C, D, E és F betőszimbólumok jelölik, ezért a hexadecimális számábrázolást alfanumerikus számábrázolásnak is nevezzük.
Számok átalakítása hexadecimálisból binárisba A mikroszámítógépek alkalmazásánál nagyon fontos a hexadecimális bináris és a bináris hexadecimális átalakítás is. A hexadecimális-bináris konverzió esetében, a polinom alapján és az
rk = 16 k = 2 4.k egyenlıség figyelembevételével, a hexadecimális szám külön minden számjegyét át lehet alakítani 4-bites bináris számmá. Például a D3B hexadecimális számot így lehet kifejezni:
(
)
(
)
(
D 3B = 1 ⋅ 2 3 + 1 ⋅ 2 2 + 0 ⋅ 21 + 1 ⋅ 2 0 ⋅ 2 8 + 0 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 21 + 1 ⋅ 2 0 ⋅ 2 4 + 1 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 2 2 + 1 ⋅ 2 0 ez másképpen
D3B = 1 ⋅ 211 + 1 ⋅ 210 + 0 ⋅ 2 9 + 1 ⋅ 2 8 + 0 ⋅ 2 7 + 0 ⋅ 2 6 + 1 ⋅ 2 5 + 1 ⋅ 2 41 ⋅ 2 3 + 0 ⋅ 2 2 + 1 ⋅ 21 + 1 ⋅ 2 0 amely szimbolikusan így írható: D3B16=1101001110112 A levezetés alapján megállapítható, hogy egy hexadecimális szám bináris megfelelıjét úgy kaphatjuk meg, hogy a hexadecimális szám minden számjegyét külön átalakítjuk négybites bináris számmá, amelyeket azután a megfelelı sorrendben egymás mellé írunk.
Számok átalakítása binárisból hexadecimálisba A bináris-hexadecimális átalakítás a hexadecimális-bináris konverzió fordítottja. A bináris számot jobbról balra 4-bites csoportokba, ún. tetrádokba (angolul: nibble) osztjuk, ahol természetesen a legnagyobb helyértékő csoport kevesebb számjegybıl is állhat. Ezután a tetrádok hexadecimális megfelelıit az adott sorrendben egymás mellé írjuk. Például alakítsuk át az 1011011100 bináris számot hexadecimálissá! 10 1101 11002=2DC16 A digitális technikában, például a mikroszámítógépekben az információ bitszáma rendszerint 4 többszöröse (4, 8, 12, 16, 24, 32, 40, 48). A bináris-hexadecimális és a fordított átalakítási eljárás egyszerősége miatt is célszerő a hosszú bináris számokat a négyszerte rövidebb hexadecimális megfelelıjükkel ábrázolni. Bájt-nak (byte) nevezzük azt az információt, amelynek kifejezésére csak két hexadecimális számjegy szükséges, és 8 bitet foglal magába.
Számok átalakítása decimálisból hexadecimálisba A decimális-hexadecimális átalakításnál a decimális számot az alapszámmal, vagyis 16-tal sorozatosan el kell osztani. Az osztás után keletkezı maradékok adják az adott szám hexadecimális megfelelıjét. Az eljárást ismét egy példa szemlélteti: - legyen az átalakítandó decimális szám 974. A hexadecimális számot a lentrıl felfelé olvasott maradékok képezik. Tehát 97410=3CE16.
Számok átalakítása hexadecimálisból decimálisba A hexadecimális-decimális konverzió a számrendszer jelölése alapján végezhetı el:
N = ±Σ +k =j − m a k ⋅ 16 k vagyis Például
FC 716 = F ⋅ 16 2 + C ⋅ 161 + 7 ⋅ 16 0 = 15 ⋅ 16 2 + 12 ⋅ 161 + 7 ⋅ 16 0 = 403910 . Az információ kódolása Információ Az információ valamely jelenségre vonatkozó értelmes közlést jelent, amelynek általában az új ismereteket szolgáltató része fontos a felhasználó részére. Általános megfogalmazásban az információ bizonyos fokú tájékozatlanságot szüntet meg. Az információ szimbólumok sokaságából áll. Ezek a szimbólumok lehetnek: • • •
6
az emberi beszéd esetén hangok, az írás esetében betők, a digitális áramkörök vagy számítógép esetében számjegyek.
)
26.B
26.B
Adat Az adat az információnak a digitális rendszerekben (pl. számítógépes rendszerekben) való konkrét megjelenési formája.
Kód A logikai áramkörök, logikai berendezések mindig kódolt információt fogadnak, dolgoznak fel és szolgáltatnak. A kód valamilyen információ kifejezésére, hordozására szolgáló rendszer.
Kódszavak Egy szimbólumhalmaz meghatározott rendszere alkotja a kódot, amelyet kódszavak alkotnak (a szimbólumhalmaz elemeibıl alkotott szimbólumsorozat). Egy kódszó egy karaktert definiál (a karakter görög eredető szó, jelentése jel, írásos szimbólum). Ilyen karakter lehet például bető, számjegy, írásjel és más, az információt teljessé tevı jel. A kódszavak lehetnek
• •
fix szóhosszúságúak és változó szóhosszúságúak.
A kódszavak képzésében többféle szimbólum fordulhat elı. Ennek megfelelıen egy kód karakterkészlete szerint két fı csoportot különböztethetünk meg:
• •
numerikus kódokat, amelyek karakterkészlete csak számokat tartalmaz, alfanumerikus kódokat, amelyek karakterkészlete számjegyeket, betőket, és írásjeleket is tartalmaz.
Kódolás Kódolásnak nevezzük két szimbólumhalmaz egymáshoz rendelését.
A különbözı kódok összefoglalása I.
A különbözı kódok összefoglalása II. Információ átvitele A kódolt információk átvitele alapján megkülönböztethetünk: • •
soros átvitelt, párhuzamos átvitelt.
Bináris kódolású számrendszerek Számítógép számrendszere A számítógép számára a tízes számrendszerben kifejezett adatokat a bevitelnél bináris számrendszerbe kell átalakítani. Szintén bináris számrendszerben adja meg a számítógép az eredményeket is, amelyeket azután át kell alakítani decimális számrendszerbe
BCD-kód Kis teljesítményő számítógépek esetén az adatok átalakítása rendszerint több idıt vesz igénybe, mint az adatfeldolgozás. Az átalakítás megkönnyítése végett nem az egész decimális számot alakítják át bináris számmá, hanem
7
26.B
26.B
helyiértékenként alakítják át binárissá. Ezt, binárisan kódolt decimális (BCD - Binary Coded Decimal) kódnak nevezzük. Minden decimális számjegyet egy négyjegyő bináris szám ábrázol.
Természetes BCD-kód A természetes BCD-kód a legelterjedtebb. Ebben a kódban a decimális számokat a megfelelı négybites bináris szám 0
1
2
3
ábrázolja. A számjegyek súlyozása 2 , 2 , 2 , 2 vagyis 1, 2, 4, 8. Ezért ezt 1248 súlyozású BCD-kódnak is nevezik.
Aiken-kód 1242 súlyozású BCD-kódot Aiken-kódnak is nevezik:
• •
0 és 4 közötti decimális számokat a megfelelı bináris számok, 5 és 9 közötti decimális számokat pedig a 11-tıl 15-nek megfelelı tetrádok ábrázolják.
9-es komplemens Az Aiken-kód elınye a kilences komplemens képzése egyszerő bitenkénti komplementálással. A 9-es komplemens hasonló az 1-es komplemenshez.
Decimális szám 9-es komplemense Egy decimális szám 9-es komplemense:
• •
ha a szám pozitív, akkor azonos az adott számmal, ha a szám negatív, akkor az abszolút értékének összege a 9-es komplemenssel 9-et eredményez.
A 9-es komplemens jelentısége a BCD-kódolású számok kivonásánál nyilvánul meg.
Stibitz-kód A Stibitz-kód (háromtöbbletes kód vagy Excess 3-kód) is hasonló elınyös tulajdonsággal rendelkezik a 9-es komplemens képzésénél, mint az Aiken-kód. A háromtöbbletes kód tetrádjai az 1248 súlyozású BCD-kód tetrádjainál hárommal nagyobbak.
Számok összeadása A BCD kódolású számok összeadása valamelyest eltér a tiszta bináris számok összeadásától. Abban az esetben, ha egy decimális helyiérték összeadásának eredménye 9-nél nagyobb, vagy átvitel keletkezik, akkor ahhoz, hogy helyes eredményt kapjunk, a helyiértékhez 6-ot kell hozzáadni. Ellenkezı esetben nincs szükség erre a mőveletre.
Ciklikus permutáció Vizsgáljuk meg a decimális 7-bıl (0111) a 8-ba (1000) való átmenetet! Bár sorrendben a 7 után a 8 következik, a bináris kódban 4 bit változik. Ha valamelyik átmenet a tőrések miatt hamarabb változik meg, mint a többi, akkor a bináris számok sorrendje már nem egyezik a valóságos decimális számok sorrendjével. Ezt a hibát küszöbölik ki a ciklikusan permutált kódok, amelyeknél csak egy bit változik meg egy egy egységnyi decimális szám megváltozására.
Gray-kód A legismertebb ciklikusan permutált kód a Gray-kód. A Gray-kód a legkisebb helyértékő számjegyek szimmetriatengelyek körüli sorozatos tükrözésébıl származik, mindig 1-gyel növelve a tükrözött helyértékeket.
Johnson-kód A Johnson-kód a Gray-kódhoz hasonló ötbites kód, amelynek jellemzıje, hogy mindig csak egy elemben tér el két szomszédos kódszó.
Ötbites kód Az ötbites kódnál mindig csak egy elemben tér el két szomszédos kódszó.
Hamming-kód A Hamming-kód egy különleges bináris kód: bináris adatátvitel során hibajavításra alkalmas.
Digitális adatok ellenırzése és javítása Redundancia A digitális rendszerekben az átviteli vezetékekre és a tárak területére zavarok hatnak. A bináris helyiértékekben emiatt keletkezı változások az információban hibát okoznak. Ahhoz, hogy ilyen hibákat felismerjünk, és adott esetben javíthassunk, a hasznos információt ellenırzı információval kell kiegészíteni. Erre azt mondjuk, hogy a kód redundanciáját növeljük, vagyis túlhatározottá tesszük.
8
26.B
26.B
Az információ többszöri ismétlése is lehetne jó megoldás, de kimutatható, hogy nem eléggé hatékony. Egy ilyen redundáns információ (kódszó) tehát két részbıl áll:
• •
hasznos információt hordozó bitekbıl, nem hasznos információt hordozó bitekbıl, vagyis redundancia bitekbıl.
Kódrendszerek Az így kialakított kódrendszerek két csoportba sorolhatók:
• •
hibaellenırzı kódrendszerek - EDC(angolul kifejezve: error detecting code), hiba-javító kódrendszerek - ECC(angolul kifejezve: error correcting code).
Hamming-féle távolság A redundáns kód Hamming-féle h távolsága a kódszóban felismerhetı illetve korrigálható hibák számának mértéke. A Hamming-távolságot a kódszavakra és a kódra egyaránt értelmezhetjük.
Hamming-távolság Két kódszó Hamming-távolsága: az egyik kódszó hány elemét kell megváltoztatni, ahhoz, hogy a másik kódszóval megegyezzék.
Kód Hamming-távolsága: - a kódot alkotó kódszavak közötti legkisebb Hamming-távolság.
Hibaellenırzı kód Paritás bit A redundancia legegyszerőbb gyakorlati formája a paritás ellenırzı bit (paritás-bit) használata. Egy n bitbıl álló kódszóhoz egy újabb bitet is hozzáadnak. A paritás-bit az információ érdemi részében található logikai 1-ek páros vagy páratlan számáról szolgáltat információt. A paritás-bit értékét úgy határozhatjuk meg, hogy az eredeti kódszóban a bitek számértékét összeadjuk és a paritás bittel: • •
vagy párosra ("even parity") vagy páratlanra ("odd parity") egészítjük ki.
A táblázat bináris kódok paritás-bittel való kiegészítését szemlélteti. • • •
A paritásbit itt az egyesek számát párosra egészíti ki. Megfigyelhetı, hogy a kód Hamming-távolsága h = l-rıl h = 2-re változott. Ezzel egy 1 bites hibát fel lehet ismerni, de nem lehet javítani, mert a hibás bit nem lokalizálható.
A paritás-bit használatával minden - az információtartalomban bekövetkezı - páratlan számú meghibásodást észlelhetünk.
Hibaellenırzés A redundancia legegyszerőbb gyakorlati formája a paritás ellenırzı bit (paritás-bit) használata. A paritás-bit alkalmazási módja:
• •
Az információ elküldésénél, elrakásánál képezzük a paritásbitet, amit szintén elküldünk vagy elrakunk. A felhasználásnál az információs bitek alapján újraképezzük a paritásbitet és egybevetjük azzal, ami eredetileg volt. Ha ezek megegyeznek, akkor tudjuk, hogy vagy nem következett be hiba, vagy pedig páros számú bithiba fordult elı.
9
26.B
26.B
Párhuzamos adatátvitel ellenırzése paritásbittel Hibajavító kód Példa a hibajavításra A hibajavító képességő kódrendszerek elvének ismertetésére a Hamming-féle kód egy egyszerő változatát mutatjuk be, mely 4 információs bithez 3 speciálisan képzett paritás bitet ad, és ennek következtében egy hiba helye megállapítható. A kódolás a következıképpen történik: Az X1, X2, X3, X4 információs bitekbıl X5, X6, X7 paritás-biteket képezünk a következı szabály szerint:
X1 + X 2 + X 3 + X 5
páros legyen,
X1 + X 2 + X 4 + X 6
páros legyen,
X1 + X 3 + X 4 + X 7
páros legyen.
Ennek megfelelıen például az 1010 információ paritás-bitekkel kibıvítve: 1010010 lesz. Az információ vételekor tehát az X1, X2, X3, X4 információs bitekbıl a fenti szabály szerint P5, P6, P7 értékekkel összehasonlítjuk. A hiba helyének megállapítását a táblázat mutatja, de ha a hibás bitek száma egynél több, a rendszer helytelenül fog javítani.
Háromelemes kódtábla Hibajavító kódok A hibajavító kódok jellemzıi: •
Ha n információs bithez k paritás bitet adunk, és a kódrendszer egy hibát tud javítani, akkor a következı egyenlıtlenségnek kell fennállnia:
2 k ≥ (n + k ) + 1 •
10
A paritás bitnek meg kell mutatnia a hibás bitet, amelyik lehet információs bit, vagy akár paritás bit is. Természetesen a hibamentes állapotot is jeleznie kell.
