3.3.3. Метод минимизации частично определенных логических функций с помощью карт Карно

Пусть не полностью определенная логическая функция R(a,b,c,d) задана с помощью карты Карно (рис 3.4).

ab cd	00	01	11	10
00	-	1	0	1
01	-	1	1	1
11	0	1	-	0
10	1	0	1	0

Рис. 3.4. Карта Карно логической функции R(a,b,c,d)

Для представления функции R(a,b,c,d) в виде минимальной ДНФ целесообразно следующее доопределение логической функции (рис.3.5):

ab cd	00	01	11	10
00	1	1	0	1
01	1	1	1	1
11	0	1	1	0
10	1	0	1	0

Рис. 3.5. Доопределенная карта Карно логической функции R(a,b,c,d)

Доопределяем функцию единицами и нулями так, чтобы при составлении ДНФ было минимальное число импликант наименьшего ранга, т.е. покрываем все единичные значения функции минимальным числом прямоугольников максимального размера так, как показано на рис.3.6.

ab cd	00	01	11	10
00	1	1	0	1
01	1	1	1	1
11	0	1	1	0
10	1	0	1	0

Рис. 3.6. Карта Карно логической функции R(a,b,c,d)

В результате минимизации получим минимальную ДНФ логической функции R(a,b, c,d):

(3.10)

Сравнение эффективности минимизированных форм часто проводят по способу Шеннона. Этот способ базируется на введении такого понятия как цена схемы – Ц. Цену схемы можно рассчитать по следующей формуле:

, (3.11)

где - количество входов уj-ого элемента, i-количество элементов.

