Podręcznik

Algebra Boole’a (ang. Boolean algebra) to szczególnego typu algebra ogólna. Dokładniej jest to 6-tka uporządkowana $(A, \cup, \cap, -, 0, 1)$, gdzie $A$ jest niepustym zbiorem, a działania $\cup, \cap, -$ i wyróżnione elementy $0, 1 \in A$ (działania zero argumentowe) spełniają cały szereg warunków tzw. aksjomatów algebry Boole’a. Działanie dwuargumentowe $"\cup"$ nazywamy sumą, działanie dwuargumentowe $"\cap"$ nazywamy iloczynem a działanie jednoargumentowe $"-"$ uzupełnieniem. Wyróżnione elementy $0, 1 \in A$ są takie, że 0 jest zerem (dla działania sumy) jest to tzw. zero algebry Boole'a a 1 jedynką dla działania mnożenia jest to tzw. jedynka algebry Boole'a.

Zanim precyzyjnie zdefiniujemy algebrę Boole'a omówimy nieco prostszą od algebry Boole'a algebrę tzw. kratę (ang. lattice).

Krata to algebra $(A, \cup, \cap)$. Działanie dwuargumentowe $"\cup"$ nazywamy sumą, działanie dwuargumentowe $"\cap"$ nazywamy iloczynem. Algebra $(A, \cup, \cap)$ jest kratą wtedy i tylko wtedy, z definicji, gdy spełnione są następujące aksjomaty (w sumie mamy 8 aksjomatów):

Zauważmy, że jeśli konsekwentnie zamienimy w powyższych aksjomatach sumę $"\cup"$ na iloczyn $"\cap"$ oraz iloczyn $"\cap"$ na sumę $"\cup"$ to otrzymamy dokładnie taki sam zestaw aksjomatów.

Krata dystrybutywna (ang. distributive lattice) to krata, w której spełnione są jeszcze dodatkowo dwa aksjomaty: rozdzielczość mnożenia względem dodawania i rozdzielczość dodawania względem mnożenia.

Algebrę $(A, \cup, \cap, -, 0, 1)$ nazywamy algebrą Boole’a jeśli $(A, \cup, \cap)$ jest kratą dystrybutywną, element 0 jest zerem dla działania dodawania a element 1 jedynką dla działania mnożenia czyli spełnione są równości (6) a ponadto działanie uzupełnienia spełnia równości (7).

Zapisując wyrażenia algebry Boole’a będziemy zakładać, że działanie uzupełnienia ma największy priorytet a potem w kolejności mnożenie i dodawanie. Tak więc mamy np.

$-x \cup -y=(-x)\cup(-y)$

Z definicji algebry Boole’a nie wynika, że musi być $1\neq0$. Jeśli $1=0$ to algebra Boole’a ma tylko jeden element. Nazywamy taką algebrę Boole’a zdegenerowaną algebrą Boole’a. Algebrę Boole’a, która ma tylko 2 elementy, nazywamy algebą Boole’a dwuelementową.

Fakt: Każda skończona algebra Boole’a $(A, \cup, \cap, -, 0, 1)$ ma $2^n$ elementów, tzn. istnieje takie $n \in N$, że $card(A)=2^n$

W każdej algebrze Boole’a oprócz wymienionych wyżej 14 aksjomatów prawdziwe są równości

$-1=0, \quad-0=1$
$-(-x)=x$
$-(x \cup y)= -x \cap -y$
$-(x \cap y)= -x \cup -y$

Ostatnie dwie równości noszą nazwę praw de Morgana

Homomorfizm i izomorfizm algebr Boole’a nie różnią się od tych pojęć dla przypadku dowolnej algebry abstrakcyjnej. Homomorfizm dwóch algebr Boole’a $(A_1, \cup, \cap, -, 0, 1)$ i $(A_2, \cup, \cap, -, 0, 1)$ to odwzorowanie $h:A_1 \rightarrow A_2$ zachowujące działania algebry Boole’a tzn. takie, że dla każdego $a, b \in A_1$ mamy

$h(a \cup b)=h(a) \cup h(b), \quad h(a\cap b)=h(a)\cap h(b)$
$h(-a)=-h(a), \hspace{4em} h(0)=0, \quad h(1)=1$

Izomorfizm to homomorfizm różnowartościowy i „na”.

Jeśli algebra Boole’a $(A, \cup, \cap, -, 1, 0)$ ma dokładnie 2 elementy (a ściślej zbiór $A$ ma dokładnie 2 elementy), to nazywamy ją dwuelementową algebrą Boole’a.

Fakt: Istnieje jedna tylko z dokładnością do izomorfizmu $2^n$ elementowa algebra Boole’a. W szczególności istnieje tylko jedna (z dokładnością do izomorfizmu) 2-elementowa algebra Boole’a.

Równości (1)-(7) to aksjomaty algebry Boole’a. Wzory (10) i (11) są prawami de Morgana dla 2-elementowej algebry Boole'a.

Funkcję boolowską nazywamy również funkcją logiczną lub funkcją przełączającą. Funkcja boolowska jest też definiowana nieco ogólniej jako funkcja postaci $f:D \rightarrow \{0,1\}^m$, gdzie $D \subset \{0,1\}^n$ jest niepustym podzbiorem zbioru wszystkich słów binarnych binarnych długości $n$.

Jeśli mówimy „funkcja boolowska $n$ argumentowa” nie precyzując $D$ to przyjmujemy, że $D=\{0,1\}^n$. Jeśli $D=\{0,1\}^n$ to funkcję boolowską nazywamy zupełną. Jeśli $D$ jest właściwym podzbiorem zbioru $\{0,1\}^n$, to funkcję boolowską nazywamy niezupełną. Jeśli $m>1$, to funkcję boolowską nazywamy wektorową.

Na ogół mówiąc funkcja boolowska będziemy mieć na myśli funkcję $f:\{0,1\}^n \rightarrow \{0,1\}$.

Zauważmy, że nawet dla małych $n$ liczba wszystkich funkcji boolowskich jest duża. Jest to bowiem liczba wariancji z powtórzeniami zbioru $2^n$ elementowego ze zbioru 2-elementowego, czyli $2^{2^n}$. Dla $n=2$ mamy 16 funkcji ale dla $n=5$ już $2^{32}$ (to więcej niż 100 milionów).

Rys.1. Układ kombinacyjny o $n$ wejściach i jednym wyjściu (układ jednowyjściowy) realizujący funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$

Rys. 2. Układ kombinacyjny o $n$ wejściach i $m$ wyjściach (układ wielowyjściowy) realizujący funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}^m$

W 2 elementowej algebrze Boole’a definiujemy kilka dodatkowych użytecznych w praktyce działań. Zaczniemy od sumy modulo 2 (suma modulo 2 jest szczególnym przypadkiem sumy modulo $m$ wprowadzanej w zbiorze $Z_m=\{0,1,...,m-1\}$). Sumę modulo 2 oznaczamy symbolem $\oplus$ i definiujemy za pomocą tabelki.

Rys. 3. Tabelka definiująca sumę modulo 2

Podstawowe własności sumy modulo 2 są następujące

$0 \oplus0=0, \qquad 1 \oplus 1=0, \qquad 1 \oplus 0=1, \qquad 0 \oplus 1=1, \qquad x \oplus x=0$

$x \oplus 1 = \overline{x}, \qquad x \oplus 0=x, \qquad x_1 \oplus x_2= \overline{x_1} \oplus \overline{x_2}, \qquad x_1 \oplus x_2=x_1 \overline{x_2}+\overline{x_1}x_2$

$(x_1 \oplus x_2) \oplus x_3=x_1 \oplus (x_2 \oplus x_3)$ (łączność sumy modulo 2)

$x_1 \oplus x_2=x_2 \oplus x_1$ (przemienność sumy modulo 2)

