2. Počítače zvnútra

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Michalovi “Žabovi” Anderlemu na

Zamysleli ste sa niekedy nad tým, ako funguje počítač? Na tej úplne najnižšej úrovni: tam, kde je to len hŕba súčiastok, ktoré sú medzi sebou rôzne poprepájané. Najprimitívnejšie súčiasky typicky rozlišujú iba dva možné stavy: ide mnou prúd a nejde mnou prúd, resp. som pod napätím a nie som pod napätím. Ako niečo takéto vôbec dokáže sčítať dve čísla? To si skúsime ukázať v tejto úlohe.

To, čo si ukážeme v tejto úlohe nie je úplne to isté, čo sa používa v počítačoch. Ale je to naozaj blízko. Najbližšie, ako vieme ísť bez toho, aby sme potrebovali fyziku. A môžem vás ubezpečiť, že týmito myšlienkami začínala éra počítačov :)

Hradlá

Počítač, ktorý budeme stavať, bude poznať iba dve hodnoty – hodnotu 0 a hodnotu 1. Skladať sa bude z káblov a logických súčiastok, ktoré budeme nazývať hradlá. Hradlá sú krabičky, ktoré majú niekoľko vstupov a niekoľko výstupov¹. Keď na každý vstup privedieme hodnotu 0 alebo 1, hradlo ich vo vnútri spracuje a na každý výstup dá určenú hodnotu, ktorú vypočítalo. Väčšinou hradlá počítajú nejaké logické funkcie.

Hradlo NOT – je jedným zo základných hradiel, má jeden vstup a jeden výstup. Na výstup vracia hodnotu opačnú k tomu, čo dostalo na vstupe. Ak teda hradlu NOT dáme na vstup 0, vráti nám 1 a naopak, ak mu dáme na vstup 1, vráti nám 0.

Hradlo AND – má dva vstupy a jeden výstup. Na výstup vráti 1 iba vtedy, ak boli obe hodnoty na vstupe 1. V opačnom prípade (aspoň na jednom vstupe bola hodnota 0) na výstup vráti 0. Toto samozrejme zodpovedá logickému AND (a zároveň), ktoré poznáte z matematiky.

Hradlá môžeme medzi sebou rôzne skladať a prepájať pomocou káblikov. Vieme teda napojiť výstup jedného hradla na vstup iného hradla a takýmto spôsobom získať zložitejšie obvody. Takisto môžeme káble rozvetviť, čo spôsobí, že tá istá hodnota pôjde do viacerých vstupov rôznych alebo rovnakých hradiel. Vhodným skombinovaním viacerých hradiel môžeme dostať obvod, ktorý sa celý správa ako nejaké (iné) hradlo.

Čo by sme však nemali s hradlami robiť, je spájať dva výstupy do jedného káblika, zaviesť výstup hradla, alebo čokoľvek čo sa z tohto výstupu počíta, na vstup toho istého hradla. Takéto konštrukcie totiž nebudú fungovať.

Príklad

Predstavme si, že máme iba zásobu hradiel NAND. Hradlo NAND má dva vstupy a jeden výstup. Hradlo vráti na výstup hodnotu 0 iba ak sú obe vstupné hodnoty rovné 1, vo všetkých ostatných prípadoch vráti na výstup 1. Iba pomocou hradiel tohto typu by sme chceli poskladať hradlá NOT a AND.

Hradlo NOT má iba jeden vstup, ktorého hodnotu máme obrátiť. Hradlo NAND ale potrebuje dva vstupy. Vstup, ktorý dostaneme, preto rozvetvíme na dva a zapojíme do NAND. Výstup z tohoto NAND-u bude výstupom nášho obvodu. Výsledná hodnota bude naozaj opačná k tomu, čo sme mali na začiatku. Ak sme totiž na vstupe obvodu mali 1, na hradlo NAND sa dostanú dve jednotky, teda toto hradlo vráti 0. Ak sme na vstupe mali 0, na NAND sa dostanú dve nuly, teda vráti nulu. Schému nášho obvodu si môžete pozrieť na obrázku.

Ešte chceme spraviť hradlo AND. Uvedomme si, že NAND vracia presne opačnú hodnotu k tomu, čo vracia AND. Z hodnôt na vstupe teda môžeme vypočítať NAND a tento výsledok zmeniť pomocou postupu, ktorý sme si popísali vyššie (v podstate použijeme hradlo NOT). Schému si môžete pozrieť nižšie.

Úloha

Vašou úlohou bude vytvoriť niekoľko zložitejších logických hradiel. Úlohy na seba nadväzujú a na riešenie niektorých podúloh sa vám zídu hradlá z predchádzajúcich podúloh. Ak vám to zadanie povoľuje, tak môžete používať hradlá z iných podúloh ako hotovú krabičku s daným názvom, ktorá sa správa tak, ako má. Pritom nemusíte mať príslušnú podúlohu ani vyriešenú. Hradiel každého typu môžete použiť ľubovoľne veľa.

1. (2 body) Hradlo OR – vašou úlohou je vytvoriť hradlo, ktoré má dva vstupy a jeden výstup. Na výstup vráti 1, ak je aspoň jedna zo vstupných hodnôt 1. 0 vráti, ak sú obe vstupné hodnoty 0. Môžete použiť iba hradlá NOT a AND.

2. (2 body) Hradlo SORT – vytvorte hradlo s dvoma vstupmi a dvoma výstupmi. Toto hradlo usporiada vstupné hodnoty, to znamená, že na výstup označený výstup A vráti menšiu z dvoch hodnôt a na výstup označený výstup B tú väčšiu. Ak sú hodnoty na vstupe rovnaké, vráti ich na výstupy v ľubovoľnom poradí (však sú rovnaké). Môžete použiť hradlá NOT, AND a OR.

