Zadanie

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ýstupov1. 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 internete2.

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

  1. (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.

  2. (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.

  3. (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/.

  1. To, na akom fyzikálnom princípe tieto krabičky fungujú vnútri, sa v priebehu histórie menilo. Najprv sa používali relé, neskôr elektrónky. V súčasných počítačoch sa používajú tranzistory.↩

  2. Napríklad tu: [http://www.gym-informatika.estranky.cz/clanky/dvojkova-sustava.html] (http://www.gym-informatika.estranky.cz/clanky/dvojkova-sustava.html)↩

Výraz znegovať označuje zmenu hodnoty na opačnú hodnotu, teda použitie jedného hradla NOT. Vo vzorovom riešení budem používať tento výraz, pretože je bežne používaný v matematike.

Podúloha a.

Keď sa snažíme pracovať s logickými hradlami alebo funkciami, častokrát sa nám oplatí napísať si celú tabuľku hodnôt pre hľadané hradlo a hľadať podobnosti s hradlami, ktoré poznáme. Vieme, že hradlo OR má vrátiť nulu iba v tom prípade ak sú obe vstupné hodnoty rovné 0, inak vráti hodnotu 1. To sa trochu podobá na hradlo AND, ktoré vráti 1 iba v jedinom prípade – keď sa obe vstupné hodnoty rovnajú 1.

Ak ale znegujeme výsledok AND, podobnosť s OR je ešte výraznejšia, pretože negovaný AND (tiež NAND) vracia 0 iba v jedinom prípade, presne tak, ako hradlo OR. Akurát tie prípady sú odlišné. OR na to potrebuje dve nuly, ale NAND dve jednotky. Ako teda zaručíme, že ak naše hradlo dostane dve 0, náš znegovaný AND dostane dve 1? Jednoducho obe vstupné hodnoty znegujeme.

Celé hradlo preto vyzerá nasledovne: znegované vstupné hodnoty vložíme do hradla AND, ktorého výsledok tiež znegujeme. Vyskúšaním všetkých štyroch možností (00, 01, 10 a 11) ľahko overíme, že takéto niečo sa správa presne ako bolo popísané v zadaní.

Podúloha b.

Na vstupe máme dve hodnoty a našou úlohou ich bolo usporiadať – na prvý výstup vrátiť menšiu z nich, na druhý väčšiu. Môžeme teda vyskúšať všetky možnosti ako vyzerá vstup a skúsiť na to napasovať nejaké z hradiel, ktoré poznáme. Oveľa lepšie je však pozrieť sa na to, ako vyzerajú výstupné hodnoty. Menšia z dvoch hodnôt bude takmer vždy hodnota 0. Jediná výnimka je, keď máme na vstupe dve 1. To je ale presne to, čo robí hradlo AND. A väčšia hodnota bude takmer vždy 1, okrem prípadu, keď máme na vstupe dve 0, čo nám vie ošetriť hradlo OR.

Celé hradlo teda vyzerá nasledovne: obe vstupné hodnoty vložíme do jedného hradla AND, ktoré bude vracať menšiu hodnotu a do jedného hradla OR, ktoré bude vracať väčšiu hodnotu. Uvedomme si, že hradlo AND je v istom zmysle rovnaké ako funkcia minimum a hradlo OR je rovnaké ako maximum.

Podúloha c.

Pri zostrojovaní hradla implikácie použijeme podobný prístup ako v podúlohe a.. Všimnime si, že hradlo IMP vracia 0 iba v jedinom prípade, keď je na prvom vstupe hodnota 1 a na druhom vstupe hodnota 0. To sa podobá na hradlo OR, ktoré vracia 0 tiež iba v jedinom prípade, keď sú obe vstupné hodnoty 0. Preto, ak chceme ako výsledok použiť výsledok hradla OR, musíme upraviť vstupné hodnoty tak, aby sa vstup 10 zmenil na 00, ktorý môžeme posunúť hradlu OR. To znamená, že nám stačí znegovať prvý vstup.

Hradlo teda vyzerá nasledovne: znegovaný prvý vstup a pôvodný druhý vstup vložíme do hradla OR, ktorého výstup je výstupom hradla IMP. Overením štyroch možností ľahko preveríme správnosť takéhoto riešenia.

Podúloha d.

Hradlo XORc je prvé maličké sčitovacie hradlo s dvoma vstupmi a dvoma výstupmi. Na vystup B vraciame 1, ak sa prenáša jednotka do vyššieho rádu. Uvedomme si ale, že to nastane iba v prípade, ak sú obe vstupné hodnoty 1. Takže vypočítať druhý vstup vieme pomocou jednoduchého hradla AND.

Komplikovanejšie je to s vystup A. Na ten máme vrátiť 1 v prípade, že prvý vstup je 1 a druhý vstup vstup je 0 alebo je prvý vstup 0 a druhý vstup je 1. Logické spojky sme zdôraznili zámerne. Vidíme, že aj v bežnom jazyku ich častokrát používame a keď si problém sformulujeme správnym spôsobom, riešenie sa ukáže samo.

Najskôr musíme vedieť zistiť, či je na prvom vstupe 1 a na druhom vstupe 0, pričom budeme chcieť použiť hradlo AND (a zároveň). To je však problém, s ktorým sme sa stretli už dvakrát, v podúlohách a. a c.. Keďže AND vráti 1 iba ak sú oba jeho vstupy rovné 1, tak na overenie zadanej podmienky vložíme do hradla AND pôvodnú prvú hodnotu a znegovanú druhú hodnotu. To isté, akurát opačne spravíme pri overovaní druhej časti – prvý vstup je 0 a druhý 1. V tomto prípade znegujeme prvý vstup a necháme druhý nezmenený.

Máme teda dve hradlá AND, z ktorých jedno vráti 1, ak je na vstupe jeden z dvoch správnych vstupov. A zistiť, či aspoň jedno z týchto hradiel naozaj vráti 1, vieme pomocou hradla OR (alebo). Tým sme skonštruovali to, čo nám popisovala vyššie uvedená veta.

Celé hradlo dokopy teda vyzerá nasledovne: zoberieme dve hradlá AND. Do prvého z nich vedie prvý vstup a znegovaný druhý vstup. Do druhého vedie znegovaný prvý vstup a pôvodný druhý vstup. Výstupy týchto dvoch hradiel potom vložíme do hradla OR. Jeho výstup bude vystup A. Hodnotu vystup B zistíme ako AND oboch pôvodných vstupov.

Podúloha e.

Ak sa nám podarilo spraviť dvojvstupový XORc, vytvoriť XOR3c by malo byť pomerne jednoduché. Pomocou XORc sčítame prvé dve vstupné hodnoty. Výsledok tohto sčítania je prvý výstup tohto hradla. K tomuto výstupu teda pričítame tretiu vstupnú hodnotu pomocou druhého hradla XORc. Prvý výstup tohto druhého hradla XORc je naozaj prvý výstup hradla XOR3c. Ostáva nám vyriešiť už len otázku, či nastal prenos do vyššieho rádu.

Prenos však musel nastať pri niektorom z dvoch sčítaní pomocou hradiel XORc. A tie majú špeciálny výstup, na ktorý vrátia 1 ak takáto udalosť nastala. Ak teda aspoň jeden z týchto dvoch výstupov obsahuje hodnotu 1, chceme ju vrátiť aj na výsledný vystup B, v čom nám pomôže hradlo OR. Všimnime si, že sa nemôže stať, že obe hradlá XORc vrátia prenosovú hodnotu 1. Súčet troch hodnôt je totiž najviac 3, a pri tom nastáva najviac jeden prenos.

Celé hradlo teda vyzerá: prvé dva vstupy pošleme do hradla XORc. Prvý výstup tohto hradla vložíme spolu s tretím vstupom do druhého hradla XORc. Prvý výstup tohto sčítania vrátime na vystup A. Hodnotu vystup B získame ako výsledok hradla OR, do ktorého vložíme druhé výstupy oboch hradiel XORc.

Podúloha f.

Ako iste tušíte, predchádzajúce dve podúlohy pomaly ale iste smerovali k riešeniu poslednej podúlohy – vytvorenie hradla SUM, ktoré dokáže sčítavať binárne čísla. Pozrime sa teda na to, ako sa sčítavajú binárne čísla.

Ako bolo napísané v zadaní, musíme ich sčitovať postupne po cifrách (bitoch), pričom začínať musíme najmenej významnými ciframi. To sú v tomto prípade cifry \(x_0\) a \(y_0\). A sčítať dve hodnoty predsa vieme pomocou hradla XORc. Prvý výstup tohto hradla nám dá súčet príslušných cifier, čo bude hodnota cifry \(z_0\) patriaca výsledku. Druhý výstup udáva, či nastal prenos. Ak nastal prenos, musíme ho totiž zahrnúť do ďalšieho sčitovania. Na zistenie cifry \(z_1\) nám teda nestačí sčítať cifry \(x_1\) a \(y_1\), ale musíme pridať aj prenos z predchádzajúceho sčítania. No a sčítať tri hodnoty vieme pomocou hradla XOR3c.

Celé hradlo SUM teda vyzerá nasledovne: použijeme jedno hradlo XORc a sedem hradiel XOR3c. Každé z týchto hradiel dostane na vstup po jednej cifre z čísel \(x\) a \(y\), pričom tieto cifry si musia zodpovedať. Hradlo XORc dostane dvojicu \((x_0,y_0)\), zvyšné dvojice \((x_1,y_1)\), \((x_2,y_2)\) až \((x_7,y_7)\) patria hradlám XOR3c. Tieto hradlá dostanú ako tretí vstup prenosovú hodnotu z predchádzajúceho sčítania, teda \((x_1,y_1)\) sa sčítava s prenosom z \((x_0,y_1)\), dvojica \((x_2,y_2)\) sa sčítava s prenosom z \((x_1,y_1)\) atď.. Prvé výstupy jednotlivých sčítaní sú postupne cifry \(z_0\) až \(z_7\). Cifra \(z_8\) je rovná prenosu posledného sčítania \((x_7,y_7)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.