$x_1\oplus x_2 \oplus x_2=x_1$

Przypomnijmy (por. rozdz.1), że zbiór $Z_m=\{0,1,2,...,m-1\}$ wraz z działaniami dodawania modulo $m$ i mnożenia modulo $m$ jest pierścieniem przemiennym z jednością a jeśli $m=p$, (gdzie p$p$jest liczbą pierwszą) to $Z_p$ jest ciałem. Zatem w szczególności $Z_2=\{0,1\}$ z dodawania działaniami modulo 2 i mnożenia modulo 2 jest ciałem.

Łatwo sprawdzić, że 2 argumentowa suma modulo 2 zdefiniowana tabelką z Rys. 2.3 i suma modulo 2 zdefiniowana jako szczególny przypadek sumy modulo $m$ (dla $m=2$) to to samo działanie. Z kolei iloczyn modulo 2 zdefiniowany jako szczególny przypadek sumy modulo $m$ (dla $m=2$) to mnożenie logiczne. Zatem trójka uporządkowana $(Z_2,\oplus,\cdot)$ jest ciałem. Zatem wprowadzenie w algebrze Boole’a sumy modulo 2 jako działania 2 argumentowego pozwala spojrzeć na zbiór $\{0,1\}$ jak na ciało.

Z algebry liniowej wiadomo (jest to prosty do sprawdzenia fakt), że jeśli $K$ jest ciałem, to iloczyn kartezjański $\underbrace{K \times K \times ... \times K}_{n}=K^n$ jest przestrzenią liniową nad ciałem $K$ . Zatem również $\underbrace{Z_2 \times Z_2 \times ... \times Z_2}_{n}=Z_2^n$ jest przestrzenią liniową nad $Z_2=\{0,1\}$. Można więc słowa binarne o długości $n$ (czyli elementy przestrzeni $Z_2^n$) nazywać wektorami.

Podobnie jeśli mamy ustalone dowolne ciało $K$ to można rozważać pierścień wielomianów $K[x]$ nad ciałem $K$. Tak też można zrobić w przypadku $Z_2$ wprowadzając wielomiany nad ciałem $Z_2=\{0,1\}$.

a)

Bramka NOT realizuje funkcję $y=\overline{x}$

b)

Bramka AND czyli bramka iloczynu (dwuwejściowego) realizuje funkcję $y=x_1x_1$. Stosowane są również bramki wielowejściowe.

c)

Dwuwejściowa bramka OR czyli bramka sumy (dwuwejściowej) realizuje funkcję $y=x_1+x_1$. Stosowane są również bramki wielowejściowe.

d)

Dwuwejściowa bramka EXOR czyli bramka sumy modulo dwa (dwuwejściowa) realizuje funkcję $y=x_1 \oplus x_1$. Stosowane są również bramki wielowejściowe EXOR. Bardzo pożyteczna jest w praktyce tożsamość $x_1 \oplus x_2=x_1\overline{x_2}+\overline{x_1}x_2$

Rys. 4. Symbole typowych bramek a) bramka NOT, b) bramka AND, c) bramka OR d) bramka EXOR

Wyrażenie boolowskie (lub forma boolowska) to formalnie poprawnie zbudowany opis funkcji boolowskiej f zawierający wprowadzone w algebrze Boole’a działania i nawiasy opisujące kolejność wykonywanych działań na wprowadzonych zmiennych (argumentach funkcji $f$). Najczęściej w tworzonych zapisach bierzemy dodatkowo pod uwagę następujący priorytet wykonywanych działań: negacja ma największy priorytet, potem mnożenie a potem dodawanie.

Iloczyn pełny $n$ zmiennych (inaczej minterm) to iloczyn zawierający $n$ różnych zmiennych zanegowanych lub nie. Minterm dla $n$ zmiennych (lub dla $n$ argumentów) jest funkcją przyjmująca wartość 1 tylko dla jednego układu argumentów $x_1,x_2,...,x_n$.

Iloczyn niepełny $n$ zmiennych to iloczyn zawierający $m$ różnych zmiennych zanegowanych lub nie.

Suma pełna $n$ zmiennych (inaczej maksterm) to suma zawierająca $n$ różnych zmiennych zanegowanych lub nie. Maksterm dla $n$ zmiennych (lub dla $n$ argumentów) jest funkcją przyjmującą wartość 0 tylko dla jednego układu argumentów $x_1,x_2,...,x_n$.

Suma niepełna $n$ zmiennych to iloczyn zawierający $m$ różnych zmiennych zanegowanych lub nie.

Postać normalna sumacyjna (inaczej postać normalna dysjunkcyjna) funkcji boolowskiej $n$ zmiennych $f$ to opis funkcji w postaci sumy iloczynów pełnych lub niepełnych.

Postać normalna iloczynowa (inaczej postać normalna koniunkcyjna) funkcji boolowskiej $n$ zmiennych $f$ to opis funkcji w postaci iloczynu sum pełnych lub niepełnych.

Implikant. Funkcja boolowska $g:\{0,1\}^n \rightarrow \{0,1\}$ implikuje inną funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$ jeśli dla każdego układu $x=(x_1,x_2,...,x_n) \in \{0,1\}^n$ takiego, że $g(x)=1$ mamy $f(x)=1$. Funkcję $g$ nazywamy implikantem funkcji $f$.

Implikant prosty funkcji boolowskiej $n$ zmiennych zapisanej w postaci normalnej sumacyjnej to iloczyn $m$ różnych zmiennych (ewentualnie zanegowanych), $m \leq n$ będący implikantem funkcji $f$ posiadający tę własność, że po usunięciu jakiejkolwiek zmiennej z tego iloczynu, tak powstała funkcja przestaje być implikantem funkcji $f$.

Dla każdej funkcji boolowskiej spełniona jest oczywista (proste sprawdzenie) ale pożyteczna równość:

$f(x_1,x_2,...,x_n)=\overline{x_1}f(0,x_2,...,x_n)+x_1f(1,x_2,...,x_n)$

Jest to tzw. wzór na rozłożenie sumacyjne funkcji boolowskiej.

Podobnie uzyskujemy wzór