3. (2 body) Hradlo IMP – vytvorte hradlo s dvoma vstupmi a jedným výstupom. Na výstup vráti toto hradlo 0, iba ak je prvý vstup (označený vstup A) rovný 1 a druhý vstup (vstup B) rovný 0. V opačnom prípade vráti na výstup hodnotu 1. Toto hradlo teda zodpovedá matematickej implikácii. Môžete použiť hradlá NOT, AND a OR.

Ako sme si povedali na začiatku, našim cieľom bude sčítavať čísla. Poznáme však iba dve cifry 0 a 1, preto budeme všetky čísla zapisovať iba pomocou týchto dvoch cifier – v binárnej (dvojkovej) sústave. Binárna sústava je vec celkom zaujímavá a ak jej chcete poriadne rozumieť, odporúčame vám prečítať si o nej niečo na internete².

Na vyriešenie tejto úlohy vám však stačí vedieť, ako čísla v binárnej sústave sčítavať. Ak chceme sčítať dve binárne čísla, môžeme si ich napísať jedno pod druhé a sčitovať zprava doľava po cifrách (presne ako sa to robí pri číslach v desiatkovej sústave). Platí, že \(0+0=0\), \(0+1=1\) a \(1+0=1\). Jediný rozdiel je pri \(1+1\), lebo to sa nemôže rovnať 2, keďže takú cifru nepoznáme, ale rovná sa 0 s tým, že jedna 1 sa prenesie do ďalšieho rádu, teda k nasledujúcej cifre (podobne, ako keď pri sčítaní dvoch čísel v desiatkovej sústave dostaneme súčet dvoch cifier väčší ako 9).

Nižšie vidíte tri príklady toho, ako funguje sčítanie binárnych čísel. V prvom príklade nastáva prenos pri sčítavaní druhej, štvrtej, piatej a šiestej cifry od konca. Všimnite si, že pri sčítavaní šiestej cifry sčítavame dokopy až tri 1 (po jednej z každého čísla a jednu z prenosu), čoho výsledkom je 1 a presunutá 1 do vyššieho rádu.

       00101011            00000001              00011011
     + 10111010          + 01111111            + 11111001
     ----------          ----------            ----------
       11100101            10000000             100010000

4. (3 body) Hradlo XORc – vytvorte hradlo s dvoma vstupmi a dvoma výstupmi. Jeho úlohou bude sčítať hodnoty, ktoré dostane na vstupe. Na výstup vystup A vráťte výsledok tohto sčítania (samozrejme, namiesto hodnoty 2 vraciate hodnotu 0) a na výstup vystup B vráťte 1, ak sa prenáša jednotka do vyššieho rádu, inak naň vráťte 0. Použiť môžete hradlá NOT, AND a OR.

5. (2 body) Hradlo XOR3c – vytvorte hradlo s tromi vstupmi a dvoma výstupmi, ktoré sčíta tri hodnoty, ktoré má na vstupe a na vystup A vráti výsledok tohto sčítania (namiesto výsledku 2 vráti 0 a namiesto výsledku 3 vráti 1) a na vystup B dá 1, ak sa pri sčítaní prenášala jednotka do vyššieho rádu. Môžete použiť hradlá NOT, AND, OR a XORc.

6. (4 body) Hradlo SUM – cieľom bude vytvoriť hradlo, ktoré sčíta dve osemciferné binárne čísla \(x\) a \(y\), ktoré môžu začínať prebytočnými nulami. Cifry týchto čísiel si označíme \(x_0, x_1 ... x_7\) a \(y_0, y_1 ... y_7\), pričom \(x_0\) a \(y_0\) sú najmenej významné cifry (tie úplne napravo). Týmito názvami si tiež označíme 16 vstupov, ktoré bude naše hradlo mať. Výstupov bude mať 9 a budú označené \(z_0\) až \(z_8\), a dokopy majú tvoriť číslo \(x+y=z\), pričom \(z_0\) je najmenej významná cifra čísla \(z\). Popíšte, ako takéto hradlo vytvoriť. Na riešenie môžete použiť hradlá NOT, AND, OR, XORc a XOR3c.

Odovzdávanie a hodnotenie

Táto úloha sa dá odovzdávať dvomi spôsobmi. Prvým z nich je odovzdať klasické .pdf, v ktorom nakreslíte hradlá podobne ako v časti Príklad a popíšete, ako ste prišli na svoje riešenie. Za postup, ktorým ste sa snažili riešiť danú podúlohu, môžete získať čiastočné body aj v prípade, že vaše riešenie úplne nefunguje.

Druhá možnosť je stiahnuť si program Logisim (je to program špeciálne určený na navrhovanie logických obvodov), vaše riešenia nakresliť v ňom a odovzdať ich na automatické testovanie. To funguje podobne ako pri programátorských úlohách: testovač vám hneď povie, či sú vaše riešenia správne, alebo nie a pridelí vám príslušný počet bodov. V prípade že vaše riešenie nefunguje, môžete si ho skúsiť opraviť a odovzdať znova (a toto môžete opakovať ľubovoľne veľa krát). Ak niektoré podúlohy (najlepšie všetky) vyriešite takýmto spôsobom, nemusíte k nim už odovzdávať žiaden slovný popis. Technické detaily k tomuto spôsobu odovzdávania nájdete na tejto stránke: https://prask.ksp.sk/logisim/.