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;
Wyszukiwarka
Podobne podstrony:
IS wyklad 14 15 01 09 MDW id 22 Nieznany
ei 2005 09 s004 id 154186 Nieznany
PIF2 2007 Wykl 09 Dzienne id 35 Nieznany
cennik 09 2013 id 109720 Nieznany
metodologia z logika id 295026 Nieznany
09 15 id 53452 Nieznany (2)
Homines2011 09 Walkowiak id 205 Nieznany
kol1, kol2, sem 3, 09 10 id 239 Nieznany
ei 2005 09 s144 id 154191 Nieznany
ei 2005 09 s150 id 154192 Nieznany
cwicz 21 02 09 Gerbera id 66461 Nieznany
LOGIKA 6 id 271991 Nieznany
2008 09 01 id 428503 Nieznany
logika 7 id 271993 Nieznany
Egz dzienne 09 2009 id 151170 Nieznany
Logika id 517887 Nieznany
cwicz 21 02 09 strzalki id 6646 Nieznany
ceny mieszkan 09 2010 id 109841 Nieznany
ei 2005 09 s022 id 154187 Nieznany
więcej podobnych podstron