1.1. System komputerowy
System komputerowy (
computer system) –
układ współdziałania dwóch składowych:
1.
oraz
2.
,
działających coraz częściej również w ramach
.
Można mówić o następujących poziomach takiego systemu:
1.sprzęt komputerowy,
2.
3.oprogramowanie użytkowe (aplikacje).
1.2. Warstwy systemu
komputerowego 1
Struktura systemu komputerowego składa
się z pięciu zasadniczych warstw:
1.
,
2.
3.
4.
i
5.
1.3. Warstwy systemu
komputerowego 2
Sprzęt – zapewnia podstawowe możliwości obliczeniowe (
, pamięć, urządzenia wejścia/wyjścia) – podstawowe
zasoby systemu komputerowego.
2. Oprogramowanie systemowe – kontroluje i koordynuje
działanie zasobów sprzętowych przez zastosowanie różnych
programów użytkowych dla różnych użytkowników. Warstwa
tworzona przez twórców systemu operacyjnego – są to
zazwyczaj wysoko wyspecjalizowani eksperci.
3. Oprogramowanie narzędziowe – dogodne interfejsy użytkowe
wspomagające
zarządzanie
zasobami
sprzętowymi
oraz
usprawniające, modyfikujące oprogramowanie systemowe,
zazwyczaj pisane przez niezależnych programistów, którzy mają
na celu usprawnienia wykonywania programów w bardziej
wygodny i wydajny sposób, a przy tym często eliminują błędy
czy też niedociągnięcia oprogramowania systemowego.
4. Oprogramowanie użytkowe – określają sposoby użycia
zasobów
systemowych
do
rozwiązywania
problemów
obliczeniowych zadanych przez użytkownika (kompilatory,
systemy baz danych, gry, oprogramowanie biurowe), tworzone
przez programistów.
5. Użytkownicy – ludzie, maszyny, inne komputery, mający
bezpośredni kontakt z oprogramowaniem użytkowym.
1.4. Układy cyfrowe
• Układ cyfrowy można przedstawić jako wielobegynnik o n binarnych
sygnałach wejściowych X = {x
1
,..., x
n
} i m binarnych sygnałach
wyjściowych Y = {y
1
,..., y
m
} . Zmienni przyjmują znaczenia z {0, 1} :
Zbiór X = {x
1
,..., x
n
} stanowi język wejściowy uklady cyfrowego.
Zbiór Y = {y
1
,..., y
m
} stanowi język wyjściowy uklady cyfrowego.
Zbiór Q = {q
1
,..., q
k
} stanowi język stanów wewnętrznych uklady
cyfrowego.
• Związki między stanami określa w postaci funkcji
Y = {X, Q }.
X
x
1
x
2
. . .
x
n
Y
y
1
y
2
. . .
y
m
Q={q
1
, q
2
,…,
q
k
}
1.5. Typy układów cyfrowych
• Istnieją trzy typy układów cyfrowych :
1. Bez pamięci (kombinacyjne) Q = 0.
2. Z ograniczoną pamięcą (sekwencyjne) Q = {q
1
,..., q
k
}.
3. Z nieograniczoną pamięcą (maczyny liczące, matematyczny model – maszyna
Turinga) Q = ∞.
• W układach kombinacyjnych stan wyjściowy Y zależy wyłącznie od obecnego w
tej chwili stanu wejściowego X.
Y = { X }.
• W układach sekwencyjnych wskutek właściwości pamiętania stanów z
poprzednich chwil, stan wyjściowy Y zależy od obecnego w tej chwili stanu
wejściowego X i tez od obecnego w tej chwili stanu pamięci Q. Stany te w
układach sekwencyjnych są określane w pewnych dyskretnych chwilach czasowych
t
1
, t
2
, t
3
, ...
Y = {X, Q}, Q = f( t
1
, t
2
, t
3
, ... )
→ Y = {X, f( t
1
, t
2
, t
3
, ... )},
• W układach z nieograniczoną pamięcią Q = ∞ stan wyjściowy Y tez zależy od
obecnego w tej chwili stanu wejściowego X i od obecnego w tej chwili stanu
pamięci Q.
Są to modeli matematyczne komputerów (maszyna Turinga).
1.6.Klasyfikację układów
cyfrowych
1.7. Podstawowe układy
kombinacyjne:
bramki
Istnieją dwa rodzaje graficznych symboli elementów logicznych:
1. symbole o kształcie prostokątnym i
2. symbole o kształtach zróżnicowanych.
1.8. Bramka
NOT
• Zmienna logiczna może mieć wartość
TRUE (PRAWDA
) lub
FALSE
(FAЈSZ
), wartość
1
lub
0
.
• Definicja.
Operacja NOT jest stosowana do pojedynczej zmiennej i
wytwarza przeciwną wartość.
Jeżeli
A
jest
1
, to
NOT A
jest równe
0
, a jeżeli
A
jest 0, to
NOT A
jest równe
1
.
Operacja NOT -
negacji
- jest zapisywana jako
A ,
lub
Ā ,
lub
A',
, lub
~A
, lub N
A
.
• Bramka
NOT
jest czasami nazywana
inwerterem
, mówimy o
„odwróceniu" wartości zmiennej lub tworzeniu jej uzupełnienia.
• Kółeczko na wyjściu symbolu wskazuje na inwersję. Kółeczka mogą
być stosowane zarówno na wejściach jak i wyjściach.
1.9. Bramka
AND
• Definicja.
Wynikiem operacji
AND -
koniunkcji
-
na
dwóch zmiennych
A
i
B
jest
1
, jeżeli
A
i
B
mają
równocześnie wartości
1
, a w przeciwnym przypadku
wynikiem operacji jest
0
.
• Operację AND "na dwóch zmiennych
A
i
B
zapisujemy
stosując symbol • (kropkę, jak w mnożeniu), lub
A∧B
,
AB
,
AB
,
A&B
, K
AB
,
• A•B = 1
tylko gdy
A = 1 i B = 1
, a dla pozostałych
kombinacji wartości zmiennych
A•B
jest równe zeru.
• Czasami symbol • (kropka) jest pomijany, tak jak
pomijany jest symbol mnożenia między zmiennymi w
zwykłym mnożeniu arytmetycznym, tj. zamiast
A•B
możemy zapisać
AB
.
1.10. Bramka AND dlu kilku
zmiennych
• Operacja AND może być zastosowana do więcej niż tylko dwóch
zmiennych. Możemy wykonać operację
AND
dlu kilku
zmiennych, tj.
A „and" B „and" C
, która jest zapisywana poprostu
ABC
.
• Wynik operacji jest równy
1, jeżeli A jest równe 1 i B jest równe
1 i C jest rowne 1.
W przeciwnym przypadku wynik jest równy
0
.
• Jest więc tylko jeden przypadek, w którym
ABC
jest równe
1,
kiedy wszystkie zmienne mają wartość
1
.
• Dowolna liczba zmiennych może być połączona operatorami
AND, ale znowu wynik operacji będzie rowny
1
tylko wtedy, gdy
wszystkie zmienne będą miały wartość
1
, a dla pozostałych
prypadków wynik operacji będzie równy
0
.
1.11. Bramka
OR
• Definicja.
Operacja
OR
zastosowana do dwóch zmiennych
A
i
B
daje w
wyniku wartość
1
, jeżeli tylko
A = 1
lub tylko
B= 1
lub zarówno
A
jak i
B
są równe
1
, a w przeciwnym przypadku (tj. gdy zarówno
A
jak i
B
są
równe
0
) wynik operacji jest równy 0.
• Symbolem przyjętym dla operacji
OR
–
alternatywy
-
jest :
A∨B
,
A+ B
, A
AB.
Symbol
+
jest stosowany w operacji dodawania arytmetycznego, ale to
nie powinno powodować niejednoznaczności zapisu, ponieważ
dodawanie arytmetyczne zwykle nie jest stosowane w wyrażeniach
boolowskich.
R
S
1.12.
Bramka
OR
dlu kilku
zmiennych
• W operacji
OR
mogą być także zastosowane więcej niż dwie
zmienne.
• Zapisalibyśmy operację z większą liczbą zmiennych,
A „or" B
„or" jako
A + B + C.
• Wynikiem takiej operacji jest
1
, jeżeli któraś ze zmiennych
A,
B
lub
C
ma wartość
1
lub jeżeli dowolne kombinacje zmiennych
A, B
lub
C
przyjmują wartości
1
.
•Jest tylko jeden przypadek, dla którego wynik operacji jest
równy
0
, gdy wszystkie zmienne
A, B i C
mają wartości
0
.
S
1.13.
BRAMKI UNIWERSALNE
Bramka
NAND
• Prawo DeMorgana określa związek między operacjami
AND i OR
. Dlatego też w
trzech podstawowych operacji
AND, OR i NOT
tylko dwie są rzeczywiście
niezbędne (
AND i NOT
lub
OR i NOT
), ponieważ trzecia operacja może być
zastąpiona wyrażeniem zapisanym za pomocą dwóch pozostałych.
• Z twierdzenia DeMorgana otrzymujemy:
• Stąd
A + B
(operacja
OR
) może być zastąpiona przez
• Wystarczą tylko dwa operatory:
AND i NOT
. Możemy więc połączyć operacje
AND i NOT
w jedną „uniwersalną" operację
NOT-AND
lub krócej
NAND
, która
może być używana do wykonywania operacji
AND, OR i NOT
, a więc do
utworzenia dowolnego wyrażenia boolowskiego.
1.14.
Bramka
NAND - Stala
Sheffera
• Operacja
NAND
dla dwóch zmiennych
A i B
jest
definiowana następująco:
1.15.
Operacje
NOT, AND i OR
realizowane za pomocą bramek
NAND
• Wszystkie trzy podstawowe operacje
AND, OR i NOT
można
otrzymać za pomocą operacji
NAND
.
• Operacja
NOT
może być otrzymana na podstawie operacii
NAND
• Operacja
OR
może być zrealizowana na podstawie operacii
NAND
:
• Operacji
AND
może być zrealizowana na podstawie operacii
NOT(NAND)
:
1.16. Bramka
NOR- Strałka
Pierce’a
• Z twierdzenia DeMorgana mamy:
• Operacja
NOR
realizującą funkcję uniwersalną
dla
dwóch zmiennych
A i B
jest definiowana następująco:
• To jest funkcja
NOT-OR,
a bramka realizująca ją jest
nazywana bramką
NOR
.
1.17. Operacje
NOT, AND i OR
realizowane za pomocą bramek
NOR
• Wszystkie trzy podstawowe operacje
AND, OR i NOT
można
otrzymać za pomocą operacji
NAND
.
• Operacja
NOT
może być otrzymana na podstawie operacii
NOR:
• Operacji
AND
może być zrealizowana na podstawie operacii
NOR
:
• Operacja
OR
może być zrealizowana na podstawie operacii
NOT
(NOR)
.
1.18. Symbole
NAND
i NOR
• W opisie układów logicznych nie stosuje się
specjalnych symboli przyporządkowanych
operacjom
NAND
czy
OR
, chociaż mają
one swoje symbole matematyczne.
• Są to
↑
dla operacji
NAND – Stala Sheffera
,
i
↓
dla operacji
NOR – Strałka
Pierce’a
.
1.19. Bramka
exclusive-OR
• Operację
exclusive-OR
zapisuje się za pomocą symbolu
.
• Dla dwóch zmiennych zapis ten ma następującą postać:
• Daje w wyniku 1, gdy
A
jest równe 1, a
B
jest równe 0 lub gdy
A
jest równe 0, a
B
jest równe 1.
• Operacja ta jest bardzo użyteczna, ponieważ umożliwia
porównanie dwóch cyfr dwójkowych (bitów) i zwraca 1 tylko
wtedy, gdy obie cyfry mają
różne
wartośći i dlatego można ją
wykorzystać w układach komparatorów cyfrowych.
1.20. Bramka
exclusive-NOR
• Dopełniająca operacja do
exclusive-OR
jest nazywana operacją
exclusive-
NOR
.
• Operację exclusive-NOR dla dwóch zmiennych zapisuje się następująco:
• Daje w wyniku 1 wtedy, gdy A = 1 i jednocześnie B=1 (składnik
AB
) albo
• wtedy, gdy
A = 0
i
B = 0
(składnik
A
B).
• Operacja ta jest bardzo użyteczna, ponieważ umożliwia porównanie dwóch
cyfr dwójkowych (bitów) i zwraca 1 tylko wtedy, gdy obie cyfry mają taką
samą wartość (tzn. gdy obie mają wartość 1 lub obie są równe 0) i dlatego
można ją wykorzystać do realizacji funkcji równoważności (tożsamości) w
układach komparatorów cyfrowych.
1.21. UKŁADY KOMBINACYJNE
• Zastosujemy podstawowe bramki do budowania
prostych układów logicznych, w których sygnały
wyjściowe zależą od wartości sygnałów występujących
na wejściach.
• Takie układy nazywa się
układami kombinacyjnymi (lub komutacyjnymi)
,
• Wartość logiczna sygnału wyjściowego zależy
wyłącznie od kombinacji wartości sygnałów
wejściowych.
• Bramki są właśnie podstawowymi układami
kombinacyjnymi i zastosujemy je do tworzenia układów
realizujących bardziej złożone funkcje kombinacyjne.
1.22. Funkcja
f = AB + C
A
B
C
AB+C
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Tablica
wartości
Układ kombinacyjny
sumacyjny.
Najprostszym sposobem zrealizowania układu jest zastosowanie
jednej bramki
AND
do wytworzenia iloczynu
AB
i jednej bramki
OR
do wytworzenia sumy
(AB) + C
.
Układ ma trzy wejścia
A, B, i C
oraz jedno wyjście
f
1
.
1.23. UKŁADY KOMBINACYJNE
Układy sumacyjne
Układ iloczynowy
1.24. Złożone układy
kombinacyjne
• Przez odpowiednie połączenie pewnej liczby podstawowych elementów
logicznych (bramek i inwertorów) można utworzyć mniej lub bardziej złożone
układy kombinacyjne. Kolejność postępowania przy syntezie kombinacyjnego
układu logicznego może być sformułowana następująco:
1) określenie funkcji przełączającej odpowiednio do postawionych
wymagań ,
2) wykonanie minimalizacji formy boolowskiej,
3) sporządzenie schematu układu, odpowiadającego zminimalizowanej
formie boolowskiej,
4) optymalizacja konfiguracji schematowej.
1.25. Sposoby opisu układów
sekwencyjnych
Automat skończony, czyli model matematyczny układu sekwencyjnego, jest
określony przez piątkę
AS = (X, Y, Q, δ, λ),
gdzie
X - alfabet wejściowy: X = {x
1
,..., x
n
}, x
B,
Y - alfabet wyjściowy: Y = (y
1
, y
2
,..., y
m
), y
B,
Q - alfabet stanów:
Q={q
0
, q
1
, q
2
,…, q
k -1
}, q
B,
δ – funkcja
przejść
: X → Q,,
λ – funkcja
wyjść
: X → Y.
• Jeżeli automat ma odrębny początkowy stan q
0
, to taki automat nazywa się
inicjalny i poznaczy się jak (A, q
o
). Jeżeli automat nie jest inicjalny, to każdy jego
stan Q = (q
0
, q
1
, ... q
k-1
) może być początkowy. Nieinicjaly automat można
rozpatrywać jak k inicjalnych automatów.
• W układach sekwencyjnych związki między stanami X, Y i Q określa się w postaci
dwóch funkcji opisujących
1. automat Mealy'ego lub
2. automat Moore'a
1.26. Automaty Mealy'ego i
Moore'a
•
Automat Mealy'ego określa się w postaci dwóch funkcji:
y(t) =λ(x(t), q(t-1)),
q(t) =δ(x(t), q(t-1)).
Pierwsza funkcja określa stan wyjść Y układu i nosi nazwę funkcji wyjść λ .
Druga funkcja określa następny stan wewnętrzny q
i nosi nazwę funkcji przejść δ.
•
Automat Moore'a określa się w postaci dwóch funkcji:
y(t) =λ( q(t)),
q(t) =δ(x(t), q(t-1)).
•
Pierwsza funkcja określa stan wyjść Y układu i nosi nazwę funkcji wyjść λ . Tu funkcji wyjść λ
zależy tylko od stany automat w moment t. Druga funkcja określa następny stan wewnętrzny q
i
nosi nazwę funkcji przejść δ.
Funkcji wyjść λ jest taka sama jak dla automatu Mealy'ego.
•
Podstawiona druga funkcja w pierwszą stwarza
y(t) =λ( δ(x(t), q(t-1))) = λ’(x(t), q(t-1)).
•
To znaczy ze jest ona podobna jak dla automatu Mealy'ego.
•
Jeśli zbiory Q, X i Y są skończone, to tworzony przez nie automat określa się jako skończony. Z
określenia δ i λ jako funkcji wynika, że dany automat jest deterministyczny. Automaty skończone
(Mealy'ego i Moore'a) są określane jako maszyny o skończonej liczbie stanów (FSM - Finite-
State Machinę).
•
Istnieją również automaty probabilistyczne, w których operuje się prawdopodobieństwami
stanów wewnętrznych Q i stanów wyjść Y.
•
Automat określa się jako zupełny, jeżeli dla wszystkich par (Q, X) ze zbioru Q
X istnieją
określone wartości funkcji δ i λ . W przeciwnym razie automat jest niezupełny.
y
q
i
λ
δ
x
b
y
q
i
λ
δ
x
a
1.27. Sekwencyjne układy
Zależnie
od
trybu
pracy
układy
sekwencyjne
dzieli się na układy
1. asynchroniczne i
2. synchroniczne.
1.28. Sekwencyjne układy
asynchroniczne
• Układy
asynchroniczne
nie
mają
wejścia
sterującego
(synchronizującego, zegarowego). Reagują one natychmiast na każdą
zmianę stanu wejściowego X, a jakakolwiek zmiana stanów Q lub Y
może w tych układach wystąpić jedynie po zmianie stanu X. Każdy
nowy stan wewnętrzny q
t+1
ustala się po niezerowym opóźnieniu
czasowym x, wynikającym z niezerowych czasów propagacji w
elementach, z których jest zbudowany dany układ. Blok zawiera
wyłącznie przerzutniki bez wejścia sterującego (zegarowego), zwane
asynchronicznymi. W układach asynchronicznych cały blok δ może
być jednak układem kombinacyjnym, a funkcja pamięci może być
wówczas uzyskana przez sprzężenie zwrotne, obejmujące ten blok.
• W układach asynchronicznych wskutek niejednakowych opóźnień
elementów układu i jego różnych dróg sygnałowych występuje
niebezpieczeństwo
wystąpienia
przejściowych
i
stabilnych
niepożądanych reakcji na zmianę stanu wejściowego. Zjawiska te
określa się jako wyścigi i hazardy. Ich analiza i wprowadzenie
odpowiednich środków zapobiegawczych przy zwiększaniu złożoności
układów analiza tak bardzo się komplikuje, że radykalnym środkiem
zaradczym jest wprowadzenie dyskretyzacji poszczególnych kroków
realizowanej operacji, czyli zastosowanie układów synchronicznych. W
układach tych wyścigi i hazardy nie występują, a ponadto synteza tych
układów jest prostsza.
1.29. Sekwencyjne układy
synchroniczne
.
• Układy synchroniczne reagują na zmianę stanu wejściowego X tylko
w dyskretnych chwilach czasowych, określonych przez zewnętrzny
sygnał periodyczny, nie będący elementem wektora X i zwany
sygnałem sterującym (zegarowym, synchronizującym, taktującym) C.
Sygnał ten jest doprowadzony do bloku pamięciowego układu. Każdy
kolejny stan wewnętrzny w układzie synchronicznym jest wytwarzany
synchronicznie z impulsami sterującymi i może być oznaczony liczbą
naturalną, odpowiadającą zwiększającej się liczbie impulsów
sterujących (zegara), liczonej od pewnego umownego zera lub
umownej chwili t. W układach synchronicznych nie występują stany
niestabilne.
• W układach asynchronicznych wskutek niejednakowych opóźnień
elementów układu i jego różnych dróg sygnałowych występuje
niebezpieczeństwo
wystąpienia
przejściowych
i
stabilnych
niepożądanych reakcji na zmianę stanu wejściowego. Zjawiska te
określa się jako wyścigi i hazardy. Ich analiza i wprowadzenie
odpowiednich środków zapobiegawczych przy zwiększaniu złożoności
układów analiza tak bardzo się komplikuje, że radykalnym środkiem
zaradczym jest wprowadzenie dyskretyzacji poszczególnych kroków
realizowanej operacji, czyli zastosowanie układów synchronicznych.
W układach tych wyścigi i hazardy nie występują, a ponadto synteza
tych układów jest prostsza.
1.30. Opis układów sekwencyjnych
1
• Opis pełny układu sekwencyjnego - Automatu
skończonego - zawiera wszystkie elementy piątki
AS = (X, Y, Q, δ, λ).
• W tym celu stosuje się :
1. Tablica przejść
2. Tablica wyjść
3. Tablica przejść i wyjść
4. Macierz przejść i wyjść
5. Graf przejść i wyjść
1.31. Opis automatów
skończonych 2
Tablica przejść
opisuje funkcję δ,
czyli każdej parze
stanów x
i
q
j
przyporządkowujemy
następny ”nowy”
stan.
Tablica wyjść
ilustruje funkcję λ ,
czyli każdej parze
stanów x
i
q
j
przyporządkowujem
y sygnał wyjściowy
y
k
.
Tablica przejść i
wyjść jednoczy
obie tablice (w
liczniku sygnały
przejść , w
mianowniku –
sygnały wyjść)
0
1
2
3
4
2/0
0/0 3/0
1/0
0/1 3/1
0/1 3/1
1/0
1/0
2/1
2/0
0/1 1/2 2/3 3/1
0/0 1/0 2/1 3/1
Graf przejść i wyjść.
Wierzchołki są
przyporządkowane stanom, a
krawędzi – sygnałom
wejściowym i sygnałom
wyjściowym
q
o
q
1
q
2
q
3
q
4
q
o
2/0
1/0
0/0 3/0
q
1
2/0
1/0
0/1 3/1
q
2
2/1
1/0
0/1 3/1
q
3
0/0 1/0 2/1 3/1
q
4
0/1 1/2 2/3 3/1
Macierz przejść i wyjść
x(t)
q(t-1)
0
1
2
3
0
3
2
1
3
1
3
2
1
3
2
3
2
1
3
3
3
3
3
3
4
4
4
4
4
x(t)
q(t-1)
0
1
2
3
0
0
0
0
0
1
1
0
0
1
2
1
0
1
1
3
0
0
1
1
4
1
2
3
1
x(t)
q(t-1)
0
1
2
3
0
3/0 2/0 1/0 3/0
1
3/1 2/0 1/0 3/1
2
3/1 2/0 1/1 3/1
3
3/0 3/0 3/1 3/1
4
4/1 4/2 4/3 4/1
1.32. Analiza automatów
skończonych
• Jeżeli mamy łańcuch sygnałów wejściowych to możemy wyznaczyć
łańcuch sygnałów wyjściowych na podstawie Grafu przejść i wyjść
lub Tablicy przejść i wyjść .
Przykład
X = 1, 2, 1, 1, 2, 2, 3, 0, 3
Q =
0,
0, 2, 1, 2, 2, 1, 1, 3, 3
Y = 0, 1, 0, 0, 1, 0, 1, 0, 1
Na podstawie analizy automatu skończonego można wyjawić następne jego stany
charakterystyczne:
1.
Stan przejściowy. W taki stan można wejść i z niego można zawsze wyjść (stany
0, 1, 2).
2.
Stan niepowracalny. W taki stan nie można się powrócić (stan 0).
3.
Stan powracalny. W taki stan można się powrócić (stany 1, 2).
4.
Stan pochłaniający. W taki stan można wejść ale niemożliwe jest wyjście z tego
stanu (stan 3).
5.
Stan izolowany. W taki stan nie można wejść i z niego nie można wyjść (stan 4).
0
1
2
3
4
2/0
0/0 3/0
1/0
0/1
3/1
0/1 3/1
1/0
1/0
2/1
2/0
0/1 1/2 2/3 3/1
0/0 1/0 2/1 3/1
1.33. Minimalizacja liczby stanów 1
• Liczbę stanów wewnętrznych w tablicy przejść i wyjść można
zmniejszyć, gdy przynajmniej dwa stany (dwa wiersze) można
zastąpić jednym bez naruszenia i prawidłowości działania układu.
• Reguły minimalizacji są następujący:
1. Stany q
i
i q
j
są wprost niezgodne, jeśli stany wyjść w
wierszach q
i
i q
j
są sprzeczne w co najmniej jednej kolumnie.
2. Stany q
i
i q
j
określamy jako wprost zgodne, jeśli dla każdego
X mają one niesprzeczne stany wyjść i przejść lub mogą stać
niesprzeczne jeśli zamienić q
i
na q
j
(lub odwrotnie).
3. Stany q
i
i q
j
są warunkowo zgodne, jeśli dla każdego X mają
one niesprzeczne stany wyjść, a stany przejść są różne.
Potrzebujemy kontynuować badanie takich stanów.
1.34. Minimalizacja liczby stanów.
Przykład
x
0
x
1
x
2
q
1
4/1
6/0
1/0
q
2
2/0
2/0
6/1
q
3
4/1
2/0
3/0
q
4
4/1
3/0
3/0
q
5
6/0
6/0
5/1
q
6
5/0
6/0
2/1
q
1
q
2
q
3
q
4
q
5
q
2
-
q
3
2-6
-
q
4
6-3;
3-1
3-2
-
q
5
6-2;
6-5
-
q
6
5-2
5-2
q
1
q
2
q
3
q
4
q
5
q
2
x
-
q
3
6-2
x
-
q
4
x
x
x
-
q
5
x
6-2 ;
6-5
x
x
-
q
6
x
5-2
x
x
5-2
x
1
x
2
x
3
q
1
4/1
2/0
1/0
q
2
2/0
2/0
2/1
q
4
4/1
1/0
1/0
1. Początkowa tablica 1
przejść i wyjść
2. Tablica 2 par stanów warunkowo zgodnych. Do
danej kratki wpisujemy znak (przekreślamy ją), jeśli
odpowiadające jej stany q
i
i q
j
są wprost niezgodne. Jeśli
stany q
i
i q
j
wyznaczające daną kratką są warunkowo
zgodne, to wpisujemy do niej wynikające z tych stanów
rożne stany następne, poza q
i
i q
j
.
3. Tablica 3 par stanów zgodnych. Badamy na zgodność
stany w nie przekreślonych kratkach. W kratce 13 wpisane
są stany 2-6. Badamy kratkę 26. Ona jest nie przekreślona
(wpisane są stany 5-2). Zostawajmy kratkę bez zmian. W
kratce 14 wpisane są stany 6-3 i 3-1. Badamy kratkę 63. Ona
jest przekreślona. To znaczy że musimy przekreślić kratkę 14
i t. d.
4. Tablica 4 z
minimalizowaną liczbą
stanów. Równoważnymi są
następne stany: 1-3, 2-5, 2-6 i
5-6. Relacja równoważności
jest zwrotną, symetryczną i
przechodnia. Następne stany w
zaznaczonych grupach są
równoważne: 1-3, 2-5-6.
Z
każdej
takiej
grupy
zestawiamy po jednemu stanu i
otrzymujemy tablicę
1.35. Przerzutnik
• Przerzutniki - to układy sekwencyjne Moore'a, które mają
jednobitowy stan wewnętrzny, identyczny ze stanem
wyjściowym:
• Q = Y, oraz stan wejściowy równy stanowi wzbudzeń: X.
• Stan logiczny przerzutnika Q jest równoważny stanowi
wyjścia Y.
• Przerzutnik jest elementarnym automatem dwustanowym,
gdyż
Q {0, 1}. Gdy przerzutnik znajduje się w jednym z tych
dwóch stanów, wówczas zmiana stanu przerzutnika może
nastąpić jedynie w wyniku podania na jego wejścia nowych
informacji (lub wyłączenia zasilania).
• Przerzutniki dzieli się na asynchroniczne (bez odrębnego
wejścia sterującego C - zegara) i synchroniczne (z
wejściem sterującym C).
• Do
opisu
właściwości
logicznych
przerzutników
wykorzystuje się tablice przejść, tablice funkcyjne, tablice
wzbudzeń i funkcje przejść (równania funkcyjne). Poza tym
są stosowane także grafy przejść i wykresy czasowe.
P = Q̅
X
Y = Q
x
1
x
2
C (zegar)
Q
Ogolny symbol
przerzutnika
X, Q, Y, P, C { 0, 1 } ;
x
1
x
2
= 11 – wzbroniony;
YP { 01 10 }
1. 36. Przerzutniki
asynchroniczne SR z bramek
NOR
• Najprostszym przerzutnikiem asynchronicznym jest statyczny przerzutnik SR (Set-
Reset). Aby go odróżnić od synchronicznego statycznego przerzutnika SR, są stosowane
także w literaturze oznaczenia sr lub wz. Jest stosowane także oznaczenie RS.
• Stany wewnętrzne i zewnętrzne wejść S, R są jednakowe.
• Zmiany stanów przerzutnika są wywołane ustawieniem na odpowiednim wejściu stanu
logicznego 1, zgodnie z tablicą przejść. Przerzutnik może zmieniać stan tylko wówczas,
gdy S = R̅. Przy SR = 00 przerzutnik pozostaje w stanie „nie zmienionym" czyli Q' = Q
i odpowiednio Y’ = Y. Stan ten zależy od tego, które z wejść było „ostatnio" w stanie 1,
tzn. czy przed stanem SR = 00 był stan 01 czy 10. Stan SR = 11 jest logicznie
zabroniony, gdyż przy przejściu z SR = 11 do 00 nie można w sposób jednoznaczny
określić stanu Q'P' (stany 01 i 10 są równouprawnione). Od przerzutników wymaga się,
aby na ich wyjściach zawsze były komplementarne stany logiczne. Oznacza to, że w
przerzutniku SR powinien być spełniony warunek S R = 0.
0
1
RS=
10
RS=
01
RS=
01
RS=
00
RS=
10
RS=
00
Tablica przejść Q
Q’
RS
Q
0
0
0
1
1
0
11-
za
b.
0
0
0
1
1
1
0
1
S
R
1
1
Y=Q
P=
Q̅
1. 37. Przerzutniki
synchroniczne
• Budowa synchronicznego przerzutnika SR jest
pokazana na rysunku. Sygnały wejściowe przerzutnika
są przenoszone (z negacją) przez bramki wejściowe
tylko przy stanie sygnału sterującego C = 1. Przy C =
0 stan Q przerzutnika synchronicznego nie zależy od
stanów wejściowych S, R..
S
R
1
1
Y=Q
P=Q̅
C
&
&
1. 38. PROGRAMOWALNE
UKŁADY LOGICZNE (PLD)
Zajmiemy
się
elementami
o
dużej
„elastyczności
konstrukcyjnej"
-
uniwersalnymi
-
nazywanymi
programowalnymi układami logicznymi
PLD
programmable logie device
.
Układy PLD mają wewnętrzną strukturę,
która może być konfigurowana do postaci
różnych układów kombinacyjnych, a często
także układów sekwencyjnych. Układy PLD
są
stosowane
w
celu
znacznego
zmniejszenia liczby elementów w złożonych
systemach cyfrowych.
1. 39. PROGRAMOWALNE UKЈADY LOGICZNE
(PLD)
• Programowalne układy logiczne zawierają bramki, a w niektórych przypadkach
także przerzutniki, rozmieszczone tak, że połączenia między tymi elementami
mogą być zmieniane w celu uzyskania różnych funkcji logicznych. Kombinacyjne
układy PLD zawierają tylko podstawowe bramki, zwykle ułożone w matryce
bramek AND i OR w sposób umożliwiający realizowanie sum iloczynów, czyli
wyrażeń boolowskich w postaci sumacyjnej. W sekwencyjnych układach PLD na
wyjściach dodano przerzutniki.
• Aby zapewnić swobodne konfigurowanie układów PLD trzeba dysponować
środkami umożliwiającymi zmianę połączeń prowadzących do tworzenia różnych
układów logicznych. Pierwotnie sposobem umożliwiającym jednokrotnie i trwale
wybór konfiguracji układu było zastosowanie w wytwarzanych układach
scalonych bezpiecznikowych elementów półprzewodnikowych (fuse - łączników)
- układy scalone programowalne za pomocą elementów przepalanych.
Początkowo elementy te wewnątrz struktury układu nie są naruszone (nie
przepalone), co zapewnia wszystkie możliwe połączenia. Wybrane elementy
łączące (łączniki) są za pomocą specjalnego programatora PLD przepalane
(rozpylane) przez użytkownika w celu zachowania tylko żądanych połączeń, czyli
ustalenia ostatecznej konfiguracji układu.
• Zazwyczaj programator układów PLD jest dołączany do komputera, a
odpowiednie oprogramowanie „tłumaczy" opis funkcji, które chcemy zrealizować
na odpowiadający im wzór połączeń wewnętrznych, konfigurujących żądany
układ. Elementy łączące są jednokrotnie „przepalane" i wzór połączeń nie może
już być zmieniony. Takie układy PLD, jak układy scalone z elementami
przepalanymi, które użytkownik może sam programować na biurku, są
nazywane programowalnymi (field programmable).
1. 40. PROGRAMOWALNE
UKЈADY LOGICZNE (PLD)
Układy scalone z elementami przepalanymi były opracowane
w
latach 70, obecnie zaś istnieją układy w wersłach PLD, w
których
zastosowano
technologię
stosowaną
w
kasowalnych
(wielokrotnie
programowalnych) pamięciach tylko do odczytu.
W
takich
układach
konfiguracja
połączeń
zależy
od
zapamiętanej
informacji
dwójkowej
w
odpowiednich
elementach
pamiętających. Komórki pamiętające występują przy każdym
elemencie łączącym (łączniku), aby przy pamiętaniu wartości
logiczneł np. 0 utrzymywać jego połączenie (zwarcie), a przy
pamiętaniu wartości np. 1 rozłączyć (rozewrzeć) je.
Układy PLD, w których zastosowano technologię pamięci i
półprzewodnikowych cechuje możliwość wielokrotnej, szybkiej
zmiany połączeń i konfigurujących.
1. 41. Programowalne matryce logiczne (PLA)
• W kombinacyłnych układach PLD przyjęta struktura logiczna umożliwia
generowanie sumacyjnych wyrażeń boolowskich wielu zmiennych.
• Na rysunku przedstawiono schemat logiczny układu kombinacyjnego PLD
mającego szesnaście wejść (I0 - I15) i osiem niezależnych wyjść (F0- F7).
• Liczba wełść i wyłść może być różna dla różnych układów PLA.
1. 42. Możliwe przypadki programowania wejść
bramki AND w programowalnej matrycy
logicznej
• (a) nieprogramowania
wełść,
• (b) podawany na wełście
bramki sygnał wełściowy
nie zanegowany,
• (c) zaprogramowany
sygnał zanegowany,
• (d) żadna wartość sygnału
wełściowego nie została
dołączona do wełścia
1.43. Przykład
1.44.
Programowaln
y układ
logiczny
- FPGA -
(AMD
PAL16L8)
1.45. Literatura
1. Barrz Wilkinson. Uklady cyfrowe.
W-wa komunikacji i
łącznośći.Warszawa. 2003.
2. Józef Kalisz. Podstawy elektroniki
cyfrowej. Wydawnictwo
komunikacji i łączności.
Warszawa, 2003.
3. Wikipedia.