2 Синтез логических схем

Синтез логических схем осуществляется на основе заданной функции алгебры логики. Функция, определенная на наборах <x_n-1, …, x_i, …, x₂, x₁, x₀> и принимающая на этих наборах значение 0 или 1, называется функцией алгебры логики.

2.1 Таблица истинности функции алгебры логики

- (1)

								1	2		3	4	f
	x4	x3	x2	x1	x0								(4)->(3)
0	0	0	0	0	0	1	1	0	0	1		1	1
1	0	0	0	0	1	1	1	0	1	0		1	0
2	0	0	0	1	0	0	1	0	0	1		0	1
3	0	0	0	1	1	0	1	0	1	0		0	1
4	0	0	1	0	0	1	0	0	0	1		1	1
5	0	0	1	0	1	1	0	0	1	0		1	0
6	0	0	1	1	0	0	0	0	0	1		0	1
7	0	0	1	1	1	0	0	0	1	0		0	1
8	0	1	0	0	0	1	1	1	1	0		1	0
9	0	1	0	0	1	1	1	1	1	0		1	0
10	0	1	0	1	0	0	1	1	1	0		0	1
11	0	1	0	1	1	0	1	1	1	0		0	1
12	0	1	1	0	0	1	0	0	0	1		1	1
13	0	1	1	0	1	1	0	0	1	0		1	0
14	0	1	1	1	0	0	0	0	0	1		0	1
15	0	1	1	1	1	0	0	0	1	0		0	1
16	1	0	0	0	0	1	1	0	0	1		1	1
17	1	0	0	0	1	1	1	0	1	0		1	0
18	1	0	0	1	0	0	1	0	0	1		1	1
19	1	0	0	1	1	0	1	0	1	0		1	0
20	1	0	1	0	0	1	0	0	0	1		1	1
21	1	0	1	0	1	1	0	0	1	0		1	0
22	1	0	1	1	0	0	0	0	0	1		1	1
23	1	0	1	1	1	0	0	0	1	0		1	0
24	1	1	0	0	0	1	1	1	1	0		1	0
25	1	1	0	0	1	1	1	1	1	0		1	0
26	1	1	0	1	0	0	1	1	1	0		1	0
27	1	1	0	1	1	0	1	1	1	0		1	0
28	1	1	1	0	0	1	0	0	0	1		1	1
29	1	1	1	0	1	1	0	0	1	0		1	0
30	1	1	1	1	0	0	0	0	0	1		1	1
31	1	1	1	1	1	0	0	0	1	0		1	0

2.2 Совершенные дизъюнктивная и конъюнктивная нормальные формы

СДНФ:

Сложность формулы (Y)=5*18=90

СКНФ:

Сложность формулы (Y)=5*14=60

3. Анализ функции алгебры логики на принадлежность к классам

Так как f(0, 0, 0, 0, 0) = 1, то данная функция алгебры логики не принадлежит к классу функций сохраняющих ноль, т.е. fK₀

Так как f(1, 1, 1, 1, 1)=0, то данная функция алгебры логики принадлежит к классу функций сохраняющих единицу, т.е. fK₁

Анализ функции алгебры логики на принадлежность к классу линейных функций:

f_л=CC₀x₀C₁x₁C₂x₂C₃x₃C₄x₄

Коэффициент С находим на наборе <0,0,0,0,0>

f(00000)= C00000=C=1, тогда C=1

Коэффициент С₄ находим на наборе <0,0,0,0,1>

f(00001)= 10 000C₄*1=1, тогда C₄=0

Коэффициент С₃ находим на наборе <0,0,0,1,0>

f(00010)= 1000C₃*10=0, тогда C₃=1

Коэффициент С₂ находим на наборе <0,0,1,0,0>

f(00100)= 100C₂*100=1, тогда C₂=0

Коэффициент С₁ находим на наборе <0,1,0,0,0>

f(01000)= 10C₁*1000=1, тогда C₁=0

Коэффициент С₀ находим на наборе <1,0,0,0,0>

f(10000)= 1C₀*10000=0, тогда C₀=1

f_л=1

Идет несовпадение, значит функция не линейная, т.е. fK_л.

Анализ функции алгебры логики на принадлежность к K_с. Выразим обратную функцию (1) и составим таблицу истинности для обратной функции и сравним с исходной :

	x4	x3	x2	x1	x0
