Схемота_ДЗ

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

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

Введение в ФАЛ стробирующего сигнала C. Минимальные ДНФ и КНФ ФАЛ конъюнктивно объединяются с синхросигналом С.

Если f(xn, …, x1) является минимальной ДНФ, то к конъюнкции C·f(xn, …, x1) применяется распределительный закон, т.е. правило раскрытия скобок, и далее преобразование вновь полученной ДНФ функции в форму базиса И – НЕ. Если f(xn, … , x1) является минимальной КНФ, то конъюнкция C·f(xn, … , x1) аналогичным образом преобразуется в форму базиса ИЛИ – НЕ.

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

Более простой форме ФАЛ соответствует логическая схема с меньшими аппаратурными затратами.

Упрощение ФАЛ называется минимизацией. В настоящее время наиболее развиты методы минимизации дизъюнктивных и конъюнктивных нормальных форм ФАЛ.

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

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

В настоящее время разработаны эффективные формализованные методы минимизации ФАЛ в классе дизъюнктивных и конъюнктивных нормальных форм.

Алгоритм получения минимальных ДНФ (КНФ) сводится к следующим этапам:

1.Нахождение сокращенной ДНФ (КНФ).

2.Нахождение всех возможных тупиковых ДНФ (КНФ).

3.Выбор из тупиковых форм минимальных ДНФ (КНФ).

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

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

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

накрытия.

Пусть на каком-либо наборе переменных функция f равна а1, а функция на том же наборе равна а2. Тогда говорят, что на данном наборе функция f своим значением а1 накрывает значение а2 функции .

Функция входит в функцию f, если все единицы функции накрываются единицами функции f, а нули функции могут быть накрыты как нулями, так и единицами функции f.

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

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

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

Любая ФАЛ имеет конечное число простых импликант, но не более числа конституент единицы в СДНФ этой функции.

Так как простые импликанты – это элементарные конъюнкции, в которые входят все конституенты единицы функции, то дизъюнкция всех простых импликант функции f(хn, …, х2, х1) равна этой функции и называется сокращенной ДНФ.

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

Если две элементарные конъюнкции/дизъюнкции ( в том числе и конституенты единицы/нуля) одного и того же ранга и одних и тех же переменных отличаются только

т.е. в правой части равенств (7), кроме члена А, остаются обе склеивающиеся конъюнкции Ахi и ̅ или дизъюнкции ( ) и ( ̅ )

Согласно теореме Квайна, если в СДНФ (СКНФ) ФАЛ выполнить все операции неполного склеивания и затем все операции поглощения, то получится сокращенная ДНФ (КНФ) этой функции.

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

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

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

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

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

Для нахождения минимальных КНФ можно рекомендовать два метода:

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

2. Минимизация функции, инверсной заданной, и преобразование полученной минимальной ДНФ функции f по законам инверсии и де Моргана.

Метод Квайна. При минимизации по методу Квайна заданную ФАЛ f(хn, … , х1) нужно представить в СДНФ, если она не задана в этой форме.

Если ФАЛ задана в произвольной ДНФ, то элементарные конъюнкции с помощью операции развертывания нужно представить в виде конституент единицы. Операция развертывания заключается в умножении элементарных конъюнкций, не являющихся конституентами единицы, на выражение типа ( ̅ ), где хi – переменная, отсутствующая в записи элементарной конъюнкции.

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

Этапы минимизации ФАЛ по методу Квайна:

1. Нахождение сокращенной ДНФ. Для этого выполняются операции неполного склеивания и поглощения с целью поиска всех простых импликант функции. Сначала попарно сравниваются все конституенты единицы функции, входящие в ее СДНФ. Если

какие-либо две конституенты единицы отличаются друг от друга только одной переменной (в одной хi, а в другой ̅ ), то выписывают их общую часть, а против этих

импликантой А. Таким образом получаются все импликанты, являющиеся конъюнкциями (n-1)-го ранга. Полученные элементарные конъюнкции (n-1)-го вновь сравнивают попарно, находят импликанты, являющиеся конъюнкциями (n-2)-го ранга, склеивающиеся конъюнкции (n-2)-го отмечают метками и т.д. Этап заканчивается, когда вновь полученные конъюнкции r-го ранга уже не склеиваются между собой. Все неотмеченные конъюнкции являются простыми импликантами. Неотмеченными могут оказаться и исходные конституенты единицы. Дизъюнкция всех простых импликант и есть сокращенная ДНФ заданной ФАЛ.

