Preskočiť na obsah

Binárna sčítačka

z Wikipédie, slobodnej encyklopédie

Binárna sčítačka[1] (iné názvy: dvojková sčítačka,[2] (binárny) sumátor[3][4], sčítačka) je kombinačný logický obvod, realizujúci sčítanie čísel, reprezentovaných v dvojkovej číselnej sústave. Tvorí dôležitú súčasť aritmeticko-logickej jednotky (ALU) centrálneho procesora (CPU) počítača.[5]

V prípade použitia 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.[5]

Jednobitové sčítačky

[upraviť | upraviť zdroj]

Polovičná sčítačka

[upraviť | upraviť zdroj]
Polovičná sčítačka z hradiel XORAND

Polovičná sčítačka[6] (iné názvy: neúplná sčítačka[7]:53, polosumátor[4]; angl. half adder) realizuje sčítanie dvoch jednociferných binárnych čísel. Vstupom sú dva jednobitové sčítance (A, B). Výstupom je jednobitový súčet (S) a jednobitový príznak prenosu do vyššieho rádu (C, z angl. carry flag).[5]

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.[5]

Booleovský zápis:

Pravdivostná tabuľka polovičnej sčítačky:

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

Úplná sčítačka

[upraviť | upraviť zdroj]
Úplná sčítačka, zložená z dvoch polovičných sčítačiek a hradla OR (bloková schéma)
Úplná sčítačka z hradiel (2× XOR, 2× AND, 1× OR). Dve polovičné sčítačky sú v schéme vyznačené červenou farbou.
Schematická značka jednobitovej úplnej sčítačky

Úplná sčítačka[6] (iné názvy: plná sčítačka, úplný sumátor, plný sumátor; angl. 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čítance: A, B, Ci (Ciangl. carry-in). Výstupom je jednobitový súčet (S) a jednobitový príznak prenosu do vyššieho rádu (Co, z angl. carry-out).

Úplnú sčítačku je možné zložiť z dvoch polovičných sčítačiek a hradla OR (pozri obr.). Hradlo OR je navyše možné bez vplyvu na funkčnosť nahradiť hradlom 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.[5]

Úplné sčítačky je možné zreťaziť vedľa seba (výstup Co jednej sčítačky prepojiť so vstupom Ci ďalšej) a realizovať tak sčítanie viacbitových čísel (pozri nižšie).[5]

Booleovský zápis:

Pravdivostná tabuľka úplnej sčítačky:

vstup výstup
A B Ci Co 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

[upraviť | upraviť zdroj]

Paralelná sčítačka je kombinačný obvod, realizujúci sčítanie viacbitových binárnych čísel.[5]

Sčítačka s propagáciou prenosu

[upraviť | upraviť zdroj]
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[6] (angl. ripple carry adder, skr. RCA) vznikne jednoduchým zreťazením N úplných 1-bitových sčítačiek, prepojením výstupu Co úplnej sčítačky n-tého bitu so vstupom Ci 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-bitovej 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.

Sčítačka s predikciou prenosu

[upraviť | upraviť zdroj]
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[7]:123, sčítačka so zrýchleným prenosom[6]; angl. 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 (angl. lookahead carry unit, skr. LCU).

Výhody:

  • výpočet súčtu s oneskorením, teoreticky nezávislým od šírky vstupu – 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 hradielO(n²) a celkový počet 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

[upraviť | upraviť zdroj]
Bloková schéma 4-bitovej BCD sčítačky zloženej z dvoch binárnych sčítačiek a pomocnej logiky
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ódovaní, kde je každá desiatková cifra reprezentovaná samostatnou š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 modulo 16 aritmetike) pripočítať hodnotu 6 (a indikovať prenos do vyššieho rádu, Co), 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 (00002) alebo hodnotu 6 (01102), pričom prepínanie týchto dvoch hodnôt zabezpečuje pomocná hradlová logika, dekódujúca výstupy prvej sčítačky.[5]:150 – 152

Napr.:

prvá sčítačka 1 > 9 druhá sčítačka desiatkový súčet
nie 0 0 = 00
nie 1 0 = 01
nie 8 0 = 08
nie 9 0 = 09
áno 9 1 = 10
áno 9 2 = 11
áno 9 8 = 17
áno 9 9 = 18

Tento obvod je vhodný pre najbežnejšie BCD kódovanie s bitovými váhami 8-4-2-1 (angl. 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

[upraviť | upraviť zdroj]

Medzi bežné TTL/CMOS integrované obvody realizujúce binárne sčítačky patria:[8][9][10]

  • 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[8] aj ľubovoľné vlastné účelové obvody sčítačiek je dnes možné pohodlne používať aj vo forme komponentov pre programovateľné hradlové polia.[7]:54 – 59, 69 – 74, 80 – 87, 108, 123 – 127, 317 – 319, 334

Referencie

[upraviť | upraviť zdroj]
  1. KOLLÁR, Dušan. Kombinačné číslicové a logické obvody [online]. Bratislava: Fakulta Matematiky, Fyziky a Informatiky UK, [cit. 2021-04-15]. Dostupné online.
  2. GNEDENKO, B. V.; KOROĽUK, V. S.; JUŠČENKO, J. L.. Základy programovania na samočinných číslicových počítačoch. Bratislava : Slovenské vydavateľstvo technickej literatúry, 1964. 363 s.
  3. sumátor. In: Slovník cudzích slov (akademický) [online]. Bratislava: Jazykovedný ústav Ľ. Štúra SAV., 2005, [cit. 2021-04-15]. Dostupné online.
  4. a b KVASNIČKA, Vladimír. Úvod do logiky pre informatikov. Bratislava : Fakulta informatiky a informačných technológií STU, 2012. Dostupné online. S. 184 – 186.
  5. a b c d e f g h ANTOŠOVÁ, Marcela; DAVÍDEK, Vratislav. Číslicová technika. 4. aktualiz. vyd. České Budějovice : Kopp, 2009. 305 s. ISBN 978-80-7232-394-4. S. 139 – 148.
  6. a b c d ÁDÁM, Norbert. Architektúry počítačových systémov [online]. Košice: Technická univerzita, [cit. 2021-04-15]. S. 53. Dostupné online.
  7. a b c MALÝ, Martin. Data, čipy, procesory : Vlastní integrované obvody na koleni. Praha : CZ.NIC, 2020. 392 s. Dostupné online. ISBN 978-80-88168-56-0. Archivované 2021-03-12 z originálu.
  8. a b ŠUSTA, Richard. Obvody řady 74 zahrnuté v Quartus II knihovně '/others/maxplus2/' [online]. susta.cz, [cit. 2021-04-15]. Dostupné online.
  9. Frank's IC 7400 [online]. Frank's Hospital Workshop, [cit. 2021-04-15]. Dostupné online.
  10. Frank's IC 4000 [online]. Frank's Hospital Workshop, [cit. 2021-04-15]. Dostupné online.

Iné projekty

[upraviť | upraviť zdroj]

Externé odkazy

[upraviť | upraviť zdroj]