Számrendszerek


  1. A SZÁMÍTÓGÉP MŰKÖDÉSÉNEK ALAPJAI

    2. 1.1 NEUMANN ELVEI

    A számítógépek felépítésének és működésének Neumann János által megfogalmazott elvei a következők:

    1. Az utasításoknak az adatokkal azonos módon (azaz egyetlen nagy kapacitású memóriában), numerikus kódok formájában való tárolása.
    2. A kettes számrendszer alkalmazása.
    3. Szükséges egy vezérlőegység, amely különbséget tud tenni utasítás és adat között, majd önműködően végrehajtja az utasításokat.
    4. A teljesen elektronikus működés.
    5. A számítógép tartalmazzon olyan számolóművet, amely képes elvégezni a logikai műveleteket is.
    6. Szükség van olyan ki/bemeneti egységekre, amelyek áthidalják a bizonyos szempontból lassú emberi kommunikációs csatorna és a gyors számítógép közti sebességkülönbséget.
    7. Megbízhatatlan alkatrészekből is lehetséges megbízható rendszert konstruálni. Ennek a feladatnak egyik lehetséges megoldása a szerkezeti tartalékolás (strukturális redundancia).

    1.2 A SZÁMRENDSZEREK

    Az köznapi életben rendszerint a 10-es (decimális) számrendszert használjuk, ezért ezt tartjuk természetesnek. A számítógépes adatok, kódok, programok megértéséhez azonban szükségünk van arra, hogy a különböző számrendszerekben szabadon hajtsunk végre műveleteket. Egy tetszőleges alapú számrendszerben a következőképpen tudunk felírni egy számot:


    ahol p jelöli a számrendszer alapját, i a helyiértéket, n a pozitív, m pedig a negatív helyiértékek számát, a pedig a számjegyeket.
    A tízes számrendszerben felírt számoknál nem jelöljük a számrendszer alapját. Azokat a számjegyeket, amelyeket egy adott számrendszerbeli szám felírásánál használhatunk, a számrendszer jelkészletének nevezzük. A jelkészlet nagyságát a számrendszer alapja egyértelműen meghatározza. A p alapú számrendszer jelkészlete a 0,1,2...p-1 számjegyekből áll. Ha p>10, akkor a szokásos számjegyekből nem állítható össze a teljes jelkészlet, a 9-nél nagyobb számjegyek jelölésére más jeleket, például betűket használunk.
    Egy adott számrendszerben, adott számú helyiértéken ábrázolható legnagyobb (K) és legkisebb (k) szám:

    K = pn+1-p-m
    k = p-m

    Példák: Számoljuk át a következő különböző alapú számrendszerbeli számokat tízes számrendszerbe:

    123,12(4) = 1*42+2*41+3*40+1*4-1+2*4-2 = 27,375
    123,12(5) = 1*52+2*51+3*50+1*5-1+2*5-2 = 38,28
    123,12(6) = 1*62+2*61+3*60+1*6-1+2*6-2 = 51,22

    1.2.1 Kettes (bináris) számrendszer
    A számítógépes adattárolás eszközei legnagyobb részben kétállapotú fizikai elemek (pl. tranzisztorok). Az egyik állapotot megfeleltetjük a nulla számnak, a másikat az egynek. Így egyetlen kétállapotú fizikai elem alkalmas egy egyjegyű, kettes számrendszerbeli szám értékének tárolására. A kettes számrendszerbe tartozó számot bináris számnak, az egyjegyű bináris számot pedig bitnek nevezzük. A bit az információ alapegysége.
    Tegyük fel, hogy n+m+1 bit áll rendelkezésünkre, és képzeljük a pontot az n+1. bit után.
    Ekkor az n+m+1 biten felírható bináris szám:

    an*2n+...+a0*20+a-1*2-1+...+a-m*2-m

    ahol az an,...,a0,a-1,...,a-m értéke 0 vagy 1.

    1.2.2 Miért jó a kettes számrendszer
    Vizsgáljuk meg, hogy a számok ábrázolására melyik a legoptimálisabban alkalmazható számrendszer.

    S = R*logRM = R*InM / InR

    ahol R a radix, vagyis az alapszám, logRM pedig a szükséges számjegyek száma.

    Keressük meg y = x / In x minimumát!


    1.1. ábra: Szemléltető grafikon



    A legoptimálisabban tehát a természetes alapú számrendszerben tudnánk ábrázolni a számokat, azonban ez a számítást nagyon nehézkessé tenné, és a technikai megvalósítása is rendkívül bonyolult lenne. Ha egész alapú számrendszerekben gondolkodunk, akkor a 3-as számrendszer lenne megfelelő, viszont a számítástechnikában használt kétállapotú elemeknek sokkal inkább megfelel a bináris számábrázolás.

    1.2.3 Tízes-kettes(decimális-bináris) számrendszerbeli számkonverziók
    a) Az egész rész konvertálása
    A decimális egészrészt addig osztjuk kettővel, amíg az osztás eredménye nulla nem lesz. Egy függőleges vonallal képezzünk két oszlopot. A vonal bal oldalán szerepelnek a hányadosok, a jobb oldalán pedig a maradékok.


    b) A törtrész konvertálása
    A törtrészt addig szorozzuk kettővel, amíg a szorzás eredménye 1,0 nem lesz. Ez ritkán következik be, ezért a végtelen, szakaszos kettedes tört ismétlődő szakaszának felismeréséig, vagy pedig az ábrázolható helyiértéktől függő oszlophosszúságig folytatjuk a szorzást. Itt is két oszlopot készítünk egy függőleges vonallal. A vonal bal oldalán szerepelnek a szorzás egész részei, a jobb oldalán pedig a törtrészei. A szorzást csak a törtrésszel folytatjuk.


    Kettes számrendszerben ez végtelen szakaszos tört, tehát elvileg végtelen sok hely kell a tárolásához.

    1.2.4 Bináris számok átalakítása decimális számokká
    Horner-séma polinomok helyettesítési értékének meghatározására:

    pn(x) = an*xn+an-1*xn-1+...+a2*x2+a1*x+a0 =
    = x(an*xn-1+an-1*xn-2+...+a2*x+a1)+a0

    Például p3(x) = 2x3+5x2-3x+4 és x1 = 3,14. Mekkora p3 (x1) értéke?

    p3(3,14) = 3,14[3,14(3,14*2+5)-2]+4 = 3,14[3,14(6,28+5)-3]+4 =
    = 3,14(3,14*11,28-3)+4 = 3,14*32,4192+4 = 105,79629

    A bináris egészrész átalakításakor x1=2, a törtrésznél pedig x2=1/2 és a0=0.
    2. pl.: 10010112=?
    1 0 0 1 0 1 1
    2 4 8 18 36 74 75

    Az utolsó összeget már nem kell megszorozni 2-vel.

    2. pl.: 0,10100112=?
    1 1 0 1 0 0 1
    0,5 0,75 0,375 0,6875 0,34375 0,171875 0,5859375

    Az utolsó összeget is el kellett osztani 2-vel.

    3. pl.: 1011,01012=?
    1 0 1 1 , 0 1 0 1
    2 4 10 11 11,3125 0,3125 0,625 0,25 0,5


    A törtrésznél hátulról kezdjük az osztást.

    1.2.5 Hexadecimális számok
    Az ember számára a kettes számrendszerben felírt szám nem eléggé áttekinthető, túl hosszú, ezért bevezetjük a binárishoz közeli hexadecimális (tizenhatos alapú) számrendszert, ami megkönnyíti a bináris számok kezelését. A hexadecimális számrendszer számjegyei növekvő sorrendben a következők:

    0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

    A betűk a 9-nél nagyobb számjegyek ábrázolására szolgálnak, tízes számrendszerbeli megfelelőjük:

    A=10; B=11; C=12; D=13; E=14; F=15

    Ha egy tetszőleges bináris számot négyes csoportokra osztunk az egészeket a törtektől elválasztó ponttól balra és jobbra indulva, a négyes csoportoknak megfeleltethetünk egy-egy hexadecimális számjegyet.
    Ha a négyes csoportokra osztásnál a törtészt jelölő ponttól jobbra vagy balra lévő csoport négynél kevesebb tagból áll, jobb oldalon a szám után, bal oldalon a szám elé annyi nullát képzelünk, hogy a csoport négy jegyből álljon.

    Bináris Hexadecimális
    0000 0
    0001 1
    0010 2
    0011 3
    0100 4
    0101 5
    0110 6
    0111 7
    1000 8
    1001 9
    1010 A
    1011 B
    1100 C
    1101 D
    1110 E
    1111 F

    1-1. táblázat: A bináris és a hexadecimális számok közötti közvetlen megfeleltetés



    1.2.6 Decimális számok konvertálása tetszőleges alapú számrendszerbe


    A fenti séma alapján elvégezhetjük a konverziót decimálisból más számrendszerekbe. Nyilvánvaló, hogy a decimális szám egészrésze minden számrendszerben egész, a törtrésze pedig tört lesz. Ez lehetővé teszi az egész- és törtrész konverzióját külön-külön.
    Először az egészrészt számoljuk át: ha a decimális számot elosztjuk a másik számrendszer alapszámával (p-vel), a maradék (a0) az új rendszerben az egyesek helyén áll. Ha a kapott hányadost újra osztjuk p-vel, a maradék (a1) a p első hatványainak megfelelő helyiértékén áll. A műveletet folytatva eljutunk a nulla hányadosig, a maradék a p alapú rendszerben felírt szám legmagasabb helyiértékű jegye.
    A törtrésznél fordítva járunk el. A decimális szám törtrészét megszorozzuk p-vel, és a kapott szám tizedesponttól balra álló (egész) része lesz a p alapú rendszerben felírt szám első, a ponttól jobbra álló jegye.
    Ezt a részt levágjuk, a megmaradt tizedes törtet tovább szorozzuk p-vel, a tizedesponttól balra eső részt ismét levágjuk, ez lesz a szám második törtjegye. Ez a folyamat nem ér mindig véget oly módon, hogy a számjegyek elfogynak, ugyanis a tízes számrendszerben véges formában felírt tört szám nem mindig írható fel véges formában egy másik rendszerben.

    1.2.7 Aritmetikai műveletek bináris számrendszerben
    A tízes számrendszerben megtanult műveletvégzés alkalmazható minden helyiértékes számrendszerben, tehát csak az ott megszokott aritmetikai műveletvégzési szabályokra van szükség.
    Az összeadás menete a következő: jobbról balra haladva összeadjuk az azonos helyiértékű számjegyeket. Ha az összeg nem haladja meg a számrendszerben leírható maximális jegyet (kettes számrendszerben ez a szám az 1), akkor leírjuk, ha meghaladja, kivonjuk belőle a számrendszer alapját (azaz 2-őt), és leírjuk a maradékot, az eggyel nagyobb helyiértéken álló számok összegéhez pedig 1-et hozzáadunk. A műveletet addig folytatjuk, amíg a számjegyek el nem fogynak.

    Példa:
    +1 +1 +1 +1 +1 +1 (átvitel)
    1 0 0 1 . 1 1
    + 1 1 0 . 1 1
    1
    0
    0
    0
    0
    .
    1
    0

    A kivonást a legalacsonyabb helyiértéken kezdjük. Ha a kisebbítendő számjegy nem kisebb mint a kivonandó, a kivonást elvégezzük, és az eredményt leírjuk. Ha kisebb "kölcsönvesszük" az eggyel nagyobb helyiértékű oszlopból a számrendszer alapját. A műveletet addig folytatjuk, amíg a számjegyek el nem fogynak.

    Példa:
    +10 +10 +10
    1 1 0 1 1 0 1 . 1 0 1
    - 1 1 1 1 0 1 . 0 1 0
    1
    1
    0
    0
    0
    0
    .
    0
    1
    1

    1-0=1 leírjuk az 1-et.
    10(2)-1=1 leírjuk az 1-et.
    1-1-0=0 leírjuk a 0-t.
    1-1=0 leírjuk a 0-t.
    0-0=0 leírjuk a 0-t.
    1-1-0=0 leírjuk a 0-t.
    1-1-0=0 leírjuk a 0-t.
    10(2)-1=1 leírjuk az 1-et.
    11(2)-1-1=1 leírjuk az 1-et.
    1-1-0=0 leírjuk a 0-t.

    Mivel a + vagy - előjel kiírására a gépi számábrázolásnál nincs lehetőség, a pozitív és a negatív számokat más módon kell megkülönböztetni. Legegyszerűbb lenne a szám valamelyik bitjét - pl. az elsőt - előjelbitnek kinevezni, pozitív számok esetén az értéke 0 lehetne, negatív számok esetén 1. Az, hogy mégsem mindig ezt az egyszerű eljárást alkalmazzák a számítástechnikában, arra vezethető vissza, hogy a negatív számokat olyan formában célszerű tárolni, hogy a gépi kivonás művelete összeadással legyen helyettesíthető. Minthogy a szorzás összeadások sorozatára, az osztás kivonások sorozatára vezethető vissza, ha sikerül a kivonást összeadásra visszavezetni, akkor a számítógépnek csak egyetlen aritmetikai műveletet, az összeadást kell tudnia elvégezni.
    Nézzük meg, hogy a negatív számok speciális ábrázolásával hogyan vezethető vissza a kivonás összeadásra. Az egyszerűség kedvéért térjünk át a tízes számrendszerbe. Tegyük fel, hogy a számok ábrázolására három pozíció áll rendelkezésünkre (a legnagyobb ábrázolható szám 103-1=999).
    Vegyünk egy tetszőleges háromjegyű számot, pl. a 234-et. Vonjuk ki 999-ből, az eredmény 765. A 765 az a szám, amely a 234-et csupa kilencesekből álló számra egészíti ki három pozíción. Ezt a számot a 234 kilences komplemensének (kiegészítőjének) nevezzük. Általában beszélhetünk a p alapú számrendszerben egy szám p-1-es komplemenséről, amely a számot olyan n pozíciójú számmá egészíti ki, amelynek minden jegye p-1. Adjunk hozzá a 765-höz 1-et, az eredmény 766.
    A 766-ot a 234 tízes komplementerének nevezzük. Általában azt a számot, amely a p alapú számrendszerben egy n pozíción felírható számot p-re egészít ki, a szám p-s komplemensének nevezzük. Láttuk, hogy a p-1-es komplemensből a p-s komplemenst 1 hozzáadásával kapjuk.

    Végezzük el az alábbi kivonást a hárompozíciós decimális számok körében:

    723-132=591

    Ezt a kivonást az alábbi egyenlőség felhasználásával másképp is elvégezhetjük:

    723-132=723+(1000-132)-1000

    Lépésenként végrehajtva, először képezzük a 132 tízes komplemensét három pozícióra, ez 868. Ezt hozzáadjuk a 723-hoz, az eredmény:

    723+868=1591

    A kapott számból kivonunk ezret, azaz elhagyjuk az első számjegyet, amit a számítógép automatikusan le is vágna, hiszen a szám ábrázolására csak három pozíció áll rendelkezésre. Így a kivonást két műveletre, egy p-s komplemensképzésre és egy összeadásra vezettük vissza.
    Kettes számrendszerben a p-1-es komplemens nem más, mint az 1-es komplemens, így a komplemensképzéskor a nullákhoz egyet, az egyekhez nullákat kell adnunk, hogy minden pozíción 1-et kapjunk. A kettes komplemens képzése meghatározás szerint egy egyes hozzáadásával valósul meg.

    Példa:
    11001110 - nyolcpozíciós bináris szám
    00110001 - a szám egyes komplemense

    001100001 - egyes komplemens
    00110010 - kettes komplemens


    Egy szintet vissza, vagy vissza a főmenübe.