2. Нахождение существенных импликант. Задача данного этапа - определить простые импликанты, которые должны обязательно входить в минимальную ДНФ, т.е. существенные импликанты. На последующих этапах определяются простые импликанты, которые можно не включать в минимальную ДНФ.

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

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

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

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

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

Сравнивая первую конституенту единицы списка с последующими, затем вторую с последующими и т.д., находим пары конституент единицы, которые отличается только одной переменной. Такие конъюнкции склеиваются по этой переменной. После выполнения всех сравнений получим элементарные конъюнкции 3-го ранга:

Сравнивая элементарные конъюнкции 3-го ранга, а, именно, первую с последующими, вторую с последующими и т.д., получим элементарную конъюнкцию 2-го ранга ̅ ̅ На этом процесс сравнения закончен. Простыми импликантами являются конъюнкции, не отмеченные знаком «*»: ̅ ̅ ̅ ̅ Знак «*» означает, что конъюнкции, отмеченные этим знаком, поглощаются другими конъюнкциями, не отмеченные этим знаком. Дизъюнкция всех простых импликант – это сокращенная ДНФ.

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

Таблица 2

исключаем строки, соответствующие этим импликантам, и столбцы 2, 3, 4, 5, 6, 7 конституент единицы, поглощаемых этими импликантами. Тогда получим табл. 3.

Таблица 3

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

Минимальной формой данной ФАЛ является f(х4, х3, х2, х1) = ̅ ̅ ̅

При большом числе переменных трудоемкость метода Квайна возрастает, что связано с необходимостью полного попарного сравнения всех конъюнкций при нахождении простых импликант. Метод Квайна-Мак-Класки упрощает поиск простых импликант за счет уменьшения числа сравнений. Однако более эффективным при числе аргументов 4-6 является применение карт Карно для нахождения простых и существенных импликант. Таким образом упрощается выполнение первого и второго этапов метода Квайна.

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

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

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

На рис. 1,а,б,в,г приведены карты Карно для функций двух, трех, четырех и пяти переменных соответственно.

Рис. 1.

Карты Карно для функций большего числа переменных строятся из карт для меньшего числа переменных. Например, карта Карно для трех переменных составлена из двух карт Карно для двух переменных, карта Карно для четырех переменных составлена из двух карт Карно для трех переменных или из четырех карт Карно для двух переменных. На рис. 1 в качестве некоторых примеров короткими отрезками линий (оси симметрии, или оси «отражения») отмечены границы карт меньшего числа переменных, из которых строятся карты Карно большего числа переменных. Например, карта Карно для трех переменных (рис. 1,б) состоит из двух карт для двух переменных х2 и х1, столбцы которых соединены по границе, отмеченной вертикальным отрезком линии. Нумерация столбцов левой карты для двух переменных х2, х1 следует в порядке 0, 1, а для правой – 1, 0, т.е. идет отражение («зеркальное») порядка нумерации столбцов по переменной х2. Левая карта для двух переменных х2, х1 соответствует переменной ̅ , правая – х3, а поэтому нумерация столбцов по переменным х3, х2 имеет порядок 00, 01, 11, 10. Аналогично можно представить, что карта Карно для пяти переменных составлена из двух карт для четырех переменных. Левая карта для четырех переменных имеет порядок нумерации столбцов по переменным х4, х3 00, 01, 11, 10, правая – 10, 11, 01, 00, т.е. отраженный («зеркальный»). Левая карта Карно четырех переменных х4, х3, х2 х1 соответствует переменной ̅ , правая – переменной х5. Поэтому нумерация столбцов по переменным х5, х4, х3 карты Карно для пяти переменных имеет порядок 000, 001, 011, 010, 110, 111, 101, 100. Далее на картах Карно разделение на карты меньшего числа переменных отрезками линий не отмечается, но подразумевается.

Каждой клетке на карте Карно соответствует определенный набор переменных. Например, на карте Карно для пяти переменных клетке, расположенной на пересечении столбца 010 и строки 11, соответствует набор 0, 1, 0, 1, 1 переменных х5, х4, х3, х2, х1.

