2017.04.01.
DIGITÁLIS TECHNIKA Dr. Lovassy Rita Dr. Pődör Bálint
BINÁRIS SZÁMRENDSZER
Óbudai Egyetem KVK Mikroelektronikai és Technológia Intézet 3. ELŐADÁS
1
2
BEVEZETŐ ÁTTEKINTÉS A 6. előadás témája a digitális rendszerekben központi szerepet játszó számrendszerek és aritmetikák.
Áttekintjük a digitális technikában használatos számrendszereket, az aritmetikai műveletek elvégzésének szabályait és célszerű algoritmusait, valamint az egyes számrendszerek közti áttérések algoritmusait is.
1. Számrendszerek 2. Bináris számok 3. Aritmetikai műveletek bináris számokkal
A digitális rendszerekben, célszerűségi okokból a 2-es (bináris) számrendszer terjedt el.
A jelen és a következő előadáshoz kapcsolódó jegyzetrészek: Rőmer jegyzet 146-160 old., 179-181 old. Zsom jegyzet I, 19-49 old., 297-299 old. Gál könyv 132-145 old., 167-201 old. Az előadások ezen könyvek megfelelő fejezetein alapulnak.
Mindezek sokféle digitális funkcionális egység működésének alapjait képezik.
3
HELYÉRTÉK
318 = 3 ⋅100 + 1 ⋅10 + 8 ⋅1
318 = 3 ⋅10 + 1⋅10 + 8 ⋅10 2
1
4
BINÁRIS SZÁMRENDSZER Szám helyértéke
11010110( 2 ) =
0
1 ⋅ 27 + 1 ⋅ 2 6 + 0 ⋅ 25 + 1 ⋅ 2 4 + 0 ⋅ 23 + 1 ⋅ 2 2 + 1⋅ 21 + 0 ⋅ 2 0
Szám alaki értéke
Számjegyek: 0,1
Számjegyek: 0,1,2,3,4,5,6,7,8,9
318 = 300 + 10 + 8
Számrendszer alapja: 10
A számítástechnika és a digitális technika a bináris számrendszerre épül
Szám valódi értéke Decimális számrendszer 5
6
1
2017.04.01.
2-ES SZÁMRENDSZER HEXADECIMÁLIS SZÁMRENDSZER A kettes számrendszert Leibniz dolgozta ki, még 1679-ben, majd 1854-ben George Boole alakította ki hozzá az algebrát. A Boole-féle algebrában nem csupán az összeadás és szorzás művelete lehetséges, hanem az ún. logikai műveletek is: és, vagy, negáció. A 2-es számrendszer használatakor az adattárolás lényegesen egyszerűbben oldható meg, mint a 10es számrendszerben. 1936-ban R. Valtat szabadalmaztatta egy 2-es számrendszerben dolgozó számítógép elvét. Ebben az időben kezdett hozzá Konrad Zuse is egy 2-es számrendszert alkalmazó, mechanikus működésű, programvezérelt számítógép kifejlesztéséhez. Valtat és Zuse felismerte, hogy a 2-es számrendszer használata egyszerűsíti a számítástechnikát. 7
14 FB = 1 ⋅163 + 4 ⋅16 2 + F ⋅161 + B ⋅16 0
= 1 ⋅ 4096 + 4 ⋅ 256 + 15 ⋅16 + 11 ⋅1
= 5371(10) Számjegyek: 0, 1,..., 9, A, B, C, D, E, F Megkülönböztető jelölés $, pl. $14FB 8
SZÁMRENDSZEREK ÉS SZÁMJEGYEIK
10-ES ÉS 2-ES SZÁMRENDSZER Pl. 2009 tízes számrendszerbeli alakja azért ez, mert
Megnevezés Alap Számjegyek ——————————————————————— Bináris (duális) 2 0,1 Ternális 3 0,1,2 Tetrális 4 0,1,2,3 Kvintális 5 0,1,2,3,4 Oktális 8 0,1,2,3,4,5,6,7 Decimális 10 0,1,2,3,4,5,6,7,8,9 Duodecimális 12 0,1,2,3,4,5,6,7,8,9,a,b Hexadecimális 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
2009 = 2x103 + 0x102 + 0x101 + 9x100 kettes számrendszerbeli alakja 111 1101 01112, mert 2009 = 1x210 + 1x29 + 1x28 + 1x27 + 1x26 + 0x25 + 1x24 + 1x23 + 0x22 + 0x21 + 1x20 Hexadecimális rendszerben pedig $7D9 9
10-ESBŐL 2-ESBE VALÓ ÁTALAKÍTÁS ALGORITMUSA
ÁTSZÁMÍTÁS KÉT SZÁMRENDSZER KÖZÖTT Egy természetes szám átírása egyik számrendszerből a másikba: a számot elosztjuk az új rendszer alap-számával, és a maradékokat jobbról balra haladva leírjuk. Pl.
2009 = 2x1004 + 1, 502 = 2x251 + 0, 125 = 2x62 + 1, 31 = 2x15 +1, 7 = 2x3 + 1, 1 = 2x0 + 1. Tehát
10
1004 = 2x502 + 0, 251 = 2x125 + 1, 62 = 2x31 + 0 , 15 = 2x7 + 1, 3 = 2x1 + 1,
A 10-esből 2-esbe való átalakítás algoritmusa így is megfogalmazható (a kapott számjegyeket jobbról balra kell leírni): Ismételd Ha a szám páratlan, írj le 1-et, és vonj ki a számból 1-et, különben írj le 0-t oszd el a számot 2-vel amíg a szám nem 0
111 1101 1001 11
12
2
2017.04.01.
POZITÍV ÉS NEGATÍV BINÁRIS SZÁMOK • A bináris szám éppen úgy mint egy decimális szám, lehet pozitív vagy negatív. • A számítógépekben az előjel ábrázolása 0 és 1 szimbólumokkal valósul meg. • A plusznak 0, a mínusznak 1 felel meg. • Ez az ún, előjelbit, mely után következik a szám abszolút értéke.
1-ES KOMPLEMENS (1-es kiegészítős számábrázolás) •Ha egy n-bites pozitív szám (egész szám) szimbolikus jelölése
N P = 0 an − 2 an − 3 ...a1a0 az azonos abszolút értékű negatív számé
N Q = 1 a n − 2 a n −3 ...a1 a 0
2-ES KOMPLEMENS (2-es kiegészítős számábrázolás)
POZITÍV ÉS NEGATÍV NÉGYBITES BINÁRIS SZÁMOK ÁBRÁZOLÁSA
•A pozitív számok ábrázolása azonos a két előbbi számábrázolással. Egy n-bites pozitív szám (egész szám) szimbolikus jelölése
M P = 0 an − 2 an − 3 ...a1 a0 az azonos abszolút értékű negatív számé pedig a következő összeg eredménye
M Q = 1 a n − 2 a n − 3 ...a1 a 0 + 1
2-ES SZÁMRENDSZER ELŐNYEI Az áramköri megvalósítás szempontjából előnyös, hogy a leképezéséhez csak két stabil állapot szükséges, így kétállapotú elemekkel: relékkel, tranzisztorokkal, mágnesezhető elemekkel könnyen leképezhető. A két egymástól távol eső stabil állapot következtében viszonylag érzéketlen a fellépő zavarokkal szemben, illetve azok könnyen elháríthatók. A digitális technika természetes számrendszere – a kétértékű megvalósításból adódóan is – a kettes számrendszer. Ehhez jól illeszkedik a hexadecimális számrendszer. Ebben a technikában a tízes számrendszer használata, néhány kivételtől (pl. decimális számlálók) eltekintve nehézkes, és 17 sok helyen indokolatlan.
2-ES SZÁMRENDSZER ELŐNYEI: MATEMATIKAI SZEMPONTOK A bináris számrendszer matematikai szempontból is előnyös. Az aritmetikai műveletek igen egyszerűen hajthatók végre, és igen egyszerű a logikai ítéletalkotás is. Ugyanazok a számjegyek használhatók fel mind az aritmetikai, mind a logikai műveletekhez.
18
3
2017.04.01.
BINÁRIS ÖSSZEADÁS
8-AS ÉS 16-OS SZÁMRENDSZER A hexadecimális számrendszert kényelmi szempontból használják, pl. mert a kettes számrendszerrel nagy számokat hosszú leírni. A hexadecimálisból könnyű a binárisra átváltani és viszont. A hexadecimális rendszert a $ jellel is jelölik. Bin-hex átváltás: négy bináris számjegy egy hexa számjegyet ad ki, pl. 1111 = $F. Egy byte két hexa számjeggyel adható meg.
Két bináris számjegy A + B = C, S alakú bináris összeadása: S - eredeti helyértéken mutatkozó összeg (sum vagy magyarul summa), C - következő helyértékre való átvitel (carry). Igazságtábla és logikai függvények: ‗ ‗ A B S C S = AB + AB = A ⊕ B —————————— 0 0 0 0 C=AB 0 1 1 0 1 0 1 0 Megvalósító elem: 1 1 0 1 félösszeadó
19
20
BINÁRIS ÖSSZEADÁS: FÉLÖSSZEADÓ
FÉLÖSSZEADÓ (HALF-ADDER) —
Feladata két bit összeadása
—
S = AB + AB = A ⊕ B A B
C=AB S
A FÖ
Félösszeadó: két bemenet és két kimenet. Két bináris számjegyet tud összeadni, előállítja az összeget és átvitelt. Nem veszi figyelembe a kisebb helyértékről jövő átvitelt.
C
B
• •
S: összeg, sum
=1
S
&
C
félösszeadó
C: maradék, átvitel, carry 21
22
BINÁRIS/HEXADECIMÁLIS ÖSSZEADÁS BIN 10001111 11001011 +1 0 1 0 1 1 0 1 ___________ 101111000
TELJES ÖSSZEADÓ
DEC
Funkciója két bit és az előző helyi értékből származó maradék (átvitel) összeadása
203 173 _____ 376
A
Az összeadás hasonló a 10-e számrendszerbelihez: két számjegyet és az előző helyértékről származó maradékot kell összeadni. Az összeg egyes helyértékén lévő számot le kell írni, a kettes helyértéken lévőt tovább kell vinni. 23
B Cin
S TÖ Cout
24
4
2017.04.01.
AZ ÖSSZEGFÜGGVÉNY (Di)
A FÜGGETLEN VÁLTOZÓKHOZ RENDELT "SÚLYOK"
(4) (2) (1) i 0 1 2 3 4 5 6 7
A FÜGGŐ VÁLTOZÓK
INDEX
TELJES ÖSSZEADÓ (FULL ADDER)
Ai Bi Ci-1 Di Ci 0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
0 0 0 1
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 1
(4) (2) (1)
A teljes összeadónak három bemenete, a két operandus, és az alacsonyabb hely-értékről érkező átvitel (Ai, Bi és Ci-1) és két kimenete, az összeg és az átvitel) (Si (a táblázatban Di jelöli) és Ci) van.
i
Ai Bi Ci-1 Di
0
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
1 2 3 4
Di = (1,2,4,7)
5 6
Ci = (3,5,6,7)
7
„sakktábla” Szimmetrikus függvény
Ci-1
Di 0
0
1
1 2
1
3
0 6
0
Ai
1
7
Bi
1 4
0
5
25
KÉT 4-BITES SZÁM ÖSSZEADÁSA
TELJES ÖSSZEADÓ EGY LEHETSÉGES MEGVALÓSÍTÁSA
Soros átvitel terjedés (ripple carry adder)
Ai ⊕ Bi ⊕ Ci-1
Ai ⊕ Bi
26
A B
Cin
A B
Cin
TÖ
TÖ Cout
A1 B1
A2 B2
A3 B3
S
Cout
A B
A0 B0 Cin
A
S
Cout
B Cin FÖ
TÖ S
Cout
S
(Ai + Bi) Ci-1 Ai + Bi
Q3
AiBi
Q2
Q1
Q0
Carry flag AiBi + (Ai + Bi) Ci-1 27
BINÁRIS SZÁMOK KIVONÁSA
BINÁRIS KIVONÁS Két bináris számjegy A - B = D, (K) alakú bináris kivonása: K - magasabb helyértékről vett kölcsön (borrow); D - eredeti helyértéken mutatkozó különbség (difference) K A B D —————————— 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 _ D =A⊕ B K=AB
28
Bináris számok kivonásának algoritmusa hasonló a decimális számokéhoz (A > B): A = AnAn-1 ... A1A0 - B = BnBn-1 ... B1B0 K = KnKn-1 ... K1K0 —————————— D = DnDn-1 ...
(kölcsön) (különbség)
Di = Di(Ai,Bi,Ki+1) a különbség i-edik bitje az i-edik különbségnél szükséges kölcsön Ki = Ki(Ai,Bi,Ki+1) és K0 = 0 29
30
5
2017.04.01.
BINÁRIS SZORZÁS
BINÁRIS SZÁMOK SZORZÁSA
Az A x B = P bináris szorzás szorzótáblája (bináris ”egyszeregy”) igen egyszerű
A bináris számok szorzása ugyanúgy történik, mint a decimális számoké:
A B P —————— 0 0 0 0 1 0 1 0 0 1 1 1
- ha a szorzó soronkövetkező számjegye 1-es, akkor összeadás következik, - ha 0-as, akkor nincs összeadás. Minden helyértéknél léptetjük a részletszorzatot a megfelelő irányba.
Lényegében azonos a logikai ÉS kapcsolattal (logikai szorzás) 31
32
BINÁRIS SZORZÁS ELVÉGZÉSE 100100 x 1011 ⇒ 36 x 11 ——— 100100 1. részletszorzat 100100 2. részletszorzat ———— 1101100 összeg 000000 3. részletszorzat ————— 01101100 összeg 100100 4. részletszorzat ————— 110001100 végösszeg ⇒ 396
Kódok, kódolás: alapfogalmak
33
34
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ÓDOLÁS ÉS DEKÓDOLÁS ABC1
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ét ABC) közötti kapcsolatot adja meg. A hozzárendelésnek nem kell feltétlenül egyértelműen megfordíthatónak lennie.
ABC2 Kódoló
ABC2
ABC1 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 35
36
6
2017.04.01.
SZIMBÓLUMKÉSZLET
KÓDSZÓ, KÓDVEKTOR
Azon elemi jelek összessége melyeket a kódolásra felhasználhatunk. 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. tízes számrendszer (a mennyiségi információ egyik kódja): - tíz darab számjegy, - tizedesvessző, - előjel, - szóköz.
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. 8 bit → byte, a kódszavak hosszát gyakran byte-ban adják meg.
Pl. bináris kód a digitális technikában: - csak két szimbólum, 0 és 1.
37
KÓDSZÓ KÉSZLET
38
BINÁRIS ÉS NEM BINÁRIS KÓDOK
Egy rendszerben használt kódszavak összessége.
Bináris kód – két elemű szimbólumkészlet.
Pl. egy beszélt nyelvben a használt összes szó. A használt szavak a megengedett, az ”értelmetlen” szavak a tiltott kódszavak.
Nem bináris kód – többelemű szimbólumkészlet. Gyakorlati megvalósíthatóság: kétállapotú elemek előnyös tulajdonságai – bináris kód.
Pl. szokásos BCD kód: 0111 megengedett, 1011 tiltott kódszó (tetrád, illetve pszeudotetrád).
39
40
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
41
42
7
2017.04.01.
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
Hiba felismerés feltétele:
Hiba javítás feltétele:
D≥3
D≥2
Két lehetőség
Általánosságban
Kód Paritásbit 11011 11010
páros paritás páratlan paritás
2k ≥ m + k −1 m információs bithez k ellenőrző bit szükséges 43
44
DECIMÁLIS SZÁMJEGYEK BINÁRIS KÓDOLÁSA
HIBAJAVÍTÁS
JEL BITEK
ADÓ
Információ ábrázolás és feldolgozás: tiszta bináris (és 1-es, valamint 2-es komplemens) kód.
VEVŐ
Adat be- és kivitel: tízes számrendszer. PARITÁS
PARITÁS BIT PARITÁS GEN.
10-es számrendszer egyes számjegyei (a 10 szimbólum, 0, 1, ... 9) kifejezése bináris kóddal:
HIBA JELZŐ
PARITÁS VIZSG.
binárisan kódolt decimális kód A hibajavítást blokkrendszerű adatátvitel esetén SOR és OSZLOP paritás ellenőrzésével is elvégezhetjük.
Binary Coded Decimal (BCD)
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
PSZEUDOTETRÁDOK AZONOSÍTÁSA A KARNAUGH TÁBLÁN
NORMÁL BCD KÓD Természetes kód - Minden számjegyhez a 4-bites bináris kódját rendeli - Természetes helyérték: 8 4 2 1
C Minimalizálás után Érvényes kódszavak
P=AB +AC
d = 8a4 + 4a3 + 2a2 +1a0
B
A hat nem megengedett kombináció (1010, ... 1111) neve pszeudotetrád.
1
1
1
1
1
1
A
A B
Nem használt, illetve érvénytelen kódszavak 47
Hibajelző:
D
A C
& 1 & 48
8
2017.04.01.
BCD ÖSSZEADÁS: +6 KORREKCIÓ
BCD (8421) ÖSSZEADÁS
789 + 213 —— 1002
Példa: decimális 427 + 131 —— 558
BCD
0111 1000 1001 + 0010 0001 0011 ———————— 1001 1001 1100 + 0110 +6 korrekció ———————— 1001 1010 0010 + 0110 +6 korrekció ———————— 1010 0000 0010 + 0110 +6 korrekció ———————— 1 0000 0000 0010
0100 0010 0111 + 0001 0011 0001 ———————— 0101 0101 1000
Mivel egyetlen helyértéken sem volt az összeg 9-nél nagyobb, ezért korrekcióra nem volt szükség
49
50
BCD KÓDÚ ÖSSZEADÁS
BCD (8421) ÖSSZEADÁS ALGORITMUSA ABCD +BCD BBCD = ABCD +bin BBCD
Decimális 6 (bináris 0 1 1 0) korrekció
A + B > 9. érvénytelen kódszó
Átvitel két dekád között
C4
ha ABCD +bin BBCD ≤ 9
B3 B2 B1 B0
B3 B2 B1 B0
C4
„0”
&
„0”
Bináris összeadó
ABCD +BCD BBCD = ABCD +bin BBCD +bin 6BCD A3 A2 A1 A0
ha ABCD +bin BBCD > 9
A3 A2 A1 A0
C0
„0”
51
1
S3 S2 S1 S0
&
B3 B2 B1 B0
Bináris összeadó A3 A2 A1 A0
C0
S3 S2 S1 S0
S3 S2 S1 S0
„0”
52
9
