Wykłady z Podstaw informatyki sem.2

MODUŁY PROGRAMU

- Moduł Crt - zawiera wszystkie podprogramy do współpracy z ekranem i klawiaturą konsoli, podprogramy do tworzenia okienek tekstowych, podprogramy do tworzenia koloru i tła wyprowadzanych znaków oraz podprogramy do generowania dźwięku. Poza nimi moduł zawiera szereg deklaracji zmiennych.

- Moduł DOS - zawiera podprogramy do wykonywania operacji systemowych tj. poszukiwanie katalogów, określenie daty i czasu, określenie pojemności dysków i wykonywanie funkcji systemu DOS. Zawiera również deklarację zmiennej DOS Error, której po wykonaniu pewnych podprogramów jest przypisywana dana typu integer. Jeśli ta dana ma wartość równą zeru, to uważa się , że wykonanie podprogramu było pomyślne. W przeciwnym razie wartość danej określa rodzaj błędu.

- Moduł Graph - zawiera obszerną bibliotekę podprogramów graficznych : - deklaracja sterowników graficznych (BGI), -automatyczne wykrycie sterowników graficznych

- Moduł BGI Driv - związany jest z modułem Graph i umożliwia dostosowanie parametrów procedur komunikacji z urządzeniami wyjściowymi do posiadanego hardware'u (device driver)

- Moduł BGI Font - umożliwia stosowanie różnych wielkości, kształtów liter oraz stylów pisania.

ZBIÓR DYREKTYW KOMPILATORA

Dyrektywy - służą do ustalenia odpowiednich cech kompilatora, przekazywania kompilatorowi informacji i sterowania kompilacją warunkową.

Stos - elementarna struktura danych definiowana przez sposób dostępu. Istnieją tylko dwie operacje: - push lub put - czyli dokładnie elementu na szczycie stosu; -i top lub get - czyli zabieranie elementu ze szczytu stosu.

Sterta - obszar w przestrzeni adresowej procesu przeznaczonego do przechowywania dynamicznie tworzonych struktur danych tego procesu, zwiększany w kierunku odwrotnym do organizowanego w procesie.

ALGEBRY BOOLE'A I ICH ZASTOSOWANIE

Dwuelementowa algebra Boole'a. Definicja Algebry Boole'a:

• dany jest zbiór złożony z dwóch różnych elementów (0,1);

• na elementach tego zbioru określamy działania: mnożenia boolowskiego, dodawania oraz negacji w taki sposób, aby otrzymać znowu elementy zbioru (0,1)

Algebry Boole'a znajdują zastosowanie do opisania pracy układów, które mają się znajdować w dwóch stanach tzw. sieci dwubiegunowych. Stanowi nieprzewodzenia sieci przyporządkowuje się 0 algebry Boole'a, a stanowi przewodzenia 1.

Aksjomaty algebry Boole'a:

0'=1, x ^ 1=x, x v 1=1, x ^y=y ^x, x ^x=x, x ^(y ^z)=(x ^y)^z, (x v y)^z=(x ^z)v(y ^z), 1'=0, x v 0=x, x ^0=0, x v y=y v x, x v x=x, x v(y v z)=(x v y)v z, (x ^ y)v z=(x v z)^(y v z), x''=x, (x ^y)'=x' v y', x ^x'=0, (x v y)'= x' ^y', x v x'=1

ZWIĄZKI ALGEBRY BOOLE'A Z ALGEBRĄ ZBIORÓW

Algebra zbiorów:

• elementami są podzbiory jakiegoś ustalonego zbioru;

• suma boolowska to zbiór tych punktów, które należą przynajmniej do jednego z tych zbiorów;

• iloczyn boolowski dwóch zbiorów to ich część wspólna;

• negacja to uzupełnienie zbiorów;

• zero to podzbiór pusty, nie zawierający żadnych elementów.

ZWIĄZKI ALGEBRY BOOLE'A Z ALGEBRĄ ZDAŃ

Algebra zdań:

• elementami są zdania, a właściwie zmienne p, q, r,..., za które możemy wstawiać różne zdania;

• do zdań p, q, r,..., (tzw. zmiennych zdaniowych) dołączamy dwa słowa: prawda i fałsz (0,1) tzw. stałe zdaniowe;

