HW moj milovany :(: HW: Zakladne operacie nad dvojkovymi cislami i v doplnkovom kode

Doporucujem vopred precitat
http://mycvut.blogspot.com/2011/06/hw-zobrazenie-cisel-so-znamienkom-v.html
http://mycvut.blogspot.com/2011/06/hw-radova-mriezka.html

a ak mate este naladu
http://mycvut.blogspot.com/2011/06/hw-polyadicke-ciselne-sustavy-prevody.html

Zakladne operacie, ktorymi sa budeme zaoberat su

scitanie
odcitanie
posuvy

Myslim, ze najlepsie to bude koncipovat tak, ze spravime operacie v desiatkovej sustave a potom v dvojkovej a v doplnkovom kode.

Scitanie

Scitanie v desiatkovej sustave mame vsetci perfektne zmaknute :). Scitanie, aj s prenosom, funguje rovnako v dvojkovej sustave a doplnkovom kode.

159

+19

---------

178

Uvedomte si, co robite pri sucte cisel v 10-ovej sustave. Scitate cisla od najnizsieho po najvyssi rad. Ak sa dostanete na vyssi rad, tak z toho spravite prenos a pricitate k dalsiemu cislu. Na papieri si dokonca nemate problem zvacsit mriezku. Takyto problem v pamatiach a registroch sa riesi zaokruhlovanim, skracovanim/rozsirovanim (vid radova mriezka).

1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 (159)

+ 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1

= 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0

Z kapitoly o doplnkovom kode je nam uz zname formalne vyjadrenie

D(A) =

A; 0 <= A < 1/2 Z
Z + A; -1/2*Z <= A < 0

v nasom pripade je n = 7, m = 0, z = 2. Preto, Z = z^(n+1) = 2^8 = 256. Znamena to, ze najvacsie zobrazitelne cislo je 255 a zaroven to znamena, ze A > 1/2 Z = 128. Mame tu cislo, ktore nemozme zobrazit v doplnkovom kode, pretoze chceme zobrazit kladne cislo v casti, kde mam miesto pre obrazy zapornych cisel. Musime si zvolit inak:

n = 3, m = 2, z = 2

Z = 2^4 = 16 => zvolime A, tak ze 0 < A < 1/2 Z A = napriklad 5 a 5 = 2 + 3

bez doplnkoveho kodu v doplnkovom kode

0 | 0 | 1 | 0 0 | 0 | 1 | 0

+ 0 | 0 | 1 | 1 + 0 | 0 | 1 | 1

= 0 | 1 | 0 | 1 = 0 | 1 | 0 | 1

Easy, ze? A easy hlavne preto, ze obe cisla zobrazujeme rovnako, nakolko pre cisla medzi 0 a 1/2Z je v obraz D(A) = A :).

Odcitanie

Tu mame sitaciu trochu zapeklitejsiu. V dvojkovej sustave to funguje rovnako, ako v desiatkovej. Problemy nam bude robit doplnkovy kod.

n = 3, m = 3, z = 2 alebo z = 10

v doplnkovom kode bude mensitel D(A) = Z + A; kde Z = 16

1 0 0 0 0, 0 0 0

- 0 1 0 0 ,0 0 1

= 0 1 0 1 1, 1 1 1

z = 10 z = 2 D(A)

0 | 0 | 0 | 4, | 5 | 0 | 0 0 | 1 | 0 | 0, | 1 | 0 | 0 0 | 1 | 0 | 0, | 1 | 0 | 0

- 0 | 0 | 0 | 4, | 1 | 2 | 5 - 0 | 1 | 0 | 0, | 0 | 0 | 1 - 1 | 0 | 1 | 1, | 1 | 1 | 1

= 0 | 0 | 0 | 0, | 3 | 7 | 5 = 0 | 0 | 0 | 0, | 0 | 1 | 1 = 1 | 1 | 0 | 0 | 1, | 1 | 0 | 1

Urcite tusite, ze sa niekde stala chyba. V doplnkovom kode totiz nemozme spachat nieco takeho, ako som tam spachal ja. Musime na to ist inak

bud odcitame doplnkove kody oboch cisel a ignorujeme pozicku z vyssieho radu
alebo prevedieme odcitanie na scitanie (k mensiteli spocitame doplnok) a ignorujeme prenos

V 2-om pripade, pre priklad 3 - 2 dostaneme:

D(3) = 3 = 011

D(-2) = Z + A = z^(2+1) + A = 8 - 2 = 6 = 110

011

+ 110

= 001

pre priklad zhora

0 | 1 | 0 | 0, | 1 | 0 | 0

+ 1 | 0 | 1 | 1, | 1 | 1 | 1

= 0 | 0 | 0 | 0, | 0 | 1 | 1

A toto nam uz sedi :).

Posuvy

Zostava nam posledna kategoria operacii a to posuvy, teda nasobenie a delenie. Pri nasobeni binarnych cisel posuvame dolava. Pri deleni zase doprava.

Vsimnite si, ze pri shifte doprava kopirujeme MSB!!!

Posuvy - Nasobenie

Najprv v dvojkovom kode skusime vynasobit 2 cisla.
1101 * 1011

