Основные понятия минимизации булевых функций

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

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

x ₁(x ₂ x ₃) = (x ₁ x ₂) x ₃; x ₁ (x ₂ x ₃) = (x ₁ x ₂) x ₃

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

x ₁ x ₂ = x ₂ x ₁; x ₁ x ₂ = x ₂ x ₁

- распределительный (дистрибутивный)

x ₁(x ₂ x ₃) = x ₁ x ₂ x ₁ x ₃

x ₁ (x ₂ x ₃) = (x ₁ x ₂)(x ₁ x ₃).

На основании этих законов можно выносить переменные за скобки, пере­ставлять местами и т.д., как и в обычной алгебре. Но только для алгебры логики действует закон двойственности (правило де Моргана):

.

Законы двойственности обобщены К. Шенноном для любых булевых функ­ций (ФАЛ):

.

Такая запись обозначает тот факт, что отрицание над записью всей функции приводит к отрицанию значения переменных и знаков, их соединяющих, т.е. дизъюнкция () заменяется знаком конъюнкции (), и наоборот.

Пример:

(*)

Заметим, что в первоначальную запись функции (*) можно значительно уп­ростить. Действительно, вынесем за скобки , тогда получим:

Из законов алгебры логики следуют следующие очевидные соотношения:

1 + x = 1, 1· x = x, x + = 1. 0· x = 0, x·x = x, x · = 0, 0 + x = x, x + x = x.

Использование этих законов позволяет упрощать исходную запись ФАЛ. Вернемся к анализу ФАЛ, представленной в таблице 5.

В первой исходной записи ФАЛ, полученной по таблице 5, в каждом логиче­ском произведении переменных (конъюнкция) присутствовали все переменные из набора x ₁ x ₂ x ₃ x ₄, а сами конъюнкции соединены символом логического сложения (дизъюнкции). Такая форма записи ФАЛ называется совершенной дизъюнктивной нормаль­ной формой (СДНФ).

Если не все переменные из набора x ₁ x ₂ x ₃ x ₄ представлены в каждой из конъ­юнкций, то такая форма по прежнему остается нормальной дизъюнктивной фор­мой, но она не относится к классу совершенных. Дизъюнктивных нормальных форм представления одной и той же ФАЛ может быть много, но совершенная ДНФ (СДНФ) одна единственная. Кроме СДНФ существует так называемая конъюнктивная нормальная форма, которая также может быть совершенной (СКНФ) и не совершенной, т.е. просто КНФ. КНФ представляет собой алгебраи­ческое выражение в виде стольких конъюнктивных членов, представляющих со­бой дизъюнкции всех переменных, при скольких наборах значений переменных функция равна 0. Если в наборе значение переменной равно 1, в дизъюнкцию входит инверсия этой переменной. Например, для табл. 5 получим:

.

Анализ СДНФ и СКНФ показывает неэкономичность записи ФАЛ. Исполь­зуя свойства ФАЛ можно преобразовать выражения за счет так называемой опе­рации склеивания, т.е.

, т.к. .

,

где a – любая ФАЛ.

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

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

В табл. 11 представлена ФАЛ, для которой СДНФ имеет вид:

.

В таблице 11 значение х ₁ = 1 распространяется на столбцы 2 и 3, считая справа налево, а значение х ₂ = 1 – на столбцы 1 и 2. Аналогично черточка х ₃ = 3 относится к нижней строке таблицы (матрицы).

В таблице 11 введены уровни симметрии по столбцам и строкам. Нулевой (0) уровень делит матрицу пополам, единичные уровни (1) делят каждую область строк или столбцов еще раз пополам. Как видно, по строкам только один нулевой (0) уровень симметрии, а по столбцам их 2.

Таблица 11

Для минимизации все клетки, содержащие 1, объединяются в замкнутые об­ласти с числом клеток 2, 4, 8… (в зависимости от числа переменных в ФАЛ). Области могут пересекаться, и одни и те же клетки могут входить в разные об­ласти. «Соседними» являются не только клетки, расположенные рядом по горизонтали и вертикали, но и клетки, находящиеся на противоположных гра­ницах карты. При охвате клеток замкнутыми областями следует стремиться к ми­нимальному числу областей.

Для табл. 11 получим:

.