$f(x_1,x_2,...,x_n)=(\overline{x_1}+f(1,x_2,...,x_n))(x_1+f(0,x_2,...,x_n)$

Jest to tzw. wzór na rozłożenie iloczynowe funkcji boolowskiej.

Stosując wielokrotnie ($n$ krotnie) wzór na rozłożenie sumacyjne funkcji boolowskiej otrzymujemy następujące twierdzenie o postaci kanonicznej sumacyjnej (lub dysjunkcyjnej).

Twierdzenie (o postaci kanonicznej sumacyjnej):

Każdą funkcję boolowską $f:\{0,1\}^n \rightarrow \{0,1\}$ można przedstawić jednoznacznie w postaci sumy implikantów prostych

gdzie $\alpha_k=f(k_{n-1},k_{n-2},...,k_0)$ a $k_{n-1}k_{n-2}...k_0$ jest $n$ bitowym zapisem NKB liczby $k\in$. $I_k(x_1,x_2,...,x_n)$ jest ($n$-argumentowym) mintermem o numerze $k$, tzn. funkcją postaci $I_k(x_1,x_2,...,x_n)=\overline{x_1}\cdot x_2 \cdot...\cdot x_n$, gdzie negacje lub ich brak odpowiada liczbie $k$ w taki sposób: umieszczamy ciąg bitów $k_{n-1}k_{n-2}...k_0$ nad zmiennymi $x_1,x_2,...,x_n$ i tam gdzie nad zmienną stoi 0, wpisujemy negację, a tam gdzie stoi 1, nie wpisujemy negacji.

Równość (*) to tzw. kanoniczna postać sumacyjna (dysjunkcyjna) funkcji boolowskiej $f(x_1,x_2,...,x_n)$.

Podobnie jak wprowadzamy kanoniczną postać sumacyjną można wprowadzić kanoniczną postać iloczynowi (koniunkcyjną) i wykazać twierdzenie o postaci kanonicznej iloczynowej.

Tabelka prawdy. Najprostszym pojęciowo opisem funkcji boolowskiej jest tabelka prawdy czyli bezpośrednie podanie wartości funkcji dla wszystkich możliwych układów argumentów. Dla większej liczby argumentów jest to jednak metoda kłopotliwa. Wyobraźmy sobie bowiem tabelkę dla funkcji boolowskiej 16 czy 32 argumentowej.

Wyrażenie boolowskie. Wygodnie jest funkcję boolowską zadawać wyrażeniem boolowskim czyli forma boolowską.

Tablica Karnaugha. Kolejną stosowaną w praktyce metodą jest tablica Karnaugh. Jest to w gruncie rzeczy odmiana tabelki prawdy.

Tablica Karnaugha to często stosowany sposób opisu, zadawania funkcji boolowskiej z reguły niewielkiej liczby zmiennych 2,3,4,5. Tablice Karnaugh można również wykorzystywać do minimalizacji funkcji boolowskich (niewielkiej liczby zmiennych). Na przykład dla funkcji boolowskiej 4 zmiennych $f(x_1,x_2,x_3,x_4)=\overline{x_1}\cdot x_2 \cdot x_3 \cdot x_4$ konstruujemy tablicę Karnaugh następująco:

Wypisujemy wartości argumentów $x_1,x_2$ w pierwszej kolumnie, tak by stanowiły 2 bitowy kod Gray’a. Podobnie wypisujemy wartości argumentów $x_3,x_4$ w pierwszym wierszu, tak by stanowiły 2 bitowy kod Gray’a

Rys. 6. Tablica Karnaugh dla funkcji $f(x_1,x_2,x_3,x_4)=\overline{x_1}\cdot x_2 \cdot x_3 \cdot x_4$

Układy kombinacyjne można budować w różny sposób np.:

• bezpośrednio łącząc bramki. Z bramek NAND, NOR i OR możemy zbudować układ pokazany na Rys. 7.
• wykorzystując bloki funkcjonalne takie jak np. multipleksery, kodery, dekodery, układy PLA i układy PLD
• wykorzystując pamięci stałe ROM, PROM, EPROM

W naturalny sposób do realizacji funkcji boolowskiej można wykorzystać pamięć ROM. Nie jest to metoda oszczędna, ale umożliwia na ogół łatwą realizację i modyfikację funkcji boolowskiej np. w przypadku zastosowania pamięci typu flash.

Rys. 7. Przykład układu kombinacyjnego realizującego pewną funkcję boolowską $f:\{0,1\}^8\rightarrow\{0,1\}$

Zegar systemu cyfrowego (ang. clock) to układ elektroniczny generujący napięciowy przebieg zegarowy (sygnał zegarowy). Sygnał zegarowy czasem jest również dla uproszczenia nazywany zegarem.

Sygnał zegarowy to prostokątny przebieg okresowy o kształcie pokazanym na Rys.1. Chwile kiedy pojawia się narastające zbocze wyznaczają dyskretne chwile czasu, w których może zachodzić zmiana stanu układu cyfrowego. Możemy powiedzieć, że system cyfrowy działa krok za krokiem w dyskretnych chwilach w takt zegara.

Podobnie chwile kiedy pojawia się zbocze opadające sygnału zegarowego można przyjąć za dyskretne chwile czasu, w których może zachodzić zmiana stanu układu cyfrowego. Trzecim sposobem jest przyjęcie że dyskretne chwile mogą być wyznaczone zarówno przez zbocza narastające jak i opadające.

W abstrakcyjnym opisie systemu cyfrowego wygodnie jest te chwile utożsamiać z liczbami naturalnymi lub całkowitymi. Na ogół w systemie cyfrowym jest jeden zegar i jest to bardzo wygodne. Czasami jednak konieczne jest zastosowanie kilku zegarów w systemie.

Zasadniczymi parametrami charakteryzującymi prostokątny przebieg zegarowy są częstotliwość $f$ oraz wypełnienie $d$. Wypełnienie (ang. duty cycle) okresowego przebiegu prostokątnego to stosunek $d=\frac{T_1}{T}$, gdzie $T=\frac{1}{f}$ jest okresem przebiegu a czas $T_1$ jest czasem trwania „pojedynczego impulsu” por. Rys.1. Typowy przebieg zegarowy ma wypełnienie ½ , ale nie jest to reguła.

Istotna jest w systemach cyfrowych stałość częstotliwości generowanego przebiegu zegarowego. Dlatego też najczęściej jako generatory przebiegu zegarowego wykorzystuje się tzw. generatory kwarcowe wykazujące wyjątkowo dobrą stałość częstotliwości. W sytuacjach specjalnych gdy musimy mieć zegar zsynchronizowany z jedynie słusznym zegarem wszechświatowym (np. w tzw. stemplowaniu czasem dokumentów) to stosuje się synchronizację generatorów kwarcowych z sygnałami czasu systemu GPS.

Częstotliwość zegara $f$ może być bardzo różna. Od dołu praktycznie nie mamy żadnych ograniczeń choć istotna jest stromość zboczy przebiegu prostokątnego. Jeśli chodzi o wartości maksymalne to we współczesnych systemach mikroprocesorowych (np. w Pentium 4) częstotliwość zegara przekracza już 3 GHz a w systemach stosujących technologie specjalne 10 GHz.

Z reguły moc wydzielana w układzie cyfrowym jest wprost proporcjonalna do częstotliwości zegara (zależność ta jest w przybliżeniu liniowa). Dzieje się tak dlatego, że bramki logiczne pobierają prąd z układu zasilania głównie w chwilach przełączeń czyli na narastających i opadających zboczach sygnału zegarowego (dotyczy to zarówno bramek TTL jak i NMOS i CMOS).

Z kolei tzw. moc obliczeniowa systemu cyfrowego (jeśli to pojęcie ma sens dla konkretnego systemu cyfrowego) jest na ogół proporcjonalna do częstotliwości zegara.

Ponieważ jednak moc wydzielająca się w układzie rośnie wraz z częstotliwością, to stosowanie wysokich częstotliwości zegara prowadzi do konieczności stosowania specjalnych układów chłodzących (radiatory, wiatraczki a czasem nawet chłodzenie wodne podobne do samochodowego). Układy pracujące z wysokimi częstotliwościami zegara muszą być bardzo starannie zaprojektowane od strony cieplnej każdy bowiem układ ma swoją graniczną temperaturę pracy, której przekroczenie grozi nieodwracalnym zniszczeniem układu.

Ogólnie rzecz biorą systemy cyfrowe dzielimy na synchroniczne tzn. działające w takt zegara i asynchroniczne, w których chwile zmiany stanu układu są wyznaczone przez zmiany stanu wejść. Wszystkie duże systemy cyfrowe takie jak np. mikroprocesory są systemami cyfrowymi synchronicznymi. Sygnał zegarowy albo generowany jest wewnątrz systemu albo doprowadzany jest z zewnątrz.

Rys. 1. Przebieg prostokątny będący sygnałem zegarowym systemu cyfrowego

Automaty skończone są abstrakcyjnymi modelami rzeczywistych systemów cyfrowych.

Automat skończony lub dokładniej deterministyczny automat skończony (DAS) to piątka uporządkowana $(Q, \Sigma, \delta, q_0, F)$, gdzie $Q$ - jest zbiorem stanów, $\Sigma$ - alfabetem wejściowym, $\delta:Q\times\Sigma\rightarrow Q$ - funkcją przejść automatu, $q_0\in F$ - tzw. stanem początkowym a $F$ – zbiorem stanów końcowych.

Stan automatu umożliwia pamiętanie historii wejścia tzn. stan w chwili bieżącej. Ogólnie rzecz biorąc zależy od słowa podanego na wejście w chwilach poprzednich.

Mówimy, że automat skończony akceptuje słowo pojawiające się na wejściu automatu, jeśli ciąg przejść ze stanu do stanu odpowiadający literom słowa wejściowego prowadzi od stanu początkowego $q_0$ do jakiegoś stanu $q$ akceptowalnego tzn takiego że $q\in F$.

Automat skończony wyobrażamy sobie jako układ o skończonej liczbie stanów, z jednym wejściem, który znajduje się w pewnym stanie $q$ i czyta ciąg symboli z alfabetu $\Sigma$, czyli czyta słowo nad alfabetem $\Sigma$ podane na wejście. Układ działa w dyskretnych chwilach, które dla uproszczenia utożsamiamy z liczbami naturalnymi. W każdej chwili $n\in N$ automat może odczytać tylko jedną literę słowa $a_n \in \Sigma$ czyta ją i zmienia stan ze stanu $q_{n-1}$ zgodnie z funkcją przejścia na $\tilde{\delta}(q_{n-1},a_n)=q_n$ po czym automat staje i czeka na następną chwilę. W kolejnych chwilach pojawiają się więc na wejściu litery $a_1,a_2,...,a_n\in\Sigma$ i następują zmiany stanu. Jeśli $\tilde{\delta}(q_{n-1},a_n)=q_n\in F$ tzn. dotarliśmy do stanu akceptującego to uważamy, że automat zaakceptował słowo wejściowe $a_1a_2...a_n$ dotychczas podane na wejście automatu.

Jeśli mamy funkcję przejścia $\delta:\Sigma\times Q\rightarrow Q$ to w naturalny sposób można ją rozszerzyć do funkcji $a\in\Sigma$ definiując $\tilde{\delta}$ następująco:

• $\tilde{\delta}(q,\varepsilon)=q$ dla każdego $q\in Q$
• $\tilde{\delta}(q,wa)=\delta(\tilde{\delta}(q,w),a)$ dla każdego $q\in Q$, dla każdego $a\in\Sigma$ i dla każdego słowa $w$ nad alfabetem $\Sigma$

Język akceptowany przez automat skończony $M=(Q,\Sigma,S,\delta,q_0,F)$ to z definicji zbiór $L(M)\overset{df}{=} \{x\in\Sigma^*; \tilde{\delta}(q_0,x)\in F\}\subseteq\Sigma^*$. Język $L\subseteq\Sigma^*$ nazywamy językiem regularnym, jeśli jest akceptowany przez jakiś automat skończony $M=(Q,\Sigma,S,\delta,q_0,F)$

Niedeterministyczny automat skończony to piątka uporządkowana $(Q,\Sigma,\delta,q_0,F)$, gdzie $Q$ jest zbiorem stanów automatu, $\Sigma$ alfabetem wejściowym, $q_0\in F$ - tzw. stanem początkowym, $F$ - zbiorem stanów końcowych a $\tilde{\delta}:Q\times\Sigma\rightarrow 2^Q$ - funkcją przejść automatu niedeterministycznego. Przypominamy, że symbolem $2^Q$ oznaczamy zbiór wszystkich podzbiorów zbioru $Q$.

Zbiór $\delta:(q,a)\subseteq Q$ jest zbiorem wszystkich stanów do których możliwe jest przejście ze stanu $q$ pod wpływem litery $a$ podanej na wejście automatu.

Zauważmy, że zdefiniowane wyżej automaty są automatami bez wyjścia. Ponieważ w praktyce najczęściej mamy do czynienia z systemami cyfrowymi z wyjściem, dlatego też wprowadza się definicje automatów skończonych z wyjściem.

Automat skończony z wyjściem to szóstka uporządkowana $(Q,\Sigma,Y,\delta,\lambda,q_0)$, gdzie $Q, \Sigma, Y$ są alfabetami, $\delta$ i $\lambda$ są funkcjami oraz $q_0\in S$. $\Sigma$ to alfabet wejściowy, $Y$ alfabet wyjściowy a $Q$ jest tzw. zbiorem stanów. Funkcja $\delta:Q\times\Sigma\rightarrow Q$ nosi nazwę funkcji przejść, funkcja $\lambda:Q\rightarrow Y$ nazywa się funkcją wyjść, a $q_0\in S$ jest tzw. stanem początkowym. Tak zdefiniowany automat nazywa się automatem Moore’a.

Jeśli funkcja $\lambda$ jest funkcją bezpośrednio zależną od wejścia tzn. $\lambda:Q\times\Sigma\rightarrow Y$, to taką szóstkę uporządkowaną $(X,Y,S,\delta,\lambda,q_0)$ nazywamy automatem Mealy'ego.

Automat skończony z wyjściem wyobrażamy sobie jako układ o skończonej liczbie stanów, z jednym wejściem i jednym wyjściem, który znajduje się w pewnym stanie $q$ i czyta ciąg symboli $a_1a_2...a_n$ z alfabetu $\Sigma$ czyli czyta słowo nad alfabetem $\Sigma$ podane na wejście. Układ działa w dyskretnych chwilach, które dla uproszczenia utożsamiamy z liczbami naturalnymi 1,2,3..... W każdej chwili $n\in N$ automat może odczytać tylko jedną literę słowa $a_n\in\Sigma$ czyta ją i zmienia stan ze stanu $q_{n-1}$ zgodnie z funkcją przejścia na $\tilde{\delta}(q_{n-1},a_n)=q_n$ i wyprowadza na wyjście literę $\lambda(q_n)$ w przypadku automatu Moore’a lub $\lambda(q_n,a_n)=b_n$ w przypadku automatu Mealy’ego po czym automat staje i czeka na następną chwilę. W kolejnych chwilach pojawiają się więc na wejściu litery $a_1,a_2,...,a_n\in\Sigma$, na wyjściu litery $b_1,b_2,...,b_n\in Y$ i następują zmiany stanu. Automaty Moore’a i Mealy’ego są więc urządzeniami do przetwarzania słów.

Układ sekwencyjny to układ elektroniczny realizujący automat skończony.

Rys. 2. Przetwarzanie słów przez automat skończony bez wyjścia

Rys. 3. Przetwarzanie słów przez automat skończony z wyjściem

Rys. 4. Schemat blokowy układu automat skończony z wyjściem a) automat Moore’a, b) automat Mealy’ego

