6. ELİADÁS
DIGITÁLIS TECHNIKA I
A 6. elıadás témája a digitális rendszerekben központi szerepet játszó számrendszerek és aritmetikák.
Dr. Pıdör Bálint BMF KVK Mikroelektronikai és Technológia Intézet
1. Számrendszerek
6. ELİADÁS: BINÁRIS SZÁMRENDSZER
2. Bináris számok 3. Aritmetikai mőveletek bináris számokkal 2008/2009 tanév 1. félév
1
2
SZÁMRENDSZEREK BEVEZETİ ÁTTEKINTÉS Áttekintjük a digitális technikában használatos számrendszereket, az aritmetikai mőveletek elvégzésének szabályait és célszerő algoritmusait, valamint az egyes szám-rendszerek közti áttérések algoritmusait is. A digitális rendszerekben, célszerőségi okokból a 2-es (bináris) számrendszer terjedt el. Mindezek sokféle digitális funkcionális egység mőködésének alapjait képezik. 3
Római számok és rendszerük
Két fı típus: - addíciós számrendszer (pl. a római számok); - helyi értékes számrendszer. A helyi értékes rendszerben a számokat polinom alakban írjuk fel m N = ao + a1r + a2r2 + ... + amrm = Σ airi i=0 r (>1) egész szám a számrendszer alapszáma (radix), ai (0 ≤ ai ≤ r-1) egész számok a számjegyek. Az ai helyi értéke ri, az alapszám megfelelı hatványa.
4
Helyérték 318 = 3 ⋅100 + 1 ⋅10 + 8 ⋅1
Szám helyértéke
318 = 3 ⋅10 2 + 1⋅101 + 8 ⋅100 A római számok rendszere különleges volt, és egyáltalán nem alkalmazkodott még a legelemibb számításokhoz sem. Tízes számrendszer, amelynek fı szimbólumai az I, X, C és M (1, 10, 100, 1000), másodlagos szimbólumai a V, L, D (az 5 többszörösei). 5
Szám alaki értéke Számjegyek: 0,1,2,3,4,5,6,7,8,9
318 = 300 + 10 + 8
Számrendszer alapja: 10
Szám valódi értéke Decimális számrendszer 6
SZÁMRENDSZEREK
q-alapú számrendszer
Számok felírása a különbözı számrendszerekben
318(10 ) = 3 ⋅100 + 1⋅10 + 8 ⋅1 10-es alapú 318( q ) = 3 ⋅ q 2 + 1 ⋅ q1 + 8 ⋅ q 0 q alapú
Valamely N szám (numerus) az R alapú (radixú) számrendszerben definíciószerően n −1
N R = ± ∑ Ak ⋅ R k alakban adható meg. Itt
x szám q-alapú számrendszerbeli alakja: an…a0 1≤aa0,i < q, i = 0,1,K , n n 1 0 ha: x = an ⋅ q + K + a1 ⋅ q + a0 ⋅ q Számjegyek: 0,1,...,(q-1)
7
N egész = An −1R
k =− h
n −1
+ ... + A1 R + A0
az egész rész, és
N tört = An −1 R n −1 + ... + A− h +1 R − h +1 + A− h R − h
tört rész. Az N szám Az R alapú számrendszerben a következı alakban adható meg:
N R = An −1... A1 A0 , A−1... A− h −1 A− h ( R)
8
2-es számrendszer Bináris számrendszer 11010110( 2 ) = 1 ⋅ 27 + 1 ⋅ 2 6 + 0 ⋅ 25 + 1 ⋅ 2 4 + 0 ⋅ 23 + 1 ⋅ 2 2 + 1 ⋅ 21 + 0 ⋅ 2 0 Számjegyek: 0,1 A számítástechnika és a digitális technika a bináris számrendszerre épül 9
A kettes számrendszert Leibniz dolgozta ki, még 1679-ben, majd 1854-ben George Boole alakította ki hozzá az algebrát. A Boole-féle algebrában nem csupán az összeadás és szorzás mővelete lehetséges, hanem az ún. logikai mőveletek is: és, vagy, negáció. A 2-es számrendszer használatakor az adattárolás lényegesen egyszerőbben oldható meg, mint a 10-es számrendszerben. 10
10-ES ÉS 2-ES SZÁMRENDSZER
Hexadecimális számrendszer
Pl. 2009 tízes számrendszerbeli alakja azért ez, mert
14 FB = 1⋅163 + 4 ⋅16 2 + F ⋅161 + B ⋅160
2009 = 2x103 + 0x102 + 0x101 + 9x100
= 1 ⋅ 4096 + 4 ⋅ 256 + 15 ⋅16 + 11 ⋅1
kettes számrendszerbeli alakja 111 1101 01112, mert
= 5371(10)
2009 = 1x210 + 1x29 + 1x28 + 1x27 + 1x26 + 0x25
Számjegyek: 0, 1,..., 9, A, B, C, D, E, F Megkülönböztetı jelölés $, pl. $14FB
1936-ban R. Valtat szabadalmaztatta egy 2-es számrendszerben dolgozó számítógép elvét. Ebben az idıben kezdett hozzá Konrad Zuse is egy 2-es számrendszert alkalmazó, mechanikus mőködéső, programvezérelt számítógép kifejlesztéséhez. Valtat és Zuse felismerte, hogy a 2-es számrendszer használata egyszerősíti a számítástechnikát.
+ 1x24 + 1x23 + 0x22 + 0x21 + 1x20 Hexadecimális rendszerben pedig $7D9 11
12
TÖRTSZÁMOK
TÖRTSZÁMOK 2-ES SZÁMRENDSZERBEN
Ha nem csak természetes számokról van szó, akkor m -1 N = Σ airi i = -h
Pl. 1111,1011 értéke 10-es számrendszerben: 1x8 + 1x4 + 1x2 + 1x1 + 1x(1/2) + 0x(1/4) + 1x(1/8) + 1x(1/16) = 15,6875 További példa:
és az N szám rövidített jelölése az r alapú (r-es) számrendszerben
11,0010 0100 0011 1111 0... = ?
N (r) = am-1am-2...a1a0,a-1a-2...a- h (r) 13
SZÁMRENDSZEREK ÉS SZÁMJEGYEIK
14
SZÁMOK KIFEJEZÉSE KÜLÖNBÖZİ SZÁMRENDSZEREKBEN
Megnevezés Alap Számjegyek ——————————————————————— Bináris (duális) 2 0,1 Ternális 3 0,1,2 Tetrális 4 0,1,2,3 Kvinális 5 0,1,2,3,4 Oktális 8 0,1,2,3,4,5,6,7 Decimális 10 0,1,2,3,4,5,6,7,8,9 Duodecimális 12 0,1,2,3,4,5,6,7,8,9,a,b Hexadecimális 16 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Pl. 1310 bináris ternális tetrális oktális decimális duodecimális hexadecimális
1101 111 31 15 13 11 D
(8 + 4 + 0 + 1) (9 + 3 + 1) (3x4 + 1) (8 + 5x1) (10 + 3x1) (12 + 1x1) (D)
15
ÁTSZÁMÍTÁS KÉT SZÁMRENDSZER KÖZÖTT
10-ESBİL 2-ESBE VALÓ ÁTALAKÍTÁS ALGORITMUSA
Egy természetes szám átírása egyik számrendszerbıl a másikba: a számot elosztjuk az új rendszer alapszámával,és a maradékokat jobbról balra haladva leírjuk. Pl.
2005 = 2x1002 + 1, 1002 = 2x501 + 0, 501 = 2x250 + 1, 250 = 2x125 + 0, 125 = 2x62 + 1, 62 = 2x31 + 0 , 31 = 2x15 +1, 15 = 2x7 + 1, 7 = 2x3 + 1, 3 = 2x1 + 1, 1 = 2x0 + 1. Tehát 111 1101 0101
16
A 10-esbıl 2-esbe való átalakítás algoritmusa így is megfogalmazható (a kapott számjegyeket jobbról balra kell leírni): Ismé Ismételd Ha a szá szám pá páratlan, írj le 11-et, és vonj ki a szá számbó mból 11-et, kü különben írj le 00-t oszd el a szá számot 22-vel amí amíg a szá szám nem 0
17
18
BINÁRIS SZÁMRENDSZER JELENTİSÉGE
”OPTIMÁLIS” (?) SZÁMRENDSZER (1)
A digitális technikában különleges szerepe van a bináris számrendszernek. A helyérték neve itt bit (binary digit), ez egyben az információ egysége is. Triád
A bináris rendszer alapszáma közel van a megvalósításhoz szükséges szerkezeti elemek száma tekintetében az optimális számrendszer alapszámához.
3 bit A szükséges szerkezeti elemek száma arányos a helyértékek és a számjegyek száma szorzatával.
Tetrád 4 bit (amerikai angol: nibble) 19
20
”OPTIMÁLIS” SZÁMRENDSZER (2)
”OPTIMÁLIS” SZÁMRENDSZER (3) Legyen pl. Nmax = 109 (1 milliárd)
R - alap (számjegyek száma is) , h - helyértékek száma, Nmax = Rh - 1 Szükséges helyértékek száma h = ln(Nmax + 1) / lnR Szükséges szerkezeti elemek száma (arányosság) S = h R = ln(Nmax + 1) R / lnR Ennek minimum helye R = e ≈ 2,71
21
Szám Alap Számjegyek Szerkezeti rendszer R száma h elemek száma ——————————————————————— Bináris 2 30 60 Ternális 3 19 57 Tetrális 4 15 60 Kvinális 5 13 65 Oktális 8 10 80 Decimális 10 9 90 22
2-ES SZÁMRENDSZER ELİNYEI: CSAK KÉT STABILIS ÁLLAPOT
8-AS ÉS 16-OS SZÁMRENDSZER
Az áramköri megvalósítás szempontjából elınyös, hogy a leképezéséhez csak két stabilis állapot szükséges, így kétállapotú elemekkel: relékkel, tranzisztorokkal, mágnesezhetı elemekkel könnyen leképezhetı.
A hexadecimális számrendszert kényelmi szempontból használják, pl. mert a kettes számrendszerrel nagy számokat hosszú leírni. A hexadecimálisból könnyő a binárisra átváltani és viszont. A hexadecimális rendszert a $ jellel is jelölik.
A két egymástól távol esı stabilis állapot következtében viszonylag érzéketlen a fellépı zavarokkal szemben, illetve azok könnyen elháríthatók.
Bin-hex átváltás: négy bináris számjegy egy hexa számjegyet ad ki, pl 1111 = $F. Egy byte két hexa számjeggyel adható meg. 23
24
A 2-ES16-OS SZÁMRENDSZER A digitális technika természetes számrendszere – a kétértékő megvalósításból adódóan is – a kettes számrendszer. Ehhez jól illeszkedik a hexadecimális számrendszer. A tízes számrendszer használata, néhány kivételtıl (pl. decimális számlálók) eltekintve nehézkes, és sok helyen indokolatlan. A bináris számrendszer matematikai szempontból is elınyös. Az aritmetikai mőveletek igen egyszerően hajthatók végre, és igen egyszerő a logikai ítéletalkotás is. Ugyanazok a számjegyek használhatók fel mind az 25 aritmetikai, mind a logikai mőveletekhez.
BINÁRIS SZÁMRENDSZER: NEGATÍV SÚLYOK
SZÁMRENDSZEREK: NEGATÍV SÚLYOK m -1 N = Σ aiRi i = -h az egyes helyértékekhez negatív súlyozás is rendelhetı! Ha csak a legnagyobb helyértékhez rendelünk negatív súlyt, akkor a negatív számok az alábbi módon ábrázolhatók —
- 4892 = 15108
26
PÉLDA TÖRTSZÁMRA 2-ES SZÁMRENDSZERBEN
—
Bináris rendszerben az 1 szimbólum nem kell! A pozitív és negatív számok leírhatók csupán 0,1 szimbólumokkal, ha a legmagasabb helyértékhez mindig negatív súlyozást rendelünk. Pl.
11,0010 0100 0011 1111 0... = ? Az egész rész 3, a kettedes törtrész pedig
0111 ⇒ -0x8 + 1x4 + 1x2 + 1x1 = 7
1/23 + 1/26 + 1/211 + ..... = 0,125 + 0,015625 + 0,00048828125 + ....
1111 ⇒ -1x8 + 1x4 + 1x2 + 1x1 = -1 Mint késıbb majd látjuk, ez a negatív szám ún. 2-es komplemens ábrázolása.
Az elızı példa megoldása:
27
= 3,141.... = π
28
BINÁRIS ÖSSZEADÁS
ARITMETIKAI MŐVELETEK BINÁRIS SZÁMOKKAL A digitális rendszerek, digitális számítógépek aritmetikai egységei közvetlenül általában csak a négy alapmővelet elvégzésére alkalmas. Ezek és néhány logikai mővelet segítségével viszont tetszıleges mővelet elvégezhetı. Elıször röviden megtárgyaljuk a négy alapmővelet végrehajtását természetes számokon, utána foglakozunk a negatív számok ábrázolásával és a velük végzett mőveletekkel. 29
Két bináris számjegy A + B = C, S alakú bináris összeadása: S - eredeti helyértéken mutatkozó összeg (sum vagy magyarul summa), C - következı helyértékre való átvitel (carry). Igazságtábla és logikai függvények: ‗ ‗ A B S C S = AB + AB = A ⊕ B ————————— 0 0 0 0 C=AB 0 1 1 0 Megvalósító elem: 1 0 1 0 félösszeadó 30 1 1 0 1
Félösszeadó
Félösszeadó • Feladata két bit összeadása
Realizálás kapukkal A
S
A
‗ ‗ S = AB + AB = A ⊕ B
FÖ
S
C
B
B S: összeg
C=AB C
C: maradék, átvitel, carry 31
32
BINÁRIS ÖSSZEADÁS: FÉLÖSSZEADÓ —
S = AB + AB = A ⊕ B A B
C=AB Félösszeadó: két bemenet és két kimenet. Két bináris számjegyet tud összeadni, elıállítja az összeget és átvitelt. Nem veszi figyelembe a kisebb helyértékrıl jövı átvitelt.
•
&
C
félösszeadó 33
BINÁRIS ÖSSZEADÁS
10001111 11001011 +1 0 1 0 1 1 0 1 ___________ 101111000
HEX 1 CB AD ___ 178
A FÜGGETLEN VÁLTOZÓKHOZ RENDELT "SÚLYOK"
(4) (2) (1) i
Ai Bi Ci-1 Di Ci
0
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
0 0 0 1
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 1
1 2 3
Az összeadás hasonló a 10-e számrendszerbelihez: két számjegyet és az elızı helyértékrıl származó maradékot kell összeadni. Az összeg egyes helyértékén lévı számot le kell írni, a kettes 35 helyértéken lévıt tovább kell vinni.
(összeg)
34
TELJES ÖSSZEADÓ (FULL ADDER)
DEC
203 173 _____ 376
(átvitel)
az összeg i-edik bitje Si = Si(Ai,Bi,Ci-1) az i-edik összeadásnál keletkezı átvitel Ci = (Ai,Bi,Ci-1) és C-1 = 0
INDEX
BIN
A = AnAn-1 ... A1A0 +B = BnBn-1 ... B1B0 C = CnCn-1 ... C1C0 —————————— S = SnSn-1 ... S1S0
S
=1
•
A FÜGGİ VÁLTOZÓK
—
BINÁRIS SZÁMOK ÖSSZEADÁSA Bináris számok összeadásának és kivonásának algoritmusa hasonló a decimális számokéhoz:
4 5 6 7
A teljes összeadónak három bemenete, a két operandus, és az alacsonyabb helyértékrıl érkezı átvitel (Ai, Bi és Ci-1) és két kimenete, az összeg és az átvitel) (Si (a táblázatban Di jelöli) és Ci) van.
36
A teljes összeadó igazságtáblája
•Ez csak egy jelölési konvenció. • Használhatnánk éppenséggel hexadecimális indexeket is a változók kombinációinak a megadására. • Ne tévesszük össze ezt a súlyozási konvenciót a Hamming súllyal!
A FÜGGETLEN VÁLTOZÓKHOZ RENDELT "SÚLYOK"
(4) (2) (1)
A FÜGGİ VÁLTOZÓK
•Mégis un. „súlyok” rendelhetık az egyes változókhoz. • Ha megállapodtunk a súlyozásban, akkor bármelyik változókombinációt egyszerőbb az un. indexével jelölni, mint binárisan leírni.
INDEX
TELJES ÖSSZEADÓ (FULL ADDER) •A független változók kombinációi nem bináris számokat jelentenek.
i
Ai Bi Ci-1 Di Ci
0
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
0 0 0 1
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 1
1 2 3 4 5 6 7
A B Cin S Co
• Add two bits and carry-in, produce one-bit sum and carry-out.
ut
0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1
37
38
A Di (összeg) függvény ábrázolása.
A függvény megadása az 1-es függvényértékekkel (2)
(4) (2) (1)
• Példa: A már tárgyalt teljes összeadó. (4) (2) (1) i 0 1 2 3 4 5 6 7
Ai Bi Ci-1 Di Ci 0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
0 0 0 1
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
0 1 1 1
Di = (1,2,4,7)
i
Ai Bi Ci-1 Di
0
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 1 1 1
0 0 1 1
0 1 0 1
1 0 0 1
1
Ci = (3,5,6,7) Itt is következetesnek kell lenni a változók súlyozását illetıen. Ez a megadási forma is unikális.
2 3 4 5 6 7
„sakktábla” Szimmetrikus függvény Ci-1
Di 0
0
1
1 2
1
3
0 6
Ai
0 1
7
Bi
1 4
0
5
39
40
A szimmetrikus függvényekrıl • Ha egy függvény változói felcserélhetık, akkor a függvényt szimmetrikusnak mondjuk. • Ha pl. n=3 (A,B,C) és A és B felcserélhetık egymással, de C-vel egyikük sem, akkor a függvény részlegesen, nevezetesen az A,B változópárra szimmetrikus. • A szimmetria lehet teljes vagy részleges. • A szimmetrikus függvényeknek speciális tulajdonságai vannak. • Jellemzı pl. a legalább részleges „sakktábla” elrendezés a K táblájukon. 41
A Di (összeg) függvény algebrai alakja. Di = m13 + m23 + m43 + m73 = = A.B.C + A.B.C + A.B.C + A.B.C = = A.(BC + BC ) + A.(BC + BC ) =
(4) (2) (1) i
Ai Bi Ci-1 Di
0
0 0 0 0
1 2 3 4 5 6 7
1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 1
0
0
1
1 2
1
3
0 6
Ai
= A.(B ⊕ C ) + A(B ⊗ C) =
Ci-1
Di
0 1
7
1 4
0
Bi
= A.(B ⊕ C ) + A.(B ⊕ C ) = = A⊕ B ⊕C
5
42
A TELJES ÖSSZEADÓ LOGIKAI EGYENLETEI
Teljes összeadó
——
A B
S
B Cin 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1
——
—
—
—
Ci = AiBiCi-1 + AiBiCi-1 + AiBiCi-1 + AiBiCi-1 Cout
= AiBi + AiCi-1 + BiCi-1 43
A 0 0 0 0 1 1 1 1
—
az összeg bit 1-es, ha a három változó közül egy vagy három 1-es (kizáró VAGY logikai kapcsolat),
TÖ
Cin
—
Si = AiBiCi-1 + AiBiCi-1 + AiBiCi-1 + AiBiCi-1
• Feladata két bit és az elızı helyi értékbıl származó maradék összeadása
Logikai függvények S Cout 0 0 S = ABCin + ABCin + ABCin + ABCin 1 0 1 0 Cout = ABCin + ABCin + 0 1 ABCin + ABCin 1 0 0 1 (Minimalizálva: 0 1 C = AB + BC + AC ) out in in 1 1
az átvitel bit 1-es, ha két változó egyidejőleg 1-es 44 (majoritás logikai kapcsolat).
TELJES ÖSSZEADÓ A teljes összeadó két félösszeadóból állítható össze. Az elsı képezi a két összeadandó bit összegét, a második ehhez adja hozzá az elızı helyértéken keletkezett átvitelt. Ai Bi
+1/2
Si
+1/2 1
Ci-1
Ci
45
TELJES ÖSSZEADÓ EGY LEHETSÉGES MEGVALÓSÍTÁSA Ai ⊕ Bi
46
Két 4 bites szám összeadása
Ai ⊕ Bi ⊕ Ci-1
A B
Cin
A B
Cin
TÖ
TÖ Cout
A1 B1
A2 B2
A3 B3
S
Cout
A B
A0 B0 Cin
S
Cout
A
B FÖ
TÖ S
Cout
S
(Ai + Bi) Ci-1 Ai + Bi
Q3
AiBi AiBi + (Ai + Bi) Ci-1 47
Q2
Q1
Q0
Carry flag 48
BINÁRIS SZÁMOK KIVONÁSA
BINÁRIS KIVONÁS Két bináris számjegy A - B = D, (K) alakú bináris kivonása: K - magasabb helyértékrıl vett kölcsön (borrow); D -eredeti helyértéken mutatkozó különbség (difference) K A B D ————————— 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1 1 49
A BINÁRIS KIVONÁS LOGIKAI EGYENLETEI
Bináris számok kivonásának algoritmusa hasonló a decimális számokéhoz (A > B): A = AnAn-1 ... A1A0 - B = BnBn-1 ... B1B0 K = KnKn-1 ... K1K0 —————————— D = DnDn-1 ... D1D0
(kölcsön) (különbség)
a különbség i-edik bitje Di = Di(Ai,Bi,Ki-1) az i-edik különbségnél szükséges kölcsön Ki = Ki(Ai,Bi,Ki-1)
50
TELJES KIVONÓ (FULL SUBTRACTOR)
Az összeadóval analóg módon adódik ——
—
—
Ai
——
Di = AiBiKi-1 + AiBiKi-1 + AiBiKi-1 + AiBiKi-1 Bi
= Ai ⊕ Bi ⊕ Ki-1 a különbség bit 1-es, ha a három változó közül egy vagy három 1-es, és —
—
Ki = AiKi-1 + AiBi + BiKi-1
A kölcsön (Ki) megvalósítása.
& & &
1
Ki A különbség (Di) megvalósítása ugyanaz mint az összegé a teljes összeadóban (azaz Ai ⊕ Bi ⊕ Ki-1).
51
BINÁRIS SZORZÁS
52
BINÁRIS SZÁMOK SZORZÁSA
Az A • B = P bináris szorzás szorzótáblája (bináris ”egyszeregy”) igen egyszerő A B P —————— 0 0 0 0 1 0 1 0 1 1 1 1 Lényegében azonos a logikai ÉS kapcsolattal (logikai szorzás)
Ki-1
1
A bináris számok szorzása ugyanúgy történik, mint a decimális számoké: - ha a szorzó soronkövetkezı számjegye 1-es, akkor összeadás következik, - ha 0-as, akkor nincs összeadás. Minden helyértéknél léptetjük a részletszorzatot a megfelelı irányba.
53
54
BINÁRIS SZORZÁS ELVÉGZÉSE 100100 x 1011 ⇒ 36 x 11 ——— 100100 1. részletszorzat 100100 2. részletszorzat ———— 1101100 összeg 000000 3. részletszorzat ————— 01101100 összeg 100100 4. részletszorzat ————— 110001100 végösszeg ⇒ 396
BINÁRIS SZORZÁS VÉGREHAJTÁSA x3
x2
x1
x0
mult iplicand szorzandó
y3
y2
y1
y0
szorzó mult iplier
(xy0 ) 4 (xy0 ) 3 (xy0 ) 2 (xy0 ) 1 (xy0 ) 0 (xy1 ) 4 (xy1 ) 3 (xy1 ) 2 (xy1 ) 1 (xy1 ) 0
pp1 pp2
(xy2 ) 4 (xy2 ) 3 (xy2 ) 2 (xy2 ) 1 (xy2 ) 0 (xy3 ) 4 (xy3 ) 3 (xy3 ) 2 (xy3 ) 1 (xy3 ) 0 p7
55
BINÁRIS SZORZÁS ALGORITMUSA
p6
p: szorzat
p5
p4
pp0
pp3
p3
p2
p1
p0
pp: rész-szorzat
56
BINÁRIS SZÁMOK OSZTÁSA
P=AxB n-1 n-1 A = Σ Ai 2i és B = Σ Bi 2i i=0 i=0 a részletszorzatok n-1 Pk = Bk Σ Ai 2i = 0 ha Bk = 0, és = A ha Bk = 1 k=0 a teljes szorzat n-1 P = Σ Pk 2k 57 k=0
A szokásos decimális „”kézi” osztáshoz hasonlóan végezhetı. Visszaállító algoritmus illetve visszaállítás nélküli algoritmus.
58
BINÁRIS OSZTÁS: VISSZAÁLLÍTÓ ALGORITMUS Példa: 14 : 5 = 2,8 1110:101=10,11… -101 0100 - 101 1111 + 101 01000 visszaállítás 101 00110
VÉGE
59
60
