BI-JPO
(Jednotky počítače)
B. Sčítání a odčítání c doc. Ing. Alois Pluháček, CSc. 2010
Katedra číslicového návrhu Fakulta informačních technologií České vysoké učení technické v Praze
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
B. Sčítání, odčítání • • • • • • • • • •
číselné soustavy a řádová mřížka sčítání a odčítání racionálních a celých čísel úplná sčítačka poloviční sčítačka sčítačka s postupným šířením přenosu sčítačka s predikcí přenosů sčítání v rámci řádové mřížky odčítačka převod odčítání na sčítání doplňkový pseudokód
BI-JPO
c A. Pluháček 2010
řádová mřížka
n . . . nejvyšší řád −m . . . nejnižší řád A ∼ an an−1 . . . a0 , a−1 . . . a−m A = an z n + an−1 z n−1 + . . . + a0 + a−1 z −1 . . . a−m z −m z . . . základ číselné soustavy Z = z n+1 modul řádové mřížky není zobrazitelný !!! −m ε=z jednotka řádové mřížky nejmenší kladné zobrazitelné číslo zobrazitelná čísla A:
0 ≤ A = k · ε < Z , kde k je celé číslo
BI-JPO
B–1
c A. Pluháček 2010
sčítání racionálních čísel ε<1
? A+B →C ?
A∗ = A/ε = A · z m je celé číslo Př.: z = 10, Z = 10 = 10n+1 , ε = 0, 01 = 10−m n = 0, m = 2 (neboli −m = −2) A = 1, 23 ⇒ A∗ = 1, 23 · 100 = 123 A · z m = A ⊳ m posuv o m míst, a to vlevo vůči řádové čárce (nebo řádové čárky vpravo — v zápise A) 1. A 7→ A∗ = A/ε odstranění řádové čárky B 7→ B ∗ = B/ε 2. C ∗ = A∗ + B ∗ 3. C ∗ 7→ C = C ∗ · ε vrácení řádové čárky Př.: 1, 23 + 4, 56 =? 1, 23 → 123, 4, 56 → 456 123 + 456 = 579 579 → 5, 79 BI-JPO
B–2
c A. Pluháček 2010
sčítání a odčítání racionálních a celých čísel sčítání racionálních čísel 7→ sčítání celých čísel analogicky: odčítání racionálních čísel 7→ odčítání celých čísel Dále bude uvažováno pouze sčítání a odčítání celých čísel ve dvojkové soustavě : z=2 ai bi si pi qi
ε=1
bit 1. sčítance A v řádu i bit 2. sčítance B v řádu i bit součtu S v řádu i přenos do řádu i přenos z řádu i
přenos
[carry]
pozn.: Index i bude někdy vypouštěn. BI-JPO
B–3
c A. Pluháček 2010
úplná sčítačka a 0 0 0 0 1 1 1 1
BI-JPO
b 0 0 1 1 0 0 1 1
p 0 1 0 1 0 1 0 1
q 0 0 0 1 0 1 1 1
s 0 1 1 0 1 0 0 1
s = a⊕b⊕p = = abp + abp + + abp + abp q = = = =
B–4
M3 (a, b, p) = ab + ap + bp = ab ⊕ ap ⊕ bp = ab + (ap ⊕ bp)
c A. Pluháček 2010
poloviční sčítačka poloviční sčítačka (půlsčítačka) a 0 0 1 1
b 0 1 0 1
q 0 0 0 1
s 0 1 1 0
s = a⊕b = ab + ab q = a·b
poloviční sčítačky ➠ úplná sčítačka
BI-JPO
B–5
c A. Pluháček 2010
sčítačka s postupným šířením přenosu n=3 Z = 16 A ∼ a3 a2 a1 a0 B ∼ b3 b2 b1 b0 S ∼ s3 s2 s1 s0 pi+1 = qi S = A + B + p0 − qn ·Z
BI-JPO
B–6
c A. Pluháček 2010
sčítačka s predikcí přenosů (angl. carry look-ahead adder) q = ab + ap + bp a = 1 a b = 0 nebo a=0ab=1 zpoždění se kumulují Pi = ai ⊕ bi Gi = ai · bi
⇒q=p ⇒
! v ustáleném stavu !
frekvence hodinových pulsů
přenos „procházíÿ řádem i přenos v řádu i vzniká — generuje se v něm
srov. výstupy půlsčítačky ! q0 = p1 = G0 + P0 · p0 q1 = p2 = G1 + P1 · p1 q1 = p2 = G1 + P1 · G0 + P1 · P0 · p0 q2 = p3 = G2 + P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · p0 atd. pozn.: alternativně lze použít Pi = ai + bi BI-JPO
B–7
c A. Pluháček 2010
sčítačka s predikcí přenosů
ii
predikce: p1 = G0 + P0 · p0 p2 = G1 + P1 · G0 + P1 · P0 · p0 p3 = G2 + P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · p0 p4 = G3 + P3 · G2 + P3 · P2 · G1 + P3 · P2 · P1 · G0 + + P3 · P2 · P1 · P0 · p0 BI-JPO
B–8
c A. Pluháček 2010
sčítačka s predikcí přenosů
iii
sčítačka s predikcí přenosů na bázi půlsčítaček
BI-JPO
B–9
c A. Pluháček 2010
sčítání v rámci řádové mřížky Výstup sčítačky: S = A + B + p0 − qn · Z Nechť p0 = 0 (nebo půlsčítačka místo úplné sčítačky v řádu 0) : S = A + B − qn · Z S se od A+B liší o násobek Z ☛ S ≡ A + B (mod Z) kongruence (modulo Z) grafické znázornění — obdoba ciferníku na hodinách: 0101 + 0100 = 0 1001 7→ 1001
BI-JPO
B – 10
c A. Pluháček 2010
sčítání v rámci řádové mřížky
ii
0101 + 1110 = 1 0011 7→ 0011
průchod nulou
⇔
přenos z nejvyššího řádu qn = 1
v tomto případě (sčítání čísel bez znaménka): qn = 1 ⇒ A + B ≥ Z (Z = 1 00002 = 1610 ) qn = 1 ⇒ přeplnění (přetečení) ∼ překročení rozsahu obecně však: !!! přenos 6≡ přeplnění (přetečení) !!! důležitý pojem: BI-JPO
přeplnění B – 11
[overflow] c A. Pluháček 2010
odčítačka úplná odčítačka a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
v 0 1 0 1 0 1 0 1
u 0 1 1 1 0 0 0 1
r 0 1 1 0 1 0 0 1
r = a⊕b⊕v = = abv + abv + abv + abv u = = ab + av + bv vi výpůjčka pro řád i ui výpůjčka z řádu i atd. — podobně jako u sčítání
výpůjčka
[borrow]
nu Toto řešení je rozumné jenom v případě, že !?! není realizována sčítačka. nu d Toto řešení tedy obvykle rozumné není! /
rozumné řešení: přidání vhodných obvodů ke sčítačce a převedení odčítání na sčítání c A. Pluháček 2010 BI-JPO B – 12
převod odčítání na sčítání A − B ≡ A + (Z −B) (mod Z)
BI-JPO
B – 13
c A. Pluháček 2010
převod odčítání na sčítání
ii
Jak najít hodnotu Z −B? n P xi z i xi ∈ h0, z − 1i X = i=0
Xmax =
n P
i
(z −1)z =
n+1 P
j
z −
j=1
i=0
n P
z i = z n+1 −1 = Z−1
i=0
z = 2: Xmax = 11 . . . 112 = Z − 1 Z = 11 . . . 112 + 1 Z − B = 11 . . . 112 − B + 1 Z−B =B+1 . . . +1 pozn.: B = 0
⇒
Æ
B . . . negace všech bitů
horká jednička [hot one]
Z − B = Z ≡ 0 (mod Z)
B + 1 = 11 . . . 11 2 + 1 = 1 00. . . 00 2 BI-JPO
B – 14
c A. Pluháček 2010
převod odčítání na sčítání
iii
A ∼ a3 a2 a1 a0 B ∼ b3 b2 b1 b0 R ∼ r3 r2 r1 r0
R = A + (Z−B) − qn · Z = A−B + (1 − qn ) · Z R = A − B + qn · Z qn = 1 qn = 0 qn = 1 qn = 0 BI-JPO
⇒ ⇒ ⇒ ⇒
0≤R
R = A−B ≥ 0 R = A−B + Z < Z A ≥B A
⇒
A−B < 0
R = A−B R = Z − (B −A)
B – 15
c A. Pluháček 2010
doplňkový pseudokód
qn = 0
qn = 1
Je-li qn = 0, tzn. B > A, pak R = Z − (B −A)
BI-JPO
⇒
B −A = Z − R
⇒
B −A = R + 1
B – 16
c A. Pluháček 2010