Rys. 5. Struktura uniwersalna automatu Moore’a z kodowaniem binarnym symboli wejściowych, wyjściowych i stanów; rejestr stanu jest rejestrem r bitowym

Rys. 6. Struktura uniwersalna automatu Mealy’ego z kodowaniem binarnym symboli wejściowych, wyjściowych i stanów

Opis automatu grafem. Z każdym automatem skończonym wiążemy diagram przejść lub dokładniej graf automatu. Jest to graf skierowany w którym wierzchołki grafu odpowiadają stanom automatu Jeśli w automacie istnieje przejście ze stanu $q_1\in Q$ do stanu $q_2\in Q$ przy wejściu $a\in\Sigma$ to diagram zawiera gałąź prowadzącą ze stanu $q_1\in Q$ do stanu $q_2\in Q$ i opatrzoną etykietą $a\in\Sigma$.

Rys.7. Opis automatu grafem. Z każdym automatem skończonym wiążemy diagram przejść czyli graf skierowany opisujący działanie automatu

Koncepcja by budować „duże” automaty z „małych” jest naturalna i praktyczna. I tak się właśnie robi definiując i konstruując elementarne cegiełki tzw. automaty elementarne. Takimi właśnie automatami są przerzutniki, które definiujemy poniżej. Przerzutnik jest układem elektronicznym (bardzo rzadko stosuje się inne rozwiązania), który może przebywać w jednym z dwóch stabilnych stanów dowolnie długo. Mówimy, że układ jest bistabilny. Ponieważ za pomocą sygnałów zewnętrznych (wejść przerzutnika) możemy zmieniać stan układu, układ przerzutnika bistabilnego jest elementarnym układem pamięciowym zdolnym do zapamiętania jednego bitu, zera albo jedynki. Oddziaływanie za pomocą sygnałów zewnętrznych na układ przerzutnika bistabilnego zmierzające do zmiany jego stanu nazywamy wyzwalaniem przerzutnika.

