Компьютерная схемотехника (стр. 5 из 32)
Целью минимизации является получение минимальной ДНФ или КНФ, содержащей минимум членов с минимальным количеством входящих в них переменных. Для этого необходимо минимальным числом контуров охватить хотя бы один раз каждую единицу (нуль). При этом необходимо стремиться, чтобы в каждое накрытие входило как можно больше смежных единиц (нулей).
На рисунке 3.1 показаны диаграммы Вейча при числе логических переменных n=2,3,4. Для n>4 диаграммы содержатся в [18]. Если наборы переменных исходной таблицы истинности упорядочены по убыванию их десятичных эквивалентов, то следует воспользоваться диаграммами Вейча, приведенными в [5, 6]
3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча
Пример 1. Для контроля за возможной деформацией металлической конструкции из-за перегрева в ее различных критических точках установлены четыре термодатчика, обозначенные ТД1, ТД2, ТД3, ТД4. Экспериментальные исследования конструкции показали, что в процессе ее эксплуатации возможны шесть сочетаний сработавших и не сработавших датчиков. При этом деформация конструкции возникала в следующих случаях:
1) сработали ТД4, ТД3 и не сработали ТД2 и ТД1;
2) сработали ТД4, ТД3, ТД2 и ТД1;
3) сработали ТД2 и не сработали ТД4, ТД3 и ТД1;
4) сработали ТД3, ТД2 и ТД1 и не сработал ТД4;
В случаях, когда:
5) сработали ТД4, ТД3, ТД2 и не сработал ТД1;
6) сработали ТД2, ТД1 и не сработали ТД4, ТД3
деформация конструкции не возникала.
Таблица 3.5
| № | Состояние датчиков | Деформация конструкции | |
| Сработали | Не сработали | ||
| 1 | ТД4, ТД3 | ТД2, ТД1 | Возникала |
| 2 | ТД4 ... ТД1 | ― | |
| 3 | ТД2 | ТД4, ТД3, ТД1 | |
| 4 | ТД3, ТД2, ТД1 | ТД4 | |
| 5 | ТД4, ТД3, ТД2 | ТД1 | Не возникала |
| 6 | ТД2, ТД1 | ТД4, ТД3 | |
По условию эксплуатации конструкции другие сочетания сработавших и не сработавших датчиков невозможны.
Необходимо спроектировать цифровое логическое устройство, включающее сигнал тревоги, если происходит срабатывание термодатчиков в опасном сочетании.
Обозначим цифровые сигналы на выходе термодатчиков логическими переменными: ТД4→D; ТД3→С; ТД2→В; ТД1→А, а логическую функцию, которую должно реализовать устройство контроля – F.
Составим таблицу истинности, отражающую требуемую логическую функцию (таблица 3.6).
Таблица 3.6
| (ТД4) | (ТД3) | (ТД2) | (ТД1) | |||
| № набора | D | C | B | A | F | |
| 0 | 0 | 0 | 0 | 0 | - | |
| 1 | 0 | 0 | 0 | 1 | - | |
| 2 | 0 | 0 | 1 | 0 | 1 | 3) |
| 3 | 0 | 0 | 1 | 1 | 0 | 6) |
| 4 | 0 | 1 | 0 | 0 | - | |
| 5 | 0 | 1 | 0 | 1 | - | |
| 6 | 0 | 1 | 1 | 0 | - | |
| 7 | 0 | 1 | 1 | 1 | 1 | 4) |
| 8 | 1 | 0 | 0 | 0 | - | |
| 9 | 1 | 0 | 0 | 1 | - | |
| 10 | 1 | 0 | 1 | 0 | - | |
| 11 | 1 | 0 | 1 | 1 | - | |
| 12 | 1 | 1 | 0 | 0 | 1 | 1) |
| 13 | 1 | 1 | 0 | 1 | - | |
| 14 | 1 | 1 | 1 | 0 | 0 | 5) |
| 15 | 1 | 1 | 1 | 1 | 1 | 2) |
Диаграмма Вейча, отражающая данную таблицу, показана на рисунке 3.2.
Рисунок 3.2
Если будем производить минимизацию по единицам, то в клетки, содержащие прочерки проставим дополнительные единицы.
Основные единицы накрываем тремя контурами: 1-й контур (1I) образуют клетки первой и последней строки, 2-й (1II) - клетки 2-го столбца и 3-й (1III) - 4-го столбца.
Итоговое булево выражение минимизированной ПФ имеет вид
.(3.9)
Это выражение должно быть реализовано цифровым логическим устройством, включающим сигнал тревоги.
Рассматриваемую функцию можно минимизировать и по нулевым значениям (нулям). Для этого доопределяем клетки с номерами 1,6,9 и 11 нулями и накрываем два основных нуля двумя прямоугольниками, включающими два и четыре элемента (нуля). Первый прямоугольник (0I) охватывает клетки с номерами 6,14, второй (0II) – 1,3,11 и 9.
Итоговое булево выражение минимизированной ПФ имеет вид
.(3.10)
Оба выражения (3.9) и (3.10) эквивалентны, и применять следует то из них, которое проще реализуется на конкретном наборе логических элементов (базисе). Этот вопрос будет рассмотрен в следующих лекциях.
Пример 2. Необходимо разработать блок приоритетных прерываний от 2-х внешних устройств: ВУ1 и ВУ2. ВУ с меньшим номером соответствует более высокий приоритет. Упрощенная структура проектируемой системы показана на рисунке 3.3.
Рисунок 3.3
На схеме приняты следующие сокращения: МПС – микропроцессорная система; ВУ – внешнее устройство; БПП – блок приоритетных прерываний; ВТП – вектор текущего прерывания, который с помощью логических переменных β1, β2 описывает возможные состояния МП-системы при обслуживании запросов прерываний от ВУ (таблица 3.7); РТП – регистр текущего прерывания (запоминает значения переменных β1, β2); ЗП1, ЗП2 – запросы прерываний от ВУ1, ВУ2 (описываются переменными α1, α2); ТП – требование прерывания (логическая функция F3); ВЗП – вектор запроса прерывания (отображается комбинацией значений логических функций F1 и F2 (таблица 3.8)).
Таблица 3.7
| №набора | β1 | β2 | ВТП |
| 0 | 0 | 0 | ожидание |
| 1 | 0 | 1 | обслуживается ВУ1 |
| 2 | 1 | 0 | обслуживается ВУ2 |
| 3 | 1 | 1 | – |
Таблица 3.8
| ВЗП | F1 | F2 |
| F3 =0 или неопределено | – | – |
| Запрос от ВУ2 | 1 | 0 |
| Запрос от ВУ1 | 0 | 1 |
МП-система периодически проверяет значение сигнала ТП (функция F3). Если ТП=0 (запрос на прерывание отсутствует), то значения функций F1, F2безразличны и МПС продолжает свою работу. Если ТП=1, то МП-система анализирует значение вектора ВЗП (комбинацию функций F1, F2) и определяет номер запроса прерывания. Так как набор переменных β1=β2=1 невозможен (таблица 3.6), то функции F1, F2, F3 в таких случаях неопределены. Таким образом, задача БПП является реализация трех логических функций F1, F2, F3, каждая из которых определяется значениями четырех логических переменных: α1, α2, β1и β2.
Составим таблицу истинности (таблица 3.9) для названных функций.
Таблица 3.9
| D | C | B | A | ||||
| № набора | α1 | α2 | β1 | β2 | F3 | F1 | F2 |
| 0 | 0 | 0 | 0 | 0 | 0 | - | - |
| 1 | 0 | 0 | 0 | 1 | 0 | - | - |
| 2 | 0 | 0 | 1 | 0 | 0 | - | - |
| 3 | 0 | 0 | 1 | 1 | - | - | - |
| 4 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 | 0 | - | - |
| 6 | 0 | 1 | 1 | 0 | 0 | - | - |
| 7 | 0 | 1 | 1 | 1 | - | - | - |
| 8 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 0 | - | - |
| 10 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 1 | 1 | - | - | - |
| 12 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 13 | 1 | 1 | 0 | 1 | 0 | - | - |
| 14 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 | - | - | - |
Представляем функции F1, F2, F3 диаграммами Вейча (рисунок 3.4)
Для F3 Для F1
Для F2
Рисунок 3.4
Булевы выражения минимизированных ПФ имеют вид:
F3= 
.(3.11)
F1= 
.(3.12)
F2= 
.(3.13)
Полученные выражения (3.11-3.13) имеют вполне конкретное логическое толкование и при наличии определенных навыков могли быть получены без составления таблицы истинности и минимизации ПФ.
Так, если F3=1, а в противном случае F1 и F2 безразличны, то запрос от ВУ1 в виде комбинации F1=0, F2=1 поступит лишь тогда, когда α1=1. Значение α2 безразлично, так как даже при α1=α2=1 все равно α1 имеет более высокий приоритет. Если α1=0, а F3=1, то это значит, что требование прерывания вызвано запросом от ВУ2 (α2=1). При записи выражения (3.11) можно было руководствоваться следующими соображениями. F3=1 в двух случаях. Во-первых, если поступил запрос от ВУ1 (α1=1) и при этом МП-система ожидает запроса либо обслуживает прерывание от ВУ2 (в обоих случаях β2=0, см. таблицу 3.8). Во вторых, если поступил запрос от ВУ2 (α2=1) и при этом МП-сиcтема находится в состоянии ожидания (β1=β2=0). Сказанное соответствует двум составляющим выражения (3.11).