4.3 Синтез комбінаційних схем

4.3.1 Представлення функції f4 в канонічній формі алгебри Буля

В даній алгебрі визначені функції {І, АБО, НЕ}. Нормальними канонічними формами є ДДНФ (Досконала диз’юктивна нормальна форма) та ДКНФ (Досконала кон’юктивна нормальна форма).

F_4ДДНФ= _{4 3 2}X₁ ˅ _{4 3}X_{2 1} ˅ _{4 3}X₂X₁ ˅ ₄X_{3 2}X₁ ˅ X_{4 3 2 1} ˅ X_{4 3 2}X₁ ˅ X_{4 3}X_{2 1} ˅ X₄X_{3 2 1} ˅ X₄X₃X_{2 1} ˅ X₄X₃X₂X₁

F_4ДКНФ=(X₄˅X₃˅X₂˅X₁)(X₄˅ ₃˅X₂˅X₁)(X₄˅ ₃˅ ₂˅X₁)(X₄˅ ₃˅ ₂˅ ₁) ( ₄˅X₃˅ ₂˅ ₁) ( ₄˅ ₃˅X₂ ˅ ₁)

2. Представлення функції f4 в канонічній формі алгебри Жегалкіна

В даній алгебрі визначені функції {І, виключне АБО, const 1}. Канонічною формою алгебри Жегалкіна є поліном Жегалкіна.

F4 = _{4 3 2}X₁ ⊕ _{4 3}X_{2 1} ⊕ _{4 3}X₂X₁ ⊕ ₄X_{3 2}X₁ ⊕ X_{4 3 2 1} ⊕ X_{4 3 2}X₁ ⊕ X_{4 3}X_{2 1} ⊕ X₄X_{3 2 1} ⊕ X₄X₃X_{2 1} ⊕ X₄X₃X₂X₁ = (X₄⊕1) (X₃⊕1)(X₂⊕1)X₁ ⊕ (X₄⊕1)(X₃⊕1)X₂(X₁⊕1) ⊕ (X₄⊕1)(X₃⊕1)X₂X₁ ⊕ (X₄⊕1)X₃(X₂⊕1)X₁ ⊕ X₄(X₃⊕1)(X₂⊕1)(X₁⊕1) ⊕ X₄(X₃⊕1)(X₂⊕1)X₁ ⊕ X₄(X₃⊕1)X₂(X₁⊕1) ⊕ X₄X₃(X₂⊕1)(X₁⊕1) ⊕ X₄X₃X₂(X₁⊕1) ⊕ X₄X₃X₂X₁ = X₄X₃X₂ ⊕ X₄X₃ ⊕ X₄X₂ ⊕ X₄ ⊕ X₃ ⊕ X₂ ⊕ 1 ⊕ X₄X₃X₂X₁ ⊕ X₃X₂X₁ ⊕ X₂X₁ ⊕ X₄X₂X₁ ⊕ X₄X₃X₂ ⊕ X₃X₂ ⊕ X₂ ⊕ X₄X₂ ⊕ X₄X₃X₂X₁ ⊕ X₄X₂X₁ ⊕ X₃X₂X₁ ⊕ X₂X₁ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₁ ⊕ X₃X₂X₁ ⊕ X₃X₁ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₂ ⊕ X₄X₃ ⊕ X₄X₃X₁ ⊕ X₄X₂X₁ ⊕ X₄X₂ ⊕ X₄X₁ ⊕ X₄ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₁ ⊕ X₄X₂X₁ ⊕ X₄X₁ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₂ ⊕ X₄X₂X₁ ⊕ X₄X₂ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₁ ⊕ X₄X₃X₂ ⊕ X₄X₃ ⊕ X₄X₃X₂X₁ ⊕ X₄X₃X₂ ⊕ X₄X₃X₂X₁ = X₃ ⊕ 1 ⊕ X₃X₂ ⊕ X₃X₂X₁ ⊕ X₃X₁ ⊕ X₄X₂X₁ ⊕ X₄X₃ ⊕ X₄X₃X₂X₁

2. Представлення функції f4 у канонічній формі алгебри Пірса

7

В даній алгебрі визначені функції {АБО-НЕ}. Канонічною формою алгебри Пірса є стрілка Пірса.

