Booleova algebra

Booleova algebra je algebraická struktura se dvěma binárními a jednou unární operací.

Jedná se o šestici ( $A$ , $\land$ , $\lor$ , $-$ , $0$ , $1$ ), kde $A$ je neprázdná množina

Nejmenší prvek $0 \in A$
Největší prvek $1 \in A$
Unární operace (negace) $\overline{0} = 1$

Budeme se soustředit na dvouprvkovou Booleovu algebru tj. budou 2 prvky:

$1$ - ( $t r u e$ )
$0$ - ( $f a l se$ )

Základní matematické symboly

Název	Znak	Definice
Negace	$\neg$ nebo $\overline{x}$	Neguje vstup, tedy z 1 dostaneme 0 a obráceně
Disjunkce (spojení)	$\lor$ nebo $+$	Logické nebo
Konjunkce (průsek)	$\land$ nebo $\cdot$	Logické a

Axiomy

Název	Součet	Součin
komutativní	$x + y = y + x$	$x \cdot y = y \cdot x$
distrubutivní	$(x + y) \cdot z = x \cdot z + y \cdot z$	$(x \cdot y) + z = (x + z) \cdot (y + z)$
neutralita 0 a 1	$x + 0 = x$	$x \cdot 1 = x$
agresivita 0 a 1	$x + 1 = 1$	$x \cdot 0 = 0$
vyloučení třetího	$x + \overline{x} = 1$	$x \cdot \overline{x} = 0$

Prohozením $0 ⇋ 1$ a zároveň $+ ⇋ \cdot$ v celém obvodu/výrazu zůstane chování (logická funkce) zachovaná (samozřejmě při prohození 1 a 0 i na vstupech/výstupech). Toto chování vychází ze symetrie námi vybraných operátorů $+$ a $\cdot$ k modelování Booleovy algebry.

Výraz	Duální výraz
$x \cdot \overline{y + \overline{z}}$	$\overline{\overline{x} + \overline{\overline{y} \cdot \overline{\overline{z}}}}$

De Morganovy zákony

Zákon
$\overline{x} + \overline{y} = \overline{(x \cdot y)}$
$\overline{x} \cdot \overline{y} = \overline{(x + y)}$

Zákon je efektivně lokální aplikací duality Booleovy algebry. Pokud v nějaké sekci obvodu vyměníme $+$ (OR) za $\cdot$ (AND) a obráceně, a na rozhraní sekce všechny znegujeme všechny signály (tím uvnitř sekce vyměníme 1 a 0), tak chování celého obvodu zůstane zachováno.
Z toho vyplývá, že lze vytvořit verzi De Morganových zákonů i pro 3 a více vstupů, klidně s odlišnými operátory.

Užitečné zákony

Název	Součet	Součin
asociativní	$x + (y + z) = (x + y) + z$	$x \cdot (y \cdot z) = (x \cdot y) \cdot z$
o idempotenci prvků (absorbce)	$x + x = x$	$x \cdot x = x$
absorbce	$x + x \cdot y = x$	$x \cdot (x + y) = x$
dvojí negace	$\overline{\overline{x}} = x$	$\overline{\overline{x}} = x$

Hradlo XOR

Hradlo XOR můžeme kdykoliv zaměnit za disjunktivní normální formu (DNF) jeho logické funkce:

$x \oplus y = x \cdot \overline{y} + \overline{x} \cdot y$

Hradla - Teorie

Pravdivostní tabulka

Pro značení budeme používat pravdivostní tabulku, která označuje nějaký vztah mezi vstupy a výstupy. Jedná se o jednoduchou tabulku, kde se nachází libovolně vstupů, (typicky A,B,CIN,...) a výstupů (typicky X,COUT,OUT,...). S následujících příkladů u hradel, hned pochopíte o co jde.

Hradla s jedním vstupem

Hradla, které mají jeden vstup jsou následující

Buffer (repeater)
NOT

Buffer (repeater)

Buffer se převážně využívá na zopakování a posílení vstupu. Taky tím "ukazujete", jakým směrem teče proud.

Symbol

Definice

Matematická definice

$Q = A$

Zápis v C

bool A;
bool Q = A;

Pravdivostní tabulka

A	Q
0	0
1	1

NOT

Hradlo NOT použijete, když potřebujete změnit hodnotu na její opak.

Neboli 0 → 1 nebo 1 → 0

Symbol

Definice

Matematická definice

$Q = \overline{A}$

Zápis v C

bool A;
bool Q = !A;

Pravdivostní tabulka

A	Q
0	1
1	0

Základní hradla se dvěma vstupy

Základní hradla, které mají dva vstupy jsou následující

AND

Hradlo AND neboli logické "a" , se využívá když chcete naplnit dvě podmíky.

Pokud platí A a B, tak pošli na výstup hodnotu 1

Symbol

Definice

V Booleově algebře se hradlo AND rovná násobení

$Q = A \cdot B$

Zápis v C:

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = A && B;

Pravdivostní tabulka

A	B	Q
0	0	0
0	1	0
1	0	0
1	1	1

OR

Hradlo OR neboli logické "nebo" , se využívá když chcete naplnit aspoň jednu podmíku.

Pokud platí A nebo B, tak pošli na výstup hodnotu 1

Symbol

Definice

V Booleově algebře se hradlo OR rovná součtu

$Q = A + B$

Zápis v C:

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = A || B;

Pravdivostní tabulka

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	1

XOR

Hradlo XOR neboli exkluzivní OR , se využívá když chcete naplnit pouze jednu podmíku. Jednoduše řečeno, když se sobě nerovnají.

*Pokud platí právě A nebo právě B, tak pošli na výstup hodnotu 1 ... Pokud se A nerovná B

Symbol

Definice

V Booleově algebře se pro hradlo XOR používá symbol $\oplus$

$Q = A \oplus B$

Zápis v C

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = A ^ B;

Pravdivostní tabulka

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	0

Opaky základních hradel se dvěma vstupy

Opaky základních hradel, existují právě 3

NAND (opak AND)
NOR (opak OR)
XNOR (opak XOR)

NAND

Hradlo NAND má opačný výstup hradla AND

Pokud neplatí A a B, tak pošli na výstup hodnotu 1

Symbol

Definice

V Booleově algebře se hradlo NAND rovná negaci násobení

$Q = \overline{(A \cdot B)}$

Zápis v C:

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = !(A && B);

Pravdivostní tabulka

A	B	Q
0	0	1
0	1	1
1	0	1
1	1	0

NOR

Hradlo NOR má opačný vstup hradla OR

Pokud neplatí A nebo B, tak pošli na výstup hodnotu 1

Symbol

Definice

V Booleově algebře se hradlo NOR rovná negaci součtu

$Q = \overline{(A + B)}$

Zápis v C:

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = !(A || B);

Pravdivostní tabulka

A	B	Q
0	0	1
0	1	0
1	0	0
1	1	0

XNOR

Hradlo XNOR je opak hradla XOR, jednoduše řečeno se jedná o ekvivalenci

Pokud se A rovná B

Symbol

Definice

V Booleově algebře se hradlo XNOR rovná negaci operaci ((\oplus))

$Q = \overline{(A \oplus B)}$

Zápis v C:

bool A = <bool_val>;
bool B = <bool_val>;
bool Q = !(A ^ B);

Pravdivostní tabulka

A	B	Q
0	0	1
0	1	0
1	0	0
1	1	1

Cheat sheet

Cheat sheet pro logické hradla

Vstup A a Vstup B dává výstup <operace>

A	B	AND	OR	XOR	NAND	NOR	XNOR
0	0	0	0	0	1	1	1
0	1	0	1	1	1	1	0
1	0	0	1	1	1	1	0
1	1	1	1	0	0	0	1

Zobrazení logických hradel v logisimu

Karnaughova mapa

Karnaughova mapa je prostředek pro minimalizaci logických obvodů. Pro pochopení Karnaughovy mapy musíme první pochopit Grayův kód.

Grayův kód

Grayův kód je binární číselná soustava, ve které se každé dvě po sobě jdoucí hodnoty liší v jedné bitové pozici.

Příkladná tabulka pro 3 bity (tučně zvýrazněný změněný bit):

A	B	C
0	0	0
0	0	1
0	1	1
0	1	0
1	1	0
1	1	1
1	0	1
1	0	0

Karnaughova mapa - příklad 1

Máme pravdivostní tabulku se vstupy $A, B, C, D$ a výstupem $Q$ :

A	B	C	D	Q	index bitu
0	0	0	0	0	0
0	0	0	1	1	1
0	0	1	0	1	2
0	0	1	1	1	3
0	1	0	0	0	4
0	1	0	1	0	5
0	1	1	0	0	6
0	1	1	1	0	7
1	0	0	0	1	8
1	0	0	1	1	9
1	0	1	0	1	10
1	0	1	1	1	11
1	1	0	0	1	12
1	1	0	1	1	13
1	1	1	0	0	14
1	1	1	1	0	15

Vytvoříme tabulku pomocí indexů v pravdivostní tabulce (odvíjí se od Grayova kódu). Neboli doplníme do obrázku

Vznikne nám následující tabulka

Zakroužkujeme sousedy

Musíme zakroužkovat všechny $1$ , kroužkujeme buď samostatnou $1$ (v tomto případě je výsledek stejný jako při stavění pomocí mintermů přímo z pravdivostní tabulky, tady K-mapa nemá žádný přínos) nebo obdélníky s obsahem rovným některé mocnině $2$ $2, 4, 8...$ , z čehož přímo výplývá (jako nutná podmínka), že obě dělky stran obdélníků musí být mocniny dvou.

Vytvoříme výrazy

Růžová - $A \cdot \overline{C}$
Zelená - $A \cdot \overline{B}$
Modrá - $\overline{B} \cdot C$
Oranžová - $\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot D$

Sečteme výrazy

$(A \cdot \overline{C}) + (A \cdot \overline{B}) + (\overline{B} \cdot C) + (\overline{A} \cdot \overline{B} \cdot \overline{C} \cdot D)$

Upravíme výraz

$A \overline{C} + A \overline{B} + \overline{B} C + \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot D = A \overline{C} + \overline{B} \cdot (A + C + \overline{A} \cdot \overline{C} \cdot D)$

Karnaughova mapa - příklad 2

Máme pravdivostní tabulku se vstupy $A, B, C$ a výstupem $Q$ :

A	B	C	Q
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Vytvoříme si Karnaughovu mapu (tam kde jsou písmena, tak je hodnota nastavená na 1)

Doplníme do tabulky

Zakroužkujeme největší obdelníky a vyjádříme je

POZOR: oranžový 1x1 obdélník není optimální (maximální), lepší by byl jako 2x2 čtverec přecházející přes hranu. Je to takhle zvolen abychom ukázali, že K-Mapa dál funguje, jenom není výsledek optimální - 1x1 čtverec je potřeba vyjádřit jako 4-term, místo 2-termu pokud bychom udělali 2x2.

Vidíme, že je blok nezávislý na tom, jestli je $A$ $0$ nebo $1$ , takže zahrneme jen proměnou $B$ a $C$

$B$ musí být $0$
$C$ musí být $0$

$Q_{1} = \overline{B} \cdot \overline{C}$

Součin jsme použili, protože je $\cdot$ totožné logickému a zároveň platí (v programovacím jazyku C -->&&)

Jelikož se jedná o torus (viz. gif), můžeme označit i hodnoty, které se nacházejí "vedle sebe" (na začátku a na konci)

Vidíme, že je výraz $Q_{2}$ nezávislý na proměnné $B$ (může být $0$ nebo $1$ )

$A$ musí být $0$
$C$ musí být $0$

$Q_{2} = \overline{A} \cdot \overline{C}$

Sjednotíme výrazy

Výsledné výrazy sečteme

$Q = Q_{1} + Q_{2} = (\overline{B} \cdot \overline{C}) + (\overline{A} \cdot \overline{C})$

Výsledný výraz si můžeme postavit v logisimu viz. obrázek

Zkontrolujeme pravdivostní tabulku.
1. Klikneme pravým tlačítkem na circuit v nabídce (základní je main)
2. Klikneme na tlačítko Build Circuit
3. Potvrdíme tlačítkem OK, popřípadě Yes
4. Vybereme v nabídce Table
5. Dostaneme tabulku viz. obrázek

Teorie - Příprava na test

1. Nakresli logická hradla, zapiš operátor hradla jako výraz (např. X=A+B), nakresli pravdivostní tabulku:

a) NOT

Řešení

$X = \overline{A}$

A	X
0	1
1	0

b) OR

Řešení

$X = A + B$

A	B	X
0	0	0
0	1	1
1	0	1
1	1	1

c) XNOR

Řešení

$X = \overline{(A ⨁ B)}$

A	B	X
0	0	1
0	1	0
1	0	0
1	1	1

d) AND

Řešení

$X = A \cdot B$

A	B	X
0	0	0
0	1	0
1	0	0
1	1	1

2. Pojmenuj následující hradla, zapiš jejich výraz a pravdivostní tabulku

Řešení

NOR

$X = \overline{(A + B)}$

A	B	X
0	0	1
0	1	0
1	0	0
1	1	0

Řešení

XOR

$X = A ⨁ B$

A	B	X
0	0	0
0	1	1
1	0	1
1	1	0

Řešení

NAND

$X = \overline{(A \cdot B)}$

A	B	Q
0	0	1
0	1	1
1	0	1
1	1	0

3. Zapiš výraz pro výstupy zapojení a pro označené vodiče:

Řešení

a) $A \cdot B$

b) $\overline{C}$

$X = (A \cdot B) ⨁ \overline{C}$

Řešení

a) $\overline{A}$

b) $B + C$

