Číselnésoustavy, sčítáníasčítačky

MI-AAK (Aritmetika a kódy)

Číselné soustavy, sčítání a sčítačky c doc. Ing. Alois Pluháček, CSc., 2011

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

A1. Číselné soustavy, sčítání a sčítačky číselné soustavy standardní soustavy řádová mřížka základní operace v obecné řádové mřížce dvojkové sčítačky – úplná sčítačka a poloviční sčítačka – sčítačka s postupným šířením přenosu – sčítačka s výhybkami – sčítačka s predikcí přenosů ∗ kaskádní zapojení – sčítačka s podmíněnými součty • sčítání v rámci řádové mřížky • • • • •

MI-AAK

c A. Pluháček 2011

číselné soustavy číselné soustavy • poziční — zejm. polyadické – standardní ∗ desítková — dekadická ∗ dvojková — binární či dyadická ∗ osmičková — oktalová ∗ šestnáctková — hexadecimální ∗ trojková — ternární či triadická apod. – nestandardní ∗ se záporným základem (zejm. soustava polská) ∗ s relativními číslicemi ∗ soustava o několika základech aj. • nepoziční – tzv. římská čísla – soustava zbytkových tříd (soustava česká) aj. c A. Pluháček 2011 MI-AAK A1 – 1

standardní soustavy

standardní číselné soustavy – polyadické A ∼ an an−1 . . . a0 , a−1 . . . a−m n P A= ai z i i=−m

z ≥2 základ (neboli báze) soustavy — přirozené číslo ai ∈ h0; z) číslice (neboli cifry) — nezáporná celá čísla 0 ≤ A ≤ z n+1 − z −m !!! Nelze zobrazit záporná čísla !!! MI-AAK

A1 – 2


řá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ý ε = z −m jednotka řádové mřížky — nejmenší kladné zobrazitelné číslo zobrazitelná čísla A: k = A/ε = A∗ A∗ ε MI-AAK

=⇒

0 ≤ A = k · ε < Z , k je celé číslo A = A∗ jednotek ε číslice v zápisu čísla A poloha řádové čárky A1 – 3


základní operace v obecné řádové mřížce

sčítání a odčítání stejné řádové mřížky obou operandů a výsledku: A = A∗ ·ε ⇒ A ± B = A∗·ε ± B ∗·ε = (A∗ ± B ∗ ) ·ε ∗ B = B ·ε Př.: z = 10, Z = 10 = 10n+1 , ε = 0, 01 = 10−m n = 0, m = 2 (neboli −m = −2) A = 1, 23 ⇒ A∗ = 1, 23/0, 01 = 123 B = 4, 56 ⇒ B ∗ = 4, 56/0, 01 = 456 A = 1, 23 + 4, 56 = (123 + 456) · 0, 01 = = 579 · 0, 01 = 5, 79 různé řádové mřížky: převod do vhodné řádové mřížky — přidání nul Př.: 1,234+56,7 = 01,234+56,700 = 57,934

Závěr: Sčítání a odčítání v obecné řádové mřížce lze snadno převést na sčítání a odčítání celých čísel. MI-AAK

A1 – 4


základní operace v obecné řádové mřížce

ii

násobení: A = A∗ ·εA B = B ∗ ·εB

⇒

A · B = A∗·εA · B ∗·εB = = (A∗ ·B ∗ ) · εA ·εB

Př.: z = 10 Z A = 10, εA = 0, 01, nA = 0, mA = 2 Z B = 100, εB = 0, 1, nB = 1, mB = 1 7, 01 · 80, 3 = (701 · 803) · 0, 001 = = 562 903 · 0, 001 = 562, 903

Závěr: Násobení v obecné řádové mřížce lze snadno převést na násobení celých čísel.

MI-AAK

A1 – 5


dvojkové sčítačky úplná sčítačka (jednomístná dvojková sčítačka) a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

MI-AAK

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

[full adder]

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

A1 – 6

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


dvojkové sčítačky

poloviční sčítačka (půlsčítačka) a 0 0 1 1

MI-AAK

b 0 1 0 1

q 0 0 0 1

s 0 1 1 0

ii

[half adder]

s = a⊕b = ab + ab q = a·b

A1 – 7


sčítačka s postupným šířením přenosu sčítačka s postupným šířením přenosu

[ripple-carry adder]

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 zapojení s půlsčítačkami

MI-AAK

A1 – 8


sčítačka s postupným šířením přenosu

ii

