Binært tallsystem

Fra Wikipedia, den frie encyklopedi

Det binære tallsystem (også totallsystemet) representerer numeriske verdier ved å bruke to symboler, som oftest sifrene 0 og 1.

Mer nøyaktig, er det binære tallsystem et posisjonssystem med grunntall to. På grunn av dens relative enkle implementasjon i elektroniske kretser blir totallsystemet brukt internt i så å si alle moderne datamaskiner.

Historie[rediger | rediger kilde]

Den første kjente beskrivelse av et totallsystem ble gjort av den indiske matematikeren Pingala i sin Chhandah-shastra, og er tidsfestet til det femte eller det andre århundret f.Kr. Pingala beskrev det binære tallsystem i sammenheng med en opplisting av vediske meter med korte eller lange vokaler. Ifølge den indiske tradisjon er Pingala den yngre broren til grammatikeren Panini.

Selv om den britiske filosofoen Francis Bacon tidligere hadde beskrevet et utviklet system for skjult binær enkoding til bruk i kryptering, ble det moderne binære totallsystem først fullt ut dokumentert av Gottfried Leibniz i det 17. århundre i hans artikkel Explication de l'Arithmétique Binaire. Mens Pingalas system bruker symbolene 1 og 2, bruker Leibniz 0 og 1 som det moderne totallsystemet.

Den britiske matematikeren George Boole publiserte i 1854 en forskningsartikkel som beskrev et logisk system som senere skulle bli kjent som boolsk algebra. Det viste seg at hans logiske system var nyttig i utviklingen av det binære system, særlig i implementeringen av den i elektroniske kretser.

Claude Shannon skrev sin masteravhandling A Symbolic Analysis of Relay and Switching Circuits i 1937. Denne beskrev for første gang i historien boolsk algebra og binær aritmetikk implementert med elektroniske reléer og brytere. Avhandlingen grunnla praktisk talt teorien bak design av digitale kretser.

George Stibitz, som da jobbet ved Bell Labs, ferdigstilte i november 1937 en relebasert datamaskin som han kalte for «Modell K» (etter «kjøkken», hvor han hadde satt den sammen), som kunne regne ved å bruke binær addisjon. Bell Labs godkjente derfor et forskningsprogram i slutten av 1938 med Stibitz ved roret. Deres Complex Number Computer, som ble ferdig den 8. januar 1940 kunne regne med komplekse tall.

I en demonstrasjon ved American Mathematical Society-konferansen ved Darthmouth College den 11. september 1940 kunne Stibbitz sende kommandoer over telefonlinjen til maskinen med en fjernskriver. Det var den første beregningsbaserte maskinen som noengang hadde blitt kontrollert over en telefonlinje. Noen av deltagerne på konferansen som overvar demonstrasjonen var John von Neumann, John Mauchly og Norbert Wiener som skrev om dette i sine memoarer.

Fremstilling[rediger | rediger kilde]

Et binært tall kan bli representert ved enhver sekvens av biter (binary digits, binære siffer), som i sin tur kan bli representert ved hjelp av enhver mekanisme som er i stand til å være i to gjensidige utelukkende tilstander. De følgende sekvenser av symboler kunne alle bli tolket som forskjellige binære numeriske verdier:

1 1 0 1 0 0 1 1
| | - | − - | |
x x o x o o x x
J J N J N N J J
på på av på av av på på
sann sann usann sann usann usann sann sann
En binær klokke kan bruke LED for å uttrykke binære verdier. I denne klokken viser hver kolonne av LED-lys et binært tall.
Binært armbåndsur som viser tiden 3:25. De fire øverste diodene er for timer, de seks nederste er for minutter. Man summerer de diodene som lyser. 1 + 2 = 3 og 1 + 8 + 16 = 25 (3:25)

Den binære verdien som blir representert i hvert tilfelle er avhengig av verdien som man gir hvert symbol. I en datamaskin kan de numeriske verdiene bli representert av to forskjellige spenninger; på en magnetisk disk kan magnetiske polariteter bli bruk. En «positiv», «ja» eller «på» -tilstand er ikke nødvendigvis lik den numeriske verdien av én; det avhenger av hvilken arkitektur som er i bruk.

