U1 vs U2
- inny zapis (dla ujemnych w U2 oprócz zanegowania modułu trzeba dodać „1”)
- w U1 ewentualną „1” przeniesienia dodajemy do najmniej znaczącego bitu, w U2 tę „1” pomijamy
- gdy na pozycji znakowej wyniku występuje „1” uzyskujemy NKB wyniku negując bity modułu i:
w U1 umieszczamy przed nim znak „-„
w U2 dodajemy „1” i umieszczamy przed NKB znak „-„
Cechy charakterystyczne:
- U1 - podwójna reprezentacja zera („0.0000” lub „1.1111”), konieczność zarezerwowania czasu na podwójne sumowanie
- U2 - jednoznaczna reprezentacja liczb, jednokrotne sumowanie
Aksjomaty algebry Boole'a:
a+b E B a*b E B
a+b = b+a a*b = b*a
a*(b+c) = a*b + a*c a+b*c = (a+b)(a+c)
a+o = a a*i = a
a+na = i a*na = o
Twierdzenia algebry Boole'a:
a+(b+c)=(a+b)+c a*(b*c) = (a*b)*c
a+a*b = a a*(a+b) = a
a*(b+c) = a*b + a*c
a+b*c = (a+b)(a+c)
a+a = a a*a = a
a+i = i a*o = o
n(a+b) = na*nb
n(a*b) = na+nb
no = i ni = o
na = a
SFP
Zbiór operacji takich, że każda funkcja logiczna może być przedstawiona za pomocą argumentów stałych 0 i 1 oraz tych operacji. Funkcje logiczne sumy, iloczynu i negacji tworzą SFP. Jeżeli mówimy, że funkcje NAND i NOR tworzą SFP, to znaczy, że za ich pomocą można przedstawić każdą złożoną funkcję logiczną.
Udowodnienie:
NAND
a = a*a = a/a
a+b = nn(a+b) = n(na*nb) = a/b = [a/a] / [b/b]
a*b = nn(a*b) = n(a/b) = [a/b] / [a/b]
NOR
a = a+a = a|a
a+b = nn(a+b) = n(a|b) = [a|b] | [a|b]
a*b = nn(a*b) = n(na+nb) = na|nb = [a|a] | [b|b]
Synteza układów kombinacyjnych
Zespół czynności, które na podstawie założeń dotyczących działania układów doprowadzają do schematu logicznego układu. Schemat powinien zawierać tylko niezbędną ilość elementów i spełniać pewne wymagania optymalności. Synteza ma za zadania zmniejszenie liczby elementów.
KPF
KPS-yi =
KPI-yi=
Wyznaczanie KPS z tablicy prawdy - rozpatrujemy tylko te wiersze, dla których y=1, przy czym zmienne o wartości 1 wchodzą do iloczynu w postaci afirmacji, a 0 w postaci negacji.
KPI - na odwrót
Minimalizacja funkcji - polega na tym, aby funkcja miała jak najmniej literałów
Literał - afirmacja lub negacja zmiennej
Elementarny iloczyn - iloczyn dowolnej liczby różnych literałów danej funkcji
PNS - suma różnych elementarnych iloczynów
Implikant - funkcja tych samych argumentów argumentów następującej własności: dla wszystkich zespołów wartości argumentów, dla których implikant jest równy 1, również dana jest funkcja jedności.
Implicent - j.w. z zerem
Prosty implikant (implicent) - implikant (implicent) będący iloczynem (sumą) elementarnym, który zmniejszany o dowolny literał przestaje być implikantem (implicentem)
Metoda tablic Karnaugh
- metoda graficzna, max do 6 zmiennych
- opis wartości zmiennych w kodzie Gray'a
- proste implikanty (implicenty) na tablicy wyznaczamy łącząc z sobą sąsiednie „1” („0”) w grupy zawierające 2k klatek
- literały o wartości „1” wchodzą do iloczynu elementarnego w postaci afirmacji, o wartości „0” w postaci negacji
- do sumy odwrotnie
- dobór grup należy utworzyć grupy obejmujące wszystkie „1” („0”) funkcji. Należy utworzyć jak najmniej jak największych grup.
- „1” lub „0” mogą być w różnych grupach jednocześnie
- wartości nieokreślone mogą wchodzić do dowolnych grup
Automat skończony z pamięcią:
Uporządkowana piątka:
<X, S, Y, δ, λ>
X - zbiór stanów wejściowych
S - wewnętrznych
Y - wyjściowych
δ - funkcja przejść
λ - funkcja wyjść
Automaty synchroniczne - stan wejść może oddziaływać na układ pamięciowy w ściśle określonych momentach wyznaczonych sygnałem na specjalnym wejściu taktującym
Automaty asynchroniczne - stan wejść wpływa w sposób ciągły na stan układu pamięciowego
Zasady tworzenia tablic przejść-wyjść
- jeśli znamy liczbę stanów wewnętrznych, tablicę p-w można utworzyć bezpośrednio z opisu
- jeśli nie, konieczna jest budowa grafu stanów automatu
- w grafach i tablicach nie wyróżnia się wśród sygnałów wejściowych stanu zegara, a jedynie zaznacza się stan wejść automatu w momentach zmiany stanu sygnału zegarowego
Przejście z postaci skróconej do KPF
PNS - iloczyny elementarne wymnaża się przez wyrażenia xi+nxi = 1
PNI - do sum elementarnych dodaje się wyrażenie xi*nxi = 0
Gdzie xi - brakujące literały
Bezpośrednio z postaci skróconej PNS lub PNI:
1.Wypisuje się ciągi binarne odpowiadające iloczynom bądź sumom elementarnym
2.W miejsce brakujących literałó wpisuje się 0 i 1
3.Wypisuje się dziesiętne odpowiedniki utworzonych ciągów
4.Zapisuje się KPF
Faktoryzacja - polega na przekształceniu postaci końcowej funkcji, zmniejszając liczbę literałów
x1*x2 + x1*x3 = x1*(x2+x3)
(x1+x2)(x1+x3) = x1+x2*x3
W realizacji stykowej należy zawsze przeprowadzić faktoryzację.
Sposoby realizacji układów kombinacyjnych
*realizacja na elementach logicznych
- budowa tablicy wartości funkcji
- minimalizacja funkcji
- realizacja na zadanych elementach
*realizacja na dekoderach i elementach logicznych
- „1 z n” i OR
- „nie 1 z n” i NAND
*realizacja na multiplekserach
Moore vs Mealy
- w automacie Moore'a wyjście jest funkcją tylko stanu wewnętrznego
- w automacie Mealy'ego wyjście jest funkcją stanu wewnętrznego i stanu wejściowego
- automat Moore'a ma niemniejszą liczbę stanów (zwykle większą) wewnętrznych niż automat Mealy'ego
Kodowanie tablicy p-w
- aby można było wyznaczyć funkcję przejść i wyjść konieczne jest zakodowanie stanów wewnętrznych w tabeli p-w
- kodowanie polega na wzajemnie jednoznacznym przyporządkowaniu każdemu ze stanów S1,…,Sn ciągu stanów automatów elementarnych Q1,…,Qk
- ponieważ każdy przerzutnik ma 2 stany, to kodowanie stanów wewnętrznych polega na wzajemnie jednoznacznym przyporządkowaniu pewnych ciągów zerojedynkowych
- w przypadku automatu synchronicznego kodowanie można przeprowadzić w dowolny sposób. Należy wybierać kod, dla którego automat zawiera minimalną ilość elementów pamięci, zaś dla poprawnego i efektywnego kodowania stosuje się rachunek podziałów
Tablica wzbudzeń - opisuje układ, który wzbudza przerzutniki, służy do projektowania układu
Pokrycie - zbiór podzbiorów zbioru S, których suma jest równa S
C = {B1, B2, …, Bn}
B1uB2u…uBn = S
Podział Л - zbiór rozłącznych podzbiorów zbioru S, których suma jest równa S
Л = {B1, B2, …, Bn}
Bi∩Bj = zbiór pusty dla i≠j
B1uB2u…uBn = S
B1uB2u…uBn = S
Iloczyn Л1*Л2 podziałów Л1 i Л2 nazywamy podział, którego blokami są przecięcia bloków podziałów Л1 z blokami podziału Л2
{134, 256}*{135, 246} = {13, 4, 5, 26}
Sumą Л1+Л2 podziałów Л1 i Л2 nazywamy najmniejszy podział Л' taki, że jeśli stan S jest elementem jakiegoś bloku z Л1 lub Л2, to cały ten blok jest zawarty w 1 bloku podziału Л'
{123, 45}+{1, 2345} = {12345}
Podział Л1<=Л2, gdy każdy blok Л1 jest zawarty w pewnym bloku Л2
{1, 2, 3, 45, 67} <= {12, 345, 67}
Podziały prawidłowe - należy je rozpatrywać, gdy do realizacji automatu chcemy uzyć minimalnej liczby elementów. Są to podziały 2-blokowe i liczba elementów każdego bloku <= 2k-1. Podziały 2-blokowe wzięte do kodowania muszą spełniać warunek
τ1*τ2*…*τk = 0
Rodzina końcowa Tk - zbiór podziałów, który można przyjąć do kodowania (spełnia warunek zerowego iloczynu)
Rodzina końcowa optymalna Tkopt - rodzina wyznaczająca kod dający najprostsze funkcje przejść i wyjść
Cena podziału wewnętrznego C(τi) - szacunkowa ilość zmiennych, od których zależy funkcja wzbudzeń przerzutnika Qi zakodowanego zgodnie z τi zmniejszony o 1. Wyznacza się ją z zależności
C(τj) = n+l-1
n- liczba zmiennych wejściowych
l - liczba sygnałów Ql, od których zależy funkcja wzbudzeń przerzutnika Qi
Podziałem zewnętrznym Лxj(yi) dla automatu Mealy'ego nazywamy podział, którego bloki zawierają tylko takie stany, którym przy sygnale wejściowym xj odpowiadają jednakowe sygnały wyjściowe
Podziałem zewnętrznym Л(yi) dla automatu Moore'a nazywamy podział, którego bloki zawierają stany, którym odpowiadają jednakowe sygnały wyjściowe.
Stany pseudo-równoważne - 2 stany zgodne mające stany stabilne w 1 kolumnie. Jeżeli są stany pseudo-równoważne, należy przeprowadzić minimalizację.
Wyścig - zjawisko istnienia różnych dróg przejść ze stanu niestabilnego do stabilnego. Wyścigi mogą wystąpić w układzie tylko wtedy, gdy przełączenie automatu wymaga zmiany stanu co najmniej 2 elementów pamięci.
Wyścig krytyczny - zjawisko możliwości przejścia automatu ze stanu niestabilnego do różnych stanów stabilnych. Trzeba usunąć.
Wyścig niekrytyczny - przejście ze stanu niestabilnego do odpowiadającego mu stanu stabilnego. Nie trzeba usuwać.
Kodowanie z zastosowaniem rachunku podziałów
- trzeba usunąć wyścigi krytyczne
- zastosowanie rachunku podziałów pozwala nie tylko usunąć wyścigi, ale również uzyskiwać układy o minimalnej złożoności
- ta metoda kodowania dopuszcza równoczesną zmianę stanu kilku elementów pamięci
- poprawne kodowanie można uzyskać wybierając podziały tak, aby zawsze istniał podział, w którym pary stanów (Sk, Sr) i (Sr, Sn) należą do różnych bloków
Rodzina końcowa TK - zbiór podziałów prawidłowych spełniających warunki:
- iloczyn podziałów daje podział zerowy
- kodowanie zgodne z podziałami TK nie powoduje wyścigów krytycznych
Optymalna rodzina końcowa TKopt - rodzina zapewniająca najprostszą postać funkcji przejść oraz funkcji wyjść
Podział wewnętrzny Л(xj) to podział, którego bloki zapewniają stany o identycznych xj - następnikach
Etapy kodowania z zastosowaniem rachunku podziałów
1.Wypisujemy podziały zewnętrzne
2.Wypisujemy podziały wewnętrzne
3.Podziały muszą być prawidłowe większe od wewnętrznych
4.Wybranie TK
5.Wybranie TKopt
6.Zakodowanie tablicy przejść
7.Wyznaczenie funkcji wzbudzeń
8.Schemat ideowy układu