0	0	0	0	0	0	1
1	0	0	0	0	1	0
2	0	0	0	1	0	1
3	0	0	0	1	1	0
4	0	0	1	0	0	1
5	0	0	1	0	1	1
6	0	0	1	1	0	1
7	0	0	1	1	1	1
8	0	1	0	0	0	1
9	0	1	0	0	1	0
10	0	1	0	1	0	1
11	0	1	0	1	1	0
12	0	1	1	0	0	1
13	0	1	1	0	1	0
14	0	1	1	1	0	1
15	0	1	1	1	1	0
16	1	0	0	0	0	0
17	1	0	0	0	1	0
18	1	0	0	1	0	1
19	1	0	0	1	1	0
20	1	0	1	0	0	0
21	1	0	1	0	1	0
22	1	0	1	1	0	1
23	1	0	1	1	1	1
24	1	1	0	0	0	0
25	1	1	0	0	1	0
26	1	1	0	1	0	1
27	1	1	0	1	1	0
28	1	1	1	0	0	0
29	1	1	1	0	1	0
30	1	1	1	1	0	1
31	1	1	1	1	1	0

Анализируем полученную таблицу и приходим к выводу что функция не принадлежит к классу f K_с.

Проверим принадлежность функции алгебры логики к классу монотонных функций f_м:

I \ j	00000	00001	00010	00011	00100	00101	00110	00111	01000
00000	*	+	+	+	+	+	+	+	-
00001	*	*
00010	*	*	*
00011	*	*	*	*
00100	*	*	*	*	*
00101	*	*	*	*	*	*
00110	*	*	*	*	*	*	*
00111	*	*	*	*	*	*	*	*
01000	*	*	*	*	*	*	*	*	*

Если в полученной матрице есть хотя бы один знак “-“, то функция не является монотонной, т.е. f K_м

2.4 Минимизация функции алгебры логики

Для минимизации несложных функций применяются алгебраические преобразования на основе законов поглощения и склеивания. Для более сложных функций разработаны специальные методы минимизации такие как: Гарвардский метод, метод минимизирующих карт, метод Квайна - Мак–Класски.

2.5 Минимизация с помощью карт Карно

	х0				х0
	х4		х4		х4		х4
х3	11001 25 0	11101 29 0	01101 13 0	01001 9 0	11000 24 0	11100 28 1	01100 12 1	01000 8 0	х1
	11011 27 0	11111 31 1	01111 15 1	01011 11 1	11010 26 0	11110 30 1	01110 14 1	01010 10 1	х1
х3	10011 19 0	10111 23 0	00111 7 1	00011 3 1	10010 18 1	10110 22 1	00110 6 1	00010 2 1

Продолжение карты Карно

	10001 17 0	10101 21 0	00101 5 0	00001 1 0	10000 16 1	10100 20 1	00100 4 1	00000 0 1	х1
	х2	х2		х2	х2	х2		х2

Записываем МДНФ в виде логической суммы конъюнкций, соответствующих выполненным накрытиям:

2.6 Минимизация методом Квайна - Мак-Класски

Этот метод использует перебор конъюнкций, которые могут присутствовать в ДНФ, эквивалентной минимизируемой функции. Исходная ФАЛ задается в виде двоичных наборов, соответствующих конъюнкциям ранга n, разбитых на подгруппы по числу единиц в наборе.

00000, 00010, 00011, 00100, 00111, 00110, 01010, 01011, 01100, 01110, 01111,

10000, 10010, 10100, 10110, 11100, 11110,11111

Таблица 2.0.1

0 группа	1 группа	2 группа	3 группа	4 группа	5 группа
00000	00010	00011	00111	01111	11111
	00100	00110	01011	11110
	10000	01010	01110
		01100	10110
		10010	11100
		10100

Выполняем склеивание, поскольку все наборы принимают участие в склеивании, то первичных импликант нет.

В результате получаем наборы 4-ого ранга, которые также разбиваем на группы:

Таблица 2.0.2

0 группа

1 группа

2 группа

3 группа

4 группа

Продолжение таблицы 2.0.2

000-0	0001-	00-11	0-111	-1111
00-00	00-10	0-011	01-11	1111-
-0000	0-010	0011-	-1110
	-0010	0-110	1-110
	001-0	-0110	111-0
	0-100	0101-	0111-
	-0100	01-10
	100-0	011-0
	10-00	-1100
		10-10
		101-0
		1-100

Выполняем склеивание, поскольку все наборы принимают участие в склеивании, то первичных импликант нет. Переходим к наборам 3-его ранга:

Таблица 2.0.3

0 группа	1 группа	2 группа	3 группа
00--0	00-1-	0--11	-111-
-00-0	0-01-	0-11-
-0-00	0--10	--110
	-0-10	01-1-
	0-1-0	-11-0
	-01-0	1-1-0
	--100
	10--0

Выполняем склеивание, поскольку все наборы принимают участие в склеивании, то первичных импликант нет. Переходим к наборам 2-его ранга:

Таблица 2.0.4

0 группа	1 группа	2 группа
-0--0	0--1-

Продолжение таблицы 2.0.4

--1-0

Наборы 2-ого ранга и не склеенные наборы 3-его ранга отнесем к первичным импликантам и внесем их в импликантную таблицу (таблица 2.0.5):

Таблица 2.0.5

	00000	00010	00011	00100	00111	00110	01010	01011	01100	01110	01111	10000	10010	10100	10110	11100	11110	11111
-111-										√	√						√	√
-0--0	√	√		√	√							√	√	√	√
0--1-		√	√		√	√	√	√		√	√
--1-0				√	√				√	√				√	√	√	√

Заполняем таблицу метками. Вычеркиваем столбцы, имеющие только одну метку, и строки, дающие эти метки. Все четыре строки вычеркнуты, значит, первичные импликанты -111-, -0--0, 0--1-, --1-0 обязательно войдут в МДНФ.

Столбцы, имеющие хотя бы одну вычеркнутую метку, также вычеркиваем: таким образом у нас все столбцы вычеркнуты.

В окончательном виде МДНФ имеет вид:

₍₁₎

Синтез схемы методом каскадов.

Синтез логической схемы в базисе И, ИЛИ, НЕ.

Преобразуем полученную МДНФ таким образом , чтобы составить логическую схему в базисе И, ИЛИ, НЕ:

₍₂₎

Метод каскадов основан на исключении переменных и получении остаточных функций. Этот метод базируется на понятии производной от функции алгебры логики.

Определяем производные функции алгебры логики по каждой из переменных:

По переменной х₄

По переменной х₃

По переменной х₂

По переменной х₁

По переменной х₀

Теперь определим вес Р каждой из производных и данные занесем в таблицы (таблицы 2-2.4):

Таблица 2 – Значения производной f по х₄

х3	х2	х1	х0	(1)	(2)	(1)(2)
0	0	0	0	1	1	0
0	0	0	1	0	0	0
0	0	1	0	1	1	0
0	0	1	1	0	1	1
0	1	0	0	1	1	0
0	1	0	1	0	0	0
0	1	1	0	1	1	0
0	1	1	1	0	1	1
1	0	0	0	0	0	0
1	0	0	1	0	0	0
1	0	1	0	0	1	1
1	0	1	1	0	1	1
1	1	0	0	1	1	0
1	1	0	1	0	0	0
1	1	1	0	1	1	0
1	1	1	1	1	1	0

Р₄=4

Таблица 2.1 – Значения производной f по х₃

х4

х2

х1

х0

(1)

(2)

(1)(2)

Продолжение таблицы 2.1

0	0	0	0	0	1	1
0	0	0	1	0	0	0
0	0	1	0	1	1	0
0	0	1	1	1	0	1
0	1	0	0	1	1	0
0	1	0	1	0	0	0
0	1	1	0	1	1	0
0	1	1	1	1	0	1
1	0	0	0	0	1	1
1	0	0	1	0	0	0
1	0	1	0	0	1	1
1	0	1	1	0	0	0
1	1	0	0	1	1	0
1	1	0	1	0	0	0
1	1	1	0	1	1	0
1	1	1	1	1	0	1

Р₃=6

Таблица 2.2 – Значения производной f по х₂

х4	х3	х1	х0	(1)	(2)	(1)(2)
0	0	0	0	1	1	0
0	0	0	1	0	0	0
0	0	1	0	1	1	0
0	0	1	1	1	1	0
0	1	0	0	1	0	1
0	1	0	1	0	0	0
0	1	1	0	1	1	0
0	1	1	1	1	1	0
1	0	0	0	1	1	0
1	0	0	1	0	0	0
1	0	1	0	1	1	0
1	0	1	1	0	0	0
1	1	0	0	1	0	1
1	1	0	1	0	0	0
1	1	1	0	1	0	1
1	1	1	1	1	0	1

Р₂=4

Таблица 2.3 – Значения производной f по х₁

х4		х3	x2	х0	(1)	(2)	(1)(2)
0		0	0	0	1	1	0
0		0	0	1	1	0	1
0	0		1	0	1	1	0
0	0		1	1	1	0	1
0	1		0	0	1	0	1
0	1		0	1	1	0	1

Продолжение таблицы 2.3

0	1	1	0	1	1	0
0	1	1	1	1	0	1
1	0	0	0	1	1	0
1	0	0	1	0	0	0
1	0	1	0	1	1	0
1	0	1	1	0	0	0
1	1	0	0	0	0	0
1	1	0	1	0	0	0
1	1	1	0	1	1	0
1	1	1	1	1	0	1

Р₁=6

Таблица 2.4 – Значения производной f по х₀