Przerzutniki dzielimy na synchroniczne i asynchroniczne. Przerzutniki synchroniczne mają specjalne wejście zegarowe (zwykłe oznaczane symbolem CLK) i mogą zmieniać stan tylko na narastającym lub opadającym zboczu sygnału zegarowego doprowadzonego do wejścia CLC. Przerzutniki asynchroniczne reagują na zmiany na wejściach natychmiast tzn. nie czekając na przyjście zbocza impulsu zegarowego. Często jednak ten sam układ elektroniczny przerzutnika jest jednocześnie układem synchronicznym i asynchronicznym.

Przerzutnik typu D jest przerzutnikiem synchronicznym opisanym tabelką.

Przerzutnik typu D najczęściej wyzwalany jest zboczem narastającym impulsu zegarowego. Mówimy, że „działa od przedniego zbocza”. Oznaczenie D pochodzi od słowa angielskiego delay czyli opóźnienie. D jest tzw. wejściem informacyjnym. Na wejście CLK podawany jest przebieg zegarowy. Przerzutnik typu D jest bardzo ważnym typem przerzutnika służy do konstrukcji m.in. rejestrów i liczników.

Rys.1. Przerzutnik typu D, synchronizowany narastającym zboczem (strzałka kończąca doprowadzenie sygnału zegarowego nie jest zaczerniona ani nie ma kółeczka); wejścia Set i Reset są asynchronicznymi wejściami ustawiającymi; sygnałem aktywnym jest poziom niski L czyli 0

Przerzutnik J-K jest dwuwejściowym przerzutnikiem synchronicznym opisanym tabelką.

Wejście J jest tzw. wejściem ustawiającym lub zapalającym wejście K jest tzw. wejściem zerującym lub gaszącym. Jednoczesne podanie 1 na wejścia J i K powoduje zmianę stanu przerzutnika na przeciwny. Przerzutnik J-K nieco częściej stosowany jest jako przerzutnik synchronizowany opadającym zboczem (ang negative edge triggered flip-flop) niż jako przerzutnik synchronizowany narastającym zboczem (ang positive edge triggered flip-flop).

Przykładem układu przerzutnika J-K synchronizowanego przednim zboczem (czyli narastającym zboczem) jest układ SN74108 serii SN74, a przykładem układu synchronizowanego opadającym zboczem jest układ SN74107.

Rys.2. Przerzutnik typu J-K, synchronizowany opadającym zboczem (strzałka kończąca doprowadzenie sygnału zegarowego nie jest zaczerniona ale ma kółeczko); wejście $\overline{CLR}$ jest asynchronicznymi wejściem zerującym; sygnałem aktywnym jest poziom niski L czyli 0

W technice cyfrowej stosowane są również bardzo podobne do przerzutników synchronicznych J-K przerzutniki synchroniczne R-S (R od ang. reset (wyzeruj), S od ang. set (ustaw 1)). Różnica w ich definicji polega jedynie na tym, że w przerzutniku R-S stan $R\cdot S=1$ jest zabroniony. Nie można jednocześnie usiłować zapalić i zgasić przerzutnika.

Przerzutnik typu T jest jednowejściowym przerzutnikiem synchronicznym opisanym tabelką.

Widać, że jedynka podana na wejście T zmienia stan przerzutnika na przeciwny. Przerzutnik typu T uzyskamy łatwo z przerzutnika J-K łącząc wejścia J i K razem.

Przerzutniki asynchroniczne to przerzutniki bistabilne nie mające wejścia zegarowego i ich stan zależy bezpośrednio od wartości wejść. Podstawowa koncepcja układu przerzutnika bistabilnego asynchronicznego to układ złożony z dwóch inweterów połączonych pętlą dodatniego sprzężenia zwrotnego.

Rys. 3. Podstawowa koncepcja układu przerzutnika bistabilnego; dwa inwetery połączone pętlą sprzężenia zwrotnego. Rysunki a) i b) ilustrują 2 stany stabilne układu

Przerzutnik r-s (czasami mówimy asynchroniczny przerzutnik R-S) to układ przerzutnika bistabilnego z dwoma wejściami asynchronicznymi R (reset, zerowanie, gaszenie) i S (set, ustawianie 1, zapalanie).

Rys.4. Przerzutnik bistabilny asynchroniczny R-S

Dwójka licząca lub przerzutnik typu t to przerzutnik bistabilny z jednym wejściem oznaczanym symbolem t, który zmienia stan w momencie pojawienia się opadającego zbocza prostokątnego impulsu podanego na wejście t.

Dwójkę liczącą łatwo można zrealizować za pomocą przerzutnika synchronicznego.

Rys. 5. Realizacja dwójki liczącej (przerzutnika typu t) za pomocą przerzutnika typu D

Rys. 6. Realizacja dwójki liczącej (przerzutnika typu t) za pomocą przerzutnika J-K

Licznik (ang counter lub binary counter) to układ elektroniczny przeznaczony do zliczania impulsów. Licznik ma wejście szeregowe na które podajemy impulsy (na ogół prostokątne) i wyjście równoległe na którym mamy słowo reprezentujące liczbę impulsów zliczonych (w ustalonym kodzie na ogół kodzie NKB). Licznik z reguły ma dodatkowe wejście ustawiające licznik w stanie początkowym tzw. wejście zerujące oznaczane najczęściej symbolem R (od ang. reset).

Liczniki dzielimy na synchroniczne i asynchroniczne. Jeśli przerzutniki wchodzące w skład licznika zmieniają stan dokładnie w momencie przyjścia opadającego zbocza zliczanego impulsu prostokątnego to taki licznik nazywamy synchronicznym. W sytuacji gdy zmiana stanu licznika wymuszana jest zmianą stanu innych przerzutników a więc z reguły odbywa się z pewnym opóźnieniem (por. opóźnienie bramek) to licznik nazywamy asynchronicznym.

Ważny jest kod numeryczny w jakim liczy licznik. Najczęściej jest to kod NKB, ale można budować liczniki liczące w innych kodach np. kodzie BCD czy kodzie Gray’a.

Rys.8. Licznik, impulsy prostokątne pojawiające się na wejściu układu nie muszą być okresowe choć często na wejście licznika podajemy przebieg zegarowy

Licznik modulo m (gdzie $m\in N,\ m\geq2$) to licznik przechodzący po wyzerowaniu przez stany 0,1,2,..., m-1,0, 1,2,...itd czyli podający na wyjściu liczbę impulsów wejściowych modulo m. Każdy typowy licznik jest licznikiem modulo pewna liczba m.

Najczęściej w praktyce wykorzystujemy liczniki modulo 2ⁿ czyli dla m=2ⁿ i jeśli mówimy licznik binarny to mamy na ogół na myśli taki właśnie licznik

Rys.9. Graf wyjaśniający zmiany stanu licznika modulo m; pojawienie się opadającego zbocza impulsu wejściowego (zbocze opadające oznaczone jest na rysunku symbolem 1/0) powoduje przejście licznika do następnego stanu (czyli zliczenie impulsu)

Liczniki programowane to liczniki w których liczba m jest podawana (w kodzie NKB) na specjalne wejście programujące.