På samme måte som man som oftest skriver tall ved å bruke arabiske tall blir binære tall som oftest skrevet ved å bruke symbolene 0 og 1. Binære tall blir ofte markert med senket skrift eller med en endelse) for å indikere grunntallet. De følgende skrivemåtene er ekvivalente:

100101 binary (eksplisitt markering av format)
100101b (en ending som indikerer binært format)
bin 100101 (en prefiks som indikerer binært format)
1001012 (senket skrift som indikerer grunntall-2 notasjon)

Binære tallverdier blir som oftest uttalt ved å uttale hvert enkelt siffer for å kunne skille dem fra desimale tall. For eksempel blir det binære tallet «100» uttalt «en null null» i stedet for «hundre» for å markere eksplisitt at det er et binært tall, og siden det er mer korrekt. Siden det binære tallet «100» er likt fire desimalt ville det vært forvirrende og numerisk ukorrekt å kalle tallet for «hundre». Er man vant med å jobbe med binære tallverdier er det både nærliggende og korrekt å kalle tallet for «fire».

Telling binært[rediger | rediger kilde]

Å telle i det binære tallsystem er likt som å telle i hvilket som helst annet tallsystem. Man starter med et enkelt siffer, og tellingen fortsetter gjennom hvert symbol i økende rekkefølge. Det desimale tallsystemet bruker symbolene 0 til 9, mens det binære bruker bare symbolene 0 og 1.

Når man ikke har flere symbol for det første sifferet, øker man det neste høyere sifferet, og tellingen starter på nytt igjen på 0. I det desimale tallsystemet går tellingen slik:

00, 01, 02, ... 07, 08, 09 (man begynner på nytt igjen på sifferet helt til høyre, og 0 blir økt)
10, 11, 12, ... 17, 18, 19 (man begynner på nytt igjen på sifferet helt til høyre, og 1 blir økt)
20, 21, 22, ...

Når sifferet helt til høyre når 9, starter tellingen igjen på 0, og det andre sifferet blir økt.

Tellingen er lik i totallsystemet, men siden man bare har to symboler er det slik at når 1 blir nådd, starter tellingen på 0 igjen, og siffert til venstre øker:

000, 001 (sifferet til høyre starter på nytt, og den andre 0 øker)
010, 011 (sifrene i midten og helt til høyre starter på nytt, og 0-tallet helt til venstre øker)
100, 101 (sifferet helt til høyre begynner på nytt, 0-tallet i midten øker)
110, 111...

Binær aritmetikk[rediger | rediger kilde]

Aritmetikk i totallsystemet er veldig likt aritmetikk i andre tallsystemer. Addisjon, subtrahering, multiplikasjon og divisjon kan gjøres på binære tall.

Addisjon[rediger | rediger kilde]

Den enkleste aritmetiske operasjon binært er addisjon. Å legge til to ensiffrede binære tall er relativt enkelt:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 (1 i mente)
1 + 1 + 1 = 11 (1 i mente)

Å addere to «1»-verdier gir verdien «10» som er ekvivalent med den desimale verdien 2. Dette er likt det som skjer i det desimale tallsystemet når enkelt ensiffrede tall er lagt sammen; hvis resultatet overstiger verdien av grunntallet (10), blir sifferet til venstre økt:

5 + 5 = 10
7 + 9 = 16

Dette er kjent som mente i de fleste tallsystemer.

  1 1 1 1 1     (mente)
    0 1 1 0 1
+   1 0 1 1 1
-------------
= 1 0 0 1 0 0

I dette eksempelet blir to tall lagt sammen: 01101 (13 desimalt) og 10111 (23 desimalt). Den øverste raden viser mentesifrene som blir brukt. Hvis man starter i kolonnen ytterst til høyre ser vi at 1 + 1 = 10. 1-tallet blir satt opp i mente, og 0-sifferet er skrevet nederst i kolonnen til høyre. Den andre kolonnen fra høyre er lagt sammen: 1 + 0 + 1 = 10 igjen; 1-tallet blir overført i mente og 0 er skrevet på bunnen. Den tredje kolonnen: 1 + 1 + 1 = 11. Denne gangen blir 1-tallet overført og et 1-tall er skrevet nederst. Hvis man fortsetter på denne måten får man sluttsvaret 100100.

