Реализация функций в элементных базисах

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

x x x ₁ x₁

x ₁× x ₂x ₁Ú x ₂

x ₂x₂

а) "НЕ" б) "И" в) "ИЛИ"

Г) «И-НЕ» д) «ИЛИ-НЕ»

Рис. 3.7. Типы логических элементов

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

Базисами являются:

классический базис {НЕ, И, ИЛИ};

базисы шефферовского типа - {И-НЕ} и {ИЛИ-НЕ}.

Рассмотрим, например, реализацию в классическом базисе функции "сложение по модулю два" для двух переменных:

f (х ₁, х ₂) = х ₁ х ₂= х ₁× х ₂v х ₁ × х ₂

Таблица истинности функции представлена таблицей 3.10, а логическая схема изображена на рис.3.8.

Таблица 3.10

X1	X2	X1	X2	X1∙ X2	X1∙ X2	X1+X2

Рис.3.8. Логическая схема функции

f = x₁ x₂ в классическом базисе

Для реализации этой схемы потребовалось 5 логических элементов - 2 элемента "НЕ", 2 элемента "И" и один элемент "ИЛИ". Для реализации такой же функции в базисах шефферовского типа требуется 6 логических элементов. Для базиса "ИЛИ-НЕ" логическая схема показана на рис.3.9.

x₁ x₁ × x₂

x₁v x₂ x₁ ~ x₂ x₁

x₂

x₂ x₁ × x₂

Рис. 3.9. Логическая схема функции

f = x₁ x₂ в базисе "ИЛИ-НЕ"

Эквивалентные преобразования имеют следующий вид:

х₁Ú х₁ Ú х₂ = х₁ × ( х₁ Úх₂ ) = х₁ × ( х₁ Ú х₂ ) = х₁ × х₁ Ú х₁ × х₂ = 0 Ú х₁ × х₂ =

= х₁ × х₂

( х₁ Ú х₂ ) Ú х₂ = ( х₁ Ú х₂ ) × х₂ = ( х₁ Ú х₂ ) × х₂ = х₁ × х₂ Ú х₂ × х₂= х₁ × х₂ Ú Ú 0 = х₁ × х₂

х₁ × х₂ Ú х₁ × х₂ = х₁ × х₂ × х₁ × х₂= ( х₁ Ú х₂ ) × ( х₁ Ú х₂ ) = ( х₁ Ú х₂ ) × ( х₁Ú

Ú х₂ ) = х₁ × х₁ Ú х₁ × х₂ Ú х₂ × х₁ Ú х₂ × х₂ = 0 Ú х₁× х₂ Ú х₁ × х₂ Ú 0 = х₁× х₂Ú Ú х₁ × х₂

х₁ × х₂ Ú х₁ × х₂ = ( х₁ Ú х₂) × ( х₁ Ú х₂) = ( х₁ Ú х₂) × (х₁Ú х₂) =( х₁ × х₁ Ú х₁ × х₂Ú

Ú х₂ × х₁ Ú х₂ × х₂) = 0 Ú х₁ × х₂Ú х₁ × х₂Ú 0 = х₁ × х₂Ú х₁ × х₂= х₁ х₂

В этих преобразованиях использовались, в основном, законы де Моргана.

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

Для технической реализации получившегося после этапа логического синтеза решения применяют технический синтез. На этом этапе решаются три задачи: компоновки, размещения и трассировки.

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

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

x₁ x₂

x₂ x₁

Рис.3.10. Пересечение связей

На рис.3.10 полюса логических элементов жестко закреплены на печатной плате. Поэтому трассировку связей х₁ - х₁ и х₂ - х₂ следует проводить в различных слоях печатной платы.

Возможно иное решение задачи. Пересечение двух связей можно реализовать в виде логической схемы - (2,2) - полюсника (рис.3.11а). При этом логические элементы можно расположить на плоскости таким образом, чтобы связи между ними не пересекались. Минимальная схема, как в классическом, так и в базисе шефферовского типа содержит 8 логических элементов

( рис 3.11б). Поэтому логические схемы, в которых пересечения замещены подобными "плоскими" (2,2) - полюсниками, обладают большой элементной избыточностью и на практике не применяются.

x₁ x₂