Синтез схем дешифратора и двоичного сумматора

Элементарные методы синтеза

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

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

При подаче на входы дешифратора какой-либо комбинации нулей и единиц еди-

ничный сигнал появляется только на одном из выходов,

DC

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

В ЭВМ дешифратор применяется для записи или

считывания информации из памяти: на вход подается

двоичный адрес определенной ячейки памяти, это

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

Рис. 9

Схему дешифратора можно построить индуктивно, добавляя для каждого входа блок из () конъюнкторов. Построенная таким образом схема дешифратора для показана на рис. 9.

Двоичный сумматор – это схема, реализующая сложение двух целых чисел, заданных в двоичной системе счисления:,.

Условное обозначение схемы сумматора показано на рис. 10.

…

…

Рис. 10

Рассмотрим хорошо известный алгоритм сложения чисел и «столбиком»:

Здесь числа обозначают результаты переносов из предыдущих разрядов. Очевидно,,.

Основываясь на тождестве

,

получаем схему, реализующую соответствующее преобразование величин в (рис. 11).

…

Рис. 12

Обозначим эту схему через ().

Тогда искомая схема получается путем

последовательного соединения блоков (рис. 12).

Здесь, и блок осуществляет преобразование

,.

Очевидно, и при.

Таким образом,

.

Рис. 11

Дата добавления: 2014-01-04