63702 (695430), страница 2

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

Текст из файла (страница 2)

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

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

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

Базис, включающий только один тип логических элементов, называется универсальным. Универсальный базис образуют, например, логические элементы И-НЕ. Двухвходовый элемент И-НЕ выполняет логическую операцию . Универсальность элемента доказывается тем, что все три функции НЕ, И, ИЛИ основного базиса могут быть выражены через функцию И-НЕ:

Элементы ИЛИ-НЕ, выполняющие операцию , также являются универсальными. Операции НЕ, И, ИЛИ выражаются через операцию ИЛИ-НЕ следующим образом:

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

получение структурной формулы в простейшей (минимальной) нормальной форме (МНФ); 2) преобразование МНФ к заданному логическому базису.

5. Минимизация переключательных функций с помощью карт Карно

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

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

Введем понятие подкуба, которое используется в теории ПФ и их минимизации. Подкуб – это совокупность 2ⁱ соседних клеток карты Карно, заполненных единицами (нулями), для которых по крайней мере одна переменная в координатах всех этих 2ⁱ клеток имеет неодинаковые значения (0 и 1). Из определения следует, что подкуб могут образовать 2, 4, 8, 16 и т.д. соседних клетки карты.

Каждый 2ⁱ-клеточный подкуб позволяет при минимизации исключить i переменных – 1,2,3,4 и т.д. Действительно, подкуб, состоящий из двух клеток, соседних по горизонтали или вертикали (рис.2,а,б,в,г) характеризуется тем, что координаты его клеток различаются значением одной переменной, а остальные переменные имеют одинаковое значение.

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

Все минтермы (макстермы), вошедшие в подкуб, склеиваются за один прием. Результатом склеивания таких клеток является получение конъюнктивного терма (если склеиваются единичные клетки) или дизъюнктивного терма (если склеиваются нулевые клетки).

Контерм (конъюнктивный терм) – результат склеивания соседних минтермов, входящих в подкуб (соседних единичных клеток). В алгебраическом представлении контерм - есть конъюнкция переменных, имеющих неизменное значение в координатах строк и столбцов всех объединяемых клеток; если неизменное значение переменной в координатах равно 1, то в конъюнкции она записывается без инверсии, если равна 0 – то с инверсией.

На рис.2,а,б,в приведены примеры записи контермов для двухклеточных подкубов, а на рис.3,а,б,в,г,д – четырехклеточных ( ) и восьмиклеточных ( ).

МДНФ – есть дизъюнкция контермов.

Пример: МДНФ для ПФ y₉ (рис.3,е) как результат минимизации по единичным значениям функции имеет вид:

. (5)

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

Для ПФ y₉ (рис.3,ж) построенные подкубы имеют следующие дизтермы:

МКНФ – есть конъюнкция дизтермов.

Пример: МКНФ для ПФ y₉ (рис.3,ж) как результат минимизации по нулевым значениям функции имеет вид:

( ) ( ) ( ). (6)

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

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

- прямоугольные области карты Карно, составляющие подкубы, могут состоять из 1, 2, 4, 8, 16 и т.д. только единичных клеток (при получении МДНФ) или только нулевых клеток (при получении МКНФ);

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

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

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

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

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

, (7)

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

6. Нормальные формы логических уравнений. Преобразование логических уравнений к заданному базису

Если при проектировании логических схем предъявляется требование получения максимального быстродействия, логическая схема строится на основе представления ПФ в нормальной алгебраической форме.

Всего существует 8 нормальных форм представления ПФ. Получим их на примере проектирования мажоритарной логической схемы (мажоритарного элементы) “2 из 3”, пронумеруем и дадим символьное обозначение путем указания операций первого и второго этапов логического преобразования.

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

= 1) И / ИЛИ

= 2) И-НЕ / И-НЕ

= 3) ИЛИ / И-НЕ

. 4) ИЛИ-НЕ / ИЛИ

5) ИЛИ / И

= =

= = 6) ИЛИ-НЕ / ИЛИ-НЕ

= =7) И / ИЛИ-НЕ

= .8) И-НЕ / И

При проектировании логических схем в зависимости от наличия определенного типа элементов (базиса) используется соответствующая нормальная форма.

7. Скобочные формы логических уравнений

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

y = x₃ x₂ x₁ x₃ x₂ x₀ x₃ x₁ x₀ .(8)

Этой функции соответствует логическая схема второго порядка, показанная на рис.6,б. На основании законов дистрибутивности функцию (8) можно представить в форме

y = x₃ [ x₂ ( x₁ x₀ ) x₁ x₀ ],(9)

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

Положительное свойство таких схем – меньшая сложность (аппаратные затраты) и стоимость.

Характеристики

Список файлов реферата