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

[1] Michael Hammer and James Campy. Reengineering the Corporation Manifesto for Business Revolution (New York: Harper Business. 1993. P.30

Основные логические элементы (обозначение, функция, реализация)

Для реализации в ТТЛ и КМОП смотри лекцию 12.

Функции описывают таблицы истинности. Словестное описание функций частично присутствует в лекции 12.

Таблица истинности для логической схемы. Определение логической функции цифровой схемы по таблице истинности.

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

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

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

Задание номер раз

Есть некий элемент с двумя входами и одним выходом, и известна его таблица истинности:

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

Внимательно смотрим и думаем…
Нас интересуют те позиции таблицы истинности, в которых выходной сигнал равен 1.

А! Вот чего мы видим: единица на входе b в любом случае приводит к единице на выходе. Здорово!

Значит, мы можем соединить вход b напрямую с выходом c … Точнее – могли бы. Но у нас есть еще одна единица на выходе – когда на оба входа поданы нули. Вспоминаем, какой элемент реагирует на два нуля? Разрешаю подглядеть в предыдущий параграф…

Правильно, элемент «ИЛИ-НЕ»! Значит, вторая единица будет формироваться элементом ИЛИ-НЕ. Давайте нарисуем для каждого случая свою схему:

Теперь надо объединить эти схемы в одну. Помним, что непосредственно соединять цифровые выходы нельзя. Значит надо их соединить через какой-то элемент. Причем, этот элемент должен выдавать единицу на выход в случае, если хотя бы на одном входе есть единица. Ну, какой это элемент?

Конечно, это «ИЛИ».

Итак:

Карты Карно.

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

На карту Карно в так называемом циклическом коде Грея заносятся минтермы. Для четырех переменных карта Карно выглядит следующим образом (рис. 1.1.):

Рис. 1.1.

На карте Карно в коде грея по горизонтали перечисляются переменные X1,X2

а по вертикали – переменные Y1,Y2.

Метод карт Карно использует одну из известных аксиом алгебры Буля:

Можно сформулировать несколько правил, основных на этой аксиоме (аксиома склеивания переменных).

Если минтермы расположены в соседних или крайних клетках строки или столбца, то ранг минтерма снижается на один порядок, а склеиванию подлежит переменная, входящая с разными показателями инверсии. На рис. 1.2. приведена карта Карно для выражения:

Рис.1.2.

Данное выражение минимизируется и равно:

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

4. Основные тождества и аксиомы алгебры логики (правила де Моргана, законы коммутативности и ассоциативности)

Аксиомы

, инволютивность отрицания, закон снятия двойного отрицания

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

Коммутативность: x y = y x, {&, }.

Идемпотентность: x x = x, {&, }.

Ассоциативность: (x y) z = x (y z), {&, }.

Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:

,

,

.

Законы де Мо́ргана:

,

.

Законы поглощения:

,

.

Другие (1):

.

.

.

.

, инволютивность отрицания, закон снятия двойного отрицания.

Другие (2):

.

.

.

.

Другие (3) (Дополнение законов де Мо́ргана):

.

.

Поиск по сайту: