СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ. ЗАДАЧИ АНАЛИЗА И СИНТЕЗА

аранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.

Лекция 28. Схемы из функциональных элементов. Задачи анализа и синтеза

Лекция 28. СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ.

ЗАДАЧИ АНАЛИЗА И СИНТЕЗА

План лекции:

1. Понятие схемы из функциональных элементов (ФЭ).

2. Задачи анализа и синтеза схем из ФЭ.

Понятие схемы из ФЭ

В современной технике управляющих и вычислительных устройств важное место занимают дискретные преобразователи, т. е. устройства, которые обладают некоторым числом входов и выходов. Наборы сигналов, поступающие на входы и возникающие на выходах, принадлежат известным конечным множествам. Устройства осуществляют преобразования входных наборов сигналов в выходные. Математической моделью таких устройств являются так называемые схемы из функциональных элементов (СФЭ).

В качестве примера рассмотрим электрическую схему из трех диодов и сопротивления, показанную на рис. 1.

Рис. 1. Электрическая схема и ее условное обозначение

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

Точки, отмеченные, будем интерпретировать как входы, а точку – как выход. Работу схемы можно описать следующим образом: если на всех входах низкий уровень напряжения, то на выходе тоже низкий, если хотя бы на одном из входов высокий уровень напряжения, то на выходе – высокий. Если обозначить состояние с высоким уровнем напряжения единицей, а с низким – нулем, то зависимость выхода от входов можно задать при помощи булевой функции .

На основании этого приведенную схему называют логическим элементом «ИЛИ».

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

Будем рассматривать логические элементы с различной зависимостью выхода от входов. Эти элементы можно соединять друг с другом, подавая выходы некоторых элементов на входы других. В результате получаем СФЭ.

Определение понятия СФЭ можно разбить на два этапа. На первом этапе раскрывается структурная часть этого понятия, на втором – функциональная.

I этап. Разобьем этот этап на ряд пунктов.

1. Имеется конечное множество объектов (), называемых логическими элементами. Каждый элемент имеет входов и один выход. Элемент графически изображается так, как указано на рис. 2.

2. По индукции определяем понятие логической сети как объекта, в котором имеется некоторое число входов и некоторое число выходов (рис. 3).

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

… …

…

Рис. 2 Рис. 3 Рис. 4

б) Индуктивный переход. Эта часть основана на использовании трех операций.

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

II. Операция присоединения элемента . Пусть сеть и элемент таковы, что и в выбрано различных выходов с номерами . Тогда фигура называется логической сетью, являющейся результатом подключения элемента к сети . Входами являются все входы , выходами – все выходы сети , кроме выходов с номерами , а также выход элемента . Сеть имеет входов и выходов (рис. 5).

… …

Рис. 6.

Рис. 5

III. Операция расщепления выхода. Пусть в сети выделен выход с номером . Тогда фигура называется логической сетью, полученной путем расщепления выхода . Входами являются все входы , выходами – все выходы сети с номерами 1, …, , , …, и еще два выхода, возникших из выхода с номером сети (рис. 6). Следовательно, имеет входов и выходов.

3. Пусть заданы алфавиты и .

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

. (1)

Приведем примеры схем.

1. Пусть множество состоит из трех элементов И (конъюнктора), ИЛИ (дизъюнктора) и НЕ (инвертора).

Тогда фигура (рис. 6) будет схемой, так как она может быть построена с использованием операций I–III.

Рис. 6 Рис. 7

2. Фигура, изображенная на рис. 7, будет также схемой.

II этап. Определение функционирования схемы.

4. Сопоставим СФЭ (1) систему функций алгебры логики

(2)

называемую также проводимостью данной схемы.

Пример. а) Для схемы имеем систему, состоящую из одного уравнения

или .

б) Для схемы аналогично получаем

Реализация булевых функций схемами из ФЭ. Задачи анализа и синтеза

схем из ФЭ

Задача анализа: для данной СФЭ (1) получить систему булевых уравнений (2).

Алгоритм решения задачи: следуя операциям построения сети I – III, последовательно вычисляем функции на выходах элементов сети.

Задача синтеза: для данного базиса функциональных элементов и произвольной системы булевых уравнений (2) построить схему (1) из заданных ФЭ, реализующую эту систему уравнений.

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

Пример. Для функции

(3)

Схема, соответствующая суперпозиции в правой части формулы (3), показана на рис. 8.

Рис. 8

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

Справедливо следующее утверждение.

Теорема. Существует алгоритм, который для каждой системы булевых функций строит минимальную схему .

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

и, следовательно, искомая схема имеет один выход.

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

, ,

– минимальная сложность схем, реализующих , которые получаются при помощи алгоритма .

Функции , называются функциями Шеннона, причем очевидно, что

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

–

СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ. ЗАДАЧИ АНАЛИЗА И СИНТЕЗА