АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОБЩИЕ СВЕДЕНИЯ

Функция называется булевой или логической (ЛФ), если она сама и ее аргументы принимают значения из множества {0, 1}.

Функция m переменных, определенная на всех 2 ^m их возможных наборах, называется полностью определенной. Если ЛФ не определена на некоторых наборах, то она называется недоопределенной.

Способы представления ЛФ. Булева функция может быть задана (представлена) словесно, таблично, аналитически, с помощью карт Карно.

Словесно описываются только простые ЛФ.

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

Аналитически (в виде формул) ЛФ может быть записана в совершенной дизъюнктивной нормальной форме (СДНФ) и в совершенной конъюнктивной нормальной форме (СКНФ).

Нормальная форма – это запись ЛФ в базисе И, ИЛИ, НЕ.

Запись булевой функции в СДНФ, заданной таблично, производится по следующему алгоритму:

· в таблице истинности выделяются строки, для которых значение функции равно единице;

· для выделенных строк записывают минтермы (конституенты 1), т. е. произведения аргументов, причем если какой-нибудь аргумент в строке равен нулю, то берется его отрицание;

· записывается логическая сумма полученных минтермов.

Представление булевой функции в СКНФ основано на понятии макстерма (конституенты 0).

Для записи булевой функции в СКНФ необходимо:

· в таблице истинности выделить строки, для которых значение функции равно нулю;

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

· записывается логическое произведение полученных макстремов.

Например, для функции неравнозначности y (x ₁, x ₂), заданной таблично (табл. 2.1), ее аналитическое представление будет иметь вид:

СДНФ ,

СКНФ .

Таблица 2.1

Номер набора	x 1	x 2	y	Минтермы мi	Макстермы Мi

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

Если функция записана в СДНФ (наиболее употребляемой), то для отображения ее на карте Карно в клетки, «координаты» которых соответствуют минтермам, вписывают единицы, в остальные клетки записывают нули (и другие символы – для недоопределенных функций).

Если ЛФ задана в СКНФ, то в клетки карты Карно, соответствующие макстермам, вписывают нули, а в остальные – единицы и другие символы. Нужно заметить, что в этом случае в «координатах» клеток переменные проставляют в инверсных значениях.

На рис. 2.1 показано отображение на картах Карно функции неравнозначности, заданной в СДНФ (а) и СКНФ (б).

а б

Рис. 2.1.

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

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

В процессе минимизации ЛФ, заданной в СДНФ, сначала находится сокращенная ДНФ (СкКНФ), затем она проверяется на лишние, не влияющие на истинность функции члены, и в результате получается тупиковая ДНФ (ТДНФ).

Если в испытуемой СкДНФ выявлено несколько лишних членов, то сразу их все исключать нельзя. В начале исключают один из избыточных членов, оставшееся выражение проверяют на лишние члены, в результате чего получают первую ТДНФ. Затем из СкДНФ удаляют второй лишний член, проводят испытание оставшихся членов, получают вторую ТДНФ и т. д. Таким образом, из всех полученных тупиковых форм можно выбрать минимальную ДНФ (МДНФ).

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

Минимизированная ДНФ ЛФ представляет собой дизъюнкцию конъюнкций общих для каждого контура переменных. Число контуров должно быть минимальным, а их площадь максимальной. Площадь прямоугольника покрытия может быть S _пр.= 2 ^m-i клеток, где i = {0, m } – целое число. Если, например, m = 3, то возможно S _пр.= 1, 2, 4, 8.

В результате можно сразу получить тупиковую форму ЛФ.

На рис. 2.2 сплошными линиями показано оптимальное покрытие единиц, которое дает тупиковую форму исходной ЛФ в СДНФ (таблица истинности – табл. 2.2) в виде . Третий контур покрытия (пунктирный) соответствует члену , который является лишним.

Таблица 2.2

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

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

Различают статические и динамические состязания.

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

Динамические состязания могут возникать при формировании на входе соседними состояниями алгоритмического перехода на выходе

от нуля к единице, и наоборот.

На практике больше внимания уделяют статическим состязаниям.

Для выявления опасных состязаний в логических схемах на практике используется критерий Хаффмена: статические состязания в устройстве с минимальной структурой имеют место, если на карте Карно при охвате соседних клеток контурами склеивания останутся хоты бы две клетки, не покрытые контуром.

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

На карте Карно (рис. 2.2) имеются две соседние клетки с «координатами» и (переходы 1 «3), не охваченные контуром покрытия единиц, и в соответствии с критерием Хаффмена в схеме могут появиться опасные 1-состязания. Их устранение достигается введением дополнительного контура покрытия (показан пунктиром), который оказался лишним при переходе от СкДНФ к ТДНФ.

Для построения данной схемы на ЛЭ И–НЕ применим к ЛФ двойное отрицание и теорему де Моргана

.

Рис. 2.3.

Логическая функция с дополнительным ЛЭ примет вид

.

Рис. 2.4. Рис. 2.5.

Для выявления опасных 0-состояний нужно перейти к покрытию на карте Карно нулей, что достигается инвертированием ЛФ и нанесением контуров и нулей в соответствии с выражением

В этом случае (рис. 2.5) соседние клетки охвачены контурами покрытия и опасных 0-состязаний не будет. Таким образом, повышение функциональной надежности комбинационных логических схем достигается введением избыточных логических элементов, что усложняет схему и приводит к увеличению аппаратных затрат. На практике применяются и другие способы построения функционально-устойчивых схем: передача сигналов от одного устройства к другому с помощью специальных импульсов синхронизации, пауза между которыми выбирается такой, чтобы за ее время полностью закончились переходные процессы в ЛЭ и схемах.

ЛАБОРАТОРНОЕ ЗАДАНИЕ

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

Таблица 2.3

1. По таблице истинности составить уравнение в СДНФ.

2. Провести минимизацию ЛФ по карте Карно.

3. Пользуясь критерием Хаффмена, определить возможность появления статических опасных состязаний (единичных и нулевых), предложить меры для их устранения.

4. Построить свободную от статических опасных состязаний минимизированную функцию в базе И–НЕ.

5. Нарисовать идеализированные временные диаграммы для опасных переходов входных сигналов.

СОДЕРЖАНИЕ ОТЧЕТА

1. Материалы, относящиеся к минимизации ЛФ, структурная схема и временные диаграммы.

2. Результаты практической проверки схемы на правильность функционирования.

3. Выводы по работе.

Литература: [3, 4]

Дата добавления: 2015-09-27 | Просмотры: 507 | Нарушение авторских прав