Warto zauważyć, że każdy licznik jest jednocześnie dzielnikiem częstotliwości, który częstotliwość $f$ okresowego prostokątnego sygnału podawanego na wejście zamienia na przebieg prostokątny o mniejszej częstotliwości z reguły $f/2,\ f/2^2,...,\ f/2^k$.

Rys. 10. Licznik programowany, na wejście programujące podawana jest liczba $m$, $m\in N,\ m\geq2$

Rys. 11. Impulsy prostokątne podawane są na wejście licznika; impulsy są rejestrowane po przyjściu opadającego zbocza impulsu

Rys. 12. Licznik jako dzielnik częstotliwości

Rys. 13. Licznik asynchroniczny modulo $2^{n+1}$ z budowany z dwójek liczących (przerzutników typu t) $P_0,P_1,...,P_n$

Ogólnie rzecz biorąc liczniki dzielimy na

• liczniki jednokierunkowe
• liczniki dwukierunkowe czyli rewersyjne

Z kolei liczniki jednokierunkowe dzielimy na

• liczące w przód (kolejny impuls zwiększa zawartość licznika)
• liczące wstecz (kolejny impuls zmniejsza zawartość licznika)

Licznik rewersyjny to licznik ze specjalnym wejściem 1-bitowym określającym kierunek zliczania.

Istotnym parametrem licznika jest maksymalna dopuszczalna częstotliwość impulsów zliczanych. Dopuszczalna tzn. taka przy której licznik działa jeszcze poprawnie.

Komparatory dzielimy na równoległe i szeregowe. Komparatory równoległe to układy kombinacyjne porównujące dwa słowa binarne $a=a_1a_2...a_n$ i $b=b_1b_2...b_n$ w kodzie NKB.

Na wejście układu podajemy więc 2 słowa $a$ i $b$ i zależnie od wyniku porównania na jednym z 3 wyjść 1-bitowych pojawia się jedynka

Jeśli a = b to na wyjściu oznaczonym symbolem ”=” mamy ”1” (a na pozostałych ”0”).

Jeśli a > b (w kodzie NKB) to na wyjściu oznaczonym symbolem ”>” mamy ”1” (a na pozostałych ”0”).

Jeśli a < b (w kodzie NKB) to na wyjściu oznaczonym symbolem ”<” mamy ”1” (a na pozostałych ”0”).

Komparator szeregowy to układ sekwencyjny porównujący bit po bicie odpowiadające sobie bity słów $a=a_1a_2...a_n$ i $b=b_1b_2...b_n$ od strony bardziej znaczących bitów. Bity $a_i$ i $b_i$ są wprowadzane na wejście układu w takt zegara. Wynik porównania pojedynczych bitów musi być zapamiętany stąd konieczność zastosowania układu sekwencyjnego. Wynik wsteczny porównania uzyskujemy po n taktach zegara.

Rys. 6. Komparator równoległy porównuje dwa słowa binarne $a=a_1a_2...a_n$ i $b=b_1b_2...b_n$ traktując je jak słowa kodowe kodu NKB

Warto zauważyć, że najprostszym komparatorem z jednym wyjściem ”=” (komparatorem porównującym tylko 2 bity) jest zanegowana suma modulo 2.

Zaczniemy omawianie sumatorów od półsumatora, układu, który dodaje 2 bity bez uwzględnienia przeniesienia z poprzedniej pozycji.

Układ dodający 2 bity powinien mieć 2 wyjścia: wyjście sumy $s$ i wyjście przeniesienia $c$. Łatwo zauważyć, że układ półsumatora opisują 2 funkcje boolowskie $s=a\oplus b$ oraz $c=a\cdot b$, gdzie $s$ jest sumą a $c$ przeniesieniem. Układ realizujący półsumator pokazany jest na rys. 20.

Rys 1. Układ realizujący półsumator $s=a\oplus b$ (bit sumy), $c=a\cdot b$ (bit przeniesienia)

Sumator jednobitowy pełny to układ kombinacyjny dodający 2 bity z uwzględnieniem przeniesień. Sumator jednobitowy pełny ma 3 wejścia ($a_i$, $b_i$ - bity sumowane oraz $c_i$ przeniesienie z poprzedniej pozycji) oraz 2 wyjścia: wyjście sumy $s_i$ i wyjście przeniesienia na następną pozycję $c_{i+1}$. Łatwo zauważyć, że układ sumatora opisują 2 funkcje boolowskie

$s_i=a_i\oplus b_i\oplus c_i$ oraz $c_{i+1}=a_i\cdot b_i+(a_i+b_i)\cdot c_i$,

gdzie $s_i$ jest sumą, $c_{i+1}$ przeniesieniem na pozycję $i+1$ a $c_i$ przeniesieniem. na pozycję $i$. Układ realizujący sumator jednobitowy pełny pokazany jest na rys 2. Jeśli czas opóźnienia bramki oznaczymy przez $\Delta t$ to czas po którym uzyskujemy w tym układzie poprawny bit sumy to $2\Delta t$. Poprawny bit przeniesienia uzyskujemy po czasie $3\Delta t$.

Rys. 2. Układ realizujący jednobitowy sumator pełny

Sumator równoległy jest układem kombinacyjnym o strukturze pokazanej na rys. 3. Dodajemy 2 liczby $a$ i $b$ w zapisie NKB (o stałej długości $n+1$ słowa kodowego). Liczby dodawane $a$ i $b$ reprezentowane są słowami binarnymi

$a=a_n a_{n-1}...a_1a_0$ i $b=b_n b_{n-1}...b_1b_0$

Suma $s=a+b$ reprezentowana jest słowem $s_n s_{n-1}...s_1s_0$. Współpracujące ze sobą sumatory pełne realizują na kolejnych pozycjach słowa dodawanie $a_i+b_i$ (z uwzględnieniem przeniesień) a więc $s_i=a_i \oplus b_i \oplus c_i$ oraz $c_{i+1}=a_i\cdot b_i+(a_i+b_i)\cdot c_i$. Warto zauważyć, że słowo wyniku sumowania $s_n s_{n-1}...s_1s_0$ (odczytywane w $n+1$ bitowym w kodzie NKB) jest równe liczbie $s=a+b$ wtedy i tylko wtedy gdy $c_{n+1}=0$. Jeśli $c_{n+1}=1$ to mówimy, że wystąpił nadmiar przy dodawaniu w kodzie NKB. W typowych mikroprocesorach pojawienie się $c_{n+1}=1$ jest zapamiętywane, powoduje ustawienie przerzutnika znacznika przeniesienia CF (ang. carry flag) na 1. Oczywiście słowo $n+2$ bitowe $c_{n+1}s_ns_{n-1}...s_1s_0$ zawsze reprezentuje poprawnie w kodzie NKB ($n+2$ bitowym) liczbę $s$.

Rys. 3. Sumator równoległy zbudowany z jednobitowych sumatorów pełnych

Ogólnie rzecz biorąc w systemach cyfrowych słowa binarne możemy przetwarzać równolegle (tak jest szybciej) lub szeregowo czyli bit po bicie (tak jest oszczędniej tzn. mniejsza ilość 2
bramek jest potrzebna do realizacji układu).

Sumator szeregowy jest typowym układem z szeregowym przetwarzaniem informacji. Schemat układu pokazany jest na rys. 4. Układ dodaje szeregowo dwa słowa binarne $a=a_na_{n-1}...a_1a_0$ i $b=b_nb_{n-1}...b_1b_0$ bit po bicie od strony najmniej znaczących bitów tzn. w pierwszym takcie zegara podajemy na wejścia sumatora bity $a_0$ i $b_0$ w drugim $a_1$ i $b_1$ itd. Dodawanie trwa więc $n+1$ taktów zegara.

Rys. 4. Sumator szeregowy