Карта заполняется в соответствии с таблицей истинности: значения 1 записываются в клетках, соответствующих наборам, на которых функция равна 1. Значения 0 функции в клетках карты обычно опускаются и эти клетки остаются пустыми. Применяется и другой способ нанесения функции на карту Карно нулями в те ячейки, на наборах которых функция равна нулю. Клетки, соответствующие наборам, на которых функция равна 1, остаются пустыми.

Одно из преимуществ карт Карно состоит в том, что на нее можно наносить функцию, заданную в произвольной ДНФ.

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

Две конституенты единицы/нуля склеиваются, если:

-они расположены в соседних клетках одной строки или одного столбца;

-они расположены в противоположных клетках одной строки или одного столбца;

-они находятся в клетках, симметрично расположенных относительно осей симметрии клетках двух карт для двух, трех, четырех и большего числа переменных, а сами карты расположены по соседству друг с другом или в

противоположных концах столбцов или строк карт (не клеток).

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

На рис. 2 приведена карта Карно для шести переменных Х6,Х5,…,X1, составленная из восьми карт для трех переменных или из четырех карт для четырех переменных.

Рис. 2 Поясним правила нахождения склеивающихся конституент единицы. Конституента

единицы, обозначенная на карте Карно (Рис. 2) буквой а ( ̅ ̅ ̅ ) склеивается с соседними конституентами единицы b (по переменной х1), с (по переменной х4), d (по переменной х3), расположенных в соседних клетках карты трех переменных, а также с конституентами единицы i (по переменной х5), h (по переменной х6), расположенных в соседних картах, а каждая из клеток i и h расположена симметрично с клеткой a относительно границ раздела карт для трех переменных. Kонституенты единицы a и e не склеиваются, так как расположены несимметрично относительно границы соседних карт Карно для трех переменных. Конституента единицы а не склеивается с конституентами единицы j и f, так как карты Карно трех переменных, в которых они расположены, не являются соседними с картой Карно трех переменных, в которой расположена конституента единицы а.

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

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

На рис. 3 приведены примеры групп склеивающихся конституент единицы.

Карты Карно позволяют легко и быстро находить простые и существенные импликанты функции по следующему алгоритму:

1. Выбирается клетка, содержащая «единицу», и определяются все возможные группы этой клетки с другими клетками, содержащими «единицы». Группам клеток, соответствуют конъюнкции, ранг которых меньше ранга конституент единицы. Определяют эти конъюнкции, соответствующие группам клеток, содержащих «единицы».

2. Анализируются эти группы. Если все «единицы» одной группы содержатся в другой группе, то первую вычеркивают. Не вычеркнутые группы являются простыми импликантами.

Если для рассматриваемой клетки с «единицей» не вычеркнутой осталась одна группа, то соответствующая ей конъюнкция является также и существенной импликантой. Если клетка с «единицей» ни с какой другой не склеивается, то соответствующая этой клетке конституента единицы является и простой, и существенной импликантой.

3. Повторяются пункты 1 и 2 для каждой клетки карты, содержащей «единицу», т.е. для каждой конституенты единицы. При достаточном опыте запись всех промежуточных групп становится ненужной, поэтому сразу записываются простые импликанты.

Минимизация по методу Квайна с применением карт Карно сводится к следующим этапам:

1.Нанесение функции на карту Карно.

2.Анализ каждой клетки с «единицей» и нахождение для нее простых и существенных импликант. Если найдена существенная импликанта, то клетки с «единицами», составляющие эту импликанту, при дальнейшем поиске простых импликант не рассматривают. Для этого их отмечают точками. Поэтому при рассмотрении карт Карно необходимо прежде всего обнаружить клетки с «единицами», которые дают существенные импликанты. Это уменьшает количество рассматриваемых клеток с «единицами».

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

4.Как и по методу Квайна составляется импликантная таблица, строки которой обозначаются простыми импликантами, полученными на этапе 2, а столбцы – конституентами единицы, оставшимися после выполнения этапа 3.

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

Пример 7. Найти минимальную ДНФ функции f(х4, х3, х2, х1), которая равна единице на наборах переменных: 2, 3, 4, 5, 7, 9, 11, 12, 13.

Решение. 1. Нанесем заданную ФАЛ на карту Карно (рис. 4,а).

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