Tablice Karnaugh dla funkcji 5 zmiennych

oś symetrii

Technika Cyfrowa 1 – Wykład 3

x x x

3 4 5

000

001

011

010

110

111

101

100

x x

1 2

00

dr inż. Sławomir Sambor

(0)

(1)

(3)

(2)

(6)

(7)

(5)

(4)

[e-mail]

01

a

(8)

(9)

(11)

(10)

(14)

(15)

(13)

(12)

ITA, budynek C-5 pokój 708,

11

e

x

d

c

(24)

(25)

(27)

(26)

(30)

(31)

(29)

(28)

Tel. [phone]

10

b

(16)

(17)

(19)

(18)

(22)

(23)

http://zstux.ita.pwr.wroc.pl/slawek/

(21)

(20)

Rozmiar 4 x 8, 25 = 32 elementy.

5 sąsiadów elementu x(11001):

a(01001)

b(10001)

c(11101)

d(11011)

e(11000)

Nowa zasada: elementy symetryczne są uważane za sąsiednie!

Analogicznie w tworzeniu grup: dwie grupy symetryczne względem siebie 1

uważane są za sąsiednie i mogą być sklejane.

Sklejanie w obrębie jednej polowy tabeli jak poprzednio: Tworzenie grup obejmujących obie polowy - wg zasady symetrii: x x x

x x x

3 4 5

3 4 5

000

001

011

010

110

111

101

100

000

001

011

010

110

111

101

100

x x

x x

1 2

1 2

00

00

01

01

11

11

10

10

1000* x /x /x /x

1

2

3

4

0*0*1 /x /x x

1

3 5

*01*1 /x x x

2 3 5

*11** x x

2

3

*1*0* x /x

x x x

*0*10

01*10 /x x x /x

2

4

11*11 x

/x x /x

1 2 4

5

2 4

5

1 2 4

5

Przykład:

Sklejanie zer

f(x , x , x , x , x )= Σ(0, 2, 4, 6, 8, 10, 12, 14, 25, 27, 29, 30, 31) - 13x5 = 65 liter 1

2

3

4

5

x x x

3 4 5

Sklejanie jedynek

000

001

011

010

110

111

101

100

x x

1 2

x x x

00

1

0

0

1

1

0

0

1

3 4 5

0***1

000

001

011

010

110

111

101

100

x +/x

x x

01

1

0

0

1

1

0

0

1

1

5

1 2

00

1

0

0

1

1

0

0

1

11

0

1

1

0

1

1

1

0

01

1

0

0

1

1

0

0

1

10

0

0

0

0

0

0

0

0

11

0

1

1

0

1

1

1

0

1*0*0 /x +x +x

10***

1

3

5

/x +x

1**00

+x +x

1

2

/x1

4

5

10

0

0

0

0

0

0

0

0

0***0 /x /x

*1110

1

5

x x x /x

2 3 4

5

11**l x x x

1 2 5

f=(/x +x +x )(/x +x +x )(/x +x )(x +/x ) - 10 liter 1

4

5

1

3

5

1

2

1

5

f=/x /x + x x x /x + x x x – 9 liter

1

5

2

3

4

5

1

2

5

Podstawy Techniki Cyfrowej i

Mikroprocesorowej

1

3 Minimalizacja funkcji niezupełnych Funkcja f(x , x , x , x , x ) przyjmuje wartość jeden dla {0, 1, 5, 7, 10, 11, 15, 16, 1

2

3

4

5

Jeśli dla pewnych wektorów WE funkcja nie jest określona, wpisujemy 26, 27, 30} oraz ma wartość nieokreśloną dla {2, 4, 9, 13, 20, 31}.

w odpowiadające im pola tabeli Karnaugh wyróżnione symbole (np. „−”) Podać minimalną postać sumacyjną.

i interpretujemy je jako 0 1ub 1 tak, jak jest to korzystne dla procesu sklejania.

Czyli wartości nieokreślone (symbole „−”) można sklejać jeśli sprzyja to powstawaniu dużych grup, ale nie trzeba się troszczyć o pokrycie ich wszystkich.

Przykład:

x x x

3 4 5

000

001

011

010

110

111

101

100

Na wejście układu kombinacyjnego podawane są tetrady kodu x x

1 2

BCD 0000, 0001, ... 1001; f(x , x , x , x ). Jego zadaniem jest wykrycie tetrad ≥ 6.

1

2

3

4

−

−

00

1

1

0

0

1

1

(0)

(1)

(3)

(2)

(6)

(7)

(5)

(4)

/x /x /x

x x

1

2

4

3 4

00

01

11

10

x x

−

1

1