Оценим полученную минимизированную ДНФ логической функции (3.10) по формуле (3.11). Элементов “И” в выражении присутствует 5 (два элемента по 2 входа, три элемента по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=2*2+3*3+1*5+4*1=22 входа

Затем оценим СДНФ функции R(a,b,c,d) воспользовавшись картой Карно. Элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=11*4+1*11+4*1=59 входов

Контрольные вопросы:

3.1. В чем состоит метод Квайна?

3.2. Сформулируйте достоинства и недостатки метода карт Карно.

3.3. Что такое импликанта и импликантная матрица?

4. ПРОГРАММИРУЕМЫЕ ПОЛЬЗОВАТЕЛЕМ ЛОГИЧЕСКИЕ МАТРИЦЫ

Создание двухуровневых программируемых пользователем логических матриц (ППЛМ) было ответом производителей цифровых интегральных микросхем на сложившуюся в конце 60-х годов прошлого века парадоксальную ситуацию: разновидностей логических микросхем требовалось все больше и больше, а объемы производства каждой разновидности постоянно снижались. В такой ситуации был найден, возможно, единственно правильный выход, который заключался в разработке и массовом выпуске достаточно универсальных интегральных микросхем, которые могли использоваться и в единичных экземплярах, но миллионами индивидуальных пользователей. Именно таким образом обеспечивался компромисс между большими затратами на организацию массового производства некоторого типа интегральных микросхем и быструю окупаемость этих затрат [1,5].

Т

акими интегральными микросхемами и стали, так называемые ныне, двухуровневые программируемые пользователем логические матрицы. Эти интегральные микросхемы позволяют (при наличии у пользователя специальных программаторов) оперативно реализовывать достаточно сложные многовыходные логические преобразователи (ЛП), закон функционирования которых изначально представляется в естественной для человека форме. Строгое математическое выражение этой естественной формы в научно-технической литературе принято называть совершенной дизъюнктивной нормальной формой (СДНФ) или ее минимизированным эквивалентом – дизъюнктивной нормальной формой (ДНФ). Универсализм двухуровневых ППЛМ обеспечивается введением на этапе их серийного производства значительной структурной избыточности как электронных элементов ППЛМ, так и электрических связей между этими элементами. При этом в архитектуру ППЛМ вводятся дополнительные электронные узлы, обеспечивающие по командам извне разрушение в определенных местах ненужных электрических связей между избыточными элементами, образующими собственно ППЛМ. Схема электрическая функциональная незапрограммированной ППЛМ показана на рис. 4.1.

Как видно из рис.4.1 ППЛМ состоит из блока инверторов (DD₁...DD_S) входных логических переменных (X₁...X_S) и двух матриц.

Матрица И реализует на шинах Z₁...Z_q элементарные конъюнкции с любым набором прямых и инверсных значений логических переменных X₁...X_S, а матрица ИЛИ реализует элементарные дизъюнкции с элементарными конъюнкциями, сформированными на шинах Z₁...Z_q. Результат операций дизъюнкции формируется на выходных шинах Y₁...Y_t.

Матрицы И и ИЛИ представляют собой систему ортогональных проводников, в узлах пересечения которых располагаются полупроводниковые элементы, реализующие с резисторами нагрузки операции И и ИЛИ. Операцию И реализуют при помощи диодов, а операцию ИЛИ – при помощи триодов.

Электрическое подключение диодов и триодов к соответствующим ортогональным проводникам осуществляется через специальные перемычки P_i (P_j), некоторые из которых при программировании ППЛМ удаляются (пережигаются) в соответствующих узлах. На рис. 4.2 показано подключение диодов в узлах матрицы И, а на рис. 4.3 – подключение триодов в узлах матрицы ИЛИ [6].

Логические уравнения для выходных сигналов Y₁...Y_t , формируемых незапрограммированными ППЛМ, имеют один и тот же вид в СДНФ:

(4.1)

где r =;

- операция логического сложения (дизъюнкция);

- операция логического умножения (конъюнкция).

Рис. 4.1. Схема электрическая функциональная незапрограммированной ППЛМ (без дополнительных электронных узлов)

Рис. 4.3. Подключение триодов в узлах матрицы ИЛИ

C

хема электрическая функциональная запрограммированной ППЛМ изображается примерно так же, как представлено на рис. 4.1. Отличие состоит в том, что метки () на схеме проставляют только в тех узлах матрицы ППЛМ, в которых должны быть подключены диоды и транзисторы, обеспечивающие реализацию логических уравнений.

Контрольные вопросы:

4.1. Какими причинами вызвано создание двухуровневых программируемых пользователем логических матриц?

4.2. Из каких матриц состоит ППЛМ, назначение этих матриц.

4.3. Как осуществляется программирование матрицы?

4.4. Какой вид имеют логические уравнения выходных сигналовY_t, формируемых незапрограммированными ППЛМ?

5. ВАРИАНТЫ И ЗАДАНИЯ КОНТРОЛЬНОЙ РАБОТЫ

Варианты контрольной работы определяются по последней и предпоследней цифрам зачетной книжки студента. В табл. 5.1 по столбцам записана предпоследняя цифра зачетной книжки, а по строкам – последняя. На пересечении строк и столбцов в ячейке таблицы записан номер варианта контрольной работы, соответствующий последней и предпоследней цифрам зачетной книжки студента.

Например:

Номер зачетной книжки студента 567398. Для определения номера контрольной работы по столбцам табл. 5.1 ищем цифру 9, а по строкам – 8. В ячейке таблицы на пересечении соответствующих строки и столбца записана цифра 7. Следовательно, номер варианта контрольной работы студента – 7.

Таблица 5.1

Послед-няя цифра	Предпоследняя цифра зачетной книжки
	0	1	2	3	4	5	6	7	8	9
0	1	11	21	5	16	24	1	0	22	0
1	2	12	22	4	14	22	2	3	21	4
2	3	13	23	3	15	23	3	12	0	8
3	4	14	24	2	13	24	4	13	8	16
4	5	15	0	1	12	0	5	8	13	20
5	6	16	10	0	11	10	6	9	17	24
6	7	17	9	20	10	9	7	5	18	12
7	8	18	8	19	21	8	8	4	19	5
8	9	19	7	18	22	7	9	3	4	7
9	10	20	6	17	23	6	10	2	6	2

Табл. 5.2 является таблицей истинности логических функций. Номер каждой логической функции из этой таблицы соответствует номеру варианта контрольной работы, например, если номер варианта 7, то в табл. 5.2 необходимо рассматривать данные для функции F_7.

Таблица 5.2

Таблица истинности логических функций F_i,i=0,…24

x3	x2	x1	x0	F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F 14	F15	F 16	F 17	F18	F 19	F20	F 21	F 22	F23	F 24
0	0	0	0	1	-	0	1	-	-	0	1	1	1	1	-	0	0	1	-	0	1	1	-	-	0	1	1	1
0	0	0	1	0	1	-	0	-	1	-	-	0	0	-	1	-	-	-	1	1	-	0	0	1	1	-	0	0
0	0	1	0	0	0	0	-	0	-	1	1	1	1	0	0	0	0	0	1	-	1	1	1	1	-	1	-	-
0	0	1	1	-	1	-	1	0	0	-	1	-	-	1	1	1	1	0	-	1	1	-	1	0	1	1	1	1
0	1	0	0	0	-	0	0	1	1	0	0	0	0	0	-	0	0	1	1	0	0	0	0	1	0	0	0	0
0	1	0	1	1	0	1	-	1	0	-	-	1	0	-	0	-	-	-	0	1	0	1	0	0	1	0	1	0
0	1	1	0	-	1	0	1	0	-	0	1	1	-	0	1	0	1	0	1	0	1	-	-	1	0	1	-	0
0	1	1	1	1	0	1	0	1	1	-	0	-	1	1	-	1	0	1	1	1	0	1	1	-	1	0	1	-
1	0	0	0	0	1	1	1	0	0	-	0	1	1	-	0	0	-	0	-	1	1	-	0	1	-	-	0	1
1	0	0	1	0	1	1	0	1	0	1	-	1	-	0	1	-	1	1	-	0	0	1	-	0	-	1	-	1
1	0	1	0	0	1	1	1	-	0	0	0	1	1	1	-	0	0	-	-	-	1	0	0	-	0	-	1	1
1	0	1	1	1	-	0	0	-	1	1	1	-	0	0	-	1	1	1	1	1	-	1	-	1	0	0	-	-
1	1	0	0	-	-	0	-	1	1	0	-	-	0	-	1	-	0	0	0	0	0	-	0	0	1	1	0	0
1	1	0	1	1	-	-	-	0	1	1	1	-	-	-	0	1	1	-	0	1	-	0	1	-	-	0	-	0
1	1	1	0	0	1	-	1	-	0	0	0	1	-	1	-	0	-	0	1	-	0	1	0	1	0	-	0	1
1	1	1	1	1	0	1	0	1	-	1	1	0	1	0	1	-	1	1	0	1	1	0	1	0	0	1	0	-

Логические переменные x₀, x₁, x₂, x₃ являются входными переменными для логических функций F_i, i=0,…24.

Для выполнения контрольной работы №2 необходимо выполнить следующие задания (все задания контрольной работы выполняются для одной логической функции, которая выбирается в соответствии с вариантом контрольной работы из табл. 5.2).

Задания для контрольной работы №2:

1. Минимизировать логическую функцию, заданную табл. 5.2, с помощью метода карт Карно (для эффективности минимизации логической функции можно доопределить таблицу истинности более выгодным для минимизации образом). В результате минимизации получить тупиковые ДНФ и КНФ логической функции.

2. Реализовать в элементных базисах ИЛИ-НЕ и И-НЕ полученные в п.1 тупиковые ДНФ и КНФ логической функции, построить логические схемы полученных выражений (при выполнении данного пункта должно получиться 4 логические схемы).

3. Минимизировать доопределенную в п. 1 логическую функцию методом Квайна, методом испытания импликант, методом импликантных матриц и сравнить полученные минимизированные формы.

4. Реализовать СДНФ логической функции на ПЛМ.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Новожилов О.П. Основы цифровой техники: учеб. пособие / О.П. Новожилов. М.: ИП РадиоСофт, 2004. 528 с.

2. Дискретная математика и математические вопросы кибернетики, т. 1 / Ю.Л. Васильев, Ф.Я. Ветухновский, В.В. Глаголев и др.; под ред. С. В. Яблонского, О. Б. Лупанова. М.: Наука, 1974. 312 с.

3. Филиппов А.Г. Проектирование логических узлов ЭВМ / А.Г. Филиппов, О.С. Белкин. М.: Сов. Радио, 1974. 344 с.

4. Лачин В.И. Электроника: учеб. пособие. 4-е изд. / В.И. Лачин, Н.С. Савелов. Ростов н/Д: Феникс, 2004. 576 с.

5. Миловзоров О.В. Электроника: учебник для вузов / О.В. Миловзоров, И.Г. Панков И.Г. М.: Высш.шк., 2004. 288 с.

6. Тюрин С.В. Практикум по теории автоматов: синтез синхронного управляющего автомата: учеб. пособие / С.В. Тюрин. Воронеж: ВГТУ, 2004. 84 с.