c) $\overline{(B + C) ⨁ D}$

$X = \overline{A} \cdot (B + C)$

$Y = (B + C) \cdot \overline{(B + C) ⨁ D}$

4. Nakresli zapojení pro následující výraz a nakresli pravdivostní tabulku

$X = (A \cdot B) + (\overline{A ⨁ C}) + \overline{B}$

Řešení - zapojení

Řešení - tabulka

Taktéž v zapojení můžeme použít jeden OR, který příjmá 3 vstupy místo dvou (jelikož sčítání je asociativní a komutativní).

Vytváření tabulky si ulehčíme spočítáním sloupců pro námi zvolené podvýrazy ( $A \cdot B$ , $\overline{A ⨁ C}$ , $\overline{B}$ ) jejich hodnoty použijeme v dalších výpočtech, abychom se vyhnuli chybám při počítání komplikovaných výrazu z hlavy. Pokud víme na první pohled hodnoty některých řádků výsledku, můžeme je vyplnit hned do výsledku a v pomocných sloupcích je přeskočit. Nutné sloupce jsou pouze vstupy ( $A$ , $B$ , $C$ ) a výstupy ( $X$ ).

$A$	$B$	$C$	$A \cdot B$	$\overline{A ⨁ C}$	$\overline{B}$	$X$
0	0	0	0	1	1	1
0	0	1	0	0	1	1
0	1	0	0	1	0	1
0	1	1	0	0	0	0
1	0	0	0	0	1	1
1	0	1	0	1	1	1
1	1	0	1	0	0	1
1	1	1	1	1	0	1

5. Zjednoduš následující výraz do co nejjednodušší podoby

Výsledek zde: $□$

$X = (A C + C + B) + \overline{B \cdot \overline{C}} + \overline{C} (\overline{A} C + C)$

Řešení

$X = (C (A + 1) + B) + \overline{B} + C + \overline{C} (C (\overline{A} + 1))$

$X = (A C + B) + \overline{B} + C + \overline{C} \cdot (\overline{A} C)$

$X = A C + B + \overline{B} + C + 0$

$X = A C + 1 + C$

$X = 1$

Výsledek zde: $□ + □$

$X = (A + C) (A \cdot B + \overline{\overline{A} + B}) + A C + C$

Řešení

$X = (A + C) (A \cdot B + A \cdot \overline{B}) + C$

$X = (A + C) (A \cdot (B + \overline{B})) + C$

$X = ((A + C) \cdot A) + C$

$X = A \cdot A + A \cdot C + C$

$X = A + C$

Instalace Logisimu Evolution

Máte správný Logisim?

Pozor na to, že používate Logisim Evolution. Klasický Logisim je už léta zastaralý, je nestabilní, nepodporuje moderní komponenty, a projektové soubory s Logisimem Evolution nejsou kompatibilní!

Verze Logisimu Evolution

Minimální požadovaná verze Logisimu Evolution v tomto předmětu je 3.9.0.

Java 21

Logisim Evolution od verze 3.9.0 vyžaduje Javu 21.

Linux

Nejpřímočařejší nainstalovat openjdk z repozitářů, e.g. na ubuntu:

apt-get install openjdk-21-jre

Windows

Doporučuji Microsoft build openjdk, protože se hezky zaintegruje do windows a aplikace to můžou bez problému najít. Pro windows tedy instalátor .msi. Během instalace je vhodné vybrat všechny features, tedy i nastavení JAVA_HOME a Oracle registry keys.

Instalace bez administrátorských práv (e.g. ve škole)

V případě, že nemáte k dispozici administrátorské práva, postačí .zip openjdk, který si rozbalíte, a do jeho bin složky (vedle java.exe) nakopírujete logisim. Přes shift-rightlick můžete pak ve složce otevřít terminál, ve kterém lze logisim spustit přes

.\java.exe -jar logisim-evolution-xxxx.jar

Je důležité mít .\ před java.exe, jinak se použije systémová, potenciálně zastaralá, java.

Logisim Evolution

Obecně stáhneme z oficiálního git repa v releases https://github.com/logisim-evolution/logisim-evolution/releases nejnovější verzi.

Tedy

Debian based (e.g. Ubuntu) - .deb
RPM package - .rpm
Windows - .msi
macOS - .dmg
Ostatní - .jar - půjde spustit buď poklikáním nebo z terminálu pomocí java -jar logisim-evolution-xxx.jar

Warning

Na linuxu pozor na instalaci z repozitářů distribuce (apt, dnf, yum, flatpak, snap, ...). Často v nich bývají zastarelé verze, které nemají pro nás potřebné bugfixy a features (třeba autosave)!

Arch linux

Můžeme nainstalovat z Arch AUR repozitáře pomocí yay

yay -S logisim-evolution-bin

Pokud preferujete instalaci ze zdrojáku, můžete vynechat -bin.

Logisim template

Template si můžete nastavit v File > Preferences... > Template > User template > Select > Vybrat template file

Všechny gaty jsou nastaveny na narrow, všechny plexery mají disabled output zero.

Download - template

Logisim - Základy

Máte správný Logisim?

Verze Logisimu Evolution

Minimální požadovaná verze Logisimu Evolution v tomto předmětu je 3.9.0.

Po úspěšném nainstalovaní logisim-evolution (viz. návod) a spuštěním, uvidíte tohle:

Template

Jako první vám doporučuji nahrát template, kde jsou všechny gaty nastavené na narrow.

template.circ

Nahrajeme template:

File --> Open --> vybereme template.circ soubor, který jsme stáhli.

Uložíme zvlášť, abychom nepřepsali náš template:

File --> Save As --> Uložíme nový soubor (taky můžeme použít zkratku Ctrl + Shift + S)

Základy

Kurzory

Kurzory se nachází v horním menu, levým kliknutím můžeme vybrat kurzor.

Jsou celkem 4

Červený kurzor - interaktivní kurzor, měníme pomocí něj hodnoty nebo se pohybujeme v logickém obvodu
Černý kurzor - měníme zapojení, vkládáme různé komponenty
Dráty - tvoření drátů
Text - na popsání obvodu

Kurozry můžeme měnit pomocí zkratky Ctrl + [1-4]

První obvod

V zelénem obdelníku se vyskytují složky obsahující různé komponenty.

Zadání

Vytvořte logický obvod, který se bude chovat úplně stejně jako logický AND.

První si vytvoříme nový obvod a to tím, že klikneme pravým tlačítkem na název našeho projektu (složka ve ktéré máme obvod main). U mě je to logisim-uvod viz. obrázek

Klikneme na Add Circuit a zvolíme jméno obvodu třeba custom_and, potvrdíme a klikneme na něj dvakrát pro otevření.

První rozklikneme složku Wiring a klikneme na komponent Pin. Komponent přetáhneme do obvodu dvakrát (AND má 2 vstupy)

Poté tam dáme AND, který najdeme v Gates/AND Gate klikneme na komponentu a přidáme ji.

Taky musíme přidat výstup (output pin), což je vlastně Pin. Takže přetáhneme komponentu do obvodu.

Klikneme na náš pin a změníme jeho vlastnosti na následující.

Nezbývá nám nic jiného než obvod propojit a máme následující logický obvod. Přidáme labely pro přehlednost, které taky najdeme ve vlastnostech.

Náš nově vytvořený obvod vložíme do main

Klikneme dvakrát na main
Vybereme custom_and a vložíme do obvodu
Přidáme nějaké input a output piny pro testování

Následovně můžeme měnit hodnotu input pinů a to, že vyberem červenou ruku nahoře v nabídce nebo pomocí zkratky Ctrl + 1

Vlastnosti komponent

Jsou 2 možnosti jak změnit vlastnosti komponent:

Pouze pro jednu instanci komponentu
- Změníme pomocí vybrání komponentu v obvodu
Pro všechny instance kompenentu
- Změníme pomocí vybrání komponentu v nabídce

Nejčastěji upravované vlastnosti jsou:

Facing - Otočení komponenty
Label - Text u komponenty
Gate Size - Velikost hradla
Output? - Jestli je Pin output nebo ne

Cvičení

Vytvořte podobné obvody pro OR a XOR.

Třetí stav a zkraty

Váš obvod může mít 4 stavy

0 - Vypnutý stav
1 - Zapnutý stav
U - Třetí stav (undefined)
E - Zkrat

Legitimní stavy

0 - Vypnutý stav
1 - Zapnutý stav
U - Třetí stav (undefined)

Legitimní stavy jsou všechny kromě zkratu. Občas se tedy stane, že i třetí stav je žádoucí.

Třetí stav

Třetí stav je nedefinovaná hodnota. Příkladné použití je pomocí Controlled Buffer (Najdeme v Gates/Controlled Buffer). Tenhle komponent vám buď propustí proud, nebo ne.

Příklad

Máme následující obvod. Pokud nic nepouštíme, máme třetí stav, hodnota není definovaná.

Pokud pustíme vstup A, tak dostaneme 0, pokud pustíme vstup B, tak dostaneme 1.

A pokud pustíme oba vstupy na jednou, dostaneme zkrat, jelikož se hodnoty liší.

Multiplexory a dekodéry

Reprezentace čísel jako binární řetězce

Čísel (zatím kladných, později celých) je nekonečno, a jsou to abstraktní objekty. Aby s nimy šlo pracovat, je potřeba je umět nějak vyjádřit. My, lidé, na to používáme desitkovou soustavu, zapíšeme např. číslo 137. Počítače pracují pouze s 0 a 1, takže tato reprezentace není vhodná. Je potřeba zvolit nějakou jinou.

Dvojková soustava

Přirozeně se nabízí použít dvojkovou soustavu neboli binární kód. Číslo reprezentujeme jako součet mocnin dvou (namísto 10 v desítkové). Tento způsob má maximální využití bitů pro přenos informace, tj. pro čísla dané velikosti je nejkratší. Pro reprezentování čísla $2^{b} - 1$ potřebujeme $b$ bitů.

https://commons.wikimedia.org/wiki/File:Binary_counter.gif

Není to ale jediný způsob, jak pomocí řetězce bitů reprezentovat číslo. S několika dalšími způsoby se ještě setkáme, jakmile začneme potřebovat umět reprezentovat záporné čísla. Prozatím ale zůstaneme u čísel kladných.

Kód "1 z N" (one-hot coding)

Kód 1 z N spočívá v zakódování čísla $n$ o z rozsahu $[0, N - 1]$ jako řetězec $N$ bitů, kde všechny bity jsou $0$ , pouze jediný $n$ -tý bit je $1$ :

$9_{10} = 100 1_{2} = 000000000100000 0_{1 o f 16}$

Tento kód je velmi neefektivní z hlediska potřebného počtu bitů, takže v tomto kódu asi nebude nic nikam posílat, ale je velmi užitečný lokálně v obvodech, protože každý bit kódu přesně vyjadřuje, jestli se jedná o dané číslo. Zároveň máme garantované, že pokud je jeden z bitů $1$ , všechny ostatní musí být $0$ (jinak by se nejednalo o validní hodnotu v kódu 1 z N). Taková sada bitů se velmi hodí na rozhodování typu "switch":

Pokud byla v paměti tato instrukce, udělej tohle (pro všechny možné instrukce)
Na vstupu je ID početní operace. Proveď danou operaci.
Pokud na vstupu byly tyto 4 hodnoty, udělej tohle, jinak udělej něco jiného (bity lze ORnout)

Dekodér

Dekodér má $2^{n}$ výstupů a $n$ bitový vstup (selector). Provádí převod z $n$ -bitového binárního čísla do kódu 1 z $2^{n}$ , tedy říká v jednoduše zpracovatelné podobě které číslo má na vstupu.

Dekodér může mít ještě vstup ENA (enable). Pokud existuje, a je na jeho vstup přivedena $0$ , dekodér má na výstupu samé nuly, což má většinou za efekt vypnutí rozhodovací logiky za ním přiojené (nenastala ani jedna z variant). Generuje pak kód "až 1 z N".

Warning

Pokud používáte dekodér s enable v Logisimu, ujistěte se, že máte nastavenou možnost "Disabled output" na "Zero". Druhá možnost "Floating" by generovala třetí stav, který je až na výjimky zakázaný!

Multiplexor

Multiplexor bere $2^{n}$ vstupů a $n$ bitový vstup selector (SEL). Výstup má pouze jeden. Může taky obsahovat enable (ENA), který určuje, jestli je součástka zapnutá nebo ne.

Warning

Opět platí, že "Disabled output" musí být až na výjimky nastavený na "Zero".

Multiplexor se chová jako "výhybka" nebo "switch statement": Na svůj jediný výstup pošle hodnotu z toho ( $n$ -tého) vstup, který je vybraný na selector vstupu ( $n$ ). Na komponentě je vyznačený 0. vstup a ostatní jsou ve vzestupném pořadí.

Multiplexor

Můžeme si chování multiplexoru shrnout do tabulky

SEL	Vysílaný vstup
00	A
01	B
10	C
11	D

Pro větší multiplexory bude tabulka větší.

Multiplexor může mít kromě "rozhodovací" šířky $n$ , která určuje počet vstupů, také "datovou" šířku $b$ , která určuje velikost sběrnice každého "kanálu" multiplexoru. Multiplexor pak jednoduše přeposílá $b$ -bitové hodnoty ze vstupů na výstup.

Demultiplexor

Demultiplexor se chová obráceně z hlediska vstupů. Má jeden vstup a $2^{n}$ výstupů.

Demultiplexor

Warning

Opět je potřeba mít "Disabled output" nastavený na "Zero".

Info