0

1

−

0

1 2

01

0

(8)

(9)

(11)

(10)

(14)

(15)

(13)

(12)

00

0

0

0

0

1

−

11

0

0

1

1

0

0

(24)

(25)

(27)

(26)

(30)

(31)

(29)

(28)

01

0

0

1

1

*11* x x

0

0

0

0

0

0

−

2

3

10

1

11

−

−

−

−

(16)

(17)

(19)

(18)

(22)

(23)

(21)

(20)

1*** x

10

1

1

−

−

1

/x /x /x

2

4

5

x /x x

x x x

2

3 4

1 2 4

/x x x

1 3 5

Wynik : f=x +x x - 3 litery.

1

2 3

f = /x /x /x + x x x + x /x x + /x x x + /x /x /x Bez wykorzystania warto

2

4

5

1 2 4

2

3 4

1 3 5

1

2

4

ści dowolnych: 2 grupy dwuelementowe, 6 liter.

6. Wypisujemy zbiór wektorów nie podlegających dalszemu sklejaniu 4 Metoda Quine’a-McCluskey’a minimalizacji form boolowskich.

(nie oznaczonych znakiem ∨)

Przy minimalizacji podobnie jak przy tablicach Karnaugh wykorzystujemy 7. Tworzymy tzw. tabelę pokrycia w której wiersze stanowią wektory wypisane tożsamości:

w poprzednim punkcie, a kolumny numery wektorów dla których funkcja A x + A/ x = A - tzw. sklejanie jedynek ma wartość 1

(B + x)(B + / x) = B - tzw. sklejanie zer 8. Na przecięciu wiersza i kolumny zaznaczmy jedynki funkcji, które pokrywa Algorytm:

dany wektor

Sklejanie jedynek

9. Tworzymy minimalne wyrażenie boolowskie

1. Wypisujemy wszystkie wektory dla których funkcja ma wartość 1.

2. Porządkujemy wektory w grupy o tej samej liczbie jedynek w kolejności rosnącej 3. Porównujemy każdy wektor grupy z wektorem z grupy następnej.

Sklejanie zer

Jeżeli takie dwa wektory różnią się tylko jedną pozycją to sklejamy je i zapisujemy Algorytm sklejania zer jest taki sam jak sklejania jedynek z tym, że zgodnie w następnej kolumnie zastępując różniące się bity znakiem *.

z zasadą dualizmu jedynki funkcji zastępujemy zerami itd.

Sklejone wektory oznaczamy ∨