F₄=(X₄˅X₃˅X₂˅X₁)(X₄˅X₃˅X₂˅X₁)(X₄˅X₃˅X₂˅X₁)(X₄˅X₃˅X₂˅X₁)× ×(X₄˅X₃˅X₂˅X₁)(X₄˅X₃˅X₂˅X₁)=(X₄˅X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)˅ ˅(X₄˅X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)=

=(X₄↓X₃↓X₂↓X₁)↓(X₄↓(X₃↓X₃)↓X₂↓X₁)↓(X₄↓(X₃↓X₃)↓(X₂↓X₂)↓X₁)↓

↓(X₄↓(X₃↓X₃)↓(X₂↓X₂)↓(X₁↓X₁))↓((X₄↓X₄)↓X₃↓(X₂↓X₂)↓(X₁↓X₁))↓

↓((X₄↓X₄)↓(X₃↓X₃)↓X₂↓(X₁↓X₁))

4.3.6 Представлення функції f₄ в канонічній формі алгебри Шефера

В даній алгебрі визначені функції {І-НЕ}. Канонічною формою алгебри

є штрих Шефера.

F₄ = X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅

˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ = (X₄X₃X₂X₁)(X₄X₃X₂X₁) (X₄X₃X₂X₁)( X₄X₃X₂X₁)( X₄X₃X₂X₁)( X₄X₃X₂X₁)( X₄X₃X₂X₁)( X₄X₃X₂X₁)×

