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

Минимизация логических функций

Минимизация логических функций — это упрощение логического выражения с целью уменьшения аппаратур­ных затрат при технической реализации цифрового уст­ройства.

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

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

В программируемых логических интегральных схемах ПЛИС жестко задана внутренняя логическая структура. Целью минимизации ПЛИС является сокращение числа конъюнкций, поиск минимальных дизъюнктивных форм.

Но требование уменьшения числа логических элемен­тов остается актуальным. С одной стороны, для создания комбинационных устройств невысокой сложности. С другой стороны БИС и СБИС на основе базовых матричных кристаллов имеют отдельные нескоммутированные ЛЭ. Число этих элементов фиксировано, обусловлено техно­логическими условиями. Уменьшение числа задействован­ных логических элементов позволяет расширить функци­ональные возможности, увеличить число решаемых задач, повысить надежность цифровой аппаратуры.

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

Упрощение по стандартным алгоритмам позволяет по­высить эффективность минимизации, применять машин­ные методы автоматического проектирования.

Исходным для проведения минимизации является за­данное функционирование комбинационного устройства в какой-либо форме. Чаще в виде таблицы истинности.

Источник

Минимизация логических схем

Составление логических выражений по таблице истинности

Каноническая сумма минтермов

Для примера, представленного на рис. 1.6, каноническая сумма минтермов будет выглядеть так:

( 2.1)

Из сравнения (1.1) и (2.1) видно, что одной и той же таблице истинности (рис. 1.6,б) соответствуют два разных логических выражения, причем (1.1) записывается более компактно, но возможности минимизации для него еще есть. Следовательно, есть возможность минимизировать и логическую схему, представленную на рис. 1.6, a.

Минимизация с помощью карт Карно

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

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

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

Пример 1. Написать минимальное выражение для таблицы истинности, представленной на рис. 2.5,а и нарисовать по нему логическую схему.

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

Первый контур охватывает четыре единицы, ему соответствует сумма минтермов: , в которой не изменяется только переменная . Второй контур охватывает две единицы. Ему соответствует сумма минтермов , в которой переменная принимает оба возможных значения, а произведение остается неизменным. Таким образом, получаем минимальное выражение:

( 2.2)

Ему соответствует логическая схема на рис. 2.5,г.

Для сравнения запишем максимальное выражение:

( 2.3)

Разница между (2.2) и (2.3) очевидна и в комментариях не нуждается, за исключением того, что схема, реализованная по (2.3), будет на порядок сложнее и, соответственно, менее надежна, чем схема, показанная на рис. 2.5,г.

Пример 2. Написать минимальное выражение для таблицы истинности, представленной на рис. 2.6,а, и нарисовать по нему логическую схему.

Источник

Минимизация логических функций

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

· Выполнять минимизацию функций с помощью карт Карно.

Метод непосредственных преобразований

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

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

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

Например, логическую функцию

в виде СДНФ, можно минимизировать следующим образом:

1. Добавим к данной функции слагаемое , которое уже есть в данной функции, используя правило х+х=х

2. Применим метод склеивания одинаково подчеркнутых элементарных конъюнкций

3. Применим метод склеивания для двух последних элементарных конъюнкций

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

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

Карты Карно

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

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

Карта Карно — это графическое представление таблицы истинности логических функций. Она представляет собой таблицу, содержащую по 2 n прямоугольных ячеек, где n — число логических переменных.

Например, карта Карно для функции четырех переменных имеет 2 4 = 16 ячеек.

Структура карты Карно для функций двух переменных показана на рисунке 2.2. 2

а) таблица истинности; б) структура карты Карно

На рисунке 2.3 представлена структура карты Карно для функции трёх переменных.

а) таблица истинности; б) структура карты Карно

Карта размечается системой координат, соответствующих значениям входных переменных. Например, верхняя строка карты для функции трех переменных (рисунок 2.3) соответствует нулевому значению переменной x1, а нижняя — ее единичному значению.

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

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

Обратим внимание на то, что координаты строк и столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00, 01, 11, 10. Изменение порядка следования наборов сделано для того, чтобы соседние наборы были соседними, т.е. отличались значением только одной переменной.

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

Процесс минимизации рассмотрим на примере, представленном на рисунке 2.4.

а) таблица истинности; б) карта Карно

Сначала формируем прямоугольники, содержащие по 2k ячеек, где k — целое число.

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

Например, на рисунке 2.4,б объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором переменная x1 изменяет свое значение. Следовательно, она исчезнет при склеивании соответствующих элементарных произведений и останутся только х2 и х3, причем переменную х2 берем в инверсном виде, т.к. она равна 0.

