МЕТОДЫ СИНТЕЗА СХЕМ ИЗ ФЭ. СХЕМЫ ДЕШИФРАТОРА И ДВОИЧНОГО СУММАТОРА
аранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.
Лекция 29. Методы синтеза схем из ФЭ. Схемы дешифратора и сумматора
Лекция 29. МЕТОДЫ СИНТЕЗА СХЕМ ИЗ ФЭ.
СХЕМЫ ДЕШИФРАТОРА И ДВОИЧНОГО СУММАТОРА
План лекции:
1. Элементарные методы синтеза схем из ФЭ.
2. Синтез схем дешифратора и двоичного сумматора.
- Элементарные методы синтеза
Рассмотрим несколько алгоритмов синтеза, использующих классический базис, состоящий из инвертора, дизъюнктора и конъюнктора.
1. Метод синтеза, основанный на совершенной ДНФ.
Рассмотрим разложение функции const в виде совершенной ДНФ:
.
Введем вспомогательный элемент (рис. 1), с помощью которого построим схему (рис. 2) , реализующую конъюнкцию .
…
при ,
=
при .
Рис. 1
Рис. 2
Очевидно, , и содержит подсхему , одинаковую для всех конъюнкций и имеющую сложность . Если «склеить» схемы , начиная от входов вплоть до вспомогательных элементов, то получим схему , для которой . Подключая выходы схемы к схеме из дизъюнкторов, мы осуществим синтез схемы для (рис. 3) по совершенной ДНФ (алгоритм ).
… Сложность этого алгоритма
.
Поскольку , то и .
Рис. 3
Пример. Построить схему, реализующую функцию .
Представим данную функцию формулой в базисе , используя, например, совершенную ДНФ:
. (1)
Для каждой логической операции в этой формуле возьмем соответствующие функциональные элементы и произведем их соединение так, как этого требует формула. В результате получим схему, показанную на рис. 4. Эта схема использует 10 элементов. Предварительное упрощение формулы (1)
позволяет для той же функции построить более простую схему (рис. 5).
Рис. 5
Рис. 4
2. Метод синтеза, основанный на более компактной реализации множества всех конъюнкций .
На рис. 6 представлено индуктивное построение многополюсника (), реализующего множество всех конъюнкций . Имеем
,
,
.
…
…
…
Базис индукции Индуктивный переход
Рис. 6
Для построения схемы, реализующей функцию , нужно в многополюснике отобрать выходы, соответствующие членам ее совершенной ДНФ , подключить их к схеме (см. рис. 3), осуществляющей логическое сложение, и удалить лишние элементы. Это потребует не более
элементов .
Таким образом, этот метод (алгоритм ) дает
.
3. Метод синтеза, основанный на разложении функции по переменной .
для краткости положим
, .
На рис. 7 представлена индуктивная процедура построения схемы для .
0 1
Базис индукции
Индуктивный переход
Рис. 7
На основании этого метода имеем алгоритм :
,
.
Окончательно имеем
.
Итак, мы видим, что построены алгоритмы и в некотором смысле дают возможность получить все более компактные реализации для функций и, в конечном счете, все более хорошие оценки для функций Шеннона. С другой стороны, получение более хороших результатов синтеза достигается за счет некоторого усложнения алгоритма.
- Синтез схем дешифратора и двоичного сумматора
Общая теория синтеза СФЭ приводит к выводу о том, что большинство булевых функций при больших значениях имеет сложные минимальные схемы. Это означает, что практическую ценность с точки зрения синтеза представляет весьма узкий класс булевых функций. Поэтому наряду с универсальными методами синтеза необходимо иметь методы синтеза, приспособленные к отдельным классам булевых функций, полнее учитывающие свойства отдельных функций.
Рассмотрим далее две многополюсные схемы, имеющиеся в каждом компьютере.
Дешифратором называется схема, имеющая входов и выходов, на которых реализуются всевозможные элементарные конъюнкции ранга . Условное обозначение такой схемы для приведено на рис. 8
При подаче на входы дешифратора какой-либо комбинации нулей и единиц еди-
ничный сигнал появляется только на одном из выходов,
остальные выходы находятся в нулевом состоянии.
В ЭВМ дешифратор применяется для записи или
считывания информации из памяти: на вход подается
двоичный адрес определенной ячейки памяти, это
Рис. 8 вызывает появление единичного сигнала ровно на одном из выходов, который связан с соответствующей ячейкой, что приводит к операции считывания-записи именно для этой ячейки.
Рис. 9
Схему дешифратора можно построить индуктивно, добавляя для каждого входа блок из () конъюнкторов. Построенная таким образом схема дешифратора для показана на рис. 9.
Двоичный сумматор – это схема, реализующая сложение двух целых чисел, заданных в двоичной системе счисления: , .
Условное обозначение схемы сумматора показано на рис. 10.
…
…
Рис. 10
Рассмотрим хорошо известный алгоритм сложения чисел и «столбиком»:
Здесь числа обозначают результаты переносов из предыдущих разрядов . Очевидно, , .
Основываясь на тождестве
,
получаем схему, реализующую соответствующее преобразование величин в (рис. 11).
…
Рис. 12
Обозначим эту схему через ().
Тогда искомая схема получается путем
последовательного соединения блоков (рис. 12).
Здесь , и блок осуществляет преобразование
, .
Очевидно, и при .
Таким образом,
.
Рис. 11
–
DC
МЕТОДЫ СИНТЕЗА СХЕМ ИЗ ФЭ. СХЕМЫ ДЕШИФРАТОРА И ДВОИЧНОГО СУММАТОРА