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

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.

Переход к базису или-не

Переход к базису ИЛИ-НЕ
Проверьте пожалуйста, правильно ли я перешел к базису ИЛИ-НЕ?

Переход к базису И,НЕ. ( проверить )
Проверьте, пожалуйста, правильно ли выполнил переход к базису И,НЕ.

Переход к базису штрих Шеффера, 8 переменных
Добрый день,подскажите,как дальше сделать переход к базису Шеффера? .

Переход от карт карно к базису пирса
Для примера имеется карта 4х4.Как мне перейти от карты сразу к базису пирса, не используя.

Пример проектирования цифрового устройства «на пальцах»

Привет, Хабр! Это начало небольшого цикла из двух статей с пошаговым проектированием цифрового устройства с уклоном на практику. Минимум «воды» и максимум практики!

Для начала работы возьмем следующие выходные параметры: 0000110001110001

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

Инструменты, материалы и прочее:

• Electronics Workbench
• Линейка, ручка и листок (для общих расчетов)
• Базовые знания дискретной математики, цифровой схемотехники и принципа работы представленных программ
• Условное графическое обозначение микросхем 7404 (аналог К155ЛН1), 7410 (аналог К155ЛА4), 7410 (аналог К155ЛА4) и 7420 (аналог К155ЛА1)
• Фактическое изображение микросхем 7404 (аналог К155ЛН1), 7410 (аналог К155ЛА4), 7410 (аналог К155ЛА4) и 7420 (аналог К155ЛА1)

Начало работы

1. Построение таблицы истинности и нахождение совершенной дизъюнктивной нормальной формы (СДНФ)

Первым делом необходимо составить таблицу истинности по формуле

где N – количество возможных вариантов, а i – количество выходных сигналов.

В представленном случае это будет выглядеть так:

На основе полученных данных можно перейти к построению таблицы истинности. Для наглядности входные сигналы были обозначены как A, B, C и D, выходной как F.

После построения таблицы истинности можно приступать к получению СДНФ. Это выполняется в два шага:

1. Выделяются строчки таблицы истинности, в которых F=1.
2. Выписывается конъюнкция переменных у всех выделенных строк по следующей формуле: если значение переменной равно 1, то в конъюнкцию включается сама переменная. Если значение равно 0, то включается отрицание переменной. Полученные конъюнкции нужно связать в дизъюнкцию.

2. Создание карты Карно, минимизация и приведение к базису И-НЕ

Полученную СДНФ необходимо сократить при помощи карт Карно.

Три шага для построения карт Карно:

1. так как используются четыре переменные (A, B, C и D), то строится таблица 5×5 клеток;
2. таблица заполняется на основе «координат» из таблицы истинности (из строк, в которых F=1) или СДНФ (суть одна. Просто кому как удобнее);
3. в заключение смежные клетки объединяются в группы. Группы не должны содержать нули. Группы должны быть кратны двум. Группы могут пересекаться.

Следующее действие — минимизация полученных групп. Общий принцип можно свести к следующему:
Если 11 — значение не меняется;
Если 00 — присваивается отрицание;
Если 01 (или 10) — вычеркивается.

Полученные произведения связываются в дизъюнкцию:

После чего составленное выражение приводится к базису И-НЕ при помощи закона де Моргана (отрицание конъюнкции есть дизъюнкция отрицаний, отрицание дизъюнкции есть конъюнкция отрицаний):

Обратите внимание на изменения — появилось двойное отрицание (по одной на «группу» и одно общее) и изменились знаки.

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

Пример логической схемы:

3. Электронная схема на основе логических элементов

Основные расчеты завершены. Теперь можно отложить листок с ручкой и линейкой. Переходим в Electronics Workbench.

В данном случае этот этап выступает «промежуточным» и упрощает процесс перехода от выражения в базисе И-НЕ к электронной схеме на основе микросхем.

1 — Питание;
2 — Переключатели, используемые для подачи сигналов;
3 — Индикаторы (применяются для наглядной проверки работоспособности);
4 — Логические элементы типа «НЕ»;
5 — Логические элементы типа «3И-НЕ»;
6 — Логический элемент типа «4И-НЕ»;
7 — Заземление.

Как можно заметить, логические элементы электронной схемы внешне отличаются от тех, что были представлены ранее (в логической схеме). Это связано с тем, что в Electronics Workbench условное графическое обозначение логических элементов выполнено по стандартам ANSI, тогда как показанная ранее логическая схема была выполнена в соответствии ГОСТ 2.743-91.

Работоспособность электронной схемы проверяется по таблице истинности. Для этого нужно нажать кнопку запуска

и начать производить переключения, проводя сравнение с таблицей истинности.

ВАЖНО: нужно проверять каждую строчку. Выборочная проверка ничего не даст.

4. Электронная схема на основе микросхем

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

Как можно заметить, в полученной электронной схеме использовано 4 микросхемы — 7404 (аналог К155ЛН1), 7410 (аналог К155ЛА4), 7410 (аналог К155ЛА4) и 7420 (аналог К155ЛА1). Для того чтобы понять, как происходит подключение, следует обратиться к фактическому изображению микросхем.

Сначала это может показаться сложным, но со временем вы поймете, что это не так уж и трудно.
ВАЖНО: не забывайте делать проверку.

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

Логические функции «И-НЕ» (функция Шеффера) и «ИЛИ-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. Пример логической

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

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

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

Минимальную КНФ можно получить сразу из карты Карно. Проводим контуры вокруг 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,в), которая по своей структуре полностью совпадает с исходной.

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