Теория дискретных систем автоматики и телемеханики 2 страница

4. Эквиваленция (читается- «А эквивалентно В»).

A

5. Логическое отрицание (инверсия, читается - НЕ).Имеет и другое обозначение:A.

­

 

6. Штрих Шеффера (читается - НЕ- И).

7. Стрелка Пирса (читается - НЕ-ИЛИ).

 

8.Сумма по модулю 2.

 

A B

 

4.3. Функционально полные системы ФАЛ.

 

ДУ автоматики и телемеханики характеризуются большим разнообразием. В связи с этим возникает вопрос о числе требуемых различных дискретных элементов для построения любого ДУ. Понятно, что эта задача сводится к определению множества таких ФАЛ, из которых можно получить любую сложную ФАЛ.

Систему функций ФАЛ называют функционально полной, если любая ФАЛ может быть выражена суперпозицией функций и переменных.

Суперпозицией называют подстановку в функцию вместо ее аргументов других функций.

Была доказана справедливость следующих утверждений:

 

Теорема 1.Если все функции функционально полной системы представимы через функции другой системы, то последняя система также функционально полна.

 

Теорема 2.Система ФАЛ функциональна полна.

 

На основании двух приведенных утверждений можно установить функциональную полноту следующих систем ФАЛ:

1. ,

2. ,

3. ,

4. ,

5. - штрих Шеффера,

6. - стрелка Пирса.

Функционально полная система ФАЛ называется базисом.

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

Например, классический базис не является минимальным, поскольку при удалении из него или он остается базисом. Базисы 5 и 6 очевидно являются минимальными.

 

Вследствие функциональной полноты функции Шеффера и стрелки Пирса любая ФАЛ может быть выражена через них. Это целесообразно с двух точек зрения.

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

Во-вторых, для большинства серий ТТЛ- и КМОП-технологий вентили И-НЕ и ИЛИ-НЕ являются базисными и предпочтительны во многих отношениях.

Вследствие этого реализация логических схем в базисе И-НЕ и ИЛИ-НЕ получила широкое распространение на практике.

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

Пусть ФАЛ имеет вид . Применим к этому выражению двойное отрицание и теорему де Моргана

.

Как видно, функция F включает только операции И-НЕ и ее реализация в базисе И-НЕ имеет вид, представленный на рис.1.

 

Рис.1.Реализация функции в базисе И-НЕ

Аналогичным образом от другой формы представления функции можно перейти к форме, удобной для реализации в базисеИЛИ-НЕ. Покажем это на примере.

Пусть функции имеет вид . Применим к этому выражению двойное отрицание и теорему де Моргана:

.

Как видно, функция F включает только операции ИЛИ-НЕ.

 

4.4. Нормальные формы ФАЛ.

Важным этапом синтеза ДУ является определение способа соединения между собой логических элементов, из которых оно «составляется». Здесь требуется представить ФАЛ через функции выбранного базиса.

Любая ФАЛ выражается через функции базиса неоднозначно. Естественно, желательно найти такую форму представления, которая дает наиболее простую схему устройства. При решении этой задачи удобно представить ФАЛ в некоторой канонической форме, называемой нормальной. Затем эта форма преобразуется так, чтобы она давала наиболее простую электрическую схему.

Имеется две канонические формы представления ФАЛ – дизъюнктивная нормальная форма (ДНФ) и конъюктивная нормальная форма (КНФ).

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

Теперь введем следующие определения: ДНФ – это дизъюнкция нескольких элементарных конъюнкций, а КНФ - это конъюнкция нескольких элементарных дизъюнкций.

Наряду с введенными нормальными формами ФАЛ, существуют еще две их разновидности:

- совершенная ДНФ (СДНФ) – представляет собой дизъюнкцию так называемых конституент единицы (минтермов), которые равны 1 на одном из тех наборов переменных, на которых и заданная функция также равна 1;

- совершенная КНФ (СКНФ) – представляет собой дизъюнкцию так называемых конституент нуля (макстермов), которые равны 0 на одном из тех наборов переменных, на которых и заданная функция также равна 0.

Для получения СДНФ нужно взять дизъюнкцию всех конституент единицы заданной ФАЛ.

Рассмотрим пример. Пусть ФАЛ от трех переменных задана своей таблицей истинности:

 

Выпишем все констиуенты единицы этой ФАЛ: , , , и объединим их операцией дизъюнкции. Полученное выражение и является СДНФ рассматриваемой ФАЛ: = + + + .

