Bitit ja lukujärjestelmät¶

Osaamistavoitteet: Tämän materiaalin läpikäytyäsi tiedät miten tietokoneen muisti rakentuu biteistä, miten tietokone niitä käsittelee binäärilukuina ja osaat tehdä muunnoksia eri lukujärjestelmien välillä.

Aiemmin ohjelmoinnin kursseilla opimme mitkä ovat tietokoneen ja eri ohjelmointikielten tuntemat lukujärjestelmät: binääri-, kymmen- ja heksadesimaaliluvut. Näistä kymmenjärjestelmä on mukana vain meidän ihmisten, ts. ohjelmoijien ja käyttäjien, takia. Tietokone vaatimattomana laskimena ei tarvitse kuin binääriluvut ja niitä vastaavat bitit. Meidän tulee kuitenkin ymmärtää miten tietokone käsittelee bittejä.

.. tosin joskus eri lukujärjestelmien kanssa laskeminen saa kummallisia käänteitä (http://www.xkcd.com/571)

Selvitetäänpäs mitä uneton ystävämme oikein laskee ja mitä lampaille yllä tapahtuu..

Bitit tietokoneen muistissa¶

Bitti on (tietotekniikassa) tietoalkion pienin käsiteltävissä oleva osa. Bitillä on kaksi toisensa poissulkevaa (loogista) tilaa: 0 ja 1, joiden merkitys on ohjelmoijan määriteltävissä. Yksittäinen bitti siis kertoo aika vähän asioita, mutta kun bittejä asetetaan jonoon peräkkäin (esim 11010100) ja tämä bittijono käsitetään binäärilukuna, voidaankin esittää aika monta numeroarvoa eli tietoalkion tilaa.

Sanan, ts. tietoalkion, koko bitteinä kertoo meille sen lukualueen koon.

2 ^ 8 = 256 // 8-bittinen luku
2 ^ 16 = 65536 // 16-bittinen luku
2 ^ 32 = 4294967296 // ...
2 ^ 64 = 1.8446744*10^19 //  ...
2 ^ .. // okei, eiköhän nämä riitä meille

Nyt positiivisen binäärilukun lukualue on siis 0 - 2^n-1, missä n on bittien määrä.

Yhdestä 8 bitin binääriluvusta käytetään nimitystä tavu (engl. byte) ja 16/32 bitin luvusta taas nimitystä sana (engl. word) ja 32/64-bitin luvusta nimitystä englanniksi long word (.. pitkä kokonaisluku). Sanan määritelmä vaihtelee arkkitehtuurista toiseen ja se on nykyään tyypillisesti sulautetuissa joko 16 tai 32 bittiä ja PC-työasemissa 64 bittiä. C:n standardi ei sanan kokoa määrittele, josta lisää kohta..

Pyrkimys säästeliäisyyteen¶

Edellisellä luennoilla opimme, että suorittimen arkkitehtuuri määrittelee sanan koon bitteinä, joka on samalla myös yhden muistipaikan koko. Näin ollen keskusmuisti on "pätkitty" sananpituuden (ok, yleensä) mukaisesti muistipaikkoihin. Ja kun jokaisella muistipaikalla on osoite, voimme löytää muistista jokaisen yksittäisen tietoalkion ja sen yksittäisen bitin arvon.

Miksi nämä tavut ja sanat kiinnostavat meitä.. eikö riittäisi, että käytetään aina vain 64-bittistä arkkitehtuuria ja muistipaikkaa, kun kerran sinne mahtuu meidän luku ihan varmasti?

Näin voimme tehdä arkkitehtuurin ja muistin määrän asettamissa rajoissa, vaikkapa työasemalla ohjelmoidessa. Mutta, koska sulautetuissa järjestelmissä muistia on yleensä vähän tarjolla verrattuna työasemiin, joudutaan sen käyttöä optimoimaan. yksi oleellinen tapa optimoida on esittää ohjelmassa juuri sopivan kokoisia muuttujia. Kun muistia on vähän, miksi käyttää pitkää kokonaislukua (64-bittinen luku, joka vie 8 tavua muistia) jos kyseisen arvo mahtuu 8-bittiseen muistipaikkaan (eli yhteen tavuun)? Pieni muistin koko on juuri niitä suunnittelupäätöksiä, joilla mikrokontrollerien valmistuskustannuksia saadaan alas verrattuna yleiskäyttöisiin prosessoreihin.

Tarkastellaan asiaa esimerkin kautta. Joissain mikrokontrollereissa (ATtiny-sarja) on muistia jopa alle yhden kilotavun (1024 tavua). Jos kilotavun muistissa yhden muistipaikan koko olisi 32 bittiä (4 tavua x 8 bittiä), muistissa olisi 1024 / (32 / 8) = 256 yksittäistä muistipaikkaa. Jos taas muistipaikan koko on 16 bittiä 1024 / (16 / 8 ) = 512 , muistissa on 512 muistipaikkaa. Jälkimmäiseen muistiin siis mahtuu enemmän yksittäisiä tietoalkioita, mutta niiden koko on pienempi.

Alla esimerkinomaisesti miten erikokoiset tietoalkiot sijoittuisivat muistiin. Kuvan arkkitehtuurissa osoitelinjoja olisi 4 ja datalinjoja sananpituuden 8 bittiä mukaan. Nyt muistin koko 2^4 muistipaikkaa, jos sanan pituus on 8 bittiä. Jos sanan pituus on 16 bittiä, on muistin koko olisi 2^3 muistipaikkaa.

(kuvassa virhe 16-bittisissä muistiosoitteissa..)

Jonoon järjesty!¶

Muistipaikassa olevan binääriluvun esittämisessä tietokoneelle (ALUlle) on vielä pari mutkaa matkassa, nimittäin bittijärjestys ja tavujärjestys.

Bittijärjestys¶

Kymmenjärjestelmän luvuissa olemme sopineet, että merkittävin numero on vasemmanpuoleisin ja siitä oikealle laskevassa järjestyksessä. Esimerkiksi, luvussa 210 isoin painoarvo on luvulla 2, joka kuvaa satasia.

Nyt binääriluku 1011 voidaan lukea kahdella tapaa: 1011 = 1* 2^0 + 0*2^1 + 1*2^2 + 1*2^3 = 13 ja 1011 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 11. Suunnasta riippuen binääriluvun arvo on eri. Myös tietokoneiden kanssa meidän pitää sopia mitenpäin binääriluku luetaan. Eli missä on merkittävin numero luvussa?

No, suorittimen arkkitehtuurissa tämän asiat ovat suunnittelijat päättäneet ja siitä kyllä ohjelmoinnin helpottamiseksi kerrotaan suorittimen manuaalissa (ts. datakirjassa). Nyt puhutaan vähiten merkitsevästä (engl. least significant bit, LSB) bitistä, jolla on siis pienin kakkosen potenssi, ja vastaavasti eniten merkitsevästä (engl. most significant bit, MSB) bitistä, jolla on suurin kakkosen potenssi.

Tavujärjestys¶

Okei, mutta mutta... jos muistipaikan koko on useita tavuja, mistä tiedämme että missä järjestyksessä sen tavut ovat? Esimerkiksi 32-bittinen sana, joka koostuu neljästä tavusta? tavu0,tavu1,tavu2,tavu3 tai tavu3,tavu2,tavu1,tavu0.

Tämä on ihan samoin arkkitehtuurin suunnittelun yhteydessä päätettävä asia. Tavujärjestys voi olla eniten merkitsevin tavu ensin (engl. big endian) tai vähiten merkitsevin ensin (engl. little endian). Esimerkiksi työasemien x86-64 -prosessoriarkkitehtuuri on little endian, mutta Sun-työasemien 32-bittinen arkkitehtuuri on big endian.

Kurssilla määritellään nyt, että eniten merkitsevä tavu on vasemmanpuoleisin tavu ja eniten merkitsevä bitti (MSB) on luvun vasemmanpuoleisin bitti. Aina liikutaan siis vasemmalta oikealle.

Negatiiviset kokonaisluvut¶

Aiemmin on esitetty tapa käyttää bittejä ja binäärilukuja positiivisten lukujen esittämiseen, mutta miten negatiiviset luvut esitetään? Seuraavassa kolme tapaa esittää negatiivisia kokonaislukuja binäärilukuina.

1. Suora (engl. signed magnitude). Voimme varata biteistä eniten merkitsevän merkkibitiksi, eli osoittamaan etumerkkiä (+ / -), jossa 0 tarkoittaa positiivista lukua ja 1 negatiivista. Esimerkiksi 0010 olisi 2 ja 1010 olisi -2. Huomataan, että tällöin luvulla nolla on kaksi esitystä, 4-bittisenä 0000 ja 1000. Tämä on huono juttu, koska joudutaan (koodissa) huomioimaan molemmat +0 ja -0.

Kun varaamme yhden bitin etumerkin käyttöön, jää meillä itse lukualueeseen n-1 -bittiä. Esimerkiksi 8-bittisen luvun lukualue tippuu 7:n bittiin, eli positiivinen lukualue olisi enää 0..127. Tilalle saamme etumerkin avulla lisäksi negatiiviset lukualueen -128..-1. Tässä siis lukualue ikäänkuin "siirtyy" negatiiviseen suuntaan!

2. Yhden komplementti Negatiivinen luku saadaan ottamalla positiivisesta negaatio. Esimerkiksi, kun luku 3 on 0011 binäärilukuna, niin -3 olisi 1100. Tässäkin esitystavassa on nollalle kaksi esitystä, 0000 ja 1111.

3. Kahden komplementti¶

Kolmas esitystapa on kaikkien kiinnostavin ja yleisesti tietotekniikassa käytetty. Joten uhrataan sille hieman enemmän aikaa.

Sovitaan taas, että eniten merkitsevä bitti (MSB) on merkkibitti: 0 positiivinen ja 1 negatiivinen. Nyt positiivisella puolella 2-komplementtiluvuissa ei ole mitään erikoista.

Negatiivisen kokonaisluvun esittämiseen on oma menetelmä:

Positiivisesta binääriluvusta otetaan negaatio: nollat ykkösiksi ja päinvastoin
Lisätään negaatioon 1.

Esimerkkejä 4-bittisillä luvuilla. 

Luku 1    0001       Luku 2    0010       

Negaatio  1110       Negaatio  1101  
            +1                   +1                  
          ----                 ----                
          1111 = -1            1110 = -2

Takaisin negatiivisesta positiiviseksi mennään samalla menetelmällä.

Luku -1   1111       Luku -2   1110      

Negaatio  0000       Negaatio  0001   
            +1                   +1                  
          ----                 ----                
          0001 = 1             0010 = 2

Esimerkki. Kuvassa 4-bittiset luvut ilman etumerkkiä ja 2-komplementtiesityksenä.

Muuta jännää¶

Lisäksi 2-komplementtiesitys on siitä kätevä, että 2-komplementtilukujen yhteenlasku toimii samoin, oli operandi positiivinen tai negatiivinen. Tämä helpottaa merkittävästi ALUn digitaalilogiikan suunnittelua..

Esimerkki. Laske 2-komplementtiluvuilla 2+3 = ? ja 2-3 = 2+(-3) = ?

Luku +2 0010            Luku +2 0010
Luku +3 0011            Luku -3 1101
+       ----            +       ----
        0101 = 5                1111 = -1

(Suorassa menetelmässä ja 1-komplementti-esityksessä tämä ei aina toimi, kokeile löytää esimerkki jossa yhteenlasku ei toimi!)

Ja sitten terveisiä Niksi-Pirkka osastolta.. nyt negatiivisen binääriluvun muunnos kymmenjärjestelmään voidaan tehdä ilman laskinta yksinkertaisella yhteenlaskulla. Idea on, että ajatellaan eniten merkitsevän bitin painoarvo (engl. rank) negatiivisena, kuvassa punaisella. Kun taas muiden bittien arvot pysyvät positiivisina. Nyt, muunnos tapahtuu siten, että lasketaan yhteen bittien painoarvoa vastaavat desimaaliluvut.

Esimerkki. 8-bittiset luvut 99 ja -99. 

01100011 -> 64 + 32 + 2 + 1 = 99
10011101 -> -128 + 16 + 8 + 4 + 1 = -99

Muunna 6-bttinen 2-komplementtiluku 101011 kymmenjärjestelmään yhteenlasku-menetelmällä.

Anna palautetta

Koitko tämän tehtävän hyödylliseksi oppimisen kannalta?

Kommentteja tehtävästä?

Heksadesimaaliluvut¶

Toinen C-kielisessä (ja konekielisessä) sulautettujen ohjelmoinnissa usein käytetty kantalukujärjestelmä on 16. Tällöin puhutaan heksadesimaalinumeroista, jotka käsittävät numerot 0-9 ja 10-15, merkitään kirjaimilla A-F.

Huomataan, että jokainen heksadesimaalinumero voidaan esittää 4:llä bitillä. Tämä onkin yksi hyvä syy miksi heksadesimaalilukuja käytetään, kun nyt voidaan yksi tavu esittää kahdella heksadesimaalinumerolla vs. hankalasti biteiksi tulkittava kymmenjärjestelmän kokonaisluku vs. silmille epämukava binääriluku.

Muunnos heksalukujen ja binäärilukujen välillä on helppo. Tiedäme, että jokaista heksanumeroa siis vastaa 4 bittiä, eli tarvitsee vain muuttaa heksanumerot yksi kerrallaan 4-bittisiksi binääriluvuiksi.

Esimerkki. Muunna heksadesimaaliluku 173A4C binääriluvuksi?

   1    7    3    A    4    C   
0001 0111 0011 1010 0100 1100

Monissa ohjelmointikielissä heksaluvut esitetään käyttäen etuliitettä 0x. Esimerkiksi.

0x0123456789ABCDEF
0xA
0x1000
0x001
0xBEEF
0xC0DE
0xBA5EBA11

Lopuksi¶

Ok, jänniä juttuja.. mutta entäs uneton ystävämme ja ne seonneet lampaat?

Nythän meille on selvää, kun vilkaisemme sarjakuvaa uudestaan, että ystävämme laskee lampaita 16-bittisillä 2-komplementtiluvuilla. Nyt yli bitti on varattu merkkibitiksi, jolloin lukualue (merkkibitti + 2^15) on -32768-32767..

Kävi ikävästi unta odotellessa ja positiivinen lukualue loppui kesken, jolloin luvut pyörähti negatiiviselle puolelle merkkibitin vaihtumisen myötä..

0000000000000001 = 1
+1
0000000000000010 = 2
+1
...
0111111111111110 = 32766 
+1
0111111111111111 = 32767 
+1
1000000000000000 = -32768
+1
1000000000000001 = -32767
+1 
1000000000000010 = -32766
...

TKJ-asiaa¶

Tästä eteenpäin materiaali sivun loppuun asti on TKJ-asiaa ja muille varsin hyvä tietää! Tämä asia käydään läpi TKJ-osuudessa, mutta JTKJ-opiskelijat voivat toki siihen perehtyä.

Liukulukuesitys¶

Katsotaan ensin miten binääriluvuille esitetään desimaalit? No, ihan vastaavasti desimaalipilkulla kuten kymmenjärjestelmässäkin. Kuvasta huomaamme, että desimaalipisteen vasemmalla puolella olevat kakkosen potenssit ovat positiivisia ja oikealla puolen negatiivisia.

Esimerkki.

Binääriluku 10.101 = 1*2^1 + 0*2^0 + 1*2^-1 + 0*2^-2 + 1*2^-3 = 2 + 0 + 1/2 + 0 + 1/8 = 2.625
Binääriluku 101.01 = 4 + 0 + 1 + 0 + 1/4 = 5.25
Binääriluku 1010.1 = 8 + 2 + 1/2 = 10.5
Binääriluku 0.111111 on desimaalilukuna 0 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 = 63/64 = 0.984375

Johtuen rajallisesta määrästä bittejä, pääsemme binäärisen desimaaliluvun esityksessä vain tiettyyn tarkkuuteen asti. Esimerkissä yllä pienin luku, joka voidaan valitulla bittimäärällä esittää oli joko 1/8 tai 1/64. Ts. pienin esitettävä arvo on LSB:tä vastaavan bitin arvo. Tästä syystä voimme binääriluvuilla esittää vain arvioita desimaaliluvuista.

Esimerkki.

Oletetaan 8-bittinen luku, josta on kokonaislukuosa 4 bittiä ja desimaaliosa myös 4 bittiä. 
Tällöin pienin luku, minkä voimme esittää on 00000001 = 2^-4 = 1/16 = 0.0625

Mutta.. miten esität binääriluvuilla desimaaliluvun, jota ei voi esittää 2:n kokonaislukupotensseilla (2^-n) valitussa tarkkuudessa.. esimerkiksi 1/3? No näissä tapauksissa desimaaliluku on yhtä päättymätön kuin peruskoulun matematiikassakin eli bittiesitykseen tulee toistoa, jolloin 1/3 = 0.01010101010101...

Jos desimaalipisteen paikka on määritelty, eli desimaaleja on aina sovittu määrä, puhutaan fixed-point-aritmetiikasta (suom. kiinteän pilkun aritmetiikka). Sitten taas floating point (liukuva pilkku) -esitys tarkoittaa sitä, että desimaalipisteen paikka "liukuu" tarpeen mukaan bittien välillä. Mutta, edelleen johtuen rajoitetusta bittimäärästä, voimme esittää vain arvion desimaaliluvusta.

Binääriluvun pyöristys¶

Samoin kuin kymmenjärjestelmän desimaalilukuja, myös binäärilukuja voidaan pyöristää. Syy miksi asia esitetään tässä, johtuu siitä että liukulukumuunnokset tekevät aika karkeita pyöristyksiä...

Tarkastellaan asiaa esimerkin kautta. Pyöristetään binääriluku lähimpään 1/4:n. Nyt pyöristystarkkuus mihin päästään on kaksi bittiä desimaaliosassa .xx (2^-2 = 1/4). Nyt pidetään binäärilukua 100 puolivälinä, jonka mukaan pyöristys ylös- tai alaspäin tehdään.

Pyöristyksessä lähdetään purkamaan lukua pyöristystarkkuutta edeltävistä biteistä:

Jos kahden viimeisen bitin xx edellä oleva bitti (eli puolivälin bitti) on 0xx, tällöin pyöristetään alaspäin.
Jos kahden viimeisen bitin xx edellä oleva bitti on 1xx, otetaan se mukaan pyöristykseen eli

(Jos kolme bittiä xxx ovat < 100, pyöristetään alaspäin)
Jos kolme bittiä xxx ovat > 100, pyöristetään ylöspäin
Jos kolme bittiä xxx = 100, huomioidaan taas edellä oleva bitti

Jos neljäs bitti on 1xxx, pyöristetään ylöspäin
Jos neljäs bitti on 0xxx, pyöristetään alaspäin

Esimerkkejä. Pyöristys 1/4 tarkkuuteen, eli .xx

10.00011 // nyt kaksi viimeistä bittiä ovat 11 ja edellä 0, joten pyöristyy alaspäin, eli 10.00 (=2)
10.00110 // pyöristyy ylöspäin, eli 10.01 (=2 1/4)
10.11100 // pyöristyy ylöspäin, eli 11.00 (=3)
10.10100 // pyöristyy alaspäin, eli 10.10 (=2 1/2)

IEEE 754 liukulukustandardi¶

Yleinen liukulukujen esitys tietokoneen muistissa perustuu IEEE 754-standardiin, jonka esityksen käymme läpi pääpiirteissään seuraavassa. Standardissa määritellään liukulukuja kahta tyyppiä: yksinkertaisen ja kaksinkertaisen tarkkuuden liukuluvut.

Liukuluvun esityksessä siihen kuuluu kolme osaa:

Etumerkki s, jossa s=0 on positiivinen ja s=1 on negatiivinen.
Murto-osan (engl. fractional) esitys

M = 1 + xxx = 1.xxx, jossa xxx vastaa murto-osaa.
Murto-osa etsitään binääriluvusta siirtämällä desimaalipistettä (molempiin suuntiin). Kts. esimerkki alla.

Eksponenttiosa E:n esitys

E = exponent - bias
bias = (2^(n-1))-1, jossa n on exponentin bittien määrä

Yksinkertaisen tarkkuuden liukuluvuissa bias = 127 ja kaksinkertaisen tarkkuuden liukuluvuissa bias = 1023.

Liukukujen kaksi tyyppiä float (yksinkertaisen tarkkuuden, single precision, 32 bittiä) ja double (kaksinkertaisen tarkkuuden, double precision, 64 bittiä esitetään seuraavasti.

Esimerkki. Muunnetaan desimaaliluku 12345.0 float-tyypin liukuluvuksi.

Luku 12345.0 on binäärilukuna 11000000111001 * 2^0

1. Etsitään M siirtämällä desimaalipistettä vasemmalle:
   (Pilkkua siirtäessä desimaaliluvun pitää pysyä samana!)
   11000000111001  * 2^0 = 12345.0
   1100000011100.1 * 2^1 = 12345.0
   110000001110.01 * 2^2 = 12345.0
   ...
   1.1000000111001 * 2^13 -> E=13
2. Lasketaan murto-osa M:n avulla. Pudotetaan luvun edestä kokonaisosa pois ja
   saadaan 1000000111001,
   johon lisätään 10 0-bittiä, jotta sen pituus on halutut 23 bittiä,
   -> murto-osa frac = 10000001110010000000000
3. Lasketaan exponentti: Kun E=13 ja bias=127, eli exponent = E + bias = 13 + 127 = 140 eli 10001100
4. Lopuksi etumerkki s=0, koska kyseessä on positiivinen luku.

Ylläolevan esimerkin tulos on siis:

Yllämainittu liukuluvun esitys on yleinen, esimerkkinä allaoleva pieni ja söötti (jap. kawaii) esitys 8:lla bitillä. Tässä bias = 7.

Erikoistapauksia¶

Koska IEEE 754-esityksellä ei voi esittää kaikkia lukuja, esimerkiksi nollaa (kokeile itse..), niin joudutaan määrittelemään muutama erikoistapaus.

Nolla: exp = 000..0 ja frac = 000..0
Ääretön: exp = 111..1 ja frac = 000..0
NaN (not a number): exp = 111..1 ja frac erisuuri kuin 000..0

NaN esittää tapaukset joita ei voi laskea, kuten sqrt(-1), ääretön - ääretön, jne..

Liukulukujen tarkkuudesta¶

Aiemmin todettiin, että liukuluku on aina arvio desimaaliluvusta ja lisäksi siinä on pyöristysvirhettä (engl. rounding error). Tarkastellaanpa asiaa ylläolevan 8-bittisen liukuluvun esityksen kautta, koska pienellä lukualueella asiaa on helpompi visualisoida.

Kuvassa alla lukualue, kun exponentti on 4 bittiä ja murto-osa 3 bittiä. Nähdään että lukualue on tiivis lähellä nollaa, mutta harvenee lukujen suurentuessa. Alemmassa kuvassa tarkemmin lukualue lähellä nollaa.

-> Näinollen tästä esityksestä aiheutuva pyöristysvirhe on iso.

Muutetaan liukulukuesitystä niin, että exponentissa onkin nyt 3 bittiä ja murto-osassa 4 bittiä (bias on nyt 3) ja katsotaan mitä lukualueelle tapahtuu. Havaitaan että lukualue on kapeampi ja alue on tiiviimpi lähellä nollaa.

-> Muutoksen seurauksena pyöristysvirhe pienenee lukualueen sisällä.

Voidaan siis yleistää, että liukuluvun lukualuetta voidaan kasvattaa lisäämällä bittejä exponenttiin ja liukuluvun tarkkuutta (erotuskykyä) kasvattaa lisäämällä bittejä murto-osaan. Mutta aina pitää huomioida aiheutuva pyöristysvirhe.

Hox! Asia voi tuntua vähäpätöiseltä, koska standardoidut float:n ja double:n lukualueet ovat varsin isoja ja tarkkoja, mutta ei ole ensimmäinen kerta kun tieteellisessä laskennassa tarkkuus ei riittäisi tai pyöristysvirheitä ei huomioitaisi..

Lopuksi¶

Nykyisin löytyy jo 32- ja 64-bittisiä isompia liukulukujen esitystapoja.

Liukuluvun esitys on käyty yksityiskohtaisesti läpi oppikirjassa. Kurssilla riittää, että osaamme muuntaa liukulukuja esitysmuodosta toiseen.

Anna palautetta

Kommentteja materiaalista?