(X₄X₃X₂X₁)( X₄X₃X₂X₁) = ((X₄/X₄)/(X₃/X₃)/(X₂/X₂)/X₁)/((X₄/X₄)/(X₃/X₃)/X₂/

/(X₁))/((X₄/X₄)/(X₃/X₃)/X₂/X₁)/((X₄/X₄)/X₃/(X₂/X₂)/X­₁)/(X₄/(X₃/X₃)/(X₂/X₂)/

/(X₁/X₁)/(X₄/(X₃/X₃)/(X₂/X₂)/X₁)/(X₄/(X₃/X₃)/X₂/(X₁/X₁)/(X₄/X₃/(X₂/X₂)/(X₁/X₁))/

/(X₄/X₃/(X₂/X₂)/(X₁/X₁))/(X₄/X₃/X₂/X₁)

4.3.6 Мінімізація функції методом невизначених коефіцієнтів

Ідея цього методу полягає у відшуканні ненульових коефіцієнтів при кожній імпліканті. Рівняння для знаходження коефіцієнтів представимо таблицею (таблиця 4.3). Виконаємо викреслення тих рядків на яких функція приймає нульові значення. Викреслимо вже знайдені нульові коефіцієнти в тих рядках таблиці, що залишилися імпліканти, що залишилися після виконання попередніх дій поглинають ті імпліканти, що розташовані справа від них. Імпліканти називаються ядрами, якщо вони єдині в рядках.

8

x4	x3	x2	x1	x4x3	x4x2	x4x1	x3x2	x3x1	x2x1	x4x3x2	x4x3x1	x4x2x1	x3x2x1	x4x3x2x1	f4
0	0	0	0	00	00	00	00	00	00	000	000	000	000	0000	0
0	0	0	1	00	00	01	00	01	01	000	001	001	001	0001	1
0	0	1	0	00	01	00	01	00	10	001	000	010	010	0010	1
0	0	1	1	00	01	01	01	01	11	001	001	011	011	0011	1
0	1	0	0	01	00	00	10	10	00	010	010	000	100	0100	0
0	1	0	1	01	00	01	10	11	01	010	011	001	101	0101	1
0	1	1	0	01	01	00	11	10	10	011	010	010	110	0110	0
0	1	1	1	01	01	01	11	11	11	011	011	011	111	0111	0
1	0	0	0	10	10	10	00	00	00	100	100	100	000	1000	1
1	0	0	1	10	10	11	00	01	01	100	101	101	001	1001	1
1	0	1	0	10	11	10	01	00	10	101	100	110	010	1010	1
1	0	1	1	10	11	11	01	01	11	101	101	111	011	1011	0
1	1	0	0	11	10	10	10	10	00	110	110	100	100	1100	1
1	1	0	1	11	10	11	10	11	01	110	111	101	101	1101	0
1	1	1	0	11	11	10	11	10	10	111	110	110	110	1110	1
1	1	1	1	11	11	11	11	11	11	111	111	111	111	1111	1

Таблиця коефіцієнтів

МДНФ = X₄X₁˅X₄X₃X₂˅X₄X₃X₁˅X₄X₂X₁˅X₃X₂X₁

4.3.7 Мінімізація функції f₄ методом Квайна-Мак-Класкі

(рисунок 4.6).

Випишемо конституенти одиниці і зробимо всі можливі склеювання і поглинання

Побудуємо таблицю покриття (таблиця 4.4).

Таблиця 4.4

Таблиця покриття

	0001	0010	0011	0101	1000	1001	1010	1100	1110	1111
00X1	˅		˅
0X01	˅			˅
X001	˅					˅
X010		˅					˅
100X					˅	˅
111X									˅	˅
1XX0					˅		˅	˅	˅

F_{4 МДНФ} = X₄X₃X₁˅X₄X₂X₁˅X₃X₂X₁˅X₄X₃X₂˅X₄X₃X₂˅X₄X₁

4.3.8. Мінімізація функції f₄ методом діаграм Вейча

Виконаємо мінімізацію функції методом Вейча (рисунок 4.7). Цей метод дуже зручний при мінімізації функції з кількістю аргументів до чотирьох включно. Кожна клітинка відповідає конституенті, а прямокутник з кількох клітинок – імпліканті.

	X3
X4	1	0	1	1
	1	1	0	1	X2
	0	0	1	1
	0	1	1	0
		X1

Рисунок 4.7 Мінімізація функції методом Вейча

F_{4 МДНФ} = X₄X₁ ˅ X₄X₃X₂ ˅X₄X₃X₂ ˅ X₄X₃X₂ ˅ X₄X₂X₁

4.3.9 Спільна мінімізація функцій f_1, f_2, f₃

Виконаємо мінімізацію прямих значень функцій. Виходячи з таблиці істинності системи перемикальних функцій записуємо комплекс кубів К⁰. Виконуємо всі попарні склеювання та отримуємо комплекси кубів К¹ і К². Шляхом поглинання термів отримуємо Z-покриття, що відповідає СДНФ і системі перемикальних функцій (рисунок 4.8).

К0	К1	К2
0000 (1, 2, 3)	X000 (1,2,3)	0XX0 (1,3)
0001 (1, 2)	X110 (1)	X11X (1)
0100 (1, 3)	X111 (1,2,3)
0110 (1, 2, 3)	X100 (1,3)
0111 (1, 2, 3)	0X10 (1,2,3)
1000 (1, 2, 3)	1X11 (1)
1001 (3)	1X00 (1,2,3)
1011 (1)	0X00 (1,3)
1100 (1, 2, 3)	00X0 (1,2,3)
1101 (2)	01X0 (1,3)
1110 (1)	11X0 (1)
1111 (1, 2, 3)	11X1 (2)
	000X (1,2)
	011X (1,2,3)
	100X (3)
	110X (2)
	111X (1)

Рисунок 4.8 Поглинання термів для мінімізації прямих значень функцій

Для видалення надлишкових імплікант будуємо таблицю покриття (таблиця 4.5).

Таблиця 4.5

F1

F2

F3

0000

0001

0010

0110

1000

1011

1100

1110

1111

0000

0001

0010

1000

1101

1111

0000

0010

0100

0111

1000

1001

1100

1111

000X (1,2)

˅

˅

˅

˅

011X (1,2,3)

˅

˅

100X (3)

˅

˅

110X (2)

˅

˅

0X10 (1,2,3)

˅

˅

˅

˅

1X11 (1)

˅

˅

00X0 (1,2,3)

˅

˅

˅

˅

˅

˅

11X0 (1)

˅

˅

˅

X000 (1,2,3)

˅

˅

˅

˅

˅

˅

X111 (1,2,3)

˅

˅

˅

˅

11X1 (2)

˅

˅

X100 (1,3)

˅

˅

˅

1X00 (1,2,3)

˅

˅

˅

˅

0XX0 (1,3)

˅

˅

˅

˅

˅

˅

˅

X11X (1)

˅

˅

˅

Таблиця покриття системи перемикальних функцій

На підставі таблиці покриття одержуємо МДНФ перемикальних функцій:

F1 = X₄X₃X₂ ˅ X₄X₂X₁ ˅ X₄X₂X₁ ˅ X₄X₃X₁ ˅ X₃X₂X₁

F2 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₁

F3 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁

Аналогічно виконаємо мінімізацію заперечень функцій.

К0	К1	К2
0001 (3)	00X1 (3)	01XX (2)
0011 (1,2,3)	0X01 (3)
0100 (1,2)	0X11 (1,2)
0101 (1,2,3)	X011 (2,3)
0110 (2,3)	010X (1,2)
0111 (1,2)	X100 (2)
1001 (1,2)	X101 (1,3)
1010 (1,2,3)	011X (2)
1011 (2,3)	10X1 (2)
1100 (2)	1X01 (1)
1101 (1,3)	101X (2,3)
1110 (2,3)	1X10 (2,3)
	X110 (2,3)

Рисунок 4.9 Поглинання термів для мінімізації заперечень

Будуємо таблицю покриття (таблиця 4.6).

Таблиця 4.6

Таблиця покриття системи заперечень перемикальних функцій

Не F1

Не F2

Не F3

0011

0101

1001

1010

1101

0011

0100

0101

1001

1010

1011

1110

0001

0011

0101

1010

1011

1101

1110

0011 (1,2,3)

˅

˅

˅

0101 (1,2,3)

˅

˅

˅

00X1 (3)

˅

˅

0X01 (3)

˅

˅

0X11 (1,2)

˅

˅

X011 (2,3)

˅

˅

˅

˅

˅

X100 (2)

˅

X101 (1,3)

˅

˅

˅

˅

10X1 (2)

˅

˅

1X01 (1)

˅

˅

101X (2,3)

˅

˅

˅

˅

1X10 (2,3)

˅

˅

˅

˅

1010 (1,2,3)

˅

˅

˅

1001 (1,2)

˅

˅

X110 (2,3)

˅

˅

На підставі таблиці покриття системи заперечень перемикальних функцій одержуємо МДНФ заперечень перемикальних функцій:

F1 = X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₂X₁ ˅ X₄X₃X₂X₁

F2 = X₄X₃X₂X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁ ˅X₄X₃X₁ ˅ X₄X₂X₁

F3 = X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₂ ˅ X₄X₂X₁

Виведемо вісім нормальних форм:

F1 = X₄X₃X₂ ˅ X₄X₂X₁ ˅ X₄X₂X₁ ˅ X₃X₂X₁

F2 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₁ І/АБО

F3 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁

F1 = X₄X₃X₂ • X₄X₂X₁ • X₄X₂X₁ • X₃X₂X₁

F2 = X₄X₃X₂ • X₄X₃X₁ • X₃X₂X₁ • X₄X₃X₁ І-НЕ/І-НЕ

F3 = X₄X₃X₂ • X₄X₃X₁ • X₃X₂X₁ • X₃X₂X₁

F1 = (X₄˅X₃˅X₂) • (X₄˅X₂˅X₁) • (X₄˅X₂˅X₁) • (X₃˅X₂˅X₁)

F2 = (X₄˅X₃˅X₂) • X₄˅X₃˅X₁) • (X₃˅X₂˅X₁) • (X₄˅X₃˅X₁) АБО/І-НЕ

F3 = (X₄˅X₃˅X₂) • (X­₄˅X₃˅X₁) • (X₃˅X₂˅X₁)˅(X₃˅X₂˅X₁)

F1 = (X₄˅X₃˅X₂) ˅ (X₄˅X₂˅X₁) ˅ (X₄˅X₂˅X₁) ˅ (X₃˅X₂˅X₁)

F2 = (X₄˅X₃˅X₂) ˅ (X₄˅X₃˅X₁) ˅ (X₃˅X₂˅X₁) ˅ (X₄˅X₃˅X₁) АБО-НЕ/АБО

F3 = (X₄˅X₃˅X₂) ˅ (X₄˅X₃˅X₁) ˅ (X₃˅X₂˅X₁) ˅ (X₃˅X₂˅X₁)

F1 = X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₂X₁ ˅ X₄X₃X₂X₁

F2 = X₄X₃X₂X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁ ˅X₄X₃X₁ ˅ X₄X₂X₁ І/АБО- НЕ

F3 = X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₂ ˅ X₄X₂X₁

F1 = X₄X₃X₂X₁ • X₄X₃X₂X₁ • X₄X₂X₁ • X₄X₃X₂X₁

F2 = X₄X₃X₂X₁ • X₃X₂X₁ • X₃X₂X₁ • X₄X₃X₁ • X₄X₂X₁ І-НЕ/І

F3 = X₄X₃X₁ • X₃X₂X₁ • X₄X₃X₂ • X₄X₂X₁

F1 = (X₄˅X₃˅X₂˅X₁) • (X₄˅X₃˅X₂˅X₁) • (X₄˅X₂˅X₁) • (X₄˅X₃˅X₂˅X₁)

F2 = (X₄˅X₃˅X₂˅X₁)•(X₃˅X₂˅X₁)•(X₃˅X₂˅X₁)•(X₄˅X₃˅X₁)•(X₄˅X₂˅X₁)

F3 = (X₄˅X₃˅X₁) • (X₃˅X₂˅X₁) • (X₄˅X₃˅X₂) • (X₄˅X₂˅X₁) АБО/І

F1 = (X₄˅X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)˅(X₄˅X₂˅X₁)˅(X₄˅X₃˅X₂˅X₁)

F2 = (X₄˅X₃˅X₂˅X₁)˅(X₃˅X₂˅X₁)˅(X₃˅X₂˅X₁)˅(X₄˅X₃˅X₁)˅(X₄˅X₂˅X₁)

F3 = (X₄˅X₃˅X₁)˅(X₃˅X₂˅X₁)˅(X₄˅X₃˅X₂)˅(X₄˅X₂˅X₁) АБО-НЕ/АБО-НЕ

3.10 Одержання операторних форм для реалізації на ПЛМ

Одержимо операторне представлення функцій на ПЛМ. На ПЛМ можна реалізувати форми {І/АБО, І/АБО-НЕ}.

F1 = X₄X₃X₂ ˅ X₄X₂X₁ ˅ X₄X₂X₁ ˅ X₃X₂X₁

F2 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₁ І/АБО

F3 = X₄X₃X₂ ˅ X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁

F1 = X₄X₃X₂X₁ ˅ X₄X₃X₂X₁ ˅ X₄X₂X₁ ˅ X₄X₃X₂X₁

F2 = X₄X₃X₂X₁ ˅ X₃X₂X₁ ˅ X₃X₂X₁ ˅X₄X₃X₁ ˅ X₄X₂X₁ І/АБО- НЕ

F3 = X₄X₃X₁ ˅ X₃X₂X₁ ˅ X₄X₃X₂ ˅ X₄X₂X₁

І/АБО : Всього 4 змінні, 9 імплікант, 3 функції. Тож оберемо ПЛМ (4,9,3).

І/АБО-НЕ : Всього 4 змінні, 11 імплікант, 3 функції. Тож оберемо ПЛМ (4,9,3).

Побудуємо мнемонічну схему ПЛМ(І/АБО) (рисунок 4.10).

Рисунок 4.10 мнемонічна схема ПЛМ(І/АБО)

Побудуємо мнемонічну схему ПЛМ(І/АБО-НЕ) (рисунок 4.11).

Рисунок 4.11 мнемонічна схема ПЛМ(І/АБО-НЕ)

За даними мнемонічних схем побудуємо карти програмування ПЛМ(I/АБО) (рисунок 4.12) та карту програмування ПЛМ(I/АБО-НЕ) (рисунок 4.13).

X4	X3	X2	X1	Pi	F1	F2	F3
0	0	0	-	P1	1	1	0
0	-	1	0	P2	1	0	0
1	-	1	0	P3	1	0	0
-	0	0	0	P4	1	1	0
0	0	-	0	P5	0	1	1
1	1	-	1	P6	0	1	0
1	0	0	-	P7	0	0	1
-	1	1	1	P8	0	0	1
-	1	0	0	P9	0	0	1

X4	X3	X2	X1	Pi	F1	F2	F3
1	1	0	0	P1	1	1	0
1	0	1	0	P2	1	0	0
0	-	1	0	P3	1	0	0
0	1	0	1	P4	1	0	0
-	0	1	1	P5	0	1	0
-	1	0	0	P6	0	1	0
0	1	-	0	P7	0	1	0
0	-	0	1	P8	0	1	1
1	1	-	0	P9	0	0	1
-	0	1	0	P10	0	0	1
0	1	0	-	P11	0	0	1

Рисунок 4.12 Карта програмування

ПЛМ (I/АБО)

Рисунок 4.13 Карта програмування ПЛМ (I/АБО-НЕ)

Отже, кращою матрицею є матриця реалізована в елементному базисі І/АБО, адже має меншу кількість вхідних сигналів.