Ячейки, расположенные в первой строке (рисунок 2.4 б), содержат единицы и являются соседними. Поэтому все они объединяются в прямоугольник, содержащий 2 2 = 4 ячейки.

Переменные х2 и х3 в пределах прямоугольника меняют свое значение; следовательно, они исчезнут из результирующего элементарного произведения. Переменная х1 остается неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки рисунка 2.4 б, содержит лишь один х1, который берем в инверсном виде, т.к. он равен 0.

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

Двум ячейкам сторого столбца соответствует сумма двух произведений

Функция, соответствующая рисунку 2.4 имеет вид:

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

Итак, можно сделать следующие выводы:

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

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

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

а) б) в)

Функция, соответствующая покрытию, показанному на рисунке 2.5 а, имеет вид:

.

Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты Карно как бы «склеиваются», образуя поверхность цилиндра. При склеивании боковых границ получается тороидальная поверхность. Следуя изложенным рассуждениям, устанавливаем, что ячейки с координатами 1011 и 0011, изображенные на рисунке 2.5 б, являются соседними и объединяются в прямоугольник. Действительно, указанным ячейкам соответствует сумма элементарных произведений

Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем элементарное произведение .

Окончательно функция, соответствующая покрытию, изображенному на рисунке 2.5 б, имеет вид

Карта Карно, показанная на рисунке 2.5 в, содержит единичные ячейки, расположенные по углам. Все четыре ячейки являются соседними, и после объединения дадут элементарное произведение

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

1. Изображается таблица для n переменных и производится разметка ее сторон.

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

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

4. Одни и те же ячейки с единицами могут входить в разные контуры.

5. Количество прямоугольников должно быть минимальным, а площадь прямоугольников максимальная.

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

7. Полученные произведения соединяем знаком логического сложения.

Контрольные вопросы:

1. Что называют минтермами и минтермами?

2.Записать функции, заданные таблицами 2.9 и 2.10 в СДНФ и СКНФ.

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

a)

b)

c)

d)

e)

f)

Логические элементы

· Таблицы логических состояний для основных функциональных логических схем;

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

· Определять логические состояния на выходах цифровых схем по известным состояниям на входах;

· Выполнять логическое проектирование в базисах микросхем;

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

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

Логическое действие осуществляется как с одной (одновходовый логический элемент) так и с множеством (многовходовый логический элемент) входных переменных.

При работе логических устройств используются три основных действия согласно алгебры Буля – «И», «ИЛИ», «НЕ».

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

Источник

Минимизация логических функций

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

Существует несколько методов минимизации логических функций:

-метод непосредственных преобразований;

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

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

х2		х2
х1	х1
	х3

х2
	х3

Рисунок 5.6 – Примеры диаграмм Вейча

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

При склеивании переменных нужно руководствоваться следующими правилами:

б) в контуры можно объединять только соседние клетки, которые содержат единицы (нули). Соседними (рядом расположенными) считаются, в том числе, клетки, расположенные на противоположных сторонах диаграммы (в противоположных строках или столбцах);

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

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

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

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

Для получения по диаграмме Вейча минимального выражения логической функции следует руководствоваться правилом: единицы и нули должны объединяться минимальным числом наибольших контуров.

Рассмотрим пример минимизации логической функции трех переменных у = f(x₁, x₂, x₃), заданной таблицей истинности (рисунок 5.5), воспользовавшись методом Карно-Вейча. Для начала воспользуемся представлением функции в дизъюнктивной нормальной форме. В этом случае диаграмма Вейча должна быть заполнена, как показано на рисунке 5.7.

Рисунок 5.7 – Минимизация функции к виду ДНФ

Из рисунка 5.7 видно, как можно наилучшим образом объединить единицы в единичные контуры. При этом в контуры могут входить и ячейки с номерами запрещенных наборов (то есть элементами которых являются «*»). В результате такого объединения получим тупиковую форму логической функции в виде дизъюнкции конъюнкций (число которых равно числу единичных контуров) входных переменных, которые не склеились:

. (5.3)

Если для представления логической функции после минимизации выбрана конъюнктивная нормальная форма, то в диаграмме Вейча объединяют нули в нулевые контуры. Как и в предыдущем случае, в нулевые контуры могут быть включены ячейки, элементами которых являются «*» (рисунок 5.8).

Рисунок 5.8 – Минимизация функции к виду КНФ

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

. (5.4)

Выражения (5.3) и (5.4) описывают структуру логического устройства, алгоритм функционирования которого задан функцией у (рисунок 5.5). Несмотря на то, что полученные выражения разные по виду, а, следовательно, и схема логического устройства в каждом случае будет выполнена по разному, сигналы на выходах этих схем на одних и тех же номерах разрешенных наборов входных переменных будут одинаковы.

Источник