Заметим, что в СДНФ каждый минтерм содержит обязательно либо переменную , либо ее инверсию. Очевидно, что каждая ФАЛ имеет единственную СДНФ, но для представления ФАЛ может существовать несколько различных ДНФ.

Перейдем теперь к СКНФ: для ее получения нужно взять конъюнкцию всех конституент нуля заданной ФАЛ.
В качестве примера рассмотрим ФАЛ, заданную той же таблицей истинности. Выпишем для нее все конституенты нуля: , , , .

Зная их, выпишем СКНФ рассматриваемой ФАЛ: =( )( )

( )( ).

Понятно, что для любой ФАЛ существует единственная СКНФ, но для представления ФАЛ может существовать несколько различных КНФ.

 

4.5.Основные законы булевой алгебры.

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

 

Аксиомы алгебры логики:

; (1)

; (2)

; (3)

; (4)

; (5)

; (6)

; (7)

; (8)

; (9)

 

Законы алгебры логики для двух и более переменных:

1) коммутативный (переместительный) закон

а) ; б) ; (10)

 

2) ассоциативный (сочетательный) закон

а) ;

б) ; (11)

 

3) дистрибутивный (распределительный) закон

а) ; ×б) ; (12)

 

4) закон поглощения

а) ; б) ; (13)

 

5) закон склеивания

а) ; б) ; (14)

в) ; г) ; (15)

 

6) закон де Моргана

а) ; б) . (16)

 

4.6.Логические элементы и синтез логических схем.

 

Каждый логический элемент – это электронное устройство, предназначенное для обработки информации, представленной в виде двоичных кодов, отобpажаемыx напpяжeниeм (сигналом) выcoкого (1) или низкого (0) уpовня. Логические элементы реализyют логические функции И, ИЛИ, НЕ и их комбинации. Указанные логические операции выполняются с помощью электронных схем, входящих в состав микросхем. Из логических элементов И, ИЛИ, НЕ и других можно сконстpуировать цифровое электронное устройство любой сложности.

Условное графическое обозначение логического элемента представляет собой прямоугольник, внутри которого ставится изображение указателя функции. Входы изображают линиями с левой стороны прямоугольника, выходы элемента - с правой стороны. При необходимости разрешается располагать входы сверху, а выходы снизу. У логических элементов И, ИЛИ и других может быть любое, начиная с двух, количество входов и один выход. У элемента НЕ (инвертора) один вход и один выход. Если вход обозначен окружностью, то это значит, что вход инвертируется. Если окружностью обозначен выход, то элемент производит логическое отрицание (инверсию) результата операции, указанной внутри прямоугольника. Ниже приведены стандартные изображения некоторых логических элементов, принятые в российских схемах. Эти элементы реализуют соответственно ФАЛ (на рисунке они расположены слева направо и сверху вниз) – конъюнкции, дизъюнкции, штрих Шеффера, стрелку Пирса, инверсию, сумму по модулю 2. Последний элемент иногда изображают иначе, внутри прямоугольника вместо символа =1 ставится символ М2.

         
 

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

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

Из минтермов и макстермов методом суперпозиции можно составить ФАЛ в виде совершенных дизъюнктивных нормальных форм (СДНФ) или совершенных конъюнктивных нормальных форм (СКНФ). Полученные таким образом функции СДНФ и СКНФ будут представлять ФАЛ по заданной таблице истинности. После получения СДНФ и СКНФ их необходимо преобразовать (минимизировать). Преобразование данных функций с целью их минимизации осуществляется с помощью законов алгебры логики и специальных разработанных методов (метод Квайна, карты Карно (диаграммы Вейча) и т. д.). На них мы остановимся позже, а сейчас рассмотрим задачу синтеза на примере таблицы истинности, представленной ниже. Для данной таблицы истинности необходимо записать выражение для выходной функции F, провести ее преобразование (минимизацию) на основе законов алгебры логики и, используя основные логические элементы – НЕ, И и ИЛИ, разработать логическую схему реализации выходной функции F.

Для решения указанной задачи представим логическую функцию F в виде СДНФ, а затем и в виде СКНФ. Найдем минтермы и макстермы этой функции. В заданной таблице истинности выходная функция F принимает логическое значение, равное логической единице, при комбинациях логических переменных A, В и С, указанных под номерами 3, 6, 8, а значение, равное логическому нулю – при комбинациях, указанных под номерами 1, 2, 4, 5,7.