0000
1101 < 1. posun (nasobitel od zadu), 1
------
01101
1101 <2. posun vpravo, 1
-------
10011
0000 < 3.posun vpravo, 0
------
01001
1101 <4. posun vpravo, 1
-------
10001111

vysledkom je 1000 1111

to bol posun vlavo pre dvojkove cisla bez znamienka. A co sa stane, ak budeme mat doplnkovy kod? Pokial ani jedno cislo nebude zaporne, tak nic. Ale ak nahodou jedno bude, tak mame problem :)

Skusme 3 * (-2) = -6
n = 3, z = 2
D(3) = 0011
D(-2) = Z + A = 16 - 2 = 14 = 1110
D(-6) = Z + A = 16 - 6 = 10 = 1010
jednotka = z^(-m) = 1
a snad si pamatame, ze A musi byt < 1/2*Z = 8, pretoze 1000 je prve cislo, ktore uz je zapornym.
D(1000) = Z + A = 10000 + A
1000 - 10000 = A = -8

takze nasobime
0011 * 1110

0000
0000 << posun 0
------
00000
0011 << posun 1
-------
00011
0000 << posun 0
-------
00001
0011 << posun 1
--------
0001 1110 #a toto nebude uplne spravne, takze ako na to?

Pre nasobenie 2-kovyvch cisel so znamienkom pouzijeme Boothov algritmus. Boothov algoritmus opakovane pridava vypocitane hodnoty cisel A a S k vysledku P a potom vykonava posun dolava na vysledku P. Ak nasobime cisla m * r, tak:

urcime A. Vyplnime MSBity hodnotou m. Zvysne bity vypln nulou. Velkost A je velkost m + velkost r + 1
urcime S. Vyplnime MSBity hodnotou -m v doplnkovom kode a zvysok vyplnime 0-ou.
urcime P. Vyplnime MSBity 0-ou. LSBity doplnime hodnotou r.
urcime LSB P.

Ak 01 => vyplnime hodnotou P + A
Ak 10 => vyplnime hodnotou P + S
Ak 00 alebo 11=> nic nerobime :)

Spravime aritmeticky posun hodnoty P o jedno miesto doprava.
Kroky 4 a 5 vykoname tolko krat, kolko je radova mriezka r
Zahodime LSB z P a mame vysledok.

3*(-4), m = 3 = 0011, r = -4 = 16 - 4 = 12 = 1100, -m = Z + A = 16 - 3 = 13 = 1101

A: 0011 0000 0
S: 1101 0000 0
P: 0000 1100 0
P: 0000 1100 0, takze ziadna praca
P: 0000 0110 0

P: 0000 1100 0 -> 0000 110 00 -> 0000 0110 0
P: 0000 0110 0 -> 0000 0110 0 -> 0000 0011 0
P: 0000 0011 0 -> 1101 0011 0 -> 1110 1001 1
P: 1110 1001 1 -> 1110 1001 1 -> 1111 0100 1

Vysledok je 1111 0100. Otazkou moze byt, ako to, ze to cislo je -12. D(-12) = Z + A = 16 - 12 = 4 = 0100 a aby sme to rozlisili od cisla 4, tak sme spravili znamienkove rozlisenie

A aby zivot nebol jednotvarny a bez bolesti hlavy, tak sa na to da ist este inak.

3*(-4), m = 3 = 0011, r = -4 = 16 - 4 = 12 = 1100, n = 3

0011 * 1100

0000
+ 0000
=   00000
+   0000
= 00000
+ 0011
= 00011 #na zaciatok pridam 0-u lebo znamienkove rozsirenie
- 0011
= 11110   #na zaciatok pridam 1-cku lebo znamienkove rozsirenie
= 11110100 !!! MUCH EASIER!

Mozno tu stoji za zmienku dodat, ako toto cislo prevedieme do 10-kovej sustavy.
D(11110100) = Z + A
11110100 - Z = A
0100 -16 = -12
1111 predstavuje znamienkove rozsirenie.

Posuvy - Delenie
Bin. cisla bez znamienka mozme delit postupnym odcitanim

27/5 == 00011011 / 00000101 postupnym odcitanim

  11011
- 101 0
----------
10110
- 101 1
----------
10001
- 101 10
----------
01100
- 101 11
----------
0111
- 101 100
----------
010
- 101 101 == delitel => koncime!

101 je vysledok, 010 je zvysok

Alebo na delenie mozme ist naopak, ako na nasobenie.

nastav kvocient na 0
zarovnaj cislice delitela a delenca zlava
Ak cast delenca je vacsia alebo rovna delitelovi

odcitaj
pripoj 1-ku zprava ku kvocientu

Inak pridaj = zprava ku kvocientu
opakuj 3 az kym delenec je mensi ako delitel
dividend je zvysok, kvocient je vysledok

00011011 / 00000101

1 ;pretoze 101 sa 1 krat vojde do 110

-----------------

11011

- 101 >> 1

-----------------

011

- 000 >> 0

----------------

111

- 101 >> 1

----------------

010 >> the end!

010 je zvysok

101 je vysledok

Delenie doplnku je zase postupne odcitavanie doplnku.

Monday, June 13, 2011

HW: Zakladne operacie nad dvojkovymi cislami i v doplnkovom kode