4. Powtarzamy procedurę 3 dla nowo powstałej kolumny tworząc następną (można sklejać tylko te wektory, które mają * na tej samej pozycji 5. Procedurę kończymy jeśli w nowo utworzonej kolumnie nie ma wektorów, które można sklejać. Jeśli w jakieś kolumnie występują dwa identyczne wektory to jeden z nich skreślamy

Przykład

f(x , x , x , x ) = Σ(0000, 0001, 0011, 0100, 0101, 1010, 1011, 1100, 1101, 1110, 1111) Tabela pokrycia

1

2

3

4

Sklejanie jedynek.

0

1

3

4

5

10

11

12

13

14

15

0, 1

0

0

0

*

∨

0

0 0 0 0

0

0 0 0 0 ∨

0, 4

0

*

0

0

∨

0, 1, 4, 5

0

*

0

*

1, 3

00*1

•

•

1

0 0 0 1

1

0 0 0 1 ∨

1, 3

0

0

*

1

0, 4, 1, 5

0

*

0

*

3, 11

*011

•

•

3

0 0 1 1

4

0 1 0 0 ∨

1, 5

0

*

0

1

∨

4, 5, 12, 13

*

1

0

*

0, 1, 4, 5

0*0*

•

•

•

•

4

0 1 0 0

3

0 0 1 1 ∨

4, 5

0

1

0

*

∨

4, 12, 5, 13

*

1

0

*

5

0 1 0 1

5

0 1 0 1 ∨

4, 5, 12, 13

*10*

4, 12

*

1

0

0

∨

10, 11, 14, 15

1

*

1

*

•

•

•

•

10

1 0 1 0

10

1 0 1 0 ∨

3, 11

*

0

1

1

10, 14, 11, 15

1

*

1

*

10, 11, 14, 15

1*1*

•

•

•

•

11

1 0 1 1

12

1 1 0 0 ∨

5, 13

*

1

0

1

∨

12, 13, 14, 15

1

1

*

*

12, 13, 14, 15

11**

•

•

•

•

12

1 1 0 0

11

1 0 1 1 ∨

10, 11

1

0

1

*

∨

13

1 1 0 1

13

1 1 0 1 ∨

12, 14, 13, 15

1

1

*

*

10, 14

1

*

1

0

∨

14

1 1 1 0

14

1 1 1 0 ∨

12, 13

1

1

0

*

∨

15

1 1 1 1

15

1 1 1 1 ∨

Wynik:

12, 14

1

1

*

0

∨

f = /x /x x + /x /x + x x + x x

1

2 4

1

3

1 2

1

3

11, 15

1

*

1

1

∨

13, 15

1

1

*

1

∨

14, 15

1

1

1

*

∨

Podstawy Techniki Cyfrowej i

Mikroprocesorowej

2

Sklejanie zer.

Metoda minimalizacji Quine’a-McCluskey’a dla funkcji niezupełnych.

f(x , x , x , x ) = Π(0010, 0110, 0111, 1000, 1001) 1

2

3

4

W przypadku funkcji niezupełnej wektory spoza dziedziny funkcji wykorzystujemy 2

0 0 1 0

2

0 0 1 0 ∨

2, 6

0 * 1 0

w procesie sklejania, ale nie uwzględniamy ich w tablicy pokrycia. Odrzucamy 6

0 1 1 0

8

1 0 0 0 ∨

8, 9

1 0 0 *

również wektory, które nie pokrywają żadnej jedynki (powstałe ze sklejenia 7

0 1 1 1

6

0 1 1 0 ∨

6, 7

0 1 1 *

samych wektorów spoza dziedziny funkcji)

8

1 0 0 0

9

1 0 0 1 ∨

9

1 0 0 1

7

0 1 1 1 ∨

Przykład:

Funkcja f(x , x , x , x , x ) przyjmuje wartość jeden dla {0, 1, 5, 7, 10, 11, 15, 16, 1

2

3

4

5

26, 27, 30} oraz ma wartość nieokreśloną dla {2, 4, 13, 20, 31}.

Wynik:

Podać minimalną postać sumacyjną.

f=( x + /x + x ) (/x + x + x ) (x +/x + /x ) 1

3

4

1

2

3

1

2

3

Funkcja minimalizowana wcześniej metodą tabel Karnaugh 0,1

0

0

0

0

*

0,1

0

0

0

0

*

∨

0

0 0 0 0 0

0

0 0 0 0 0

∨

0,1,4,5

0

0

*

0

*

0,2

0

0

0

*

0

0,2

0

0

0

*

0

0,4

0

0

*

0

0

∨

0,4,1,5

0

0

*

0

*

1

0 0 0 0 1

1

0 0 0 0 1

∨

0,4

0

0

*

0

0

0,16

*

0

0

0

0

0,16

*

0

0

0

0

∨

0,4,16,20

*

0

*

0

0

2

0 0 0 1 0

2

0 0 0 1 0

∨

1,5

0

0

*

0

1

1,5

0

0

*

0

1

∨

0,16,4,20

*

0

*

0

0

4

0 0 1 0 0

4

0 0 1 0 0

∨

2,10

0

*

0

1

0

2,10

0

*

0

1

0

5,7,13,15

0

*

1

*

1

4,5

0

0

1

0

*

4,5

0

0

1

0

*

∨

5

0 0 1 0 1

16

1 0 0 0 0

∨

5,13,7,15

0

*

1

*

1

4,20

*

0

1

0

0

4,20

*

0

1

0

0

∨

7

0 0 1 1 1

5

0 0 1 0 1

∨

10,11,26,27

*

1

0

1

*

16,20

1

0

*

0

0

16,20

1

0

*

0

0

∨

10

0 1 0 1 0

10

0 1 0 1 0

∨

5,7

0

0

1

*

1

5,7

0

0

1

*

1

∨

10,26,11,27

*

1

0

1

*

5,13

0

*

1

0

1

5,13

0

*

1

0

1

∨

11

0 1 0 1 1

20

1 0 1 0 0

∨

11,15,27,31

*

1

*

1

1

10,11

0

1

0

1

*

10,11

0

1

0

1

*

∨

13

0 1 1 0 1

7

0 0 1 1 1

∨

11,27,15,31

*

1

*

1

1

10,26

*

1

0

1

0

10,26

*

1

0

1

0

∨

15

0 1 1 1 1

11

0 1 0 1 1

∨

7,15

0

*

1

1

1

7,15

0

*

1

1

1

∨

26,27,30,31

1

1

*

1

*

16

1 0 0 0 0

13

0 1 1 0 1

∨

11,15

0

1

*

1

1

11,15

0

1

*

1

1

∨

26,30,27,31

1

1

*

1

*

11,27

*

1

0

1

1

∨

20

1 0 1 0 0

26

1 1 0 1 0

∨

11,27

*

1

0

1

1

13,15

0

1

1

*

1

13,15

0

1

1

*

1

∨

26

1 1 0 1 0

15

0 1 1 1 1

∨

26,27

1

1

0

1

*

26,27

1

1

0

1

*

∨

27

1 1 0 1 1

27

1 1 0 1 1

∨

26,30

1

1

*

1

0

26,30

1

1

*

1

0

∨

30

1 1 1 1 0

30

1 1 1 1 0

∨

15,31

*

1

1

1

1

15,31

*

1

1

1

1

∨

31

1 1 1 1 1

31

1 1 1 1 1

∨

27,31

1

1

*

1

1

27,31

1

1

*

1

1

∨

30,31

1

1

1

1

*

30,31

1

1

1

1

*

∨

Metoda Quine’a-McCluskey’a w zapisie dziesiętnym.

0

1

5

7

10

11

15

16

26

27

30

W przypadku funkcji dużej liczby zmiennych wypisywanie wielu kolumn

•

jest uciążliwe i łatwo powoduje błędy, dlatego bardziej wskazane jest 0, 2

000*0

•

posługiwanie się zapisem dziesiętnym.

2, 10

0*010

•

•

•

•

Ogólne zasady są jak poprzednio, a kolejność czynności jest następująca: 10,11,26,27

*101*

•

•

•

0,4,1,5

00*0*

1. Określamy liczbę jedynek dla danego wektora opisującego postać kanoniczną

•

•

0,4,16,20

*0*00

funkcji i wypisujemy kolumnę z podziałem na grupy o tej samej liczbie jedynek.

•

•

•

5,7,13,15

0*1*1

2. Druga kolumna powstaje z pierwszej w wyniku sklejenia, przy czym obowiązują

•

•

•

11,15,27,31

*1*11

następujące zasady:

•

•

•

26,27,30,31

11*1*

a) skleja się liczby należące do sąsiednich grup, b) sklejane liczby muszą się różnić o 2 k ( k = 0,1,2,...), c) liczby można sklejać tylko wówczas, gdy liczba z grupy o większej liczbie jedynek jest większa,