qi = ai bi + ai pi + bi pi . . . přenos do vyššího řádu qi = ai bi + (ai pi ⊕ bi pi ) = ai bi + (ai ⊕ bi ) · pi ai = 0 a bi = 0 ⇒ qi = 0 . . . přenos v řádu i zaniká ai = 1 a bi = 1 ⇒ qi = 1 . . . přenos v řádu i vzniká jinak (je-li ai 6= bi ) ⇒ qi = pi . . . přenos přes řád i prochází pi+1 = qi = pi ! ale až v ustáleném stavu ! pi+1 je zpožděno vůči pi zpoždění se kumulují ➠ frekvence hodinových pulsů nutno uvažovat největší zpoždění qi = Gi + Pi · pi , kde Gi = ai · bi (přenos v řádu i vzniká — generuje se v něm) Pi = ai ⊕ bi (přenos „procházíÿ řádem i) Pi = 1, Pi+1 = 1, . . . , Pi+k = 1

=⇒ qi+k = pi

pi · Pi · Pi+1 = 1, · . . . · Pi+k = 1

=⇒ qi+k = 1

MI-AAK

A1 – 9


sčítačka s výhybkami


[carry skip adder]

Sčítačka je rozdělena na sekce po k řádech. Přenos, který by musel projít přes k řádů sekci obejde, po „výhybceÿ. Poznámky: • Ke snížení maximálního zpoždění dojde jen v případě, že sekce jsou aspoň tři. • Místo Pi = ai ⊕ bi lze evidentně použít Pi′ = Pi + Gi , tzn. Pi′ = ai + bi . • Je-li úplná sčítačka vytvořena ze dvou půlsčítaček, lze použít jako Pi = ai ⊕ bi výstup první půlsčítačky. • Sekce lze sdružovat (analogicky jako sčítačky) do větších sekcí (do jakýchsi „nadsekcíÿ), a ty popř. do ještě větších sekcí atd. MI-AAK

A1 – 10



ii

Př.: 3 sekce po 4 řádech ∼ celkem 21 bitů jedna sekce:

tři sekce:

MI-AAK

A1 – 11


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


[carry look-ahead adder]

q = ab + (ap ⊕ bp) = ab + (a ⊕ b) · p = G + P · p = ab + ap + bp = ab + (a + b) · p = G + P ′ · p Gi = ai · bi Pi = ai ⊕ bi Pi′ = ai + bi

přenos se v řádu i generuje přenos „procházíÿ řádem i přenos „procházíÿ řádem i nebo se v něm generuje

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. Místo Pi lze použít Pi′ .

MI-AAK

A1 – 12



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 MI-AAK

A1 – 13



iii

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 MI-AAK

A1 – 14



iv

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

MI-AAK

A1 – 15


sčítačka s predikcí přenosů — kaskádní zapojení 4bitová sekce (jako příklad): p1 p2 p3 p4

= = = =

G0 + P0 · p0 G1 + P1 · G0 + P1 · P0 · p0 G2 + P2 · G1 + P2 · P1 · G0 + P2 · P1 · P0 · p0 G 3 + P3 · G 2 + P3 · P2 · G 1 + P3 · P2 · P1 · G 0 + + P3 · P2 · P1 · P0 · p0

G∗ P∗ G∗ P∗

= G 3 + P3 · G 2 + P3 · P2 · G 1 + P3 · P2 · P1 · G 0 = P3 · P2 · P1 · P0 . . . v sekci se generuje přenos z jejího nejvyššího řádu . . . přenos sekcí prochází p4 = G∗ + P ∗ · p0

MI-AAK

A1 – 16


sčítačka s predikcí přenosů — kaskádní zapojení

MI-AAK

A1 – 17

ii


sčítačka s podmíněnými součty

sčítačka s podmíněnými součty [conditional sum adder] stavební prvek: s0 s1 q0 q1

= = = =

a⊕b a⊕b⊕1 a·b a+b

... ... ... ...

součet, součet, přenos, přenos,

je-li je-li je-li je-li

p p p p

= = = =

0 1 0 1

multiplexor:

dvojice multiplexorů:

MI-AAK

A1 – 18



ii

zapojení 8bitové sčítačky

MI-AAK

A1 – 19



iii

Není-li třeba určovat např. přenosy z řádů 0, 1, . . . , 6, lze vypustit příslušné multiplexory:

MI-AAK

A1 – 20



iv

4bitová sčítačka

MI-AAK

A1 – 21



4bitová sčítačka — 1001 + 1110 + p = ?

MI-AAK

A1 – 22

v

pro p =

0 1




MI-AAK

A1 – 23

vi

pro p =

0 1




MI-AAK

A1 – 24

vii

pro p =

0 1


sčítání v rámci řádové mřížky 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

MI-AAK

A1 – 25


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 MI-AAK

A1 – 26


Číselnésoustavy, sčítáníasčítačky

Recommend Documents