Zobrazenie zdroja stránky Binárna sčítačka

'''Binárna sčítačka'''<ref name="kollar-digit" /> (iné názvy: '''dvojková sčítačka''',<ref>{{Citácia knihy | priezvisko = Gnedenko | meno = B. V. | autor = | odkaz na autora = | priezvisko2 = Koroľuk | meno2 = V. S. | autor2 = | odkaz na autora2 = | priezvisko3 = Juščenko | meno3 = J. L. | autor3 = | odkaz na autora3 = | titul = Základy programovania na samočinných číslicových počítačoch | vydanie = | vydavateľ = Slovenské vydavateľstvo technickej literatúry | miesto = Bratislava | rok = 1964 | počet strán = 363 | url = | isbn = | kapitola = | strany = | jazyk = }}</ref> (binárny) '''sumátor'''<ref>sumátor. In: {{Citácia elektronického dokumentu | priezvisko = | meno = | autor = | odkaz na autora = | titul = Slovník cudzích slov (akademický) | url = https://slovnik.juls.savba.sk/?w=sum%C3%A1tor | vydavateľ = Jazykovedný ústav Ľ. Štúra SAV. | dátum vydania = 2005 | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = Bratislava | jazyk = }}</ref><ref name="kvasnicka-2012" />, '''sčítačka''') je [[kombinačný obvod|kombinačný logický obvod]], realizujúci [[sčítanie]] čísel, reprezentovaných v [[dvojková číselná sústava|dvojkovej číselnej sústave]]. Tvorí dôležitú súčasť [[aritmeticko-logická jednotka|aritmeticko-logickej jednotky]] (ALU) [[CPU|centrálneho procesora]] (CPU) [[počítač]]a.<ref name="antosova-2009" />

V prípade použitia [[dvojkový doplnok|dvojkového doplnkového]] kódovania záporných čísel sa dá sčítačka veľmi jednoducho rozšíriť na sčítačku-odčítačku.<ref name="antosova-2009" />

== Jednobitové sčítačky ==

=== Polovičná sčítačka ===
[[Súbor:Half-adder.svg|náhľad|Polovičná sčítačka z hradiel [[hradlo XOR|XOR]] a [[hradlo AND|AND]]]]
'''Polovičná sčítačka'''<ref name="adam" /> (iné názvy: '''neúplná sčítačka'''<ref name="maly-2020" />{{rp|53}}, '''polosumátor'''<ref name="kvasnicka-2012" />; {{eng|''half adder''}}) realizuje sčítanie dvoch jednociferných binárnych čísel. Vstupom sú dva jednobitové [[sčítanec|sčítance]] (''A'', ''B''). Výstupom je jednobitový [[sčítanie|súčet]] (''S'') a jednobitový [[príznak prenosu]] do vyššieho rádu (''C'', z {{eng|''carry flag''}}).<ref name="antosova-2009" />

Polovičná sčítačka odovzdáva ďalej príznak prenosu do ďalšieho rádu, sama však nedokáže spracovať prenos z predchádzajúceho rádu. Nestačí preto na realizáciu viacbitového sčítania.<ref name="antosova-2009" />

[[Boolova algebra|Booleovský]] zápis:
:<math>S = A \oplus B</math>
:<math>C = A \cdot B</math>

Pravdivostná tabuľka polovičnej sčítačky:
{| class="wikitable" style="text-align:center"
|-
! colspan="2" | vstup !!!! colspan="2" | výstup
|-
! A !! B !!!! C !! S
|-
| 0 || 0 |||| 0 || 0
|-
| 0 || 1 |||| 0 || 1
|-
| 1 || 0 |||| 0 || 1
|-
| 1 || 1 |||| 1 || 0
|-
|}

{{clear}}

=== Úplná sčítačka ===
[[Súbor:Full_Adder_Blocks.svg|náhľad|Úplná sčítačka, zložená z dvoch polovičných sčítačiek a hradla [[hradlo OR|OR]] (bloková schéma)]]
[[Súbor:Full Adder Modules.svg|náhľad|Úplná sčítačka z hradiel (2× [[hradlo XOR|XOR]], 2×  [[hradlo AND|AND]], 1× [[hradlo OR|OR]]). Dve polovičné sčítačky sú v schéme vyznačené červenou farbou.]]
[[Súbor:1-bit full-adder.svg|náhľad|Schematická značka jednobitovej úplnej sčítačky]]

'''Úplná sčítačka'''<ref name="adam" /> (iné názvy: '''plná sčítačka''', '''úplný sumátor''', '''plný sumátor'''; {{eng|''full adder''}}) realizuje sčítanie dvoch jednociferných binárnych čísel s pripočítaním prenosu z predchádzajúceho rádu. Vstupom sú tri jednobitové [[sčítanec|sčítance]]: ''A'', ''B'', ''C<sub>i</sub>'' (C<sub>i</sub> z {{eng|''carry-in''}}). Výstupom je jednobitový [[sčítanie|súčet]] (''S'') a jednobitový [[príznak prenosu]] do vyššieho rádu (''C<sub>o</sub>'', z {{eng|''carry-out''}}).

Úplnú sčítačku je možné zložiť z dvoch polovičných sčítačiek a [[logické hradlo|hradla]] [[hradlo OR|OR]] (pozri obr.). Hradlo OR je navyše možné bez vplyvu na funkčnosť nahradiť hradlom [[hradlo XOR|XOR]], nakoľko kombinácia vstupov (1, 1), pri ktorej by sa ich výstup líšil nemôže v prípade sčítania nastať (buď nastane prenos iba v prvej polovičnej sčítačke, alebo iba v druhej). Na vytvorenie úplnej sčítačky tak stačia 2 typy hradiel, čo je praktické pri ich realizácii.<ref name="antosova-2009" />

Úplné sčítačky je možné zreťaziť vedľa seba (výstup C<sub>o</sub> jednej sčítačky prepojiť so vstupom C<sub>i</sub> ďalšej) a realizovať tak sčítanie viacbitových čísel (pozri nižšie).<ref name="antosova-2009" />

Booleovský zápis:
:<math>S = (A \oplus B) \oplus C_i</math>
:<math>C_o = (A \cdot B) + (C_i \cdot (A \oplus B)) = (A \cdot B) + (B \cdot C_i) + (C_i \cdot A)</math>

Pravdivostná tabuľka úplnej sčítačky:
{| class="wikitable" style="text-align:center"
|-
!colspan="3"| vstup !!!!colspan="2"| výstup
|-
! A !! B !! C<sub>i</sub> !!!! C<sub>o</sub> !! S
|-
| 0 || 0 || 0 |||| 0 || 0
|-
| 0 || 0 || 1 |||| 0 || 1
|-
| 0 || 1 || 0 |||| 0 || 1
|-
| 0 || 1 || 1 |||| 1 || 0
|-
| 1 || 0 || 0 |||| 0 || 1
|-
| 1 || 0 || 1 |||| 1 || 0
|-
| 1 || 1 || 0 |||| 1 || 0
|-
| 1 || 1 || 1 |||| 1 || 1
|-
|}

== Paralelné sčítačky ==
'''Paralelná sčítačka''' je kombinačný obvod, realizujúci sčítanie viacbitových binárnych čísel.<ref name="antosova-2009" />

=== Sčítačka s propagáciou prenosu ===
[[Súbor:4-bit ripple carry adder.svg|náhľad|4-bitová sčítačka s propagáciou prenosu. Doba ustálenia obvodu je 2 × 4 = 8 čiastkových hradlových oneskorení.]]

N-bitová '''sčítačka s propagáciou prenosu''' alebo '''sčítačka so sériovým prenosom'''<ref name="adam" /> ({{eng|''ripple carry adder''}}, skr. '''RCA''') vznikne jednoduchým zreťazením N úplných 1-bitových sčítačiek, prepojením výstupu C<sub>o</sub> úplnej sčítačky n-tého bitu so vstupom C<sub>i</sub> sčítačky (n+1). bitu (pozri obr.). Vstupom výslednej N-bitovej sčítačky sú potom dve N-bitové čísla (+ prípadný prenos z predchádzajúceho rádu), výstupom je ich súčet, široký N+1 bitov (N bitov + prenos). Názov je odvodený z princípu – príznak prenosu sa odovzdáva (propaguje) z jedného bitu do druhého.

Sčítačka s propagáciou prenosu je jednoduchá na návrh a realizáciu a teoreticky je rozšíriteľná na ľubovoľný počet bitov. Má však zásadnú nevýhodu: s rastúcou šírkou (a teda počtom zreťazených úplných sčítačiek) priamo úmerne narastá celkové oneskorenie (''doba ustálenia'') výsledného obvodu. Signál prenosu prechádza v každej úplnej sčítačke dvoma hradlami, takže korektný súčet sa na výstupe napr. [[32-bit]]ovej sčítačky s propagáciou prenosu objaví s oneskorením až 64 čiastkových ''hradlových oneskorení'', čo by mohlo výrazne obmedzovať ''priepustnosť'' (maximálny možný počet sčítaní za jednotku času) sekvenčného zariadenia, využívajúceho takýto typ sčítačky. Toto obmedzenie viedlo k snahe navrhnúť N-bitové sčítačky s menším oneskorením.

{{clear}}

=== Sčítačka s predikciou prenosu ===
[[Súbor:4-bit carry lookahead adder.svg|náhľad|4-bitová sčítačka s predikciou prenosu]]

'''Sčítačka s predikciou prenosu''' (iné názvy: '''sčítačka s predvídaním prenosu'''<ref name="maly-2020" />{{rp|123}}, '''sčítačka so zrýchleným prenosom'''<ref name="adam" />; {{eng|''carry lookahead adder''}}, skr. '''CLA''') je N-bitová binárna sčítačka, schopná vypočítať súčet v kratšom čase (v jednotkách hradlového oneskorenia) než sčítačka s propagáciou prenosu (RCA). Pri RCA musí každá čiastková 1-bitová sčítačka „čakať“ na korektný príznak prenosu od sčítačky predchádzajúceho bitu. Pri CLA sú (zjednodušene povedané) všetky prenosy medzi rádmi vypočítané súčasne – kombinačným obvodom, nazývaným ''jednotka predikcie prenosu'' ({{eng|''lookahead carry unit''}}, skr. LCU).

Výhody:
* výpočet súčtu s oneskorením, teoreticky nezávislým od šírky vstupu – ''[[asymptotická zložitosť|O]](1)'', zatiaľ čo sčítačka s propagáciou prenosu má oneskorenie priamo úmerné šírke vstupu – ''O(n)''

Nevýhody:
* vyššie nároky na celkový počet [[logické hradlo|hradiel]] – ''O(n²)'' a celkový počet [[tranzistor (polovodičová súčiastka)|tranzistorov]] (''O(n³)'' kvôli potrebe hradiel s počtom vstupov úmerným šírke sčítačky) v porovnaní so sčítačkou s propagáciou prenosu (''O(n)'' hradiel)
* od určitého počtu bitov prestáva byť prakticky realizovateľná (kvôli počtu hradiel a výrobným obmedzeniam na počet vstupov jedného hradla). Široké sčítačky je preto potrebné realizovať viacúrovňovo – kombinovaním princípu predikcie prenosu (na nižšej úrovni) s propagáciou prenosu (na vyššej úrovni), prípadne použitím princípu predikcie prenosu na dvoch (alebo viacerých) úrovniach.

== BCD sčítačky ==
[[Súbor:Adder 4 Bit BCD.svg|náhľad|Bloková schéma 4-bitovej BCD sčítačky zloženej z dvoch binárnych sčítačiek a pomocnej logiky]]
[[Súbor:Adder 4 Bit BCD Pins.svg|náhľad|Schéma 4-bitovej BCD sčítačky z konkrétnych TTL obvodov z rodiny 7400]]
Pre sčítavanie čísel reprezentovaných v [[BCD kód|BCD kódovaní]], kde je každá [[desiatková číselná sústava|desiatková]] cifra reprezentovaná samostatnou [[nibble|štvoricou bitov]], je možné použiť obvod zložený z dvoch 4-bitových úplných binárnych sčítačiek a pomocnej logiky.

Prvá sčítačka binárne sčíta 4-bitové BCD sčítance, pričom pokiaľ je ich súčet ≤ 9, je už jej výstupom platná BCD reprezentácia výsledku. Ak je hodnota súčtu > 9, je k nemu potrebné (v [[modulárna aritmetika|modulo 16 aritmetike]]) pripočítať hodnotu 6 (a indikovať prenos do vyššieho rádu, ''C<sub>o</sub>''), aby výsledok znova binárne reprezentoval príslušnú desiatkovú cifru súčtu. Toto pričítanie zabezpečuje druhá 4-bitová sčítačka, ktorá má ako jedného sčítanca výstup prvej sčítačky a ako druhého buď hodnotu 0 (0000<sub>2</sub>) alebo hodnotu 6 (0110<sub>2</sub>), pričom prepínanie týchto dvoch hodnôt zabezpečuje pomocná hradlová logika, dekódujúca výstupy prvej sčítačky.<ref name="antosova-2009" />{{rp|150{{--}}152}}

Napr.:
{| class="wikitable" style="text-align: center;"
|-
! prvá sčítačka !! ∑<sub>1</sub> > 9 !! druhá sčítačka !! desiatkový súčet
|-
| <math>0 + 0 \equiv \ \ 0 \pmod {16}</math> || nie || <math>\ \ 0 + 0 \equiv 0 \pmod {16}</math> || 0 + 0 = {{0}}'''0'''
|-
| <math>1 + 0 \equiv \ \ 1 \pmod {16}</math> || nie || <math>\ \ 1 + 0 \equiv 1 \pmod {16}</math> || 1 + 0 = {{0}}'''1'''
|-
| colspan=4 | <math>\cdots</math>
|-
| <math>8 + 0 \equiv \ \ 8 \pmod {16}</math> || nie || <math>\ \ 8 + 0 \equiv 8 \pmod {16}</math> || 8 + 0 = {{0}}'''8'''
|-
| <math>9 + 0 \equiv \ \ 9 \pmod {16}</math> || nie || <math>\ \ 9 + 0 \equiv 9 \pmod {16}</math> || 9 + 0 = {{0}}'''9'''
|- style="border-top-width: 2px"
| <math>9 + 1 \equiv 10 \pmod {16}</math> || áno || <math>10 + 6 \equiv 0 \pmod {16}</math> || 9 + 1 = 1'''0'''
|-
| <math>9 + 2 \equiv 11 \pmod {16}</math> || áno || <math>11 + 6 \equiv 1 \pmod {16}</math> || 9 + 2 = 1'''1'''
|-
| colspan=4 style="text-align: center;" | <math>\cdots</math>
|-
| <math>9 + 8 \equiv \ \ 1 \pmod {16}</math> || áno || <math>\ \ 1 + 6 \equiv 7 \pmod {16}</math> || 9 + 8 = 1'''7'''
|-
| <math>9 + 9 \equiv \ \ 2 \pmod {16}</math> || áno || <math>\ \ 2 + 6 \equiv 8 \pmod {16}</math> || 9 + 9 = 1'''8'''
|-
|}

Tento obvod je vhodný pre najbežnejšie BCD kódovanie s bitovými váhami 8-4-2-1 ({{eng|''natural binary coded decimal''}}; skr. NBCD), pri ktorom reprezentácia hodnôt 0{{--}}9 priamo zodpovedá ich zápisom v dvojkovej sústave.

== Integrované obvody ==
Medzi bežné [[Transistor–transistor logic|TTL]]/[[Complementary Metal Oxide Semiconductor|CMOS]] [[integrovaný obvod|integrované obvody]] realizujúce binárne sčítačky patria:<ref name="susta-74">{{Citácia elektronického dokumentu | priezvisko = Šusta | meno = Richard | autor = | odkaz na autora = | titul = Obvody řady 74 zahrnuté v Quartus II knihovně '/others/maxplus2/' | url = http://susta.cz/fel/74/index.htm | vydavateľ = susta.cz | dátum vydania = | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = | jazyk = }}</ref><ref>{{Citácia elektronického dokumentu | priezvisko = | meno = | autor = | odkaz na autora = | titul = Frank's IC 7400 | url = http://frankshospitalworkshop.com/electronics/ic_7400.html | vydavateľ = Frank's Hospital Workshop | dátum vydania = | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = | jazyk = }}</ref><ref>{{Citácia elektronického dokumentu | priezvisko = | meno = | autor = | odkaz na autora = | titul = Frank's IC 4000 | url = http://frankshospitalworkshop.com/electronics/ic_4000.html | vydavateľ = Frank's Hospital Workshop | dátum vydania = | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = | jazyk = }}</ref>
* 7480: 1-bitová úplná sčítačka
* 7482: 2-bitová úplná sčítačka
* 7483: 4-bitová úplná sčítačka so zrýchleným prenosom
* 74181: 4-bitová 16-funkčná aritmeticko-logická jednotka (ALU)
* 74183: 2× 1-bitová úplná sčítačka
* 74283: 4-bitová úplná sčítačka so zrýchleným prenosom
* 74381: 4-bitová ALU s výstupmi „generate“ a „propagate“
* 74382: 4-bitová ALU s výstupmi „ripple carry“ a „overflow“
* 74385: 4× 1-bitová sčítačka/odčítačka
* 74456: natural binary coded decimal (NBCD) sčítačka
* 4008: 4-bitová úplná sčítačka so zrýchleným prenosom
* 4032: 3× sériová sčítačka
* 4038: 3× sériová sčítačka (spúšťanie zostupnou hranou)
* 4560: NBCD sčítačka
* 40181: 4-bitová 16-funkčná ALU

Ekvivalenty uvedených obvodov<ref name="susta-74" /> aj ľubovoľné vlastné účelové obvody sčítačiek je dnes možné pohodlne používať aj vo forme komponentov pre [[Field programmable gate array|programovateľné hradlové polia]].<ref name="maly-2020" />{{rp|54{{--}}59, 69{{--}}74, 80{{--}}87, 108, 123{{--}}127, 317{{--}}319, 334}}

== Referencie ==
{{referencie|refs=
<ref name="antosova-2009">{{Citácia knihy | priezvisko = Antošová | meno = Marcela | autor = | odkaz na autora = | priezvisko2 = Davídek | meno2 = Vratislav | autor2 = | odkaz na autora2 = | titul = Číslicová technika | vydanie = 4. aktualiz | vydavateľ = Kopp | miesto = České Budějovice | rok = 2009 | počet strán = 305 | url = | isbn = 978-80-7232-394-4 | kapitola = | strany = 139{{--}}148| jazyk = }}</ref>
<ref name="adam">{{Citácia elektronického dokumentu | priezvisko = Ádám | meno = Norbert | autor = | odkaz na autora = | titul = Architektúry počítačových systémov | url = http://aps.fei.tuke.sk/doc/T2.pdf#page=53 | vydavateľ = Technická univerzita | strany = 53 | dátum vydania = | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = Košice | jazyk = }}</ref>
<ref name="kvasnicka-2012">{{Citácia knihy | priezvisko = Kvasnička | meno = Vladimír | autor = | odkaz na autora = | titul = Úvod do logiky pre informatikov | vydanie = | vydavateľ = Fakulta informatiky a informačných technológií STU | miesto = Bratislava | rok = 2012 | url = http://www2.fiit.stuba.sk/~kvasnicka/Logika/Book_all.pdf#page=184 | isbn = | kapitola = | strany = 184{{--}}186 | jazyk = }}</ref>
<ref name="kollar-digit">{{Citácia elektronického dokumentu | priezvisko = Kollár | meno = Dušan | autor = | odkaz na autora = | titul = Kombinačné číslicové a logické obvody | url = http://www.dnp.fmph.uniba.sk/~kollar/dg_w/digit1.htm | vydavateľ = Fakulta Matematiky, Fyziky a Informatiky UK | dátum vydania = | dátum aktualizácie = | dátum prístupu = 2021-04-15 | miesto = Bratislava | jazyk = }}</ref>
<ref name="maly-2020">{{Citácia knihy | priezvisko = Malý | meno = Martin | autor =  | odkaz na autora =  | titul = Data, čipy, procesory : Vlastní integrované obvody na koleni | vydanie =  | vydavateľ = CZ.NIC | miesto = Praha | rok = 2020 | url = https://knihy.nic.cz/files/edice/Data_cipy_procesory.pdf | isbn = 978-80-88168-56-0 | počet strán = 392 | kapitola =  | strany =  | jazyk =  | url archívu = https://web.archive.org/web/20210312234200/https://knihy.nic.cz/files/edice/Data_cipy_procesory.pdf | dátum archivácie = 2021-03-12 }}</ref>´
}}

== Pozri aj ==
* [[dvojková číselná sústava]]
* [[binárna násobička]]
* [[aritmeticko-logická jednotka]] (ALU)
* [[hradlo XOR]]
* [[zoznam základných logických obvodov]]

== Iné projekty ==
{{projekt}}

== Externé odkazy ==
* [https://elektrokniha.cz/circuitjs.html?startCircuit=halfadd.txt Polovičná sčítačka] {{Webarchive|url=https://web.archive.org/web/20211016092031/https://elektrokniha.cz/circuitjs.html?startCircuit=halfadd.txt |date=2021-10-16 }}, [https://elektrokniha.cz/circuitjs.html?startCircuit=fulladd.txt úplná sčítačka] {{Webarchive|url=https://web.archive.org/web/20210415235507/https://elektrokniha.cz/circuitjs.html?startCircuit=fulladd.txt |date=2021-04-15 }} – interaktívne simulácie hradlových obvodov k publikácii [https://knihy.nic.cz/#hradla ''Hradla, volty, jednočipy''] Martina Malého
* [https://www.ecsis.riec.tohoku.ac.jp/topics/amg/i-amg/doc/algorithm Hardvérové algoritmy pre aritmetické moduly] {{eng icon}}
* [http://www.righto.com/2020/11/reverse-engineering-carry-lookahead.html Reverzné inžinierstvo obvodu zrýchleného prenosu sčítačky v ALU procesora Intel 8008] {{eng icon}}

[[Kategória:Logické obvody]]
[[Kategória:Počítačová aritmetika]]