Bc. Vojtěch Hordějčuk

„Čas je způsob, jakým příroda zajišťuje, aby se vše neodehrálo najednou.” - J. A. Wheeler

Domů » Wiki » Kombinační obvody » Sčítačka

Binární sčítačka

Základní operací ve výpočetní technice je sčítání. Dokonce i násobení, dělení a odčítání se na sčítání dá převést. Proto se nyní seznámíme se základním kombinačním obvodem, který dokáže sečíst dvě binární čísla a vrátit výsledek. Řeč bude o binární sčítačce, která je srdcem aritmeticko-logické jednotky (ALU) každého procesoru.

Součet jednobitových čísel

Na začátek pro jistotu shrneme základní pravidla pro sčítání v binární soustavě:

\begin{align*} 0_2+0_2&=0_2=0_{10} \\ 0_2+1_2&=1_2=1_{10} \\ 1_2+0_2&=1_2=1_{10} \\ 1_2+1_2&=10_2=2_{10} \\ \end{align}

Následuje popis kombinačního obvodu, který tyto výpočty realizuje pomocí logických hradel.

Poloviční sčítačka (half-adder)

Už z názvu je patrné, že se bude jednat o nějakou zjednodušenou verzi sčítačky nebo o její část. Co jí tedy k úplnosti chybí? Poloviční sčítačka umí sečíst dvě jednobitová čísla, vrátit jednobitový výsledek a přenos do vyššího řádu. Neumí však ke sčítancům přičíst přenos z nižšího řádu. Vícebitovou sčítačku bychom z ní tím pádem postavit nemohli.

Vstupy a výstupy

  • vstup A = první sčítanec
  • vstup B = druhý sčítanec
  • výstup S = součet (sum)
  • výstup C = přenos do vyššího řádu (carry)

Pravdivostní tabulka

Protože máme dva vstupy, bude mít pravdivostní tabulka 4 řádky (2 umocněno počtem vstupů). Jsou to všechny možné kombinace sčítanců. Z tabulky lze vyčíst, že jsou hodnoty výstupu S shodné s logickým hradlem XOR. Sloupec C je také podobný jednomu hradlu, a to hradlu AND.

vstup A vstup B výstup S výstup C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Schéma zapojení

schéma zapojení poloviční sčítačky

Booleovské rovnice

Funkci poloviční sčítačky lze popsat těmito booleovskými rovnicemi:

\begin{align*} S &= (A \land \lnot B) \lor (\lnot A \land B) \\ C &= A \land B \\ \end{align}

Úplná sčítačka (full-adder)

Úplná sčítačka musí umět to samé jako poloviční sčítačka (sečíst dvě jednobitová čísla, vrátit jednobitový výsledek a přenos). Navíc ještě musí správně aplikovat přenos z nižšího řádu. Jedině tak se bude jednat o plně použitelný blok, který lze kaskádovitě propojit a vytvořit tak plnohodnotnou vícebitovou sčítačku.

Vstupy a výstupy

  • vstup A = první sčítanec
  • vstup B = druhý sčítanec
  • vstup C in = přenos z nižšího řádu (carry in)
  • výstup S = součet (sum)
  • výstup C out = přenos do vyššího řádu (carry out)

Pravdivostní tabulka

vstup A vstup B vstup C in výstup S výstup C out
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

Schéma zapojení

Už umíme sestavit poloviční sčítačku. Nyní ze dvou polovičních sčítaček sestavíme jednu úplnou sčítačku. V první poloviční sčítačce sečteme jednobitové operandy A, B a tento výsledek sečteme v druhé poloviční sčítačce s přenosem z nižšího řádu C in. Přenos do vyššího řádu uskutečníme právě tehdy, když se přenos objeví v libovolné poloviční sčítačce (v obou zároveň se objevit nemůže).

Přenosy z polovičních sčítaček tedy spojíme pomocí hradla OR nebo XOR (zde se jejich odlišnost neprojeví) a jeho výstup označíme jako přenos do vyššího řádu.

schéma zapojení úplné sčítačky

Každou poloviční sčítačku ve výše uvedeném schématu nyní rozkresleme na hradla. Dostaneme následující schéma, které se skládá ze dvou hradel AND a XOR:

schéma zapojení úplné sčítačky

