3. gyakorlat Számrendszerek: Kettes számrendszer: {0, 1} Tízes számrendszer: {0, 1, 2, ... , 9} 16-os (hexadecimális számrendszer): {0, 1, 2, ... , 9, A, B, C, D, E, F} Alaki érték: 0, 1, 2, ..., 9, ... Helyi érték: attól függ, hogy a szám melyik pozíción áll Példa: 58310 = 5 * 100 + 8 * 10 + 3 * 1 = 5 * 102 + 8 * 101 + 3 * 100 58316 = 5 * 256 + 8 * 16 + 3 * 1 = 5 * 162 + 8 * 161 + 3 * 160 Számrendszerek közötti konverzió: 58316 = ?10 256
16
1
5
8
3
58310 = ?16 163 = 4096, 58310 7110 710 58310
5 * 256 + 8 * 16 + 3 * 1 = 141110
162 = 256, 161 = 16, / 256 = 2 / 16 = 4 / 1 = 7 =
160 = 1
24716
58310 = ?2 210 = 1024, 29 = 512, 28 = 256, 27 = 128, 26 = 64, 25 = 32, 24 = 16, 23 = 8, 22 = 4, 21 = 2, 20=1 58310 / 512 = 1 7110 / 256 = 0 7110 / 128 = 0 7110 / 64 = 1 710 / 32 = 0 710 / 16 = 0 710 / 8 = 0 710 / 4 = 1 310 / 2 = 1 110 / 1 = 1 58310
=
10010001112
Másik megoldás: (jegyzet) 58310 = ?2 /2 Maradék 58310 1 29110 1 14510 1 7210 0 3610 0 1810 0 910 1 410 0 210 0 110 1 58310 = 10010001112
58310 = ?16 /16 Maradék 583 7 36 4 2 2
58310 = 24716
1100102 = ?10 64
32
16
8
4
2
1
1 1 1100102 = 32 + 16 + 2 = 50
0
0
1
0
Törtek konvertálása 35.13210 = ?2 /2
Maradék
35 17 8 4 2 1
1 1 0 0 0 1
egész
*2
0.132 0 .264 0 .528 1 .056 0 .112 0 .224 0 .448 0 .896 1 .792 1 .584 ... ... Nem biztos, hogy véges tizedes tört binárisan is véges lesz!
Horner elrendezés: Hogy néz ki a 28710 szám Horner elrendezésben? (((2 * 10 + 8) * 10 + 7 ) Hogy néz ki a 5728 szám Horner elrendezésben? (((5 * 8 + 7) * 8 + 2)
Összeadás: Mi a 111011012 és a 0001112 számok összege? 11101101 + 000111 11110100 Mi a 14AA516 és a F3216 számok összege? 14AA5 + F 32 15 9D7 Előjeles fixpontos számok ábrázolásai: Előjeles abszolút érték: balról az első bit az előjel: 0, ha a szám pozitív, 1, ha negatív • a 0 kétféleképpen ábrázolható: 10000000, 00000000 • a legkisebb szám -127, a legnagyobb 127 Egyes komplemens: az első bit az előjel (0, ha pozitív; 1, ha negatív) A szám -1-szerese úgy kapható meg, hogy minden bitjét ellenkezőjére állítjuk. • a 0 kétféleképpen ábrázolható: 00000000, 11111111 Kettes komplemens: az első bit az előjel, 0: pozitív, 1: negatív a pozitív szám negáltja úgy kapható meg, hogy az egyes komplemenshez hozzáadunk 1-et. • a legkisebb szám a -128, a legnagyobb 127 • a nulla egyértelműen ábrázolható Feladat: számoljuk ki a 4310 kettes komplemensét. Megoldás: 4310 = 001010112 00101011 (pozitív szám kettes komplemense önmaga, ha <= 127) Feladat: számoljuk ki a -12310 kettes komplemensét. Megoldás: a gyakorlaton 12310 = 01111011 011110112 (pozitív szám kettes komplemense önmaga, ha <= 127) -12310 = 10000101 (ez már kettes komplemens) Többletes számábrázolás: a szám és a többlet összegét ábrázoljuk előjel nélkül, m bites szám esetén a többlet 2m-1 vagy 2m-1-1 pl.: 3510 = 00100011 többletes érték: 101000112 35 + 128 -3510 = 10100011 többletes érték: 010111012 128 - 35 = 93 • a legkisebb szám -128, a legnagyobb 127, • a nulla egyértelműen meghatározható • a 2m-1 többletes ábrázolás azonos a kettes komplemenssel fordított előjellel. • lebegőpontos számok kitevő-részénél használják
BCD (Binary Coded Decimal) ábrázolás: minden decimális számjegyet négy biten ábrázolunk. a negatív számokat 9-es vagy 10-es komplemens kóddal ábrázoljuk. Megjegyzés: A 9-es és 10-es komplemens ahhoz kell, hogy tudjunk negatív számokat ábrázolni. A 10-es komplemens úgy állítható elő, hogy balról az első BCD szám (4 bit) értéke dönt abban, hogy mi lesz az előjel. Ha ennek értéke 0, ... 4, akkor a szám pozitív, ha 5, ..., 9 akkor negatív. Ezen kívül, a szám többi részét hozzá kell adnunk, talán könnyebben megérthető az alábbi táblázat alapján. Tehát pl. ha kétjegyű BCD számunk van, akkor 00 a 0-t jelenti, a 49 még a 49-et, de 50 már -50-et, mert kétjegyű számmal 100 különböző értéket tudunk ábrázolni, -50-től 49-ig. A komplemens arra utal, hogy negatív számok esetén -50-hez kell hozzáadni a második számjegy értékét. BCD 00 01
Decimális érték 0 1 ...
49 50 51 52
49 -50 -49 (-50 + 1) -48 (-50 + 2) ...
99
-1 (-50 + 49)
A 9-es komplemens annyiban különbözik a 10-es komplemenstől, hogy le kell vonni belőle 1-et. Az előadásjegyzetben szereplő 30110 és -30110 számok a következő módon ábrázolhatóak BCD kóddal (most binárisan) 30110 = 0000 0011 0000 0001BCD (BCD) -30110 = 1001 0110 1001 1000BCD (BCD 9-es komplemens) -30110 = 1001 0110 1001 1001BCD (BCD 10-es komplemens) Ez azért van így, mert három számjeggyel 1000 különböző érték ábrázolható. 1000 - 301 = 699, vagyis, a 10-es komplemens értéke így jön ki. A 9-es komplemens meg eggyel kevesebb.
A BCD számoknál megkülönböztetünk pakolt és pakolatlan számokat. Mivel minden decimális számjegy ábrázolásához elegendő 4 bit (0000, ..., 1001), így egy bájton ábrázolhatunk két BCD számjegyet. Ha egy bájton két BCD számjegyet ábrázolunk, akkor ezt pakolt BCD számábrázolásnak nevezzük. Ha minden BCD számjegyet egy bájton ábrázolunk (a felső 4 bit csupa 0), akkor ezt az ábrázolási módot pakolatlan BCD számábrázolásnak nevezzük. Feladat: ábrázoljuk pakolt BCD kóddal a 5710-et. Megoldás: 0101 0111BCD Feladat: ábrázoljuk pakolt BCD kóddal a -3410-et. Használjunk 9-es komplemenst. Megoldás: -342 = -50 + 16 = 66 0110 0110BCD (BCD)
Lebegőpontos számok: Általában normalizált alakban ábrázoljuk. A nulla általában csupa 0-ból áll, meghatározható a legkisebb és legnagyobb ábrázolható szám, valamint a legkisebb és legnagyobb hiba. Az IEEE 754 standard szerint single: 32 bit: előjel (1 bit), kitevőrész (8 bit 127-többletes), a törtrész abszolút értéke (23 bit) double: 64 bit: előjel (1 bit), kitevőrész (11 bit 1023-többletes), a törtrész abszolút értéke (52 bit) Normalizált számok: kitevőrész = kitevő + 127 (-126, ..., 127). Közvetlenül a törtrész elé kell képzelni egy 1-est (implicit bit) és a bináris pontot. pl.: 1 = 001111111000...00002 előjel
kitevőrész
1.
törtrész
0.5 = 001111110000...00002 előjel
kitevőrész
1.
törtrész
Normalizálatlan számok: ha a kitevőrész = 0, ilyenkor a kitevő = -126 nem 127 a bináris pontot implicit 0 előzi meg, ami nincs ábrázolva 000000000100...00002 pl.: 2-127 = -149 -2 = 100000000000...00012 Ha a kitevőrész = 255, akkor vagy túl nagy számokról, vagy NaN-ról beszélünk. Bájtsorrend: nagy endián a legmagasabb helyértékű bájt a szóban a legalacsonyabb címen kis endián a legmagasabb helyértékű bájt a szóban a legmagasabb címen
Hamming kód, hibajavító kód: Két kódszó Hamming-távolsága az eltérő bitek száma. A biteket 1.-től számozzuk. A kódszóba paritás biteket helyezünk el, amelyek azt mutatják, hogy az általuk ellenőrzött pozíciókon páros vagy páratlan számú 1-es van. A paritásbiteket a 2-hatvány pozíciókra helyezzük el. A k-adik bitet azok az k1, k2, ..., kj paritásbitek ellenőrzik, amelyek összege k, vagyis k1 + k2 + ... + kj = k. Pl.: a 7. bitet az 1. a 2. és 4. bit ellenőrzi. Ha egy bit elromlik, akkor a paritásbitek alapján ki lehet számolni, hogy melyik bit romlott el. Megjegyzés: A paritásbitek által ellenőrzött pozíciók megkaphatók, ha felírjuk a pozíciók bináris alakját.
1. bit: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, ... 2. bit: 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, ... 4. bit: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, ... 8. bit: 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, ... 16. bit: 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, ... ... Példa: A paritás biteket úgy állítjuk be, hogy az ellenőrzött pozíciókon az 1-esek száma páros legyen eredeti adat: 01100110 eredeti adat paritás bitekkel: 01001100011 pozíciók 12345678901 elrontott adat paritás bitekkel (a 10. bit romlott el): 01001100001 A paritásbitekkel ellenőrizhetjük, hogy melyik pozíción romlott el a bit értéke. Az 1. pozíción lévő paritásbit jó, tehát a 1., 3., 5., 7., 9., 11. pozíciókon lévő bitek jók A 2. pozíción lévő paritásbit nem jó, tehát a 2., 3., 6., 7., 10., 11. pozíción lévő bitek egyike rossz A 4. pozíción lévő paritásbit jó, tehát a 4., 5., 6., 7. pozíción lévő bitek értékei jók lehetnek. A 8. pozíción lévő paritásbit nem jó, tehát a 8., 9., 10., 11. pozíciókon lévő bitek egyike rossz. Tehát összesítve az 2., 3., 6., 7., 8., 9., 10., 11. valamelyike rossz. Azt láttuk, hogy a 3., 6., 7., 9., 11. pozíciókon jó bitek állnak. Marad a 8-as és a 10-es pozíció. A 8-as bit értéke még nem ad információt, viszont a 2-es bit értéke rossz, és e kettő közül csak a 10. bitpozíciót ellenőrzi a 2. bit, vagyis ez romlott el. Feladat: A 0110101102 adatot lássuk el paritásbitekkel. Megoldás: a gyakorlaton 1001110110110 1234567890123 Feladat: Melyik bitje sérült a 10011101001102 szónak? Megoldás: a gyakorlaton 1001110100110 1234567890123 A 1. bit értéke rossz: a 1., 3., 5., 7., 9., 11., 13. bit valamelyike rossz A 2. bit értéke jó, tehát a 2., 3., 6., 7., 10., 11. bit értéke jó A 4. bit éréke rossz, tehát a 4., 5., 6., 7., 12., 13. bit jó A 8. bit értéke rossz, tehát a 8., 9., 10., 11., 12., 13. bit valamelyike rossz Tehát az 1., 9., valamelyike rossz. Ha a 9. bit rossz, akkor a 8.-nak is rossznak kell lennie.
