Pretvorba iz desetiškega sistema v ostale sisteme

Pretvorba iz desetiškega sistema v ostale sisteme in obratno, osnove Boolove algebre, seštevalniki (half adder ...)

Ljudje lahko računamo in shajamo z različnimi številskimi sistemi, a najbolj nam je domač desetiški sistem (večina jih meni, da je temu vzrok 10 prstov na naših rokah; kako bi se imenoval številski sistem, če bi imeli 12 prstov?). V desetiškem sistemu poznamo 10 osnovnih števil (znakov) (0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ), vsa ostala so izpeljana iz teh osnovnih (enajst = 11, dvanajst = 12, ... enaindvajset 21, ...). V dvojiškem imamo samo 2 števili 0, 1. Po logiki kombinacij desetiškega sistema zapišemo 0 kot 0, 1 kot 1, dve kot 10, tri kot 11, štiri kot 100, pet kot 101, sedem kot 111, osem kot 1000, devet 1001 itd. Trojiški sistem ima enako logiko: nič 0, ena 1, dva 2, tri 10, štiri 11, pet 12, šest 20, sedem 21 itd. Poglejmo kako najlažje pridemo iz desetiškega v ostale sisteme. Iz zgornjih zapisov in tudi iz logike sistemov vidimo, da so zapisi nedesetiških sistemov ostanki pri deljenju desetiškega sistema z osnovo nedesetiškega sistema (kvocientov do stopnje, ko je kvocient manjši od osnove, osnova je število znakov nekega sistema). Primer pretvorbe števil 8 in 10 v dvojiški sistem in 29 v trojiški sistem:

kvocient operacija  ostanek (8 v dvojiški)
4         8:2       0
2         4:2       0
1         2:2       0
0         1:2       1
8 je torej v dvojiškem sistemu 1000 (ostanki zapisani od spodaj navzgor)       

kvocient operacija  ostanek (10 v dvojiški)
5        10:2       0
2         5:2       1
1         2:2       0
0         1:2       1 
10 je torej v dvojiškem sistemu 1010 

kvocient operacija  ostanek (29 v trojiški)
9        29:3       2
3         9:3       0
1         3:3       0
0         1:3       1 
29 je torej v trojiškem sistemu 1002 

Pretvorba nazaj v desetiški sistem je enostavna, obratna 
(če smo prej n krat po stopnjah delili,
bomo sedaj osnovo potencirali, množili z ostankom in sešteli 
delne rezultate).
Primera:
-kot že vemo je 1010 v dvojiškem deset (10), preverimo
0*2⁰ = 0
1*2¹ = 2
0*2² = 0
1*2³ = 8
                ----
         vsota = 10
       
- 1002 je v trojiškem devetindvajset (29), preverimo
2*3⁰ =  2
0*3¹ =  0
0*3² =  0
1*3³ = 27
                ----
          vsota = 29

ZAKAJ VSE TO, različni številski sistemi (zdi se, da je desetiški sitem čisto zadosti - kot bomo videli, temu ni tako ...)? Zakaj torej še ostali sistemi?

Zaradi teorije same, zaradi logike, radovednosti, nekaj zaradi "lepote", nečimernosti, tekmovalnosti ..., tisto pa kar - ponavadi zmeraj sledi (iz, za nekatere nepotrebne, teorije) je, izjemna uporabnost teorij, miselnih iger ... Nedesetiški številski sistemi, predvsem dvojiški ("samo" dve možnosti 1, 0), predstavljajo zaradi svoje enostavnosti izjemno uporabno vrednost, recimo v računalniški procesorski tehnologiji logičnih vrat. Vrednost ena (1) namreč predstavlja napetost (ali tok) na nekem elementu, vrednost nič (0) pa stanje, ko ni napetosti (ali ni toka). S kombinacijo tranzistorjev (mikroelektronskih stikal) lahko dosežemo izjemne sposobnosti, danes skoraj že nepogrešljivih, "miselnih" strojev, to je računalnikov.

Prepustimo se igri, ki sledi v nadaljevanju.

Nekaj zgodovine.

