Y36SAP
26.2.2007
Y36SAP-2 Logické obvody kombinační Formy popisu Příklad návrhu Sčítačka 2007-Kubátová
Y36SAP-Logické obvody
1
Logický obvod • Vstupy a výstupy nabývají pouze hodnot 0 nebo 1
Kombinační obvod – popsán kombinační funkcí Hodnoty všech výstupních proměnných jsou v každém časovém okamžiku určeny pouze hodnotami vstupních proměnných v témže časovém okamžiku 2007-Kubátová
Y36SAP-Logické obvody
2
1
Y36SAP
26.2.2007
Kombinační funkce Kombinační funkce: outk = f(i1, i2, i3, … ip), k=1,2,…,m i1 i2 i3
out1 out2
f
outm
ip
2007-Kubátová
Y36SAP-Logické obvody
3
Základní kombinační prvky - hradla Wire
Inverter In Out 0 1
Out = In
In
0 1
A
Out
B
0 0 1 1
A
Out
B
2007-Kubátová
A B 0 0 0 1 1 0 1 1
A
1 1 1 0
A
A 1 1 0 0
Out
B
DeMorgan’s Theorem
Out = A • B = A + B
1 1 1 0
A B
Y36SAP-Logické obvody
0 0 1 1
B Out 0 1 0 1
1 0 0 0
Out = A + B = A • B
B Out 1 0 1 0
1 0
NOR Gate
B Out 0 1 0 1
0 1
Out = In
NAND Gate A
In Out
Out
Out
A B 0 0 0 1 1 0 1 1
A 1 1 0 0
B Out 1 0 1 0
1 0 0 0 4
2
Y36SAP
26.2.2007
Obecná kombinační logická buňka, zpoždění Vout
A B
. . .
Combinational Logic Cell
Delay Va -> Vout
X
Cout
X X
X
X X
X
delay per unit load
Internal Delay Ccritical
Cout
Kombinační buňka (symbol) je plně určena: – Funkčním chováním (input -> output) • Pravdivostní tabulka, logická rovnice, …. – Zatížením vstupů – Propagačním zpožděním z každého vstupu na výstup a pro každou změnu signálu 2007-Kubátová
Y36SAP-Logické obvody
5
Návrhový proces • • • • • • • •
Specifikace Určení vstupů a výstupů Pravdivostní tabulky Boolovské rovnice Návrh realizace na úrovni hradel Simulace na úrovni hradel Realizace číslicového obvodu Ověření návrhu
2007-Kubátová
Y36SAP-Logické obvody
6
3
Y36SAP
26.2.2007
Základní pojmy logické syntézy •
Logické funkce a jejich reprezentace, formy popisu a jejich vzájemný převod – – – –
•
tabulka n-rozměrné krychle algebraický zápis mapy
Logická minimalizace – • •
•
Karnaughova mapa (metoda Quine-McCluskey)
Realizace na úrovni hradel
2007-Kubátová
Y36SAP-Logické obvody
7
Boolovská n-krychle (cube) Bn • B = { 0,1} • B2 = {0,1} X {0,1} = {00, 01, 10, 11}
B0
B2
B1 B4 B3
2007-Kubátová
Y36SAP-Logické obvody
8
4
Y36SAP
26.2.2007
Booleovské funkce n
f(x) : B B B = {0, 1}, x = (x1, x2, …, xn) • x1, x2, … jsou proměnné - variables • x1, x1, x2, x2, … jsou literály - literals n • Každému vrcholu B je přiřazena 0 nebo 1 – onset f je {x|f(x)=1} =f 1 = f -1(1) – offset f je {x|f(x)=0} =f 0 = f -1(0) • jestliže f 1 = Bn, f je tautologie, tzn. f ≡ 1 n • jestliže f 0 = B (f 1 = ∅), f není splnitelná • jestliže f(x) = g(x) pro všechna x ∈Bn, pak f a g jsou ekvivalentní Obvyklé zjednodušení: f namísto f 1 2007-Kubátová
Y36SAP-Logické obvody
9
Literály Literál je proměnná nebo její negace y, y Literál reprezentuje logickou funkci. Literál x1 reprezentuje logickou funkci f, kde f = {x| x1 = 1} f = x1
g = x1
x1
x1
Literál x1 reprezentuje logickou funkci g, kde g = {x| x1 = 0} 2007-Kubátová
Y36SAP-Logické obvody
10
5
Y36SAP
26.2.2007
Boolovské formule - výrazy Boolovské formule (Boolean formulas) mohou být reprezentovány formulemi definovanými jako zřetězení • závorek ( , ) • literálů x, y, z, x, y, z • Boolovských operátorů + (OR), . (AND) • komplementace, např. x + y Příklady f = x1 . x2 + x1 . x2 = (x1+x2) . (x1+x2) h = a + b . c = a . (b + c) Obvykle nahrazujeme . jen zřetězením, a . b → ab 2007-Kubátová
Y36SAP-Logické obvody
11
Logické funkce Existuje 2n vrcholů v prostoru Bn 111
x3
x2
000
x1
000 1 001 0 010 1 011 0 100 ⇒ 1 101 0 110 1 111 0
n
2
Existuje 2 různých logických funkcí Každá podmnožina vrcholů tvoří jinou logickou funkci: f ⊆ Bn 2007-Kubátová
Y36SAP-Logické obvody
12
6
Y36SAP
26.2.2007
Logické funkce • Ale existuje nekonečně logických formulí f=x+y = xy + xy + xy = xx + xy + y = (x + y)(x + y) + xy
• Syntéza – nalezení "nejlepší" formule (nebo “reprezentace”) z hlediska cílové platformy
2007-Kubátová
Y36SAP-Logické obvody
13
Boolovské operace AND, OR, KOMPLEMENT f : Bn → B g : Bn → B • AND - fg = h kde h = {x| f(x)=1 and g(x)=1} • OR - f + g = h kde h = {x| f(x)=1 or g(x)=1} • KOMPLEMENT - f = h kde h = {x| f(x) = 0} 2007-Kubátová
Y36SAP-Logické obvody
14
7
Y36SAP
26.2.2007
Úpravy algebraických výrazů Shannonův expanzní teorém:
f (a, b,...., c) = a. f (1, b,..., c) + a . f (0, b,..., c) Důkaz: platí pro všechna a ..... Důsledek:
∀a ∈ {0,1}
f (a, b,...., c) = a.g (b,..., c) + a .h(b,..., c) Každá logická funkce se dá zapsat pomocí logického součtu, součinu a negace 2007-Kubátová
Y36SAP-Logické obvody
15
Y36SAP-Logické obvody
16
Booleeova agebra:
BA = {B,+,•, ,0 ,1} B = {0,1} x, y , z ∈ B a platí Huntingtonovy axiomy
2007-Kubátová
8
Y36SAP
26.2.2007
2007-Kubátová
Y36SAP-Logické obvody
17
Krychle - cube • Logický součin (AND) množiny literálů (“conjunction - konjunkce” literálů) je krychle C = xy C = (x=1)(y=0) ale může to být i samotný literál z y
x
x =1 2007-Kubátová
y =0 Y36SAP-Logické obvody
xy 18
9
Y36SAP
26.2.2007
Reprezentace Boolovských funkcí • Pravdivostní tabulka funkce f : Bn → B je vyjádření jejich hodnot všech 2n vrcholů z Bn. abcd f • Pro 0 0000 0 f = abcd + abcd + abcd + abcd + abcd + 1 0001 1 2 0010 0 abcd + abcd + abcd Pravdivostní tabulka (truth table): Nepoužitelná pro velká n (ale je kanonická - canonical) Kanonická znamená: když jsou dvě funkce stejné, je jejich kanonická reprezentace izomorfní. 2007-Kubátová
Y36SAP-Logické obvody
3 0011 1 4 0100 0 5 0101 1 6 0110 0 7 0111 0 8 1000 0 9 1001 1 10 1010 0 11 1011 1 12 1100 0 13 1101 1 14 1110 1 15 1111 1 19
Pravdivostní tabulka
2007-Kubátová
Y36SAP-Logické obvody
20
10
Y36SAP
26.2.2007
Logický obvod • • • •
Dvojkové signály – 0 a 1 Číslicový návrh Číslicové obvody – logické obvody Realizace základních bloků číslicového počítače – obecněji číslicového systému a jejich komunikace • Kombinační obvody x sekvenční obvody • Práce s moderními návrhovými systémy
2007-Kubátová
Y36SAP-Logické obvody
21
Jednotlivé fáze návrhového procesu pro číslicové systémy • • • • • • • •
Specifikace Příklad 1, sl. 23 - 25 Určení vstupů a výstupů Pravdivostní tabulky Příklad 1, sl. 26-31 Booleovské rovnice Návrh realizace na úrovni hradel Příklad 1, sl. 32-35 Simulace na úrovni hradel Realizace číslicového obvodu Ověření návrhu
2007-Kubátová
Y36SAP-Logické obvody
22
11
Y36SAP
26.2.2007
Příklad 1
Co ?
Chci sčítat …
Co chci dostat?
JAK ???
2007-Kubátová
Y36SAP-Logické obvody
23
Příklad 1
Dvojkové číslo S = A+B
Dvojková čísla A a B JAK - číslicově
Dvojková čísla budou nejprve 1 bitová, tzn.: 0+0=0, 0+1=1, 1+0=1, ale pozor 1+1=10 !!!
2007-Kubátová
Y36SAP-Logické obvody
Přenos !!!
24
12
Y36SAP
26.2.2007
Příklad 1 a s b
Σ
p
2007-Kubátová
q
Y36SAP-Logické obvody
25
Příklad 1 - intuitivně a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
2007-Kubátová
p 0 1 0 1 0 1 0 1
q 0 0 0 1 0 1 1 1
s 0 1 1 0 1 0 0 1
s = abp + abp + abp + abp q = abp + abp + abp + abp
Y36SAP-Logické obvody
Úpravy výrazů na tabuli:
26
13
Y36SAP
26.2.2007
Příklad 1 – stavový index si 0 1 2 3 4 5 6 7
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
p 0 1 0 1 0 1 0 1
2007-Kubátová
q 0 0 0 1 0 1 1 1
S 0 1 1 0 1 0 0 1
SOP – Úplná normální disjunktivní forma
q = abp + abp + abp + abp
p
b
a si – stavový index
Y36SAP-Logické obvody
27
Příklad 1 - krychle si 0 1 2 3 4 5 6 7
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
2007-Kubátová
p 0 1 0 1 0 1 0 1
q S 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1
SOP – Úplná normální disjunktivní forma ÚNDF
q = abp + abp + abp + abp bp
p
ap
ab b
a SOP – Minimální normální disjunktivní forma MNDF
Y36SAP-Logické obvody
q = bp + ap +ab 28
14
Y36SAP
26.2.2007
Mapy
Svobodova mapa
2007-Kubátová
Y36SAP-Logické obvody
Karnaughova mapa
29
Zápis do mapy – podle přiřazení proměnných, tzn. proužků, které vyjadřují kdy nabývá proměnná hodnotu 1
Minimalizace v mapě – viz →
2007-Kubátová
Y36SAP-Logické obvody
30
15
Y36SAP
26.2.2007
Změna velikosti mapy – zvyšování počtu proměnných
Karnaughova
Svobodova 2007-Kubátová
Y36SAP-Logické obvody
31
Realizace pomocí hradel Hradla
A .B = P …. and
C .D = P 2007-Kubátová
E+F = R … or, V
G xor H = S Y36SAP-Logické obvody
32
16
Y36SAP
26.2.2007
Funkce hradel, Booleova algebra NAND Gate
NOR Gate
Invertor A
Out
In
B
Out
A
Out
B
Out = In A 0 0 1 1
B Out 0 1 0 1
A
1 1 1 0
2007-Kubátová
B
Out
In Out
0
0
1
0 1
0
1
0
1
0
0
1
1
0
1 0
Y36SAP-Logické obvody
33
Funkce hradel, Booleova algebra OR Gate XOR Gate XOR Gate A
AND Gate
AND Gate Out
G
H
S
A 0 0 1 1
0
0
0
0
1
1
1
0
1
1
1
0
2007-Kubátová
A
Out
B
B
B Out 0 1 0 1
0 1 1 1
Y36SAP-Logické obvody
A 0 0 1 1
B Out 0 1 0 1
0 0 0 1
34
17
Y36SAP
26.2.2007
Sčítačka p S
q
2007-Kubátová
Y36SAP-Logické obvody
35
Sčítačka-jiné řešení
2007-Kubátová
Y36SAP-Logické obvody
36
18
Y36SAP
26.2.2007
Sčítačka - ještě jiné řešení
2007-Kubátová
Y36SAP-Logické obvody
37
• • • • • • • •
Specifikace Určení vstupů a výstupů Pravdivostní tabulky Booleovské rovnice Návrh realizace na úrovni hradel Simulace na úrovni hradel Realizace číslicového obvodu Ověření návrhu
2007-Kubátová
Y36SAP-Logické obvody
automatizováno
Programovatelné obvody
38
19
Y36SAP
26.2.2007
Kombinační x sekvenční obvody • Kombinační – vystup je dán kombinací vstupů, „nezáleží“ na čase • Sekvenční – výstup závisí na posloupnosti (sekvenci) hodnot na vstupech, realizuje se tzv. zpětnou vazbou • Vše lze matematicky popsat – Logická funkce – Konečný automat - FSM 2007-Kubátová
Y36SAP-Logické obvody
39
20
