1.1. System komputerowy

System komputerowy (

ang.

computer system) –

układ współdziałania dwóch składowych:

1.

sprzętu komputerowego

oraz

2.

oprogramowania

,

działających coraz częściej również w ramach

sieci komputerowej

.

Można mówić o następujących poziomach takiego systemu:
1.sprzęt komputerowy,
2.

system operacyjny

(oprogramowanie systemowe),

3.oprogramowanie użytkowe (aplikacje).

1.2. Warstwy systemu

komputerowego 1

Struktura systemu komputerowego składa
się z pięciu zasadniczych warstw:
1.

sprzętowa

,

2.

system operacyjny

,

3.

programy narzędziowe

,

4.

programy użytkowe

i

5.

użytkownicy

.

1.3. Warstwy systemu

komputerowego 2

1.

Sprzęt – zapewnia podstawowe możliwości obliczeniowe (

procesor

, 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

,

AB

,

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.