Struktury počítačových systémů Studijní programy OI a KyR Verze 1.1 - 6.10.2016 opravený snímek 16, doplněný 36 a 47(dříve 46) zkráceno podle odpřednášené látky ČVUT-FEL v Praze – kód předmětu A0B35SPS
Vysvětlivky Předmět se začal přednášet pro zahraniční studenty o rok dříve než pro české studenty a stále zůstává v cizojazyčných studijních programech. Kvůli tomu se napřed tvořily anglické přednášky. Anglické snímky se na přání studentů letos z poloviny přeložily do češtiny. I v přeložené části se někde pořád budou používat anglické termíny kvůli nejednotných či neznámých českým ekvivalentů; anglický termín je obvykle již ustálený.
Značka bude 3S signalizovat: "Skrytý Snímek pro Samostudium", který se na přednášce zpravidla nepromítal. Buď shrnuje výklad, nebo ho rozšiřuje. Šipka na dolním okraji znamená pouhou pomocnou značku pro přednášejícího, že existuje ještě další část v animaci snímku. [ Zdroj: British Museum ] SPS
Kvíz: Znáte tento "stoneware"? 2
1. ročník
SPS-Struktury počítačových systémů
LGR: Logika a grafy
OI+
DMA: Diskrétní matematika
OI+
JAG: Jazyky, automaty a gramatiky
zimní
SPS: Struktury počítačových systémů
letní.
2. ročník
APO - Architektura počítačů
Volitelné •APH Aplikace programovatelných hradlových polí •DIT Digitální technika •MIK Mikrokontroléry •PPS Průmyslové počítačové systémy SPS
3
Literatura Přednášky + cvičení 1. 2.
3.
4.
Šusta, R.: Logické funkce-prerekvizita, ČVUT-FEL 2016 Enoch O. Hwang: Digital Logic and Microprocesor Design with VHDL, Electronix 2004, 513 s. https://dcenet.felk.cvut.cz/fpga/ -> Knihovna Bayer, J. - Hanzálek, Z. - Šusta, R.: Logické řízení. 2. vyd. Praha: ČVUT 2008. 270 s. ISBN 978-80-0104106-2. Bayer, J. - Šusta, R.: Logické řízení - cvičení. 1. vyd. Praha: ČVUT 2008. 208 s. ISBN 978-80-01-04105-5.
Přednášející Richard Šusta preferovaný email:
[email protected] (
[email protected]), +420 2 2435 7359
+ na cvičení: Martin Hlinovský
[email protected], +420 2 2435 7477
Stránky předmětu
Google hledej: "fel sps" https://moodle.dce.fel.cvut.cz/course/view.php?id=5 https://moodle.dce.fel.cvut.cz/ -> starý moodle https://moodle.fel.cvut.cz/course/view.php?id=778 -> nový moodle https://dce.fel.cvut.cz/ -> E-kurzy systému Moodle
http://susta.cz/fel/ nebo www.susta.cz/fel
Stránky cvičení (přihlášení přes FelId) https://dcenet.felk.cvut.cz/fpga/ -> přihlášení heslem do KOSu
http://dcenet.felk.cvut.cz/ http://dcenet.felk.cvut.cz/edu/fpga/ <-Instalace a dokumentace (bez přihlášení) 5
Počítačový systém a jeho nitro
[ (c) Tron]
Co už víte o počítačích…
Technologie
Historie
Programování
Počítač
Rozdělení
SPS
7
Struktura počítače - horní úroveň Periferní zařízení
Program + Obvody logické a analogové Počítač
Počítač
Vstupy Výstupy
CPU Systémové propojení
Komunikace
Hlavní paměť
CPU - eng: Central Processing Unit aka Central Processor Unit cz: nejčastěji jako "procesor" (Pozn. eng: aka = also known as) SPS
8
Struktura CPU Strojový kód a logické obvody CPU Computer
Registry
ALU
I/O Systémové sběrnice Paměť
CPU
Vnitřní CPU komunikace
Control Unit cz: řadič
ALU - eng: Arithmetic and Logic Unit, cz: Aritmeticko-logická jednotka SPS
9
Struktura řadiče
Control Unit / Řadič CPU
Sekvenční logika
ALU Internal Bus
Control Unit
Registry a dekodéry řadiče
Registers
Logické obvody SPS
Paměti pro řadič
10
Různé kódy One hot
Gray code
Gray code ordered numbers
x”0”
0000 0000 = x"00"
0000 0000 0000 0001
0000
0
01
x”1”
0000 0001 = x"01"
0000 0000 0000 0010
0001
0010
02
x”2”
0000 0010 = x"02"
0000 0000 0000 0100
0011
3
0011
03
x”3”
0000 0011 = x"03"
0000 0000 0000 1000
0010
4
0100
04
x”4”
0000 0100 = x"04"
0000 0000 0001 0000
0110
5
0101
05
x”5”
0000 0101 = x"05"
0000 0000 0010 0000
0111
6
0110
06
x”6”
0000 0110 = x"06"
0000 0000 0100 0000
0101
7
0111
07
x”7”
0000 0111 = x"07"
0000 0000 1000 0000
0100
8
1000
10
x”8”
0000 1000 = x"08"
0000 0001 0000 0000
1100
9
1001
11
x”9”
0000 1001 = x"09"
0000 0010 0000 0000
1101
10
1010
12
x”A”
0001 0000 = x"10"
0000 0100 0000 0000
1111
11
1011
13
x”B”
0001 0001 = x"11"
0000 1000 0000 0000
1110
12
1100
14
x”C”
0001 0010 = x"12"
0001 0000 0000 0000
1010
13
1101
15
x”D”
0001 0011 = x"13"
0010 0000 0000 0000
1011
14
1110
16
x”E”
0001 0100 = x"14"
0100 0000 0000 0000
1001
15
1111
17
x”F”
0001 0101 = x"15"
1000 0000 0000 0000
1000
Binary 8421
Octal 421
Hex
0
0000
00
1
0001
2
SPS
(VHDL syntax)
Always only 1-bit changes between adjacent codes
BCD binary / hex
Dec.
1 3 2 6 7 5 4
12 13 15 14 10 11 9 8 11
Gray Code / Grayův kód
Grayovy kódy se nehodí pro výpočty, ale používají se v měření, komunikaci a minimalizaci logických obvodů. Rychlé změny mezi 3 a 4 vyvolají: Grayův kód: 111 <-> 110 - pouze 1 bit není jistý Binární: 100 <-> 011, všechny 3 bity jsou nejisté.
111
000
100
000
0 110
1
001
4 100
010
3 011
001
3
2 101
101
111
011
4 110
010
Některé systémy používají "Gray code based ordering" - cz: řazení podle Grayova kódu, např. Karnaughovy mapy pro minimalizace logických funkcí. SPS
12
Logické funkce základ digitální techniky
Úplně definovaná logická funkce [eng: Completely Specified Logic Function]
Definice: Úplně definovaná logická funkce n proměnných y =f(x1,x2,x3,..xn) je zobrazení Bn→B, kde B = {0, 1} (x1,x2,x3,..xn) ∈ Bn , xi ∈ B, y ∈ B
SPS
14
Neúplně definovaná logická funkce Definice: Neúplně definovaná logická funkce n proměnných y =f(x1,x2,x3,..xn) je zobrazení Bn→B ∪ { X }, kde B = {0,1} , X-označuje "don't care" (x1,x2,x3,..xn) ∈ Bn , xi ∈ B, y ∈ B ∪ { X }
X - "don't-care" (cz: "nezadáno", "je to jedno"?) označuje poznámku, že o hodnotě rozhodneme později během další kroků návrhu dle toho, co se ukáže výhodnější. Všechna X se časem stanou pevně přiřazenými logickými 0 či 1, protože každý logický výraz nebo logický obvod je popsaný jedině úplně definovanými logickými funkcemi.
SPS
15
Příklad B: Morseův maják EAEA...
N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
D 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 SPS
C 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
A 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
M 0 1 0 0 0 1 0 1 1 1 0 0 X X X X
Čítač 0..11
Pravdivostní tabulka (zobrazení B4→B ∪ { X } )
D C B A
N
M
EA = . .- = 010001011100 Erb Akát
16
Kombinační logický obvod Definice: Výstupy y1 ... ym kombinačního logického obvodu jsou logické funkce s n-vstupy x1 ... xn. y1=f1(x1,x2,..xn) ... ym=fm(x1,x3,..xn),
n vstupů
x1 x2 xn
Kombinační logický obvod (KLO / KO)
y1 y2
m výstupů
ym
KO =kombinační logický obvod, eng. Combinational Logic (Circuit)
SPS
18
Sekvenční logický obvod Definice: Výstupy y1 ... ym sekvenčního logického obvodu jsou logické funkce s n-vstupy x1 ... xn a p hodnotami vnitřních paměťových prvků s1 (t), s2 (t),..sp (t) . Hodnoty si(t) závisí na jejich počátečním stavu a hodnotách vstupů xi od času t=0 až po současnost
y1(t)=f1(x1,x2,..xn, s1(t), s2(t),..sp(t)) ... ym(t)=f1(x1,x2,..xn, s1(t), s2(t),..sp(t))
n vstupů
x1 x2 xn
Kombinační logický obvod (KLO / KO)
Vstupy stavu
y1 y2 ym
m výstupů
Stavové výstupy p - paměťových prvků
SPS
19
Kombinační versus sekvenční obvod
Kombinační obvod je speciálním případem sekvenčního obvodu s 0 paměťovými prvky. Stejné hodnoty x1 ... xn na vstupech kombinačního obvodu dávají pokaždé stejné hodnoty y1 ... ym na výstupech. Sekvenční obvody lze rozdělit na kombinační obvody a vnitřní paměťové prvky.
Paměťové prvky patří mezi sekvenční obvody. Mají jednoduchou strukturu, a tak tvoří jakési stavební kameny složitějších sekvenčních obvodů. Vydělují se ze jejich struktur pro snadnění návrhu.
Činnost sekvenčních obvodů vychází z kombinačních obvodů, a tak se sekvenčním obvodům budeme věnovat až v pozdějších přednáškách. SPS
20
Př. E: 2bitový komparátor
SPS
B1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
A0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1
N1 Y
B1 B0
Úplná pravdivostní tabulka A1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
A1 A0
A1 A0 >= B1 B0
N2
Zkrácená pravd. tabulka A1 0 0 0 0 1 1 1 1
B1 0 0 0 1 0 1 1 1
A0 0 0 1 0 0 1
B0 0 1 0 1 -
Y 1 0 1 0 1 1 0 1
Sloučené řádky v pravd.tabulce - hodnota vstupu nemá žádný vliv na hodnotu výstupu, symbol - představuje něco jako "wildcard" (cz: náhradní/maskovací znak) 21
Truth Table N 0 1 2 3 4 5 6 7 8 9 10 11 12-15
D 0 0 0 0 0 0 0 0 1 1 1 1 1
C 0 0 0 0 1 1 1 1 0 0 0 0 1
B 0 0 1 1 0 0 1 1 0 0 1 1 -
A 0 1 0 1 0 1 0 1 0 1 0 1 -
M 0 1 0 0 0 1 0 1 1 1 0 0 X
Counter 0..11
Příklad B2: Morseův maják EAEA... D C B A
N
M
EA = . .- = 010001011100
Tabulka zkrácena
Poznámka: Tabulka by se dala samozřejmě ještě více zkrátit, ale smyslem zkracování tabulek není napsat minimum řádků, ale přehledný popis funkce. V našem případě naznačujeme poslední bit sekvence na řádku číslo 11. SPS
22
Logické funkce ve výrazech
Příklad C2: 3bitový dekodér 1 z N (one hot decoder)
N A B C
F0
F1
F2
F3
F4
F5
F6
F7
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
2
0
1
0
0
0
1
0
0
0
0
0
3
0
1
1
0
0
0
1
0
0
0
0
4
1
0
0
0
0
0
0
1
0
0
0
5
1
0
1
0
0
0
0
0
1
0
0
6
1
1
0
0
0
0
0
0
0
1
0
7
1
1
1
0
0
0
0
0
0
0
1
A B C
3x8
8
F
F0=m(0)=A'.B'.C'
F1=m(1)=A'.B'.C
F2=m(2)=A'.B.C'
F3=m(3)=A'.B.C
F4=m(4)=A.B'.C'
F5=m(5)=A.B'.C
F6=m(6)=A.B.C'
F7=m(7)=A.B.C
Definice: Součinový člen (A product term), kde každá proměnná se objeví nejvýše jednou, a to buď jen v negované nebo jen v přímé formě, se nazývá minterm; často se značí jako m(.) SPS
24
Logické schéma - grafická forma výrazu F0 = A'.B'.C' C
F1 = A'.B'.C
B
F2 = A'.B.C'
A
F3 = A'.B.C F4 = A.B'.C' F5 = A.B'.C F6 = A.B.C'
F7 = A.B.C
SPS
A B
C
F0
F1
F2
F3
F4
F5
F6
F7
0 0
0
1
0
0
0
0
0
0
0
0 0
1
0
1
0
0
0
0
0
0
0 1
0
0
0
1
0
0
0
0
0
0 1
1
0
0
0
1
0
0
0
0
1 0
0
0
0
0
0
1
0
0
0
1 0
1
0
0
0
0
0
1
0
0
1 1
0
0
0
0
0
0
0
1
0
1 1
1
0
0
0
0
0
0
0
1
And hradlo (eng:AND gate) A B
X = A.B
Invertor A
A' 25
Disjunktivní normální forma
Sum-of-Products = S-o-P, založená na minterms F = 001
011
101
110
111
A'B'C + A'BC + AB'C + ABC' + ABC A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 0 1 0 1 0 1 1 1
F' 1 0 1 0 1 0 0 0
F' = A'B'C' + A'BC' + AB'C'
Pozn.: Mintermy popisují prvky on-setu. Zapisují proměnné podle binární hodnoty. Např. F1=m(1)=A'+B'+C pro index 1, který je binárně 001, má v mintermu negevané proměnné A' a B' v místě '00' a proměnnou C na místě hodnot '1'. SPS
26
Příklad D2: 1 z N N
A
B
C
F0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
1
1
0
1
1
1
1
1
1
2
0
1
0
1
1
0
1
1
1
1
1
3
0
1
1
1
1
1
0
1
1
1
1
4
1
0
0
1
1
1
1
0
1
1
1
5
1
0
1
1
1
1
1
1
0
1
1
6
1
1
0
1
1
1
1
1
1
0
1
7
1
1
1
1
1
1
1
1
1
1
0
F0=M(0)=A+B+C F4=M(4)=A'+B+C
F1
F2
F3
F4
F5
F1=M(1)=A+B+C' F5=M(5)=A'+B+C'
F6
F7
3bit one cold decoder
A B C
F2=M(2)=A+B'+C F6=M(6)=A'+B'+C
3x8
8
F
F3=M(3)=A+B'+C' F7=M(7)=A'+B'+C'
Definice: Součtový člen (eng: A sum term), kde každá proměnná se objeví nejvýše jednou buď jen v negované nebo jen v přímé formě, se nazývá maxterm, obvykle značený jako M(.)
SPS
27
Konjunktivní normální forma
Products-of-Sum = P-o-S, založená na F= 000 010 100 maxtermech F = (A + B + C) (A + B' + C) (A' + B + C) A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 0 1 0 1 0 1 1 1
F' 1 0 1 0 1 0 0 0
F' = (A + B + C') (A + B' + C') (A' + B + C') (A' + B' + C) (A' + B' + C')
Pozn.: Maxtermy popisují prvky off-setu. Zapisují proměnné negovaně vzhledem k binární hodnotě! Např. F4=M(4)=A'+B+C pro index 4, který je binárně 100, má v maxtermu proměnnou A' v místě '1' a negované proměnné B' a C' na místech hodnot '00'. SPS
28
Příklad: 2 bitový komparátor 1/2 Pravdivostní tabulka n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 A1 A0
B1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
A0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
N1 Y
B1 B0
B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1
S-o-P- Sum of Products (mintermy - onset) Y = ∑ m(0,2,3,8,9,10,11,12,14,15) = A1'.B1'.A0'.B0'+ (0) A1'.B1'.A0.B0'+A1'.B1'.A0.B0 + (2, 3) A1.B1'.A0'.B0' + A1.B1'.A0'.B0+ (8, 9) A1.B1'.A0.B0' + A1.B1'.A0.B0+ (10,11) A1.B1.A0'.B0'+ (12) A1.B1.A0.B0'+A1.B1.A0.B0 (14, 15) P-o-S Product of Sums (maxtermy - offset) Y = ∏ M(1,4,5,6,7,13) = (A1+B1+A0+B0'). (1) (A1+B1'+A0+B0).(A1+B1'+A0+B0'). (4,5) (A1+B1'+A0'+B0).(A1+B1'+A0'+B0'). (6,7) (A1'+B1'+A0+B0') (13)
A1 A0 >= B1 B0
N2
SPS
29
Příklad: 2 bitový komparátor 2/2 Zkrácená pravd.tab. n A1 B1 A0 B0
0 1 2,3 4,5,6,7 8,9,10,11 12 13 14,15
0 0 0 0 1 1 1 1
0 0 0 1 0 1 1 1
0 0 1 0 0 1
0 1 0 1 -
Y 1 0 1 0 1 1 0 1
A1 A0
N1 Y
B1 B0
N2
A1 A0 >= B1 B0
Sum of minterms (onset) Y = ∑ m(0,2,3,8,9,10,11,12,14,15) = A1'.B1'.A0'.B0'+ (0) A1'.B1'.A0 + (2,3) A1.B1'+ (8,9,10,11) A1.B1.A0'.B0'+ (12) A1.B1.A0 (14,15) Product of maxterms (offset) Y = ∏ M(1,4,5,6,7,13) = (A1+B1+A0+B0'). (1) (A1+B1'). (4,5,6,7) (A1'+B1'+A0+B0') (13) Poznámka: Výsledek není zatím minimální.
SPS
30
Zkrácená pravd. tab. N 0 1 2 3 4 5 6 7 8 9 10 11 12-15
D 0 0 0 0 0 0 0 0 1 1 1 1 1
SPS
C 0 0 0 0 1 1 1 1 0 0 0 0 1
B 0 0 1 1 0 0 1 1 0 0 1 1 -
A 0 1 0 1 0 1 0 1 0 1 0 1 -
M 0 1 0 0 0 1 0 1 1 1 0 0 X
Counter 0..11
Příklad: Morseův maják EAEA... D C B A
N
M
EA = . .- = 010001011100 onset -musí být v 1 offset -musí být v 0 don’t care set (0 nebo 1)?
Co bude lepší? => nevíme, třeba
nám minimalizační metody!
31
Minimalizace Karnaughovy mapy
Boolean cubes ~ Booleovské krychle
n vstupních proměnných = n-rozměrná krychle 11
01 0
1-rozměr
1
Y
X
2-rozměry
00
X
10 0111
111
1111
4-rozměry 3-rozměry
Y Z
000
SPS
101 X
Y 0000
Z
W X
1000
33
Pravdivostní tabulky jako Booleovské krychle On-set – vyplněné uzly, off-set – prázdné uzly ab 00 01 10 11
b
f 0 0 1 1
01
f 10
Výstupy
N
A
B
C
y
0
0
0
0
0
1
0
0
1
0
2
0
1
0
1
3
0
1
1
1
4
1
0
0
1
5
1
0
1
1
6
1
1
0
0
7
1
1
1
0
SPS
a
00
Vstupy
ab f 0- 0 1- 1
11
011
111 110
010 B 000
001
C A
101 100
34
Minimalizace Booleovské krychle
Spojujeme uzly na hraně v jeden Příklad: A
B
F
0
0
1
0
1
0
1
0
1
1
1
0
A
B
F
-
0
1
-
1
0
F 11
01 B
00
A
10
Hodnota nezávisí na A, pouze na B
Teorém
a’.b’ + a.b' = b’ SPS
dva uzly dimenze 0, každý popisuje jen jeden výstup, se spojí ve dvojici (úsečku dimenze 1)
Teorém (a'+b').(a+b')
= b' 35
Odvození teorémů
a’.b’ + a.b' = (a’ + a).b' = 1.b' = b'
(a'+b').(a+b')
= (a'+b').a+(a'+b').b' = a'.a+b'.a+a'.b'+b'.b' = 0+b'.a+a'.b'+b' = (a+a').b'+b' = 1.b'+b' = b'+b' = b'
SPS
36
Karnaughovy mapy (KM)
Booleovské krychle rozvinuté do roviny Sousedé jdou přes hrany
mezi
prvním a posledním sloupcem mezi horní a dolní řádkou 011
A C
000 010
110
100
001 011
111
101
B
111
110
010
001
B C 000
A
101 100
A C
0
1
0
1
0
1
0
0
B
SPS
B C A 37
Karnaughovy mapy (pokr.) KM vychází z řazení dle Grayova kódu (Gray code ordering), tj. pouze 1 bit se mění při pohybu vodorovně nebo svisle v mapě, např. 00, 01, 11, 10. Dodržení Grayova řazení je naprosto nutnou podmínkou pro použití Karnaughovy mapy! C
AB 0 1
Různé styly pro KM
00
011
10
0
2
6
4
1
3
7
5
C
0
2
6
4
1
3
7
5
B
111 110
010
001
B C 000
A
C
101
100
A
A B
A
0
2
6
4
0
2
6
4
1
3
7
5
1
3
7
5
B SPS
11
01
C 38
Grayovy kódy a Grayovo uspořádání Existuje mnoho Grayových kódů a tím i mnoho způsobů nakreslení Karnaughovy mapy. Pokud začneme od 0, pak existuje celkem: 2 kódy/řazení dvoubitových binárních čísel 0 1 3 2, 0 2 3 1 18 kódů/řazení pro tříbitová binární čísla 0 1 3 2 6 7 5 4, 0 1 3 2 6 4 5 7, 0 1 3 7 5 4 6 2 0 1 5 4 6 7 3 2, 0 1 5 4 6 2 3 7, 0 1 5 7 3 2 6 4 0 2 3 1 5 4 6 7, 0 2 3 1 5 7 6 4, 0 2 3 7 6 4 5 1 0 2 6 7 3 1 5 4, 0 2 6 4 5 7 3 1, 0 2 6 4 5 1 3 7 0 4 5 7 6 2 3 1, 0 4 5 1 3 2 6 7, 0 4 5 1 3 7 6 2 0 4 6 7 5 1 3 2, 0 4 6 2 3 1 5 7, 0 4 6 2 3 7 5 1 5712 kódů/řazení pro 4 bitová binární čísla; 5859364320 kódů/řazení pro 5 bitová binární čísla. Poznámka: Další podrobnosti k tématu Grayových kódů najdete při hledání anglického pojmu “Hamiltonian paths on hypercube” (i.e. on n-dimensional cube) SPS
39
Příklad: Karnaughova mapa pro 8 proměnných • Menší mapy lze získat dělením větší mapy. • Všimněte si, že úsečky nižší úrovně jsou umístěné symetricky vůči koncům úseček vyšší úrovně. • Celkové délky úseček jednotlivých úrovní (proměnných) pokrývají vždy polovinu polí.
a b c d
e f g h SPS
40
Příklady Karnaughovy mapy A C
0
0
1
1
0
0
1
1
G(A,B,C) =
A
B A C
1
0
0
1
0
0
1
1
F(A,B,C) = m(0,4,5,7) = AC + B’C’
B A C
0
1
1
0
1
1
0
0
F'(A,B,C) = m(1,2,3,6)
= BC’ + A’C
B
Cvičení: Nakreslete odpovídající Booleovské krychle SPS
41
Příklad: Majorita
Funkce majorita (eng. majority function aka median operator) má n vstupů a jeden výstup - ten bude "false", pokud n/2 a více výstupu je "false", jinak má hodnot0 "true". Úkol: Navrhněte 3-bitovou majoritu. A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
Y 0 0 0 1 0 1 1 1
(A'+A).B.C 111
B C 000
A.B.(C'+C)
101 A
A.(B+B').C
Y = B.C+A.B+A.C SPS
42
Majorita na krychli a mapě (A'+A).B.C 111
A
A.B.(C'+C) C
B C 000
0
0
1
0
0
1
1
1
101
A.B + A.C + B.C
B
A.(B+B').C
A
(A+C+B'). (A+C+B) 111
A
(A+B+C'). (A+B+C) B C 000
101 A
SPS
C
(A'+B+C).(A+B+C)
0
0
1
0
0
1
1
1
(A+B) . (B+C) . (A+C)
B
43
Majorita ze 3
A
INPUT VCC
AND2
inst
B
INPUT VCC
AND2
OUTPUT
inst2
C
INPUT VCC
OR3
Y
inst4
AND2
inst3
SPS
44
4vstupová KM a pravdivostní tabulka dcba
Y
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
dcba
Y
a
a
b
d c
b
0000
0010
0011
0001
0
1
1
0
0100
0110
0111
0101
0
0
0
0
1100
1110
1111
1101
0
0
0
0
1000
1010
1011
1001
0
0
0
0
d c
S-o-P: F=b.c’.d’ P-o-S: F=b.c’.d’ SPS
45
KM: 4 vstupy
F(A,B,C,D) = m(0,2,3,5,6,7,8,10,11,14,15) F = C + A’BD
+ B’D’ A
C
1
0
0
1
0
1
0
0
1 1
1
1
1
1
1 1
0111
D
Y 0000
Z
W X
1111
1000
B
Snažíme se najít minimální počet pokrytí.
Pozor: Každé pokrytí zahrnuje nějaký počet polí určený mocninou 2 - tj. 1, 2, 4, 8, 16 atd. SPS
46
Příklad: KM pro 2bitový komparátor Tabulka n A1 B1 A0 B0
0 1 2,3 4,5,6,7 8,9,10,11 12 13 14,15
0 0 0 0 1 1 1 1
0 0 0 1 0 1 1 1
0 0 1 0 0 1 A1
B0 1
4
12
8
2
6
14
10
3
7
15
11
1
5
13
9
B1 4
Y 1 0 1 0 1 1 0 1
0 1 0 1 8
0
SoP z tabulky Y = ∑ m(0,2,3,8,9,10,11,12,14,15) = A1'.B1'.A0'.B0'+ (0) A1'.B1'.A0 + (2,3) A1.B1'+ (8,9,10,11) A1.B1.A0'.B0'+ (12) A1.B1.A0 (14,15)
A0 2
B0
A1 1
0
1
1
1
0
1
1
1
0
1
1
0
0
0
1
A0
Funkce z KM B1'B0' (0,2,8,10) +A0.B1' (2,3,10,11) +A1.B1' (8,9,10,11) +A1.B0' (8,10,12,14) +A1.A0 (10,11,14,15)
B1
Minimalizace se dosahuje násobným pokrytím stavu. SPS
47
KM a stavy "don't care": 0, 1, x
f(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13) f
= A'D + B'C'D f = A'D + C'D
bez "don't care" s "don't care"
A
C
A
0
0
X
0
1
1
X
1
1
1
0
0
0
X
0
0
D
B
•
SPS
don't care můžeme brát jako 0 nebo 1 podle toho, co je výhodnější
C
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
D
B
KM finální logické funkce 48
Karnaughovy mapy a "don’t care" dcba 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Y 1 1 1 1 0 1 0 X 1 0 1 1 1 X 1 X
a
b
b
1
1
1
1
1
1
1
1
0
0
-
1
0
0
-
1
1
1
-
-
1
1
-
-
1
1
1
0
1
1
1
0
d c
d c
FSoP1 x c.d b.c a.c a.d
a
FPoS x a c d . a b d FSoP1 x FSoP2 x FPoS x ;
FSoP2 x c.d b.c a.d a.d
FSoP1 x FŚoP2 x FPoS x ; x; Fn x 0 1 SPS
Pokryjeme-li don't care stavy • SoP termy, budou 1. • PoS termy, budou 0. 49
Morseův maják EAEA... Čítač 0..11
Pravd. tabulka N 0 1 2 3 4 5 6 7 8 9 10 11 12-15
D 0 0 0 0 0 0 0 0 1 1 1 1 1
C 0 0 0 0 1 1 1 1 0 0 0 0 1
B 0 0 1 1 0 0 1 1 0 0 1 1 -
A 0 1 0 1 0 1 0 1 0 1 0 1 -
M 0 1 0 0 0 1 0 1 1 1 0 0 X
EA = . .- = 010001011100
D C B A
N
M
Krok 1 - přepíšeme tabulku do KM podle pořadí řádků
Krok 2 - pokryjeme KM A
C
A
0
2
3
1
8
10
11
9
12
14
15
13
4
6
7
5
D
B
C
0
0
0
1
1
0
0
1
X
X
X
X
0
0
1
1
D
B
P-o-S: M = (A+D).(B’+C) Krok 3: Za domácí úkol vytvořte S-o-P pokrytí majáku. SPS
50
Grafická forma výrazu Counter 0..11
A B C D
P-o-S: M = (A+D).(B’+C) Simulace majáku
X - don't care
D C B A Maják SPS
51
K-mapy pro více proměnných
ab = 10
a=1
de 00
bc 00 01
11
10 ab = 11
10
00 01 11
10
00 01 11
10
00 01 11
10
00 10 11 10
00 01 11
10
ab = 01
00 10 11 10
00 10 11 10
cd 00 01 11
10 11 10
10 11 10
a=0
ef 00
ab = 00
00 10 11 10
SPS
52
KM pro 5 proměnných 1/2 KM pro 5 proměnných
DE 00 01
A=0 BC DE 00 01 11 10 A =0 00 0 4 12 8 01 1 5 13 9 11 3 7 15 11 10 2 6 14 10
11
A =1
01 11 10
00
01
11
16
20
28
17 19
18
21 23
22
29 31
30
10 24
01
1
A=1
10 1
11
10 1
1
1
1
DE 00 01 1 11
11
1
10 1
BC DE 00
BC 00
1
BC 00
01
1
1
1
1
10
25 27
26
f(A,B,C,D,E) = m(2,5,7,8,10, 13,15,17,19,21,23,24,29 31) = C E + A B' E + B C' D' E' + A' C' D E'
SPS
53
KM pro 5 proměnných 2/2 f(A,B,C,D,E) = m(2,5,7,8,10, 13,15,17,19,21,23,24,29 31) C
C LSB- E 0
4
12
8
1
5
13
9
3
7
15
2
6
18
D
B
0
0
0
1
0
1
1
0
11
0
1
1
0
14
10
1
0
0
1
22
30
26
0
0
0
0
19
23
31
27
1
1
1
0
17
21
29
25
1
1
1
0
16
20
28
24
0
0
0
1
A - MSB
SPS
B
LSB- E D
A - MSB
54
Sousedé u KM pro 8 proměnných a b c d
e f g h SPS
55
K-mapy
- Použití-
Miniotázka na doma: Minimalizujte KM detektoru prvočísel
F(w,x,y,z) = (1,2,3,5,7,11,13) A-1
D-8
C-4 B-2
SPS
57
Miniotázka: Minimalizujte KM detektoru prvočísel
F(a,b,c,d) = (1,2,3,5,7,11,13) Krok 1 - vytvoříme číslování podle vah bitů
Krok 2 - pokryjeme KM
A-1
C-4
0
2
3
1
8
10
11
9
12
14
15
13
4
6
7
5
A
D-8
B-2
C
0
1
1
1
0
0
1
0
0
0
0
1
0
0
1
1
D
B
A.D'+A.B'.C+A.B.C'+B.C'.D' =A.D'+A.(B xor C)+B.C'.D' SPS
58