Układ sumatora równoległego o strukturze pokazanej na Rys. 3. sumuje 2 liczby w czasie $(n+1)\Delta t$, gdzie $\Delta t$ jest czasem opóźnienia bramki. Stosując układ przewidywania przeniesień (ang. look ahead) możemy znacznie przyśpieszyć działanie układu sumatora równoległego. Żeby opisać działanie układu przewidywania przeniesień wprowadzamy dla każdej i-tej pozycji 3 pomocnicze funkcje (określające stan pozycji) zdefiniowane następująco

$P_i=a_1\oplus b_i\quad$- $P_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie propagacji

$G_i=a_ib_i\quad$- $G_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie generacji

$S_i=\overline{a_i}\cdot\overline{b_i}\quad$- $S_i=1$ wtedy i tylko wtedy gdy pozycja $i$ jest w stanie generacji 0

Zauważmy, że

$c_1=G_0+P_0c_0$

$c_2=G_1+P_1G_0+P_1P_0c_0$

$c_3=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0c_0$

$......$

$c_i=G_{i-1}+P_{i-1}G_{i-2}+P_{i-1}P_{i-2}G_{i-3}+\ldots+P_{i-1}P_{i-2}P_{i-3}...P_1G_0+P_{i-1}P_{i-2}P_{i-3}...P_0c_0$

$......$

$c_{n+1}=G_n+P_nG_{n-1}+P_nP_{n-1}G_{n-2}+\ldots+P_nP_{n-1}P_{n-2}...P_1G_0+P_nP_{n-1}P_{n-2}...P_0c_0$

Zatem gdybyśmy dysponowali bramkami o odpowiedniej ilości wejść, można by obliczyć każde przeniesienie w czasie $3\Delta t$. Układ sumatora wykorzystujący układ przewidywania przeniesień jest więc potencjalnie znacznie szybszy od zwykłego układu sumatora równoległego. Układ sumatora z przewidywaniem przeniesień pokazany jest na Rys.5.

Rys. 5. Sumator równoległy z układem przewidywania przeniesień

Mnożenie wykonujemy jako wielokrotne dodawanie z przesunięciem. Oczywiście można zaprojektować do wykonywania mnożenia układ kombinacyjny złożony z samych sumatorów ale liczba użytych sumatorów jest wtedy równa $m\cdot n$, gdzie $m$ i $n$ są długościami mnożonych słów.

Ogólnie rzecz biorąc pamięci dzielimy na ulotne (ang volatile memory) i nieulotne (ang. nonvolatile memory). Pamięci ulotne to takie, w których przechowywana informacja znika po wyłączeniu zasilania (tracimy ją bezpowrotnie) a nieulotne to takie, które nie tracą zapisanej informacji po wyłączeniu zasilania.

Wyobrażamy sobie pamięć jako zestaw $m$ rejestrów $n$ bitowych (por. rys 25), które nazywamy komórkami (ang locations). Każda komórka ma przyporządkowany adres $a \in$ jednoznacznie ją identyfikujący. Możemy więc powiedzieć, że pamięć to zestaw zaadresowanych rejestrów. Podstawowymi parametrem pamięci jest jej pojemność wyrażana na ogół liczbą pamiętanych bajtów oraz długość pamiętanego w pamięci słowa. Każda pamięć ma specjalne wejście tzw. wejście adresowe na które podawany jest adres wybranej komórki. Pamięci dzielimy na 2 zasadnicze grupy: pamięci ROM (tylko do odczytu) i pamięci RAM (do odczytu i zapisu).

Rys.1. Pamięć jako zestaw rejestrów (tzw. komórek) zaadresowanych liczbami całkowitymi ze zbioru ; z reguły $m=2^k$ dla pewnego $k \in N$, czyli liczba komórek pamięci jest na ogół potęgą 2

Pamięć ROM (ang. Read Only Memory) to inaczej tzw. pamięć stała (por. Rys. 2.). Jest to pamięć, z której możemy tylko odczytywać informacje podając na wejście adresowe pamięci ROM liczbę ze zbioru  czyli adres. Adres podawany jest z reguły w kodzie NKB (naturalny kod binarny). Nie tracimy danych po wyłączeniu zasilania pamięci ROM. Pamięć ROM zaliczana jest więc do kategorii pamięci nieulotnych (ang. nonvolatile memory). Wyjście danych jest na ogół wyjściem trójstanowym. Typowa pamięć stała ma 2 wejścia sterujące $\mathrm{\overline{OE}}$ (output enable) i $\mathrm{\overline{CE}}$ (chip enable). Stan wysokiej impedancji wyjścia uzyskujemy dla $\mathrm{\overline{OE}=1}$. Sygnał $\mathrm{\overline{CE}=1}$ wyłącza układ ROM. Jeśli $\mathrm{\overline{OE}=0}$ i $\mathrm{\overline{CE}=0}$, to na wyjściu mamy słowo n-bitowe napisane w pamięci pod adresem a.

Żeby pamięć ROM była użyteczna, musi być w pewien sposób jak mówimy zaprogramowana, tzn. do jej komórek muszą być wpisane słowa, które chcemy pamiętać. Współczesne pamięci ROM mogą być albo programowane maską w fabryce albo mogą być też w łatwy sposób programowane przez użytkownika. (są to tzw. pamięci PROM od ang. Programmable ROM).

Istnieje wiele typów pamięci PROM m.in. pamięci EPROM (Electrically Programmable ROM), EEPROM (Electrically Erasable ROM) oraz pamięci typu flash. Pamięci flash stanowią odmianę pamięci EEPROM czyli pamięci kasowalnych elektrycznie. Pamięci flash dają się jednak kasować (w całości lub dużych blokach) bardzo szybko (w około 1ms).

Najczęściej stosowanymi obecnie pamięciami ROM są właśnie pamięci typu flash. Np. część systemu operacyjnego komputera nazywana BIOS (Basic Input Output System) jest zapisywana z reguły w pamięci typu flash.

Z punktu widzenia teorii układów logicznych pamięć ROM jest uniwersalnym układem kombinacyjnym. Dlatego też wygodnie jest małe pamięci ROM realizować jako tzw. układy PLA (ang Programmable Logic Array) (por. następny podrozdział). Jednocześnie za pomocą pamięci ROM można łatwo zrealizować dowolny układ kombinacyjny lub automat skończony. Istota rzeczy polega tu oczywiście na zapamiętaniu funkcji boolowskiej lub funkcji przejść i wyjść opisującej automat.

Do współczesnych pamięci PROM można z reguły dane zapisywać wielokrotnie, ale zapis nowych danych trwa relatywnie długo w porównaniu z czasem odczytu lub wymaga użycia specjalnych urządzeń programujących tzw. programatorów (por. pamięci PROM, EPROM, EEPROM).

Wszystkie pamięci ROM są pamięciami półprzewodnikowymi choć oczywiście można skonstruować pamięć w której słowa binarne będziemy pamiętać za pomocą odpowiednio włączonych przełączników mechanicznych.

Rys. 2. Pamięć stała czyli pamięć ROM

Pamięć RAM (ang. Random Access Memory) to inaczej pamięć o dostępie swobodnym. Jest to uporządkowany zestaw rejestrów (komórek), z których każdy jest jednoznacznie identyfikowany przez liczbę z  czyli adres. Różnica pomiędzy pamięciami ROM i RAM polega na tym, że do komórek pamięci RAM możemy zapisywać słowa binarne i odczytywać z nich zapisane słowa, natomiast pamięć ROM służy zasadniczo tylko do odczytu.

Pamięć RAM (por. Rys. 3) ma wejście adresowe, wejście danych wyjście danych i dwa wejścia sterujące: wejście wyboru układu $\mathrm{\overline{CE}}$ (Chip Enable) (czasami oznaczane jako $\mathrm{\overline{CS}}$ od ang. chip select) i wejście $\mathrm{R/ \overline{W}}$ mówiące o tym czy dane zapisujemy czy odczytujemy. Adres podawany jest z reguły jako słowo binarne kodzie NKB (naturalny kod binarny). Najczęściej adresy są kolejnymi liczbami całkowitymi od 0 do $m=2^k-1$, gdzie k jest długością słowa adresowego. Wszystkie adresy pamięci nazywamy przestrzenią adresową.