Subtrahering[rediger | rediger kilde]

Subtrahering virker på stort sett samme måte:

0 - 0 = 0
0 - 1 = 1 (med låning)
1 - 0 = 1
1 - 1 = 0

Et binært tall kan bli subtrahert fra et annet på følgende måte:

    *   * * *   (kolonner med stjerne har blitt lånt fra)
  1 1 0 1 1 1 0
–     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1

Å subtrahere et positivt tall er ekvivalent til å addere et negativt tall med lik absoluttverdi; datamaskiner bruker vanligvis toerkomplement notasjonen for å representere negative verdier. Denne notasjonen eliminerer behovet for en eget "trekke-fra"-operasjon. For flere detaljer, se toerkomplement.

Multiplikasjon[rediger | rediger kilde]

Multiplisering i det binære tallsystemet er tilsvarende metoden i det desimale tallsystemet. To tall A og B kan bli mulitplisert ved delvise produkter: for hvert siffer i B blir produktet av det sifferet i A utregnet og skrevet på en ny linje, et hakk til venstre for hver gang. Summen av alle disse delvise produktene gir sluttresultatet.

Siden det bare finnes to siffer i det binære tallsystemet, finnes det bare to mulige resultat av hver delvise multiplisering:

  • Hvis sifferet i B er 0, blir det delvise produktet også 0
  • Hvis sifferet i B er 1, blir det delvise produktet likt A

For eksempel blir de binære tallene 1011 og 1010 multiplisert som følger:

           1 0 1 1   (A)
         × 1 0 1 0   (B)
         ---------
           0 0 0 0   ← Tilsvarer til null i B
         1 0 1 1     ← Tilsvarer til en i B
       0 0 0 0
   + 1 0 1 1
   ---------------
   = 1 1 0 1 1 1 0

Dividering[rediger | rediger kilde]

Dividering i det binære tallsystemet er likt metoden brukt i det desimale tallsystem:


Bitvise logiske operasjoner[rediger | rediger kilde]

Selv om det ikke er direkte relatert til den numeriske tolkningen av binære symboler, kan sekvenser av bits bli manipulert ved å bruke Boolske logisk operator. Når en streng med binære symboler blir manipulert på denne måten kalles det en bitvis operasjon.

De logiske operandene AND, OR og Eksklusiv disjunksjon kan bli utført på samsvarende bits på to binære tall. Den logiske NOT operasjonen kan bli utført på individuelle bits i et enkelt binærtall.

Slike operasjoner kan enkelte ganger bli brukt som aritmetiske snarveier, og kan også ha andre fordeler ved utregning. For eksempel kan man kutte av den siste biten av et binært tall (også kjent som binærskifting), tilsvarer å dele på to desimalt.

Se bitvis operasjon.

Konvertering til og fra andre tallsystemer[rediger | rediger kilde]

Desimal[rediger | rediger kilde]

Denne metoden fungerer for konvertering fra alle grunntall, men det finnes bedre metoder for grunntall som er kvadrater av to, som for de oktale og heksadesimale tallsystemene beskrevet under.

Siffre i posisjoneringstallsystemer på lavere eller mindre signifikante posisjoner representerer stadig lavere potenser av grunntallet. Starteksponenten er en mindre enn antall siffre i tallet. Et femsifret tall starter med en eksponent på fire. I det desimale systemet er grunntallet ti, så sifferet helt til venstre i et femsiffret tall representerer 104 (titusen) posisjonen. F.eks.:

9735210 er lik:
9 ganger 104 (9 × 10000 = 90000) pluss
7 ganger 103 (7 × 1000 = 7000) pluss
3 ganger 102 (3 × 100 = 300) pluss
5 ganger 101 (5 × 10 = 50) pluss
2 ganger 100 (2 × 1 = 2)