• ze zmiennych oraz stałych za pomocą trzech spójników: lub, i, nie (v ,^, ') budowane są nowe zdania, tzw. funkcje zdaniowe. Funkcje te przyjmują wartości prawda lub fałsz;

• dwie funkcje zdaniowe uważane są za równe, jeśli dla każdego szczególnego podstawienia w miejscu p, q, r,..., dowolnych zdań otrzymamy w wyniku zdanie albo oba fałszywe albo oba zdania prawdziwe;

• algebra zdań jest algebrą logiki i w takiej interpretacji aksjomaty A1-A10* wyrażają prawa logiki np. p i p'=0.

Zagadnienie odwrotne : dla danej tabeli pracy sieci - zbudować sieć.

Wielomiany Boole'a standardowa postać wyrażeń boolowskich.

Przez sumowanie tych części można otrzymać każdą funkcję boolowską dwóch zmiennych.

Poniższa tabela przedstawia wartość czterech funkcji zwanych wielomianami minimalnymi.

x	y	P00 x' ∧ y'	P01 x' ∧ y'	P1o x ∧ y'	P11 x ∧ y
0	0	1	0	0	0
0	1	0	1	0	0
1	0	0	0	1	0
1	1	0	0	0	1

Tabela - wartość wielomianów minimalnych dwóch zmiennych

Weźmy funkcję f=x ∨ y' i przedstawmy ją w postaci sumy wielomianów minimalnych.

Tworzymy tabelę pracy funkcji f.

x	y	F=x ∨ y'	Wielomian
0	0	1	P00
0	1	0	P01
1	0	1	P10
1	1	1	P11

Zapisujemy funkcję f w postaci sumy wielomianów minimalnych :

F(x,y) = x ∨ y' = (1 ∧ P₀₀) ∨ (0 ∧ P₀₁) ∨ (1 ∧ P₁₀) ∨ (1 ∧ P₁₁) = (1 ∧ (x' ∧ y')) ∨ (0 ∧ (x' ∧ y)) ∨ (1 ∧ (x ∧ y')) ∨ (1 ∧ (x ∧ y)) = (x' ∧ y') ∨ (x ∧ y') ∨ (x ∧ y)

Otrzymana postać funkcji to wielomian boolowski dwóch zmiennych.

Lista różnych wielomianów boolowskich zawierających dwie zmienne jest równa 2^k = 16, gdzie k jest liczbą wielomianów minimalnych k = 2ⁿ = 4 , gdzie n jest liczbą zmiennych.

Wielomiany te można przedstawić :

Lp.	Funkcja f(x,y)	Współczynniki przy Pij
				x'∧y'	x∧y'	x'∧y	x∧y
1.		0	0	0	0
2.	x'∧y'	1	0	0	0
3.	x∧y'	0	1	0	0
4.	x'∧y	0	0	1	0
5.	x∧y	0	0	0	1
6.	y'	1	1	0	0
7.	x'	1	0	1	0
8.	(x∧y')∨(x'∧y)	0	1	1	0
9.	(x'∧y')∨(x∧y)	1	0	0	1
10.	x	0	1	0	1
11.	y	0	0	1	1
12.	x'∨y'	1	1	1	0
13.	x∨y'	1	1	0	1
14.	x'∨y	1	0	1	1
15.	x∨y	0	1	1	1
16.	1	1	1	1	1

RÓŻNICA SYMETRYCZNA

Różnicę symetryczną określa się w następujący sposób :

Definicja

x ≠ y = (x ∧ y') ∨ (x' ∧ y)

tabela

≠	0	1
0	0	1
1	1	0

zachodzi : x ≠ x = 0

Różnica symetryczna nazywa się również dodawaniem modulo 2

DYSJUNKCJA SHEFFERA

Dysjunkcję Sheffera określa się w sposób następujący :

Definicja

x  y = x' ∨ y'

tabela

	0	1
0	1	1
1	1	0

Definiowanie operacji boolowskich za pomocą dysjunkcji Sheffera :

1. x' = x  x (negacja boolowska)

2. x ∨ y = x'  y\ = (x  x)  (y  y) (suma boolowska)

3. x ∧ y = (x  y)' = (x  y)  (x  y) (iloczyn boolowski)

Wnioski: wszystkie operacje boolowskie : negacje , suma i iloczyn - dwóch zmiennych da się sprowadzić do dysjunkcji Sheffera

Liczba wielomianów minimalnych trzech zmiennych jest równa 2³ = 8.

Każdą funkcję boolowską f(x,y,z) trzech zmiennych można przedstawić jako sumę wielomianów minimalnych , każdy pomnożony przez odpowiedni współczynnik równy 0 lub 1.

Przykład:

Znależć możliwie prostą sieć zawierającą wyłączniki x,y,z , która przewodzi tylko dla następujących stanów wyłączników :

0,1,0; 1,0,0; 1,0,1; 1,1,0; 1,1,1;

1. Budujemy tabelę pracy sieci ( w kolumnę f wpisujemy jedynki zgodnie z zadawanymi stanami przewodzenia sieci)

2. Do tabelki pracy sieci dopisujemy kolumnę P wielomianów minimalnych. Wpisuje się ten wielomian minimalny , który jest równy jeden dla zadanego układu zer i jedynek wartości zmiennych x , y , z

3. Zapisujemy funkcję f(x , y , z) jako sumę iloczynów kolumn 4 i 5 tabelki pracy , tzn. mnożymy wartości funkcji f przez wielomian minimalny i wyniki sumujemy f(x,y,z)=0

4. Opuszczamy wszystkie składniki równe zero i upraszczamy otrzymane wyrażenie ( za pomocą aksjomatów i znanych tożsamości)

f(x,y,z) = (x' ∧ y ∧ z') ∨ (x ∧ y' ∧ z') v (x ∧ y' ∧ z) ∨ (x ∧ y ∧ z') ∨ (x ∧ y ∧ z) =

(x' ∧ (y ∧ z')) ∨ (x ∧ (y' ∧ z')) ∨ (x ∧ (y' ∧z)) ∨ (x ∧ (y ∧ z')) ∨ (x ∧ (y (y z)) =

(x'∧ (y ∧ z')) ∨ (x ∧ [(y' ∧ z') ∨ (y' ∧ z) ∨ (y ∧ z') ∨ (y ∧ z)] )=