Одним из вариантов карты Карно является представление кодирования бу­лева пространства кодом Грея, в котором при переходе от клетки к клетке как по вертикали, так и по горизонтали меняется значение только одной переменной.

Такое представление хорошо воспринимается визуально благодаря симмет­рии по осям. В данном случае это оси «0–0» и «1–1». Эта симметрия позволяет легче находить области склеивания конституент, для которых значения какой-либо переменной x_i не влияет на значение ФАЛ. Речь идет о «ручной» минимизации с использованием визуального восприятия, что эффективно при n ≤ 6.

Действительно, для верхней области, охватывающей две 1 при , видно, что значение x ₂ несущественно, т.к. ФАЛ равна 1 как при x ₂, так и при , но обе 1 в булевом пространстве при лежат в области x ₁. Аналогично для значения x₃ не существенно значение x ₁, но обе 1 соответствуют x ₂.

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

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

Соседними между собой являются также крайние левые клетки карты с крайними правыми и крайние верхние клетки карты с крайними нижними (как если бы карты были свернуты в цилиндры по вертикали и горизонтали).

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

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

- для каждой клетки, в которой функция имеет значение 1, записывается конъ­юнкция всех входных переменных (прямых или инверсных);

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

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

1. Все единицы (при записи функции в дизъюнктивной форме) и все нули (при за­писи функции в конъюнктивной форме) должны быть заключены в прямо­угольные контуры. Единичные контуры могут объединять несколько единиц, но не должны содержать внутри себя нулей. Нулевые контуры могут объединять не­сколько нулей, но не должны содержать внутри себя единиц. Одноименные кон­туры могут накла­дываться друг на друга, т.е. одна и та же единица (или нуль) мо­жет входить в не­сколько единичных (нулевых) контуров.

2. Площадь любого контура должна быть симметричной относительно гра­ниц пе­ременных, пересекаемых данным контуром. Другими словами, число кле­ток в контуре должно быть равно 2 ⁿ, где п = 0, 1, 2, 3, 4,..., т.е. число клеток вы­ражается числами 1, 2, 4, 8, 16, 32, ….

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

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

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

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

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

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

Рассмотрим пример ФАЛ для шести переменных (табл. 12). Все области 1, объединенные двойными линиями, представляют один интервал ФАЛ, для кото­рого по горизонтали очевидна независимость от x ₁ и x ₃, а по вертикали от x ₄ и x ₆, т.е. весь интервал соответствует . Верхняя область, объединенная сплошным овалом в одну линию по горизонтали, соответствует x ₂ x ₃, а по вертикали , т.е. , а нижняя соответствует , тогда получим:

.

Последняя запись в скобках для х ₃ и х ₆ как уже говорилось называется функ­цией (обозначим Ζ) суммы по модулю 2 и обозначаются символом . Другое назва­ние функции Ζ – функция неравнозначности, т.к. она принимает значение 1 только при различных значениях переменных.

.

Таблица 12

Заметим, что обратная ей функция имеет вид:

.

Эта функция называется функцией тождественности, т.к. она принимает зна­чение 1 только при одинаковых (тождественных «0» и «1») значениях перемен­ных

.

Тогда выражение для y можно записать в виде

.

Существуют функции, значение которых неопределенно на некоторых наборах входных переменных, т.е. некая комбинация, например , не может быть реализована. Практических примеров таких булевых функций много, особенно для реальных технологических процессов. Все такие комбинации переменных также наносятся на карту Карно и отмечаются символом, отличающимся от символа «0» или «1», с целью получения минимальной формы булевых функций Такие булевы функции называются не полностью определенными*.

КОМБИНАЦИОННЫЙ ПРЕОБРАЗОВАТЕЛЬ ИНФОРМАЦИИ

РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

ОБРАБОТКИ СИГНАЛОВ

Распределенные микропроцессорные системы с явно выделенными ло­гиче­скими преобразователями информации (ЛПИ) позволяют обеспе­чить параллель­ность и высокую скорость обработки информации, что очень важно в задачах ре­ального времени, быстрых алгоритмах обработки сигна­лов и др.

Организация ЛПИ в виде параллельно организованной структуры позво­ляет вычислять наиболее сложные операции (типа умножения) за ог­раниченное число тактов. Метод построения ЛПИ для реализации опера­ции умножения при числе разрядов п ≤8 сводится к представлению произ­ведения С = А∙Вв виде раз­но­сти квадратов:

, (2)

где R = A + B, P = A – B.

Логическое выражение для R² и Р²находится методом прямого счи­ты­вания из ПЗУ или через комбинационные схемы с использованием ми­нимизации бу­левых функций по картам Карно для каждого q_i разряда квадратора. Квадратор – это устройство, определяющее величину x в степени 2, если x задано в виде кода.

Такой традиционный путь синтеза возможен для небольших значений п (n ≤ 8), но уже при n > 6 этот путь синтеза затруднен, т.к. требует умения про­во­дить проце­дуру минимизации по картам Карно большой размерности, а число таких карт равно 2∙ n.

Поэтому более предпочтительным может оказаться аналитический спо­соб получения минимальных выражений для соответствующих разря­дов преобразова­телей. Этот способ учитывает особенности операции воз­веде­ния в квадрат на ос­нове применения вертикальной процедуры обра­ботки информации [29].

Рассмотрим первый способ минимизации на примере синте­за структуры че­тырехразрядного квадратора (синтез на основе карт Карно).

В этом случае расположим все восемь карт Карно для четырех входных переменных в соответствии с весом выходной переменной y_i (табл. 13). При возведении в квадрат число выходных переменных необходимо взять в 2 раза больше. Для каждой карты по горизонтали закодированы все комбинации х₁х₀: 00, 01, 11, 10, а по вертикали – х₃х₂. Для кодирования применен код Грея.

Заполним эти карты в соответствии со значениями чисел у = х² при
изменении х в диапазоне от 0 до 15. Тогда получим следующие комбина­ции рас­положения единиц и нулей на картах Карно (табл. 13).

Проводя минимизацию по картам Карно, получим минимальные выражения для y_i:

y ₀ = x ₀; y ₁ = 0; y ₂ = ; y ₃ = ;

у ₄ = ; (3)

у ₅ = ;

y ₆ = ;

y ₇ = x ₃∙ x ₂.

Таблица 13

Представление чисел у = х ²на картах Карно

yi

y 7

y 6

y 5

y 4

y 3

y 2

y 1

y 0

Теперь с учетом выражений (3) получим структуру комбинационного квадра­тора (рис. 11), которая в виде единого блока изображена на рис. 12.

Функциональные и логические преобразователи

дискретной автоматики

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

Рис. 11. Структура квадратора

x3

Рис. 12. Квадратор

Если на наборе x_n, x_{n- 1}, …, x ₂, x ₁ двоичных переменных задана система буле­вых функций y ₁, y ₂, …, y_m, которую обобщенно обозначим символом F, то она мо­жет быть реализована неким устройством (рис. 13), которое называется «черным ящиком», так как структурная организация его не известна. Поскольку x_i, y_j {0,1}, то реализация такого устройства называется комбинационной схемой, т.к. для конкретного значения набора x_i, (который называется комбинацией) оп­реде­лено значение y_j, .

Рис. 13

Простейшей реализацией комбинационной схемы F является постоянное за­поминающее устройство (ПЗУ), тогда y₁, y₂, …, y_m – значения на выходных «клем­мах» ПЗУ или коды соответствия x ₁, x ₂, x ₃, …, x_n y ₁, y ₂, …, y_m, которые «записаны» в числовой блок ПЗУ как константы, где x ₁, x ₂, x ₃, …, x_n – адрес ПЗУ.

Модель «черного ящика» является простейшей системообразующей моде­лью для представления устройств, т.к. она позволяет на основе изучения объекта управления найти это соответствие, т.е. формализованное правило преоб­разова­ния { x }→{ y }.

В задачах проектирования и определения структурной организации автомата модель «черного ящика» оказывается полезной в двух случаях:

1) Функция системы управления действительно может быть выражена ав­томатом с одним внутренним состоянием. Тогда другие структурные модели не требуются, и детальное проектирование связано лишь с определением па­раметри­ческих характеристик (объем памяти, число каскадов и др.) струк­туры ВПИ.

2) Функция системы более сложна, не может быть сведена к функции ав­то­мата с одним состоянием, но анализ по модели «черного ящика» позволяет полностью уточнить все входы и выходы, уяснить требуемую форму представле­ния входных и выходных сигналов, разрядность представления сиг­налов по вхо­дам и выходам.

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

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