Логических устройств

Частной задачей, возникающей на первом этапе, является доопределение значений выходных сигналов (и функций) при не оговорённых условиях. Это - задача синтеза по неполностью заданным условиям. Произвольное доопределение условий работы устройства может привести к неоправданным затратам на его создание. Поэтому названную процедуру следует выполнить при минимизации логико-математической модели устройства.

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

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

1) задача минимизации алгебраических форм функций;

2) поиск алгебраических форм неполностью определённых логических функций.

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

В общем случае задача минимизации формулируется следующим образом: требуется отыскать такое алгебраическое выражение функции, в котором содержалось бы наименьшее число независимых переменных (букв) и наименьшее число логических символов. Так при минимизации функций в базисе {И, ИЛИ, НЕ} в алгебраическом (минимальном) выражении должно быть наименьшее число переменных и наименьшее число логических символов (конъюнкции, дизъюнкции и инверсии). А при минимизации функций в «смешанном» базисе, содержащем, например, кроме перечисленных символов, ещё и символ Å (суммы по mod2), также должно быть наименьшее число переменных и указанных символов.

Поиск алгебраических выражений неполностью определённых функций также многовариантная задача. В работе [5] изложен метод «неопределённых коэффициентов» для отыскания алгебраических выражений недоопределённых функций. Однако он практически непригоден для поиска выражений функций от 6 аргументов, громоздок и мало эффективен при неавтоматизированном применении («вручную»). Если же применять карты Карно для минимизации недоопределённых функций, то сложность получаемых выражений будет зависеть от степени недоопределённости и варианта доопределения. Этих же вариантов может быть очень много.

Достаточно просто указанные частные задачи решаются на основе визуально-матричного метода минимизации логических функций, основы которого изложены в работах [3, 6].

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

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

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

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

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

1. Логическая функция представляется в СДНФ. Причем, если она задана таблицей истинности, то представляют путем записи “по единицам”; если она задана алгебраической произвольной дизъюнктивной форме - путем применения операций развертывания, формул Де Моргана и др.

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

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

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

3. Находят минимальные дизъюнктивные нормальные формы (МДНФ) по импликантной матрице.

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

Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов с поглощательными ими членами СДНФ, отмечают крестиками [5].

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

Пример 4.1.Минимизировать логическую функцию:

Решение:1. Функция задана в алгебраической форме, применяя операции развертывания

получают СДНФ, содержащую шесть членов:

2. Операции склеивания проводят в следующем порядке:

1) выполняются все возможные склеивания 1-ого члена с остальными;

2) выполняются все возможные склеивания 2-ого члена с остальными, кроме 1-ого;

3) выполняются все возможные склеивания 3-ого члена с остальными, кроме 1-ого и второго и т.д.

Склеиваться могут только те члены, у которых число переменных с отрицаниями отличается на единицу.

Результаты склеивания и поглощения:

Звездочками отмечают те члены СДНФ, которые поглощаются произведениями, образовавшимися после склеивания.

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

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

3. Строят для заданной функции импликантную матрицу (табл.4.1.).

Таблица 4.1.

Простые импликанты (минтермы)	Члены СДНФ
	х	х
		х	х
			х	х
				х	х
					х	х

Для получения МДНФ необходимо найти минимальное число импликант, которые совместно накрывают крестиками все столбцы импликантной матрицы:

.

Сложность логической функции определяется числом переменных входящих в ее выражение: в заданной функции 14, в минимальной - 9.

Первый алгоритм получения минимальной конъюктивной нормальной формы (МКНФ) логической функции:

1. Логическую функцию представляют в СКНФ. Причем, если она задана таблицей истинности, то ее записывают “по нулям”; если она задана алгебраически в произвольной конъюнктивной форме, то для записи в СКНФ выполняют все возможные операции развертывания.

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

3. МКНФ находят по макстермной матрице.

Пример 4.2. Логическая функция задана таблицей истинности. Найти МКНФ этой функции.

Решение:1. Выписывают заданную функцию в СКНФ “по нулям” таблицы истинности:

2. Проводят операции склеивания и поглощения:

В данном примере поглощаются все четыре члена исходного выражения и, следовательно, СКНФ

.

4. Макстермная матрица задана табл.4.2.

Таблица 4.2.

Простые импликанты (макстермы)	Члены СКНФ
	х	х
	х			х
			х	х

5. МКНФ логической функции: .

Второй алгоритм получения МКНФ логической функции:

1. Логическая функция представляется в СДНФ заданной функцией, взятой с отрицанием.

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

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

2. Находят МДНФ по рассмотренному выше алгоритму.

3. От полученной МДНФ берут отрицание и, после преобразований по формулам Де Моргана, получают МКНФ.

Пример 4.3.Найти МКНФ, функции заданной таблицей истинности.

Решение:1. СДНФ, взятая с отрицанием:

2. Результаты склеивания и поглощения:

3. МДНФ, взятая с отрицанием:

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

.

В методе Квайна есть одно существенное неудобство, связанное с необходимостью полного по парного сравнивания минтермов на этапе построения сокращенной. ДНФ. В 1956 г. Мак - Класки предположил модернизацию первого этапа метода Квайна, дающую существенное уменьшение количества сравнений минтермов [17].

Идея метода Мак - Класки заключается в следующем. Все минтермы записываются в виде двоичных номеров, например, как 1010. Эти номера разбиваются на группы по числу единиц в номере, т. е. в i-ю группу попадают номера, имеющие в своей записи i единиц. Попарное сравнение производится только между соседними по номеру группами, т.к. минтермы, пригодные для склеивания, отличаются друг от друга только в одном разряде. При образовании минтермов с ранга выше нулевого, в разряды, соответствующие исключенным переменным, ставится тире.

Метод предусматривает следующую последовательность действий для получения сокращенной ДНФ.

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

Затем склеиваются минтермы четвертого ранга и снова склеивающиеся минтермы помечаются звездочками:

Образуются минтермы второго ранга:

Первичными (простыми) импликантами являются:

2. Расстановка меток. Для данной функции сокращенная ДНФ имеет вид:

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

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

В рассматриваемом примере исключается строка и столбцы

.

В результате получаем таблицу:

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

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

Пример 4.4. Произвести минимизацию функции, заданной таблично.

Решение. СДНФ для этой таблицы:

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

1-й и 4-й члены (результат склеивания )

2-й и 3-й члены (результат склеивания )

2-й и 4-й члены (результат склеивания )

3-й и 5-й члены (результат склеивания )

4-й и 5-й члены (результат склеивания )

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

Повторяем операции склеивания и поглощения.

Здесь операция склеивания проводится с двумя парами: и , и , и дальнейшее склеивание невозможно, это является сокращенной формой (а в данном примере и минимальной формой)

В данной функции и являются простыми импликантами