4-8. СИНТЕЗ ОДНОРОДНЫХ СХЕМ НА ИНТЕГРАЛЬНЫХ МОДУЛЯХ

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

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

разместить в одном модуле, по-прежнему дебатируется среди специалистов.

Наиболее технологичными из интегральных схем являются модули из МОП (металл — окисел — полупроводник) - транзисторов, сформированные на монокристаллических пластинках. Основная переключаемая схема на МОП-транзисторах — это инвертор, изображенный на рис. 4-40,а.

Рис. 4-40.

Электроды, обозначенные на рис. 4-40,а цифрами 1—3, называются соответственно затвором, стоком и истоком (последние симметричны). При подаче между затвором и истоком некоторого напряжения (знак которого зависит от типа проводимости транзистора, превышающего пороговое) величина тока стока заметно возрастает, что дает возможность использовать транзистор в ключевом режиме. В качестве нагрузочного резистора обычно используется другой МОП-транзистор, на затвор которого подается напряжение питания. Выполнение логических функций обеспечивается параллельным (на общую нагрузку) и последовательным включением транзисторов, как показано на рис. 4-40, б и в. Это дает ключ к синтезу схем: непосредственным соединением транзисторов в различных последовательно-параллельных комбинациях без использования дополнительных компонент можно реализовать любые логические функции.

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

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

Рис. 4-41.

Однородными схемами будем называть схемы, составленные из одинаковых и одинаково соединенных модулей — например, таких, какие изображены на рис. 4-41.

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

по типу связей. (односторонними будем называть сети, у которых подача выходного сигнала модуля на вход модуля исключает связь модуля со входом модуля, и двусторонние — сети, в которых одна связь предполагает наличие второй);

по размерности пространства в принятом способе расположения модулей в сети (одномерные, обычно называемые цепочками, пример которых дан на рис. 4-41,а; двумерные или решетки — рис. 4-41, б и т. д.).

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

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

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

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

Одноканальные бесповоротные цепочки из настраиваемых модулей (каскады Майтра)

Пусть каждый модуль в цепочке, показанной на рис. 4-42, реализует любую из 10 булевых функций, существенно зависящих от двух переменных. Если допустить возможность подачи на внешний вход как переменной, так и ее инверсии, то, как легко показать, можно использовать модуль, который реализуют лишь три логические операции: (конъюнкцию, дизъюнкцию и сумму по модулю 2 соответственно). Таким образом, в этом разделе задачу синтеза однородных цепочек нам удобно свести к синтезу сетей, составленных из элементов трех типов. По имени автора, начавшего исследования таких цепочек, они часто называются майтровскими каскадами. Настроечные входы модуля пока не будем принимать во внимание, но отметим, что если подача инверсий переменных не допускается, это можно сделать введением дополнительного настроечного входа а:

Рис. 4-42.

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

Ограничимся сначала рассмотрением одномерных сетей типа рис. 4-42, в которых каждая переменная подается только на один внешний вход элемента. Исключение составляет только крайний левый элемент, на который подаются две переменные. Такую

схему естественно назвать бесповторной. Входы схемы могут быть упорядочены произвольно. Поведение схемы на рис. 4-42 описывается выражением

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

Процедура синтеза майтровских каскадов основана на следующей теореме и следствии из нее.

Теорема 26. Для того чтобы логическая функция допускала тривиальную декомпозицию относительно переменной равным либо либо либо где необходимо и достаточно выполнять одно из двух условий: а) одна из остаточных функций или обращалась в константу; б) .

Следствие 1. По значению остаточной функции вид тривиальной декомпозиции (если она возможна) может быть определен однозначно следующим образом:

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

Пример 4-16. Логическая функция существенно зависит от всех четырех переменных, поскольку

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

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

Цепочка, представленная на рис. 4-43, имеет собственную функцию, рассматриваемую в примере.

Рис. 4-43.

Очевидно, что не всякая логическая функция может быть реализована цепочкой типа рис. 4-42.

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

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

Различные вариации схемы могут быть получены применениями формул де Моргана всеми возможными способами.

Остается предложить конструкцию модуля, допускающего настройку на реализацию функций Пусть при реализуется операция при при а настройка запрещена. Тогда модуль (рис. 4-44,а) может иметь, например, следующую собственную функцию:

Рис. 4-44.

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

Каждый такой модуль вполне может быть выполнен в одном корпусе в интегральном исполнении и использован как для реализации рассмотренного выше класса функций, так и для класса, описываемого в следующем разделе. Отметим также, что цепочка не более чем из модулей типа рис. 4-44, б может реализовать, в частности, любой минитерм ДНФ или КНФ с числом букв .

В качестве упражнения читатель может прикинуть, сколько МОП-транзисторов потребуется для реализации обеих модификаций модуля.

Одноканальные повторные сети

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

Процедура синтеза повторных сетей совпадает с изложенной в предыдущем разделе, но включает

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

Пример 4-18. Функция как легко убедиться, нереализуема в классе бесповторных сетей, но поскольку то Упрощая, получаем Соответствующая сеть показана на рис. 4-45. Не представляет труда перерисовать ее на модулях типа 4-44, б.

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

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

Рис. 4-45.

Как видно из примера 4-18, в случае повторных сетей существует проблема минимизации. Семейство сетей можно получить теми же способами, что и в бесповторных.

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

Двухканальные сети