Pokud má 1-bitový demultiplexor nastavený "Disabled output" na "Zero", chová se stejně (má stejnou logickou funkci a pravdivostní tabulku) jako Dekodér s enable. Datový vstup demultiplexoru pak plní stejnou funkci jako enable u dekodéru.

Cvičení

Důležité

V kombinačních obvodech je až na vyjímky zakázáno používat třetí stav! Každý obvod, pro který by šla vytvořit pravdivostní tabulka, jde postavit ze základních hradel, bez třetího stavu!

Vytvořte si vlastní dekodér, který bude mít 2 bitový SEL vstup.

Done

Dekodér 2-bitový SEL

Vytvořte si vlastní multiplexor, který bude mít 2 bitový SEL vstup a 1 bitové datové bity, pomocí logických bran.

Done

Multiplexor 2-bitový SEL

Komparátor

Cvičení

1 bitový komparátor

Postavte 1 bitový komparátor, který má 2 vstupy $A, B$ a 3 výstupy A>B (GT), A=B (EQ), A<B (LT)

Řešení

2 bitový komparátor

Postavte 2 bitový komparátor, který má dva 2 bitové vstupy $A, B$ a 3 výstupy A>B (GT), A=B (EQ), A<B (LT)

Řešení - Komparátor 2b

Řešení - compGE

Řešení - Popis

Vytvořili jsme si compGE, abychom ušetřili dvě logic gaty, jelikož potřebujeme pro 2 bitový komparátor pouze GT a EQ.

ALU - Úvod

Poznámka

Obsah této stránky slouží jako úvod k principu ALU, má pouze informační povahu a není součástí zadání ALU!

Každé CPU vyžaduje ALU neboli Arithmetic Logic Unit. Jedná se o "krabičku", která dokáže různé operace jako například sčítání, odčítání, bitwise operace, atd... V této kapitole se dozvíte, co je vše potřeba v ALU obsáhnout.

Info

ALU musíte postavit do samostatného modulu, který se musí jmenovat přesně ALU. Jinak nebude možné ALU ohodnotit!

Vstupy ALU

vstup A a B - n-bitový vstup, záleží kolika bitové děláte ALU
CIN - Carry IN, 1 bitová dodatečná hodnota
SEL - Nebo taky Opcode, typicky 4 bitový, rozhoduje kolik vaše ALU umí operací

Výstupy ALU

OUTP - n-bitový výstup, záleží kolika bitové děláte ALU
HOUT - použito pro násobení, využito pro vyšší polovinu výsledku
ZERO - 1 bitová hodnota, rozhoduje jestli jsou na výstupu samé nuly
COUT - Carry OUT z operací, 1 bitová hodnota
SIGN - Znaménko hodnoty výstupu (totožné s nejvyšším bitem hodnoty)
GT, LT, EQ - Nepovinně můžeme přidat operace z komparátoru, jde nahradit pomocí odčítání a ZERO a SIGN výstupy

Důležité

Aby bylo možné vaše ALU ohodnotit, je potřeba pro tyto dráty dodržet přesně výše uvedené názvy!

UI (uživatelské rozhraní)

Pro uživatelské rozhraní můžete použít například tyhle logisim komponenty.

Komponenty vstupů

Wiring/Pin - pro 1 bitové hodnoty
Memory/Register - pro n bitové hodnoty
Input/Output/Button - tlačítko pro například operace

Komponenty výstypů

Input/Output/LED - pro 1 bitové hodnoty
Wiring/Pin - pro n bitové hodnoty
Input/Output/Hex Digit Display - pro 4 bitové hodnoty, doporučuji dost přehledné pro výstup

Příkladný main v projektu ALU může vypadat následovně.

ALU Example Main

Operace ALU (`SEL`)

Bitwise operace

Jednoduché logické gaty pro n-bitové vstupy

NOT
OR
AND
XOR

Shifty

Posune nám hodnotu buď doleva SHL, nebo doprava SHR. Pokud by hodnota utekla, tedy například na hodnotu 1000 0000 budeme chtít použít operaci SHL, tak rozsvítíme COUT na 1 a OUT bude 0000 0000.

SHL - Shift left
SHR - Shift right

Příklad SHL

A	OUT	COUT
`0000 0001`	`0000 0010`	`0`
`1000 0000`	`0000 0000`	`1`
`1011 0111`	`0110 1110`	`1`
`0101 1101`	`1011 1010`	`0`

Příklad SHR

A	OUT	COUT
`0000 0001`	`0000 0000`	`1`
`1000 0000`	`0100 0000`	`0`
`1011 0111`	`0101 1011`	`1`
`0101 1101`	`0010 1110`	`1`

Rotace

Stejné jako shifty, ale při přetečení nastavíme nejmenší hodnotu na 1. Například máme hodnotu 0000 0001 a použijeme operaci ROTR, tak nastavíme OUT na 1000 0000 a označíme COUT na 1

ROTL - Rotate left
ROTR - Rotate right

Příklad ROTL

A	OUT	COUT
`0000 0001`	`0000 0010`	`0`
`1000 0000`	`0000 0001`	`1`
`1011 0111`	`0110 1111`	`1`
`0101 1101`	`1011 1010`	`0`

Příklad ROTR

A	OUT	COUT
`0000 0001`	`1000 0000`	`1`
`1000 0000`	`0100 0000`	`0`
`1011 0111`	`1101 1011`	`1`
`0101 1101`	`1010 1110`	`1`

Sčítačka

Sčítačka by měla být schopna provést více operací, jedná se o následující.

ADD - sčítání
SUB - odčítání
INC - inkrement (A + 1)
DEC - dekrement (A - 1)

Násobení

Bonusově můžete dodělat násobení neboli MUL. Zde se výsledek rozděluje na dva výstupy a to horní část HOUT a dolní část OUT.

MUL - násobení

ALU - Sčítačka/odčítačka

Sčítačka je podstatná část ALU. Po určitých úpravách z ní můžeme udělat dokonce i odčítačku. Začneme jednoduše, a to s jedno bitovou verzí.

Half-adder (1 bit adder)

Pravdivostní tabulka pro half-adder vypadá následovně.

Solution

A	B	OUT	COUT
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Pomocí karnaughovy mapy nebo i logiky (odkoukání) můžeme zjistit, že sčítání (OUT) je vlastně XOR a COUT je jenom AND. Takže half-adder vypadá následovně.

Solution

Half-adder

Full-adder

Full-adder využívá half adder a pomocí něj přijímá další argument a to CIN, neboli carry in.

Pravdivostní tabulka pro full-adder vypadá následovně.

Solution

CIN	A	B	OUT	COUT
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

Jediné, co tedy uděláme je, že přidáme half-adder 2 krát, jeden na A+B a druhý na výsledek z prvního X a CIN, neboli X+CIN.

COUT half-adderů by se měly sčítat, ale jelikož nemůže nastat případ, kdy jsou oba dva COUT 1, tak nám stačí OR. Taky se nemusíme bát přetečení, jelikož při sčítání 3 bitů se hodnota vždy vejde do 2 bitů (maximální hodnota je 3).

Solution

Full-adder

Binární odčítačka

Odčítání jako sčítání

Sice lze postavit dedikovaný obvod, který umí odečíst dvě čísla, podobným postupem jako u sčítačky, akorát podle odčítání pod sebou.

Nicméně o odčítání se dá uvažovat jako o přičítání záporných čísel, v matematice je to běžná věc.

$a - b = a + (- b)$

Pokud bychom tedy byli schopní vytvořit nějaký jednoduchý obvod, který z $b$ umí vytvořit nějakou hodnotu $- b$ , kterou můžeme přičíst k $a$ , abychom dostali $a - b$ , můžeme pro odčítání použít naši existující sčítačku.

Záporná čísla

Číslu $- b$ z předchozího příkladu budeme říkat zaporné číslo. Samozřejmě se pořád pohybujeme v digitální logice, toto číslo bude v počítači muset být reprezentované nějakou sekvencí $1$ a $0$ . Způsobů, jak to udělat, je hned několik (stejně jako u kladných čísel jsme měli binární kód, Grayův kód a BCD), a každá reprezentace bude mít své výhody a nevýhody.

V každém případě předpokládáme, že šířka našeho čísla v bitech je konstantní, protože naše sčítačka/ALU/CPU bude umět pracovat vždy s přesne $n$ -bitovými čísly.

Přímý kód (sign-magnitude)

Asi nejjendodušší, co vás napadne, je do jednoho z bitů (zpravidla největšího) "prostě" uložit znaménko zakódvané jako $0$ nebo $1$ , a zbytek bitů interpretovat jako normální číslo.

Tato reprezentace má několik nevýhod, zejména:

Pro sčítání těchto čísel je potřeba speciální sčítačka, zčásti protože:
Máme dvě různé nuly, $+ 0 = 000 0_{2}$ a $- 0 = 100 0_{2}$ , tedy i porovnávání čísel je komplikovanější
Odčítání nelze realizovat jednoduše jako přičtení záporného čísla

Aditivní kód (offset binary)

Další přirozený způsob spočívá v posunutí nuly "doprostřed" reprezentovatelného rozsahu - směrem nahoru budou kladná, směrem dolů záporná. Tedy v případě 8-bit čísel, kde máme 256 různých čísel, můžeme dát nulu na číslo $128$ , takže $129$ bude $1$ a $127$ bude $- 1$ .

Jedná se v podstatě o přímý kód, ale s opačným významem bitu znaménka, má stejné nevýhody.

