Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
1
Algebra Boole’a (1847)
〈{0,1}, +, 〉
• dodawanie i mno enie (logiczne) – działania domkni te w {0,1}
∈
⋅
∈
+
⇒
∈
x
x
x
x
x
x
• identyczno ci 0,1 – neutralne wzgl dem działa dwuargumentowych
x
x
x
x
x
=
⋅
=
+
⇒
∈
• przemienno działa
x
x
x
x
x
x
x
x
x
x
+
=
+
⋅
=
⋅
⇒
∈
• istnienie negacji (elementu przeciwnego)
=
+
∧
=
⋅
⇒
∈
∃
⇒
∈
x
x
x
x
x
x
• wzajemna rozdzielno działa
x
x
x
x
x
x
x
x
x
x
⋅
+
⋅
=
+
⋅
⇒
∈
x
x
x
x
x
x
x
x
x
x
+
⋅
+
=
⋅
+
⇒
∈
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
2
Aksjomaty Huntingtona – formalna definicja algebr Boole’a (1907)
〈U u u
u
× 〉
• domkni to działa + i × w zbiorze U
U
U
U
∈
×
∈
+
⇒
∈
x
x
x
x
x
x
• przemienno
U
U
U
∈
×
=
×
∈
+
=
+
⇒
∈
x
x
x
x
x
x
x
x
x
x
• obecno elementów neutralnych
x
x
x
=
∅
+
⇒
∈
∀
∈
∃∅
U
U
x
x
x
=
ℑ
×
⇒
∈
∀
∈
∃ℑ
U
U
• istnienie elementów przeciwnych
U
U
U
U
U
∈
−
+
∈
−
∃
∧
∈
×
∈
∃
⇒
∈
−
−
x
x
x
x
x
x
x
• wzajemna rozdzielno działa
x
x
x
x
x
x
x
x
x
x
×
+
×
=
+
×
⇒
∈ U
x
x
x
x
x
x
x
x
x
x
+
×
+
=
×
+
⇒
∈ U
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
3
Logika dwuwarto ciowa (1)
• negacja
1
0
0
1
=
⇒
=
∧
=
⇒
=
x
x
x
x
• suma logiczna
x
+ z = 1 ⇔ x = 1 ∨ z = 1
• iloczyn logiczny
x ⋅ z
= 1 ⇔ x = 1 ∧ z = 1
Wła ciwo ci
– zasadnicze twierdzenia
• podwójna negacja
x
x
=
• idempotentność
x ⋅ x
= x,
x
+ x = x
• dominacja
x ⋅
0 = 0,
x
+ 1 = 1
• pochłanianie
x ⋅
( x + z ) = x,
x
+ x z = x
• uproszczenie
z
x
z
x
x
⋅
=
+
⋅
)
(
z
x
z
x
x
+
=
⋅
+
• minimalizacja
x
z
x
z
x
=
⋅
+
⋅
x
z
x
z
x
=
+
⋅
+
)
(
)
(
• łączność
)
(
)
(
z
y
x
z
y
x
⋅
⋅
=
⋅
⋅
)
(
)
(
z
y
x
z
y
x
+
+
=
+
+
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
4
Logika dwuwarto ciowa (2)
Prawa de’Morgana:
podstawowe
uogólnione
• negacja sumy
z
x
z
x
⋅
=
+
∏
∑
=
=
=
=
=
n
i
i
i
n
i
i
i
x
x
1
1
• negacja iloczynu
z
x
z
x
+
=
⋅
∑
∏
=
=
=
=
=
n
i
i
i
n
i
i
i
x
x
1
1
Suma wykluczaj ca
(suma modulo 2)
x
z
z
x
z
x
z
x
z
x
z
x
⊕
=
+
⋅
+
=
⋅
+
⋅
=
⊕
)
(
)
(
Wła ciwo ci
z
x
z
x
z
x
⊕
=
⊕
=
⊕
)
(
)
(
z
y
x
z
y
x
⊕
⊕
=
⊕
⊕
0
=
⊕ x
x
,
1
=
⊕ x
x
x
x
=
⊕ 0
,
x
x
=
⊕1
z
x
z
x
z
x
z
x
z
x
⋅
+
⊕
=
⋅
⊕
⊕
=
+
)
(
z
x
z
x
x
⋅
=
+
⊕
)
(
z
x
z
x
x
⋅
=
⋅
⊕
)
(
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
5
Funkcje logiczne (1)
Tablica prawdy
(truth table) – zbiór wszystkich par (x
∈{0,1}
n
, f (x))
}
1
,
0
{
)
,
,...,
(
)
(
:
}
1
,
0
{
)
,
,...,
(
1
2
1
2
∈
=
∈
=
∀
⇔
∈
x
x
x
f
f
x
x
x
f
n
n
n
x
x
F
F
F
∈
⇒
∈
f
f
F
F
F
F
∈
∧
∈
+
∧
∈
⋅
⇒
∈
g
f
g
f
g
f
g
f
o
)
(
)
(
,
Funkcje monotoniczne
• pozytywnie
)
|
(
)
|
(
:
)
(
)
(
i
i
i
i
y
f
x
f
y
x
i
f
f
y
x
y
x
y
x
f
f
f
f
⇒
∀
⇔
⇒
z
x
z
x
AND
⋅
=
)
,
(
z
x
z
x
OR
+
=
)
,
(
• negatywnie
)
|
(
)
|
(
:
)
(
)
(
i
i
i
i
y
f
x
f
y
x
i
f
f
y
x
y
x
y
x
p
p
p
f
⇒
∀
⇔
⇒
z
x
z
x
NAND
⋅
=
)
,
(
z
x
z
x
NOR
+
=
)
,
(
Funkcje niemonotoniczne dwóch zmiennych
z
x
z
x
XOR
⊕
=
)
,
(
z
x
z
x
EQV
⊕
=
)
,
(
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
6
Funkcje logiczne (2)
)
|
,
,...,
(
)
|
(
1
2
i
i
n
i
a
x
x
x
x
f
a
f
=
=
x
Twierdzenie Shannona
)
0
|
(
)
1
|
(
)
(
i
i
i
i
f
x
f
x
f
x
x
x
⋅
+
⋅
=
))
1
|
(
(
))
0
|
(
(
)
(
i
i
i
i
f
x
f
x
f
x
x
x
+
⋅
+
=
Niech
x
x
x
x
=
=
0
1
oraz
, więc
a
a
x
x
−
=
1
)
(
(a = 0 lub 1)
• postać dyzjunkcyjna (dis-junctio – rozłączam)
∑
∏
∈
=
=
=
n
s
n
i
i
a
s
n
n
x
a
a
a
f
x
x
x
f
f
2
a
x
1
)
(
1
2
1
2
)
,
,...,
(
)
,
,...,
(
)
(
• postać koniunkcyjna (con-junctio –łączę)
∏
∑
∈
=
+
=
=
n
s
n
i
i
a
s
n
n
x
a
a
a
f
x
x
x
f
f
2
a
x
)
)
,
,...,
(
(
)
,
,...,
(
)
(
1
)
(
1
2
1
2
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
7
Funkcje logiczne (3)
RóŜnica boolowska
)
1
|
(
)
0
|
(
)
(
i
i
i
f
f
f
dx
d
x
x
x
⊕
=
jeśli d f
(x) / dx
i
= 0 , to f (x) nie zależy od x
i
, jeśli d f (x) / dx
i
= 1 , to f (x) =x
i
Funkcja komplementarna – negacja funkcji
∏ ∑
∑ ∏
∈
∈
−
∈
∈
=
=
=
I
i
S
s
i
a
s
I
i
S
s
i
a
s
C
i
s
i
s
x
x
f
f
)
(
1
)
(
)
(
)
(
x
x
Funkcja dualna
∏ ∑
∑ ∏
∈
∈
∈
∈
−
=
=
=
I
i
S
s
i
a
s
I
i
S
s
i
a
s
D
i
s
i
s
x
x
f
f
)
(
)
(
1
)
(
)
(
x
x
System funkcjonalnie pełny
Zbiór funkcji, za których pomoc mo na wyrazi dowoln funkcj
{NOT, AND, OR}, {NAND}, {NOR}
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
8
Minimalizacja funkcji logicznych
Min(i)termy
(konstytuenty jedynki)
)
0
)
(
0
)
(
&
1
)
(
1
)
(
(
...
)
(
2
2
1
1
=
⇒
=
=
⇒
=
⇔
∈
=
x
x
x
x
m
x
i
i
a
i
a
i
a
i
i
m
f
f
m
x
x
x
m
k
k
• dyzjunkcyjna postać normalna (kanoniczna) funkcji
∑ ∏
∑
=
=
=
i
s
i
a
s
i
i
n
s
x
m
x
x
x
f
f
)
(
1
2
)
(
)
,
,...,
(
)
(
x
x
Max(i)termy
(konstytuenty zera)
)
1
)
(
1
)
(
&
0
)
(
0
)
(
(
...
)
(
2
2
1
1
=
⇒
=
=
⇒
=
⇔
∈
+
+
=
x
x
x
x
M
x
i
i
a
i
a
i
a
i
i
M
f
f
M
x
x
x
M
k
k
• koniunkcyjna postać normalna (kanoniczna) funkcji
∏ ∑
∏
=
=
=
i
s
i
a
s
i
i
n
s
x
M
x
x
x
f
f
)
(
1
2
)
(
)
,
,...,
(
)
(
x
x
Metody minimalizacji
• tradycyjne – siatki Karnaugh, metoda Quine’a-Mc’Cluskey’a
• nowe – metoda ESPRESSO (heurystyczna redukcja wymiaru+ Q-McC)
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
9
Bramki (funktory) logiczne proste
x+z
x
x
⊕z
x
⊕z
x+z
x+z
x
⋅
z
x
⋅
z
x
⋅
z
z
x
z
x
z
x
z
x
z
x
z
x
z
x
z
x
x
Bramka wielowejściowa – realizująca standardową funkcję m zmiennych
m
m
x
x
x
x
x
x
AND
⋅
⋅
⋅
=
...
)
,...,
,
(
2
1
2
1
,
m
m
x
x
x
x
x
x
OR
+
+
+
=
...
)
,...,
,
(
2
1
2
1
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
10
Sieci logiczne
s=x
⊕y⊕z
z
x
y
c=
(x
⊕y)⋅z+x⋅y
s
x
0
z
x
1
x
2
x
3
x=s
⋅z⋅x
0
+s
⋅z⋅x
1
+s
⋅z⋅x
2
+s
⋅z⋅x
3
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
11
Bramki (funktory) logiczne zło one
multiplekser i demultiplekser
s
⋅
x
x
s
⋅
x
0
+s
⋅
x
1
s
x
0
x
1
s
s
⋅
x
=
=
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
12
Bramki (funktory) logiczne zło one
g
s=x
⊕
y
⊕
z
c
–
AT
= 1
c
+
=
(x
⊕
y
)c
–
+xy
c
+
A
= 7
T
s
= 4
T
c
= 4
x
y
s
A
= 2
T
= 2
A
= 2
T
= 2
c
–
c
+
x
y
s
A
= 2
T
= 2
g
s=x
⊕
y
⊕
z
c
+
=
(x+y)c
–
+xy
p=x
⊕
y
p=x
+y
A
= 7
T
s
= 4
T
c
= 3
AT
= 1
AT
= 1
AT
= 1
AT
= 1
AT
= 1
AT
= 1
AT
= 1
sumator
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
13
Elementy pami taj ce – przerzutniki
asynchroniczny przerzutnik RS
Q
Q
S
R
Q
S
R
Q
R
S Q
t
+1
0
0
Q
t
0
1
1
1
0
0
1
1
—
synchroniczny przerzutnik D
D
C
C D Q
t
+1
0 — Q
t
1 0
0
1 1
1
Q
Q
Q
D
C
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
14
Rejestry
RD
Q
0
D
0
WR
Q
1
D
1
Q
2
D
2
Q
n
–1
D
n
–1
RD
Q
0
D
in
C
Q
1
Q
2
Q
n
–1
D
out
rejestr równoległy i szeregowy
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
15
Ocena zło ono ci układów cyfrowych (1)
Sterowalność i obciąŜalność bramek – charakterystyki technologiczne
• liczba wej (fan-in) i obci alno wyj (drive)
Charakterystyki rozmiar– czas
(Area– Time, AT)
• bramka prosta monotoniczna (AND, OR, NAND, NOR) – A = 1, T = 1
• bramka prosta niemonotoniczna (XOR, XNOR), MUX2 – A = 2, T = 2
• bramka monotoniczna m-wej ciowa – A = m –1, T = log m
• inwerter (NOT) – A = 0, T = 0
Sieć logiczna
• rozmiar A – suma liczby bramek przeliczeniowych
• czas T – najdłu sza cie ka propagacji zmiany stanu wej cia do wyj cia
Układ sekwencyjny
• czas stabilizacji wyj cia (latency) lub najkrótszy cykl zmiany wej
Inne charakterystyki
• w układach arytmetycznych – liczba przeliczeniowych bramek XOR
• w układach programowalnych – liczba komórek LUT (look-up table
– programowalna matryca ROM zadaj ca funkcj kilku zmiennych)
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
16
Funkcje rekursywne
x = x
1
| | x
2
| | x
3
| | … – zło enie wektorów zmiennych wej ciowych
{f
1
, f
2
, f
3
, … } – zbiór funkcji
Funkcje nierekursywne (non-recursive)
f
i
=f
i
(x)=f
i
(x
i
), i=1,2,3,…
Funkcje rekursywne (recursive)
f
i
= f
i
( x ) =
ϕ
i
( f
1
( x ), f
2
( x ), … f
j
( x )) j = 1, 2, 3, … i – 1
Funkcje rekursywne skojarzone (recursive associative)
a) pojedyncze (szeregowe) f(x) = f
(n)
(x
n
, f
(n–1)
(x
n
–1
, f
(n–2)
(x
n
–2
, f
(1)
(x
1
)…)))
b) grupowe f(x) = f
(n)
(x
n
, … , x
p
, f
(p)
(x
p
–1
, … , x
r
, f
(r)
(x
r
–1
, f
(k)
( x
k
–1
, … x
1
)…)))
Funkcje rekursywne nieskojarzone (recursive non-associative)
a) pojedyncze f
k
(x) = f
(k)
(x
k
, f
(k–1)
(x
k
–1
, f
(k–2)
(x
k
–2
, f
(1)
(x
1
)…)))
b) grupowe (wspólne funkcje cz ciowe dla ró nych wyj )
Problem prefiksowy
– wyznaczanie funkcji rekursywnej skojarzonej
• – asocjacyjny operator binarny (suma, iloczyn, …)
y
i
= x
i
•y
i
–1
, y
0
= x
0
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
17
Przesuni cia
metody
• rejestr przesuwny (shift register) –zmienny czas wykonania
• przesuwnik kaskadowy (barrel shifter) – stały czas wykonania
a)
b)
x
0
MPX MPX MPX MPX MPX MPX MPX MPX
MPX MPX MPX MPX MPX MPX MPX MPX
MPX MPX MPX MPX MPX MPX MPX MPX
2
0
2
1
2
2
ShL-1
x
1
x
2
x
3
x
4
x
5
x
6
x
7
ShL-2
ShL-4
RS
x
i
x
i 2
n
x
i
( )
MPX
ShL
x
i+
2
n
ShR
−
0
Przesuwnik kaskadowy: a) multiplekser b) schemat dla przesuni cia w lewo
Je li suma potrzebnej liczby przesuni
w lewo i prawo nie jest du a
mo na realizowa tylko przesuni cia w jedn stron
Logika układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
LUC –
18
Nieco o technologii
Niektóre bramki logiczne (logic gate) maj bardzo prost realizacj CMOS,
w której wykorzystuje si bramki transmisyjne (pass-transistor gate)
Multiplekser 2-we
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
1
J zyki opisu sprz tu – HDL
HDL – Hardware Description Language
Podstawowe elementy opisu:
jednostka (entity) – „czarna skrzynka”, która ma wej cia i wyj cia
architektura (architecture) – opis wn trza jednostki,
strukturalny
behavioralny
J zyki VHDL, AHDL, VERILOG – ró ni si składni , semantyk , etc.
EDA (Electronic Design Automation)
Narz dzia automatyzacji projektowania elektroniki EDA, takie jak:
Virtex, Leonardo, Cadence, etc. akceptuj i generuj opis HDL
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
2
J zyki opisu sprz tu – VHDL
z
x
y
g
c
s
entity blok
h
z
x
y
g
c
s
architecture bramki of blok
h
entity blok is
port (x,y,z:in bit; c,s:out bit, g,h:inout bit);
end entity blok;
architecture bramki of blok is
begin
g<=x and y;
h<=x xor y;
s<=z xor h;
c<=(z and h) or g;
end architecture bramki;
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
3
Sieciowy opis architektury (1)
definicja bramek
definicja jednostki
(wej cia, wyj cia, dwukierunkowe)
definicja architektury
(struktura – opis działania)
entity AND2 is
port (x,y:in bit; z:out bit);
end entity AND2;
architecture bramka of AND2 is
begin
z<=x and y;
end architecture bramka;
entity XOR2 is
port (x,y:in bit; z:out bit);
end entity XOR2;
architecture bramka of XOR2 is
begin
z<=x xor y;
end architecture bramka;
entity OR2 is
port (x,y:in bit; z:out bit);
end entity OR2;
architecture bramka of OR2 is
begin
z<=x or y;
end architecture bramka;
UWAGA: z<=x<=y
oznacza
z
←
(x
≤
y)
, czyli przypisanie
z
wartości logicznej
x
≤
y
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
4
Sieciowy opis architektury (2)
architecture netlist of blok is
component AND2
port (a,b:in bit; z:out bit);
end component AND2;
component OR2
port (a,b:in bit; z:out bit);
end component OR2;
component XOR2
port (a,b:in bit; z:out bit);
end component XOR2;
signal g,h,r:bit;
begin
g1:XOR2 port map (x,y,h);
g2:AND2 port map (x,y,g);
g3:AND2 port map (z,h,r);
g4:OR2 port map (g,r,c);
g5:XOR2 port map (z,h,s);
end architecture netlist;
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
5
Sieciowy opis architektury (3)
definicja jednostki
entity XOR2 is
port (x,y:in bit; z:out bit);
end entity XOR2;
architecture bramka of XOR2 is
begin
z<=x xor y;
end architecture bramka;
składnik
(
component
) – uniwersalny opis zdefiniowanej wcze niej jednostki
component XOR2
port (a,b:in bit; z:out bit);
end component XOR2;
instancja
– konkretne odwzorowanie składnika danego typu w sieci
g1:XOR2 port map (x,y,h); – domniemane automatyczne
g1:XOR2 port map (y=>b,h=>z,x=>a); – domniemane jawne
albo z odwołaniem do biblioteki (
work
) i architektury
(bramka)
g1:entity work.XOR2(bramka) port map (y=>b,h=>z,x=>a);
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
1
J zyki opisu sprz tu – VERILOG (1)
c
a
b
p
q
s
module blok (a,b,c,p,q,r,s)
r
x
z
module blok (a,b,…,p,q,…)
input a,b,…;
// wej cia a,b,…
output p,q,…;
// wyj cia p,q,…
wire x,y,…;
// sygnały wewn trzne x,y,…
assign z=a&b;
// funkcja AND
assign x=a^b;
// funkcja XOR
assign p=z;
//
assign q=z|c&x; // funkcja OR/AND
assign r=x;
// funkcja XOR
assign s=x^c;
// funkcja XOR
endmodule;
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
2
J zyki opisu sprz tu – VERILOG (2)
Wektory, magistrale, wywołania
module blok (a,b,…,p,q,…)
input [3:0] a,b; // wej cia a[3],a[2],…,b[1],b[0]
output p,q,…;
// wyj cia p,q,…
wire x,y,…;
// sygnały wewn trzne x,y,…
blok inst1 (…); // wywołanie modułu
assign s=x^c;
// funkcje wyj cia
endmodule;
// wywołanie modułu „blok” z parametrami z1,z2,…
blok inst1 (z1,z2,…,s1,s2,…);
// utworzony moduł inst1 o architekturze takiej jak
// moduł „blok”
[i:j] xx // xx[i],xx[i+1],…,xx[j]
Symboliczny opis układów cyfrowych
© Janusz Biernat
,
AK1-L-09-Logika.doc
HDL–
3
J zyki opisu sprz tu – VERILOG (3)
Wektory, magistrale, wywołania
inout [3:0] a,b; // dwukierunkowe a, b
przypisania:
jawne (explicit)I
wire s;
assign s = x ^ c;
implikowane (implicit)
wire s = x & y;
wektory:
xx[k,m]
{xx[2:1], xx[2:1]} = {xx[2], xx[1], xx[2], xx[1]}
{2{xx[2:1]}, a} = {xx[2], xx[1], xx[2], xx[1], a}
parametry – stałe
parameter xsize = 3;