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-y_i =

KPI-y_i=

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 2^k 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 x_i+nx_i = 1

PNI - do sum elementarnych dodaje się wyrażenie x_i*nx_i = 0

Gdzie x_i - 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

x₁*x₂ + x₁*x₃ = x₁*(x₂+x₃)

(x₁+x₂)(x₁+x₃) = x₁+x₂*x₃

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 = {B₁, B₂, …, B_n}

B₁uB₂u…uB_n = S

Podział Л - zbiór rozłącznych podzbiorów zbioru S, których suma jest równa S

Л = {B₁, B₂, …, B_n}

B_i∩B_j = zbiór pusty dla i≠j

B₁uB₂u…uB_n = S

B₁uB₂u…uB_n = S

Iloczyn Л₁*Л₂ podziałów Л₁ i Л₂ nazywamy podział, którego blokami są przecięcia bloków podziałów Л₁ z blokami podziału Л₂

{134, 256}*{135, 246} = {13, 4, 5, 26}

Sumą Л₁+Л₂ podziałów Л₁ i Л₂ nazywamy najmniejszy podział Л' taki, że jeśli stan S jest elementem jakiegoś bloku z Л₁ lub Л₂, to cały ten blok jest zawarty w 1 bloku podziału Л'

{123, 45}+{1, 2345} = {12345}

Podział Л₁<=Л₂, gdy każdy blok Л₁ jest zawarty w pewnym bloku Л₂

{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 <= 2^k-1. Podziały 2-blokowe wzięte do kodowania muszą spełniać warunek

τ₁*τ₂*…*τ_k = 0

Rodzina końcowa T_k - zbiór podziałów, który można przyjąć do kodowania (spełnia warunek zerowego iloczynu)

Rodzina końcowa optymalna T_kopt - 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 Q_i 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 Q_l, od których zależy funkcja wzbudzeń przerzutnika Q_i

Podziałem zewnętrznym Лx_j(y_i) dla automatu Mealy'ego nazywamy podział, którego bloki zawierają tylko takie stany, którym przy sygnale wejściowym x_j odpowiadają jednakowe sygnały wyjściowe

Podziałem zewnętrznym Л(y_i) 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 (S_k, S_r) i (S_r, S_n) należą do różnych bloków

Rodzina końcowa T_K - zbiór podziałów prawidłowych spełniających warunki:

- iloczyn podziałów daje podział zerowy

- kodowanie zgodne z podziałami T_K nie powoduje wyścigów krytycznych

Optymalna rodzina końcowa T_Kopt - rodzina zapewniająca najprostszą postać funkcji przejść oraz funkcji wyjść

Podział wewnętrzny Л(x_j) to podział, którego bloki zapewniają stany o identycznych x_j - 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 T_K

5.Wybranie T_Kopt

6.Zakodowanie tablicy przejść

7.Wyznaczenie funkcji wzbudzeń

8.Schemat ideowy układu

---