Še pred pojavom elektronskih kalkulatorjev so v prodajalnah in uradih uporabljali mehanske seštevalne stroje. Če izvzamemo nekaj izboljšav, jih poznamo nespremenjene skoraj 300 let. Njihovo delovanje je zasnovano na prenosnem razmerju zobatih koles. Prvi seštevalni stroj je izdelal Pascal za uporabo v očetovem uradu (matematik in filozof Blaise Pascal 1623-1662 je bil praktičen in hkrati zelo duhoven krščanski um, znane so njegove Misli, ki še danes ostajajo izziv). Množenje in deljenje je tovrstnemu stroju dodal Leibniz. Tako je bil mehanski kalkulator pripravljen za množično uporabo.
Dvojiška števila je prvi omenjal Francis Bacon leta 1623. Že omenjeni Gottfried Wilhelm Leibniz (1646-1716), veliki matematik in filozof, je med drugim odkril možnost uporabe dvojiške aritmetike. Na stara leta je prišel v spor z Newtonom glede prvenstva pri uvedbi diferencialnega računa (odvodi, integrali). George Boole 1815-1864, angleški logik in matematik je vpeljal logiko skozi algebro vrednosti 0 in 1, kar je direktno povezano z dvojiškim (binarnim) sistemom, logičnimi vrati in razvojem modernih računalniških procesorjev.

Pretvorba iz desetiškega v ostale sisteme s funkcijo toString.
Vstavi desetiško število:

Results (pretvorba v sistem - max. do 36):

Zakaj pretvorbe do 36-iškega sistema in kaj pomenijo črke v zapisu številskih sistemov nad 10. Poglejmo primer.
29 zapišimo v 16-inski sistem (opomba: 16-tinski ali heksadecimalni sistem je, poleg dvojiškega, takorekoč privzet v računalništvu).
29:16 = 1 ostane 13
1 :16 = 0 ostane 1
Zapis 113 bi bil zavajujoč, večsmiseln, zato 13 nadomestimo s četrto (13-9=4) zaporedno malo tiskano črko angleške abecede, to je z d. 29 v 16-inskem sistemu je torej 1d. Pretvorba nazaj pa je (d*16⁰+1*16¹=13*16⁰+1*16¹)=13+16=29). Ni težko izračunati, da ta nadomestitev gre do 36-inskega sistema, saj velja 26_črk + 9 + 1 = 36 (+1 za ostanek 0, skupaj 36). Glej tabelo stevilskih prireditev angleški abecedi:
a=10, b=11, c=12, d=13, e=14, f=15, g=16, h=17, i=18, j=19, k=20, l=21, m=22, n=23, o=24, p=25, q=26, r=27, s=28, t=29, u=30, v=31, w=32, x=33, y=34, z=35
Zgornja tabela je upoštevana pri pretvorbi nazaj v desetiški sistem.

2)
Pretvorba iz ostalih sistemov v desetiškega

-uporabil function vdesetiskix(osnova,stevilo) in jo implementiral v
function vdesetiski(form) {
form.result2.value = vdesetiskix(form.sis2.value,form.xx.value);
}
-uporabi jo spodaj

Vpiši sistem iz katerega pretvarjaš (do 36):
Vstavi nedesetiško število (ne uporabljaj exp. zapisa):

Results2 (pretvorba v desetiški sistem):

Boolova algebra in logična vrata (IN, ALI, XALI, NE)
Računanje z 1 in 0, računalniška logika.
BOOLOva pravila za logična vrata:
ALI vrata        IN vrata       XALI vrata       NE vrata
0 ali 0 = 0      0 in 0 = 0     0 xali 0 = 0     ne 1 = 0
0 ali 1 = 1      0 in 1 = 0     0 xali 1 = 1     ne 0 = 1
1 ali 0 = 1      1 in 0 = 0     1 xali 0 = 1
1 ali 1 = 1      1 in 1 = 1     1 xali 1 = 0

Vsa ta vrat se seveda dajo zanikati z NE vrati, tako dobimo:
NE IN, NE ALI, NE XALI vrata.

a)
Izberi znak (in(AND) = &, ali(OR) = |, xali(XOR)=^):
xy=> z  
    
    
    
    

b)
ne (NOT)=~ (binarno zanikanje, zmeraj glej zadnje desno mesto 
            binarnih zapisov, 0 gre v 1 in 1 v 0)
x   NE(~)x 
    ~ ( binarni zapis za x in za ~x )
                            (levi pomik << za 1  ~x)
Kot vidimo je operacija zanikanja pomembna tudi za 
generiranje negativnih števil.




4)
Računanje z 1 in 0, računalniška logika, BOOLOva pravila

Pri Boolovi algebri se najprej izvede negacija "NE", 
nato "IN (&)" operacija in nazadnje "ALI (|)" operacija.

a)
Forma za izračun poljubnih boolovih izrazov (ročni vnos), 
recimo: 0 | (0 & ( 0 | 1 | 0 )) 
 
 

