B. Sčítání,odčítání adoplňkovýkód

B. Sčítání, odčítání a doplňkový kód • • • • • • • • • • • •

číselné soustavy a řádová mřížka sčítání a odčítání racionálních a celých čísel úplná a poloviční sčítačka sčítačka s postupným šířením přenosu a 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ý kód sčítání a odčítání v doplňkovém kódu kombinační část jednoduché aritmetické jednotky aritmetický posuv v doplňkovém kódu rozšiřování řádové mřížky v doplňkovém kódu

JPO 2005/6

c A. Pluháček 19.3.2006

řádová mřížka

n . . . nejvyšší řád −m . . . nejnižší řád A ∼ an an−1 . . . a0 , a1 . . . a−m A = an z n + an−1 z n−1 + . . . + a0 + a1 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: JPO 2005/6

0 ≤ A = k · ε < Z , k je celé číslo B1


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 v zápise A vpravo 1. A → A∗ = A/ε odstranění řádové čárky B → B ∗ = B/ε 2. C ∗ = A∗ + B ∗ 3. C ∗ → C = C ∗ · ε vrácení řádové čárky Př.: 1, 23 + 4, 56 =? 1, 23 → 123, 4, 56 → 456 123 + 456 = 579 579 → 5, 79 JPO 2005/6

B2


sčítání a odčítání racionálních a celých čísel sčítání racionálních čísel → sčítání celých čísel analogicky: odčítání racionálních čísel → odčítání celých čísel dále pouze sčítání a odčítání celých čísel ve dvojkové soustavě z=2 ai bi si pi qi

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

JPO 2005/6

B3

ε=1

přenos — angl. carry


úplná a poloviční sčítačka úplná sčítačka a b p q 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

s 0 1 1 0 1 0 0 1

i

s = a⊕b⊕p = = abp + abp + + abp + abp q = = = =

M3 (a, b, p) = ab + ap + bp = ab ⊕ ap ⊕ bp = ab + (ap ⊕ bp)

poloviční sčítačka (půlsčítačka) a b q s s = a⊕b 0 0 0 0 = ab + ab 0 1 0 1 1 0 0 1 q = a·b 1 1 1 0 JPO 2005/6

B4


úplná a poloviční sčítačka

ii

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 JPO 2005/6

B5


sčítačka s predikcí přenosů (angl. carry look-ahead adder)

i

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 JPO 2005/6

B6


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 JPO 2005/6

B7


sčítačka s predikcí přenosů

iii

sčítačka s predikcí přenosů na bázi půlsčítaček

JPO 2005/6

B8


sčítání v rámci řádové mřížky

i

Výstup sčítačky: S = A + B + p0 − qn · Z Nechť p0 = 0 (nebo úplná sčítačka v řádu 0 je nahrazena půlsčítačkou): S = A + B − qn · Z S se liší od A + B o násobek Z 7→ S ≡ A + B (mod Z) graﬁcké znázornění (obdoba ciferníku na hodinách): 0101 + 0100 = 0 1001 → 1001

JPO 2005/6

B9


sčítání v rámci řádové mřížky

ii

0101 + 1110 = 1 0011 → 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í) !!! přeplnění — angl. overﬂow JPO 2005/6

B 10


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

výpůjčka — angl. borrow

atd. - podobně jako u sčítání

??? Lze upravit sčítačku na odčítačku? Jak? ??? JPO 2005/6

B 11


převod odčítání na sčítání

i

A − B ≡ A + (Z −B) (mod Z)

JPO 2005/6

B 12



ii

Jak najít hodnotu Z −B? n P xi z i xi ∈ h0, z − 1i X = i=0

n P

Xmax =

(z − 1)z =

i=0

= Z −1 z = 2:

i

n+1 P

j

z −

j=1

n P

z i = z n+1 − 1 =

i=0

Xmax = 11. . . 11 = Z − 1 Z = 11. . . 11 + 1

xx. . . xx — řádová mřížka

Z − B = 11. . . 11 − B + 1 Z−B =B+1

B . . . negace všech bitů

. . . + 1 — tzv. horká jednička (angl. hot one) pozn.: B = 0 ⇒ Z − B = Z ≡ 0 (mod Z) B + 1 = 11. . . 11 + 1 = 1 00. . . 00 JPO 2005/6

B 13



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 JPO 2005/6

⇒ ⇒ ⇒ ⇒

0≤R
R =A−B ≥0 R =A−B−Z
⇒A−B <0

R =A−B R = Z − (B − A) B 14



iv

doplňkový pseudokód

qn = 0

qn = 1

Je-li qn = 0, tzn. B > A, pak R = Z − (B −A)

JPO 2005/6

⇒

B −A = Z − R

⇒

B −A = R + 1

B 15


doplňkový kód

i

X 0 1 2 3 4 5 6 7 -8 -7 -6 -5 -4 -3 -2 -1 JPO 2005/6

B 16

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

D(X) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 c A. Pluháček 19.3.2006

doplňkový kód

− 12 Z ≤ X <

D(X) =