(x' ∧ (y ∧ z')) ∨ (x ∧ 1) =

(x' ∧ (y ∧ z')) ∨ x =

(x' ∨ x) ∧ ((y ∧ z') ∨ x) =

1 ∧ ((y ∧ z') ∨ x) =

(y ∧ z') ∨ x

ALGORYTMICZNE METODY MINIMALIZACJI FUNKCJI BOOLOWSKICH

1. Metoda Quineia McCluskeya

Proces przeszukiwania F_n składa się z dwóch etapów :

1. wyznaczenie F_s i F_z

2. wyznaczenie F_n i F_s

Przykład:

Wyznaczyć minimalną formułę boolowską równoważną formule :

F₁= x₁'x₂'x₃x₄' + x₁'x₂'x₃x₄ + x₁'x₂x₃x₄ + x₁x₂x₃'x₄' + x₁x₂x₃'x₄ + x₁x₂x₃x₄' + x₁x₂x₃x₄

Etap pierwszy (operacja sklejania)

1. Wpisujemy kombinacją zer i jedynek (wektory) odpowiadające kolejnym pełnym iloczynem (kolumna a) iloczynom tym przyporządkowujemy numery kodując wektory w systemie dziesiętnym

2. Szeregujemy te kombinacje wg liczby jedynek. Otrzymujemy w ten sposób grupy z n=1,2,... jedynek (kolumna b)

3. Porównujemy każdą kombinację należącą do grupy i-tej z każdą kombinacją należącą do grupy i + 1 . Jeżeli dwie takie kombinacje różnią się tylko na jednej pozycji , to kombinacje te sklejamy zastępując pozycje różniące się symbolem φ (fi). Wykorzystujemy tu związek xy +xy' = x. Tworzymy nową tablicę (kolumna d) a w poprzedniej oznaczamy znacznikiem √ kombinacje używane przy dokonywaniu sklejeń

4. Kontynuujemy procedurę usuwając kombinacje powtarzające się i łącząc kombinacje różniące się na jednej pozycji

5. Procedurę kończymy , gdy nie ma już możliwości dokonywania dalszych sklejeń (kolumna d)

6. Tworzymy zbiór kombinacji nie mogących podlegać dalszemu sklejeniu. Do zbioru tego należą te kombinacje , które nie mogą być zabrane do dalszego sklejania.

a)

2	0010
3	0011
6	0110
7	0111
12	1100
13	1100
14	1110
15	1111

b)

2	0010	V
3	0011	V
6	0110	V
12	1100	V
7	0111	V
13	1101	V
14		V
15		V

c)

2,3	001φ	∨
2,6	0φ10	∨
3,7	0φ11	∨
6,7	011φ	∨
6,14	φ110	∨
12,13	110φ	∨
12,14	11φ0	∨
7,15	φ111	∨
13,15	11φ1	∨
14,15	111φ	∨