Rezultat  



b)
Forma za izračun boolovih izrazov s kombinacijo 
treh spremenljivk (x,y,z).

Zanikamo tako, da vnesemo velike črke: X=ne(x), Y=ne(y), Z=ne(z)
   
Vpiši operacijo  
x   y   z   izraz       rezultat
    
    
    
    
    
    
    
    

Nekaj kombinacij (testiraj):
x | y & Z
X | ( z & Y | x)
x & Y | z & (Z | X & y | z)
Y | (x & (Y | z | X))
Z & y & X | y & Z | x

5) Nekaj primerov računanja z binarnimi števili.


Primeri dvojiškega seštevanja, odštevanja, dvojiški komplement, množenja

Seštevanje (enaka pravila kot pri desetiškem sistemu, le da vse parcialne 
vsote spremenimo v dvojiški sistem):
 (3)    11
+(5)  +101
---   ----
8     1000 
            ( komentar, desni stolpič: 1+1=2 je 
              v dvojiškem 10, 0 ohranimo 1 prenesemo v levo, naslednji
              stolpič: 1+0+1_prenos=2, kar je 10, 0 ohranimo 1 prenesemo, 
              levi stolpič: 1+1_prenos=2, kar je 10, 
              0 ohranimo 1 gre za mesto levo, tako dobimo 1000, to je 8 )      

 (4)   100
+(6)  +110
---   ----
10    1010 

 (3)    11
+(5)  +101 
+(7)  +111
---   ----
 15   1111 
            ( komentar, desni stolpič: 1+1+1=3, v dvojiškem je to 11, 
              1 ohranimo in levo enko prenesemo levo itd )


Odštevanje - dvojiški komplement
Račun 16-12=4, lahko zapišemo kot seštevanje 16+(-12)=4, to logiko
uporabi tudi računlnik pri odštevanju, odšteva torej tako, da prišteje 
negativno število.

Poglejmo si preprost primer le za petmestna dvojiška števila ABCDE 
(ostala morebitna mesta na levi naš preprost računalnik odreže xyABCDE=ABCDE).
Prvo levo število naj bo rezervirano za predznak (1 je plus +, 0 je minus -) 
1BCDE je pozitivno število, 0ABCD pa negativno.
Binarno 10000 je 16, ker pa je leva številka 1, hkrati nas zapis 
predstavlja negativno število -16.
Kako lahko torej predstavimo števila od -16 do +15, primeri: 
-15 = -16 + 1 lahko predstavimo kot 10000 +    1 = 10001
-14 = -16 + 2 lahko predstavimo kot 10000 +   10 = 10010
  .
  .
  .
 -9 = -16 + 7  .................... 10000 +  111 = 10111   
  .
  .
  .
 -3 = -16 + 13  .................... 10000 + 1101 = 11101 
 -2 = -16 + 14  .................... 10000 + 1110 = 11110 
 -1 = -16 + 15  .................... 10000 + 1111 = 11111
  0 =                                               00000
  1 =                                               00001
  2 =                                               00010
   .
   .
   .
 14 =                                               01110
 15 =                                               01111

Uporabimo zgornjo logiko pri odštevanju:
-primer 12 - 4 = 8 (-4 = -16 +12 = 10000 + 1100 =11100; 12 = 1100 = 01100)
  + 12     01100
  -  4     11100    
   ---     -----
     8    101000 => 01000 = 8
                    ( dobimo 6 mest, a kot smo se že dogovorili,
                      naš računalnik "odvečna" leva mesta odreže,
                      na zapisu 101000 vidi samo 01000 kar je 8) 


-primer 7 - 16 = -9
  +  7     00111
  - 16     10000    
   ---     -----
    -9     10111 =>  -9

-primer -3 - 4 = -7
  -  3     11101
  -  4     11100    
   ---     -----
    -7    111001 => odrežemo skrajno levo mesto in dobimo 11001 = -7




Množenje
Množenje z binarnimi števili je načeloma enako kot z desetiškimi. 
Vsota 1 + 0 je 1, vsota 1 + 1 = 2 v dvojiškem pa (10), 1 prenesemo 
(za mesto levo), 0 ohranimo. Enako velja za 1+1+1 =3, v dvojiškem 
11, 1 ohranimi in 1 prenesemo; za 1+1+1+1+1 = 5 velja 1001, desno 
enko ohranimo, leve vrednosti prenesemo v levo. Glej primere.