Минтермы запишем в следующем виде: ; ; . Минтермы представляют собой логические произведения (конъюнкции) логических переменных А, В, и С при значениях логической функции F, равных логической единице (комбинации 3, 6, 8). Сомножители (логические переменные A, В и С) входят в минтерм в прямом виде (без отрицания), если их значения равны логической единице, и в инверсном (с отрицанием), если их значения равны логическому нулю. Логическая функция F в виде СДНФ будет равна логической сумме минтермов: = .После минимизации логической функции F сиспользованием законов алгебры логики получим ее искомое выражение: .

Макстермы запишем в следующем виде:

Логическая функция в виде СКНФ будет равна логическому произведению макстермов:

Поскольку полученное выражение для F в виде СКНФ является более громоздким по сравнению с представлением F в виде СДНФ, то в качестве окончательного выражения для F примем ее выражение в виде СДНФ.

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

Используем полученное выражение логической функции F для разработки (построения) логической схемы на основе функционально полного набора логических элементов НЕ, И и ИЛИ. При построении логической схемы необходимо учитывать установленные в алгебре логики правила (старшинство операций) для выполнения логических операций, которые в данном случае реализуются с помощью логических элементов НЕ, И и ИЛИ. Старшинство производимых логических операций принято следующее: операция инверсии (отрицания), операция логического умножения (конъюнкции) и затем операция логического сложения (дизъюнкции). Реализация функции F в виде логической схемы, приведена на рис.

 

Рассмотренные выше таблицы истинности логических элементов показывают установившиеся значения логических переменных. Однако когда логические переменные представлены в виде электрических сигналов, то необходимо некоторое время для того, чтобы значение логической функции достигло уровня установившегося состояния из-за внутренних задержек по времени в электронных логических элементах. В среднем задержка электрического сигнала такого элемента составляет 10-9 с. В ДУ двоичные сигналы проходят через множество электронных схем, и задержка по времени может стать значительной. В этом случае выделяется отрезок времени (такт) на каждый шаг логической операции. Если операция заканчивается раньше, чем заканчивается тактовое время, то устройство, входящее в состав ДУ, ожидает ее окончания. В результате скорость выполнения операций несколько снижается, но достигается высокая надежность, так как обеспечивается синхронизация между многими параллельно выполняющимися операциями в ДУ. Синхронизация устройств в компьютере обеспечивается с помощью специального генератора – генератора тактовой частоты, который вырабатывает электрические импульсы стабильной частоты.

 

5. Минимизация ФАЛ.

Одна и та же ФАЛ может быть представлена различными ДНФ (в этом случае говорят, что они эквивалентны). Возникает задача нахождения среди эквивалентных форм оптимальных в каком-то смысле, например, минимальной по числу входящих в нее переменных. Решение такого рода задач имеет важные приложения в практике проектирования логических схем, поскольку сложность последних определяется размером ДНФ, и чем она проще, тем компактнее схема. Получение простейших ДНФ представляет собой сложную задачу, называемую задачей минимизации ДНФ (в классе ДНФ). За критерий простоты принимается общее число переменных в формуле.

 

5.1. Метод алгебраических преобразований.

Простейшие методы упрощения ДНФ имеют локальный характер и состоят в их алгебраических преобразованиях. При рассмотрении пар термов используются законы поглощения ( ), склеивания ( ) и удаления переменной ( ).

Продемонстрируем приемы локального упрощения ДНФ на примере:

.

Рассмотрим еще один пример:

.

 

5.2. Метод Квайна – Мак-Класки.

Опишем и проиллюстрируем его на конкретном примере ФАЛ от четырех переменных, заданной в виде таблицы истинности, представленной ниже.

№ набора Переменные Значение ФАЛ F

 

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

Теперь начнем реализацию метода Квайна – Мак-Класки для нашего примера. Сначала выпишем СДНФ рассматриваемой ФАЛ. Для удобства работы с ней представим ее в виде столбца, а каждой конституенте единицы в этом столбце присвоим порядковый номер (он указан справа от конституенты)

= + (1)

+ (2)

+ (3)

+ (4)

+ (5)

. (6)

Теперь выполним всевозможные склеивания выписанных конституент единицы:

(1-2) (1-3) ; (2-4) ; (3-4) ;(4-6) ;(5-6) .

Полученные термы вновь подвергнем склеиванию (в нашем примере возможными оказались только два склеивания):

((1-2) –(3-4)) ;((1-3)-(2-4)) .








Дата добавления: 2018-11-25; просмотров: 612;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.044 сек.