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