Rejestry składające się na pamięć nazywamy komórkami (pamięci). Liczbę komórek pamięci nazywamy pojemnością pamięci. Typowe pojemności pamięci RAM we współczesnym systemie mikrokomputerowym to 128 MB do 1 GB, ale można spotkać stacje robocze z pamięcią RAM np. 4GB. Z kolei w bardzo prostych mikroprocesorach jednoukładowych stosowane są pamięci RAM np. o pojemności 256 B (por. mikroprocesory rodziny Intel MCS-51). Warto w tym miejscu przypomnieć, że przy określaniu pojemności pamięci B oznacza bajt, b oznacza bit, k (kilo) oznacza 1024, M (mega) oznacza 2²⁰, G (giga) oznacza 2³⁰.

Pamięci RAM są z reguły półprzewodnikowymi pamięciami ulotnymi pełniącymi w systemie cyfrowym funkcję tzw. pamięci operacyjnej lub pamięci głównej. Z punktu widzenia teorii układów logicznych pamięć RAM jest układem sekwencyjnym.

Rys. 3. Pamięć o dostępie swobodnym czyli pamięć RAM

Pamięci RAM dzielimy na pamięci statyczne (pamięci SRAM) i pamięci dynamiczne (pamięci DRAM). SRAM (Static Random Access Memory) to tzw. statyczna pamięć RAM. Elementem pamiętającym takiej pamięci jest przerzutnik bistabilny z reguły zrealizowany w technice CMOS. Pamięć SRAM jest więc ulotna (ang. volatile memory). Po wyłączeniu i ponownym włączeniu napięcia zasilającego przerzutnik stanowiący komórkę elementarną może się ustawić w dowolnym z dwu możliwych stanów. W pamięci SRAM nie ma konieczności odświeżania komórek elementarnych jak w pamięciach DRAM, o których za chwilę. Pamięci SRAM mają mniejszy czas dostępu (są szybsze) niż pamięci DRAM ale komórka elementarna zajmuje więcej miejsca na chipie stąd mniejsze pojemności tych pamięci. Pamięci SRAM stosowane są w systemach komputerowych jako szybkie pamięci podręczne czyli pamięci typu cache poziomu pierwszego (pamięci cache L1) i poziomu drugiego (pamięci cache L2).

DRAM (ang. Dynamic Random Access Memory) to tzw. dynamiczna pamięć RAM. Pamięci tego typu są zbudowane z tranzystorów MOS. Elementem pamiętającym 1-bitowej komórki elementarnej pamięci DRAM jest kondensator a ściśle rzecz biorąc pojemność wejściowa tranzystora MOS o wartości 30-50 fF (femtofarady). Zasada pamiętania 0 i 1 jest więc taka sama jak w przypadku układów próbkująco-pamiętających (układów S/H) i tak jak w przypadku układów S/H z powodu nieuniknionych prądów upływu następuje szybkie rozładowywanie się kondensatora. Pociąga to za sobą konieczność okresowego doładowywania komórek pamiętających stan wysoki H co nazywamy odświeżaniem pamięci DRAM. W typowej pamięci DRAM odświeżanie odbywa się co około kilkanaście ms. Z reguły nie odświeżamy od razu całej pamięci DRAM ale pewien jej fragment potem następny itd. Czas dostępu do pamięci DRAM jest rzędu 50 ns. Typowa organizacja kostek pamięci DRAM to np 64M x 4 (czterobitowe słowa wyjściowe), 128M x 2 (dwubitowe słowa wyjściowe), 256Mx1 (jednobitowe słowa wyjściowe).

Pamięci DRAM dzielą się na synchroniczne i asynchroniczne. Obecnie prawie wyłącznie stosuje się pamięci synchroniczne tzw. SDRAM (Synchronous DRAM) pracujące w takt zegara systemu i umożliwiające wykonanie kolejnych czynności przez pamięć zakładkowo (pipelining) co pozwala znacznie skrócić cykl odczytu. Dane przesyłane są w seriach tzw. "burst". Pamięci synchroniczne wykorzystujące narastające i opadające zbocze zegara noszą nazwę DDR SDRAM (Double Data Rate SDRAM). Typowe pamięci DDR SDRAM pracują z magistralami taktowanymi zegarem 133 MHz.

Podstawowe parametry pamięci RAM to czas dostępu do pamięci (access time), czas cyklu (ang cycle time) i pojemność pamięci RAM.

Pamięci (kostki pamięci czyli chipy) SDRAM umieszcza się najczęściej na małych płytkach drukowanych tzw. modułach DIMM (ang. Dual In line Memory Module).

Pamięci specjalne to pamięci FIFO, LIFO i pamięci CAM.

Pamięć FIFO (ang. First in - First out) to inaczej kolejka.
Pamięć LIFO (ang. Last in - First out) to inaczej stos.
Pamięć CAM (ang. Content Addressable Memory) to inaczej pamięć asocjacyjna lub pamięć skojarzeniowa. Pamięci specjalne zostaną omówione szerzej w rozdziale o architekturze systemów komputerowych.

Rys.2. Układ sterowania mikroprogramowanego

Mikroprogramowane układy sterowania są prostą regularną metodą projektowania układów sterujących systemów cyfrowych. Na Rys.2. pokazany jest schemat mikroprogramowanego układu sterującego. Z punktu widzenia teorii układów logicznych jest to automat skończony. Układ pracuje synchronicznie w takt zegara. Do rejestru adresu mikroinstrukcji wczytywany jest w każdym takcie zegara adres pod którym w pamięci ROM (pamięci mikroprogramów) umieszczone są sygnały sterujące. Sygnały sterujące pojawiają się więc wyjściu układu w takt zegara. Sygnały warunków $w_1,w_2,\ldots,w_r$, za pomocą tzw. sekwensera mogą modyfikować sposób w jaki wykonuje się mikroprogram. Sygnały sterujące sterują przepływem danych w części wykonawczej systemu.

Rejestr liczący to układ pokazany na Rys.3.

Rys.3. Rejestr liczący

Rejestr liniowy nazywamy też rejestrem LFSR ( ang. Linear Feedback Shift Register). Jest to rejestr liczący z funkcją boolowską $f$ zadaną wzorem

$f(Q_n,Q_{n-1},...,Q_0)=k_nQ_n \oplus k_{n-1}Q_{n-1} \oplus .... \oplus k_0Q_0 \qquad\qquad\qquad (^*)$

gdzie $(k_n,k_{n-1},...,k_0)\in\{0,1\}^{n+1}$ jest ustalonym słowem binarnym definiującym rejestr liniowy. Funkcja $f:\{0,1\}^{n+1}\rightarrow\{0,1\}$ zdefiniowana wzorem (*) jest przekształceniem liniowym stąd nazwa rejestru. Rejestr liniowy jest szczególnym przypadkiem tzw. maszyny liniowej lub automatu liniowego (Linear Sequential Machine). Każdy rejestr liniowy jest scharakteryzowany przez swój tzw. wielomian charakterystyczny

$w(x)=k_nx^n\oplus k_{n-1}x^{n-1}\oplus ... \oplus k_1x\oplus k_0$

Jest to wielomian o współczynnikach w ciele $Z_2$. Jeśli wielomian charakterystyczny jest nierozkładalny, to rejestr liniowy wychodzący z dowolnego stanu różnego od samych zer przechodzi przez $2^{n+1}-1$ stanów.

Rejestry liniowe stosowane są między innymi jako generatory liczb pseudolosowych.