10. ELİADÁS
DIGITÁLIS TECHNIKA I
1. A jelterjedési idık hatása a kombinációs hálózatok mőködésére
Dr. Pıdör Bálint BMF KVK Mikroelektronikai és Technológia Intézet
2. Kódok: hibajelzés és javítás 10. ELİADÁS
2008/2009 tanév 1. félév 1
A JELTERJEDÉSI IDİK HATÁSA A KOMBINÁCIÓS HÁLÓZATOK MŐKÖDÉSÉRE
A JELTERJEDÉS KÉSLELTETÉSE
Összefoglaló néven: hazárdok.
Ideális helyzet: a kapuk a bemeneteikre jutó jelek megérkezésével egyidejőleg állítják elı a kimeneti jelértéket, és a kapuk közötti összekötetéseken a terjedéshez nem kell idı.
1. Statikus hazárd. 2. Dinamikus hazárd. 3. Funkcionális hazárd.
Reális helyzet: a kapuk a kimeneti jeleket csak késéssel állítják elı, és az összekötetéseken a jel terjedési sebessége véges, ez további késleltetést okoz.
Rövid, de jól érthetı leírás: http://e-oktat.pmmf.hu/digtech32 Teljes részletességgel: Arató 101-114 old.
2
3
A JELTERJEDÉSI KÉSLELTETÉS HATÁSA A MŐKÖDÉSRE
4
A JELKÉSLELTETÉS OKAI
A késleltetı hatások átmenetileg hibás kimeneti kombinációkat hozhatnak létre. A hibák elıfordulása a környezeti változóktól: hımérséklet, öregedés, stb. függhet, így elızetesen nem vehetık számításba. Az ilyen véletlenszerő, rendszertelen hibajelenségeket neve hazárdjelenség. Tervezéskor arra kell törekedni, hogy a kombinációs hálózat mőködése a lehetı legnagyobb mértékben független legyen a késleltetési viszonyok alakulásától. 5
1. Megvalósított kapu: a kimeneti jel értéke rövid, de véges idı alatt változik meg. A kimeneti jel új értékének eléréséhez szükséges idı: megszólalási idı (angol propagation delay). 2. Összekötetések: EM hullámok véges terjedési sebessége, illetve a szórt kapacitások és induktivitások okozta késleltetés.
6
A KAPUK KÉSLELTETİ HATÁSA bemenıjel 1
X
X
HAZÁRDJELENSÉGEK
t
idális kimenıjel
HAZÁRD a kimeneten „0” vagy „1” impulzus nem a logikai feltétel hatására keletkezik. A késleltetések gyakran váratlan feltételektıl (pl. melegedés) is függhetnek, ezért nem mindig tartható kézben. HAZÁRD TÍPUSOK Sztatikus hazárd „0”-ás típusú hazárd „1”-es típusú hazárd
valóságos kimenıjel ∆ X
1
&
X
F = X⋅X = 0
1
1 F = X + X =1
X X
∆X
Dinamikus hazárd Funkcionális hazárdok
Fid Fval
7
JELKÉSLELTETÉS, STATIKUS HAZÁRD
8
KÉSLELTETÉS, STATIKUS HAZÁRD
BE Az Yki kimenet mindig 1 (H-szint) mivel a bemenı jel ellenfázisban vezérli az Y1 és Y2 kimenetet adó NAND kapukat. A három sorbakapcsolt inverter az egyik ágon késlelteti a jelet, így Y2 még akkor is 1, mikor már Y1 is elérte az 1-et. Így rövid idıre Yki 0 állapotba kerül (L szintő tőimpulzs). 9
Y1 Y2 KI
10
STATIKUS HAZÁRD KOMBINÁCIÓS HÁLÓZATBAN
RACE HAZARD
—
F(ABC) = AB + AC _ ABC = 111 → ABC = 011
1 cm = 100 nsec
Ha
Statikus hazárd (negatív impulzus, kb. 40 nsec)
∆t1+∆t3 < ∆t4+∆t6 A • B a kimeneten
(hallgatói mérés)
1→0→1 lép fel !
&
1 C
11
∆t1
∆t3 F
1
∆t4 &
∆t6 12
STATIKUS HAZÁRD KOMBINÁCIÓS HÁLÓZATBAN
STATIKUS HAZÁRD KIKÜSZÖBÖLÉSE (1)
—
C 1 1 1
1
F(ABC) = AB + AC
C
Kritikus átmenet: _ ABC = 111 → ABC = 011 A & B B •
1 1
1 C
—
B F(ABC) = AB + AC + BC F
1
A
A statikus hazárd kiküszöbölése: meg kell akadályozni a kritikus átmenet hatását, ehhez a BC prímimplikánst is le kell fedni.
&
1 A
1 Kritikus átmenet: _ ABC = 111 → ABC = 011
13
STATIKUS HAZÁRD KIKÜSZÖBÖLÉSE (2)
STATIKUS HAZÁRDTÓL MENTES HÁLÓZATOK
C 1
A B
•
1 1
&
1 B C
&
14
1
F
1
A kétszintő ÉS-VAGY hálózat csak akkor mentes a statikus hazárdtól, ha az 1 kimeneti értéket elıállító bemeneti kombinációk közül bármely két szomszédoshoz található legalább egy olyan ÉS kapu, melynek kimenete mindkét szomszédos bemeneti kombináció esetén 1 értékő. Máskép: bármely két szomszédos mintermhez található legalább egy olyan prímimplikáns, mely mindkét mintermet lefedi.
A & 15
STATIKUS HAZÁRDTÓL MENTES HÁLÓZATOK TERVEZÉSE
16
STATIKUS HAZÁRD KONJUNKTÍV HÁLÓZATBAN
Tervezési iránymutatás: A legegyszerőbb hazárdmentes diszjunktív alak úgy hozható létre, hogy a legegyszerőbb diszjunkítv alakot kiegészítjük a lehetı legkevesebb és legegyszerőbb prímimplikánssal a szükséges lefedési feltétel kielégítésére.
17
Az elızı analízis a kétszintő VAGY-ÉS hálózatokra is érvényes. A módosítás csak annyi, hogy a 0 kimeneti értéket elıállító szomszédos bemeneti kombinációkat kell vizsgálni, és szükség esetén a közös lefedést biztosító VAGY kapukat emgvalósítani.
18
KARNAUGH TÁBLA
PÉLDA: KÉTSZINTŐ HÁLÓZAT HAZÁRDMENTESÍTÉSE
___ _ _ F(A,B,C,D) = B D + A B C + A C D + B C D
Adja meg az
C
___ _ _ F(A,B,C,D) = B D + A B C + A C D + B C D
1
legegyszerőbb diszjunktív alakban adott függvénnyel leírt kombinációs hálózat kétszintő ÉS-VAGY alakú statikus hazárd mentes elvi logikai rajzát.
1
1
1
1
1
1
B A
Vizsgálja meg a NAND kapus megvalósítást. (7400 4x2 bemenet, 7420 2x4 bemenet, 7430 1x8 bement).
1 D
19
POTENCIÁLIS HAZÁRDOK
20
HAZÁRDMENTESÍTÉS
___ _ _ F(A,B,C,D) = B D + A B C + A C D + B C D
___ _ _ F(A,B,C,D) = B D + A B C + A C D + B C D C 1
1
C Három átmenetnél léphet fel hazárd:
1
1
1
1 1
1
1
0001↔0101
1
1
1
1010↔1011
B A 1
D
B A 1
1
D
21
ÖSSZEFOGLALÓ
22
REALIZÁLÁS NAND KAPUKKAL
___ _ _ F(A,B,C,D) = B D + A B C + A C D + B C D A négy (lényeges) prímimplikánsával realizálható minimális hálózatot a hazárdmentesítéshez további három redundás prímimplikánssal kell kiegészíteni, ezek az alábbiak: _ _ _ __ _ A C D, A B C, A B D A hazárdmentes hálózat 1 kétbemenető ÉS, 6 hárombemenető ÉS, valamint 1 hétbemenető VAGY kapuból áll.
A hazárdok eliminálásához három újabb hurok szükséges
1
0000↔0010
1
1
1
23
Realizálás NAND kapukkal: (ÉS-VAGY ⇒ NAND-NAND) Minimális hálózat: 7400 (4x2 bemenet) 7420 (2x4 bemenet) 7430 (1x8 bemenet) Hazárdmentes hálózat: 7400 (4x2 bemenet) 7420 (2x4 bemenet) 7430 (1x8 bemenet)
1/4 1 1/2 1 1/4 3 1 24
STATIC RACE HAZARDS
PRÍMIMPLIKÁNSOK: SZÁMÍTÓGÉPPEL
K maps are useful for detecting and eliminating race hazards.
C 1
1
1
1
_ An additional term BC would eliminate the potential race hazards, B bridging between the green and blue output state or blue and red output states.
1 A 1
1 D
25
ELIMINATION OF RACE HAZARDS C 1
1
1
1 1
A 1
1
1
26
DINAMIKUS HAZÁRD
_ An additional term BC eliminates the potential race hazards, bridging between the green and blue output state or blue and red output states. B The term is redundant in terms of the logic state of the system, but such redundant terms are often needed to assure race-free dynamic performance.
D
1
Dinamikus hazárd az a jelenség, ha egyetlen bement megváltozásakor egy egyszerő kimeneti változást kellene kapni (pl. be: 1⇒0, kimenet 0 ⇒1, de ehelyett egy többlet többlet ugrással áll be az állandósult kimenet (pl. 0 ⇒1 ⇒0 ⇒1).
27
28
DINAMIKUS HAZÁRD ÉS KIKÜSZÖBÖLÉSE
FUNKCIONÁLIS HAZÁRD Akkor fordulhat elı, ha két vagy több bemeneti változó egyszerre változik, pl. 101⇒110. Két lehetséges idıbeli sorrend lehetséges, és így a kimeneten rövid idıre a 0 állapot is felléphet.
A jelenség három- vagy többszintő hálózatokban léphet fel, és csak akkor, ha valamelyik szinten statikus hazárd van. Az egyes szinteken felléphetı statikus hazárdok kiküszöbölésével tehát a dinamikus hazárd is kiküszöbölhetı.
B
C
A
1
0
0
0
1
1
1
1⇒ ⇒1 29
B
C
0
A
B
C
0
1
0
0
0
1
1
1
1⇒ ⇒0⇒ ⇒1
A
0
1
0
0
0
1
1
1
1⇒ ⇒1⇒ ⇒1 30
FUNKCIONÁLIS HAZÁRD KIKÜSZÖBÖLÉSE A funkcionális hazárd kiküszöbölésének legbiztosabb módja az, ha nem engedjük meg a nem szomszédos változásokat. Ezt a bemeneti kombinációkat elıállító egységben kell megvalósítani.
KÓDOK: HIBAJELZÉS ÉS HIBAJAVÍTÁS
A másik lehetıség órajel használata és szinkronizálás. 31
HIBAJELZÉS ÉS HIBAJAVÍTÁS
32
HAMMING TÁVOLSÁG Két kódszó Hamming távolságát úgy határozzák meg, hogy a két kódszó azonos helyen álló elemeit összehasonlítják, és megállapítják hány helyen áll különbözı bit. Az így kapott szám a Hamming távolság.
Hibajavítás: hiba felismerés illetve hiba javítása. Redundancia szükésges a kódban. Legegyszerőbb eset: bit-hiba jelzése Elv: a hiba akkor deríthetı fel, ha a kódszó készletben bármely két kódszó között a Hammingtávolság legalább kettı, vagy nagyobb.
33
SPECIÁLIS KÓDOK DECIMÁLIS SZÁMJEGYEKHEZ 5-bıl 2-es kód (másnéven kvináris kód) illetve a hasonló bikvináris és kvibináris kód sajátossága hogy mindegyik kódszóban két 1-es van. Ez bizonyos hibavédettséget jelent, de a kódszavak redundásak. A bikvináris, illetve kvibináris kód hét bites. A bikvináris kód elsı két bitje 0 1 vagy 1 0, a súlyozásuk pedig 5, illetve 1. A fennmaradó 5 bitbıl midig négy 0 és egy 1, a súlyozásuk pedig rendre 4,3,2,1,0. Pl. 3(dec) → 0101000 6(dec) → 1000010 35
A Gray kód pl. bármely két szomszédos kódszava csak egy bitben különbözik, ezért a Gray kód Hamming távolsága 1. A BCD és a bináris kód (legkisebb) Hamming távolsága szintén 1.
34
SPECIÁLIS BCD KÓDOK
36
HIBAJELZÉS: HAMMING TÁVOLSÁG MESTERSÉGES MEGNÖVELÉSE
HIBAJELZÉS: PARITÁSBIT
Hamming-távolság növelése:
Paritásbit: a minimális Hamming távolság kettı lesz. Ekkor 1 bit hiba észlehetı.
- többlet bitek hozzáadása; - meg nem engedett kódszavak beiktatása.
Ezt alkalmazzák pl. az ASCII kódban.
Paritásbit hozzáadása: minden olyan kódszó megengedett melyben a paritás páros, amelyben pedig páratlan, az tiltott.
37
38
HIBAFELISMERİ ÉS HIBAJAVÍTÓ KÓDOK
PARITÁSBIT Páros paritás: az 1-esek száma páros. A kódszóban lévı 1-esek számát 1 vagy 0 hozzáadásával párossá egészítjük ki. 0 a paritásbit, ha az 1-esek száma páros volt.
Legegyszerőbb hibafelismerési eljárás: paritásbit átvitele
Páratlan paritás: az 1-esek száma páratlan. A kódszóban lévı 1-esek számát 1 vagy 0 hozzáadásával páratlanná egészítjük ki. 1 a paritásbit, ha az 1-esek száma páros volt.
Két lehetıség Kód Paritásbit páros paritás 11011 páratlan paritás 1 1 0 1 0 39
40
Kódok hibavédelmi képessége
PARITÁS GENERÁTOR Paritásbit képzése: ANTIVALENCIA (XOR) mővelet alkalmazása a kódszó bitjeire, pl. 4 bit esetén háromszor. Példa:
Zaj, zavar Hiba felismerés feltétele:
Kódszó
Paritásbit
0001 0110 1110
0⊕0⊕0⊕1=1 0⊕1⊕1⊕0=0 1⊕1⊕1⊕0=1
Rendeltetési hely
Átvivı közeg
Adatforrás
D≥2
Hiba javítás feltétele:
D≥3
Általánosságban
2k ≥ m + k −1 m információs bithez k ellenırzı bit szükséges 41
42
HIBAFELISMERİ ÉS HIBAJAVÍTÓ KÓDOK
HIBAJAVÍTÓ KÓDOK Tömbátvitel: kereszt és hosszirányban paritásbitek
Hibajavítás (4 + 3):
6
A1 A2 A3 A4 A5 A6 A7
1100110
hibátlan kódszó (6)
0
1110110
hibás kódszó (3. Bit)
0
8
0
4
2
1
X X
0
X
1
1
0
A3 A5 A7 0 1 0
A1=1
A1 A3 A5 A7 1 1 1 0
E0=1
A3 A6 A7 0 1 0
A2=1
A2 A3 A6 A7 1 1 1 0
E1=1
A5 A6 A7 1 1 0
A4=0
A4 A5 A6 A7 0 1 1 0
E2=0
E2 E1 E0 0 1 1 =3
43
8 byte átvitele tömbként, egy bit hiba felfedhetı és kijavítható. 44
HIBAJAVÍTÁS JEL BITEK
ADÓ
VEVİ PARITÁS
PARITÁS BIT PARITÁS
PARITÁS
GEN.
VIZSG.
VÉGE
HIBA JELZİ
A hibajavítást blokkrendszerő adatátvitel esetén SOR és OSZLOP paritás ellenırzésével is elvégezhetjük. Ily módon egyetlen hiba a hibás sor és oszlop metszéspontjában van, így a hiba értékcserével javítható45
46
