Представление функций алгебры логики

Функция в алгебре логики — алгебраическое выражение, которое содержит элементы алгебры логики х, у, z, связанные между собой операциями, определенными в этой алгебре.

Функция f(xbх2,,хп), которая, как и ее аргументы, может принимать только два значения, называется булевой или переключательной функцией (ПФ). Задание булевой функции означает, что каждому из возможных сочетаний аргументов поставлено в соответствие определенное значение f. При п аргументах общее число сочетаний ш = 2". Так как каждому сочетанию аргументов соответствуют два значения функции (0, 1),

-уП

общее число функций F = 2 . Переключательная функция может быть задана таблицей истинности или с помощью булевых выражений в одной из нормальных форм — совершенной дизъюнктивной (Сов. ДНФ) или совершенной конъюнктивной (Сов. КНФ). Нормальной формой считают представление этих функций путем суперпозиций вспомогательных функций — конституэнт единицы К" или конституэнт нуля L".

где Tj, Т0 — множество наборов, на которых функция принимает значение 1 и О соответственно.

Эти соотношения используются для синтеза логических (переключательных) функций и вычислительных схем.

Комбинационные схемы

Так как целью булевой алгебры является структурно-функциональное описание логических схем, то необходимо располагать соответствующей методикой. Представив логическую схему, или комбинационную схему, в виде черного ящика (рис. 4.30, а), имеющего п входов и один выход, ее поведение можно определять некоторой переключательной функцией f(X[, х2, ..., хп) — функцией п логических переменных, например трех: Представление комбинационной схемы

Рис. 4.30. Представление комбинационной схемы: а — комбинационная схема с одним выходом; б — комбинационная схема со многими выходами

Комбинационная схема может иметь и несколько выходов (рис. 4.30, б). Примером такой комбинационной схемы служит преобразователь кода "8421 —» 2421" (рис. 4.31).

Комбинационная схема преобразователя кода

Рис. 4.31. Комбинационная схема преобразователя кода

Элементарными переключательными функциями являются функции одного и двух аргументов. Существует 16 функций двух аргументов. С помощью набора переключательных функций двух аргументов можно описать любую цифровую систему. На практике используют не все функции, а лишь те из них, которые методом суперпозиции (замена одной функции другими) обеспечивают представление любой другой функции. Набор таких функций называют функционально-полным или базисом. Основными наборами являются: булевый базис В, = {v, л, -.}, включающий операции И, ИЛИ, НЕ и два универсальных базиса — В2 = = {/}, каждый из которых включает только одну функциюПирса (ИЛИ-HE) или Шеффера (И-НЕ) соответственно. С помощью этих функций можно описать поведение любой цифровой системы.

Для описания поведения комбинационной схемы (см. рис. 4.30, а) необходимо установить соответствие между входными и выходными сигналами, т.е. выразить функцию f" как функцию входных переменных. Зависимость вход => выход в комбинационной схеме в общем случае может быть описана различными способами — временными диаграммами, таблично, номером переключательной функции и др., в том числе и аналитически, например в Сов. ДНФ (выражение (4.5)). Задание условий работы любой комбинационной схемы в виде формул упрощает процесс построения самой комбинационной схемы, так как существует ряд эквивалентных преобразований, в результате которых логические формулы упрощаются. Переключательные функции оказались особенно полезными для описания работы логических элементов ЭВМ.

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

Логические элементы

Рис. 4.32. Логические элементы

Комбинационная схема (рис. 4.33) представляет собой совокупность логических элементов И, ИЛИ, НЕ, организованных определенным образом для реализации зависимости (4.5). Сложность таких схем оценивается по Квайну (подсчитывается общее число входов — Сь схем И и ИЛИ). Для комбинационной схемы, показанной на рис. 4.33, ценаСь= 12.

Комбинационная схема в примере

Рис. 4.33. Комбинационная схема в примере

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

  • ? описание алгоритма функционирования комбинационной схемы;
  • ? минимизация переключательных функций (отдельных и системы в целом), описывающих поведение комбинационной схемы;
  • ? переход к базису И-НЕ либо ИЛИ-НЕ;
  • ? реализация системы переключательных функций на стандартных ИС заданной серии

и представляет собой многошаговый итерационный процесс с возвратом назад и пересмотром ранее принятых решений.

Критерием аппаратной сложности комбинационных схем, реализованных на ИС, является число корпусов ИС либо число их выводов для устройств, реализуемых на печатной плате. Такой метод построения комбинационной схемы может быть использован для реализации сравнительно простых устройств на ИС средней степени интеграции наиболее перспективных в настоящее время серий 1533, 1531 (ТТЛШ) и 1554 (КМОП).

Сложные цифровые устройства проектируются сегодня на базе программируемых логических интегральных схем (ПЛИС), представляющих собой новую элементную базу, обладающую гибкостью заказных БИС и доступностью традиционной «жесткой» логики. Главным отличительным свойством ПЛИС является возможность их настройки самим пользователем путем программирования, под которым понимается изменение внутренней структуры ИС таким образом, чтобы она обеспечивала реализацию заданных переключательных функций на аппаратном уровне. Простейшими представителями ПЛИС являются программируемые постоянные запоминающие устройства (ППЗУ), программируемые логические матрицы (ПЛМ), программируемые матрицы логики (ПМЛ) и другие стандартные БИС, ориентированные на реализацию комбинационной логики.

Метод построения цифровых схем на новой элементной базе с использованием новых технологий проектирования изложен в работе [7].

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >