Wstęp do Informatyki
Wykład 3
Cyfrowe układy logiczne
Autor: Dr hab. Marek J. Greniewski
Wstęp do Informatyki
Wykład 3
Cyfrowe układy logiczne
Autor: Dr hab. Marek J. Greniewski
Podział na części architektoniczną i
układową współczesnego komputera
Układy we-wy
Procesor
Kompilator
System
operacyjny
(Windows 2K)
Aplikacje (np. Netscape)
Układy cyfrowe
Obwody
scalone
Lista rozkazów
określająca architekturę
Ścieżki danych i sterowanie
Bramki i
elementy
pamięci
Pamięć
Hardware
Software
Assemble
r
Cyfrowe układy logiczne
.
Elementy podstawowe
• Do realizacji funkcji przechowywania, przenoszenia,
przetwarzania i sterowania komputera potrzebne
są tylko
dwa typy elementów podstawowych:
– bramki
– komórki pamięci
.
• Bramka jest przyrządem, który realizuje prostą
funkcję logiczną, taką jak, AND, OR, NOT, NOR,
NAND
• Komórka pamięci jest przyrządem, który może
przechowywać pojedynczy bit danych - oznacza to,
że przyrząd ten w określonym czasie może
znajdować się w jednym z dwóch stabilnych stanów
2. Bramka AND (i) - iloczyn logiczny
3. Bramka OR (lub) - suma logiczna
4. Bramka NOT (nie) - negacja
5. Bramka NAND - negacja iloczynu
6. Bramka NOR - negacja sumy
7. Bramka XOR - równoważność
8. Bramka XNOR - nierównoważność
PODSTAWOWE BRAMKI LOGICZNE
9. BUFOR
1. Co to jest bramka?
• Kombinacyjne układy cyfrowe najczęściej
budowane są za pomocą tzw. bramek.
• Bramką (
gate
) nazywa się układ elektroniczny
realizujący funkcję boolowską, posiadający
określoną liczbę wejść i jedno wyjście.
• Jak każdy układ elektroniczny, tak i bramki
opisywane są wieloma parametrami zarówno
funkcjonalnymi (liczba wejść, liczba wyjść,
realizowana funkcja, przeznaczenie i in.), jak i
elektrycznymi (pobierana moc zasilania,
obciążalność prądem układów sterujących
wejściami, możliwość wysterowania wejść
innych układów itp.) oraz dynamicznymi
(czasy zmiany sygnału na wyjściu układu,
wnoszone opóźnienia i inne).
Co to jest BRAMKA?
(początek)
• Bramki produkowane są jako układy
scalone.
• Do produkcji układów scalonych były i są
stosowane różne technologie.
• Pierwsza z nich to technologia TTL
(
transistor-transistor
logic
),
jedną
z
następnych CMOS (
complementary MOS
).
W jednym układzie scalonym znajdowało
się początkowo kilka bramek.
• Przykładowo w jednym układzie scalonym
znajdowały się 4 bramki dwuwejściowe lub
trzy bramki trzy-wejściowe, lub dwie
bramki czterowejściowe, lub jedna bramka
ośmiowejściowa.
• Natomiast współczesne obwody scalone
wielkiej skali integracji - VLSI (czyli
Very
Large Scale Integration
) zawierają już
miliony bramek.
Co to jest BRAMKA?
(kontynuacja)
• Bramki AND, OR, NAND i NOR mogą
występować jako wielowejściowe.
• Bramki sumy modulo 2 XOR występują tylko jako
dwuwejściowe.
• Bramka NOT jest jednowejściowa.
• Spotyka się także bramki w wykonaniu
specjalnym. Mogą to być tzw. bramki z otwartym
kolektorem (
open collector
) - OC stosowane
celem uzyskania możliwości zwierania wyjść
bramek lub bramki trzystanowe (
three-state
logic
) wykorzystywane np. w magistralach
(szynach) komputera.
Co to jest BRAMKA?
(zakończenie)
BRAMKA
„AND”
Bramka AND realizuje iloczyn logiczny. Jeżeli na jej wejściach podane są jedynki
to na wyjściu jest jedynka, w każdym innym przypadku na wyjściu jest zero.
A
B
Y
Y=A•B
A
B
Y
1
0
1
0
1
0
Tablica zero-
jedynkowa
Y=A•B
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
PRZYKŁAD BRAMKI „AND”
0
1
=
0
Przykład pokazuje przypadek, w którym na
wejścia (AB) zostały podane sygnały zero i jeden,
w wyniku czego na wyjściu (Y) otrzymujemy zero.
A
B
Y = A • B
0
1
0
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
0
1
0
BRAMKA
„OR”
Bramka OR realizuje sumę logiczną. Jeżeli przynajmniej na jednym wejściu
podana jest jedynka, to na wyjściu (Y) jest jedynka.
A
B
Y
Y=A+B
Y=A+B
Tablica zero-
jedynkowa
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
A
B
Y
1
0
1
0
1
0
PRZYKŁAD BRAMKI „OR”
0
+
1
=
1
Przykład pokazuje przypadek, w którym
na wejścia (AB) zostały podane sygnały
zero i jeden,w wyniku czego na wyjściu
(Y) otrzymujemy jedynkę.
A
B
0
1
1
Y = A + B
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
0
1
1
BRAMKA
„NOT”
A
Y
Y=A
Bramka NOT realizuje operację zaprzeczenia. Jeżeli na wejściu podana jest
jedynka, to na wyjściu (Y) będzie zero i odwrotnie.
Y=A
A
Y
0
1
1
0
Tablica zero-
jedynkowa
A
Y
1
0
1
0
PRZYKŁAD BRAMKI „NOT”
1
Przykład pokazuje przypadek, w którym na
wejście (A) podana została jedynka, w wyniku
czego na wyjściu (Y) otrzymujemy zero.
A
1
=
0
0
Y = A
A
Y
0
1
1
0
0
1
BRAMKA
„
NAND”
Bramka NAND jest złożona z bramek NOT i AND. Zasada działania jest taka sama
jak bramki AND z tą różnicą, że sygnał wyjściowy jest jeszcze negowany.
A
B
Y
Y=A•B
A
B
Y
1
0
1
0
1
0
Y=A•B
Tablica zero-
jedynkowa
A
B
Y
0
0
1
0
1
1
1
0
1
1
1
0
PRZYKŁAD BRAMKI „NAND”
Przykład pokazuje przypadek, w którym na
wejścia (AB) zostały podane sygnały zero
i jeden, w wyniku czego na wyjściu (Y)
otrzymujemy negację zera, czyli jedynkę.
A
B
0
1
1
0
1
=
0
=
1
Y = A • B
A
B
Y
0
0
1
0
1
1
1
0
1
1
1
0
0
1
1
BRAMKA
„NOR”
Bramka NOR jest złożona z bramek: NOT i OR. Zasada działania jest taka sama jak
bramki OR z tą różnicą, że sygnał wyjściowy jest jeszcze negowany.
A
B
Y
Y=A+B
A
B
Y
1
0
1
0
1
0
Y=A+B
Tablica zero-
jedynkowa
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
0
PRZYKŁAD BRAMKI „NOR”
Przykład pokazuje przypadek, w którym na wejścia
(AB) zostały podane sygnały zero i jeden, w wyniku
czego na wyjściu (Y) otrzymujemy jedynkę.
A
B
Y = A + B
0
+
1
=
1
=
0
0
1
0
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
BRAMKA
„
XOR”
Jeżeli sygnały wejściowe są sobie równe (A=B=0 lub A=B=1),
to na wyjściu (Y) jest zero.
A
B
Y
Y=A + B
A
B
Y
1
0
1
0
1
0
Y=A + B
Y=A•B + A•B
Tablica zero-
jedynkowa
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
PRZYKŁAD BRAMKI „XOR”
Przykład pokazuje przypadek, w którym na wejścia
(AB) zostały podane sygnały zero i jeden, w wyniku
czego na wyjściu (Y) otrzymujemy jedynkę.
A
B
1
0
x
1
+
0
x
1
=
1
+
0
=
1
0
1
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
0
Y=A + B
Y=A•B + A•B
0
1
1
Y
BRAMKA
„XNOR”
Jeżeli sygnały wejściowe są sobie równe (A=B=0 lub A=B=1),
to na wyjściu (Y) jest jedynka.
A
B
Y
Y=A B
A
B
Y
1
0
1
0
1
0
Y=A B
Y=A•B + A•B
Tablica zero-
jedynkowa
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
1
PRZYKŁAD BRAMKI „XNOR”
Przykład pokazuje przypadek, w którym na
wejścia (AB) zostały podane sygnały zero i jeden,
w wyniku czego na wyjściu (Y) otrzymujemy zero.
0
x
1
+
0
x
1
=
0
+
0
=
0
Y=A B
Y=A•B + A•B
A
B
Y
0
0
1
0
1
0
1
0
0
1
1
1
Y
0
1
0
A
B
0
1
0
BUFOR czyli np. linia
opóźniająca
A
Y
Y=A
A
Y
0
0
1
1
Y=A
Tablica zero-
jedynkowa
Zastosowanie bramek
• Z bramek budowane są układy kombinacyjne,
takie jak:
– Multiplexery,
– Demultiplexery,
– Kodery,
– Dekodery.
• Z bramek budowane są przerzutniki – składowe
układów sekwencyjnych, takie jak
– Przerzutnik S-R,
– Przerzutnik synchroniczny S-R,
– Przerzutnik D,
– Przerzutnik J-K.
• Przerzutniki są wykorzystywane jako składowe:
– Rejestrów (np. równoległych i przesuwanych),
– Liczników (np. szeregowych, synchronicznych).
Logika kombinacyjna CL
• y
i
= f(x
0
, x
1
, ..., x
n-1
) gdzie x, y przyjmują wartości {0,
1}, zaś indeks i przyjmuje wartości {0, 1, 2, ..., n-1}
• y jest funkcją jedynie od x
• jeśli zmienimy wartości zmiennych x, to wartość y
zmieni się niemal natychmiast
• oznacza to, że czas propagacji układu
kombinacyjnego można pominąć!!!
Układy kombinacyjne
• Układ kombinacyjny jest zbiorem wzajemnie połączonych
bramek, którego stan wyjść w dowolnej chwili (kwancie
czasowym – określonym taktem zegara) jest wyłącznie funkcją
stanu wejść w tej samej chwili.
• Podobnie jak w przypadku pojedynczej bramki, po ustaleniu
stanu na wejściu – prawie natychmiast pojawia się sygnał na
wyjściu, przy czym występuje tylko opóźnienie bramkowe,
odpowiadające czasowi propagacji sygnału elektrycznego w
bramce.
• Ogólnie rzecz biorąc, układ kombinacyjny zawiera n wejść i m
wyjść binarnych i realizuje określone funkcje boolowskie.
• Układy kombinacyjne budowane są z bramek.
• Złożoność funkcji jest ograniczoną związkiem pomiędzy
długością sumy czasu propagacji najdłuższej ścieżki danych
binarnych układu kombinacyjnego – a długością sygnału
pojedynczego taktu zegara. Suma czasu propagacji sygnału w
układzie kombinacyjnym nie może przekraczać czasu trwania
pojedynczego sygnału taktującego zegara.
Zasada taktowania
zegarem
układu
kombinacyjnego
Zegar
.
.
.
.
.
.
.
.
.
.
.
.
Układ kombinacyjny
Algebra Boole’a
•
Do projektowania i analizowania cyfrowych układów
logicznych w komputerach i innych systemach cyfrowych
używana jest gałąź matematyki zwana algebrą Boole’a.
•
Nazwano ją tak dla uczczenia brytyjskiego matematyka
Georga’a Boole’a, który zaproponował podstawowe zasady
tej algebry w pracy zatytułowanej „An Investigation of the
Laws of Thought on Which to Found Mathematical Theories
of Logic and Probabilities (Badania praw myśli, które mogą
być podstawą matematycznych teorii logiki i
prawdopodobieństwa)”.
•
W roku 1938 Claude Shannon, wówczas asystent na
wydziale elektrycznym MIT (późniejszy twórca teorii
informacji), zasugerował zastosowanie algebry Boole’a do
rozwiązywania problemów projektowania układów
przekaźnikowych.
•
Metody Shannona zostały następnie użyte do analizowania
oraz projektowania elektronicznych układów cyfrowych.
Algebra Boole’a
• Podobnie jak inne rodzaje algebry, algebra Boole’a
używa zmiennych i operacji.
• W tym przypadku są to logiczne zmienne i
operacje, które mogą przyjmować wartości 1
(
Prawda
) i 0 (
Fałsz
), natomiast podstawowymi
operacjami logicznymi są
AND
(i),
OR
(lub) i
NOT
(nie).
• Trzy inne użyteczne operatory algebry Boole’a to
XOR
(albo – czyli lub wykluczające),
NAND
(nie-i)
oraz
NOR
(nie-lub).
• Operator
NAND
jest zdefiniowany jako:
a
NAND
b =
NOT
( a
AND
b)
• Operator
NOR
jest zdefiniowany jako:
a
NOR
b =
NOT
( a
OR
b)
• Natomiast operator
XOR
jest zdefiniowany jako:
a
XOR b
= ( a
AND
b)
OR
( a
NAND
b).
Algebra Boole’a
podstawowe tożsamości
a b
NOT
a a
AND
b a
OR
b a
XOR
b a
NAND
b a
NOR
b
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 1 0
1 1 0 1 1 0 0 0
Podstawowe postulaty
a * b = b * a a + b = b + a
Prawo przemienności
a * (b + c) = (a * b) + (a * c) a + (b * c) = (a + b) * (a + c)
Prawo rozdzielczości
1 * a = a 0 + a = a
Prawo tożsamości
Pozostałe tożsamości
a * NOTa = 0 a + NOTa = 1
Prawo odwrotności
0 * a = 0 1 + a = 1
a * (b * c) = (a * b) * c a + (b + c) = (a + b) + c
Prawo łączenia
NOT(a * b) = NOTa + NOTb NOT(a + b) = NOTa * NOTb
Twierdzenie DeMorgana
Podstawowe bramki logiczne
Nazwa Symbol graficzny
Funkcja
Boolowska
Tabelka funkcji
AND
F = A • B
lub
F = AB
A | 0 0 1 1
B | 0 1 0 1
F | 0 0 0 1
OR
F = A + B
A | 0 0 1 1
B | 0 1 0 1
F | 0 1 1 1
NOT
__
F = A
A | 0 1
F | 1 0
NAN
D
___
F = (A • B)
A | 0 0 1 1
B | 0 1 0 1
F | 1 0 0 0
NOR
_____
F = (A + B)
A | 0 0 1 1
B | 0 1 0 1
F | 1 0 0 0
A
B
A
B
F
F
A
B
A
B
F
F
A
F
F
Twierdzenia DeMorgan’a
NAND Gate
NOR Gate
Out
A
B
A
B
Out
A B Out
1
1
1
0 0
0 1
1 0
1 1
0
A
B
Out
Out
A
B
Out = A • B = A + B
A B Out
0 0
1
0 1
0
1 0
0
1 1
0
A B Out
1 1
1
1 0
1
0 1
1
0 0
0
0 0
0 1
1 0
1 1
A B
A B Out
1 1
1
1 0
0
0 1
0
0 0
0
0 0
0 1
1 0
1 1
A B
Out = A + B = A • B
Układy kombinacyjne
• Realizacja funkcji Boole’a.
• Realizacja wszystkich funkcji boolowskich za
pomocą bramki NAND.
• Realizacja wszystkich funkcji boolowskich za
pomocą bramki NOR.
• Multipleksery.
• Dekodery.
• Sumatory.
Zastosowanie bramki
NAND
A
A’
A
B
(A*B)’
A*B
A
B
A’
B’
A+B
Zastosowanie bramki
NOR
A
A’
A
B
(A+B)’
A+B
A
B
A’
B’
A*B
Definiowanie układu
kombinacyjnego
• Układ kombinacyjny jest zbiorem wzajemnie
połączonych bramek, którego stan wyjść w dowolnej
chwili jest wyłącznie funkcją stanu wejść w tej samej
chwili.
• Układ kombinacyjny zawiera n wejść i m wyjść
binarnych
• Podobnie jak bramkę, układ kombinacyjny można
zdefiniować na jeden z trzech sposobów:
– Tablicą zero-jedynkową. Dla każdej z 2
n
możliwych
kombinacji sygnałów wejściowych podana jest wartość
binarna każdego z m sygnałów wyjściowych.
– Schematem graficznym – czyli schematem połączeń bramek
– Funkcjami Boole’owskimi – gdzie każdy sygnał wyjściowy
jest wyrażony jako funkcja sygnałów wejściowych.
Układ opisany tablicą zero-
jedynkową
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
Układ opisany schematem
wersja (a)
A
B
C
F
Układ opisany schematem
wersja (b)
A
B
C
F
Układ opisany funkcją
Boolea’owską
(a) F = A’ * B * C’ + A’ * B * C + A
* B * C’
(b) F =
(A+B+C)*(A+B+C’)*(A’+B+C)*(
A’+B’+C’)
Uproszczenia
algebraiczne
F = (A’ * B + B * C’)
F = B * (A’ + C’)
A
C
B
F
Realizacja układu z bramek
NAND
A
B
C
F
F = B * (A’ +
C’)
Multiplekser
• Multiplekser jest układem kombinacyjnym, który łączy wiele
wejść, (np. D0, D1, D2 i D3) z jednym wyjściem F, a o
którego działaniu decydują sygnały sterujące (np. S1 i S2).
• Na wyjście F multipleksera dostarczany jest sygnał z
jednego wybranego wejścia. Sygnały sterujące
multiplekserem decydują o wyborze wejścia.
• Multipleksery są używane w układach cyfrowych do
sterowania przepływem sygnałów i danych.
• Przykładem jest ładowanie licznika programu (PC). Liczba
wprowadzana do licznika programu, może pochodzić z
jednego z kilku źródeł:
– Układu pół-sumatora, jeśli stan PC ma być inkrementowany w celu
określenia adresu następnego rozkazu
– Rejestru rozkazu (IR), jeśli został właśnie wykonany rozkaz skokowy
używający adresu bezpośredniego
– Wyjścia ALU, jeśli rozkaz skokowy określa adres, używając trybu
indeksowego.
Tablica multipleksera
pokazująca jakim kombinacjom sygnałów
sterującym S1, S2 odpowiada przełączenie
poszczególnych wejść na wyjście
S2
S1
F
0
0
D0
0
1
D1
1
0
D2
1
1
D3
Symbol multipleksera
MUX
4 do 1
D0
D
1
D2
D3
F
S1
S2
W
e
jś
ci
a
Sterowanie
Wyjście
Schemat multipleksera
S1
S2
D0
D1
D2
D3
F
Wejście multiplekserowe
do PC
MUX
0
4 do 1
MUX
1
4 do 1
MUX
15
4 do 1
S1
S2
S1
S2
S1
S
2
PC
0
PC
1
PC
15
C
0
IR
0
ALU
0
C
1
IR
1
ALU
1
C
15
IR
15
ALU
15
Przykład dotyczący 16 bitowego adresu (PC
0
, PC
1
, ... , PC
15
).
Źródła (C
0
, C
1
, ... , C
15
), (IR
0
, IR
1
, ... , IR
15
) oraz ALU – są połączone
z liniami wejściowymi poszczególnych multiplekserów, zaś wyjścia tych
ostatnich – połączone są do poszczególnych bitów rejestru PC.
Dekoder
•
Dekoder jest układem kombinacyjnym o pewnej liczbie linii
wyjściowych, z których w określonej chwili sygnał może być
wysłany na jedynie jedną linię, zależnie od kombinacji
sygnałów na liniach wejściowych.
•
Ogólnie mówiąc, dekoder ma N wejść i
2
N
wyjść.
•
Dekodery znajdują wiele zastosowań w komputerach.
Jednym z przykładów zastosowań jest dekodowanie adresu.
•
Załóżmy dalej, że chcemy zbudować pamięć 1-kilobajtową
przy użyciu 4 układów RAM o pojemności 256x8 bitów
każdy. Przy czym, chcemy mieć jedną zunifikowaną
przestrzeń adresową, którą możemy podzielić następująco:
– Adresy szesnastkowe od 0000 do 00FF układ pamięciowy RAM 0
– Adresy szesnastkowe od 0100 do 01FF układ pamięciowy RAM 1
– Adresy szesnastkowe od 0200 do 02FF układ pamięciowy RAM 2
– Adresy szesnastkowe od 0300 do 03FF układ pamięciowy RAM 3
Tablica dekodera
Pokazuje jakiej kombinacji sygnałów
wejściowych A, B, C
- odpowiada pojawienie się sygnału x na jednym
z wyjść
A
B
C
Dan
e
D0 D1 D2 D3 D4 D5 D6 D7
0
0
0
x
x
0
0
0
0
0
0
0
0
0
1
x
0
x
0
0
0
0
0
0
0
1
0
x
0
0
x
0
0
0
0
0
0
1
1
x
0
0
0
x
0
0
0
0
1
0
0
x
0
0
0
0
x
0
0
0
1
0
1
x
0
0
0
0
0
x
0
0
1
1
0
x
0
0
0
0
0
0
x
0
1
1
1
x
0
0
0
0
0
0
0
x
Symbol dekodera
Dekoder
N do 2
N
N – bitowy
adres miejsca
przeznaczenia
Wejście
danych
2
N
wyjść binarnych
Przykład dekodowania
adresu
256x8
RAM
Dekoder
2 do 4
256x8
RAM
256x8
RAM
256x8
RAM
A0
A7
A8
A9
Zezwolenie
Zezwolenie
Zezwolenie
Zezwolenie
Schemat
dekodera
A
B
C
D0
D1
D2
D3
D4
D5
D6
D7
000
001
010
011
100
101
110
111
Pamięć stała ROM
• Układy kombinacyjne są często określane jako układy
„bez pamięci”, ponieważ ich wyjścia zależą jedynie od
bieżącego stanu ich wejść, a żadne informacje historyczne
o poprzednich stanach wejść nie są zachowywane.
• Istniej jednak pewien rodzaj pamięci, który jest
realizowany za pomocą układów kombinacyjnych, a
mianowicie pamięć stała ROM.
• ROM jest pamięcią, która umożliwia wykonanie wyłącznie
operacji odczytu. Informacja binarna zawarta w ROM jest
w związku z tym trwała. Jest ona zapisywana w pamięci
ROM w toku procesu wytwarzania modułu pamięci.
• Wobec tego określona kombinacja sygnałów wejściowych
ROM – podana na linie adresowe, prowadzi zawsze do tej
samej kombinacja sygnałów na liniach wyjściowych.
Tablica pamięci stałej
ROM
------Linie wejściowe------ ----- Linie
wyjściowe------
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
1
1
0
0
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
0
0
1
0
0
1
1
1
0
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
0
1
0
0
1
1
1
1
1
1
0
0
0
64-bitowa pamięć ROM
D
e
ko
d
e
r 4
x
1
6
X
1
X
2
X
3
X
4
Z
1
Z
2
Z
3
Z
4
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Sumatory
•
Obszarem o zasadniczym znaczeniu, którego
jeszcze nie rozpatrywaliśmy, są operacje
arytmetyczne.
•
Obecnie omówimy, jako przykład funkcję
dodawania binarnego liczb.
•
Suma binarna różni się tym od sumy w algebrze
Boole’a, że wynik obejmuje przeniesienie
pomiędzy pozycjami binarnymi dodawanych
liczb binarnych.
•
Dodawanie binarne można wyrazić za pomocą
wyrażeń algebry Boolea.
Tablica dodawania
binarnego
C
in
A
B
Suma
C
out
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Sumator 4-bitowy
C
3
S
y
g
n
a
ł
p
rz
e
p
e
łn
ie
n
ia
C
in
C
2
C
in
C
1
C
in
C
0
C
in
0
S
3
S
2
S
1
S
0
A
3
B
3
A
2
B
2
A
1
B
1
A
0
B
0
Wzory na stany dwóch wyjść
sumatora
suma
= A’ * B’ * C + A’ * B * C’ + A * B * C + A * B’ * C’
= (A’ * B’ + A * B) * C + (A’ * B + A * B’) * C’
przeniesienie
= A * B + A * C + B * C
= A * B + (A + B) *C
Schemat sumatora
suma
przeniesienie
A’
B’
C
A’
B
C’
A
B
C
A
B’
C’
A
B
A
C
B
C
Sumatory wielobitowe
• Dysponujemy więc układami logicznymi niezbędnymi do budowy
wielobitowego sumatora.
• Zauważmy, że ponieważ wartość wyjściowa każdego sumatora
zależy od przeniesienia z poprzedniego sumatora, istnieje
opóźnienie narastające od najmniej znaczącego do najbardziej
znaczącego bitu, ponieważ w każdym sumatorze jednobitowym
następują pewne opóźnienia bramkowe, które się kumulują.
• Gdyby wartości przeniesienia mogły być określone bez
przechodzenia przez wszystkie pośrednie szczeble, każdy
sumator jednobitowy mógłby działać niezależnie i opóźnienia by
się nie kumulowały.
• Można to osiągnąć, stosując rozwiązanie nazywane układem
przeniesienia na bardziej znaczące pozycje (
carry look-a-head
).
• Dla wyjaśnienia tego rozwiązania ponownie rozważmy sumator
4-bitowy.
Wzory na
carry look-a-
head
Chcemy więc otrzymać wyrażenia, które określają wartości na wejściu
Dowolnego szczebla sumatora, bez odnoszenia się do poprzednich
wartości przeniesienia:
(1)C
0
= A
0
* B
0
(2)C
1
= A
1
* B
1
+ (A
1
+ B
1
) * C
0
Podstawiając równości (1) do (2) otrzymamy:
(3)C
1
= A
1
* B
1
+ A
1
* A
0
* B
0
+ B
1
* A
0
* B
0
Powtarzając tę samą procedurę, otrzymujemy:
(4)C
2
= A
2
* B
2
+ A
2
* A
1
* B
1
+ A
2
* B
1
* A
0
* B
0
+ B
2
* A
1
* B
1
+ B
2
* A
1
* A
0
* B
0
+ B
2
* B
1
* A
0
* B
0
Postępowanie to możemy powtarzać dla dowolnie długich sumatorów.
Każdy składnik przeniesienia może być wyrażony w postaci sumy
iloczynów jako funkcja wyłącznie oryginalnych danych wejściowych,
bez zależności od przeniesień.
Układy sekwencyjne
• Układy kombinacyjne służą do wdrażania
podstawowych funkcji komputera. Jednak, poza
szczególnym przypadkiem pamięci ROM, nie
umożliwiają one zrealizowania układów pamięci lub
przechowywania informacji o stanie, które również
mają zasadnicze znaczenie dla działania komputera.
• Bieżący stan wyjścia układu sekwencyjnego zależy
nie tylko od bieżącego stanu wejścia, ale również od
historii stanu wejścia.
• Inaczej mówiąc, bieżący stan wyjścia układu
sekwencyjnego zależy od bieżącego stanu wejścia
oraz od bieżącego stanu samego układu
sekwencyjnego.
Przerzutniki
• Najprostszą formą układu sekwencyjnego jest
przerzutnik.
• Istnieje szereg rodzajów przerzutników, jednak wszystkie
mają następujące dwie własności:
– Przerzutnik jest układem dwustabilnym. Utrzymuje się w jednym
z dwóch stanów i bez sygnału wejściowego nie zmienia stanu.
Czyli przerzutnik działa jako pamięć jednobitowa.
– Przerzutnik ma dwa wyjścia, które zawsze dopełniają się
wzajemnie. Są one często oznaczane jako Q i Q’.
• W dalszym ciągu omówimy cztery rodzaje przerzutników:
– Przerzutnik zatrzaskowy S-R
– Synchronizowany przerzutnik S-R
– Przerzutnik D
– Przerzutnik J-K.
Przerzutnik zatrzaskowy
R
S
Q
Q’
S R Q
n+1
0 0 Q
n
0 1 0
1 0 1
1 1 ?
Odpowiedzi układu na serie wartości wejściowych
t 0 1 2 3 4 5 6 7 8 9
S 1 0 0 0 0 0 0 0 1 0
R 0 0 0 1 0 0 1 0 0 0
Q
n+1
1 1 1 0 0 0 0 0 1 1
Przebiegi czasowe
przerzutnika S-R
1
S
0
1
R
0
0
Q
1
0
Q’
1
2Δt
Δt
2Δt
Δt
t
Synchronizacja
przerzutnika S-R
• Zmiana stanu wyjścia przerzutnika S-R następuje po
krótkim opóźnieniu, jako reakcja na zmianę stanu
wejścia. Określimy to jako
działanie asynchroniczne
.
• Częściej jednak, zdarzenia w komputerze są
synchronizowane impulsami zegara, zmiany stanu mogą
nastąpić tylko wtedy gdy pojawi się impuls zegarowy.
• Przerzutnik S-R synchronizowany impulsami zegara
nazywamy
synchronicznym przerzutnikiem S-R
.
• W synchronicznym przerzutniku S-R, stany wejść S i R są
doprowadzane do bramek NOR przerzutnika tylko
podczas trwania impulsu zegarowego.
Synchronizowany
przerzutnik S-R
R
S
zegar
Q
Q’
Rozwiązywanie problemu
S-R
• W przypadku przerzutnika S-R problem jest to, że należy
zapobiegać powstawaniu sytuacji, w której równocześnie R =
1, S = 1.
• Jednym ze sposobów osiągnięcia tego jest pozostawienie tylko
jednego wejścia.
• Tak właśnie jest rozwiązany przerzutnik D, gdzie za pomocą
inwertora (funkcji negacji) zagwarantowano, że nie-zegarowe
wejścia do dwóch bramek AND dają stany, które są swoją
negacją.
• Stan na wyjściu przerzutnika D jest zawsze równy ostatniej
wartości stanu wejścia. Dlatego przerzutnik D jest często
określany jako linia opóźniająca, ponieważ pojawienie się na
wejściu 0 lub 1 – pojawia się na wyjściu z opóźnieniem jednego
cyklu zegara.
Przerzutnik D
zegar
D
Q
Q’
D Q
n+1
0 0
1 1
Inne rozwiązanie
problemu S-R
• Kolejnym użytecznym przerzutnikiem jest
przerzutnik J-K
.
• Podobnie jak przerzutnik S-R ma dwa wejścia. W odróżnieniu
jednak od przerzutnika S-R wszystkie możliwe kombinacje
stanów wejść przerzutnika J-K są dopuszczalne.
• Zauważmy, że pierwsze trzy kombinacje wartości wejść i
wyjść przerzutnika J-K są identyczne jak dla przerzutnika S-
R.
• Samo wejście J umożliwia realizację ustawienia na wejściu
wartości 1 (
set
), zaś samo wejście K realizuje kasowanie
(
reset
).
• Gdy oba wejścia (J i K) są równe 1, stan wyjścia ulega
zanegowaniu. Jeśli więc Q jest równe 1, to ustawienie
stanów wejść J = 1 i K = 1 powoduje zmianę stanu wyjścia Q
na 0. Jeśli zaś Q jest równe 0, to ustawienie stanów wejść J
= 1 i K = 1 powoduje zmianę stanu wyjścia Q na 1.
Przerzutnik J-K
K
zegar
J
Q
Q’
J K Q
n+1
0 0 Q
n
0 1 0
1 0 1
1 1 Q’
n
Symbole podstawowych
przerzutników
C
k
C
k
C
k
S Q
R Q’
J Q
K Q’
D Q
Q’
S R Q
n+1
0 0 Q
n
0 1 0
1 0 1
1 1
?
J K Q
n+1
0 0 Q
n
0 1 0
1 0 1
1 1 Q’
n
D Q
n+1
0 0
1 1
Rejestry
• Jako przykład zastosowania przerzutników,
przeanalizujemy jeden z zasadniczych
elementów procesora:
rejestr
.
• Jak wiemy, rejestr jest układem cyfrowym
używanym między innymi wewnątrz procesora
do przechowywania jednego lub wielu bitów
danych.
• Powszechnie używane są dwa rodzaje rejestrów:
– Rejestry równoległe
– Rejestry przesuwające.
Rejestr równoległy
S Q
R
S Q
R
S Q
R
S Q
R
S Q
R
S Q
R
S Q
R
S Q
R
D
o7
D
o6
D
o5
D
o4
D
o3
D
o2
D
o1
D
o0
D
i7
D
i6
D
i5
D
i4
D
i3
D
i2
D
i1
D
i0
Input
strobe
Reset
Output
strobe
Linie wejścia
Linie wyjściowe
5-bitowy rejestr
przesuwający
S
5
Y
5
C
R
5
Y’
5
S
4
Y
4
C
R
4
Y’
4
S
3
Y
3
C
R
3
Y’
3
S
2
Y
2
C
R
2
Y’
2
S
1
Y
1
C
R
1
Y’
1
zegar
X
Liczniki
• Inną użyteczną kategorią układów sekwencyjnych są
liczniki
.
• Licznik jest rejestrem, którego zawartość może być z łatwością
inkrementowana 1 modulo pojemność rejestru.
• Rejestr wykonany z n przerzutników może liczyć od 0 do 2
n
– 1.
• Gdy zawartość licznika jest zwiększana poza jego wartość
maksymalną, jest on ustawiony na 0.
• Przykładem licznika występującego w procesorze jest licznik
programu IC.
• Liczniki mogą być projektowane jako
asynchroniczne
lub
synchroniczne
.
• Liczniki asynchroniczne są stosunkowo powolne, ponieważ
przerzutnik wyzwala zmianę stanu następnego przerzutnika.
• W liczniku synchronicznym wszystkie przerzutniki zmieniają stan
jednocześnie i dlatego są o wiele szybsze od liczników
asynchronicznych. Dlatego też, są one powszechnie stosowane
w procesorach.
Licznik asynchroniczny
(szeregowy)
J Q
Ck
K Q’
J Q
Ck
K Q’
J Q
Ck
K Q’
J Q
Ck
K Q’
zegar
poziom
wysoki
Q
0
Q
1
Q
2
Q
3
zeg
ar
Q
0
Q
1
Q
2
Q
3
Licznik synchroniczny
J C
Ck
K C’
J B
Ck
K B’
J A
Ck
K A’
wysoki
zegar