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)
slawomir.sambor@pwr.wroc.pl
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. 0 71 320 30 78
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
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