Первая последовательность совпадает с функцией элемента «ИЛИ», вторая – получается инвертированием выходной функции элемента «И».

Отсюда вытекает реализация элемента типа «ИСКЛЮЧАЮЩЕЕ ИЛИ» в базисе «И», «ИЛИ», «НЕ» (рис. 3.27):

Рис. 3.27

На рис. 3.28 приведена полная схема двоичного сумматора, реализованная на элементах классического базиса «И», «ИЛИ» и «НЕ».

Рис. 3.28

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

3.4.3. Оптимизация схемы двоичного сумматора, реализованного на элементах «И», «ИЛИ», «НЕ»

1 этап – необходимо устранить избыточность, которая бросается в глаза – одинаковые элементы с одинаковыми входами (элементы «И» и «ИЛИ» с входными переменными и , рис. 3.29):

Рис. 3.29

2 этап – исключение из схемы последовательно соединённых инверторов. В покрытой формальным образом схеме, могут присутствовать цепочки из двух последовательных инверторов, которые получаются при инвертировании выходных и входных сигналов последовательно соединённых блоков. Подобные цепочки обычно возникают при покрытии элементами «2И-НЕ» (либо «2ИЛИ-НЕ») и в рассматриваемом примере отсутствуют. Такой вариант будет рассмотрен ниже.

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

3 этап – анализ схемы с учётом недоопределённости логических функций.

Обозначим оставшиеся элементы буквами – и проведем анализ схемы:

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

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

Рассмотрим элемент (он находится прямо на выходе схемы) с учётом возможной недоопределённости его входных логических функций. Для этого «зафиксируем» последовательность на одном из входов (поступающую с выхода элемента ) и попробуем подобрать такую последовательность , поступающую на другой вход, чтобы выходная последовательность элемента не изменилась (рис. 3.29):

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

Рис. 3.30

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

Для элемента фиксируем последовательность блока и находим допустимую последовательность :

Этой последовательности не противоречит выход элемента , но он подчинён элементу , следовательно, образуется обратная связь и такое соединение выполнять нельзя.

В окончательном варианте получаем схему двоичного сумматора, состоящую из 9 элементов (7 двухвходовых и 2 инвертора) со сложностью 32 бита (рис. 3.31):

Рис. 3.31

3.4.4. Покрытие схемы двоичного сумматора элементами «2И-НЕ»

В этом случае производится замещение получившихся при детализации блоков (см. рис.3.26) логическими элементами заданного типа – «2И-НЕ» с последовательностью 1110. В случае несовпадения логических функций замещаемого блока и элемента покрытия, необходимо добавить инверторы на соответствующих входах или выходах элементов. Эти инверторы также реализуются на элементах «2И-НЕ» путём объединения входов.

В результате выполнения этих операций получается схема, состоящая из заданных логических элементов (рис. 3.32):

Рис. 3.32

3.4.5. Оптимизация схемы двоичного сумматора, реализованного на элементах «2И-НЕ»

После формального выполнения покрытия схема носит явно избыточный характер. На 1-ом этапе оптимизации удаляем из схемы «лишние» элементы, имеющие одинаковые входы ( и ). Затем, на 2-ом этапе удаляются цепочки последовательно соединённых инверторов. Результат выполнения этих операций приведён на рис. 3.33:

Рис. 3.33

На 3-ем этапе оптимизации проводтся анализ схемы, предварительно обозначив оставшиеся элементы буквами – :

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

Рассмотрим элемент (он находится прямо на выходе схемы) с учётом возможной недоопределённости его входных логических функций. Для этого «зафиксируем» последовательность на одном из входов (поступающую с выхода элемента ) и попробуем подобрать такую последовательность , поступающую на другой вход, чтобы выходная последовательность элемента не изменилась:

Последовательность (), которую можно подать вместо последовательности , не противоречит логической последовательности, формирующейся на выходе элемента () и он не является подчинённым элементу , следовательно, на нижний вход элемента можно подать сигнал с выхода элемента . Таким образом, из схемы можно исключить элементы , , и (рис. 3.34):

Рис. 3.34

Фиксируем последовательность блока и находим допустимую последовательность :

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

Рассмотрим другой выход схемы. Для элемента : фиксируем последовательность блока и находим допустимую последовательность – :

Такой последовательности на выходах элементов схемы тоже не формируется.

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

В окончательном варианте схема сумматора по модулю 2 состоит из девяти двухвходовых элементов «И-НЕ» и имеет сложность 36 бит. Из 18 элементов, формально покрывших схему, удалось исключить 9 «лишних» элементов (рис. 3.35):

Рис. 3.35.

Следует заметить, что если бы мы при детализации блока, реализующего функцию , для реализации трёхвходового блока 3-го типа взяли вариант 2 (см. рис. 3.4б), то на выходе схемы получили бы блок типа «И». При покрытии такой схемы элементами «2И-НЕ» на её выходе включается инвертор, который в дальнейшем практически невозможно исключить из схемы. Поэтому при выборе варианта реализации той или иной схемы следует учитывать тип базисных элементов (выходной блок схемы должен совпадать по типу с элементами базиса, поскольку при этом отпадает необходимость включения инвертора на выходе схемы).

Аналогично можно синтезировать разряд двоичного сумматора на элементах «2ИЛИ-НЕ», которые так же являются функционально полным базисом.

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

3.4.6. Покрытие схемы двоичного сумматора мультиплексорами

В качестве элемента покрытия логических схем очень удобно использовать мультиплексоры различных типов. Процедура покрытия комбинационных схем подробно изложена в [ ].

