Как перейти к базису и не

Универсальные базисы

Логические функции «И-НЕ» (функция Шеффера) и «ИЛИ-HE» (функция Пирса) занимают особое положение в цифровой технике и называются универсальными базисами (так же как и элементы, их реализующие). Причина заключается в следующем: цифровое устройство, выполняющее любую логическую функцию, можно построить, имея элементы только одного вида («ИЛИ-HE» либо «И-НЕ»). При интегральной технологии с точки зрения надежности и стоимости использование однотипных элементов весьма предпочтительно.

Операции «ИЛИ-HE», «И-НЕ»

Операция «ИЛИ-HE» математически обозначается стрелкой «1» (стрелка Пирса) и для функции двух переменных записывается так:

Операция «И-НЕ» изображается значком штрих «|» (штрих Шеффера), и согласно определению в случае двух аргументов для нее применяется запись

На рис. 18.5, а, б даны таблицы истинности и условные изображения соответствующих элементов на структурных схемах.

Рис. 18.5. Условные изображения и таблицы истинности элементов, выполняющих логические операции: «ИЛИ-HE» (я); «И-НЕ» (б)

Универсальность функций «ИЛИ-HE» и «И-НЕ»

Обоснованием универсального характера функций Пирса и Шеффера являются алгебраические выражения, связывающие простейшие логические действия (сложение, умножение и инверсию) с любой из этих функций. Их несложно получить при помощи законов алгебры логики (и прежде всего закона де Моргана). Эти соотношения (включая краткий вывод) помещены в табл. 18.6 и 18.7, там же изображены функциональные схемы, выполняющие логические действия «ИЛИ», «И», «НЕ», построенные на однотипных универсальных базисах.

Таблица 18.6

Реализация простейших логических операций «НЕ», «ИЛИ», «И» в универсальном базисе «ИЛИ-НЕ»

Таблица 18.7

Реализация простейших логических операций «НЕ», «ИЛИ», «И» в универсальном базисе «И-НЕ»

8. Приведение логической функции к заданному базису

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

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

8.1 Приведение логической функции к базису и-не.

Для приведения ЛФ из базиса И, ИЛИ, НЕ в базис И-НЕ используют закон двойного отрицания.

Сначала выполняются операции И-НЕ на минтермах C 1 _iF(A_i), а затем операция И-НЕ над результатами.

Пример приведения ЛФ к базису И-НЕ.

Функция представлена в виде карты Карно.

Результат минимизации в базисе И, ИЛИ, НЕ и перевод в базис И-НЕ:

; ;.

Рис.29. Схема в базисе И, ИЛИ, НЕ. Рис.30. Схема в базисе И-НЕ.

8.2. Преобразование лф к базису или-не

За основу следует взять СКНФ ЛФ и использовать закон двойного отрицания.

Сначала выполняют операцию ИЛИ-НЕ на макстермах [CiF(Ai)], а затем операция ИЛИ-НЕ над результатом.

Как и СДНФ, СКНФ сначала следует минимизировать. Практическая последовательность получения минимальной КНФ может быть следующей: __

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

б) инвертируя выражение функции и применяя правило де Моргана, получаем минимальную КНФ.

Рис.31. Пример логической

(для сравнения функция та же,

что и для преобразования в базис И-НЕ).

а) F = X1X3 + X2X3 + X2X3X4;

б) приводим к конъюктивной нормальной форме:

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

Подвергая МКНФ двойной инверсии и используя правило де Моргана, приводим ЛФ к базису ИЛИ-НЕ. Для рассмотренного примера МКНФ в базисе ИЛИ-НЕ:

Рис.32. Схема в базисе И, ИЛИ, НЕ. Рис.33. Схема в базисе ИЛИ-НЕ.

В результате мы получили четыре варианта реализации логической функции: а) конъюктивная форма в базисе И, ИЛИ, НЕ (рис.29); б) дизъюнктивная форма в базисе И, ИЛИ, НЕ (рис.32); в) в базисе И-НЕ (рис.30); г) в базисе ИЛИ-НЕ (рис.33).

9. Минимизация логических функций с несколькими выходами

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

В качестве примера минимизации ЛФ с несколькими функциями рассмотрим синтез преобразователя кода 8421 в код 2421.

Обозначим входные переменные, соответствующие отдельным разрядам кода 8421,- Х4,Х3,Х2,Х1, а выходные переменные кода 2421 — Y4,Y3,Y2,Y1.

Как перейти к базису и не

Вследствие функциональной полноты функций Шеффера и стрелки Пирса (см табл 2 2) реализующие их вентили или ИЛИ—НЕ могут представлять любую булеву операцию И, ИЛИ, НЕ и таким образом самостоятельно образовать базис, в котором реализуется логическая функция. Это целесообразно с двух точек зрения. Во-первых, при проектировании логических схем можно обойтись одним единственным типом вентиля, что позволяет предельно унифицировать эгот процесс. Во-вторых, для большинства серий ТТЛ- и КМОП-логик вентиль , как и ИЛИ—НЕ, является базисным и предпочтителен во многих отношениях. Вследствие этого реализация логических схем в базисах и ИЛИ—НЕ получила широкое распространение в практике.

Булевы операции И, ИЛИ, НЕ штрих Шеффера соотношениями .

Отсюда следует, что вентиль , таблица соответствия которого дана на рис. 3.7,а, эквивалентен вентилю НЕ—ИЛИ (см. табл. 3.1) и позволяет — реализовать булевы операции, как показано на рис. . Для реализации инверсии имеются два варианта: либо на все входы вентиля подается переменная . либо на все входы, кроме входа , подается единица. Обычно эти особенности на схемах отсутствуют и используется упрощенное представление с одним входом (рис. ).

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

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

В случае произвольных многоступенчатых схем сначала преобразуются по изложенному выше правилу соседние уровни И—ИЛИ, а остальные вентили И и ИЛИ заменяются их эквивалентами в базисе (рис. 3.7). В качестве примера на рис. 3.9,а показана схема, полученная в результате такого преобразования из схемы рис. 3.6,в.

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

Как видно из рассмотренных примеров, переход к базису

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

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

На рис. 3.11, дуальном рис. 3.8, показан переход от двухуровневой схемы ИЛИ/И, которая соответствует конъюнктивной нормальной форме , к реализации в базисе ИЛИ—НЕ. Здесь исходная схема (рис. 3.11,а) преобразуется так, что можно устранить последовательно включенные пары инверторов (рис. ). После этого получаем схему (рис. 3.11,в), которая по своей структуре полностью совпадает с исходной.

На рис. , б показаны две эквивалентные реализации в базисе ИЛИ—НЕ функции, заданной в нормальной и преобразованной формах.