d)

2	3	6	7	0φ1φ
6	7	14	15	φ11φ
12	13	14	15	11φφ

Ważne d) pomijamy zestawy numerów nie prowadzących do nowych kombinacji np. 2,6,3,7 = 2,3,6,7

Etap drugi (operacja wyboru zbiorów minimalnych iloczynów , tzw. Implikantów)

Wyniki poprzedniego etapu przedstawiamy w tabeli :

x1' * x3	2 , 3 , 6 , 7
x2 * x3	6 , 7 , 14 , 15
x1 * x2	12 , 13 , 14 , 15

Poszukujemy najmniejszego zbioru wierszy , mającego jedynki we wszystkich kolumnach.

W rezultacie otrzymujemy , że :

F₁ = x₁'x₂'x₃x₄' + x₁'x₂'x₃x₄ + x₁'x₂x₃x₄' + x₁'x₂x₃x₄ + x₁x₂x₃'x₄' + x₁x₂x₃'x₄ + x₁x₂x₃x₄' + x₁x₂x₃x₄ = (x₁'x₃) ∨ (x₁x₂)

2. Metoda tablic Karnaugha

Przy minimalizacji korzysta się z faktu , że dla dowolnego A zachodzi zależność : (A ∧ x) ∨ (A ∧ x') = A czyli dwa człony iloczynowe wyrażenia , różniące się jedną negacją można zastąpić jednym członem bez literału różnicującego. Działanie takie nosi nazwę sklejania , a sklejane człony to wyrażenia sąsiednie.

Założenia metody Karnaugha :

1. Do przeprowadzenia operacji sklejania wykorzystuje się specjalne tablice.

2. Do opisu pól tablic wykorzystuje się kod Gray'a.

3. Jeśli w tak zbudowanej tablicy dwa symbole leżą obok siebie to odpowiadają one wyrażeniom sąsiednim , które można kleić.

4. Sąsiadujące ze sobą pola tablicy obwodzi się linią i opisuje jednym wyrażeniem boolowskim.

5. Skleja się ze sobą 2,4,8,... kratki tablicy.

UKŁADY I AUTOMATY

Układ logiczny - model urządzenia mający m wejść i n wyjść określany niekiedy jako tzw. „skrzynka”. Sygnały na wyjściach i wejściach mogą umownie przyjmować wartości 0 i 1. Stan wejścia wektor wejściowy o m składowych stan wyjścia wektor wyjścia o n składowych.

x- zbiór możliwych wektorów wejściowych x

y- zbiór możliwych wektorów wyjściowych y

Implementacja skalarna

m wejść dwuwartościowych

n wyjść dwuwartościowych

Implementacja wektora

Jedno wejście 2^m wartościowe

Jedno wyjście 2ⁿ wartościowe

Automatem typu Mealy'ego - nazywamy uporządkowaną piątkę M=<X , S , Y , δ , λ> w której :

X = {x₁ , x₂ , ... , x_n} - zbiór liter wejściowych

S = {s₁ , s₂ , ... , s_n} - zbiór stanów wewnętrznych

Y = {y₁ , y₂ , ... , y_n} - zbiór liter wyjściowych

przy czym zbiory te są kończone i nie są puste

δ : Dδ → S funkcje przejść

λ: Dλ → Y funkcje wyjść

D_δ c X _x S

D_λ c X x S

Funkcja przejść przyporządkowuje więc każdej parze złożonej z litery wejść i stanu obecnego i należącej do D_δ stan następny. Funkcja wyjść przyporządkowuje każdej parze złożonej z litery wejściowej i stanu obecnego i należącej do D_λ - litery wyjściowej. Można to zapisać w sposób następujący :

V < x^k , s^k > ∈ D_δ δ : < x^k , s^k > → s^{k + 1} = δ (x^k , s^k)

V < x^k , s^k > ∈ D_λ λ : < x^k , s^k > → y^{k + 1} = λ (x^k , s^k)

Indeksy k , k+1 odpowiadają kolejnym punktom dyskretnej skali czasu. Gdy automat modeluje logiczny układ synchroniczny , dyskretna skala czasu ma charakter zewnętrzny. Natomiast gdy automat modeluje logiczny układ asynchroniczny , dyskretna skala czasu jest wytwarzana przez sam układ.

Automatem (skończonym) typu Moore'a - nazywamy automat jak w definicji Maley'ego w którym D_λ c S .Tak więc funkcja wyjść przyporządkowuje każdemu stanowi należącemu do D_λ literę wyjściową co zapisujemy

Vs ∈ D_λ λ : s^k → y^k = λ { s^k }

W szczególnym przypadku gdy

D_δ = X x S , D_λ = X x S (albo dla typu Moore'a D_δ = S) automat nazywamy automatem zupełnym.

Przejście od układu logicznego do automatu ( i odwrotnie ) ma charakter zmiany oznaczeń :

Układ logiczny Automat

X x

X X

Y y

Y Y

Q s

Q{q} S

δ δ

λ λ

wejście x ∈ X → → wyjście y ∈ Y

gdzie

• duża litera oznacza zbiór

• mała litera oznacza element

• wektory są wyróżnione pogrubieniem

• litery greckie oznaczają funkcję

• funkcje wektorowe oznaczono literami greckimi z podkreśleniem

Oznaczenie :

x , y , z - wektory

m , p , n - długość wektorów

u , w , r - liczba elementów zbiorów X , S , Y

Zachodzi :

2^m >= u

2^p >= w

2ⁿ >= v

Przejście od układu sekwencyjnego do automatu polega na podaniu funkcji f₁,f₂,f₃ takich , że :

f₁ : x → x

f₂ : q → s

f₃ : y → y

oraz na następującym określeniu funkcji δ i λ automatu :

δ (x , s) = f₂ (δ (f₁ ^-1 (x) , f₂ ^-1 (s))

λ (x , s) = f₃ (λ (f₁ ^-1 (x) , f₂ ^-1 (s))

Bijekcja w matematyce to relacja będąca sunjekcją i jednocześnie injekcją , surjekcja , odwzorowanie zbioru A na zbiorze B - takie , że każdy element zbioru B przyporządkowany jest co najmniej jednemu elementowi zbioru A

Injekcja w matematyce jest relacją przyporządkowującą jeden element zbioru A i tylko jeden element zbioru B

Inaczej można powiedzieć , że jest to relacja zanurzenia zbioru w zbiorze lub odwzorowanie zbioru w zbiór. Przejście od automatu do układu sekwencyjnego polega na podaniu funkcji q₁,q₂,q₃ takich , że :

q₁ : x → x' c x

q₂ : s → q' c q

q₃ : y → y' c y

przy czym liczby naturalne m , p , n muszą być takie , aby :

u = x <= 2^m

w = s <= 2^p

v = y <= 2ⁿ

oraz na następującym określeniu funkcji δ i λ dla układu sekwencyjnego

δ (x,q) = q₂(δ (q₁^-1(x) , q₂^-1(q) ) )

λ (x,q) = q₃(λ (q₁^-1(x) , q₂^-1(q) ) )

Przykład:

Zaprojektować automat z alfabetem wejściowym {a,b,c} i alfabetem wyjściowym {0,1}. Jeżeli w trzech kolejnych skokach układu symbol a pojawia się w wyjściu parzystą ilość razy, to sygnał wyjściowy ma wynosić 0 , jeżeli nieparzystą to sygnał wyjściowy ma wynosić 1. Sygnał wyjściowy jest więc określony tylko co trzeci skok układu.

Wypisujemy wszystkie możliwe sekwencje wejściowe i wyjściowe i odpowiadające im sekwencje wyjściowe :

	a	b	c	a	b	c
m	n	p	q	-	-	-
n	r	s	t	-	-	-
p	u	v	w	-	-	-
q	x	y	z	-	-	-
r	m	m	m	1	0	0
s	m	m	m	0	1	1
t	m	m	m	0	1	1
u	m	m	m	0	1	1
v	m	m	m	1	0	0
w	m	m	m	1	0	0
x	m	m	m	0	1	1
y	m	m	m	1	0	0
z	m	m	m	1	0	0

Wiersze r , v , w , y , z oraz s , t , u , x są identyczne - zatem można tablicę uprościć

	a	b	c	a	c	b
m	n	p	q	-	-	-
n	r	s	s	-	-	-
p	s	r	r	-	-	-
q	s	r	r	-	-	-
r	m	m	m	1	0	0
s	m	m	m	0	1	1

Ponieważ zmienione zostały oznaczenia w tablicy , można dodatkowo uprościć identyczne wiersze p i q. Zatem otrzymamy

	a	b	c	a	c	b
m	n	p	p	-	-	-
n	r	s	s	-	-	-
p	s	r	r	-	-	-
r	m	m	m	1	0	0
s	m	m	m	0	1	1

Ponieważ w otrzymanej tablicy kolumny b i c są identyczne mogą być zastąpione jedną kolumną. Wprowadzając nowe oznaczenia ( o zamiast a i 1 zamiast b i c ; 1, 2, 3, 4, 5 odpowiednio zamiast m , n , p , r , s ) otrzymuje się tablicę przejść / wyjść i graf sterów zaprojektowanego automatu :

	0	1	0	1
1	2	3	-	-
2	4	5	-	-
3	5	4	-	-
4	1	1	1	0
5	1	1	0	1

Automat ten można zrealizować również jako automat Moore'a

	x 1 0		y
1	2	3	-
2	4	5	-
3	5	4	-
4	6	7	-
5	7	6	-
6	2	3	0
7	2	3	1

SYNTEZA WŁAŚCIWA - PROJEKTOWANIE AUTOMATÓW

Synteza właściwa - to konstrukcja tablicy przejść - wyjść automatu , którego sposób pracy podano w sposób słowny. Synteza polega na przyporządkowaniu każdej parze złożonej z litery sekwencji wejściowej i odpowiadającej jej litery sekwencji wyjściowej osobnego stanu i takim dobraniu funkcji , żeby automat pracował w zadany sposób.

UKŁADY KOMBINACYJNE

Układem kombinacyjnym nazywamy układ logiczny bez pamięci , a więc układ w którym istnieje jednoznacznie zależność między zmienną wyjścia (sygnałem wyjściowym) a zmienną wejściową

Układ kombinacyjny o m wejściach i m wyjściach binarnych przyporządkowuje każdemu wektorowi wejściom x o m składowych binarnych wektor wyjściowy y o mn składowych binarnych. Układ taki realizuje więc funkcję wektorową λ , czyli n funkcji m zmiennych.

Układ ten może być zadany za pomocą opisu słownego lub za pomocą tablicy. Synteza układu z użyciem układów małego stopnia scalania (SSI - Small Scale Integration) polega na przejściu od układu o danych charakterystykach zew. Do sieci złożonych z elementarnych układów logicznych , tj. do schematu logicznego. Synteza sprowadza się więc do otrzymania możliwie najprostszego zestawu form boolowskich , przedstawiających zależności :

Y_j = λ_j (x₁ , x₂ , x₃ , ... , x_n) dla j= 1,2,3,...,n

	α0	α1	α2	α3	Nazwa	Symbol i sposób przedstawiania za pomocą operatorów + ,- , *
f0	0	0	0	0	Stała 0	0
f1	0	0	0	1	Iloczyn (i -AND)	xy
f2	0	0	1	0	Iloczyn z zakazem dla y	x - y=xy'
f3	0	0	1	1	Zmienna x	x
f4	0	1	0	0	Iloczyn z zakazem dla x	y - x = x'y
f5	0	1	0	1	Zmienna y	y
f6	0	1	1	0	Suma modula 2	x ⊕ y = x'y + xy'
f7	0	1	1	1	Suma (lub - OR)	x + y
f8	1	0	0	0	Operacja Pierce'a (NOR)	x ↓ y = (x+y)' = x'y'
f9	1	0	0	1	Równoważność	x ⊗ y = x'y' + xy
f10	1	0	1	0	Negacja y (NOT)	y'
f11	1	0	1	1	Implikacja x przez y	y → x = x + y'
f12	1	1	0	0	Negacja x (NOT)	x'
f13	1	1	0	1	Implikacja y przez x	x → y = x' + y
f14	1	1	1	0	Operacja Sheffera (NAND)	x  y = x'y' = x' + y'
f15	1	1	1	1	Stała 1	1

Funkcjonalnie pełnym zestawem bramek logicznych nazywamy zestaw bramek realizujących wszystkie działania tworzące funkcjonalnie pełny zestaw operatorów logicznych

Wielowejściową bramką i (lub) nazywamy bramkę realizującą działanie Π a_i ( ∑ a_i )

Gdzie symbole Π , ∑ oznaczają iloczyn lub sumę boolowską dla większej od 2 czynników

Wielowejściową bramkę „uogólnioną” NAND („uogólnioną” NOR) nazywamy bramkę realizującą działanie

NAND - oznacza NOT-AND

NOR - oznacza NOT-OR

ZASADY SYNTEZY UKŁADÓW KOMBINACYJNYCH MAŁEGO STOPNIA SCALENIA

Złożony układ kombinacyjny otrzymujemy łącząc bramki (elementarne układy logiczne) zgodnie z następującymi zasadami:

1. wyjście bramki może być dołączone do jednego lub więcej innych bramek

2. wyjścia dwóch bramek nie mogą być łączone ze sobą bezpośrednio

Etapy syntezy układów kombinacyjnych:

1. na podstawie opisu pracy układów konstrułuje się tablicę funkcji λ

2. na podstawie tablicy otrzymuje się uproszczone formuły opisujące układ ( formuły te mają postać sumy , iloczynu lub iloczynu sumy)

3. dostosowuje się otrzymane wyrażenie do wybranego zestawu elementarnych układów kombinacyjnych i tworzy schemat logiczny

BLOKI KOMBINACYJNE ŚREDNIEGO STOPNIA SCALENIA MULTIPLEKSERY I DEKODERY

Multiplekserem - nazywamy układ kombinacyjny o m wejściach adresowych (a₁, … ,a_m)=a, k=2^m, wejściach informacyjnych u₀, … u_k-1, dodatkowym wejściem strofującym b' oraz wyjściem y.

Działanie multipleksera:

Sygnał pojawiający się na wyjściu y jest równy sygnałowi pojawiającemu się na wejściu informacyjnym u_i wybranym przez wektor a: wektor ten traktowany jest jako liczba dwójkowa musi być równy i. Dodatkowo musi być b=0 gdyż dla b=1 następuje zerowanie wyjścia.

Mamy więc y=b'u_i dla i=ε(a_i) lub y=b'Σ_i=0 do (2^m-1) WB (a_i)*u_i

WB(a_i) oznacza tu iloczyn pełnych zmiennych adresowych, a u_i - sygnał na odpowiednim wejściu informacyjnym. Otrzymane wyrażenie jest identyczne z kanoniczną postacią sumy dla funkcji boolowskiej. Oznacza to, że funkcja o m zmiennych może być realizowana za pomocą multipleksera o m wejściach adresowych; dla każdego z 2^m wejść informacyjnych należy przyjąć sygnał 0 lub 1 w zależności od wartości funkcji dla danego adresu.

Operator MUX - inny zapis działania multipleksera:

Y=b' MUX(u_o, u₁, … , u_2m-1, a₁, a₂, … , a_m)

Obecnie są produkowane multipleksery o m=2, 3, 4 wejściach.

Rozważyć należy przypadek podziału zbioru zmiennych {x₁, x₂, … , x_m} na dwa rozłączne podzbiory A i I liczące odpowiednio n elementów i m-n elementów.

A={x_i1, … , x_in}

I={x_in+1, … , x_im}

Otrzymujemy realizację funkcji boolowskiej m zmiennych za pomocą głównego multipleksera o n wejściach adresowych; postać m-n zmiennych doprowadza się do wejść informacyjnych multipleksera głównego przez układy małego stopnia scalenia lub przez warstwę multiplekserów.

Zamiast układów scalonych małej skali integracji można użyć multipleksery realizujące funkcje f₁, f₂, f₃, (f₀=0, więc można ją pominąć) otrzymuje się wtedy dwupoziomową strukturę multiplekserów. Wartości funkcji n podane na wejścia informacyjne multiplekserów pierwszego poziomu o zmiennych adresowych x₁, x₂ wynoszą odpowiednio (należy pamiętać o zmianie kolejności wskaźników 0, 1, 3, 2 z tablicy Karnaugha na 0, 1, 2, 3 dla wyznaczonych funkcji):

U₀1=1

Metoda wyznaczania funkcji f_i

1) Budowa funkcji f_j rozpoczyna się od narysowania tablic Karnougha dla funkcji f(x1, x2, x2, x4) i f*(x1, x2, x2, x4). Kolumny tablic odpowiadają kombinacją zmiennych adresowych x3, x4. numery kolumn odpowiadają funkcji f_i.

Funkcje f_i mogą być realizowane w układach małej skali integracji i podawane na wejścia informacyjne multipleksera.

Dla danej funkcji f* schemat multipleksera z funkcjami f₁ i f₂ zrealizowanymi za pomocą układów małej skali integracji przyjmuje postać: rysunek

Realizacja struktury dwupoziomowej jest możliwa po zdefiniowaniu funkcji u równych (f0=0 oraz f3=1 są funkcjami trywialnymi): rysunek

2) Dla rozważanej funkcji (tablica prawdy) można przyjąć inny podział zmiennych x1, x2, x3, x4 i założyć że zmiennymi adresowymi będą x1 i x3 a zmiennymi informacyjnymi x2 i x4

Jeżeli A={x1, x3} i I={x2, x4}, to wtedy w tablicy Karnough każdy kwadrat składający się z czterech kratek odpowiada kombinacjom adresowym x1, x3.

Funkcje dwóch zmiennych x2, x4 odpowiadające kolejnym kwadratom mają teraz postać:

3) Dla rozważanej funkcji (tablicy prawdy) można przyjąć jeszcze inny podział zmiennych x1, x2, x3, x4 i założyć że zmiennymi adresowymi będą x2, x3 i x4, a zmienną informacyjną x1. w tym przypadku rozważana funkcja f czterech zmiennych (dana w tablicy prawdy) będzie realizowana na multiplekserze o 3 wejściach adresowych i jednoelementowym zbiorze zmiennych informacyjnych.

Każdemu numerowi kombinacji trzech zmiennych odpowiadają dwie różne kratki dla x1=0 i x1=1

F⁰ i f¹ oznaczają części tablicy Karnough odpowiednio dla x1=0 i x1=1

Różnych od siebie par kratek będzie 8. rozwiązaniem zatem będzie 8 funkcji f₀ … f₇ zmiennej x₁.

Funkcje te buduje się korzystając z następujących reguł:

1. jeśli wartości funkcji f_j są takie same: 0 lub 1 to będze odpowiednio f_j=0 lub f_j=1 (wartości funkcji f_i nie zależą od x₁)

2. jeśli wartości funkcji f_j w obu kratkach są różne od siebie i odpowiadają wartościom x1(x1) to f_j=x (f_j=x1)

Jeśli rozważać się będzie funkcję niezupełną f* to stosując tablicę Karnough i w/w reguły otrzymać można funkcje f₀, … , f₇

W metodzie syntezy brak jest jednoznacznych kryteriów podziału zbioru zmiennych na adresowe i informacyjne i niezbędne jest stosowanie prób.

METODY SYNTEZY KOMBINACYJNEJ I ZASADY KODOWANIA STANÓW DLA UKŁADÓW MAŁEGO STOPNIA SCALENIA

Liczniki

Licznikiem nazywamy układ logiczny sekwencyjny przeznaczony do zliczania impulsów wejściowych. Pojawienie się kolejnego impulsu wejściowego powoduje zmianę stanu licznika, przy czym kolejnym stanom odpowiada liczba zliczonych do osiągnięcia tego stanu impulsów wejściowych. Najczęściej zliczaniu podlegają impulsy zegarowe , a dodatkowe wejścia służą do programowania sposobu liczenia.

Szeregowy licznik Modulo16 pracuje zgodnie z naturalnym cyklem podanym w takiej samej tablicy jak dla licznika równoległego. W chwili rozpoczynania liczenia licznik jest wyzerowany. Opadające zbocze pierwszego impulsu powoduje zmianę stanu 0 na 1, przerzutnika q₀. Przerzutnik q₁ nie zmienia się gdyż zmiana stanu stanowi zbocze narastające, a przerzutnik Rs działa od zbocza opadającego. Opadające zbocze drugiego impulsu zegarowego powoduje zmianę stanu 1 na 0 przerzutnika q₀ co wywołuje zmianę 0 na 1 przerzutnika q₁.Po impulsie 15 Licznik wraca do stanu 0000.

Rejestry

Rejestr - blok funkcjonalny zbudowany z przerzutników , służący do przechowywania w komputerze informacji w postaci cyfrowej.

Przerzutnik - (flip-flop FF ) element mogący przyjmować na przemian dwa stany 0 i 1, używany jako1-bitowy element pamięci , stosowany do budowy rejestrów.

Rejestr synchroniczny - rejestr zbudowany z przerzutników synchronicznych , które pobierają informacje z wejścia i przekazują na wyjście w chwilach określanych przez zmiany doprowadzanego do niego sygnału.( zbocza impulsu zegarowego) . W pozostałych chwilach stan rejestru synchronicznego się nie zmienia. Oprócz pamiętania informacji rejestry mogą wykonywać mikrooperacje np. przesuwanie, zwiększanie.

Rodzaje rejestrów:

• rejestr równoległy - składa się z zestawu nie powiązanych ze sobą przerzutników, z układu zerowania .Informacje cyfrowe są wpisywane równolegle do przerzutników po ich uprzednim wyzerowaniu

• rejestr szeregowy - składa się z zestawu przerzutników połączonych ze sobą kaskadowo.

---