Jedničkový doplňěk (one's complement)

Další dva možné způsoby reprezentace spočívají v hledání opačných prvků ke kladným číslům pomocí nějakého vzorce. Nejjednodušší takový vzorec je najít záporné číslo pomocí bitwise negace.

$- b = \overline{b}$

Tedy $0$ bude $000 0_{2}$ a $111 1_{2}$ . Protože $1$ je $000 1_{2}$ , $- 1$ bude $111 0_{2}$ , a podobně.

Tento kód má zase podobné nevýhody.

Dvojkový doplněk (two's complement)

Pojďme zkusit vymyslet takový kód, který bude mít vhodnou reprezentaci záporných čísel, abychom odstranili nevýhody ostatních kódů. Tedy chceme mít pouze jednu nulu, chceme aby kladné čísla měla stejnou reprezentaci jako bez znaménka, a chceme, aby šlo odčítat přičtením záporného čísla:

$a - b = a + (- b)$

Když pracujeme s n-bitovými čísly, tak vlastně pracujeme s groupu $Z_{2^{n}}^{+}$ , protože hodnoty $2^{n}$ a větší neumíme reprezentovat a horní bity zahazujeme (carry).

Např. sčítáme 8-bit čísla, pohybujeme se v $Z_{256}^{+}$ : $255 + 1 = 0 (mod 256)$

Chceme označit některá čísla z této grupy jako záporná tak, aby platily následující pravidla:

Pro každé kladné $b^{+}$ (které reprezentujeme jako číslo bez znaménka) musí existovat takové $b^{-}$ , aby platitlo $a - b^{+} = a + (- b^{+}) = a + b^{-}$ .
To je ekvivalentní tvrzení $b^{+} + b^{-} = 0$

Hledané $b^{-}$ je tedy aditivní inverzí $b^{+}$ v $Z_{2^{n}}^{+}$ . Tu umíme aritmeticky najít:

Řešení

$b^{-} = 2^{n} - b^{+}$

Pokud toto pravidlo budeme aplikovat na nezáporná čísla počínaje nulou (která je korektně sama svojí vlastní inverzí), začneme záporným číslům přiřazovat reprezentace. Přestaneme, jakmile nám dojdou volná čísla (číslo, které jsme označili jako záporné už nemůžeme zároveň považovat za kladné). Pro n=3 skončíme s následujícím přiřazením:

Binární řetězec	Bez znaménka	Dvojkový doplněk?
`000`	`0`	`0`
`001`	`1`	`1`
`010`	`2`	`2`
`011`	`3`	`3`
`100`	`4`	`4` nebo `-4` ?
`101`	`5`	`-3`
`110`	`6`	`-2`
`111`	`7`	`-1`

Tento kód ja zajímavý tím, že není nemá symetrický rozsah, tedy stejný počet kladných a záporných čísel. To vyplývá automaticky z požadavku mít pouze jednu nulu, přičemž čísel je pořád sudý počet. "Lichý" binární řetězec můžeme přiřadit buď číslu $4$ nebo $- 4$ , výsledný kód bude fungovat stejně, protože nad $Z_{8}^{+}$ platí, že $x + 4 = x - 4$ . Vlastně tedy (stejně jako pro nulu), platí, že $4 = - 4$ .

Tvoří prvky dvojkového doplňku a sčítání stále grupu?

Ano, pouze jsme prvkům dali jiné názvy. Operátor $+$ nad nimi se chová pořád stejně jako v původním $Z_{2^{n}}^{+}$ . Mezi sčítáním čísel bez znaménka a ve dvojkovém doplňku není na binární úrovní žádný rozdíl. To znamená, že pro sčítání čísel ve dvojkovém doplňku můžeme používat stejnou sčítačku, jako pro nezáporná čísla!

Musíme se tedy při tvorbě kódu rozhodnout, jestli chceme více záporných a více kladných čísel, aby šly čísla jednoznačně interpretovat. Pokud se rozhodneme "lichému" řetezci přiřadit zápornou hodnotu, získáme pro nás kód navíc jednu velmi hezkou vlastnost:

Binární řetězec	Bez znaménka	Dvojkový doplněk
`0 00`	`0`	`0`
`0 01`	`1`	`1`
`0 10`	`2`	`2`
`0 11`	`3`	`3`
`1 00`	`4`	`-4`
`1 01`	`5`	`-3`
`1 10`	`6`	`-2`
`1 11`	`7`	`-1`

Info

Nejmohutnější (most significant) bit binárního řetězce ve dvojkovém doplňku přímo odpovídá znaménku čísla!

Tip

Tomuto kódu, jak jsem jej teď sestavili, se říká dvojkový doplněk nebo doplňkový kód, a používá jej drtivá většina architektur a jazyků pro reprezentaci záporných čísel.

Rozdělili jsme tak grupu na dvě stejně velké poloviny: zápornou a nezápornou:

Two's complement

Konkrétní příklad

Co se vlastně na pozadí děje, když odečteme pomocí této techniky nějaké číslo?

Complement subtraction

Pracujeme s 4-bitovými čísly, tedy (bez znaménka) v $Z_{2^{4}}^{+}$ . Se znaménkem pracujeme v doplňkovém kódu ona obrázku.

Chceme spočítat $5 - 3$ . Nalezneme opačnou hodnotu pro číslo $3$ :

$- 3 = 2^{4} - 3 = 16 - 3 = 1 3_{10} = 110 1_{2}$

Výsledek můžeme oveřit na obrázku. Takže z našeho příkladu se stane:

$5 - 3 = 5 + (- 3) = 5 + 13 = 18 = 2 (mod 2^{4})$

Získali jsme správný výsledek. Pozorujeme, že odčítání vlastně funguje pomocí přičtení "velkého" čísla, což způsobí přetečení o "tak akorát" velké číslo, abychom dostali správný výsledek. Znamená to, že carry-out už nám bohužel nemůže nic říct o tom, zda je výsledek validní.

Lze spočítat absolutní hodnotu z libovolného čísla ve dvojkovém doplňku?

Ne bez zvětšení počtu bitů. Pro 3-bitové číslo $- 4$ :

$∣ - 4 ∣ = 4$

ale $4$ lze reprezentovat pouze ve 4- a více-bitových číslech.

Je to opravdová situace, která může nastat ve strojových číslech se znaménkem:

fn main() {
    let min = std::i8::MIN + 1; // -128 + 1 = -127
    println!(" min: {}", min);
    println!("|min|: {}", min.abs());
}

fn main() {
    let min = std::i8::MIN; // -128
    println!(" min: {}", min);
    println!("|min|: {}", min.abs());
}

Validita výsledku, přetečení (carry) a přeplňení (overflow)

U sčítání jsme měli výstup carry, který nám indikoval, že výsledek se nevejde do šířky výstupu sčítačky. Tomu jevu se říkalo přetečení.

U záporných čísel se to trochu komplikuje - jak jsme si ukázali na příkladu, zde nám carry může a nemusí nastat ikdyž je výsledek validní. Tedy "přetečení" neboli carry nám nepomůže.

Potřebujeme vymslet jiný indikátor toho, jestli operace ve dvojkovém doplňku byla validní. Pokud tomu tak nebude, budeme tomu říkat přeplňení (overflow).

Přeplnění nastane, pokud hodnota "vyjede" z reprezentovatelného rozsahu. U čísel se znaménkem to může být směrem nahoru (mělo vyjít číslo vyšší, než to nejvyšší reprezentovatelné) nebo směrem dolů (menší než nejmenší reprezentovatelné).

Danou operací sčítaní nebo odčítání se můžeme na kruhu posunou pouze o půlkruh. Tedy, pokud se budeme pohybovat směrem k nule, musíme garantovaně skončit v druhé půlce kruhu, a naše odpověď bude validní. Např. pokud jsme v záporných číslech a přičítáme, skončíme nejdál o půlkruh dál v kladných číslech, na správném výsledku.
Pokud tedy sčítáme kladné a záporné číslo, nemůže přeplnění nastat.

Problém nastává, pokud máme záporné číslo a chceme dále odečítat, nebo máme kladné číslo a chceme dále přičítat. Tedy, přeloženo pouze na součty, máme záporné číslo a chceme přičíst záporné číslo, nebo máme kladné číslo, a chceme přičíst kladné číslo. Tam by se mohlo stát, že se přehoupneme přes hranici MIN-MAX, a číslo náhle změní polaritu.
Tedy, pokud sčítáme kladné a kladné číslo, musí být výsledek kladný, aby byl validní.
Podobně, pokud sčítáme záporné a záporné číslo, musí být výsledek záporný.

Jak víme, znaménko je u čísel se znaménkem vždy Most Significant Bit hodnoty, můžeme tedy sestavit pravdivostní tabulku pro vyhodnocení overflow:

A	B	A+B	Overflow?
+	-	X	0
-	+	X	0
+	+	+	0
+	+	-	1
-	-	-	0
-	-	+	1

Tento signál si pojmenujeme overflow a vyvedeme taky z ALU, podobně jako cout, bude užitečný procesoru v rozhodování o validitě operací se znaménkem.

Efektivní hledání opačného čísla ve dvojkovém doplňku

Našli jsme tedy pěkný kód, který nás nechá pro odčítání recyklovat naši existující sčítačku. Ale, abychom doopravdy mohli odčítat, musíme být schopni rychle nalézt k danému číslu jeho opačné číslo.

Vzorec pro opačné číslo v doplňkovém kódu je následující:

$b^{-} = 2^{n} - b^{+}$

...ovšem pro výpočet tohoto vzorce musíme umět odčítat. Je potřeba se tohoto odčítání nějak "zbavit" a nahradit ho jinou operací, kterou spočítat umíme.

S trochou algebry získáme:

$b^{-} = 2^{n} - b^{+} = (2^{n} - 1 + 1) - b^{+} = (2^{n} - 1) - b^{+} + 1$

$(2^{n} - 1)$ v tomto výrazu je konstanta, která má podobu binárního řetězce samých jedniček o délce $n$ . Odečtením libovolného čísla od takové hodnoty nikdy nenastane žádný přenos a odečítaná hodnota se touto operací jednoduše zneguje (vyzkoušejte odečtením pod sebou na papíře), tedy $(2^{n} - 1) - b^{+} = \overline{b^{+}}$ . Dosazením do původního vzorce dostáváme

$b^{-} = \overline{b^{+}} + 1$

což je vzorec pro efektivní výpočet opačného čísla ve dvojkovém doplňku v hardwaru. Pozor, pokud je dvojkový doplňěk n-bitový, musí i negace být n-bitová!

Tedy, pokud chceme odečíst dvě čísla A, B, stačí provést:

$A - B = A + (- B) = A + \overline{B} + 1$

Pokud chceme odčítat, přivedeme tedy na vstup B naší odčítačky invertovanou hodnotu. Na první pohled se zdá, že budeme muset provést dva součty, nicméně $+ 1$ lze na naší sčítačce zajistit pomocí vstupu cin, který při odčítání zafixujeme na kostantní 1.

Z poloviční odčítačky na úplnou

Tím, že jsme takhle použili cin, jsme znemožnili řetězení více menších rozdílů pro provedení většího, jako to šlo u sčítání. Hovoříme tedy o poloviční odčítačce (half-subber). Jak tedy tuto funkcionalitu obnovit, a získat plnou odčítačku (full-subber)?

U odčítání se řetězení provádí pomocí tzv. výpůjčky (borrow). Pokud je borrow-in $1$ , odečteme ještě o jedničku více (podobné ale opačné chování jako carry). Na výstupu odčítačky je naopak borrow-out, který signalizuje přetečení do záporných hodnot, tedy v dalším řádu se má odečíst jednička navíc (borrow-in).

Pokud do našich výpočtů zahrneme borrow-in ( $b_{in}$ ):

$A - B - b_{in} = A + \overline{B} + 1 - b_{in}$

$1 - b_{in}$ lze podobně jako předtím vyjádřit jako $\overline{b_{in}}$ . Máme tedy:

$A - B - b_{in} = A + \overline{B} + \overline{b_{in}}$

Tuto operaci opět provedeme na naší sčítačce, jako cin při odčítání přivedeme $\overline{b_{in}}$ . borrow-in je tedy pouze invertované carry-in.

Kvůli neuvedeným skutečnostem (doplňkový pseudokód) platí to samé pro borrow_out:

$b_{o u t} = \overline{c_{o u t}}$

Tedy abychom dostali borrow_out pro odčítání, stačí znegovat carry_out z výše uvedeného součtu.

Summary

Obecně tedy platí, že carry u sčítání a borrow u odčítání jsou přesné opaky. Tedy pokud převádíme odčítání na sčítání, je potřeba převést borrow-in na carry-in, provést součet, a poté převést výsledný carry-out na borrow-out.

V ALU bude typicky pouze jeden carry-in a jeden carry-out výstup. Tyto IO mají pak dvojí smysl, během sčítání zastávají funkci carry, a během odčítání borrow.

Sčítačka-Odčítačka

ALU musí samozřejmě umět nějěnom odčítat, ale i sčítat. Nestačí tedy zkonvertovat sčítačku na odčítačku. Taky není dobré řešení mít dvě sčítačky, jednu na sčítání a odčítání, když ALU děla v jeden čas vždy pouze jednu z obou operací, to je v ALU penalizováno.

Je tedy potřeba postavit modul sčítačka-odčítačka, který umí obojí, a má speciální vstup (může se jmenovat např. sub jako subtract), kterým lze zapnout režim odčítání.

V režimu sčítání bude počítat $A + B + C I N = O U T, CO U T$ .
V režimu odčítání bude počítat $A - B = O U T, CO U T$ (varianta half_sub)
- Tedy $C I N$ se nebere v potaz, $CO U T$ výstup je zapojen stejně jako u součtu.
Alternativně v režimu odčítání bude počítat $A - B - B I N = O U T, BO U T$ (varianta full_sub)
- $B I N, BO U T$ mají korektní borrow chování ve dvojkovém doplňku, viz "Jak zřetězím dve odčítání"
- $C I N / B I N$ je jeden vstup pojmenovaný CIN nebo CIN_BIN, který přepíná své chování podle toho, zda se zrovna odčítá.
- $CO U T / BO U T$ stejně.

Implementace

Pro implementaci této komponenty je samozřejmě potřeba mít jako modul hotovou sčítačku. Poté stačí pomocí vhodných multiplexorů podle vstupu sub vybírat, jaké hodnoty vlastně na vstupy sčítačky chceme přivést, případně jaké hodnoty (třeba vypočtené z výstupů sčítačky) chceme vyvést na výstupy modulu.

Zadání projektu ALU

Vytvořte v Logisim Evolution modul tzv. Aritmeticko-Logické jednotky (ALU). ALU je (v našem provedení) kombinační obvod, který umí provést vždy jednu vybranou z několika podporovaných aritmetických nebo logických operací.

Formální náležitosti odevzdání

Danger

V případě nedodržení některého z těchto požadavků bude ALU hodnoceno 0 body.

Odevzdání

Odevzdávání probíhá na platformě Submitty hostované mnou na adrese: https://submit.vojacek.org. Pro přihlášení potřebujete přihlašovací údaje, které jste dostali automatizovaným emailem (zkuste se podívat i do spamu, a email ze spamu přesuňte do doručených, aby se vám nesmazal!). Více informací naleznete právě v tomto emailu. V případě problémů mě kontaktujte emailem.

V případě, že by systém nefungoval, je záložní metoda odevzdání emailem. V takovém případě odevzdáváte vždy přímo v příloze zip archiv pojmenovaný alu_{jmeno}_{prijmeni}_{cislo odevzdani}.zip. Odkazy na OneDrive atp. nejsou přípustné, protože jejich obsah lze upravit po odevzdání. Projekt ALU se bez problému vejde přímo do emailu.

Soubory odevzdání

Název souboru	Popis
ALU.circ	Projektový soubor Logisimu obsahující ALU
*.circ	Libovolné další .circ soubory nutné pro funkčnost ALU
OPCODES.txt	Strojově čitelný popis operačních kódů implementovaných v ALU
Dokumentace.xlsx/.ods	Uživatelsky přívětivá dokumentace ALU
README.md	Jakékoliv další připomínky k odevzdání

Warning

Je potřeba dodržet přesné názvy souborů, včetně kapitalizace! ALU budu vyhodnocovat částečně strojově, v případě špatně pojmenovaných souborů nepůjde ohodnotit.

Projekt v Logisimu

Použijte Logisim Evolution 3.9.0
Modul ALU v Logisimu se musí jmenovat ALU. Pokud ho máte jiný, vytvořte správně pojmenovaný modul a překopírujte obsah (Ctrl-A, Ctrl-C, Ctrl-V).
Všechna dvou-vstupová hradla musí mít velikost Narrow, pokud není vyloženě vhodné mít jinou. Doporučuji použít template.
Všechny moduly mají pojmenované všechny vstupy a výstupy vhodným jménem.
Používání třetího stavu (a jej generující komponenty) je obecně zakázáno. U každého použití je nutné odůvodnit (text toolem v logisimu v místě použití), proč je to vhodné místo klasických hradel a že nenastává žádný z problémů obecně spojeným s třetím stavem.
V ALU je dovoleno je používat následující komponenty z knihoven:
- Wiring: Splitter, Pin, Probe, Tunnel, Constant
- Gates: NOT, Buffer, AND, OR, NAND, NOR, XOR, XNOR
Pro postavení modulu ALU by neměly být žádné jiné komponenty potřeba. V případě nejasností se ptejte. Mimo modul ALU můžete použít libovolné komponenty - např. pro testování, ukázku, etc.
V ALU je pouze jedna instance 16-bit sčítačky. Všechny operace, které ji potřebují, se na ní musí vystřídat, ALU provádí pouze jednu operaci zároveň. Použití více sčítaček je penalizováno jako hrubá neefektivita zapojení.

Bonusové operace

Pro implementování bonusových operací jsou tyto restrikce rozvolněné. Např. uvnitř násobičky můžete použít vestavěnou sčítačku, čímž se zásadně zrychlí simulace obvodu. Dokonce to doporučuji. Nemůžete ale např. pro implementaci násobičky použít logisimovou násobičku.

V modulu main, alu_main, alu_showcase nebo podobně bude implementovaná showcase vašeho ALU:
- Je zde položený váš ALU modul
- Všechny vstupy jsou odvozené z komponent, kterým lze jednoduše upravovat hodnota v decimal nebo hexadecimal (např. input pin se správně nastaveným radixem)
- Všechny výstupy jsou napojené na komponenty, na kterých je srozumitelně vidět jejich hodnota (opět decimal nebo hexadecimal) (např. LED, output pin se správně nastaveným radixem)
- Radix (soustava, e.g. decimal nebo hexadecimal) všech vstupů a výstupů je stejný

Příklad showcase

Dokumentace.xlsx

Každý číslicový modul (v praxi se používá zkratka IP znamenající Intellectual Property) musí mít detailní dokumentaci, často jsou to dokumenty o desítkách až stovkách stran.

Interní dokumentace slouží pro zorientování v implementaci modulu a navázání na vývoj po delší době nebo po kolegovi. Tu u ALU vynecháme.

Externí dokumentace dokumentuje interface (vstupy a výstupy) modulu, jeho operační režimy, chování, zakázané kombinace vstupů, případně elektrické vlastnosti. U nás jako 90% externí dokumentace slouží toto zadání - vstupy, výstupy a chování jsou tu přesně popsané. Je ale potřeba zdokumentovat hodnoty vstupu SEL, které jsou plně ve vaší režii.

Pro tento účel jako součást odevzdání ALU vypracujete soubor Dokumentace.xlsx (nebo .ods), ve kterém tohle chování popíšete. Formát a obsah dokumentace není striktně definovaný, ale měl by pro každou implementovanou operaci obsahovat v přehledné podobě alespoň následující informace:

Hodnotu SEL v desítkové soustavě (jako v OPCODES.txt)
Binární rozvoj SEL s obravenými buňkami. Bity uspořádejte tak, že MSB bude vlevo.
ID operace
Mnemoniku krátce vystihující chování operace (příklady máte uvedené ve sloupci Mnemo v tabulkách a v obrázku níže. Není tu správná a špatná odpověď, stačí si vymyslet krátký "assemblerový" způsob, kterým by mohl programátor tuto operaci chtít použít v programu. Důležité je pouze, aby vámi zvolený styl byl konzistentní napříč celou ALU dokumentací)
Stručný slovní popis operace (e.g. Sečte A, B a CIN. Výsledek je OUTP, COUT. Spočítá OVER, ZERO, SIGN.)

Podmíněné formátování

Pro automatické podbarvení buněk s binárním rozvojem můžete použít podmíněné formátování. Na použítých stylech nezáleží, stačí, aby byly odlišné.

Tyto údaje má smysl formátovat do tabulky (proto xlsx), a takové tabulce nesmí chybět hlavička. Obzvlášť u binárního rozvoje je vhodné označít číslo každého bitu, případně MSB a LSB (Most- a Least-Significant-Bit).

Příklad dokumentace:

OPCODES.txt

Soubor OPCODES.txt je strojově čítelnou verzí dokumentace, která slouží pro automatizovaný opravovač, aby věděl, jaké operace jste implementovali a jak je nechat ALU spočítat. Je to CSV bez hlavičky s řádky ve formátu {opcode},{ID}, např.

0,and
1,or
2,not
3,cla
15,mul8

opcode je zde číslo, které se přívádí na vstup SEL, zapsané v desítkové soustavě. "opcode" je zkratka pro operation code, neboli číslo identifikující operaci.

ID je ID operace, jak je uvedené ve sloupci ID v tomto zadání, nebo custom jako označení oprace, která není v zadání (pro vyjímečné případy, kdy chcete naimplementovat nějakou jinou operaci navíc za bonusové body).

Info

V případě použití custom budu danou operaci hodnotit ručně, je tedy potřeba, aby byla detailně popsaná v dokumentaci ALU.

Na pořadí nezáleží, a v souboru nesmí být žádné jiné údaje. Sada popsaných operací musí být konzistentní s dokumentací!

Plagiáty

Všechny projekty v předmětu APS jsou samostatné práce, musí tedy produktem vaší vlastní práce. Je povoleno projekty probírat, konzultovat, nechat si pomoct s řešením problému. Je nepřípustné odevzdávat cizí práci, a to včetně případů, kdy jste obvod podle předlohy zapojili sami.

Ve skriptech a na internetu je dostatek informací pro řešení projektu, je nutné danou problematiku pochopit.

Do výsledného hodnocení se bude vždy započítávat pouze vaše vlastní práce. V případě porušení budou uděleny nevratné záporné body.

Hodnocení

Za ALU, které správně implementuje všechny zadané operace, je možné získat až 20 bodů.

V případě, že povinné ALU je hodnocené 20 body, je možné získat až 6 bonusových bodů za bonusové operace.

Vstupy a výstupy (I/O) ALU

Naše ALU je 16-bitové, to znamená že umí zpracovat data (čísla) o šířce 16 bitů. Z toho vyplývá, že všechny vstupy a výstupy, kterými tečou data (čísla), musí mít 16 bitů.

Název v Logisimu	I/O	Šířka	Popis funkce
`A`, `B`	IN	16	16-bitové vstupy do ALU
`CIN`	IN	1	Vstup carry-in (borrow-in) pro některé ALU operace (+, -, posuny, ...)
`SEL`	IN	4	Vybírá aktuálně prováděnou operaci v ALU
`OUTP`	OUT	16	16-bitový výstup z ALU
`HOUT`	OUT	16	Horní polovina výsledku, pokud je výsledek operace širší než 16 bitů (např. násobení 16bit x 16bit)
`COUT`	OUT	1	Výstup carry-out (borrow-out) pro některé ALU operace (+, -, posuny, ...)
`ZERO`	OUT	1	Indikuje, že `OUTP` je roven `0`
`SIGN`	OUT	1	Indikuje, že `OUTP`, pokud ho interpretujeme ve dvojkovém doplňku, je záporné číslo
`OVER`	OUT	1	V případě, že došlo k součtu, indikuje, že pokud by se operace brala jako ve dvojkovém doplňku, je výsledek nevalidní (nevešel se do reprezentovatelného rozsahu)
`GT`, `LT`, `EQ`	OUT	1	Indikují vztah porovnání mezi `A` a `B` nezávisle na aktuálně vybrané operaci. `GT` se rozumí `A > B`.

Info

Ne všechny I/O musí být nutně přítomné, pouze ty, které jsou potřeba pro nějakou z implementovaných operací. Taky je přípustné mít I/O navíc, které slouží nějaké funkcionalitě nad rámec, nebo bonusovým operacím - v takových situacích bude funkcionalita ověřena ručně.

Important

Vstupy a výstupy musí být pojmenované přesně podle tabulky, jinak jejich hodnota nebude při opravování brána v potaz! Modul ALU se musí jmenovat ALU!

Definovanost výstupů a relevance vstupů

Následující tabulka definuje, které výstupy musí být pro danou operaci smysluplně definované (mít hodnotu podle definice operace) a na kterých vstupech hodnota závisí.

Hint

Jako rule of thumb platí: každý výstup z ALU by měl být vypočten pomocí aktuálně vybrané operace v ALU, nebo být $0$ pokud to nedává smysl.

ID	Inputy	Outputy
`xor`, `or`, `and`	$A, B$	$OUTP$
`not`	$A$	$OUTP$
`shr`, `shl`	$A, CIN$	$OUTP, COUT$
`rotr`, `rotl`	$A$	$OUTP$
`add`	$A, B, CIN$	$OUTP, COUT, OVER$
`sub_half`	$A, B$	$OUTP, OVER$
`sub_full`	$A, B, CIN$	$OUTP, COUT, OVER$
`inc`	$A$	$OUTP, COUT, OVER$
`dec`	$A$	$OUTP, OVER$
`mul8`	$A_{[7:0]}, B_{[7:0]}$	$OUTP$
`mul16`	$A, B$	$HOUT, OUTP$
`swap8`	$A$	$OUTP$
`bsh`	$A, B_{[3:0]}, CIN$	$OUTP$
`bshl`	$A, B_{[3:0]}$	$OUTP$
`bshr`	$A, B_{[3:0]}$	$OUTP$
všechny		$ZERO, SIGN$
binární		$GT, LT, EQ$

Note

V ostatních případech musí hodnota těchto výstupů být $0$ ! Není přípustné, aby na výstupech kdykoliv byl třetí stav, error, nebo náhodná/nerelvantní hodnota.

Operace ALU

Pseudokód

$A \leftarrow B$ značí assignment, tedy že bity z B se použijí pro konstrukci A (výsledku).

${A, B}$ značí konkatenaci, tedy že bity A a B se spojí do širší hodnoty, více důležité bity vlevo. Do takové hodnoty lze i assignovat.

$\forall i$ v tomto kontextu značí "pro všechny $i$ (indexy bitů)", kromě indexů, pro které operaci nelze provést. Typicky 0..15, což jsou indexy bitů 16-bitové hodnoty, kde index $0$ je LSB (Least Significant Bit).

$A_{[7:0]}$ značí slice neboli bitový výběr. V tomto případě vybereme bity 7 až 0, ve výsledné hodnotě budou uspořádané tak, že bit z je nejvíc vlevo (MSB), tedy neměníme pořadí bitů.

Typy operací

Typ	Význam
‼️	Povinné a důležité
❗	Povinné
❓	...za určitých podmínek
🤷‍♂️	Volitelné
🧑‍🎓	Bonusové

Operace po bitech (bitwise)

Typ	ID	Mnemo	Pseudokód	Popis
‼️	`xor`	A XOR B	$\forall i : OUTP_{i} \leftarrow A_{i} \oplus B_{i}$	XOR A a B po bitech
‼️	`or`	A OR B	$\forall i : OUTP_{i} \leftarrow A_{i} + B_{i}$	OR A a B po bitech
‼️	`and`	A AND B	$\forall i : OUTP_{i} \leftarrow A_{i} \cdot B_{i}$	AND A a B po bitech
‼️	`not`	NOT A	$\forall i : OUTP_{i} \leftarrow \overline{A_{i}}$	NOT A po bitech

Více informací na wikipedii: Bitwise operators

Posuny a rotace (shifts and rotations)

Typ	ID	Mnemo	Pseudokód	Popis
‼️	`shr`	SHR A	$\forall i : OUTP_{i} \leftarrow A_{i + 1}$ $OUTP_{15} \leftarrow CIN$ $COUT \leftarrow A_{0}$	Logický posun doprava
‼️	`shl`	SHL A	$\forall i : OUTP_{i} \leftarrow A_{i - 1}$ $OUTP_{0} \leftarrow CIN$ $COUT \leftarrow A_{15}$	Logický posun doleva
‼️	`rotr`	ROTR A	$\forall i : OUTP_{i} \leftarrow A_{i + 1}$ $OUTP_{15} \leftarrow A_{0}$	Rotace doprava
‼️	`rotl`	ROTL A	$\forall i : OUTP_{i} \leftarrow A_{i - 1}$ $OUTP_{0} \leftarrow A_{15}$	Rotace doleva

Tip

Pomocí logických posunů (a správného použití carry) lze rychle provést dělení a násobení dvěma, a to jak u čísel bez znaménka, tak u čísel v doplňkovém kódu.

Shifty

Info

Takto naspecifikovaný logický posun se někdy nazývá rotace skrz carry.

Shift left (rotate left through carry)

Shift right (rotate right through carry)

Více informací na wikipedii: Rotate through carry

Rotace

Rotate left

Rotate right

Vice informací na wikipedii: Rotate

Sčítání a odčítání

Typ	ID	Mnemo	Pseudokód	Popis
‼️	`add`	A ADD B	${COUT, OUTP}$ $\leftarrow A + B + CIN$	Součet respektující carry
‼️ ❓	`sub_half`	A SUB B	$OUTP \leftarrow A - B$	Rozdíl bez borrow
‼️ ❓	`sub_full`	A SUB B	${COUT, OUTP}$ $\leftarrow A - B - CIN$	Rozdíl respektující borrow
❗	`inc`	INC A	${COUT, OUTP}$ $\leftarrow A + 1$	Zvětšení A o 1
❗	`dec`	DEC A	$OUTP \leftarrow A - 1$	Změnšení A o 1

Info

Z operací sub_half a sub_full stačí implementovat pouze jednu. V případě volby sub_half bude pomocí ALU obtížné odečítat větší než 16bit hodnoty.

Warning

Operace inc a dec neberou v potaz hodnotu CIN a provádějí vždy úpravu o 1!

Operace inc musí správně vygenerovat COUT!

Operace dec nemusí správně vygenerovat COUT (netestuje se).

Operace add, sub_half, sub_full, inc, dec musí generovat OVER, pro případ, že jim programátor dal čísla se znaménkem.

Jedna sčítačka

Pro implementaci všech 4 "sčítacích" operací je potřeba použít pouze jedinou sčítačku. Protože ALU vždy vykonává pouze jednu vybranou operaci, jedna instance sčítačky stačí, a jednolivé operace se na ní musí "vystřídat".

Více informací v kapitolách o sčítání a odčítání.

Bonusové

Info

Pro všechny bonusové operace platí, že můžete používat libovolné komponenty, kromě těch, které přímo implementují danou operaci.

Např. v mul můžete použít jakoukoliv sčítačku, ale ne (vestavěnou) násobičku. V cla nesmíte použít vestavěnout sčítačku. V barrel shifteru nesmíte použít jakýkoliv vestavěný shifter. etc.

Typ	ID	Mnemo	Pseudokód	Popis
🧑‍🎓	`mul16`	A MUL B	${HOUT, OUTP}$ $\leftarrow A * B$	16bit násobení A a B
🧑‍🎓 ❓	`mul8`	AL MUL BL	$OUTP$ $\leftarrow A_{[7:0]} * B_{[7:0]}$	8bit násobení spodních polovin A a B
❗ ❓	`swap8`	SWAP8 A	${A_{[15:8]}, A_{[7:0]}}$ $\leftarrow {A_{[7:0]}, A_{[15:8]}}$	Výměna horního a spodního bytu A
🧑‍🎓	`mul16k`	A MUL B	viz `mul16`	16b násobení pomocí Karatsubova alg.
🧑‍🎓	`cla`	A ADD B	viz `add`	Použijte místo `add` pokud jste implementovali CLA.
🧑‍🎓	`bsh`	A SHC B	$i f CIN$ $A \leftarrow A << B_{[3:0]}$ $e l se$ $A \leftarrow A >> B_{[3:0]}$	Posun A o B doleva/doprava
🧑‍🎓 ❓	`bshl`	A SHL B	$A \leftarrow A << B_{[3:0]}$	Posun A o B doleva
🧑‍🎓 ❓	`bshr`	A SHR B	$A \leftarrow A >> B_{[3:0]}$	Posun A o B doprava
🧑‍🎓	`bcd`	BCD A	-	převod A na BCD

Násobení (~2b)

Stačí implementovat násobičku kladných čísel podle naivního násobení pod sebou. Za pokročilejší řešení (násobení čísel ve dvojkovém doplňku, efektivnější násobička jako Dadda nebo Wallace multiplier) získáte větší počet bodů (indikujte v README).

Varianty

Pro splnění násobení je potřeba implementovat buď mul16 (velká operace), nebo mul8+swap8 (menší operace + pomocná operace). V obou případech bude možné násobit libovolně velké čísla v softwaru pomocí částečných násobků.

Doporučuji variantu mul8+swap8, protože bude v obvodu mnohem méně hradel, což urychlí simulaci.

V případě implementace barrel shifteru lze operaci swap8 vynechat, protože jí lze nahradit pomocí série operací bshl, bshr, or.

Alternativně lze za více bodů rozšířit mul8 na mul16 pomocí Karatsubova algoritmu (viz níže).

Doporučení

Používejte během stavění moduly, pokud potřebujete opakovat nějakou část obvodu.

Karatsubovo efektivní násobení (~1b navíc k násobení)

Alternativní způsob implementace 16bit násobení, pokud už máte postavenou 8bit násobičku.

Standardně je pro implementaci 16bit násobení potřeba provést čtyři 8bit násobky (AL*BL, AL*BH, AH*BL, AH*BH) a posčítat správně výsledky. To odpovídá klasickému "naivnímu" školnímu násobení pod sebou.

Ovšem Anatolij Alexejevič Karacuba (anglicky Karatsuba) v roce 1962 publikoval algoritmus, pomocí kterého lze 16bit násobení provést pouze pomocí tří 8bit násobků, za cenu několika sčítání navíc.

Tento Karatsubův algoritmus se hodí primárně pro urychlení velkých násobků v softwarových rutinách, kde máme od hardwaru k dispozici pouze 8b/16/32b násobení. Počet hardwarových násobení, které je potřeba provést pro vypočtení nbit x nbit násobku je $O (n^{l o g_{2} 3}) \approx O (n^{1.58})$ , což je podstatný rozdíl oproti naivnímu násobení pod sebou, kde je to $O (n^{2})$ .

Pro implementaci v HW se hodí spíše násobičky založené na efektivnější redukci součtů (Dadda, Wallace), nicméně pro porozumění algoritmu poslouží i jeho implementace v HW.

Zadání

Buď:

implementujte 8bit násbičku klasicky, nebo
implementujte 4bit násobičku klasicky, a pomocí tří jejich instancí dle Karatsubova algoritmu zapojte 8bit násobičku.

Poté, pomocí tří 8bit násobiček dle Karatsubova algoritmu zapojte 16bit násobičku. Touto násobičkou implementujte operaci mul16, ale označte ji v OPCODES.txt jako mul16k.

Sčítačka s predikcí přenosů (CLA) (~2b)

Neboli Carry Lookahead Adder (CLA). Klasický postup sčítání zprava doleva (Ripple-carry adder) je pomalý. Analýzou vztahu carry-in jednotlivých full-adderů ke vstupům lze zjistit, že každý carry-in/out lze předpovědět přímo ze předchozích vstupů vypočtením několika násobků, které se sečtou. Tedy čas pro výpočet bude vždy pouze daný pouze rychlostí vícevstupového AND (kterých se provede několik paralelně) a následného vícevstupového OR. Při implementaci v tranzistorech je vícevstupový AND/OR rychlejší, než řetězec hradel XOR+OR, který najdeme v klasickém ripple-carry adderu (RCA).

Získáváme tedy recept na to, jak postavit sčítačku, kde rychlost výpočtu výsledku je kvazi-konstantní vůči šířce sčítačky, ovšem za cenu velkého nárůstu hradel (pro každý full-adder musíme přidat několik širokých AND a jeden široký OR). Velikost prediktoru roste s tím, jak daleko dopředu predikci provádíme. Má tedy smysl udělat určitý trade-off, a predikci někde uříznout. Např. postavit 4b adder s predikcí (velmi rychlý), a ten 4x zřetězit na 16b adder.

Více informací na wikipedii: Carry lookahead adder

Ovšem i po zřetězení 4x 4bit-CLA za sebe není potřeba čekat na ripple-carry propagaci zkrz tyto CLA. Lze použít stejný princip jako předtím, a každý ze čtyř COUT předpovědět ze vstupů ( $P$ a $G$ každého CLA lze vypočítat z $P$ a $G$ full-adderů uvnitř). Jednotce, která toto zaopatřuje se říká Lookahead carry unit (LCU), a je to dobře studovaný obvod.

Více informací na wikipedii: Lookahead carry unit

Varianty

4bit-CLA, 4x zřetězeno - 1b
8bit-CLA, 2x zřetězeno - 2b (relativně velký obvod)
4bit-CLA + LCU - 2b
jiná varianta - dle domluvy

Řešení

Modifikujte svojí existující sčítačku, nevkládejte do ALU další. V OPCODES.txt indikujte místo add operaci cla.

Do full-adderu přidejte výstupy $P$ , $G$ . Pro přehlednost umístěte prediktor do samostatného modulu, který bude brát na vstupu všechny $P_{i}$ , $G_{i}$ , a CIN a na výstupu n-bitový COUT (nebo n-krát $CO U T_{i}$ ).

Pozor

V prediktoru se nesmí vyskytovat řetězec z CIN na nejvyšší COUT, to by mělo stejnou rychlost jako RCA. Je potřeba výraz pro predikci každého bitu plně vyexpandovat a vyjádřit jako součet násobků / sum of products (SOP) / disjunktivní normální formu (DNF), a zapojit pomocí vícevstupových hradel.

Logický posun A doprava/doleva o B míst (Barrel shifter) (~2b)

Pro implementaci posunu o libovolný počet míst se nabízí několik variant, nejefektivnější z hlediska využití tranzistorů je tzv. cross-bar shifter. Nicméně používá třetí stav (controlled buffery nebo na úrovni tranzistorů transmission gates), a proto není vhodný pro implementaci na FPGA, které třetí stav nepodporují.

Princip spočívá v rozložení velikosti posunu na součet mocnin dvou (to je jeho binární reprezentace, tu už máme!), a postupného provedení posunu o každou složku součtu zvlášť. Např. posun o 10 provedeme posunem o 8 a o 2 (posun o 4 a o 1 neprovedeme). Provedení/neprovedení posunu se dá přepínat multiplexorem.

Přehledný diagram implementace tohoto postupu se poměrně špatně hledá, proto ho uvádím zde:

Barrel Shifter pomocí $lo g_{2} n$ multiplexorů (zdroj)

Pro plný počet bodů je potřeba implementovat shift doleva i doprava, v jedné ze dvou variant:

Varianty

bsh - posun doleva pokud $CIN = 1$ , jinak posun doprava
bshl+bshr - posun každým směrem jako zvlášť operace ALU (vhodné pokud vám zbývá dost volných hodnot selectoru)

Info

Není potřeba řešit CIN a COUT jako u shl/shr.

Posun u 16bit hodnot dává smysl provádět o 0-15 míst, posun o více má za výsledek vždy 0. Vaše operace nemusí správně řešit větší hodnoty posunu než 15, stačí tedy brát v potaz pouze spodní 4 bity B.

Konverze z binárky na BCD (~2b)

Implementujte v ALU modul, který převede hodnoty 0-9999 na vstupu A na čtyřmístnou reprezentaci čísla v Binary Coded Decimal (BCD). Tato reprezentace je vhodná pro e.g. zobrazování hodnot v desítkové soustavě na 7-segmentovém displeji. Toto zobrazování budete mít následně jednodušší implementovat jako output v CPU, címž si zajistíte nějaké body za CPU IO.

Tedy $OUTP_{[3:0]}$ bude obsahovat jednotky, $OUTP_{[7:4]}$ desítky, $OUTP_{[11:8]}$ stovky a $OUTP_{[15:12]}$ tisíce hodnoty na vstupu $A$ interpretované v desítkové soustavě. Čísla na vstupu větší než 9999 nemusíte řešit. Takové čísla se vejdou do 14 bitů, takže stačí pracovat s těmito spodními bity vstupu.

Algoritmus, kterým se tento převod dá efektivně (bez dělení a modula!) provést, se jmenuje Double-Dabble. Dá se implementovat jak v SW (opakovanou aplikací porovnání a přičtení), tak v HW (zařazením za sebe tolik modulů provádějících porovnání+přičtení tak, aby se každému bitu stalo to samé, co v SW rutině). Příklad implementace v HW (pro větší hodnoty než máte zadáno) je na konci článku o Double-Dabble.

Efektivní zapojení

"Double" v algoritmu je pouze logický posun doleva, ten lze realizovat jednoduše úpravou zapojení vodičů do další fáze (je zdarma).

V jádrové operaci algoritmu "porovnání a podmíněné přičtení" se porovnává s konstantou (>4), a přičítá konstanta (+3). Obvody pro provedení těchto operací jdou oproti obecnému porovnání a sčítání dramaticky zjednodušit:

Buď, jako jsme delali při úpravě výrazů v Booleově algebře (konstantní jedničky a nuly ve výrazu vždy lze nějak zjednodušit) - rozkreslit si 4b komparátor a 4b sčítačku s těmito konstantami na vstupu a zjednodušovat pomocí booleovy algebry (zapisovat hodnoty konstantních vodičů a škrtat nepotřebná hradla). Samotné rozhodnutí lze vyřešit malým multiplexorem.
Přistupovat k modulu jako funkci o 4 vstupech a 4 výstupech, jejíž pravdivostní tabulku známe, testy sestavit vzorce pro každý z výstupů lze jednoduše pomocí Karnaughovy mapy.

Pouze řešení s efektivním komparátorem a zvětšovačkou bude hodnoceno plným počtem bodů.

Paměti - Sekvenční obvody

Původní verze lekce

memory_blank.circ

Kombinační obvody

Kombinační obvody lze ekvivalentně zadefinovat několika způsoby:

Hodnoty výstupů jsou plně definované pouze hodnotami vstupů
Obvod implementuje matematickou funkci, tj. lze popsat pravdivostní tabulkou
V obvodu se nevyskytují žádné cykly (nepřímá závislost závislost vstupu hradla na jeho výstupu)

Příklad kombinačního obvodu

Kombinační obvod

Sekvenční obvody

Sekvenční obvody jsou ty obvody, které nejsou kombinační, tj. vyskutyjí se v nich nějaké cykly. Tyto cykly způsobují zajímavé chování (paměť), ale jsou obtížnější analyzovat.

Příkladný sekvenční obvod s OR

Sekvenční obvod

Znázornění v pravdivostní tabulce

Protože X je zároveň výstup a vstup do obvodu, musíme tyto dvě jeho funkce rozdělit:

$X$ - aktuální hodnota vodiče X, tj. vstup
$X^{'}$ - příští hodnota vodiče X, tj. výstup.

"Příští" tady znamená, jakmile dané hradlo zpracuje své vstupy a aktualizuje svůj výstup - jeho tzv. propagační delay, který je vždy nenulový, závislý na výrobním procesu (typická hodnota např. 10ns). Tedy je to hodnota X v budoucnosti.

Nyní v pravdivostní tabulce můžeme popsat, jaké bude příští X $X^{'}$ v závislosti na aktuálním X $X$ a vstupu $A$ :

A	X	X'
0	0	0
0	1	1
1	0	1
1	1	1

Z chování obvodu vidíme, že pokud je $A = 0$ , $X$ se nezmění ( $X^{'} = X$ ), a pokud $A = 1$ , pak na $X$ nezáleží a $X^{'} = 1$ . Můžeme tedy pravdivostní tabulku zjednodušit zavedením neznámé $S$ :

A	X	X'
0	S	S
1	S	1

V této tabulce může S nabýt libovolných hodnot ( $0$ nebo $1$ ) a každá varianta repreznetuje jeden řádek. Nicméně z takto zjednodušené tabulky je lépe vidět časové chování obvodu:

Pokud se obvod nachází v nějakém "stavu" $S$ , tak při $A = 0$ v něm zůstane, ale při $A = 1$ přejde do stavu $S = 1$ .

Zároveň platí, že abychom mohli znát hodnotu výstupu, musíme znát hodnotu aktuálního stavu $S$ , který může být skrytý uvnitř obvodu, nestačí nám pouze vstup $A$ - typická vlastnost sekvenčních obvodů.

Popis výrazem a nekonečné vyhodnocování

Obvod můžeme popsat i výrazem:

$X^{'} = X + A$

kde $X^{'}$ značí příští hodnotu a $X$ tu stávající. Pokud nám ale vyjde jiné $X^{'}$ , než jsem měli $X$ , obvod na něj okamžitě zareaguje (je to vstup) a spustí výpočet znovu po dosazení $X^{'}$ za $X$ , tedy potenciálně je nutné popsat obvod takto:

$X^{'} = (X + A) + A = X + A$

Zde vidíme, že výraz se po opakovaném (klidně i nekonečném) dosazování $X^{'}$ za $X$ nemění. Z toho lze odvodit, že je garantovaně stabilní. Nemusí tomu tak být vždy

Nestabilní obvody

Nejjednodušší nestabilní obvod je následující obvod o nula vstupech:

Tento obvod můžeme zase modelovat pomocí výrazu:

$X^{'} = \overline{X}$

Pokud ale budeme opakovaně dosazovat, nedostaneme ten samý výraz. Označme $X_{0}$ (neznámý) počáteční stav $X$ , a $X_{i}$ stav po $i$ dosazeních (neboli po $i$ provedeních obvodu). Každý stav se vypočítává z toho předchozího.

$X_{1} = \overline{X_{0}}$ $X_{2} = \overline{X_{1}} = \overline{\overline{X_{0}}} = X_{0}$ $X_{3} = \overline{X_{2}} = \overline{X_{0}}$ $X_{4} = \overline{X_{3}} = X_{0}$

Můžeme tedy říct, že protože $X_{4} \neq = X_{3}$ a obecně $X_{i + 1} \neq = X_{i}$ , stav obvodu se po každém provedení hradla změní, a tedy není stabilní, nikdy se neustálí na jednu stálou hodnotu, neboli osciluje. Skutečně, potvrdí nám to i simulace Logisimem:

SR Latch

Sekvenční obvody můžete využít pro paměť pomocí hradla OR. Hradlo OR nám vstup zapne a nechá výstup neustále zapnutý, ale nemáme ho zatím jak vyresetovat.

Sekvenční obvod

Abychom ho mohli vyresetovat, přidáme další vstup a to R jako reset.

SR Latch

Zapíšeme do výrazu

$Q = S + B = S + (Q \cdot \overline{R})$

Zapíšeme chování do pravdivostní tabulky

R	S	Q	Q'
0	0	Q	Q
0	1	X	1
1	0	X	0
1	1	X	1

Vytvořili jsme SR Latch, který se ale dá optimalizovat, tak abychom potřebovali 2 stejné gaty a to NOR viz. gif.

SR Latch

Latch vs Flip Flop

Signály

Stavy signálů

Na následujícím obrázku vidíme 4 definice.

High Level (Active-High) - zde probíhá ukládání
Low Level (Active-Low) - značí se jako CLK nebo ENA
Rising/Falling edge hodnota se zpracuje v okamžíku přechodu CLK signálu z high na low a opačně

Latch

Latch je level-triggered. To znamená, že latch bere vstup, když je zapnutý viz. obrázek

Latch

Flip Flop

Flip flop je edge-triggered. To znamená, že buď bere vstup na rising edge nebo falling edge. Na následujícím obrázku bere vstup na rising edge.

Flip Flop

Oscillation apparent

V rámci sekvenčních obvodů můžete narazit na chybu Oscillation apparent. Znamená to, že jste v nějakém paradoxním cyklu. Vyřešíte to následovně:

Odstraníme problémový prvek
Reset Simulation (CTRL+R)
Pokud není zapnuté tak --> Auto-Propagate (CTRL+E)

Bonusové materiály

Latch vs Flip Flop - https://www.youtube.com/watch?v=LTtuYeSmJ2g
Latch a Flip Flop na wikipedii
- Anglicky (víc informací) - https://en.wikipedia.org/wiki/Flip-flop_(electronics)
- Česky - https://cs.wikipedia.org/wiki/Bistabiln%C3%AD_klopn%C3%BD_obvod

Paměti - Asynchronní obvody

Původní verze lekce

Asynchronní obvody fungují bez clocku, takže jakmile je na vstupu hodnota, zpracuje se.

SR (Set-Reset) latch

SR latch jde vytvořit mnoho způsoby, nejčastější jsou SR NOR latch a SR NAND latch

Obrázek SR NOR latch

SR NOR latch

Obrázek SR NAND latch

SR NAND latch

Pravdivostní tabulka

S	R	Q'	Poznámka
0	0	Q	Beze změny
0	1	0	Reset
1	0	1	Set
1	1	?	Set+Reset

Jaké jsou rozdíly mezi SR NAND a SR NOR? (3)

Výstup při set+reset je u NAND 1, u NOR 0
Vstupy set a reset mají u NAND invertovanou logiku
U NAND SR je kladný výstup u hradla se set vstupem, u NOR SR je to opačně

JK latch

JK latch se primárně používá na toggle.

Pravdivostní tabulka JK latch

J	K	Q'	Poznámka
0	0	Q	Beze změny
0	1	0	Reset
1	0	1	Set
1	1	Q	Toggle

Gated D (data) latch

Gatování - možnost vypnout či zapnout prvek, pomocí vstupu (typicky ENABLE).

D latch využívá vstup enable jako 2 vstup. Tvořící sérii pravidel.

E	D	$Q^{'}$	$\overline{Q^{'}}$	Poznámka
0	-	Q	$\overline{Q}$	Beze změny
1	0	0	1	Zápis 0 (reset)
1	1	1	0	Zápis 1 (set)

Diagram

Gated D latch

Paměti - Synchronní obvody

Původní verze lekce viz asynchronní obvody

Synchronní obvody

Jsou ovládané extra clockem (CLK), který určuje kdy obvod pracuje. Příkladné obvody jsou:

SR-flip-flop
T-flip-flop
D-flip-flop

V následující kapitole se podíváme na D-flip-flop, jelikož je nejzajímavější.

Jak synchronizovat obvod? (Rising/Falling edge detektor)

Vytvoření Rising/Falling edge detektoru viz. obrázek

Rising edge detektor (pomocí NOT delaye)

U falling edge detektoru jen prohodíme NAND gatu za AND gatu.

D (Data) Flip Flop

Pravdivostní tabulka

Clock	D	$Q_{n e x t}$
`Rising edge`	0	0
`Rising edge`	1	1
`Non-rising`	X	Q

D flip-flop jde vytvořit mnoha způsoby. Ukážeme si dva, a to klasickou variantu a master-slave variantu.

Master-slave D-flipflop

Vytvoříme ho pomocí 2 Gated D-latch. Pozor, aktivuje se na Falling edge.

Negative edge triggered master slave D flip-flop

Varianta pro Rising edge.

D-Type Flip-flop Diagram

Optimalizovaná varianta

Můžeme vystavět pomocí 6 NAND gate.

Edge triggered D flip flop

Můžeme přidat 2 vstupy pro asynchronní set a reset. Stačí jenom NAND gaty vyměnit za 3-vstupové.

Edge triggered D flip flop with set and reset

Registr

Pokud chceme ukládat vícebitové hodnoty, stačí položit několik D-flip-flopů vedle sebe:

alt text

Shift Register

Shift register je užitečná varianta registru. Je tvořen z několika D flip-flopů zapojených v zřetězení do sebe. Při každém clocku se hodnoty v shift registru posunou o jednu pozici po směru toku dat. To umožňuje shift registr naplnit v čase za sebou přicházejícími 1bit hodnotami a následně pracovat s celou hodnotou.

4 Bit Shift Register

Bonusové materiály

Shift register anglická wikipedie - https://en.wikipedia.org/wiki/Shift_register
Flip-flopy a latche - https://en.wikipedia.org/wiki/Flip-flop_(electronics)

CPU - Úvod

CPU neboli Central Processing Unit je užitečný pro jakýkoliv logický problém. Zvládne využívat tupé jednotky vašeho počítače a rozhoduje, co mají dělat...

Legenda k obrázku:

červená - control flow
černá - data flow

CPU se typicky skládá z:

Control Unit (CU) - rozřazuje instrukce
Registry - často velmi rychlé paměti CPU
Kombinační logika - obecné kombinační obvody, zde patří například vaše ALU
Main Memory - typicky RAM nebo ROM
Input/Output - vstupy výstupy vašeho CPU

Sběrnice (bus)

Sběrnice typicky přenáší informace mezi komponenty ve vašem CPU. Nejlíp se to vysvětlí na datové sběrnici, která přenáší různá data mezi registry, output z ALU apod.

Typicky během instrukce pošlete nějakou hodnotu na sběrnici. Takže například chcete přesunout hodnotu registru B do registru C, tak vyšlete hodnotu registru B na sběrnici (enable) a nastavíte hodnotu registru C na hodnotu sběrnice (set).

Typy:

adresová/address - typicky pro adresy v paměti
datová/data - pro vysílaná data
řídící/control - kominukaci mezi komponenty

CPU - Návrh

Průvodce návrhem CPU.

Architektura

Harvardská - oddělená paměť programu (ROM) a paměť dat (RAM)

Von Neumannova - sjednocená paměť (RAM)

Náčrt

Doporučuji si načrtnout návrh vašeho CPU a podle toho se rozhodovat. Důležitý bod u vašeho návrhu CPU je kolika bitové jste dělali ALU. Pokud máte 8 bitové ALU, tak nemůžete mít 16 bitovou sběrnici (pokud něco nevyčarujete, možné je všechno...).

Navrhované šířky/počty

Šířka adress v ROM
Šířka hodnot v ROM
Šířka adress v RAM
Šířka hodnot v RAM
Šířka instrukcí
Počet registrů
Šířka sběrnice

I/O (Vstup/Výstup)

Alespoň jeden vstup a výstup

Příkladné vstupy

klávesnice (Input/Output/Keyboard)
registr (Memory/Register)

Příkladné výstupy

Řada ledek (Input/Output/LED)
HEX displej (Input/Output/Hex Digit Display)
TTY (Input/Output/TTY)
LED Matrix (Input/Output/LED Matrix)

Instrukce

Vaše CPU by mělo mít několik vlastností:

možnost spočítat libovolný početní problém
libovolně pracovat s registry a pamětí

Zkráceně by mělo být, co nejvíce univerzální... Tohle je dobré mít v hlavě při návrhu instrukcí.

Instrukci si můžete rozčlenit jakkoliv chcete. U mého CPU jsem měl pouze OP code a ARGy, ale můžete do instrukce schovat různé flagy apod... (technicky vzato jsou to taky argumenty, ale pouze jednobitové :D)

V excelu pak vypadají instrukce nějak takhle

Doporučené konvence

{X} - libovolný registr X
[X] - hodnota na adrese X

Doporučuji navrhnout v excelu nebo google sheets. Tabulka s jménem instrukce, krátky popis a její kód.

Typické instrukce jsou:

mov {R1} {R2} - přesune hodnotu registru z R1 do R2
movi {R1} 8b - přesune hodnotu v instrukci do R1
add {R1} {R2} - sečte R1 R2
jmp {X} - skočí na instrukci {X} v programu
...

Průběh exekuce instrukce

Fetch
- Načti hodnotu z instrukční paměti na adrese PC (Program Counter) do IR (Instruction Register)
- Přičti k PC jedna
Decode instruction
- Přečti IR, rozhodni se, zda potřebuješ další bity k instrukci
- Pokud ano, opakuj fetch, ale výsledek ulož do argument registrů,...
Execute instruction
- Podle toho, co je v IR, tak se zachovej

Vyžadované instrukce

Aritmetické

Instrukce, které se zabývají počty. Typicky vše co umí vaše ALU.

Příklady:

add A,B - přičti fixní registry A a B a výsledek ulož do A
sub {R1},{R2} - odečti libovolné dva registry a výsledek ulož do R1
shr {R1} - Proveď SHR operaci na libovolný registr R1 a výsledek ulož do R1

Paměťové

Přesuny mezi registry (kromě interních jako např. program counter)
Immediate data instrukce - instrukce, která vám dovolí nahrát libovolné číslo do registru
- movi {R1} {8b number} - nahraje do libovolného registru R1 8 bitové číslo
Práce s RAM - primárně načítání a ukládání z RAM
- load {R1} - načtení hodnoty z adresy HL (dva fixní registry pro adresu RAMky) do libovolného registru R1
- store {R1} - uložení hodnoty z libovolného registru R1 do adresy HL

Control Flow

Jumpy v programu - rozdělují se na podmíněné a nepodmíněné

Nepodmíněné:

jmp {X} - jump na určitou instrukci
jmpr {X} - jump na instrukci o X instrukcí dopředu či dozadu

Podmíněné:

jmpz {X} - skoč na X instrukci pokud je flaga ZERO rovná jedné
jumpr {X} - to stejné ale relativní jump
jmpc {X} - skoč na X instrukci pokud je flaga CARRY rovná jedné

Ostatní

Typicky I/O
led - toggle na LEDku

CPU - Stavba

Doporučuji si CPU rozdělit na 5 částí:

Registry - vnitřní paměti CPU
CU (Control Unit) - něco co vaši instrukci přijme a podle toho vykoná kroky
Control room - debug část pro čtení obsahů registrů a podobných věcí
Input/Output - vstupy,výstupy...
Paměť (RAM/ROM) - v harvardské architektuře typicky ROM pro program a RAM pro data, ve Von Neumannově architektuře pouze RAM

Hrdinské komponenty pro vaše CPU

Gates/Controlled Buffer - rozhoduje jestli pouštíte proud nebo ne, v parametrech navolíte pouze vstupní a výstupní Data Bits
Wiring/Tunnel - komponenta pro přehlednost, vytvoříte n komponent se stejným labelem (Label) a bude vám přenášet vstup bez nutných kabelů přes celou plochu
Wiring/Probe - debug věc, pro zjištění hodnoty na kabelu...
Memory/Register - nejpoužívanější paměťová buňka

Stepper

Stepper vám "stepuje" (krokuje) vaše instrukce. Jelikož některé instrukce zaberou více cyklů...

Jedná se o jednoduchý n-bitový counter s n-bitovým decoderem. Se vstupem CLK (Clock) a RST (Reset) a n-výstupy.

2 bitový stepper vypadá následovně:

Registry

Ovládání registru může vypadat následovně

Velmi doporučuji použití tunelů (Wiring/Tunnel) a vytvořit konvence jako například <registr>_set apod..

Ovládání pro register A:

a_set - 1, když setujeme register A
a_ena - 1, když pouštíme register A na sběrnici
rst - 1, když chceme provést reset registrů

Program Counter (PC)

Program counter je komponenta CPU, která vám říká, na jakém řádku programu (instrukce) se nacházíte. Potřebujete pro něj 2 věci:

zvětšit o 1
změnit hodnotu pro jmp

Na obrázku jsou piny na ovládání, to je jen pro testování.

CPU - Programování

Od assembly k operačním systémům

Alexandr Pleskot (4.K 2024/25) ve spolupráci s Danem Bulantem v rámci svého maturitního projektu vypracoval článek, který pojednává o assembly, vztahu k C a operačnímu systému. Je to hezký úvod do programování v assembly, a následně přehled o tom, co je potřeba, aby na procesoru mohl bežet operační systém, což už je mimo obsah tohoto předmětu (my se spokojíme s tzv. "baremetal" mikrokontrolerem).

Od assembly k operačním systémům

Customasm

Velmi zkrácená dokumentace pro customasm...

Pro vaše CPU budete muset vytvořit example program. Velmi doporučuji webovou aplikaci customasm

git - https://github.com/hlorenzi/customasm
web - https://hlorenzi.github.io/customasm/web/
wiki - https://github.com/hlorenzi/customasm/wiki

Jelikož má customasm svou vlastní dokumentaci, tak tuhle část projdu velmi zkráceně...

Subruledef

První si nadefinujeme podpravidla (typy) jako například registry apod.

#subruledef register
{
    A => 0x0
    B => 0x1
    C => 0x2
    D => 0x3
}

Ruledef (instrukce)

Zde nadefinujeme instrukce, viz. příkladná mv instrukce. Dejme tomu, že opcode pro mov instrukci je 1001 a šířka instrukcí je 16 bitů.

#ruledef
{
    mv {src: register},{dst: register} => 0b1001 @ src`4 @ dst`4 @ 0x0
}

mv - název instrukce
{src: register} - název parametru a typ, zde typ definovaný v subruledef register
, - separátor
{dst: register} - druhý argument dst
=> - operátor přepiš jako
0b1001 - 0b znamená zapsáno v bitech a 1001 je opcode instrukce
@ - používá se jako separátor
src`4 - argument src zakóduj jako 4 bitový
dst`4 - stejné
0x0 - 0x hexdecimální zápis čísla 0, pro doplnění do 16 bitů (naše šířka instrukce)

Dobré podotknout, že jako typ zde používám pouze register, ale velmi často použijete i další typy a to:

uXX - unsigned hodnoty
sXX - signed hodnoty
iXX - signed nebo unsigned hodnoty

Programování

Typicky začnete program s start. Velmi doporučuji psát komentáře pomocí ;

start:
    ; přesune hodnotu z registru C do registru D
    mv C,D

Celý example vypadá takhle:

#subruledef register
{
    A => 0x0
    B => 0x1
    C => 0x2
    D => 0x3
}

#ruledef
{
    mv {src: register},{dst: register} => 0b1001 @ src`4 @ dst`4 @ 0x0
}

start:
    ; přesune hodnotu z registru C do registru D
    mv C,D

Export do logisimu

Output Format: LogiSim 8-bit nebo Output Format: LogiSim 16-bit podle šířky paměti
Assemble (Ctrl+Enter) >>
Zkopírujte výstup a uložte do .txt souboru
Klikněte na vaši Memory/ROM komponentu v logisimu
Klikněte u vlastnosti Contents na (click to edit)
Open a vyberte soubor, kde jste si uložili výstup customasm

Markdown

Tyto skripta se kompilují pomocí mdbook, je tedy možné používat všechny tímto programem podporované konstrukce.

Časem je cílem podorovat i build do pdf, což nejspíš omezí některé syntaxe, aby mohl proběhnout build do html i do pdf ze stejného zdrojového kódu.

Navíc jsou do mdbook nainstalované preprocessory, které umožňují používat další druhy syntaxe. Preprocesory jsou uvedeny cca v pořadí, ve kterém se spoštějí:

checklist 📘

Umožňuje vložit do markdownu inline TODO, ze kterých se udělá globální seznam ve speciální kapitole, s odkazy.

Příklad

{{#check Note-1 | This is an important note}}

tera 📘

Nahrazuje template výrazy tera v markdownu podle contextu v src/context.toml. Tohle je nejjednodušší způsob, jak zadefinovat a recyklovat řetězce napříč celými skripty.

Příklad

This string is from the context.toml file

Autoři těchto skript jsou jaywor1, Michal Vojáček.

Číslo	Autor
1	jaywor1
2	Michal Vojáček
end	end

cmdrun 📘

Umožňuje do skript přidat výstup libovolného unix příkazu, což je užitečné např. pro generování výstupů z logisimu, nebo buildování latexu.

Přichází s tím samozřejmě určitý risk, proto doporučuji provozovat mdbook builder v dockeru. Všechny použití tohoto preprocesoru lze najít pomocí:

grep -roP '\<\!\-\- cmdrun\K.+(?=\-\-\>)' --exclude-dir book .

Příklad

Jako příklad seznam všech použití toho preprocesoru ve skriptech (příkaz výše):

./src/99_ostatni/markdown.md: cd ../.. && grep --color=no -roP '\<\!\-\- cmdrun\K.+(?=\-\-\>)' --exclude-dir book .

katex 📘

Umožňuje použití $ a $$ pro psaní matematických výrazů.

Příklad

$\nabla f (x) \in R^{n}$

image-size 📘

Markdown neumožňuje specifikaci velikosti a centrování obrázků, tento preprocesor tuto funkcionalitu přidává.

Do budoucna chci projekt upravit a rozvolnit syntaxi, aby šlo specifikovat pouze zarovnání, bez šířky.
TODO: image-size-fork

Příklad

admonish 📘

Umožňuje vytvářet HTML "bannery", které volitelně můžou být rozbalovací.

Vyvolává se pomocí ```admonish info title="Title",collapsible=true, kde místo info můžou být následující vestavěné styly:

Příklad

note

Takhle vypadá rozbalovací sekce.

abstract, summary, tldr

info, todo

tip, hint, important

success, check, done

question, help, faq

warning, caution, attention

failure, fail, missing

danger, error

bug

example

quote, cite

quiz

TODO

kroki

TODO

emojicodes 📘

Umožňuje vkládat do textu emoji pomocí Github shortcode ohraničeného ::

Kompletní seznam shortcodes

Příklad

👨‍❤️‍👨 👩‍❤️‍👩 ✅ 🏳️‍🌈 🏳️‍⚧️

embedify

TODO

footnote

TODO

pagetoc 📘

Přidává na generovanou stránku vpravo sidebar s navigací v aktuální kapitole, pokud na nej je horizontální místo ve viewportu.

Poděkování

Děkuji všem zmíněným za pomoc v projektu APS skripta

@mvojacek - oponent projektu
- GitHub - https://github.com/mvojacek
@aestheticdisaster - pomoc s pravopisem
- GitHub - https://github.com/aestheticdisaster

Zdroje

Čitelný formát

Wikipedia

Obrázky

Gify

https://en.wikipedia.org/wiki/Karnaugh_map#/media/File:Torus_from_rectangle.gif

Tex

https://texample.net/tikz/examples/complement/

ČSN ISO 690

[1] RUST-LANG, nedatováno. Rust-Lang/mdbook: Create book from markdown files. like Gitbook but implemented in rust. GitHub [online] [vid. 25. únor 2024]. Získáno z: https://github.com/rust-lang/mdBook

[2] ANON., 2022a. Karnaughova Mapa. Wikipedia [online] [vid. 25. únor 2024]. Získáno z: https://cs.wikipedia.org/wiki/Karnaughova_mapa

[3] ANON., 2022a. Adresní SBĚRNICE. Wikipedia [online] [vid. 25. únor 2024]. Získáno z: https://cs.wikipedia.org/wiki/Adresn%C3%AD_sb%C4%9Brnice

[4] ANON., 2023. Control Bus. Wikipedia [online] [vid. 25. únor 2024]. Získáno z: https://en.wikipedia.org/wiki/Control_bus

[5] ANON., nedatováno. Example: Visualisation of two’s complement for a 4-bit-value. TeXample.net [online] [vid. 25. únor 2024]. Získáno z: https://texample.net/tikz/examples/complement/

[6] ANON., 2024. Karnaugh map. Wikipedia [online] [vid. 25. únor 2024]. Získáno z: https://en.wikipedia.org/wiki/Karnaugh_map#/media/File:Torus_from_rectangle.gif

[7] ANON., nedatováno. File:Buffer ANSI Labelled.svg. Wikimedia Commons [online] [vid. 25. únor 2024 b]. Získáno z: https://commons.wikimedia.org/wiki/File:Buffer_ANSI_Labelled.svg

[8] File:NOT ANSI labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:NOT_ANSI_Labelled.svg

[9] ANON., nedatováno. File:Buffer ANSI Labelled.svg. Wikimedia Commons [online] [vid. 28. únor 2024 b]. Získáno z: https://commons.wikimedia.org/wiki/File:Buffer_ANSI_Labelled.svg

[10] File:or ANSI Labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:OR_ANSI_Labelled.svg

[11] File:NAND ANSI Labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:NAND_ANSI_Labelled.svg

[12] File:nor ANSI Labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:NOR_ANSI_Labelled.svg

[13] File:XOR ANSI Labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:XOR_ANSI_Labelled.svg

[14] File:XNOR ANSI Labelled.svg. Wikimedia Commons [online]. [vid. 27. únor 2024]. Získáno z: https://commons.wikimedia.org/wiki/File:XNOR_ANSI_Labelled.svg

[15] ANON., nedatováno. File:K-map minterms a.svg. Wikimedia Commons [online] [vid. 28. únor 2024 d]. Získáno z: https://commons.wikimedia.org/wiki/File:K-map_minterms_A.svg

[16] ANON., nedatováno. File:Sr Flip-flop diagram.svg. Wikimedia Commons [online] [vid. 28. únor 2024 e]. Získáno z: https://commons.wikimedia.org/wiki/File:SR_Flip-flop_Diagram.svg

[17] ANON., nedatováno. File:d-type transparent latch (NOR).SVG. Wikimedia Commons [online] [vid. 28. únor 2024 d]. Získáno z: https://commons.wikimedia.org/wiki/File:D-type_Transparent_Latch_(NOR).svg

[18] ANON., nedatováno. File:edge triggered D flip flop.svg. Wikimedia Commons [online] [vid. 29. únor 2024 e]. Získáno z: https://commons.wikimedia.org/wiki/File:Edge_triggered_D_flip_flop.svg

[19] ANON., nedatováno. File:edge triggered D flip flop with set and reset.svg. Wikimedia Commons [online] [vid. 29. únor 2024 e]. Získáno z: https://commons.wikimedia.org/wiki/File:Edge_triggered_D_flip_flop_with_set_and_reset.svg

[20] ANON., nedatováno. File:negative-edge triggered master slave D flip-flop.svg. Wikimedia Commons [online] [vid. 29. únor 2024 h]. Získáno z: https://commons.wikimedia.org/wiki/File:Negative-edge_triggered_master_slave_D_flip-flop.svg

[21] ANON., nedatováno. File:D-type flip-flop diagram.svg. Wikimedia Commons [online] [vid. 29. únor 2024 d]. Získáno z: https://commons.wikimedia.org/wiki/File:D-Type_Flip-flop_Diagram.svg

[22] ANON., nedatováno. File:4 bit shift register 001.SVG. Wikimedia Commons [online] [vid. 29. únor 2024 b]. Získáno z: https://commons.wikimedia.org/wiki/File:4_Bit_Shift_Register_001.svg

[23] ANON., nedatováno. File:Harvard architecture.svg. Wikimedia Commons [online] [vid. 29. únor 2024 i]. Získáno z: https://commons.wikimedia.org/wiki/File:Harvard_architecture.svg

[24] ANON., nedatováno. File:von Neumann Architecture.svg. Wikimedia Commons [online] [vid. 29. únor 2024 m]. Získáno z: https://commons.wikimedia.org/wiki/File:Von_Neumann_Architecture.svg

[25] ANON., nedatováno. File:abasiccomputer.svg. Wikimedia Commons [online] [vid. 29. únor 2024 c]. Získáno z: https://commons.wikimedia.org/wiki/File:ABasicComputer.svg

Checklist

Markdown:
- Forknout mdbook-image-size a rozvolnit syntaxi (image-size-fork)
- quiz (TODO)
- toc (TODO)
- kroki (TODO)
- embedify (TODO)
- footnote (TODO)

APS Skripta