D(X) ≡ X

ii

1 Z 2

X, je-li X ≥ 0, Z + X = Z − |X|, je-li X < 0.

(mod Z)

D D D D(X) ∼ xD n xn−1 . . . x1 x0

xD n = 0 ⇐⇒ D(X) ≥ 0 xD n = 1 ⇐⇒ D(X) < 0 JPO 2005/6

B 17


doplňkový kód — sčítání a odčítání

sčítání: D(A+B) ≡ A+B ≡ D(A) + D(B) (mod Z)

sečíst D(A) + D(B) a ignorovat přenos qn z nejvyššího řádu označování: D(A) + D(B) − qn ·Z = S D D D D(A) ∼ aD n an−1 . . . a1 a0 D D D D(B) ∼ bD n bn−1 . . . b1 b0 D D D S ∼ sD n sn−1 . . . s1 s0

odčítání: D(A−B) ≡ A − B ≡ D(A)−D(B) (mod Z)

odečíst D(B) od D(A) a ignorovat výpůjčku vn pro nejvyšší řád anebo převést odečítání na sčítání, tzn. sečíst D(A) + D(B) + 1 a ignorovat přenos qn z nejvyššího řádu

JPO 2005/6

B 18


doplňkový kód — přeplnění

i

přeplnění při sčítání (A+B ≥ 12 Z nebo A+B < − 12 Z): 1. A < 0 a B ≥ 0 ⇒ A ≤ A + B < B B <0 a A≥0 ⇒ B ≤A+B < A

! k přeplnění nemůže dojít ! 2. A ≥ 0 a B ≥ 0 přeplnění: A + B ≥ 12 Z výsledek má opačné znaménko viz příklad 5 + 4 → −7 3. A < 0 a B < 0 přeplnění: A + B < − 21 Z výsledek má opačné znaménko viz příklad (−5) + (−5) → 6 JPO 2005/6

B 19



ii

detekce přeplnění: 1

D aD n = bn = 0

a

sD n = 1

D aD n = bn = 1

a

sD n = 0

nebo

D D D D D over = aD n · bn · sn + an · bn · sn

2

aD n 0 0 0 0 1 1 1 1

bD n 0 0 1 1 0 0 1 1

pD n 0

1 0 1 0 1

0 1

D qn 0

0 0 1 0 1

1 1

sD n 0 1 1 0 1 0 0 1

qn = pn qn 6= pn qn qn qn qn

= = = =

pn pn pn pn

qn 6= pn qn = pn

over = qn ⊕ pn JPO 2005/6

B 20



iii

1

2

JPO 2005/6

B 21


kombinační část jednoduché aritmetické jednotky řídicí signály add neg inc výstup 0 0 0 A 1 0 0 A+B 0 1 1 A−B 0 0 1 A+1 1 1 0 A−1

stavové signály: carry přenos z nejvyššího řádu over přeplnění v doplňkovém kódu q n 6= pn JPO 2005/6

B 22


doplňkový kód — aritmetický posuv vlevo obecně: aritmetický posuv o j míst vlevo ∼ násobení z j z = 2 aritmetický posun o 1 místo vlevo A ⊳ 1 = 2A = A + A doplňkový kód:

s=a⊕b⊕p q = ab + ap + bp

aritmetický posun o 1 místo

JPO 2005/6

& a=b

=⇒

s=p q=a

vlevo v doplňkovém kódu:

B 23


doplňkový kód — aritmetický posuv vpravo Úvaha: Je-li po korektním posuvu vpravo, při němž nedojde ke ztrátě přesnosti, proveden opačný posuv (tzn. vlevo), musí se získat původního hodnota. Z toho plyne: Je třeba provést logický posuv a do nejvyššího řádu doplnit stejný bit, jaký tam byl před posuvem.

JPO 2005/6

B 24


doplňkový kód — rozšiřování řádové mřížky

i

problém: Jak převést kratší zápis na delší?

X, Z + X, X, D ′ (X) = Y + X, D(X) =

pro X ≥ 0 pro X < 0

Z = 2n+1

pro X ≥ 0 pro X < 0

Y = 2k+1

1. X ≥ 0

⇒ 0 v nejvyšším řádu D ′ (X) = D(X) = X

2. X < 0

⇒ 1 v nejvyšším řádu D ′ (X) = D(X) + Y − Z Y − Z = 2k+1 − 2n+1 = (2k−n − 1) · 2n+1 2k−n − 1 ∼ |11.{z . . 11 } násobení 2

n+1

JPO 2005/6

B 25

n−k

. . . posuv o n+1 míst doleva (přidat n+1 nul zprava) c A. Pluháček 19.3.2006

doplňkový kód — rozšiřování řádové mřížky

ii

příklad: n = 3, Z = 1 00002 k = 7, Y = 1 0000 00002 D(6) D ′ (6)

= 0110 = 0000 0110

D(−6) = 1010 D ′ (−6) = 1111 1010

JPO 2005/6

B 26


B. Sčítání,odčítání adoplňkovýkód

Recommend Documents