В качестве примера рассмотрим мультиплексор типа 4/2, представляющий собой коммутатор на четыре положения. Такие мультиплексоры широко распространены в различных сериях интегральных микросхем (ххххКП2 – сдвоенный мультиплексор со входами разрешения) и библиотеках логических элементов в САПР, предназначенных для разработки схем на программируемых логических интегральных схемах (ПЛИС). Графическое изображение такого мультиплексора приведено на рис. 3.36.

Рис. 3.36. Двухканальный мультиплексор ххххКП2

Если на управляющие входы и подана комбинация (00), то вход соединён с выходом , а вход – с выходом . При подаче на управляющие входы комбинации (01) вход соединён с выходом , а вход – с выходом . И так далее. Входы и служат для разрешения передачи сигналов со входа на выход (разрешение осуществляется низким уровнем) и могут быть использованы для расширения функциональных возможностей рассматриваемого мультиплексора. При решении задач логического синтеза его можно пока не учитывать. Будем считать, что на эти входы подан разрешающий сигнал (0).

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

Если на входы и подана комбинация (00), то выход половины мультиплексора соединён со входом, имеющим вес . Поэтому начальный участок двоичной последовательности состоит из восьми нулей и восьми единиц. Если на управляющие входы подана комбинация (01), то с выходом рассматриваемой половины мультиплексора соединён вход . Поэтому следующий отрезок двоичной последовательности состоит из чередующихся четырёх нулей и четырёх единиц. И так далее. В результате получаем двоичную последовательность мультплекора 4/1:

(1)

Логическая функция (1) сохраняет значение «0» и значение «1». Она несамодвойственна, так как принимает одно и то же значение «0» по адресам 1 и 62. (им соответствуют взаимно инверсные наборы значений аргументов функции). Функция (1) монотонна потому, что при возрастании двоичного набора значений аргументов значение функции не убывает. Рассматриваемая логическая функция нелинейна, так как при разложении числовой последовательности (1) по весам и , например, мы получаем в нулевом столбце матрицы одну единицу. Значит, в полиноме Жегалкина будет, по крайней мере одно, попарное произведение аргументов.

Функция (1) одна не образует функционально полную систему логических функций. Поэтому, на одних только мультиплексорах нельзя построить любую комбинационную логическую схему. Для того, чтобы систему функций сделать функционально полной, нужно добавить функцию (или несколько функций), не сохраняющую значение «0», не сохраняющую значение «1» и немонотонную. Такой функцией является «НЕ». Поэтому, на мультиплексорах и инверторах можно реализовать любую комбинационную логическую схему. В базис также следует включить «Константу «0» и «Константу «1», так как они сравнительно просто реализуются на потенциальных логических элементах. Подача «Константы «0» на какой-либо вход соответствует подключению этого входа к общему проводу, а подача «Константы «1» – соединению его с плюсом источника питания (возможно через токоограничительный резистор).

Двоичную последовательность (1) разложим по управляющим переменным и .

(2)

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

В полученной матрице имеются все возможные двоичные четырёх элементные столбцы.

С помощью мультиплексора 4/2 можно реализовать любую логическую функцию трёх аргументов, так как при разложении исключаются два аргумента (эти переменные подаются на управляющие входы и ), а на входы , , и подаются функции одного аргумента. Это могут быть либо константы, либо функция тождества, либо инверсия третьего аргумента.

В качестве примера построим на мультиплексорах 4/2 разряд двоичного сумматора, заданный следующей числовой последовательностью:

. (3)

Функцию переноса (старший разряд числовой последовательности) (3) реализуем на верхней половине мультиплексора, а функцию суммы (младший разряд) – на нижней. Разложим двоичные последовательности () и () сумматора по всем возможным парам входных переменных (это значит, что выделенные переменные, по которым ведётся разложение подаются на управляющие входы и мультиплексора). Логические функции, которые необходимо подать на входы , , и мультиплексора определяются строками матрицы разложения.

Функции и являются симметричными, поэтому все матрицы одинаковые и, следовательно, можно брать для реализации любой вариант разложения. Для реализации функции на вход верхней половины мультиплексора подаётся «Константа «0» (строка матрицы 00). На входы и подается переменная, имеющая вес 1 (строка матрицы 01), а на вход – «Константа «1» (строка матрицы 11).

Для реализации функции на входы и нижней половины мультиплексора подаётся переменная с весом 1 (строка матрицы 01), а на входы и – инверсное значение переменной с весом 1 (строка матрицы 10). Схема разряда двоичного сумматора на сдвоенном мультиплексоре 4/1 (ххххКП2) приведена на рис. 3.37.

Рис. 3.37.

Здесь «Константы «0» и «1», которые подаются на входы и , обозначены в виде символов взятых в кавычки («Константа «0» подаётся и на входы разрешения и ). Входные переменные с весами 4, 2, и 1 обозначены в виде соответствующих символов без кавычек. Инверсное значение переменной, имеющей вес 1, реализовано с использованием дополнительного инвертора.

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

При использовании более сложных мультиплексоров (8/1 или 16/1) возможно достаточно простое покрытие функций 4-х или 5-и аргументов. При этом разложение ведётся по трём (в случае использования мультиплексора 8/1) или четырём (при использовании мультиплексора 16/1) входным переменным, которые затем подаются на управляющие (адресные) входы мультиплексора. Каждая из строк полученной матрицы состоит из двух элементов и представляет собой либо одну из констант, либо функцию тождества, либо инверсию оставшегося невыделенным аргумента. Эти строки необходимо подать на входы соответствующие входы данных мультиплексоров. Переменные для построения матрицы разложения выбираются таким образом, чтобы в строках по возможности отсутствовала комбинация (10). В этом случае удаётся реализовать требуемую функцию без использования дополнительных инверторов. В противном случае потребуется как минимум один элемент для формирования инверсии оставшегося аргумента.

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