Å multiplisere med grunntallet er enkelt. Man flytter siffrene et hakk til venstre, og 0 er lagt til høyresiden av tallet. For eksempel, 9735 ganger 10 er lik 97350. Derfor er en måte å tolke en streng med siffer er at det siste sifferet [?]. 97352 er lik 9735 ganger 10 pluss 2. Et eksempel på binær form er 11011001112 er lik 1101100112 ganger 2 pluss 1. Dette er essensen i konverteringsmetoden. I hvert steg skriver en nummeret som skal konverteres som 2*k + 0 eller 2*k + 1 for et heltall k som

blir det nye tallet som skal konverteres.

11810 er lik
59 x 2 + 0
(29 x 2 + 1) x 2 + 0
((14 x 2 + 1) x 2 + 1) x 2 + 0
(((7 x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
((((3 x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
(((((1 x 2 + 1) x 2 + 1) x 2 + 0) x 2 + 1) x 2 + 1) x 2 + 0
1 x 26 + 1 x 25 + 1 x 24 + 0 x 23 + 1 x

22 + 1 x 21 + 0 x 20

'11101102

algoritmen for å konvertere en heltallsdesimaltall til sin binære form er å dele tallet på to, og skrive resten på ett-posisjonen. Resultatet er igjen dividert på to, og resten skrevet på den neste posisjonen til venstre. Denne prosessen gjentar man til nummeret når null.

For eksempel er 11810 binært:

Operasjon Rest
118/2 = 59 0
59/2 = 29 1
29/2 = 14 1
14/2 = 7 0
7/2 = 3 1
3/2 = 1 1
1/2 = 0 1

Hvis man leser sekvensen av rester fra bunnen og oppover får man det binære tallet 11101102.

For å konvertere fra binært til desimalt gjør man det hele omvendt. Man starter fra venstre, og dobler resultatet og legger til neste siffer til det ikke finnes flere. I eksempelet konverteres 1100101011012 til desimalform:

Resultat Gjenværende siffer
0 110010101101
0*2 + 1 = 1 10010101101
1*2 + 1 = 3 0010101101
3*2 + 0 = 6 010101101
6*2 + 0 = 12 10101101
12*2 + 1 = 25 0101101
25*2 + 0 = 50 101101
50*2 + 1 = 101 01101
101*2 + 0 = 202 1101
202*2 + 1 = 405 101
405*2 + 1 = 811 01
811*2 + 0 = 1622 1
1622*2 + 1 = 3245

og resultatet er 324510.

Heksadesimalt[rediger | rediger kilde]

Da heksadesimaltallenes basis 16 = 24, vil en konvertering være særlig enkel - et heksadesimalt siffer representerer en gruppe av fire binære sifre.

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

Eksempel: 3F816 = 0011111110002

Også desimale tall kan legges til i tabellen. Da vil ikke tabellen vise bokstaver etter 1001 (9) i binære tallsystemet, men resten av tallene som 10, 11 og 12 og videre feks:

Desimale tall til venstre nedenfor . binære tall til høyre nedenfor.

    0               0000
    1               0001
    2               0010
    3               0011
    4               0100
    5               0101
    6               0110
    7               0111
    8               1000
    9               1001
   10               1010
   11               1011
   12               1100
   13               1101
   14               1110
   15               1111

Oktalt[rediger | rediger kilde]

Oktaltallenes basis er 23 – et oktalt siffer representerer en gruppe av tre binære siffre.

Oktalt Binært
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Eksempel: 1738 = 0011110112

Brøk[rediger | rediger kilde]

I titallsystemet heter desimalene tideler, hundredeler, tusendeler, titusendeler, hundretusendeler osv. Disse tallene er henholdsvis 10−1, 10−2, 10−3, 10−4, 10−5.

Sifrene til høyre for kommaet i totallsystemet representerer (i rekkefølge fra venstre mot høyre) 2−1, 2−2, 2−3, 2−4, 2−5 osv. Disse tallene er med andre ord 1/2, 1/4, 1/8, 1/16 og 1/32.

Tallet 0,01 i totallsystemet er en firedel. Ved å summere 0,1 og 0,001 får man at tallet 0,101 i totallsystemet er en halv pluss en åttedel, det vil si fem åttedeler.

Se også[rediger | rediger kilde]