NOTAKI Z TECHNIKI
NOTAKI Z TECHNIKI
CYFROWEJ
CYFROWEJ
Skrypt Studencki
Autor: Anna Wencka
NOTAKI Z TECHNIKI
NOTAKI Z TECHNIKI
CYFROWEJ
CYFROWEJ
Skrypt Studencki
Autor: Anna Wencka
WPROWADZENIE
1.
Pojęcia podstawowe:
•
Czym zajmuje się elektronika ?
•
Informacja
•
Sygnał
•
Uproszczona klasyfikacja układów
elektronicznych
Uproszczona klasyfikacja układów
elektronicznych
W z m a c n i a c z e
.
.
.
U k ła d y l i n io w e
M o d u l a to r y
P r o s to w n i k i
P o w i e l a c z e
...
U k ła d y n ie li n i o w e
U k ła d y a n a lo g o w e
U k l a d y k o m b i n a c y jn e
U k ła d y s y n c h r o n i c z n e
U k ła d y a s y n c h r o n ic z n e
U k ła d y s e k w e n c y j n e
U k ła d y c y fr o w e
U k ła d y e l e k tr o n i c z n e
POJĘCIE UKŁADU CYFROWEGO,
POJĘCIE UKŁADU LOGICZNEGO
UKŁAD
LOGICZNY
x
m
x
2
x
1
y
1
y
2
y
n
x
i
{0;1}
i=1,2,...,m
y
j
{0;1}
j=1,2,...,n
Programowalny układ logiczny
UKŁAD
LOGICZNY
x
m
x
2
x
1
y
1
y
2
y
n
s
k
s
2
s
1
SPOSOBY PRZEDSTAWIANIA
INFORMACJI W UKŁADACH
LOGICZNYCH
1. Kodowanie cyfrowe
2. Kody:
•
NKB
•
BCD (Binary Coded Decimal)
•
„1 z n”
•
Unitarny
•
Kod wskaźnika 7- elementowego
•
Gray’a
Kodowanie cyfrowe
INFORMACJ
A
CIĄGI
BINARNE
KODOWANIE
NKB – Naturalny kod binarny
0 1 2 3 4 5
6 7
0
0
0
0
0
0
0
1
1
1
1
1
1
1
2
4
8
000 001 010 011 100 101
110 111
NKB w zakresie od 0 do 15
0
0 0 0 0
1
0 0 0 1
2
0 0 1 0
3
0 0 1 1
4
0 1 0 0
5
0 1 0 1
6
0 1 1 0
7
0 1 1 1
8
1 0 0 0
9
1 0 0 1
10
1 0 1 0
11
1 0 1 1
12
1 1 0 0
13
1 1 0 1
14
1 1 1 0
15
1 1 1 1
8 4 2 1
BCD
(25)
10
= ( 1 1 0 0 1 )
NKB
16 8 4 2 1
(25)
10
= ( 0 0 1 0 0 1 0 1 )
BCD
(Każda
cyfra oddzielnie)
{
{
2
5
4 BITY BO CYFRY SĄ OD 0 DO 9
„ 1 z n ”
W praktyce używa się „ 1 z 10 ”
W praktyce używa się „ 1 z 10 ” (naturalny,
pierścieniowy lub pierwotny)
9 8 7 6 5 4 3 2 1 0
8
0
1
0 0 0 0 0 0 0 0
5
0 0 0 0
1
0 0 0 0 0
Unitarny
( 1 ) 1
( 2 ) 11
( 3 ) 111
( 4 ) 1111
Kod wskaźnika 7- elementowego
b
g
f
e
d
c
a
a b c d e f g
0 1 1 1 1 1 1 0
2 1 1 0 1 1 0 1
6 1 0 1 1 1 1 1
1 0 1 1 0 0 0 0
8 1 1 1 1 1 1 1
3 1 1 1 1 0 0 1
5 1 0 1 1 1 0 1
4 0 1 1 0 0 1 1
9 1 1 1 1 0 1 1
7 1 1 1 0 0 0 0
Kod Gray’a
2- bitowy
0 0
0 1
1 1
1 0
3- bitowy
0
000
1
001
2
011
3
010
4
110
5
111
6
101
7
100
1- bitowy n =
1 0
1
11
0
11
1
10
1
00
0
00
1
01
1
01
0
10
0
1
1
0
0
0
1
1
0
Kod Gray’a dla czterech zmiennych
0
0
0 0
0
0
0 1
0
0
1 1
0
0
1 0
0
1
1 0
0
1
1 1
0
1
0 1
0
1
0 0
1
1
0 0
1
1
0 1
1
1
1 1
1
1
1 0
1
0
1 0
1
0
1 1
1
0
0 1
1
0
0 0
1110
1111
1101
100
0
1001
1011
101
0
110
0
0110
011
1
010
1
000
0
000
1
001
1
001
0
010
0
Podstawy algebry Boole’a
1. Założenia algebry Boole’a
2. Definicja działań „+” i „*”
3. Aksjomaty
4. Twierdzenia
5. Ilustracja dowodu twierdzenia a + a * b = a
6. Ilustracja praw pochłaniania w algebrze
zbiorów
7. Funkcja boolowska
8. Tabela prawdy (logiczna)
9. Zapis numeryczny
10. Dekompresja
Shannona
11. Minimalizacja funkcji
boolowskich
Założenia algebry Boole’a
Binarną algebrę Boole’a tworzą:
Zbiór dwuelementowy {0;1}
Wyróżnione elementy tego zbioru – 0 i 1 (czyli oba są
wyróżnione )
Dwa działania (operacje, funktory) – suma logiczna (+)
oraz iloczyn logiczny (*) zdefiniowane dalej
Zestaw aksjomatów 1- 5, 1’- 5’
Wynikający z aksjomatów zestaw twierdzeń 1- 7, 1’- 7’, 8
Definicja działań „+” i „*” w algebrze Boole’a
a
b
a+b
a*b
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
a, b {0;1}
lub i
Aksjomaty według Huntingtona
Aksjomaty
Określenia
1. a + b {0,1}
1’. a * b
{0,1}
Wynik sumy
(iloczynu)
należy do
zbioru {0;1}
2. a + b = b + a
2’. a * b = b * a Przemienność
sumy
(iloczynu)
3. a * (b + c) = a
* b + a *c
3’. a + b * c =
(a + b) * (a +
c)
Rozdzielność
iloczynu
(sumy)
względem
sumy
(iloczynu)
4. a + 0 = a
4’. a * 1 = a
Istnieje
element
neutralny pod
względem
sumy
(iloczynu)
5. Istnieje taki
element a, że
a + a = 1
5’. Istnieje taki
element a, że
a * a = 0
Aksjomat ten
stanowi
właściwie
definicję
działania „-”
zwanego
negacją
Twierdzenia
Twierdzenia
Określenia
1. a + (b + c) = (a +
b) + c
1’. a * (b * c ) = (a *
b) * c
Prawo łączności sumy
(iloczynu)
2. a + a * b = a
2’. a * (a + b) = a
Prawo absorbcji
(pochłaniania)
3. a + a * b = a + b
3’. a * (a + b) = a * b
4. a + 1 = 1
4’. a * 0 = 0
Prawo dominacji elementu
max (min)
5. a + a = a
5’. a * a = a
Prawo idempotentności
6. a + b = a * b
6’. a * b = a + b
Prawa de Morgana !
7. 0 = 1
7’. 1 = 0
Prawo istnienia elementu
przeciwnego
8. a = a
Prawo podwójnej negacji
Ilustracja dowodu twierdzenia a + a * b = a
metodą zero – jedynkową tabelkową
a
b
Lewa
Prawa
a
a * b a + a *
b
a
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
1
1
1
1
1
1
1
1
L = P
a B
a a B = a
a
a B
a
a (a B) =
a
a B
a
a
a
a
B
B
Ilustracja praw pochłaniania w algebrze zbiorów
Przejścia
Rachunek
Zdań
Algebra
zbiorów
Algebra
Boole’a
v
+
*
~
‘
-
Fałsz
0
Prawda
1
Interpretacja fizyczna binarnej algebry Boole’a
zestyk
rozwierny
zestyk zwierny
+
negacja
afirmacja
+
suma
logiczna
iloczyn logiczny
+
+
Interpretacja fizyczna aksjomatów binarnej
algebry Boole’a
a
b
a
c
a
b
a
b
a
c
a
a
b
b
c
a
a
a
a
a
b
c
a
b
a
b
a
a
a
a
2.
2’
.
3.
3’
.
4.
4’
.
5.
5’
.
Funkcja boolowska i
sposoby jej określania
1. Definicja funkcji
2. Sposoby określania w analizie
matematycznej
3. Sposoby określania w teorii układów
logicznych
Definicja funkcji boolowskiej
Funkcją boolowską m zmiennych x
1
, x
2
,...,
x
m
, gdzie x
i
{0;1} nazywamy takie
odwzorowanie, które wariancjom zero-
jedynkowym zmiennych x
1
, x
2
,..., x
m
przyporządkuje wartość funkcji (oznaczaną
= y) równą 0, bądź 1, co można symbolicznie
zapisać następująco:
y = f (x
1
, x
2
,..., x
m
)
UKŁAD
LOGICZNY
x
m
x
2
x
1
y = f (x
1
, x
2
,...,
x
m
)
2
m
Sposoby określania w teorii układów
logicznych
1. Tabela prawdy
2. Formuła boolowska
3. Graf
4. Uproszczony zapis numeryczny
Tabela prawdy dla jednej funkcji
x
1
...
x
m
y
0
0
...
0
.
.
.
.
.
.
.
.
.
.
.
.
1
1
...
1
x
2
(m+1) kolumn
2
m
w
ie
rs
z
y
Tabela prawdy dla wielu funkcji
x
2
x
1
...
x
m
y
0
0
...
0
.
.
.
.
.
.
.
.
.
.
.
.
1
1
...
1
y
2
...
y
n
...
.
.
.
...
(m+n) kolumn
2
m
w
ie
rs
z
y
Formuła boolowska
Formuła boolowska jest to zapis ( wyrażenie )
utworzony ze zmiennych x
1
,x
2
, ... , x
m
oraz ich negacji
i stałych 0, 1 za pomocą działań „+” , „
*
” .
Dopuszcza się w formule użycie nawiasów tam gdzie
to niezbędne. Daną funkcję można przedstawić
różnymi formułami, ale dana formuła reprezentuje
sobą tylko jedna funkcję.
np.: a*( a + b ) ; a + a * b ; a * b + a * b to
formuły prezentujące tą samą funkcję.
Graf
( 0,0 )
( 0,1 )
( 1,0 )
( 1,1 )
0
1