х4	х3	х2	х1	(1)	(2)	(1)(2)
0	0	0	0	0	1	1
0	0	0	1	1	1	0
0	0	1	0	0	1	1
0	0	1	1	1	1	0
0	1	0	0	0	0	0
0	1	0	1	1	1	0
0	1	1	0	1	1	1
0	1	1	1	0	1	0
1	0	0	0	0	1	1
1	0	0	1	0	1	1
1	0	1	0	0	1	1
1	0	1	1	0	1	1
1	1	0	0	0	0	0
1	1	0	1	0	0	0
1	1	1	0	0	0	0
1	1	1	1	1	1	0

Р₀=7

Так как максимальный вес имеет производная по переменной х₀, то из f исключаем х₀.

После исключения можно записать нулевую и единичную остаточные функции:

Определим, какую из переменных следует исключить из единичной остаточной функции (таблицы 2.5 -2.8).

Таблица 2.5 Значения производной f по х₄

X3	х2	х1	(1)	(2)	(1)(2)
0	0	0	0	0	0
0	0	1	0	1	1
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	0	0	0
1	0	1	0	1	1
1	1	0	0	0	0
1	1	1	1	1	1

Р_х4=4

Таблица 2.6 Значения производной f по х₃

x4	х2	Х1	(1)	(2)	(1)(2)
0	0	0	0	0	0
0	0	1	1	1	0
0	1	0	0	0	0
0	1	1	1	1	0
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	0	0	0
1	1	1	1	0	1

Р_х3=1

Таблица 2.7 Значения производной f по х₂

x4	Х3		Х1		(1)		(2)	(1)(2)
0	0		0		0		0	0
0	0		1		1		1	0
0		1		0		0	0		0
0		1		1		1	1		0
1		0		0		0	0		0
1		0		1		0	0		0
1		1		0		0	0		0
1		1		1		1	0		1

Р_х2=1

Таблица 2.8 Значения производной f по х₁

Х4	Х3	Х2	(1)	(1)0
0	0	0	1	1
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Р_х1=5

Из f(1) исключаем х₁, тогда:

Определим, какую из переменных следует исключить из остаточной функции f(1,1) (таблицы 2.9 – 2.11).

Таблица 2.9 Значения производной f по х₄

Х3	Х2	(1)	(1)1
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

Р_х4 =3

Таблица 2.10 Значения производной f по х₃

Х4	Х2	(1)	(2)	(1)(2)
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	1	1	0	1

Р_х3=1

Таблица 2.11 Значения производной f по х₂

х1	х0	(1)	(2)	(1) (2)
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	1	1	0	1

Р_х2=1

Исключаем х₄ и получаем остаточные функции:

Определим, какую из переменных следует исключить из остаточной функции f(1,0) (таблицы 2.12 - 2.18).

Таблица 2.12 Значения производной f по х₄

x3	х2	х1	(1)	(2)	(1)(2)
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	1	0
0	1	1	1	1	0
1	0	0	0	0	0
1	0	1	0	1	1
1	1	0	1	1	0
1	1	1	1	1	0

Р_х4=1

Таблица 2.13 Значения производной f по х₃

X4	х2	Х1	(1)	1(1)
0	0	0	0	1
0	0	1	1	0
0	1	0	1	0
0	1	1	1	0
1	0	0	0	1

Продолжение таблицы 2.13

1	0	1	0	1
1	1	0	1	0
1	1	1	1	0

Р_х3=3

Таблица 2.14 Значения производной f по х₂

X4	X3	X1	(1)	1(1)
0	0	0	1	0
0	0	1	1	0
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	0	1
1	1	1	0	1

Р_х2=3

Таблица 2.15 Значения производной f по х₁

X4	X3	X2	(1)	(2)	(1)(2)
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	0	1
0	1	1	1	1	0
1	0	0	1	1	0
1	0	1	1	1	0
1	1	0	1	0	1
1	1	1	1	1	0

Р_х1=2

Исключаем x₂

Таблица 2.16 Значения производной f по х₄

X3	X1	(1)	(2)	(1) (2)
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	1	0	1	1

Р_х4=1

Таблица 2.17 Значения производной f по х₃

X4	X1	(1)	(1) 1
0	0	0	1
0	1	1	0
1	0	0	1
1	1	0	1

Р_х3=3

Таблица 2.18 Значения производной f по х₁

X4	X3	(1)	(2)	(1) (2)
0	0	1	1	0
0	1	1	0	1
1	0	1	1	0
1	1	0	0	0

Р_х1=1

Исключаем x₃

Полученные остаточные функции можно реализовать при помощи двухвходовых логических элементов и блоков исключения переменной