-primer 1                                     -primer 2  
14X12      v dvojiškem sistemu  => 101X11    |      14X12
-----                              ------    |      -----
   28                                 101    |       0000
+14                                 +101     |      0000
-----                              ------    |     1110
 168                                 1111    |    1110 
                                             |    --------
                                             |   10101000     to je (168)     


- primer 3
             45X31 =1395 
             101101X11111
             ------------
                   101101
                  101101
                 101101
                101101
               101101
              -----------
              10101110011 => 1395
             (12243534211 - vsote zaradi seštevanja nad črto in binarnih ostankov )





Logična vrata in preproste operacije

Polovični seštevalnik (half adder, H.A.), ki sešteva dve enomestni binarni 
števili (x+y=cs, 0+0=0=00, 0+1 ali 1+0=1=01, 1+1=2=10).
c je prenos s je vsota.
Testiraj spodnja vrata s signaloma x in y.
(lahko narediš simulacijo z javascriptom)
x+y=cs desetiška_vsota
0 0 00 0
0 1 01 1
1 0 01 1
1 1 10 2



Slika konbinacije vrat za polovični seštevalnik (half adder).

Testiraj spodnjo shemo half adderja (x+y= ):


 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 




x 
 

 _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _   ALI 
   _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
IN         vsota 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
(  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  IN 
     _  NE 
    _  _ 
_  _  _ 



y 
 

 _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 



 
_  _  _ 
_  _  _ 
_  _  _ 
_  _  _ 
_     prenos 




Rezultat half adderja (x+y)=  





Celi seštevalnik (full adder, F/A.), treh enomestnih števil.
z = vhodni prenos, c = prenos, s = vsota
x+y+z=cs desetiška_vsota
0 0 0 00 0
1 0 0 01 1
0 1 0 01 1
0 0 1 01 1
0 1 1 10 2
1 0 1 10 2
1 1 0 10 2
1 1 1 11 3 

Slika konbinacije vrat za celi seštevalnik (full adder).


Spodaj je vezje sestavljeno iz half adderjev (H.A., H/A) in 
or vrat, ki sešteva par trimestnih binarnih števil do 
vsote 15, oziroma 14. Preveri.

Testiraj seštevalnik, tako da izbiraš x in y, z se sam binarno računa nato se pretvori v desetiški rezultat.

z(S0 S1 S2 S3) => desetiški rezultat je z = x+ y=

Izhodi iz H.A.-jev in OR vrat: hac1 has2 hac2 hac3 ali1 hac4 has4 hac5

x( A0 A1 A2 ) izberi x

y( B0 B1 B2 ) izberi y (drugi način, 1 ali 0 dobiš s pritiskom na gumbe)

Oglej si tudi potek delovanja seštevalnika na sliki z AKTIVNIMI vhodi in izhodi!!!!!!!!!!


H.A. je half adder (polovični seštevalnik)
x=(A0 A1 A2) je prvo trimestno dvojiško število, y=(B0 B1 B2)
je drugo trimestno dvojiško število, z=(S0 S1 S2 S3) je 
dvojiški rezultat. Če (3+4=7) in 3 => x(A0=1, A1=1) 
in 4 => y(B0=0, B1=0, B3=1), na izhodu dobimo 
z(S0=1, S1=1, S2=1, S3=0)=7.


8 bitni seštevalnik


8 bitni seštevalnik. Zgornja vrsta predstavlja prvo in  
vrsta pod njo drugo dvojiško število. Spodnja vrsta je 
namenjena rezultatu. Rdeče črte so prenos (carry).
Preveri rezultat na shemi.
Opomba: (1 bit predstavlja eno mesto 1 ali 0),
8 bitov je en zlog ali byt (beri bajt).

TESTIRAJ spodnjo javascript simulacijo 8-bitnega seštevalnika.

število x: A7 A6 A5 A4 A3 A2 A1 A0

število y: B7 B6 B5 B4 B3 B2 B1 B0

prenos: C7 C6 C5 C4 C3 C2 C1 C0

vsota z: S8(C7) S7 S6 S5 S4 S3 S2 S1 S0
desetiški rezultat je z = x+ y=

Se dopolnjuje!

Najbrž ste že utrujeni, a nekaj primerov vas je najbrž prepričalo, da se da z 1 in 0 in s pametnimi kombinacijami logičnih vrat lepo računati in to je bil tudi moj cilj. Računalnik počne ravno to in tudi ta stran-vsebina je posledica iste logike.

Avtor, Zorko Vičar
-leto: 2002 (11111010010)