Идея реализации произвольной логической функции, представленной полиномом Жегалкина, на двухканальной одномерной сети из модулей типа рис. 4-46,а состоит в следующем. Пусть в верхнем канале происходит формирование члена полинома (конъюнкции), а в нижнем канале к текущему значению полинома (т. е. ранее вычисленной его части) прибавляется по модулю 2

очередное значение конъюнкции. Это легко сделать, если

Как происходит в этом случае настройка элементов цепочки, ясно из примера.

Пример 4-19. Реализация функции на элементах типа рис. 4-46, а показана на рис. 4-46, б.

Максимальная длина сети, реализующей произвольную функцию переменных, равна — максимальное число конъюнкций в полиноме Жегалкина, -средняя длина одной конъюнкции).

Рис. 4-46.

Аналогично можно реализовать функции, заданные в ОДНФ, если в верхнем канале по-прежнему формировать импликанты, а в нижнем — текущее значение ОДНФ. Но в этом случае нужно иметь дополнительный настроечный вход для получения инверсии входной переменной. Система собственных функций соответствующего модуля (рис. 4-47,а) имеет вид:

Приуер Реализация функции показана на

Максимальная длина сети в этом случае равна

Минимизация числа модулей типа рис. 4-46,а и 4-47,а в цепочках может быть достигнута за счет подачи переменных на граничные боковые входы крайних модулей (что и сделано в вышеприведенных примерах), а в некоторых случаях — и на настроечные внешние входы Кроме того, если в модуле рис. 4-46,а добавить еще один настроечный вход для получения инверсии х, то можно минимизировать число букв, если представить заданную функцию в виде разложения (2-18) с инверсиями переменных.

Рис. 4-47.

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

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

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

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

Граничным боковым сигналом является значение вычисляемой формулы равно 1 и 0, если выходной боковой сигнал крайнего правого модуля равен соответственно.

Кратко поясним, как составлена таблица. Граничный боковой сигнал подается на крайний левый модуль цепочки, находящейся в режиме Тот же сигнал будет на выходе этого модуля. На внешний вход второго модуля, работающего в режиме подается переменная Если она равна 1, то на его боковом

выходе вновь появляется сигнал в противном случае — сигнал На боковом выходе модуля будет либо сигнал если либо сигнал если для какого-либо

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

Теперь остается закодировать значения боковых и внешних сигналов. Это может быть сделано, например, так:

Кодировка режимов совпадает, если предположить, что сигналы, обозначенные в предыдущей таблице звездочками, доопределены так же, как в столбце

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

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

модуля (рис. 4-48,а):

Граничные сигналы в цепочке значение скобочной формы равно 1, если на выходе крайнего правого модуля и рано 0 при

Рис. 4-48.

Пример 4-21. Реализовать на модулях типа рис. 4-48,а функцию

Прежде всего эту функцию надо представить в скобочной форме типа произведений сумм произведений, в данном случае в виде

Число символов в ней равно 11. Значит, схема должна состоять из 11 модулей типа рис. 4-48, а. Заметим, что при реализации на модулях типа рис. 4-47,а потребовалось бы на один модуль больше.

Разводка внешних входов показана на рис. 4-48, б. Для наглядности модули помечены символами режимов, на которые они настраиваются. Для двух наборов значений внешних переменных

(второй из них указан в скобках) на схеме указаны вычисленные значения сигналов и выходов модулей.

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

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

Двумерные универсальные сети

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

На рис. 4-14,а изображен феррит, с помощью которого может быть реализована функция Вебба, а на рис. 4-14,б - дизъюнкция большого числа переменных.

Пример 4-1. Реализовать на магнитных сердечниках функцию

Соответствующая схема дана на рис. 4-15,а. Интересно отметить, что скобочная МДНФ для заданной функции

реализуется гораздо сложнее (рис. 4-15, б).

Рис. 4-15. (см. скан)

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

Работу каждого сердечника, входящего в функциональную схему, определяет некоторая функция

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

Составляем теперь неравенств:

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

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

Конечно, такой метод решения практически неприменим вручную уже при весьма скромном числе аргументов функции (практически вручную можно решать задачу

Пусть первой исключается переменная Имеем

Остаточные функции реализуются, как легко видеть, бееповторными сетями, как показано на рис. 4-50. Крайний, слева модуль в верхнем ряду является избыточным. Возможная минимизация решеток по числу модулей достигается варьированием порядка исключения переменных и использованием методов функциональной декомпозиции,

Рис. 4-50.

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

Пример 4-23. Использование разложения (4-25) для построения пирамидальной схемы из трехвходовых мажоритарных элементов приводит при исключении двух переменных к рис. 4-51,а. Изображенная на этом рисунке схема позволяет реалшовать любую функцию трех Переменных, если каждая из функций может принимать одно из четырех значений: Пусть задана односторонняя решетка тииа рис. 4-41, б, поведение модулей которой

(кликните для просмотра скана)

также описывается мажоритарной функцией, а информация распространяется только слева — направо и сверху — вниз. Результат вложения схемы рис. 4-51,а в решетку такого типа показан на рис. 4-51, б. Нумерация «функциональных» модулей совпадает с принятой на рис. 4-51,а. Остальные 17 модулей не несут логической нагрузки — они служат либо для транспортировки сигналов («соединительные» модули заштрихованы), либо для их блокировки («буферные» модули зачернены).

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

Лучшие результаты достигаются при применении специальных методов, ориентированных на синтез схем с заданной топологией и учитывающих особенности используемых модулей. Для сравнения на рис. 4-51, б приведена решетка для реализации произвольной функции трех переменных. Решетка содержит 9 модулей вместо 24 в схеме рис. 4-51, б.