Další možný způsob zapojení je uveden níže. Toto zapojení není založeno na polovičních sčítačkách, ale na booleovských rovnicích úplné sčítačky, které najdete níže.

schéma zapojení úplné sčítačky

Booleovské rovnice

Funkci sčítačky lze formálně zapsat následujícími booleovskými rovnicemi:

\begin{align*} (\otimes &= XOR) \\ S &= A \otimes B \otimes C_{in} \\ C_{out} &= (B \land C_{in}) \lor (A \land C_{in}) \lor (A \land C) \\ \end{align}

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

Již umíme sečíst dvě jednobitová čísla a to včetně správného použití přenosu. Co když ale potřebujeme sčítat větší čísla? Vícebitové sčítačky se zpravidla skládají z několika úplných jednobitových sčítaček, kterých je právě tolik, kolik bitů chceme umět sčítat. V dnešní době nejsou výjimkou ani 64-bitové sčítačky.

Vstupy a výstupy

V závislosti na použití vícebitové sčítačky můžeme přivést na přenos z nižšího řádu logickou 0 nebo pro nejnižší řád použít poloviční sčítačku. Přenos do vyššího řádu lze použít pro zjištění přetečení (výsledek je mimo rozsah).

  • vstupy A1 .. An = bity prvního n-bitového sčítance (prvního operandu)
  • vstupy B1 .. Bn = bity druhého n-bitového sčítance (druhého operandu)
  • výstupy S1 .. Sn = bity n-bitového součtu
  • vstup C in = přenos z nižšího řádu (carry in)
  • výstup C out = přenos do vyššího řádu (carry out)

Schéma zapojení

Vícebitovou sčítačku s postupným šířením přenosu sestavíme zřetězením několika jednobitových úplných sčítaček. Každá sčítačka sečte jeden bit sčítanců a aplikuje přenos z nižšího řádu. Případný přenos pošle dál do vyššího bitu. Jak vidíme, přenos se postupně šíří z nejnižšího bitu do nejvyššího. Z tohoto chování vychází i název zapojení.

Toto zapojení je velmi jednoduché a intuitivní, ale bohužel i značně pomalé. Každá sčítačka totiž musí počkat na ustálení sčítačky v nižším řádu, aby vracela správný výsledek. Proto byly vymyšleny rychlejší způsoby zapojení vícebitové sčítačky (např. s predikcí přenosu), ale jejich popis je mimo rámec tohoto článku.

schéma zapojení vícebitové sčítačky

Paralelní sčítačka

Zkonstruována byla i paralelní sčítačka, která dokáže sečíst dvě binární čísla v logaritmickém čase. Využívá k tomu paralelního prefixového součtu.

Nechť X a Y jsou dvě vstupní binární čísla, například tato:

X 0 1 0 1 1 0 1  1
Y 0 1 1 0 1 0 0  1

Nejprve se na základě obou operandů X a Y vytvoří řetězec B, který se skládá ze tří symbolů:

  • S (stop) – zastavit šíření přenosu (pro XY = 00)
  • P (propagate) – propagovat přenos (pro XY = 10, 01)
  • G (generate) – vytvořit přenos (pro XY = 11)
X 0 1 0 1 1 0 1  1
Y 0 1 1 0 1 0 0  1
B S G P P G S P  G

Z řetězce B se v další fázi vytvoří nový řetězec B' použitím prefixového součtu od nejnižšího bitu (zprava doleva) s binárním operátorem x, který je definován následující tabulkou:

x S P G
S S S S
P S P G
G G G  G

Následuje tvorba bitového řetězce s carry bity. Jeho nejnižší bit je 0 a každá další číslice je dána odpovídajícím symbolem ve slově B'. Symbol G vytvoří na dané pozici 1, symbol S vytvoří 0 a symbol P převezme číslici z nižšího řádu (zprava).

Celý průběh výpočtu vypadá takto:

X 0 1 0 1 1 0 1  1
Y 0 1 1 0 1 0 0  1
B S G P P G S P  G
B' S G G G G S G  G
C 0 1 1 1 1  0  1  1  0
Z  1 1 0 0 0  1 0 0

Reference

  • předmět X36LOB na FEL ČVUT
  • předmět X36PAR na FEL ČVUT