2016.11.28.
PÉLDA A LEGEGYSZERŰBB KONJUNKTÍV ALAK KÉPZÉSÉRE
DIGITÁLIS TECHNIKA I
Három négyes és két kettes hurok jelölhető ki. Pl. a felső sorbeli négyes hurok (a peremeken ellentétesnek kell venni a változókat!)
C
Dr. Lovassy Rita Dr. Pődör Bálint Óbudai Egyetem KVK Mikroelektronikai és Technológia Intézet
1
1
B
10. ELŐADÁS 1
1
1
A 1 1
D
(A + B)
1 Maxtermek: a mintermeket tartalmazó K táblából a 0-t tartalmazó cellákat tekintjük, és a peremen a változókat 2 komplementáljuk!
LEGEGYSZERŰBB KONJUNKTÍV ALGEBRAI ALAK
—
——
—
——
—
—
Kódok, kódolás:
—
F=AB + B D+AC D +AC D +B C
alapfogalmak —
—
—
—
F = (A+B)(B+D)(A+C+D)(A+C+D)(B+C) Természetesen ugyanez olvasható ki a Karnaugh táblázatból is. 3
KÓD Code (m)
- francia szó, eredeti szűkebb értelme a rejtjellel kapcsolatos.
Kód
- információ kifejezésének, közlésének, megjelenítésének egyik formája.
Kód
- információt hordozó szimbólumok, - szimbólumokból felépített szavak, - szimbólumok és szavak összekapcsolási szabályai.
Kód
- előírás, mely egyazon információ két ábrázolási formája közötti kapcsolatot adja meg. A hozzárendelésnek nem kell feltétlenül egyértelműen megfordíthatónak lennie.
4
SZIMBÓLUMKÉSZLET Azon elemi jelek összessége melyeket a kódolásra felhasználhatunk. Pl. tízes számrendszer (a mennyiségi információ egyik kódja): - tíz darab számjegy, - tizedesvessző, - előjel, - szóköz. Pl. bináris kód a digitális technikában: - csak két szimbólum, 0 és 1.
5
6
1
2016.11.28.
KÓDSZÓ, KÓDVEKTOR
KÓDSZÓ KÉSZLET Egy rendszerben használt kódszavak összessége.
A szimbólumkészletből alkotott sorozat. Definiálni kell az egyes jelek összekapcsolási, illetve az egyes szavak megkülönböztetésének szabályait.
Pl. egy beszélt nyelvben a használt összes szó. A használt szavak a megengedett, az ”értelmetlen” szavak a tiltott kódszavak.
Kétértékű (bináris) kód: az alkotóelem a bit. A kódszavak különböző hosszúságúak lehetnek.
Pl. szokásos BCD kód: 0111 megengedett, 1011 tiltott kódszó (tetrád, illetve pszeudotetrád).
7
SZÓHOSSZÚSÁG
8
BINÁRIS ÉS NEM BINÁRIS KÓDOK
A kódszóban lévő szimbólumok száma.
Bináris kód – két elemű szimbólumkészlet.
Fix és változó szóhosszúságú rendszerek.
Nem bináris kód – többelemű szimbólumkészlet.
Pl. az emberek személyi számai vagy adószámai fix szóhosszúságú, szokásos neveik pedig változó szóhosszúságú kódszavak.
Gyakorlati megvalósíthatóság: kétállapotú elemek előnyös tulajdonságai – bináris kód.
9
KÓDSZAVAK MAXIMÁLIS SZÁMA
10
HAMMING TÁVOLSÁG
Adott kódban a megkülönböztethető kódszavak maximális száma a szóhosszúságtól és a jelkészlet nagyságától függ. Két azonos szóhosszúságú kódszó HAMMING távolságát (D) úgy számítjuk ki, hogy a két kódszó azonos helyén álló elemeit összehasonlítjuk és megszámláljuk, hogy hány helyen áll különböző bit.
Bináris kód: n – kódszavak hossza, akkor 2n. Pl. n = 8, ekkor 256 kódszó lehet. Lehetőségek: természetes számok 0 - 255 (egyenes kód); előjeles számok -128-től +127-ig (2-es komplemens kód);
11
A kódszókészlet HAMMING távolsága: a kódszó készletelemei közötti legkisebb Hamming távolság.
12
2
2016.11.28.
ADATÁTVITEL
KÓDOLT INFORMÁCIÓ TOVÁBBÍTÁSA
Kódolt információ átvitele: többféle üzemmódban lehet - soros, - párhuzamos, - vegyes.
Soros átvitel
Soros átvitel: csatornák száma kicsi, adatátvitel ideje nagy. Párhuzamos átvitel: egyidejűleg több csatornán. Vegyes üzemmód: a két átvitelfajta valamilyen kombinációja. Az adó és vevőoldali berendezések bonyolultabbak, és költségesebbek.
Párhuzamos átvitel
Vegyes üzemmód
13
14
KÓDOK HIBAVÉDELMI KÉPESSÉGE Rendeltetési hely
Átvivő közeg
Adatforrás
HIBAFELISMERŐ ÉS HIBAJAVÍTÓ KÓDOK
Legegyszerűbb hibafelismerési eljárás: Zaj, zavar paritásbit átvitele Két lehetőség Általánosságban
páros paritás páratlan paritás
2k ≥ m + k −1
Kód Paritásbit 11011 11010
m információs bithez k ellenőrző bit szükséges 15
16
PÁROS PARITÁSBIT GENERÁLÁS A
B
C
D
F
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
X
1
0
1
1
X
1
1
0
0
X
1
1
0
1
X
1
1
1
0
X
1
1
1
1
X
PÁROS PARITÁSBIT GENERÁLÁS
Egy F(A,B,C,D) logikai függvény 4-bites BCD karaktereket egészít ki páros paritás bittel. Készítsen logikai hálózatot a megvalósításra.
C 1
1
1
1
4
F ( A, B, C, D ) = ∑ ( (1, 2, 4, 7,8 ) + (10 − 15 ) )
B X
X
X
X
X
X
A 1 17
D
18
3
2016.11.28.
PÁROS PARITÁSBIT GENERÁLÁS
HIBAJAVÍTÁS
F=A⊕B ⊕ C⊕ D
C
JEL BITEK
ADÓ
1
1
1
=1
1
X
X
X
X
X
X
PARITÁS
=1
GEN.
A 1
PARITÁS
PARITÁS BIT
=1
B
VEVŐ
D
PARITÁS VIZSG.
HIBA JELZŐ
A hibajavítást blokkrendszerű adatátvitel esetén SOR és OSZLOP paritás ellenőrzésével is elvégezhetjük. 19
NUMERIKUS ÉS ALFANUMERIKUS KÓDOK
Ily módon egyetlen hiba a hibás sor és oszlop metszéspontjában van, így a hiba értékcserével javítható20
AZ ÁBRÁZOLANDÓ SZÁM ÉRTÉKÉN ALAPULÓ KÓDOK
Információk két nagy csoportja: - csak számot tartalmazó, numerikus, - számokat és betűket tartalmazó, alfanumerikus.
• Fő szempont a műveletek minél egyszerűbb elvégzése - Bináris aritmetikához igazodó kód kell • Előjeles számok ábrázolása - Ne legyen szükség külön kivonás műveletre
Pl. numerikus kódokra: - tiszta bináris kód, 1-es és 2-es komplemens kód, - binárisan kódolt decimális (BCD) számjegy kódok, - egyéb bináris kódok, pl. Gray kód.
• Racionális számok ábrázolása - Pontosság - Nagyságrend
Pl. alfanumerikus kódokra: - telex kód (5 bites) - ASCII (American Standard Code for Information Exchange, 8 bites) 21
22
DECIMÁLIS SZÁMJEGYEK BINÁRIS KÓDOLÁSA
TETRÁD KÓDOK TÍPUSAI ÉS ALGORITMUSAI
Információ ábrázolás és feldolgozás: tiszta bináris (és 1-es, valamint 2-es komplemens) kód. Adat be- és kivitel: tízes számrendszer. 10-es számrendszer egyes számjegyei (a 10 szimbólum, 0, 1, ... 9) kifejezése bináris kóddal: binárisan kódolt decimális kód
Súlyozott (helyi értékes ) kódok - ”normál” (természetes) BCD kód, Aiken kód, stb. Súlyozatlan kódok - Stibitz (3 többletes) kód, Glixon kód és rokon egylépéses kódok, stb. Tetrád kód:
a4a3a2a1
Súlyok:
s4s3s2s1
ai = 0,1
Decimális számjegy értéke:
Binary Coded Decimal (BCD)
d = a4s4 +a3s3 + a2s3 +a1s1 23
24
4
2016.11.28.
SÚLYOZOTT TETRÁD KÓDOK
AIKEN KÓD - 4,2,2,1 v. 2,4,2,1 helyértékek - Többféle hozzárendelés lehetséges - Aritmetika: kivonás helyett 9-es komplemens +1 hozzáadása
A legfontosabb súlyozott tetrád kódok súlyozásai: 8 5 2 4 5 7 7
4 2 1 4 2 1 4 2 1 2 2 1 3 1 1 4 2 1 4 -2 -1
normál v. természetes BCD kód
d = 4a4 + 2a3 + 2a2 +1a0
(Aiken kód) Aiken kód
Tetrádok indexei: 0,1,2,3,6,9,12,13,14,15 1-esek számát minimalizáló kód
25
26
AIKEN-IRODALMI ÁTTEKINTÉS -1937-ben H. H. Aiken összefoglalta azokat a mérnöki elveket, melyek alapján - felhasználva a lyukkártya-gépeket, az automatikus telefonközpontok jelfogóit és kapcsoló szerkezeteit - felépíthető a automatikus számítógép. -1944. augusztusában bemutatták a Harvard Egyetemen az Automatic Sequence Controlled Calculatort -Működési sebessége: 2 szám összeadása 0.3 s, szorzása 6 s, osztása kb. 15 s
15,5 m hosszú és 2,5 m magas gép tömege 35.000 kg volt, 800 ezer alkatrészből és 800 km hosszúságú vezetékből állt.
-72 db huszonháromjegyű szám (+előjel) tárolására vállalkozott -Az adatokat lyukkártyáról, az utasításokat a villanyzongoránál használatoshoz hasonló, 24-csatornás lyukszalagról vitték be. 27
(Technikatörténet 1760-1960)
STIBITZ - IRODALMI ÁTTEKINTÉS • A Bell Telefon Laboratórium munkatársa jelfogókból egy olyan gépet tervezett, amely automatikusan átalakította a komplex számokkal történő számítások logikai műveleteit. • 1946. júliusában, a másikat 1947. február univerzális gép építése • A normál tizes helyett “biquinary” kódot használt (mint a japán szoroban). Ebben minden számot 7 jelfogó tárolt. Ebből öt a 0...4 közötti jegyeket, kettő a 0 és az 5 jegyeket képviselte. Mivel minden számot két jelfogó ábrázolt, lehetővé tette a hibaellenőrzést. Másik sajátosság, hogy minden számot lebegőpontosan ábrázolt. Sebessége: összeadás 300 ms, szorzás 1 s, osztás 2.2 s, négyzetgyökvonás 4.3 s.
Önkomplemens kódok, pl.: 4221 8 4 -2 -1 Excess-3
30
5
2016.11.28.
KÜLÖNFÉLE KÓDOK
SÚLYOZOTT BCD KÓDOK
31
3-TÖBBLETES (EXCESS-3, STIBITZ) KÓD
32
NEM SÚLYOZOTT BCD KÓDOK
Előfeszített súlyozott kód d = 8a4 + 4a3 + 2a2 +1a0 - 3 - A 3-mal nagyobb szám BCD kódja - Önkomplemens kód - Aritmetika: az ötödik biten jelzi az átvitelt, viszont az eredményt korrigálni kell Tetrádok indexei: 3,4,5,6,7,8,9,10,11,12,
33
EGYLÉPÉSES KÓDOK, GRAY-KÓD
34
4-BITES GRAY KÓD A KARNAUGH TÁBLÁN
A Gray-kód olyan kód, amivel a kvantált mintát digitálisan kifejezve, a szomszédos kvantálási szinteket képviselő kódszavak egymástól csak egy bitjükben különböznek. A Gray-kódot minimális változású kód. A Gray-kód speciális esete az ún. egylépéses kódoknak. A Gray-kód 2n számú n-bites bites kódszavak olyan sorrendben, hogy bármelyik két szomszédos kódszó csak egyetlen bitben különbözik. Ez áll az első és utolsó kódszóra is (ciklikusság). Alkalmazás: méréstechnika, lineáris vagy szöghelyzet érzékelése és kódolása (pozíció-kódolás). A műszeriparban és az automatizálásban a legelterjedtebb egylépéses 35 kód (“reflected binary”: tükrözött bináris) kód
A Gray kód képzési szabálya 4-biten 36
6
2016.11.28.
MÁS EGYLÉPÉSES KÓDOK Sok más, hasonló tulajdonságú (egylépéses) kód ismeretes. Pl. Glixon-kód, tetrád kódszavak, sorrendjük
KÓDÁTALAKÍTÓ HÁLÓZATOK, KÓDVÁLTÓK, DEKÓDEREK
0000 (0) → 0001 (1) → 0011 (2) → 0010 (3) → 0110 (4) → 0111 (5) → 0101 (6)→ 0100 (7) → 1100 (8) → 1000 (9)
37
38
KÓDOLÁS ÉS DEKÓDOLÁS ABC1
ABC2 Kódoló
ABC2
ABC1
•
A kódolás az a művelet, amikor valamilyen információhalmazt egy rögzített, kölcsönösen megfeleltető, egyértelmű szabályrendszer szerint egy másik információhalmazra leképezünk, pl.: decimális számrendszerbeli számokat kell binárisan megjeleníteni. A dekódolás a kódolás fordított művelete.
• • • • •
INFORMÁCIÓFORRÁS KÓDOLÓ CSATORNAILLESZTŐ DEKÓDOLÓ INFORMÁCIÓ NYELŐCSATORNA
Dekódoló
Bár a a kódolás és dekódolás egymással felcserélhető, a gyakorlatban kódolás ha a szokásosabb, vagy eleve adott ABC a kiindulási alap, és dekódolás a fordított eset. Pl. 10-es számrendszer ⇒ 2-es rendszer - kódolás 2-es számrendszer ⇒ 10-es rendszer - dekódolás 39
KÓDÁTALAKÍTÓK
KÓDÁTALAKÍTÓ HÁLÓZATOK, KÓDVÁLTÓK, DEKÓDEREK
Kódátalakítókra akkor van szükség, ha az adatforrás és a nyelő kódrendszere nem egyezik meg. Pl.:
A digitális technikában gyakran van szükség különböző kódrendszerek közötti átalakításra, kódváltásra. A kódátalakító hálózatok lényegében több bemeneti és kimeneti ponttal rendelkező kombinációs hálózatok. Megvalósíthatók egyedi logikai kapukból a kombinációs hálózatok megvalósítása ismert eljárásai szerint. Sok esetben célszerűbb a memóriaelemeken alapuló megvalósítás.
41
Helyzet érzékelő
Gray Bináris
Gray 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Bináris
NBCD 10 8421 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0001 0001 0001 0001 0001
1 8421 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
42
7
2016.11.28.
EGYSZERŰ PÉLDA: 3-BITES BIN/GRAY ÁTALAKÍTÁS
BINÁRIS/GRAY ÉS GRAY/BINÁRIS KONVERZIÓ ALGORITMUSAI Bináris: b3b2b1b0
Bin/Gray átalakítás:
Dec Bin Gray ——————————— 0 0 0 0 0 0 0 1 0 0 1 0 0 1 2 0 1 0 0 1 1 3 0 1 1 0 1 0 4 1 0 0 1 1 0 5 1 0 1 1 1 1 6 1 1 0 1 0 1 7 1 1 1 1 0 0 ———————————
- Gray első bitje azonos a bináris kód 1. (MSB) bitjével, - a második bit a bináris szám 1. és 2. bitjének KIZÁRÓ-VAGY függvénye, - a harmadik bit a bináris kód 2. és 3. bitjének KIZÁRÓ-VAGY függvénye, - és így tovább.
Gray: g3g2g1g0
Bináris → Gray Gray → Bináris ————————————————————— b3 = g3 g3 = b3 g2 = b3 ⊕ b2 b2 = g3 ⊕ g2 g1 = b2 ⊕ b1 b1 = g3 ⊕ g2 ⊕ g1 = b2 ⊕ g1 g0 = b1 ⊕ b0 b0 = g3 ⊕ g2 ⊕ g1 ⊕ g0 = stb. Bináris → Gray: Gray → Bináris:
gi = bi+1 ⊕ bi bi = bi+1 ⊕ gi
43
44
BINÁRIS/GRAY KÓDÁTALAKÍTÓ
BINÁRIS/GRAY KONVERZIÓ 0 b3 Bináris
1
0
0
1
1
0
0
1
Gray
1
1
0
1
0
1
0
1
1 b2
1 b1
1 b0
0 g3 =1 1 g2
=1
=1
0 g1
0 g0
45
46
FUNKCIONÁLIS ELEMEK
FUNKCIONÁLIS ELEMEK I
Funkcionális elemek – a digitális rendszerek építőkövei 48
8
2016.11.28.
FUNKCIONÁLIS ELEMEK
TERVEZÉS KAPUÁRAMKÖRÖKKEL
• Kombinációs funkcionális elemek • Sorrendi funkcionális elemek • Memória elemek
A logikai hálózatok tervezésének és realizálásának hagyományos módszere a kapuáramkörök alkalmazásán alapul.
Kombinációs funkcionális elemek XOR Kódoló (encoder) Dekódoló (decoder) Multiplexer (MUX) Demultiplexer (DEMUX) Komparátor Aritmetikai elemek (fél-és teljes összeadó, stb.)
Korszerűbb változata a programozható logikai elemeken (PLD) alapul, de ma már egyre inkább alkalmazzák az ún. FPGA (Field Programmable Gate Array) eszközöket. Ezek kapu- illetve tranzisztor szintű elemeket tartalmaznak, a chip felületén többnyire egyenletes elhelyezett konfigurálható logikai blokkokban, melyet hierarchikus huzalozási erőforrások egészítenek ki.
49
FUNKCIONÁLIS ELEMEK: INTEGRÁLT ÁRAMKÖRÖK OSZTÁLYOZÁSA
Sokszor azonban előnyösen alkalmazható a funkcionális 50 elemek felhasználását is alapul vevő tervezési eljárás.
DEKÓDOLÓ (DECODER) ÁRAMKÖR
A legfontosabb funkcionális áramkörök készen rendelkezésre állnak mint ún. közepes integráltságú áramkörök (medium scale integrated (MSI) circuits). Integrált áramkörök osztályozása komplexitás (integráltsági fok) szerint: SSI Small Scale Integration: kb. 10 alacsony szintű elem (kapu) MSI Medium Scale Integration: 10-100 LSI Large Scale Integration: 100-1.000 VLSI Very Large Scale Integration: > 1.000 ULSI Ultra Large Scale Integration: > 10.000 GLSI Giga Large Scale Integration: > 100.000 RLSI Ridiculously (?) Large Scale Integration : > 1.000.000
Kódolt információ dekódolása (konverzió) Egyidőben-egyszerre csak egy logikai kimeneti változó (tehát a dekódolt) lehet igaz, a többi hamis! 2N kimenet dekódolásához N bemenet kell! Gyakran alkalmazott eszköz, kapható 2-, 3-, 4-,… bemenetű IC formájában
51
52
N – 2N DEKÓDOLÓ
”1 AZ N KÖZÜL” DEKÓDOLÓK Kombinációs áramkör: n bemenete és m kimenete van. A bemeneti kombinációk lehetséges száma 2n, a kimenetek száma pedig m ≤ 2n. A kimenetek közül mindig csak az egyik 1 és az összes többi 0, vagy fordítva, az egyik 0 és a többi 1.
y0 LSB
x0
y1
x1 n-to-2n
Az n-bites bináris bemeneti kóddal kiválaszt egyet az m kimeneti vonal közül, mely csak az adott bemeneti kód megjelenése esetén lesz aktív.
Decoder MSB xn-1
Természetesen a legtöbbször MSI integrált áramkörként megvalósított hálózat tartalmazhat egyéb ”kényelmi” vezérlő bemeneteket (pl. engedélyező) is. 53
y2n-1
54
9
2016.11.28.
2-to-4 Decoder
3-to-8 Decoder
data
address
4-vonalas dekóder, kapu-szintű logikai vázlat 55
8-vonalas dekóder, kapu-szintű logikai vázlat
C
B
A
A
DEKODOLÓ MEGVALÓSÍTÁSOK
B m0 = CBA m1 = CBA
.
A
C
A
B
m2 = CBA
A
LSB A
m3 = CBA
LSB A m0
MSB B
A
m0
MSB B
B m4 = CBA
m1
A
C
m5 = CBA
m1
m6 = CBA
A
B A
m2
56
m2
m7 = CBA
m0 m1 m2 m3 m4
8- és 16-vonalas dekóderek, kapu-szintű logikai vázlat
m5 m6 m7
(b)
(a)
m3
m3
(a)
m0
m1
m2
m3
m4
m5
m6
m7
m8
m9
m10
m11
m12
m13
m14
m15
(b) k0
C
k1
2-to-4
m1
D MSB
LSB A
k2
m0
MSB B
k3
m2 l1
l2
l0
(c)
m3
l3
2-to-4
B
57
(c)
A LSB
58
Decoder with enable: 2-to-4
Dekóder engedélyező bemenettel A kapu-szintek száma nagyobb, késleltetés megnő
59
10
