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

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

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

х = 0, если х ≠ 1;

х =1, если х ≠ 0. (18 1)

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

Таблица 7

1. Составление логических функций

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

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

(19)

Каждый член в (19) соответствует некоторому набору значений аргументов, при котором равна единице.

Пример логической функции, не являющейся СДНФ (20)

, (20)

т.к. не все члены объединены логической суммой и не каждая из них содержит все аргументы.

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

, (21)

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

Примером функции, не относящейся к СКНФ, является (22)

(22)

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

2. Приведение ФАЛ к совершенной канонической форме в базисе И, ИЛИ, НЕ

В случае если ФАЛ, заданная аналитически, не относится к СДНФ (СКНФ), а так же при не полностью заданной функции (таблица 8),

Таблица 8

когда значения на некоторых выходах логического устройства не появляются никогда,

ее необходимо привести совершенному виду.

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

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

(23)

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

Тогда выражение для приобретает вид СДНФ

(24)

Конъюнктивная нормальная форма, полученная из таблицы 8

(25)

Для получения минимальной формы СКНФ запрещенные значения в таблице 8 заменяются лог.0 и искомая минимальная форма приобретает вид

(26)

При составлении (26) учтено свойство идемпотентности (исключения повторения)

3. Составление структурной схемы логического устройства

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

4. Переход к сокращенной форме записи логической функции

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

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

Если в структуре логической функции выявляются пары членов вида

, (27)

то выполняется операция склеивания (поскольку, ), приводящая к результату (z), который вводится в выражение функции в качестве дополнительного члена в выражение функции .

Выражение вида

(28)

позволяет приводить операцию поглощения (вычеркиваются все члены, поглощаемые z; z поглощает z·x).

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

(29)

выглядит следующим образом:

- получение сокращенной формы ФАЛ из (29) сводится применению операции склеиваниячленов СДНФ: 1↔2, 2↔3, 4↔6, 5↔6, что приводит к формированию сокращенной формы логического выражения заданной функции простыми импликантами (члены сокращенной формы ФАЛ):

(30)

- получение минимальной формы:

Переход к минимальной форме осуществляется с помощью импликантной матрицы (таблица 9), в строке которой записываются (30) сокращенные формы логического выражения (простые импликанты), а в столбцы – члены СДНФ заданной функции (29)

Таблица 9

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

Используя операцию поглощения:

- выбираем простые импликанты, которые составляют ядро минимальной формы СДНФ (ядро - импликанты, обеспечивающие проведение операции поглощения членов СДНФ исходной функции);

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

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

Рассмотренная последовательность операций сохраняется и для миниминизации совершенной конъюнктивной нормальной функции (СКНФ) по методу Квайна, но при этом нужно учесть, что несколько изменяются формы используемых соотношений (формулы 1-17):

- операция склеивания (31)

- операция поглощения . (32)

Для некоторой логической функции СКНФ, заданной аналитическим выражением

(33)

Проведя операцию склеивания членов 2↔3, 1↔7, 5↔6, 4↔10, 8↔10 получим сокращенную форму СКНФ

(34)

Операция поглощения проводится с применением импликантной матрицы (аналогичной таблице 9) с включением в строки членов матрицы (33), а в столбцы - импликантов выражения (34). Завершением задачи является структурная схема цифрового устройства, построенная на основании выражения (34).

Миниминизацию логической функции методом карт Вейча рассмотрим на примере получения минимальной конъюнктивной нормальной формы для логической функции, заданной таблицей 10

Таблица10

Совершенная конъюнктивная нормальная форма, соответствующая таблице10, имеет вид

(35)

Проведя операцию склеивания (5 ↔ 8, другие комбинации членов логической функции не удовлетворяют тождеству 31) получаем сокращенную форму СКНФ (36)

(36)

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

Таблица 11

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

Так, для первого столбца таблицы 10 (таблицы истинности) все аргументы имеют нулевое значение, а логическая функция – лог.1, т.е. выбирается сочетание аргументов (или их инверсий, обеспечивающих единичное значение):

первый столбец: - нижняя клетка в правом углу;

второй столбец - последняя клетка в третьей строке и т.д.

Заполнив клетки таблицы, соответствующие лог. 1, остальным присваиваете значение лог.0. Таким образом, карта Вейча, соответствующая таблице истинности (таблица 10), примет вид таблицы 11.

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

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

В таблице 11 приведены «внутренние» замкнутые области (I, II, V, VI, VII), а так же полученные «сворачиванием» карты в цилиндр по горизонтальной оси (IV) или вдоль вертикальной оси (III) с объединением противоположных граней.

Формирование сомножителя для каждой замкнутой области МКНФ проводится дизъюнкцией входящих в него аргументов с использованием основных тождеств:

I:

II:

III: , откуда ;

IV: , отсюда ;

V: ;

VI:

VII:

Минимальная конъюнктивная форма логической функции принимает вид:

(37)

После склеивания первого и третьего членов ФАЛ (37) МКНФ принимает вид:

(38)

Результатом, завершающим выполнение задачи, является построение структурной схемы цифрового устройства на основе логического выражения (38).

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

4. Цифровая схема, соответствующая минимальной форме логической функции, строится с применением обозначений логических элементов (таблица 4) по аналогии с рис.1.