Wynik:

d) wynik sklejenia a z b zapisuje się w postaci a, b ( c) – przy czym c jest różnicą f = x /x x + /x /x /x +/x /x /x + /x x x + x x x 2

3 4

1

2

4

2

4

5

1 3 5

1 2 4

między a i b

Podstawy Techniki Cyfrowej i

Mikroprocesorowej

3

3 Następne kolumny powstają z poprzednich przy zachowaniu tych samych zasad; Przykład

dodatkowo różnice umieszczone w nawiasach sklejanych wyrażeń muszą f(x , x , x , x ) = Σ[0, 1, 2, 4, 5, 10, 12, (8, 14)]

1

2

3

4

być jednakowe, a wynik ma w nawiasie nie jedną lecz kilka różnic.

0,1 (1)

∨

0,1,4,5 (1,4)

4 Wyrażenia, których nie udało się skleić wpisuje się w tablicę pokrycia i ruguje 0

∨

0,2 (2)

∨

wyrażenia zbędne.

1

∨

0,4 (4)

∨

0,2,8,10 (2,8)

2

∨

4

∨

0,8 (8)

∨

5 Wyrażenia niezredukowane zmienia się na postać binarną, a następnie literową, 0,4,8,12 (4,8)

8

∨

zgodnie z zasadami:

1,5 (4)

∨

5

∨

a) wypisuje się w postaci binarnej pierwszą liczbę wchodząca w skład wyrażenia 2,10 (8)

∨

10

∨

8,10,12,14 (2,4)

b) na pozycjach, których waga równa jest podanym w nawiasie różnicom, 4,5 (1)

∨

pisze się * zamiast zera lub jedynki

12

∨

0

1

2

4

5

10

12

c) poszczególnym pozycją zero-jedynkowym przypisuje się odpowiednie litery 4,12 (8)

∨

14

∨

0,1,4,5 (1,4)

0*0*

•

•

•

•

8,10 (2)

∨

0,2,8,10 (2,8)

*0*0

•

•

•

8,12 (4)

∨

0,4,8,12 (4,8)

**00

•

•

•

10,14 (4)

∨

8,10,12,14 (2,4)

1**0

•

•

Wynik

12,14 (2)

∨

f = /x /x + /x /x + /x /x

lub

f = /x /x + /x /x + x /x

1

3

2

4

3

4

1

3

2

4

1

4

Podstawy Techniki Cyfrowej i

Mikroprocesorowej

4