Автор: Потёмкин И.С.
Теги: компьютерные технологии вычислительная техника микропроцессоры автоматика автоматизация цифровая техника
Год: 1981
Текст
БИБЛИОТЕКА
по
АВТОМАТИКЕ
Выпуск 618
И. С. ПОТЕМКИН
АВТОМАТИЗАЦИЯ
СИНТЕЗА
ФУНКЦИОНАЛЬНЫХ
СХЕМ
(на примере сумматоров
с групповым переносом)
МОСКВА ЭНЕРГОИЗДАТ 1981
ББК 32.97
П 64
УДК 681.325.55.042
РЕДАКЦИОННАЯ КОЛЛЕГИЯ:
И. В. Антик, Г. Т. Артамонов, А. А. Воронов, Л. М. Закс,
В. К. Левин, В. С. Малое, В. Э. Низе, Д. А. Поспелов,
И. В. Прангишвили, Ф. Е. Темников, Г. М. Уланов,
Ю. М. Черкасов, А. С. Шаталов
Потемкин И. С.
П64 Автоматизация синтеза функциональных схем:
(на примере сумматоров с групповым переносом).—
М.: Энергоиздат, 1981, 88 с, ил.— (Б-ка по авто-
матике; Вып. 618).
Оггисаны методика дискретного комбинаторного синтеза, способы
сокращения перебора, подход к выбору при нескольких критериях.
Методика позволяет строить программы автоматического синтеза опе-
рационных узлов ЭВМ. За 1 час программа генерирует схемы сумма-
торов с групповым переносом в распространенных базисах, по каче-
ству сравнимые с построенными квалифицированным инженером. Ана-
лизируются и сравниваются сумматоры с различными типами группо-
вого переноса
Для инженеров, занимающихся вопросами автоматизации проек-
тирования управляющей цифровой аппаратуры, а также разработкой
функциональных схем цифровых устройств.
30 к.
п
30502-479
051(01)-81
182-81(3) "2405000000
ББК 32.97
6Ф7
Q Энергоиздат, 198 \
ПРЕДИСЛОВИЕ
В этой книге предлагается для автоматизации синтеза логиче-
ских схем функциональных узлов ЭВМ и, в частности, многоразряд-
ных сумматоров с групповым переносом предлагается использовать
метод комбинирования с помощью ЭВМ логических фрагментов,
более крупных, чем логический элемент, с последующей програм-
мной проверкой качества получающихся вариантов и выбора #з них
наилучшего с точки зрения технического задания (ТЗ).
Еще Лейбниц считал, что искусство изобретения имеет две со-
ставляющие: 1) комбинирование (синтез), в результате которого
порождаются различные варианты, и 2) анализ получившихся
вариантов. К этому способу формализации процесса создания новых
объектов периодически обращались различные исследователи; одна-
ко попытки эти носили весьма нерегулярный характер, и осознанное
применение метода как такового еще не получило широкого распро-
странения в кругу инженеров. Основным препятствием, видимо,
было слишком большое число получающихся вариантов, оценить и
сравнить которые человеку было не под силу.
Путевку в жизнь этому заманчивому по своей простоте спосо-
бу может дать вычислительная техника. В книге изложена методи-
ка, которая позволяет с помощью ЭВМ выполнить не только оцен-
ку готовых вариантов, но и сам процесс их порождения. Любопыт-
но, что принцип порождения по своей сути оказывается очень близ-
ким к идее порождающих грамматик формальных языков. В этой
процедуре синтеза объектов отчетливо прослеживаются как синтак-
сический, так и семантический механизмы, а базовые фрагменты,
из которых строится схема, играют роль терминальных символов
языка.
В книге показано, как можно при решении многих практических
задач синтеза технических объектов избежать чрезмерно большого
количества порождаемых вариантов. Важным достоинством описы-
ваемой методики является то, что специалист-разработчик програм-
мы синтеза имеет право не представлять хорошо свойств всего поля
проектируемых объектов, т. е. не знать, каким сочетаниям парамет-
ров соответствуют хорошие схемы. Ему достаточно лишь наметить
программе довольно широкие области, где можно попытаться поис-
кать решения, а непосредственный поиск хорошего объекта програм-
ма выполнит сама. В книге обращается внимание на ряд других
ценных свойств принятого подхода, который проверялся на програм-
мах автоматического синтеза сумматоров, счетчиков, схем поиска
левой единицы и других узлов. Этот подход можно использовать
для синтеза не только логических схем, но также и других техниче-
ских объектов в тех случаях, когда основной проблемой является
не столько оптимизация параметров р рамках заданной структуры,
сколько поиск самой структуры
3
При реализации методики автоматического синтеза для по-
строения схем сумматоров очень продуктивным оказался новый под-
ход к структуре сумматора с групповым переносом, позволивший
представить его логическую схему как композицию базовых фраг-
ментов весьма малого числа типов. Принятое структурное деление
удобно также для первоначального изучения сложных сумматоров
и для сравнения их между собой. В книге приведены схемы базо-
вых фрагментов, из которых автоматически или «вручную» можно
строить схемы сумматоров. При этом автор старался отобрать для
практического использования возможно лучшие фрагменты. Есть
в книге и схемные решения, которые, насколько это известно, ра-
нее в литературе не освещались. К ним можно отнести использова-
ние инверсных групповых переносов, экономичный способ формиро-
вания выходного переноса, способ устранения состязаний в сумма-
торе со сквозным переносом (с обходными цепями) и некоторые
другие.
В книге приведен ряд результатов, полученных при программ-
ном синтезе сумматоров с групповым переносом. Для синтеза сум-
матора по ТЗ заказчика требуется около часа времени ЭВМ сред-
него класса, а качество полученных схем соизмеримо с качеством
схем, созданных инженером достаточно высокой квалификации.
Приведен анализ результатов синтеза, выявивший полезные свойст-
ва ряда классов сумматора, в частности трехярусных, которые до
сих пор редко попадали в поле зрения разработчиков схем.
Книга построена так, чтобы читатели, интересующиеся лишь
общими вопросами автоматического синтеза технических объектов,
могли читать только § 1—4, при этом совершенно не требуется зна-
комства со схемами сумматоров. Если такой читатель имеет пред-
ставление о сумматорах, он может добавить к этому списку еще
и § 14, иллюстрирующий материал первой части книги. Те, кого
интересуют сумматоры с групповым переносом безотносительно
к вопросам автоматического синтеза, могут ограничиться § 5—14,
посвященными непосредственно схемам сумматоров.
Автор
ГЛАВА ПЕРВАЯ
ВАРИАНТНЫЙ СИНТЕЗ
1. ПРИНЦИП ВАРИАНТНОГО СИНТЕЗА
а) АЛГОРИТМ И ИСЧИСЛЕНИЯ
Задача автоматизации синтеза логических схем ставится уже
давно, однако заметных успехов в области автоматического синте-
за логических схем многовходовых операционных узлов пока нет.
Во всяком случае, все реально используемые схемы являются кра-
сивыми догадками, изобретениями, а отнюдь не закономерным
результатом применения какой-либо формальной процедуры. При-
чина, по мнению автора, кроется в том, что поиск решения задачи
синтеза ведется всегда в одном и том же направлении: в направле-
нии разработки некоторой целенаправленной процедуры, т. е. стро-
гого алгоритма синтеза в духе А. А. Маркова, представляющего
собой набор не слишком большого числа простых правил, по мере
выполнения которых разработчик неуклонно, детерминированно
продвигался бы в заданном направлении к поставленной цели, пока
через некоторое число шагов не построил бы' хорошую в определен-
ном смысле логическую схему.
Тем не менее использование четких процедур, однозначно веду-
щих к цели, — не единственный способ, применяемый в практике
разработчиков. Другой метод, которым часто решают задачи, — это
метод проб и ошибок. При работе по этому методу на первом эта-
пе порождается гипотеза, т. е. строится (мысленно или на бумаге)
некоторый гипотетический объект (схема, конструкция и т. п.),
о котором наперед не известно, окажется ли он хорошим, а иногда
даже не известно, будет ли он вообще работать. Вторым этапом
является проверка (с помощью логических построений, расчетов,
моделирования и т. п.) качества гипотезы, т. е. определение харак-
теристик получившегося объекта (времени задержки, объема обо-
рудования, потребляемой мощности). Проверка результата — это
уже задача анализа, которая в отличие от задачи синтеза, в прин-
ципе всегда решается и притом однозначно. Вероятнее всего,, сразу
после первой пробы хороший результат получить не удастся. Тог-
да можно породить еще одну гипотезу, снова ее проверить и т. д.,
пока результат окажется удовлетворительным.
В отличие от алгоритма, который на каждом шаге указывает,
куда нужно идти, чтобы приблизиться к ответу, на этапе порожде-
ния гипотезы лишь известно, куда можно идти, т. е. известно лишь,
где в принципе может быть решение. Есть ли оно там на самом
деле или нет, выяснится только после второго шага — проверки,
т. е. после замыкания петли обратной связи.
На указанное различие в способах получения решения впервые,
видимо, обратили внимание В. Б. Борщев и Ю. А. Шрейдер [Л. 1].
Авторы отмечают, что набор правил, который позволяет порождать
5
гипотезы, нс является алгоритмом, поскольку в нем нет указания
о том, куда нужно идти, чтобы получить результат. Это не алго-
ритм, а исчисление, т. е. набор некоторых предписаний, которые
лищь разрешают делать какие-то преобразования.
Примером исчисления, которым широко пользуются в процессе
синтеза логических схем, являются преобразования алгебры логики.
Набор правил говорит лишь о том, как можно преобразовать исход-
ное булево выражение, но ничего не говорит о том, как нужно его
преобразовать, чтобы на заданном логическом базисе (например,
базисе 155 серии) получить минимальную задержку, или минималь-
ное число корпусов, .или некоторый компромисс между этими тре-
бованиями. Те, кто привык воспринимать преобразования алгебры
логики как алгоритмы, могут в- качестве эксперимента попытаться
самостоятельно преобразовать общеизвестные булевы выражения
для суммы и переноса i(L) и (2), (см. § 6.) так, чтобы они в резуль-
тате описывали сумматор, который по скорости и экономичности
не уступал бы схемам, приведенным, скажем, на рис. 7 или 22.
После нескольких часов работы любой человек легко соглашается
с тем, что процесс поиска хорошей схемы принципиально отличает-
ся от поиска, например, корней квадратного уравнения: алгоритм
решения квадратного уравнения четко указывает, как нужно преоб-
разовать выражение, чтобы получить искомые корни, а правила
булевой алгебры никакого целеуказания не содержат.
Если выполнить все возможные преобразования, разрешенные
заданным исчислением, то будет получено множество гипотез (мно-
жество вариантов объекта). Таким образом, исчисление, т. е. спи-
сок правил порождения гипотез, можно рассматривать как неяв-
ное описание множества возможных вариантов объекта. Помимо за-
дания исчисления нужно задать еще способ перехода к очередной
гипотезе, если рассмотренная на предыдущем шаге гипотеза не при-
нята как окончательная. Способов выборки для заданного исчисле-
ния может быть очень много. Одним из крайних случаев может
быть методическое порождение всех возможных вариантов в опре-
деленном порядке (полный перебор). В качестве другой крайности
можно рассматривать совершенно случайный выбор гипотез. Меж-
ду этими крайними точками заключено множество других возмож-
ных способов выбора, основанных на каких-либо предпочтениях.
Таким образом, чтобы формализовать процесс порождения ги-
потез, надо иметь два различных описания: 1) набор правил исчис-
ления, неявно задающий множество допустимых объектов-гипотез,
и 2) процедуру выборки очередной гипотезы из числа разрешенных
исчислением. Кроме того, поскольку в исчислении отсутствует поня-
тие цели, нужно к двум предыдущим описаниям, обеспечивающим
процесс порождения гипотез, добавить еще третье описание — про-
цедуру оценки качества порожденных гипотез и выбора лучшей из
них с точки зрения заданного критерия.
Очевидно преимуществом алгоритма перед исчислением являет-
ся то, что алгоритм гарантирует достижение цели, и притом весьма
коротким путем. Но это верно лишь в случае, когда алгоритм уже
есть. Обратим внимание на не совсем очевидный момент: поскольку
алгоритм при любых разрешенных сочетаниях входных данных целе-
направленно ведет к результату, то мы вправе сказать, что в каком-
то смысле алгоритм «знает» абсолютно все решения данной задачи
при любых сочетаниях входных переменных. Это — большое удоб-
ство для того, кто пользуется алгоритмом, но одновременно и боль-
6
шой недостаток для разработчика алгоритма. Ведь для того, чтобы
выразить в виде системы четких правил процесс получения всех ре-
шений, разработчик алгоритма предварительно должен очень хорошо
изучить все поле возможных решений, т. е. решить очень много
задач «вручную», еще не имея алгоритма. В каком-то смысле алго-
ритм — это компактный и удобный способ передать другим (в том
числе и ЭВМ) свой опыт решения класса задач, полученный при
детальном исследовании какого-либо процесса, явления и т. д.
Для объектов типа логических схем сложных многоразрядных
функциональных узлов с учетом произвольной разрядности прост-
ранство решений оказывается исключительно обширным — порядка
десятков — сотен тысяч вариантов. Обследовать и осознать такое
пространство с приемлемой степенью детализации за разумное чис-
ло лет для человека не представляется возможным. Следовательно,
столь же эфемерной выглядит и задача построения алгоритма ори-
ентирования в этом пространстве, т. е. целенаправленного синтеза
логических схем достаточно сложных узлов. Это, на взгляд автора,
и является причиной того, что многолетние попытки создать целе-
направленные алгоритмы автоматического синтеза сложных логиче-
ских схем операционных узлов не дали до сих пор существенных
практических результатов.
Ситуация в корне меняется, если синтез логических схем осно-
вывается не на алгоритме, а на исчислении, порождающем схемы-
гипотезы, качество которых оценивается потом в порядке акта
обратной связи. Самое существенное различие заключается в том,
что в данном случае программист не должен формулировать в виде
программы указания, где в пространстве решений находятся хоро-
шие схемы. От негр вообще не требуется знания свойств простран-
ства решений. Он должен лишь суметь сформулировать намного
более простые правила: что можно попробовать, чтобы получить
решение. Информацияг о качестве каждого полученного решения
будет извлекаться из пространства решений самой программой
с помощью расчетных формул. При таком подходе сложность син-
тезируемой схемы уже в граздо меньшей степени определяется зна-
ниями и возможностями самого программиста. Он в каком-то смыс-
ле закладывает в программу меньше, чем потом от нее получает.
Программа вполне может получить решение, совершенно неожидан-
ное для ее составителя, решение, о существовании которого он и не
подозревал.
Если к тому же программа составлена ведущим специалистом
в данной области, то она может синтезировать решение, которое
ранее вообще никому не было известно. Такое решение по праву бу-
дет удовлетворять общепринятым требованиям новизны и патенто-
пригодности. В этой ситуации распространенное убеждение, что про-
грамма выдает человеку не более того, что он в нее заложил, ста-
новится уже весьма спорным. В основу описываемого в данной
книге метода вариантного синтеза положены именно исчисления,
а не жесткие целенаправленные алгоритмы.
Однако здесь возникают некоторые терминологические трудно-
сти. Построенные машинные программы автоматического синтеза
как-то затушевывают разницу в подходах к решению задач с пози-
ций создания целенаправленных алгоритмов и с позиций поиска
методом проб и ошибок в пространстве, заданном исчислением:
«раз и то и другое представимо в виде машинной программы, зна-
чит, и то и другое —алгоритм!» В то же время разница в подходах
настолько существенна, что выбор подхода часто определяет успех
7
всего дела. Поэтому будем помнить о двух возможных исходных
принципах, на основе которых могут строиться программы, а по-
скольку термин «алгоритм» строго не определен, в последующем
тексте слово «алгоритм» будет использоваться не как синоним
слова «программа», а как обозначение некоторого «целенаправлен-
ного» подхода к синтезу, основанного на предписаниях типа «нуж-
но», в отличие от подхода, базирующегося на исчислениях и
использующего предписания типа «можно».
б) КОМБИНАТОРНОЕ ПОРОЖДЕНИЕ ВАРИАНТОВ
Метод вариантного синтеза основывается на следующих пред-
посылках:
1. Объект проектирования (ОП) можно описать с помощью
сравнительно небольшого числа параметров. В простейшем случае
ОП можно представить состоящим из некоторого числа фрагментов
разных типов, соединенных в определенном порядке, например из
нескольких блоков. Блок каждого типа выполняет определенную
функцию и одновременно рассматривается как параметр, характе-
ризующий /ОП.
2. Каждый параметр может иметь несколько значений, т. е.
фрагмент каждого типа (каждый блок) может существовать в виде
нескольких модификаций, которые одинаковы с точки зрения выпол-
нямой функции, но отличаются какими-либо существенными техни-
ческими характеристиками, например размерами, стоимостью, вре-
менем задержки и т. п.
3. Существует способ оценки качества всего объекта, который
при известных значениях параметров объекта позволяет щ группы
объектов выбрать один или несколько лучших в некотором смысле.
Приведем примеры описания ОП с помощью набора парамет-
ров. Как известно, при сложении чисел с плавающей запятой нужно
для выравнивания порядков сдвинуть вправо мантиссу одного из
операндов, затем сложить мантиссы и после этого сдвинуть резуль-
тат, если необходима его нормализация. В соответствии с этим
устройство обработки мантисс некоторого гипотетического процес-
сора можно представить состоящим из трех блоков: блока сдвига
вправо для выравнивания порядков, блока алгебраического сложе-
ния (сумматора) и блока сдвига влево для нормализации. Для
упрощения примера не будем рассматривать возможность выполне-
ния обоих сдвигов на одном сдвигателе.
Пусть по каким-то соображениям, связанным, например, с уни-
фикацией, разрешено использовать лишь ограниченное число вари-
антов освоенных в производстве сдвигателей и сумматоров. Назо-
вем эти разрешенные к применению блоки базовыми фрагментами.
Тогда группу базовых фрагментов каждого типа можно рассматри-
вать как параметр и устройство сложения мантисс может быть опи-
сано тремя параметрами: П1 — вид сдвигателя вправо, П2 — вид
сумматора, ПЗ — вид сдвигателя влево. Число значений каждого па-
раметра равно числу базовых фрагментов данного типа. Например,
число значений П2 равно числу разрешенных к применению сумма-
торов.
В роли параметров не обязательно должны выступать сугубо
материальные базовые фрагменты. Параметрами могут быть число-
вые и любые другие характеристики. Набор параметров должен
лишь обеспечить возможность описания любых существенных раз-
6
личйй между объектами. Другими словами, параметры — это любые
свойства объекта, позволяющие определить важные для заказчика
и изготовителя характеристики, по значению которых один вариант
объекта отличается от другого. Так, для трансформатора толщина
листа и марка стали не являются конструктивными единицами, са-
мостоятельно участвующими в операции сборки, но тем не менее их
целесообразно рассматривать как параметры, которые существенно
влияют на эксплуатационные характеристики готового изделия.
Если комбинировать значения параметров в различных допусти-
мых сочетаниях, то можно получать различные варианты объекта,
вычислять характеристики каждого полученного варианта и продол-
жать комбинирование, пока не будет получен объект, удовлетворяю-
щий заданию (если он вообще может быть построен по данному
принципу из существующих фрагментов). В этом и заключается суть
метода вариантного синтеза. Простота метода позволяет реализо-
вать его в виде программы ЭВМ. Легко заметить, что метод бази-
руется не на целенаправленной процедуре типа алгоритма, вычисля-
ющего, какие именно фрагменты нужно использовать в каждом кон-
кретном случае, чтобы удовлетворить конкретному заданию, а на
исчислении, указывающем лишь, как можно комбинировать фраг-
менты, т. е. где можно искать решение. Оценку решений и выбор из
них наиболее подходящих по заданным критериям программа про-
изводит сама. Разработчик программы имеет право не знать, для
каких вариантов задания какая комбинация фрагментов окажется
наилучшей. Это очень важно при большой сложности объекта, т. е.
при большом числе возможных вариантов.
в) МОРФОЛОГИЧЕСКИЙ ЯЩИК
В 1942 г. австрийский астроном Ф. Цвикки разработал метод
поиска новых технических решений, основанный на систематическом
изучении возможных вариантов объекта, и назвал его методом
морфологического ящика. Морфология — это наука о строении объ-
екта, а морфологический ящик — это таблица фрагментов, которые
могут входить в состав объекта, т. е. таблица, отражающая строе-
ние объекта/его морфологию (см., например, [Л 12]). Уровень фор-
мализации метода морфологического ящика невысок, поскольку
метод был ориентирован на использование человеком и предназна-
чен Ф. Цвикки для поиска принципиальных технических решений на
начальных стадиях проектирования. Дальнейшие исследования ме-
тодов инженерного творчества и развития вычислительной техники
привели к постановке задачи автоматического программного синте-
за новых технических структур. В нашей стране работы по автома-
тизации синтеза структур операционных блоков ЭВМ были начаты
в конце 60-х годов, и одними из первых публикаций, насколько это
известно автору, были [Л. 19 и 20].
Излагаемый в данной книге метод вариантного синтеза можно
рассматривать как дальнейшее развитие идеи морфологического
ящика. Метод обладает высокой степенью формализации и поэтому
позволяет выполнять синтез новых объектов целиком с помощью
программы, без участия человека.
Построим морфологический ящик приведенного в качестве при-
мера устройства сложения мантисс чисел с плавающей запятой.
Пусть разрешено использовать два вида сдвигателей вправо — А и
В, три вида сумматоров — а, (3 и у и три вида сдвигателя влево,
9
которые называются 1, 2 и 3. Тогда можно сказать, что параметр
П1 имеет два значения — А и Б, а параметры П2 и ПЗ — по три
значения — а, 0, у и 1, 2, 3 соответственно.
При морфологическом анализе (изучении строения) какого-то
объекта иногда обнаруживается, что существуют варианты, в опи-
сании которых некоторый параметр вообще отсутствует. Например,
в некоторых специализированных процессорах на вход блока сло-
жения мантисс могут поступать числа, имеющие заведомо одинако-
вый порядок, В этом случае надобность в сдвигателе вправо отпа-
дает вообще. Чтобы иметь возможность описывать и такие вариан-
ты объектов, введем в списки значений параметров там, где это
нужно, наряду с существующими значениями еще и пустое значе-
ние, которое символизирует полное отсутствие данного параметра
в описании объекта. В нашем примере будем полагать, что Ш кро-
ме значений А и В имеет еще и значение О, т. е. пустое значение.
Все сказанное представим в виде табл. 1, которую и будем на-
зывать морфологическим ящиком устройства сложения мантисс.
Ящик имеет гнезда —П1, П2, ПЗ —по числу параметров. Имя гнез-
да и его номер совпадают с именем и номером соответствующего
параметра.
Таблица 1
Морфологический ящик устройства сложения мантисс
Ш. Сдвигатель вправо
П2. Сумматор
ПЗ. Сдвигатель влево
Значение па-
раметра "
Характеристики
Усло-
вие
Значение
параметра
Характеристики
Усло-
вие
Значение
параметра
Характе-
ристики
XI.1 '
Т
Q
Х2А
Т
Q
Т
Q
А
1
2
5
А или
ос
0
10
6
Х2.\
1
4
6
О
В
0
4
2
х\л
|
1
12
3
Не В
2
5
8
О
0
0
0
—
1
18
2
Х\А
со
7
4
идиОа
Чтобы формализовать процедуру синтеза объектов, классиче-
ская структура ящика, предложенная Ф. Цвикки, была модифици-
рована. В гнезда в дополнение к основному полю «Значение пара-
метра» были добавлены еще два поля: «Условие» и «Характеристи-
ки». Роль добавочных полей будет ясна при дальнейшем рассмот-
рении.
Состав гнезд и правила выборки их содержимого выступают
в роли исчисления, или формальной системы, т. е. позволяют опи-
сать множество возможных вариантов объекта. Если выбрать по
одному значению параметра из каждого .гнезда, то тем самым бу-
дет идентифицирована одна из мыслимых реализаций ОП. Посколь-
ку каждый вариант ОП характеризуется вполне определенным и
притом единственным сочетанием значений параметров, будем это
сочетание использовать в качестве имени данного варианта объекта.
При этом можно использовать как сами названия значения пара-
метров, так и порядковые номера этих значений: вариант Aal, или
111, вариант 002, или 322 и т. д.
10
В полях характеристик обратим внимание пока лишь на две
характеристики — Т и Q, которые отражают в некоторых условных
единицах, время задержки и аппаратурные затраты каждого базо-
вого фрагмента (каждого значения параметра). Пользуясь этими
данными, оценочная программа может вычислить значения Т и Q
для любой заданной комбинации значений параметров, т. е. для
любого заданного варианта ОП.
Типичная задача, с которой сталкивается разработчик логиче-
ских схем функциональных узлов, формулируется приблизительно
следующим образом: при заданном ограничении на время задержки
(например, 7^25 в единицах табл. 1) синтезировать устройство,
имеющее минимальные аппаратурные затраты Q. Задача в принципе
не меняется, если задать ограничение, по Q и потребовать минимиза-
ции Т. Одним из возможных способов решения задачи является
полный перебор всех вариантов, вычисление их характеристик Т и
Q.h сравнение результатов. Этот метод описывается наиболее про-
стой программой и, если вариантов не слишком много, то всегда
гарантировано нахождение наилучшего решения. Кроме того, метод
полного перебора обладает еще целым рядом ценных свойств, кото-
рые будут отмечаться по ходу изложения. Способам сокращения
перебора для случаев, когда число возможных вариантов непомерно
велико, будет посвящен специальный раздел, а пока будем пола-
гать, что число вариантов не слишком большое, и можно использо-
вать метод полного перебора. Практика показывает, что это допу-
щение отнюдь не беспочвенно: при синтезе логических схем многих
массовых функциональных узлов (сумматоров, счетчиков, регистров,
дешифраторов и т. п.) число реально перебираемых программой
вариантов не превышает нескольких тысяч, и при этом расход ма-
шинного времени средней ЭВМ, как правило, укладывается в пре-
делы одного часа.
. Заметим, что задача синтеза объекта, имеющего экстремальное
значение какой-либо одной характеристики, например минимально
возможную временную задержку, значительно проще, чем сформу-
лированная выше задача разработчика, поскольку при ее решении
проблемы перебора вариантов не возникает. Самый быстродейст-
вующий объект получается, если из каждого гнезда морфологиче-
ского ящика (табл. 1) выберем фрагмент, имеющий минимальное
значение Т. Если сдвигатель вправо • не нужен, то таким объектом
будет объект Oal, а если сдвигатель необходим, то объект Аа\.
Точно так же самыми экономичными устройствами будут объекты
ОуЗ или ВуЗ. Однако в технике редко требуется получать эстре-
мальные значения какой-либо одной характеристики в ущерб всем
остальным, поэтому в качестве основной задачи проектирования мы
примем задачу, когда требуется минимизировать (максимизировать)
значение какой-либо одной характеристики не любой ценой, а
при заданном ограничении по другой (или другим) характеристи-
кам.
Характеристик, которые одновременно интересуют заказчика,
может быть и больше двух. Кроме времени задержки и числа кор-
пусов микросхем заказчика могут интересовать потребляемая мощ-
ность, стоимость и другие" показатели. Однако при решении задачи
синтеза методом полного перебора не имеет принципиального зна-
чения число характеристик, по которым ведется отбор. Поэтому для
упрощения изложения и наглядности графиков в дальнейшем будем
полагать,- что есть лишь две существенные для заказчиков характе-
ристики:' время задержки Т- и аппаратурные затраты Q.
11
Совокупность вариантов ОП, порождаемых путем комбинирова-
ния различных значений параметров, удобно представлять в виде
графа, показанного на рис. 1. Этот граф мы будем называть «де-
ревом синтеза» и пока не будем различать сплошные и пунктирные
ветви. Различным ярусам дерева синтеза соответствуют различные
параметры, а ветвям, выходящим из узлов, — значения этих пара-
метров. Тупиковые вершины (листья дерева) отображают различные
возможные варианты объекта. Процедуру построения какого-либо
объекта, т. е. процедуру выбора значений всех его параметров, мож-
но представать как движение от самой левой корневой вершины
Рис. 1. Дерево синтеза.
к самой правой тупиковой, причем в каждой промежуточной вер-
шине осуществляется выбор направления движения. Выбор может
быть как случайным, так и закономерным.
•Дерево синтеза содержит, ло сути, ту же информацию, что и
морфологический ящик, но человеку работать с графом, если он не
слишком велик, оказывается намного удобнее: на графе уже изо-
бражены все возможные комбинации параметров, а в ящике они
лишь подразумеваются, и их надо строить «в уме». Однако в па-
мяти ЭВМ множество вариантов ОП удобнее - хранить в виде
морфологического ящика и прилагаемых к нему правил комбиниро-
вания базовых фрагментов, т. е. в форме исчисления. По сравнению
с хранением возможных вариантов в виде полного списка это тре-
бует во много раз меньшего объема памяти и избавляет человека
от утомительной работы по составлению вручную списка из тысяч
вариантов объекта.
2. ПРОЦЕДУРА АВТОМАТИЧЕСКОГО СИНТЕЗА
а) ПРОГРАММНАЯ ГЕНЕРАЦИЯ ВАРИАНТОВ
В процедуре автоматического синтеза ОП можно вьГделить три
этапа: 1) порождение различных допускаемых морфологическим
ящиком комбинаций значений параметров, т. е. порождение множе-
12
ства вариантов ОП; 2) вычисление значений важных для заказчика
характеристик порожденных объектов; 3) выявление лучшего объек-
та на основании анализа характеристик по критериям качества, за-
данным в конкретном ТЗ. Этапом собственно синтеза является
этап 1; этапы 2 и 3 — это этапы анализа уже готовых вариантов,
порожденных на 1-м этапе.
Рассмотрим подробнее основные моменты, связанные с форма-
лизацией этапа программного порождения объектов. Процедура по-
рождения списка объектов при полном переборе аналогична проце-
дуре порождения последовательности чисел в позиционной системе
счисления. Число разрядов равно числу параметров. Номер разряда
совпадает с номером параметра, а число цифр в разряде равно
числу значений данного параметра. Такая процедура, примененная
к морфологическому ящику (см. табл. 1), начнет генерировать по-
следовательность имен объектов Ла1, Ла2, ЛаЗ, Л pi, Л|32, Л|33, Лу\
и т. д. Обратим внимание на то, что эта процедура порождает все
возможные варианты объекта независимо-от порядка, в котором
сами параметры или их значения размещены в морфологическом
ящике. Другими словами, при построении ящика не требуется вы-
полнять каких-либо исследований и работ по упорядочению па-
раметров и их значений. Это очень существенное облегчение в слу-
чае сколько-нибудь сложных объектов.
б) ЗАПРЕЩЕННЫЕ ВЕТВИ
В реальных объектах практически можно реализовать отнюдь
не любые комбинации значений параметров. В технических системах
существует множество ограничений, запрещающих совместное
использование определенных фрагментов из-за их несоответствия по
каким-либо свойствам. Так, нельзя непосредственно стыковать выход
блока, вырабатывающего инверсию некоторой функции, со входом
другого блока, требующего прямого значения этой функции.
Если на дереве синтеза изображать лишь практически реали-
зуемые сочетания параметров, то часть его ветвей исчезнет, дерево
станет нерегулярным, неполным. Ограничения на сочетания некото-
рых значений параметров, т. е. расположение запрещенных ветвей
дерева в реальных объектах, не подчиняются какому-либо простому,
общему, закону. Эти ограничения специфичны для каждого класса
объектов и известны специалисту, квалифицированному в данной
области. Поэтому при разработке программ автоматического синте-
за положение запрещенных (или, наоборот, реально выполнимых)
ветвей дерева не может быть как-то вычислено, а должно быть
записано в память машины со слов специалистов (группы специали-
стов) данной предметной области.
Между прочим, именно этот материал по обидной традии часто
квалифицируется как «описательный», «не имеющий должного уров-
ня математизации», и это неоправданно ограничивает ему доступ
в книги, а тем более в научные публикации. При этом упускается
из виду то, что граф значений параметров (безразлично, представ-
ленный в виде чертежа, списка или словесного описания) передает
саму структуру класса объектов или явлений, т. е. ту их сторону,
которую невозможно передать на языке формул математического
анализа. Найти же общий вид графа и расположение его запрещен-
ных ветвей в сложных новых объектах отнюдь не проще, чем подо-
брать подходящие математические зависимости для вычисления зна-
чений характеристик.
13
Хранить запрещенные ветви в виде списка нерационально из-за
большого его размера, трудоемкости составления и сложности вне-
сения изменений. После исследования ряда вариантов автор пришел
к выводу, что наиболее рационально хранить информацию о запре-
щенных ветвях непосредственно в морфологическом ящике. Этой
цели и служат поля условий ящика — табл. 1. В поле условий каж-
дого гнезда в виде логических функций записаны условия _реализуе-
мости ветви дерева с данным значением параметра. На дереве
(рис. 1) сплошными линиями показаны ветви, разрешенные полями
условий, приведенных в табл. 1. Запрещенные ветви показаны пунк-
тиром.
Процедура порождения списка возможных вариантов объекта
при наличии в графе запрещенных ветвей работает в общем так же,
как было описано выше при порождении полного списка имен всех
вершин графа, только каждый раз перед подстановкой в формируе-
мое имя объекта очередного значения параметра программа прове-
ряет условие возможности его подстановки. Если условие выпол-
няется, то данное значение вносится в формируемое имя, а если
условие не выполняется, то программа пробует следующее значение
параметра данного гнезда и т. д.
Теперь обратим внимание на то, что в полях характеристик
кроме величин Т и Q присутствуют еще специальные однобитовые
стыковочные характеристики X 1.1 и X 2.1. Стыковочные характе-
ристики отражают некоторые свойства фрагментов, влияющие на
возможность стыковки других фрагментов с данным. Это могут
быть, например, признак фазности выходного сигнала ((прямой или
инверсный), признак допустимой нагрузочной способности фрагмента
(до 10 или 30) и т. д. При использовании стыковочных характери-
стик условия подстановки каждого значения параметра, записанные
в поле условий, могут опираться не только прямо на значения дру-
гих параметров, как например, условие „Л или О" при значении а
параметра П2, но также и на стыковочные характеристики других
параметров (условие X 1.1 при значении ip). С введением стыковоч-
ных характеристик укорачиваются выражения для условии, сокра-
щается машинное время их проверки. Если не пользоваться характе-
ристиками, то многие условия превращаются в списки-перечисления
значений параметра длиной до половины содержимого гнезда. При-
мером такой цепочки может быть условие при значении а: если бы
число значений параметра П1 было не 3, а, скажем, 16 и сумматор а
мог стыковаться лишь с теми восемью сдвигателями П1, которые
имеют парафазный выход, то условие при а состояло бы из восьми
членов, соединенных союзом «или». Если же ввести бинарную сты-
ковочную характеристику сдвигателя «парафазность выхода» X 1.2
с возможными значениями: 1 — парафазный и 0 — однофазный вы-
ход, то условием при а будет лишь один член — ссылка на значение
характеристики X 1.2. Пример набора стыковочных характеристик
реальных фрагментов рассматривается в § б.е при разборе табл. 2.
Важным достоинством использования в условиях применимости
только стыковочных характеристик, а не хамих значений параметра,
является удобство внесения изменений в списки значений парамет-
ров. Если в процессе эксплуатации системы потребуется ввести но-
вое значение какого-либо параметра, достаточно это значение вместе
с его характеристиками и условиями применения один раз вписать
в соответствующее гнездо. После этого процедура порождения будет
автоматически составлять кроме прежних также и все имена объек-
тов с участием нового значения параметров. Аналогично можно
14
вычеркивать устаревшие значения параметров, никак не меняя текст
программы синтеза.
Чтобы принятая процедура последовательного формирования
имен объектов могла работать, условия обязательно должны опи-
раться на уже построенную часть имени, т. е. аргументами условия
должны быть значения параметров или стыковочных характеристик
любых гнезд ящика, но обязательно расположенных левее того гнез-
да, в котором находится это условие. Можно доказать, что это
требование выполнимо при любых сочетаниях запрещенных ветвей
дерева и при любом порядке следования его ярусов, т. е. парамет-
ров в ящике. При этом будет меняться лишь вид выражений для
условий и иногда они могут выглядеть несколько непривычно для
специалиста. У параметра, лежащего в самом левом гнезде (П1),
поля условий не требуется, поскольку в первом ярусе дерева синте-
за запрещенных ветвей не бывает.
Некоторые значения параметров безусловны, т. е. ограничений
на их применение нет. В табл. 1 кроме параметра Ш безусловным
является значение у параметра П2. Стыковочные характеристики
в гнезде параметра ПЗ не нужны, так как нет параметров, стоящих
правее него.
Принятый метод хранения сложных, неправильных графов пу-
тем введения в состав морфологического ящика условий применимо-
сти данного значения параметра оказался очень удобным на прак-
тике. При заполнении морфологического ящика специалисту в каж-
.дый момент времени необходимо в поле своего внимания держать
лишь ограниченное число запретов на стыковку, а именно толь-
ко те запреты, которые относятся к рассматриваемому в дан-
ный момент значению параметра. О запретах на сочетаемость других
значений параметров разработчик может в этот момент не думать и
может даже совершенно не представлять, как выглядит' все дерево
целиком с учетом всех ограничений. Заметим, что это было бы
безусловно необходимо в случае решения хранить запрещенные или
разрешенные ветви непосредственно в виде списка, размещенного
в ЗУ ЭВМ.
Согласно современным представлениям одна из форм хранения
в памяти человека сложных структур — это семантические сети,
а используемая структурна ящика является одной из форм машин-
ного представления простой семантической сети в виде гнездового
списка. Поэтому, специалисты предметной области легко справляют-
ся с заполнением полей условий морфологического ящика, а слож-
ный граф синтеза с большим числом нерегулярных ветвей строит
уже сама программа. Форма введения информации в программу,
близкая к форме, в которой ее помнит сам специалист, и отсутствие
рутинной работы по построению вручную сложного графа являются
достоинствами принятого метода хранения структуры объекта.
Идея использования условий стыковки для хранения деревьев
синтеза с запрещенными ветвями базируется на экспериментально
наблюдаемых общих чертах строения различных объектов, создан-
ных человеком: запрещенные ветви огромного числа объектов рас-
положены не абсолютно случайно. Практически реализуемые соче-
тания значений параметров имеют тенденцию образовывать относи-
тельно компактные группы. Часто наблюдается стремление к неко-
торой регулярности, упорядоченности структуры графа. Поэтому
выражения для условий стыковки значений параметров почти всег-
да оказываются простыми и короткими: каждое условие редко
определяется значениями или характеристиками, принадлежащими
15
более чем двум — четырем различным гнездам. Это также обеспе-
чивает простоту заполнения гнезд ящика при разработке программ.
Программное воплощение морфологического ящика представ-
ляет собой иерархическую списковую структуру и не вызывает ка-
ких-либо проблем у программиста.
в) ОГРАНИЧЕНИЯ ЗАКАЗЧИКА
Все свойства объекта принято делить на внешние характеристи-
ки и внутренние параметры. Внешние характеристики — это то, что
непосредственно интересует заказчика, например время задержки,
объем оборудования, потребляемая мощность и т. п. Внутренние па-
раметры— это свойства объекта, которые, оказывая влияние на
внешние характеристики, сами по себе заказчика не интересуют.
Они играют роль свободных переменных, находящихся в руках раз-
работчика. Выбирая соответствующим образом значения внутренних
параметров, разработчик обеспечивает требуемые значения внешних
характеристик. Для нашего устройства сложения мантисс внутрен-
ними параметрами являются конкретные виды используемых сдвига -
телей и сумматоров. Смысл деления свойств на внешние и внутрен-
ние заключается в различном отношении к ним на разных этапах
проектирования. .Так, входом всей системы синтеза являются внеш-
ние характеристики, а выходом — внутренние параметры, т. е. при
синтезе решается задача: как должен быть построен объект, обла-
дающий заданными свойствами? Входом системы анализа, наоборот,
являются внутренние параметры, а выходом — внешние характери-
стики, т. е. ищется ответ на вопрос — какими свойствами обладает
объект, имеющий заданную структуру?
Это деление не абсолютно. Оно верно лишь для данного кон-
кретного ТЗ, а в ТЗ различных заказчиков на один и тот же
объект некоторые свойства могут выступать то в роли внутренних,
то в роли внешних. Для заказчика, связанного требованиями уни-
фикации или имеющего ограниченные возможности снабжения, та-
кие параметры, как конкретный тип того или иного фрагмента, бу-
дут внешними характеристиками, задаваемыми в ТЗ, а для заказ-
чика, свободного от этих ограничений, те же самые параметры в ТЗ
не будут указаны. Они будут отданы на откуп разработчику, т. е.
окажутся внутренними.
Чтобы заказчик мог самостоятельно задавать ограничения на
состав базовых фрагментов, нужно дать ему возможность исклю-
чать из морфологического ящика любые нежелательные значения
параметров. Для этого в программе автоматического синтеза сум-
маторов принята табличная форма технического задания. Заказчик
заполняет анкету, в которой кроме вопросов, касающихся требуе-
мой разрядности, ограничений на время задержки, объем оборудо-
вания и т. п., приведены списки возможных значений^ всех пара-
метров, характеризующих сумматор. Если какие-либо значения неко-
торых параметров не устраивают заказчика, он вычеркивает их из
списка. На основании этой информации транслятор ТЗ создает, ра-
бочий дубль морфологического ящика, в котором остаются лишь те
значения параметров, которые заказчика устраивают. Только эти
значения будут участвовать в порождении вариантов ОП.
Таким образом, заказчик сам определяет, , какие параметры
в данном акте проектирования будут внутренними, а какие внеш-
ними, причем при любом делении протрамма синтеза остается одной
16
й той же, а запреты, накладываемые на значения параметров, не
только не усложняют процесс синтеза, но даже несколько упрощают
его, поскольку уменьшают объем перебора.
Методы построения объектов, основанные на целенаправленных
алгоритмах, не дают возможности заказчику произвольно запрещать
применение любых значений параметров, поскольку всякий строгий
алгоритм всегда имеет четко регламентированные списки входных и
выходных переменных. Поэтому, если требовать, чтобы какие-то
выходные переменные могли становиться входными и наоборот, то
для каждой мыслимой комбинации входных и выходных переменных
придется создавать свой алгоритм направленного построения объек-
та, «хорошего» в данном конкретном случае. Метод же, основанный
на исчислении, в нашем случае — на комбинировании фрагментов,
напротив, легко позволяет заказчику по своему усмотрению делить
параметры, описывающие объект, например базовые фрагменты —
на внешние, значения которых он задает сам, и внутренние, значе-
ния которых выбирает программа. Оставленные заказчиком степени
свободы программа использует для минимизации значения какой-
либо выбранной заказчиком характеристики, например аппаратур-
ных затрат.
Для всех порожденных вариантов объекта вычисляются значе-
ния характеристик, по которым будет выполняться отбор. В данной
книге принято, что такими характеристиками являются время за-
держки Т и аппаратурные затраты Q. Характеристик может быть и
больше. Вычисление внешних характеристик производится блоком
программы, содержащим набор формул. Часть значений параметров
являются аргументами этих формул, например число разрядов сум-
матора. Значения других параметров определяют вид формулы. Так,
время задержки Т для сумматоров, отличающихся значениями па-
раметра «Вид переноса» (параллельный или последовательный), вы-
числяется по совершенно различным формулам. Каждая формула
снабжается условиями ее применимости, и набор формул для вы-
числения каждой характеристики образует список-гнездо, аналогич-
ное рассмотренным гнездам морфологического ящика. Составление
и программирование расчетных формул — это наиболее привычная
и хорошо освещенная в литературе область деятельности разработ-
чика. Поэтому в данной главе не будет уделяться внимания про-
граммному блоку вычисления характеристик. Формулы для расчета
Т и Q сумматоров различного типа будут приведены в § 5—12.
В программе автоматического синтеза полезно выделить две со-
ставляющие: инвариантную, т. е. не зависящую от конкретного типа
объекта проектирования, общую для довольно широкого класса
объектов, и предметно-ориентированную, т. е. содержащую специ-
фическую информацию об объектах конкретного типа (например,
именно о сумматорах, именно о счетчиках и т. д.). Инвариантными
являются сама структура морфологического ящика, процедура фор-
мирования имени очередного варианта объекта, процедуры проверки
условий и исключения из ящика запрещенных заказчиком значений
параметров. Эти программы можно составлять, совершенно не зная
свойств ОП, для которого они предназначены.
Предметно-ориентированной является информация, содержащая-
ся в морфологическом ящике: имена параметров, наименования их
значений, выражения для условий применимости, характеристики
значений параметров, формулы для вычисления < характеристик всего
объекта. Эта информация специфична для каждого вида объекта, и
получить ее можно лишь от квалифицированного специалиста кон-
2—1Ш 17
кретной области. Вывести ее с помощью каких-либо формул или
общих соображений, не имея знаний о данной предметной области,
невозможно.
При разработке пакетов программ автоматического синтеза не-
скольких объектов рационально инвариантную часть сделать в виде
универсальной программы и заполнять ее проблемно-ориентирован-
ной информацией, относящейся к каждому объекту.
г) СИНТАКСИС И СЕМАНТИКА СИНТЕЗА
Интересно отметить, что принцип описания объектов путем за-
дания возможных значений параметров, записанных в гнездах мор-
фологического ящика, очень близок к логистике по Черчу и к струк-
туре исследованных Н. Хомским порождающих грамматик. Все мно-
жество объектов данного класса вместе с законами их строения
(морфологией) и порождения можно рассматривать как некоторый
язык (о формальных языках и грамматиках см., например, [Л. 4]).
Проектируемый объект — это начальный символ языка. Имена па-
раметров — «сдвигатель вправо», «сумматор», «сдвигатель влево» —
соответствуют нетерминальным символам языка, а значения пара-
метров, перечисленные в гнездах ящика, — терминальным символом.
Последовательность расположения ярусов дерева синтеза задается
правилами подстановки грамматики языка. Легко показать, что лю-
бой граф с чередующимися вершинами И и ИЛИ соответствует
контекстно-свободной грамматике Хомского, а рассматриваемые
в этой книжке деревья синтеза являются простейшими частными
случаями И-ИЛИ графа (описание объекта должно включать все
наименования параметров, а для каждого наименования допустимо
значение одно, или другое и т. д.
Отмеченная близость структур в двух, казалось бы, различных
областях человеческой деятельности свидетельствует, видимо, о глу-
боком сходстве интеллектуальных процессов, к которым в конце
концов сводятся как конструирование новых технических объектов,
так и построение фраз языка. Но в силу сложившихся традиций
инженерам больше понятна идеология морфологического ящика,
а программистам — идеология грамматик языка.. Поэтому отмечен-
ная аналогия окажется полезной при совместной работе специали-
стов предметной области и программистов над программами авто-
матического синтеза. Кроме того, лингвистический подход к процессу
синтеза позволит применить уже существующий аппарат формаль-
ных грамматик для построения более сильных, многоуровневых про-
грамм автоматического синтеза, откровенно эксплуатирующих ре-
курсивную природу грамматик и способных поэтому проектировать
весьма сложные объекты.
Исследователи языков кроме понятия «грамматика» (синтаксис)
вводят еще понятие «семантика» — смыслового содержания предло-
жения. Осмысленные предложения образуют лишь часть всего мно-
жества грамматически правильно построенных фраз. Другая часть
грамматически правильных предложений бессмысленна. В проекти-
ровании аналогом бессмысленных фраз являются имена объектов,
образованные при движении по запрещенным ветвям дерева синте-
за, изображенного на рис. 1. Эти имена вполне допустимы с точки
зрения возможности комбинирования (грамматики), но они нереали-
зуемы, невыполнимы, т. е. в данном случае бессмысленны. Правила
построения лишь осмысленных комбинаций параметров, т. е. лишь
18
реально выполнимых объектов, предложено записывать в соответст-
вующем поле гнезда в виде условий применимости данного значения
параметра (см. табл. 1). Введение поля условий применимости зна-
чений параметров является одним из возможных способов формаль-
ного задания осмысленных комбинаций фрагментов объекта, или,
другими словами, возможным способом формализации семантики
языка синтеза.
д) О КАЧЕСТВЕ ПОРОЖДАЕМЫХ ОБЪЕКТОВ
Отметим два характерных критических замечания, которые
иногда высказываются в адрес метода вариантного синтеза:
I. Если набор фрагментов и законы комбинирования заданы, то
тем самым все возможные варианты уже предопределены составите-
лем программы. Где же здесь автоматическое проектирование?
Возражение вызвано смешением понятий «способ задания множе-
ства элементов» и «нахождение элемента- данного множества, обла-
дающего определенными свойствами». Если говорить строго, то по
этому поводу А. Чёрчем еще в 30-е годы в теории алгоритмов
доказано, что существуют перечислимые, но не разрешимые множе-
ства. Другими словами, на языке более известных понятий можно
утверждать, что любое написанное в ближайшие годы стихотворение
должно состоять из известных слов, набор которых ограничен и
которые соединены не * менее известными правилами грамматики.
Однако от этого в общем верного утверждения еще очень далеко
до создания конкретного хорошего стихотворения. Точно так же
в нашем случае в программу вводятся лишь словарь, грамматика,
семантика и критерий отбора по качеству. Каких-либо конкретных
правил «как сделать хорошо» мы в программу не вводим. Более
того, мы имеем право совершенно не знать этих ' правил.
С чисто практической точки зрения, когда число вариантов воз-
растает до сотен и тысяч, а характеристики каждого объекта вы-
являются лишь в результате расчета, человек уже не в силах доста-
точно быстро не только назвать наилучший объект, но даже хотя
бы перечислить без ошибок все возможные варианты. В этом случае
перед ним стоит трудная задача и ответ он воспринимает как но-
вую для себя информацию независимо от того, кто его получил, —
человек-исполнитель или. программа. Понятие «новое» нё абсолютно
и в зависимости от точки зрения может трактоваться по-разному.
Если в классе достаточно сложных объектов условиться считать,
как это принято в системе патентования, что новый и полезный —
это такой объект, который, отвечая практическим запросам, отли-
чается от созданных ранее, и притом в лучшую сторону, то за про-
граммой вправе признать возможность создания нового.
II. Программа использует лишь жестко заданный, ограниченный
набор фрагментов и способов их соединения, а человек, используя
свои интеллектуальные способности, может расширить этот набор,
поэтому объекты, порожденные программой, будут всегда примитив-
нее и хуже объектов, созданных инженером. Это замечание отно-
сится уже к практической ценности метода вариантного синтеза, и
по его поводу рассмотрим три момента.
1. Замечание верно, если дело касается науки или искусства.
Однако в данном случае рассматривается конструкторская работа,
т. е. синтез технических объектов, фрагментами которых также в по-
давляющем большинстве являются промышленные изделия. А это
значит, что набор возможных фрагментов определяется не столько
2* 19
интеллектом разработчика, сколько каталогами предприятий-изгото-
вителей и действующими стандартами. Действительно, обычный раз-
работчик серийной аппаратуры не может выйти за рамки выпускае-
мых промышленностью микросхем, транзисторов и других радиоде-
талей или нарушить действующие стандарты на размещение дета-
лей, выполнение соединений на платах и т. д.
Большую свободу разработчику предоставляют наборы способов
построения схем, наборы различных технических принципов, при-
емов, поскольку ассортимент их не является принудительным. Но
эти наборы в общем известны и описаны в технической литературе,
а количество различных способов в каждом наборе весьма ограни-
чено. Если попробовать оценить, сколько способов ускорения пробе-
га переноса в сумматоре или ускорения умножения, деления, реаль-
но пробует применить инженер сегодня в своих разработках, то
окажется, что число их редко превышает 10 и почти никогда — 20.
Поэтому в области массовых технических разработок с точки зрения
возможности использовать широкое разнообразие фрагментов и прин-
ципов программа практически не уступает человеку. Кроме того, не-
большое число реально используемых фрагментов является сущест-
венной предпосылкой практической осуществимоети полного перебора:
поскольку число фрагментов невелико, то и полное число вариантов
очень часто оказывается в пределах возможностей машинного пе-
ребора.
2. При разработке программы есть возможность прибегнуть
к услугам коллектива очень квалифицированных специалистов, по-
этому в тех случаях, когда набор фрагментов и принципов может
выходить за рамки каталогов, стандартов и массовой технической
литературы, в программу будет заложен более обширный и качест-
венный набор, чем тот, которым реально пользуется огромная армия
инженеров средней квалификации.
3. Любая разумно построенная программная система имеет
средства для внесения изменений. По мере освоения промышленно-
стью новых фрагментов и появления в литературе новых способов
построения'схем администратор системы может вводить их в состав
программы. Принятый метод хранения множества объектов в виде
морфологического ящика позволяет очень легко расширять список
базовых фрагментов.
Таким образом, во многих областях технического проектирова-
ния инженер средней квалификации практически не имеет преиму-
ществ перед хорошо составленной и поддерживаемой программой
с точки зрения числа и качества используемых фрагментов и спо-
собов их соединения. Что же касается точности хранения один раз
введенного материала, скорости порождения вариантов и вычисле-
ния их характеристик, то здесь преимущества ЭВМ очевидны. Ска-
занное подтверждают и результаты экспериментов с программой
синтеза сумматоров. Программа, построенная на основе описанных
принципов (см. [Л. 5]), синтезировала сумматоры во много раз
быстрее человека (за час и менее), при этом по качеству получен-
ные схемы были соизмеримы со схемами, созданными весьма квали-
фицированными разработчиками, и были заметно лучше сумматоров,
построенных средним инженером.
3. ОПТИМАЛЬНОСТЬ ПРИ НЕСКОЛЬКИХ КРИТЕРИЯХ
а) ЦЕЛЕВЫЕ ФУНКЦИИ ЗАКАЗЧИКА
В ТЗ заказчиков различными могут быть не только списки за-
прещенных или, наоборот, желательных фрагментов, но и требования
к сочетанию значений выходных характеристик. Вот примеры типич-
ных заданий на значения выходных характеристик функциональных
узлов определенной разрядности: «Минимально возможное время
задержки», «Время задержки не более заданного и при этом мини-
мальны аппаратурные затраты», «Минимальное значение произве-
дения времени задержки на аппаратурные затраты», «Минимально
возможные аппаратурные затраты». Важным достоинством методов,
основанных на ненаправленном комбинировании значений парамет*
ров, в частности метода полного перебора, является их универсаль-
ность по отношению к любому виду задания значений внешних ха-
рактеристик. Действительно, программа порождения вариантов и
вычисления их характеристик всего одна и работает она всегда
одинаково. Только после окончания ее работы на этапе отбора по-
рожденные схемы проходят через фильтр, настроенный в соответст-
вии с конкретными комбинациями выходных характеристик, указан-
ными в ТЗ. Если бы для автоматического построения схемы был
принят принцип жесткого, целенаправленного алгоритма, то почти
для каждого из приведенных выше примеров формулировки задания
пришлось бы строить свою процедуру, поскольку для каждой фор-
мулировки «хорошими» оказываются решения из совершенно разных
областей пространства параметров. Если учесть, что различных тре-
бований на комбинации характеристик может быть очень много, то
становится очевидным, что с точки зрения разнообразия обслужи-
ваемых формулировок задания метод полного перебора не имеет
себе равных.
б) ОПТИМАЛЬНОСТЬ ПО ПАРЕТО
На рис. 2 показано некоторое множество объектов. Объекты
изображены в виде точек на плоскости характеристик, важных для
заказчика — времени задержки Т и аппаратурных затрат Q. По
остальным важным с точки зрения заказчика показателям все
объекты предполагаются одинаковыми. Рассмотрим пару точек 2
и 5. Объект 5 хуже объекта 2, так как аппаратурные затраты у него
такие же, как и у объекта 2, а вре-
мя задержки больше. Аналогично
объект 6 хуже объекта 3. Тем более
плохими будут объекты 7—10, по-
скольку для каждого из них найдет-
ся другой объект, который лучше
данного и по Г, и по 0 сразу. Объ-
екты* /—4 образуют группу объек-
тов, не сравнимых между собой по
Т и Q: в любой паре один объект
Рис. 2. Сравнение объектов по двум
характеристикам.
/, 2, 3, 4 — объекты, оптимальные по Па-
рето.
7
8*
10
о
®
В
2*
®
21
лучше другого по одной характеристике, но хуже по другой.
Такая группа объектов, в которой невозможно, переходя от
одного объекта к другому, улучшать значение одной характеристи-
ки, не ухудшая при этом значения никакой другой, называется груп-
пой объектов, оптимальных по Парёто или просто «группой Паре-
то». Эти объекты образуют группу своего рода «лучших представи-
телей» всего множества объектов. Все остальные заведомо хуже
тех, что вошли в группу Парёто. Среди объектов, оптимальных по
Парёто (рис. 2), можно выделить две характерные точки: / — са-
мый быстрый объект и 4 — самый дешевый. Группу Парёто можно
выделить не только при двух, но и при любом большем числе ха-
рактеристик, важно только, чтобы для каждой характеристики
в отдельности были определены направления «хорошо» и «плохо».
Так, для трех характеристик — Г, Q и потребляемой мощности Р —
все множество объектов образует трехмерное объемное «облако».
Не претендуя на строгость, можно считать, что в группу Парёто
войдут объекты, лежащие в пограничном слое «облака», обращенном
к началу координат. Подробнее об оптимальности по Парето можно
прочесть в [Л. 2]. Многомерные задачи в данном случае принци-
пиально не отличаются от двумерных, поэтому в дальнейшем для
удобства графической иллюстрации будут рассматривать простран-
ства двух характеристик.
Понятие оптимальности по Парето оказывается во многих слу-
чаях очень удобным. Вот некоторые соображения, в связи с кото-
рыми используется понятие.
1. Если появилось некое новое множество объектов, из которых
предполагается компоновать более сложные объекты, то во многих
случаях допустимо для дальнейшего использования в качестве ба-
зовых фрагментов оставлять не все объекты, а лишь объекты, опти-
мальные по Парето. В результате списки базовых фрагментов ока-
зываются очень короткими, что значительно сокращает как размер
массива памяти, так и объем дальнейшей работы. Базовые фрагмен-
ты сумматоров, описанные в этой книге, были отобраны именно по
такому принципу.
2. Еще встречаются иногда в "некоторых ТЗ требования типа
«разработать логический узел, обеспечивающий минимальную вре-
менную задержку при минимальных аппаратурных затратах». Из
рис. 2 ясно, что подобные формулировки бессмысленны.
3. Широко распространены формулировки ТЗ, в которых за-
даются граничные значения по всем характеристикам: Г^Гтз,
^Qt3 . При этом, поскольку заказчику, как правило, не известно
положение области Парето, вероятность того, что значения характе-
ристик, указанные в ТЗ, попадут прямо в нее, очень мала. Скорее
всего, требования ТЗ попадут или левее и ниже границы Парето
(точка А на рис. 2), где объектов не существует вообще (требова-
ния ТЗ завышены, невыполнимы), или правее и выше этой границы,
в зону плохих решений (точка В рис. 2: требования ТЗ занижены,
ТЗ допускает построение не лучших объектов). Подобная форма за-
дания часто оправдана при работе с человеком-проектировщиком,
но при работе с программой автоматического синтеза рациональнее
задавать в ТЗ ограничения не по абсолютно всем характеристикам,
а по всем, кроме одной, и при этом потребовать минимизации зна-
чения этой последней характеристики. Так," при двух характеристи-
ках Т и Q возможны два варианта задания: Т^.ТТЗ, при этом
минимизировать Q, и Q^QT3» при этом минимизировать Т. При
22
такой формулировке задания программа будет выдавать решения,
наилучшие из возможных при использовании данных принципов и
фрагментов. Нетрудно заметить (рис. 2), что эти решения всегда
принадлежат группе Парето. Не составляют исключения и экстре-
мальные формулировки ТЗ, требующие нахождения объектов с ми-
нимально возможными значениями Т или Q.
4. На этапах эскизного проектирования и при выполнении иссле-
довательских работ распространены ТЗ, где требуется минимизиро-
вать некоторую функцию от внешних характеристик, например
Ui=WiT+W2Q; U2=TQ.
Объекты, отвечающие этим требованиям, также входят в состав
оптимальных по Парето.
5. Для подбора оптимальных пар взаимодействующих блоков
(см. § 4,ж) необходимо получение всей группы Парето.
Оказывается, что при весьма широком диапазоне практических
формулировок ТЗ искомые объекты всегда принадлежат группе
Парето, и поэтому рационально ввести еще одну операцию, не за-
висимую от вида ТЗ, — операцию выделения группы Парето. Имен-
но эту группу, а не весь массив порожденных гипотез, имеет смысл
рассматривать как продукцию универсальной части программ синте-
за. Она будет служить исходным материалом для программ филь-
трации на следующем, последнем этапе, когда происходит выделение
объекта, наилучшего с точки зрения конкретной целевой функции
конкретного. ТЗ. Ценно здесь то, что объектов, оптимальных по
Парето, и участвующих в последней специфической процедуре филь-
трации, будет значительно меньше, чем всех порожденных гипотез.
Объекты, не вошедшие в группу Парето, — это внутренние издерж-
ки САПР, которые не требуется сохранять, а тем более выводить
на печать (кроме режимов отладки и некоторых специфических
заданий). Это — аналог неудачных решений человека-конструктора,
от которых он сам быстро отказывается.
Список объектов, оптимальных по Парето, формируется по мере
синтеза объектов-гипотез и вычисления их характеристик. Каждый
вновь порожденный объект сравнивается сначала по значению одной,
затем — другой характеристики и т. д. — с объектами, уже занесен-
ными в список. В зависимости от результатов сравнения новый
объект или дополняет список, т. е. вносится в него на соответствую-
щее место, или замещает в этом списке один или несколько объек-
тов, или, что бывает чаще всего, забывается как не принадлежащий
к группе Парето.
Заметим, что для каждого конкретного сочетания запретов за-
казчика на значения внутренних параметров множество Парето бу:
дет свое. Это замечание, во-первых, отвечает на распространенный
вопрос — а зачем нужна программная система автоматического син-
теза?- Нельзя ли один раз составить список объектов, оптимальных
по Парето, и снабдить им всех потенциальных заказчиков? Во-вто-
рых, из этого замечания следует, что программа синтеза, построен-
ная на основе целенаправленного алгоритма, выводящего в опреде-
ленную область пространства решений, годится только для жестко
заданного'набора значений параметров (базовых фрагментов). Если
часть из них заказчик запретит или в систему буДут введены новые
фрагменты, то «хорошей» станет уже другая область, и для выхода
в нее нужно будет создавать новый алгоритм. В противоположность
этому метод перебора универсален по отношению к любой комбина-
ции дополнений или запретов на значения любых параметров.
23
4. МЕТОДЫ СОКРАЩЕНИЯ ПЕРЕБОРА
а) ВЛИЯНИЕ ЗАПРЕЩЕННЫХ ВЕТВЕЙ
Вернемся к вопросу об объеме перебора при вариантном синте-
зе. Опасение, что расход машинного времени при полном переборе
вариантов может выйти за рамки разумно допустимых пределов,
действительно обоснованно. В связи с этим прежде всего обратим
внимание на то, что дерево синтеза имеет запрещенные ветви, отче-
го реальный объем перебора оказывается значительно меньше рас-
пространенной его оценки, представляющей произведение чисел зна-
чений всех параметров. Так, если объект описывается восемью па-
раметрами, каждый из которых имеет* по шесть значений, то число
мыслимых сочетаний значений параметров составляет б8, что превы-
шает 1,6 «10е. Перебор такого числа вариантов лежит сегодня за
пределами возможностей финансирования разработок логических
схем. В то же время, если из-за физических ограничений на сочетае-
мость некоторых значений параметров при каждом просмотре гнезда
в среднем половина значений параметров не привлекается к порож-
дению объектов, число вариантов будет уже З8, т. е. около 6,5-103.
При синтезе логических, схем это соответствует примерно 1 ч
работы ЭВМ среднего класса. Если к тому же заказчик по каким-
то своим соображениям запретит применение 1/3 заложенных в си-
стему фрагментов, то число вариантов сократится более чем в 25' раз
и упадет до 28=256, а машинное время — до нескольких минут.
К * сожалению, оценить реальный объем перебора невозможно, не
выполнив предварительно значительной работы по формулировке
условий применимости различных значений параметров, т. е. не за-
полнив весь морфологический ящик.
б) СОКРАЩЕНИЕ ПЕРЕБОРА. И АПРИОРНЫЕ СВЕДЕНИЯ
Известно, что человек в процессе поиска решения не переби-
рает всех вариантов, поэтому исключительно заманчивой выглядит
перспектива снабдить такими же способностями и программу. Рас-
смотрим в связи с этим некоторые общие соображения. Задача син-
теза хороших вариантов аналогична задаче успешного прохожде-
ния древовидного лабиринта, в котором несколько (или даже один)
из последних коридоров имеют выход. Если лабиринт абсолютно
неизвестный, то единственным способом решения задачи будет про-
стой перебор вариантов независимо от интеллектуального уровня
блуждающего. Чтобы иметь возможность сократить перебор, нужно
заранее что-то знать о лабиринте.
Эти знания могут носить двоякий характер. Во-первых, весь
лабиринт может иметь какие-то особые, удобные для нас свойства.
Пусть, например, известно, что к выходу могут привести лишь ко-
ридоры, идущие вверх, а те, что идут вниз, всегда заканчиваются
тупиками. В этой ситуации появляется возможность на некоторых
развилках делать уже не слепой, а. обоснованный выбор. Во-вто-
рых, из опыта прошлых блужданий именно в этом лабиринте нам
может быть точно известно расположение ходов в некоторых его
областях. В любом случае для сокращения перебора необходимо
иметь не совсем «черный» лабиринт, т. е. обязательно кое-что знать
о нем заранее.
24
в) ОСОБЫЕ СВОЙСТВА ПРОСТРАНСТВА ПАРАМЕТРОВ
Из методов сокращения перебора, использующих особые свой-
ства пространства параметров (лабиринта), наибольшей популярно-
стью пользуются методы линейного программирования и последо-
вательного конструирования. Для применения метода линейного
программирования необходимо, чтобы пространство параметров
было линейным, т. е. чтобы внешние характеристики линейно за-
висели от значений параметров. В задачах синтеза логических схем
достаточно сложных узлов требования линейности практически ни-
когда не выполняются и этот в общем сильный и удобный метод
не может быть применен.
Второй метод, который дает хорошие результаты в некоторых
областях проектирования, основан на возможности упорядочить
по степени влияния на внешние характеристики как сами парамет-
ры, так и значения каждого параметра. Это использовано, напри-
мер, в [20]. Если такое упорядочение проведено, то поиск решения
можно осуществлять путем последовательного конструирования объ-
екта в несколько этапов, выбирая каждый раз значение лишь одного
параметра. Число проб при этом оказывается близким к двоичному
логарифму полного числа мыслимых вариантов, т* е. сокращение
перебора может быть весьма значительным.
Требование упорядочения самих параметров и их .значений по
степени влияния на внешнюю характеристику равносильно требо-
ванию монотонности зависимости внешней характеристики от зна-
чений параметров. В' реальных сколько-нибудь сложных объектах
и, в частности, в функциональных схемах это требование настолько
часто нарушается, что применять метод последовательного конструи-
рования становится невозможно. Недостаток этого метода в слу-
чаях, когда его можно применить, — его жесткая ориентированность
на оптимизацию лишь какой-то одной внешней.характеристики. Для
поиска ОП по значению другой характеристики все упорядочение
будет уже совершенно иным.
С отмеченными выше и другими хорошо исследованными в ма-
тематике методами сокращения перебора читатель можеть ознако-
миться, например, по [10]. В задачах синтеза логических схем
сложных операционных узлов эти методы могут найти лишь весь-
ма ограниченное применение, а чаще неприменимы вообще, потому
что в их основе лежит предположение о том, что исследуемое про-
странство обладает некоторыми простыми и удобными свойствами,
а в рассматриваемом случае это предположение, к сожалению, не
подтверждается.
г) ЭВРИСТИКИ
Квалифицированный разработчик, помня результаты сделанных
прежде попыток, знает много частных рекомендаций, относящихся
к использованию конкретных сочетаний фрагментов, числовых па-
раметров и т. п. Э-ти знания не образуют единой цельной картины,
не обладают свойством массовости, и поэтому они не могут претен-
довать на то, чтобы называться алгоритмом. Такие знания о ло-
кальных свойствах в узкой конкретной области и основанные на
них частные рекомендации принято называть эвристиками. По мере
накопления опыта эти «островки известности» образуют довольно
густую сеть в пространстве решений, в результате чего число не-
?5
обходимых проб и ошибок при поиске очередного нового решения
заметно сокращается. Степенью густоты этой сети в большой мере
и отличается опытный разработчик схем, и вообще любой мастер
своего дела, от молодого специалиста.
Используя понятие о дереве синтеза, можно сказать, что эври-
стики— это знания относительно рациональности применения неко-
торых сочетаний значений параметров (некоторых ветвей дерева)
для получения значений характеристик, заданных в ТЗ. Так, если
заказчику функционального узла требуется в основном экономич-
ность по затратам оборудования, а время задержки безразлично,
то на время выполнения его заказа можно исключить из зоны по-
иска область параллельных схем: искомая схема наверняка будет
последовательной.
Подобные эвристики должны при определенных формулировках
ТЗ не включать в порождаемые варианты некоторые сочетания
значений параметров (некоторые ветви дерева), уменьшая, таким
образом, объем перебора. Функции исключения ветвей можно воз-
ложить на уже знакомые нам поля условий в гнездах морфологи-
ческого ящика с той лишь разницей, что раньше исключались фи-
зически неосуществимые сочетания, а теперь — просто нерациональ-
ные. В программе поле условий, кодирующих эвристики, лучше
отделить от поля условий, определяющих реализуемость, поскольку
методы работы с этими полями различны. Поля условий физиче-
ской реализуемости должны заполняться обязательно, и притом еще
на этапе создания программной системы, после чего должны быть
защищены по записи. Поля условий рациональных сочетаний мо-
гут заполняться также в процессе создания системы, но при не-
достатке знаний заполнять их не обязательно. С пустыми или не
полностью заполненными полями система будет выдавать заказчику
объекты ничуть не худшие, только делать это она будет медленнее.
Условия в этих полях можно постепенно дополнять / в процессе
эксплуатации системы по мере накопления и анализа опыта про-
ектирования. За сокращение перебора приходится платить работой
по исследованию пространства и представлению полученной инфор-
мации в форме, удобной для использования программой синтеза.
Видимо, эта работа будет оправдана для тех областей простран-
ства решений, к которым заказчики обращаются часто, и не будет
оправдана в противных случаях. Пределом на этом пути будет
проведение очень детальных исследований пространства решений
и формулирование четких правил (алгоритмов), позволяющих при
некотором разнообразии начальных условий целенаправленно, без
поиска выходить на лучший вариант.
д) ТЕКУЩИЕ ОЦЕНКИ
В ТЗ часть значений внешних характеристик задается в виде
ограничений. В то же время многие внешние характеристики яв-
ляются аддитивными функциями относительно целой группы пара-
метров. Так, число корпусов, потребляемая мощность, масса, стои-
мость, а часто и время задержки для всей схемы получаются сум-
мированием этих величин для всех блоков, составляющих объект.
Тогда программу синтеза можно построить так, чтобы вычисление
внешних характеристик и сравнение результата с ТЗ выполнялись
не после того, как синтез варианта уже окончен, а в несколько эта-
пов в процессе синтеза по мере подстановки фрагментов. Как толь?-
2§
ко значение какой-либо из внешних характеристик превысит огра-
ничение ТЗ, синтез данного варианта прекратится и произойдет
смена значения последнего параметра, на котором оборвался син-
тез. Существенно здесь то, что из процесса порождения исключается
не один вариант, а целый куст вариантов, начинающийся с той
ветви, которая вызвала превышение ограничения. Чем раньше это
произошло, тем ощутимее сокращение перебора.
Метод применим и в том случае, когда в ТЗ задано не огра-
ничение на значение данной характеристики, а требование, миними-
зации (максимизации) этого значения. В этом случае эталоном^
с которым сравнивается порождаемый вариант, будет не значение,
записанное в ТЗ, а значение характеристики варианта, наилучшего
из порожденных на данный момент. Этот вариант хранится в спе-
циальной ячейке программы и замещается тем из порождаемых
вариантов, который оказался еще лучше.
Препятствием на пути применения, этого метода является
усложнение ведущей программы, а также то, что массив расчетных
формул часто не помещается в оперативной памяти ЭВМ вместе
с программой порождения вариантов. В этом случае из-за огром-
ного числа обменов между 'дисками или барабанами и оперативной
памятью настолько замедлится работа, что сведется на нет выиг-
рыш от сокращения перебора. Компромиссным решением будет при-
менение для текущих оценок простых приближенных формул
с асимметричным расположением погрешности, чтобы1 ошибочное
вычеркивание хороших вариантов было исключено. Число вари-
антов, порождаемых с учетом такой предварительной отбраковки и
предназначенных для последующей строгой оценки по точным фор-
мулам, оказывается во много раз меньше числа вариантов, порож-
даемых программой, которая не способна производить текущие
оценки в процессе своего творчества.
е) СЛУЧАЙНЫЙ ПОИСК
Объем перебора можно сократить, если порождать не все раз-
решенные деревом синтеза варианты, а только часть из них. На-
пример, можно выбирать значения параметров не подряд, по счет-
чику, как при полном переборе, а с помощью датчика случайных
чисел. Если отказаться от полного перебора вариантов, не имея
при этом достаточно полной априорной информации о свойствах
пространства решений, то приходится сразу же отказаться и от
требования найти объект, наилучший из возможных, поскольку
точное расположение его не известно. Возможность потери хороших
объектов, т. е. ухудшение в среднем результата проектирования,
и является в данном случае платой за сокращение перебора.
При случайном поиске можно использовать три критерия для
останова программы, ведущей синтез: 1) выработан отпущенный ре-
сурс времени или числа проб; на выход выдается наилучший из
объектов, полученных за время работы; 2) получен объект, каче-
ство которого превышает заданный уровень (например, уровень ка-
чества объекта, который был создан ранее или в другой организа-
ции); 3) темп роста качества в получаемой последовательности объ-
ектов, где каждый член является наилучшим из всех, порожденных
до него, упал ниже заданного предела.
Идеология неполного перебора и только что перечисленные
критерии прекращения поиска широко используются в практике
27
технического проектирования из-за необозримо огромного числа
вариантов, т. е. слишком большой сложности реальных техниче-
ских объектов. Так, на проектирование уникальных в своем роде
изделий выделяется некоторый ресурс времени и денег, и наилуч-
ший из полученных за это время вариантов принимается в качестве
проекта. При проектировании нового варианта какого-либо рас-
пространенного изделия задача считается выполненной, если каче-
ство полученного изделия превысило качество существующих.
Такой же принцип лежит и в основе патентного дела. Поток
последующих усовершенствований убеждает в том, что практически
в любом проекте, к сожалению, так и не удастся выйти* на точку
абсолютного максимума.
В нрограммах случайного поиска исходные вероятности выбора
значений параметров не обязательно должны быть одинаковыми.
Эти вероятности могут отражать представление разработчика про-
граммы о частоте встречаемости различных значений в удачных
вариантах объектов. В таких программах можно сравнительно лег-
ко вводить простейшие, элементы самообучения. Для этого после
выдачи заказчику наилучшего из синтезированных вариантов спе-
циальный программный модуль должен несколько увеличить веро-
ятность последующего выбора тех значений параметров, которые
вошли в состав этого объекта". Такое самообучение весьма эффек-
тивно, если заказчики в основном работают в ограниченной обла-
сти поля значений внешних характеристик (например, их интересу-
ют только быстрые многоразрядные сумматоры). Некоторые про-
граммы с подобными методами^ самообучения описаны в [12].
Еще раз отметим, что применение методов случайного поиска
всегда сопряжено с возможностью потери хороших решений, а как
раз именно это очень нежелательно при проектировании аппарату-
ры, предназначенной для серийного, а тем более массового произ-
водства.
Возможность применения методов сокращения перебора нагляд-
но иллюстрирует целесообразность разбиения процесса проектиро-
вания логических схем (а также и многих других объектов) на
две самостоятельные задачи:
1) выявление грамматики, а также в принятом здесь понима-
нии и семантики, дающих принципиальную возможность формально
и достаточно компактно описать любой вариант объекта заданного
класса, разумеется, в пределах принятых ограничений на дета-
лизацию и возможное разнообразие (другими словами — построе-
ние морфологического ящика);
2) выбор правил, по которым из заданного грамматикой мно-
жества будет выбираться и синтезироваться подмножество объек-
тов-гипотез, предназначенных для сравнения по их характеристи-
кам. В частности при использовании полного перебора, указанное
подмножество совпадает со всем множеством, но в общем случае
это не обязательно.
ж) СТРУЮУРИРОВАНИЕ ОБЪЕКТА
Объем перебора при синтезе можно значительно сократить пу-
тем представления объекта в виде структуры из более мелких еди-
ниц и многоэтапной организации проектирования. Пусть нам уда-
лось разделить ОП на такие структурные единицы, что значения
внешних характеристик всего ОП определяются как суммы значе-
28
ний этих характеристик для каждой такой единицы. Как правило,
это легко удается, если характеристики представляют собой уже
упоминавшиеся .аддитивные величины — объем оборудования, стои-
мость, время задержки и т. д.
Разделив ОП на несколько структурных единиц (допустим, на
несколько узлов), на I этапе синтезируют все единицы (узлы) по
отдельности независимо друг от друга. При этом получается какое-
то количество вариантов узла каждого типа. На II этапе комбини-
руют между собой полученные варианты этих узлов, синтезируя
тем самым различные варианты уже всего объекта, при этом типы
узлов играют роль параметров для всего объекта, а различные
варианты узла «каждого типа — роль значений' этих параметров.
Суть предлагаемого метода заключается в том, что на II этапе
в процедуре комбинирования участвуют отнюдь не все синтезиро-
ванные узлы, а лишь узлы, оптимальные по Парето в пространстве
внешних характеристик. Заметим, что при ограничениях на возмож-
ности стыковки узлов в процедуре комбинирования могут участво-
вать и некоторые близкие соседи группы Парето, но для упроще-
ния изложения основного принципа эти детали рассматриваться не
будут. Число перспективных узлов, т. е. узлов, оптимальных по
Парето, обычно во много раз меньше полного множества синтези-
рованных узлов. Так, например, по результатам экспериментов над
программами синтеза функциональных схем из 1000 объектов лишь
около 30 принадлежали группе Парето в пространстве двух ха-
рактеристик.
В качестве иллюстрации предлагаемого принципа рассмотрим
ОПг описываемый шестью параметрами, каждый из которых имеет
10 значений. Тогда объем перебора при обычном, одноэтапном син-
тезе составит 106 вариантов. Рассмотрим двухэтапный процесс син-
теза того же объекта. Пусть нам удалось представить объект как
структуру из двух узлов — узел типа 1 и$ узел типа 2, причем из
шести имеющихся параметров три характеризуют узел 1, а остав-
шиеся три — узел 2. Тогда объем перебора при синтезе каждого
из двух узлов составит 103 вариантов, из которых около 30 будут
оптимальны по Парето. Теперь оценим объем перебора на II этапе
при синтезе всего объекта из «лучших представителей» узлов 1 и 2
типа: 30^103. Общий объем перебора при двухэтапном синтезе
всего объекта составляет лишь около 3000 (2 раза по 103 на первом
этапе и 103 — на втором). Если расчленить ОП на три узла по
два параметра на узел, то суммарный объем перебора можно сде-
лать еще меньше. Нетрудно заметить, что, действуя этим методом,
можно к совершенно, казалось бы, безнадежным с точки зрения
объема перебора объектам применять метод вариантного синтеза
и при этом на каждом этапе использовать полный перебор, реали-
зуя все его положительные стороны и не выходя за разумные рам-
ки расхода' машинного времени.
Отметим, что введение структурного деления, о котором здесь
говорится, не тождественно повторению традиционного деления лю-
бого сложного объекта на более мелкие функциональные элементы.
Автор ратует за осознанное разделение ОП на части с доста-
точно малым числом параметров, целью которого является удер-
живать объем перебора в разумных с точки зрения затрат машин-
ного времени пределах. Иными словами, предлагается сознательно
управлять объемом перебора при вариантном синтезе ОП. Части, на
которые при этом делится ОП, — это фактически лишь небольшие
29
группы параметров, обладающие тем свойством, что для этих групп
внешние характеристики аддитивны. Это деление в принципе может
не совпадать с традиционным конструктивным или функциональным
делением объекта, «хотя чем ближе проходят эти линии раздела, тем
удобнее работать. Программы синтеза I и II этапов (этапов может
быть и больше двух) поочередно вводятся в действие программой-
диспетчером.
Сознательно управлять объемом перебора в некоторых преде-
лах можно и при одноэтапном синтезе за счет выбора уровня
сложности фрагментов. Деление на фрагменты, блоки и т. п. в боль-
шой мере условно. Очевидно, чем больший уровень сложности фраг-
ментов выбрал разработчик системы проектирования, тем меньше
будет число типов этих фрагментов, т. е. тем меньше объем пере-
бора., Однако повышение уровня сложности фрагментов требует
большей квалификации составителя программы и большего объема
работы по анализу возможных видов фрагментов и выделению из
них оптимальных по Парето для занесения в гнезда морфологиче-
ского ящика. В этом случае составитель берет на себя часть ра-
боты, которую могла бы выполнять программа синтеза, использую-
щая простые фрагменты. Подготовку человеком сложных фрагмен-
тов можно рассматривать как. первый этап двухэтапного синтеза,
выполняемый вручную. Вопрос о сложности фрагментов сводится,
таким образом, к вопросу о рациональном разделении труда между
человеком — составителем программы и ЭВМ. При этом надо учи-
тывать существующее соотношение между уровнем знаний о про-
ектируемом объекте, стоимостью машинного времени и ожидаемой
интенсивностью использования программы автоматического синтеза.
Как будет видно из дальнейшего, сложность блоков, на которые
предложено делить сумматор, выбрана такой, что, с одной сто-
роны, блоки не оказываются слишком крупными, т. е. их структура
вполне обозрима для разработчика системы, а с другой стороны, они
и не слишком мелки, т. е. число их возможных комбинаций не
слишком велико с точки зрения осуществимости полного перебора
вариантов с помощью ЭВМ.
ГЛАВА ВТОРАЯ
АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ
СУММАТОРОВ
5- ХАРАКТЕРИСТИКИ СУММАТОРА И ЕГО СТРУКТУРА
а) ВНЕШНИЕ. ХАРАКТЕРИСТИКИ СУММАТОРА
Комбинационным' двоичным параллельным сумматором будем
называть комбинационную логическую схему, отрабатывающую
функцию суммы двоичных чисел а и Ь, поступающих на сумматор
параллельным кодом. Схема имеет п входов для первого слагаемо-
го а, п входов для второго слагаемого bun выходов суммы S.
Кроме входов слагаемых и выходов суммы сумматор часто имеет
вход переноса гвх в младший разряд и выход переноса РВых из
старшего разряда, которые используются при выполнении опера-
ций в обратном или дополнительном кодах, с числами, разрядность
которых превышает разрядность сумматора, при округлении резуль-
татов умножения и в ряде других случаев.
30
Не будем особо выделять в сумматоре разряды знака, округ-
ления и т. п., поскольку с точки зрения структуры сумматора они
идентичны соседним числовым разрядам. Кроме того, не будем рас-
сматривать схемы сложения чисел, представленных различными
избыточными кодами, и, в частности, сумматоров с встроенной си-
стемой контроля. По этим вопросам читатель может обратиться
к [17]. В дальнейшем для краткости определенный таким обра-
зом комбинационный двоичный сумматор будем называть просто
сумматор (СМ).
Сумматор, как и любой другой объект проектирования, можно
описать рядом параметров. К внешним характеристикам, т. е. к па-
раметрам, которые непосредственно интересуют заказчика с точки
зрения применения СМ, обычно относятся разрядность СМ, .модуль
суммирования, задержка срабатывания Т, аппаратурные затраты Q,
потребляемая мощность, характеристики, определяющие условия
стыковки СМ с соседними функциональными узлами — наличие или
отсутствие требования парафазности входных сигналов, выдача
суммы в прямом или инвертированном виде и т. п. В зависимости
от конкретных условий список внешних характеристик может быть
сужен или расширен.
Рассмотрим указанные характеристики несколько подробнее.
Будем полагать, что разрядность сумматора п может принимать
любые целые значения от 1 до 64. Значения разрядности больше
64 ц цифровых устройствах встречаются редко.
Модуль суммирования я-разрядного двоичного сумматора мо-
жет принимать два значения: 2п и 2П—1. Тракт переноса СМ, скла-
дывающего числа по модулю 2П, имеет начало — младший разряд
и конец — старший разряд, т. е. СМ разомкнут по тракту переноса.
Такой СМ применяется при сложении чисел в дополнительном коде
(ДК). У СМ по модулю 2П—1 тракт переноса замкнут в кольцо
с помощью циклической связи «выход переноса старшего разряда —
вход переноса младшего разряда». Такой СМ применяется при сло-
жении чисел в обратном коде (ОК). В дальнейшем СМ по модулю
2П будем -называть СМ ДК, а СМ по модулю 2n—1 —СМ ОК.
Задержку срабатывания СМ будем характеризовать временами
задержки его основных трактов:
Таз — задержка тракта суммы, измеряемая . от момента подачи
слагаемых а и 6 до момента установления правильного значения
суммы во всех разрядах при условии, что переходные -процессы,
вызванные подачей входного переноса гвх в младший разряд, не
влияют на величину Tas (например, если сигнал гвх был подан за-
ранее и связанные с ним переходные процессы уже закончились);
Tr s—задержка тракта перенос — сумма, измеряемая от момен-
вх
та подачи на младший разряд СМ сигнала входного переноса гвх
до момента установления правильного значения суммы во всех раз-
рядах при условии, что слагаемые а и Ь были поданы заранее;
ТаР —задержка тракта слагаемые — перенос, измеряемая от
момента подачи слагаемых до момента установления правильного
значения выходного переноса из сумматора РЪы4. при условии, что
входной перенос сумматора гвх был подан заранее;
Т р —задержка тракта переноса СМ, измеряемая от мо-
вх вых
мента поступления сигнала переноса гвх на вход младшего разряда
31
СМ до момента установления правильного значения переноса ЯВых
из старшего разряда при условии, что слагаемые а и b были по-
даны заранее;
Тем — задержка сложения СМ. Она равна наибольшей из че-
тырех предыдущих величин. Тем характеризует время, отсчитывае-
мое от момента одновременной подачи входных величин a, b и гвх,
по истечении которого можно получить правильные значения как
о, ТЭК И "вых. Чаще всего наибольшей оказывается задержка Tas-
Аппаратурные затраты Q в зависимости от технологической
базы и ряда других условий заказчик может измерять числом кор-
пусов MHKpocxeMJ числом бескорпусных логических элементов при
гибридной технологии, площадью, занимаемой СМ на кристалле
при твердотельном исполнении, и т. д.
В данной книге качество схем оценивается по задержке Т и
аппаратурным затратам Q. Оценки ориентированы на использование
интегральных микросхем одной из наиболее массовых в настоящее
время серий К155. Эти оценки годятся и для других серий, если
последние имеют тот же набор логических элементов, а элементы —
такое же соотношение величин задержек, как и в серии К155, на-
пример К130, К133. Ознакомившись с предлагаемой методикой,
читатель, если это ему потребуется, сможет выполнить синтез и
оценку сложных СМ и на иной технологической основе, в том числе
и при использовании однокорпусных 2- и 4-разрядных СМ, изго-
товляемых на базе схем средней интеграции. Другими будут лишь
числовые данные. Параметры серии К155 взяты из [18]. За еди-
ницу времени задержки т принято время задержки элементов без
расширителей. Время задержки элементов с подключенными расши-
рителями" вычисляется согласно [18]. Аппаратурные затраты Q
вычисляются в двенадцатых долях корпуса элементов серии К155,
поскольку у наиболее распространенного корпуса с 14 выводами
число логических выводов равно 12.
Если в серии, используемой читателем, принятая система оце-
нок работает неудовлетворительно, он может подкорректировать
ее или использовать любую другую систему оценок. Нужно лишь
помнить, что это не точный, подсчет, а оценки. Они позволяют
уверенно говорить о том, какой вариант схемы лучше, только если
полученные величины Т или Q отличаются не менее чем, например,
на 20%. Если разница оценок по Т и Q меньше, то такие схемы
неразличимы и заслуживают того, чтобы их точнее просчитали уже
по данным ТУ. Удобство и польза оценок заключаются в том, что
лишь небольшая доля всего множества вариантов, из которых надо
выбирать решение, потребует выполнения второго приближения.
Многие варианты будут отвергнуты на основе простых оценок.
При вычислении Т и Q с помощью ЭВМ необходимость в си-
стеме упрощенных оценок обычно отпадает и расчет ведется на
основе значений Т и Q, записанных в ТУ. Для того чтобы рас-
четные формулы не зависели от номера серии микросхем, время
задержек элементов в формулах для ЭВМ указывается не в нано-
секундах, а с помощью меток типа «Т элемента 2И-НЕ», «Т эле-
мента 2И-2ИЛИ-НЕ». Аналогично поступают и с вычислением Q.
Тогда при смене серии достаточно лишь указать расчетному модулю
программы номер таблицы значений Г и Q элементов нужной се-
рии. Расчетные формулы в таком универсальном виде весьма гро-
моздки и в этой книге не приводятся, но их легко написать по
аналогии с формулами, приведенными в § 5—12,
Потребляемая мощность и стоимость СМ при выбранных эле-
ментах примерно пропорциональны величине Q, и для простоты
изложения вопросы минимизации этих параметров рассматриваться
1не будут. При необходимости читатель может сделать это само-
стоятельно аналогично минимизации аппаратурных затрат Q.
б) СТРУКТУРНОЕ ДЕЛЕНИЕ СУММАТОРА
Чтобы сократить время сложения многоразрядных чисел, нужно
как-то ускорить распространение сигнала переноса вдоль цепочки
разрядов. По этому вопросу было проведено большое количество
исследований. Почти все они связаны с реорганизацией тракта пере-
носа и, как правило, не касаются тракта суммы. Поэтому структур-
ное деление СМ начнем с того, что весь тракт переноса многораз-
рядного СМ выделим в самостоятельный функциональный узел —
'.блок переноса, а в качестве второго самостоятельного функциональ-
ного узла будем рассматривать блоки суммы. Другими словами,
сбудем делить СМ не поперек цепочки разрядов, как это обычно
щринято, а вдоль нее. Задача блока переноса: получив на вход
слагаемые, выработать сигналы переноса для блоков суммы. Блок
переноса характеризуется единственным временным параметром —
временем задержки тракта «слагаемые — перенос». Задача блока
суммы: получив сигнал переноса из блока переноса, отработать
функцию суммы. Конечно, блок суммы кроме сигнала переноса
получает на свои входы также и слагаемые а и 6. Однако в ре-
альных схемах СМ все переходные процессы, начавшиеся в момент
;подачи на блоки суммы слагаемых, к моменту отработки блоком
^переноса сигнала переноса оказываются уже законченными и для
.выработки правильного значения суммы блоки суммы ждут лишь
^сигнала переноса. Поэтому можно считать, что временной параметр
•у блока суммы также всего один: время задержки тракта «пере-
нос— сумма». При таком делении блоки переноса и суммы ока-
зываются в известной мере независимыми один от другого, что по-
зволяет получать новые схемы СМ комбинаторным способом, ис-
пользуя совместно с одним и тем же блоком переноса различные
варианты блоков суммы и наоборот. Время задержки Tas СМ, со-
бранного из таких блоков, вычисляется как сумма времен задержки
блока переноса по тракту «слагаемые — перенос» и блока суммы по
тракту «перенос — сумма», аппаратурные затраты СМ — как сумма
затрат блока переноса и блоков суммы.
Подчеркнем, что деление СМ на блок переноса и блоки суммы
?ие имеет отношения к конструктив-
ному делению СМ на микросборки, ^
шлаты и т. п. Предлагаемое деление
гявляется чисто функциональным. Я/—
Щель его — облегчить как изучение, -
ггак и .проектирование функцкональ- 1
щых схт сложных СМ за счет вве-
дения унифицированных функцио- •
наяьных единиц, базовых фрагментов, •
таких, как «блоки переноса, блоки •
Рис. 3. Представление сумматора
в виде блока переноса и блоков h
суммы.
^3—1119 33
1*1
ВОСУМ
fi(a,b)
•
о
•
I
f*i(a,b)\
суммы и составляющие. Поскольку базовые фрагменты состоят из
многих логических элементов, число фрагментов в составе СМ ока-
зывается во много раз меньше, чем число логических элементов. Это
настолько упрощает решение различных комбинаторных задач при
проектировании функциональной схемы СМ, что позволяет форма-
лизовать и автоматизировать этот процесс.
На рис. 3 /г-разрядный СМ разбит на блок переноса Б1ПЕРЕ и
п блоков суммы БОСУМ. На входы блока 51 ПЕРЕ поступают вход-
ной перенос сумматора г„х и все разряды слагаемых а* и bi. Ha
выходах блока Б1ПЕРЕ отрабатываются разрядные переносы г*.
При построении СМ часто удается выразить Sx не как функцию
Г{ и самих слагаемых а» и bi, а как функцию г< и некоторых про-
межуточных функций от йг и bi\ f\{ait bi), /2(0*, bi), которые по-
лучаются в блоке Б1ПЕРЕ в процессе выработки переносов г*.
Это дает возможность уменьшить аппаратурные затраты СМ. Циф-
ра 1 в обозначении блока переноса Б1ПЕРЕ и цифра 0 в обозна-
чении блока суммы БОСУМ означают, что блок Б1ПЕРЕ многораз-
рядный, а блок БОСУМ одноразрядный.
6. ОДНОЯРУСНЫЕ СУММАТОРЫ
С ПОСЛЕДОВАТЕЛЬНЫМ ПЕРЕНОСОМ
а) ОДНОРАЗРЯДНЫЙ СУММАТОР
Сумматор, у которого сигнал переноса Pi в соседний старший
разряд получается как логическая функция слагаемых данного раз-
ряда at и bi и переноса в данный разряд г и называется сумматором
с последовательным (ПОС) переносом. Блок переноса Б1 ПЕРЕ та-
кого СМ, который будем называть Б1ПЕРЁПОС, получается наи-
более экономичным по аппаратурным затратам. Он состоит из оди-
наковых логических схем, число которых равно числу разрядов СМ.
Каждую из таких одноразрядных схем назовем БОПЕРЕ (рис. 4,а).
Сигнал Pi в качестве r*+i поступает на вход г следующего (/-Ц)-го
блока Б1ПЕРЕ и (t—j—1) -го блока суммы БОСУМ. Обозначение
Б1СУМПОС и я на рис. 4,а будут ясны из § 7 и 8.
В силу регулярности структуры сумматоров с ПОС переносом
бывает удобно рассматривать комбинацию i-ro разряда тракта ПОС
переноса БОПЕРЕ и относящегося к нему иго блока суммы
БОСУМ* совместно. Такая комбинация называется одноразрядным
сумматором. На рис. 4,6 показан 4-разрядный СМ, представленный
в терминах одноразрядных СМ. Представление СМ в виде группы
одноразрядных сумматоров наиболее широко распространено в ли-
тературе. Для нас такое представление в дальнейшем будет неудоб-
но, и представление СМ в виде цепочки одноразрядных суммато-
ров будет использовано лишь в пределах данного параграфа.
Как следует из курса арифметических основ ЭВМ (см., напри-
мер, [14]), дизъюнктивная совершенная нормальная форма (ДСНФ)
функций Р и S одноразрядного СМ записывается следующим об-
разом:
P=fab\Jrab\/rdb\Jrab; (1)
34
S=rab\/rab\/rab\/rab.
(2)
Рис. 4. Од-
ноярусный
сумматор с
последова-
тельным пе-
реносом.
а —СМ пред-
ставлен в ви-
де блока пе-
реноса и бло-
ков- поразряд-
ных сумм; б—
СМ представ-
лен как цепоч-
ка однораз-
рядных сум-
маторов.
61 ПЕРЕ ПОС
г
а
Ь
Р
а
к.
Ъ
Б1СУМПОС
SM1 №->S/
St "*-M
SMZ
\s\-s,
3
p
SM3
s
a
ь
ьА
а) Ю
Несмотря на то что по способу поступления слагаемых СМ
с ПОС переносом относится к параллельным, процесс образования
суммы в нем носит сугубо последовательный характер и при наи-.
худших сочетаниях слагаемых сигнал переноса должен пройти по-
следовательно через тракты переноса всех одноразрядных СМ. Вы-
разим задержку ^-разрядного СМ с ПОС переносом через времен-
ные параметры одноразрядного СМ. Для этого по аналогии с че-
тырьмя величинами, характеризующими время задержки много-
разрядного СМ (см. § 5,а), введем величины, характеризующие вре-
мена задержки различных трактов одноразрядного CM: tas, Us,
tap, trp. Так, tas — это время задержки тракта суммы от момента
подачи слагаемых а и b до момента установления правильного зна-
чения суммы 5 в данном разряде при условии, что сигнал переноса
г был подан заранее, и т. д.
Обозначим входной перенос гвх ^-разрядного СМ через е,
а выходной Рвых-через £пс (перенос последовательный) (причина
введения этих обозначений будет ясна из дальнейшего изложения),
тогда
TaS=taP + &-2)*rP+trS; (3)
TaEnC = taP + (k-\)trP^ (5)
TEnc = ktrP, (6)
3*
35
Смыбл выражений легко проследить по схеме на рис. 4,6. Йз
(3) —(6) видно, что на времена задержек СМ наибольшее влия-
ние оказывает время задержки в тракте переноса каждого разряда
trpy поскольку оно входит в формулу с коэффициентом, близким
к значению разрядности k.
Рассмотрим несколько вариантов схем, построенных на элемен-
тах распространенных серий и обладающих наилучшими из воз-
можных в используемых базисах характеристиками по времени за-
держки в тракте переноса trp и при этом достаточно экономичных
по затратам оборудования Q. В дальнейшем эти схемы будем ис-
пользовать в качестве базовых фрагментов для построения более
сложных СМ.
б) СУММАТОР НА ЭЛЕМЕНТАХ И-ИЛИ-НЕ
На рис. 5 показана схема одноразрядного СМ, реализующего^
функции
Р = аь\/ ar\J br\ S =аР\/ ьРу rPV abr.
На этом же рисунке представлены оценки схемы по Т и Q
при построении ее в базисе микросхем серии К155. Использование
1-, 2- и 4-разрядных СМ серии К155, размещенных в одном кор-
пусе, для построения более сложных СМ будет описано позже,
а пока нашей целью является изучение различных принципов по-
строения суммирующих схем, и, как уже отмечалось, базис серии
К155 вместе с присущей ему системой оценок будет выступать
в роли языка, хорошо знакомого инженерам.
На примере СМ на рис. 5 удобно рассмотреть следующие осо-
бенности, присущие также и другим приведенным ниже схемам
одноразрядных СМ:
1. В блоке БОСУМ используются не только слагаемые а и 6,
но также и промежуточная функция, полученная на аппаратуре
блока БОПЕРЕ, в данном случае — инверсия переноса Р. Это по-
зволяет сделать БОСУМ весьма экономичным.
2. Стремление минимизиро-
60ПЕРЕ
Рис. 5. Одноразрядный СМ на
двух элементах И-ИЛИ-НЕ.
1а8
Q-24.
2т; tn
-It; trS-*:; tr
= 1т;
вать наиболее неприятную для СМ
задержку в тракте» переноса trp
привело к тому, что в тракте пе-
реноса гР остался всего один ло-
гический элемент (И-ИЛИ-НЕ).
Поскольку многие элементы со-
временных серий инвертируют сиг-
нал, выполнение тракта переноса
на одном элементе приводит к то-
му, что выход переноса обяза-
тельно получается инвертирован-
ным. Казалось бы, это должно
затруднить стыковку одноразряд-
ных СМ друг с другом по тракту
переноса, поскольку на вход бло-
ка переноса СМ требуется пода-
вать неинвертированную величину
36
Р. Введение же дополнительного инвертора примерно удвоит время
задержки ГСм. Однако при построении именно СМ это затруднение
легко обходится, поскольку и функция переноса (1), и функция сум-
мы (2) относятся к классу самодвойственных, т. е. таких функций,
значения которых инвертируются при инвертировании всех вхо-
дящих в них переменных (см., например, Г14]). Поэтому поступим
следующим образом. Соединим блоки БОПЕРЕ соседних разрядов
по тракту переноса последовательно без промежуточных инверторов.
На те разряды, на которые поступают инвертированные значения
переноса, слагаемые ч также подадим инверсным кодом (а и Б),
сняв их, допустим, с инверсных выходов триггеров соответствую-
щих разрядов. Тогда в силу самодвойственности функций на вы-
ходах этих разрядов получатся неинвертированные значения Р ц
S. На те разряды, на которые поступают неинвертированные зна-
чения переносов, слагаемые а и Ь будем подавать неинвертирован-
ными и соответственно получать на выходах этих разрядов инвер-
тированные значения переноса Р и суммы 5.
3. Поскольку значение суммы нечетных разрядов оказывается
инвертированным, то, чтобы не было черезразрядной инверсии ре-
зультата, в нечетных разрядах результат нужно снимать с инверс-
ных выходов триггеров регистра суммы. Если же черезразрядная
инверсия недопустима уже на выходе логических схем СМ, при-
дется в состав СМ в каждый нечетный разряд добавить по инвер-
тору, что соответственно увеличит аппаратурные затраты Q всего
СМ, а если число разрядов нечетное — то и время сложения Гсм.
Сумматор на рис. 5 выгодно отличается от трех последующих
схем тем, что он не требует на входе парафазного кода слагаемых,
что важно, если ограничено число линий связи. Именно такие одно-
разрядные фрагменты использованы в 1-, 2- и 4-разрядных СМ
К155ИМ1, К155ИМ2, К155ИМЗ, размещенных в одном корпусе и
выпускаемых в составе серии К155.
в) СУММАТОР, ИСПОЛЬЗУЮЩИЙ СЛОЖЕНИЕ ПО МОДУЛЮ 2
Сумматор данного типа показан на рис. 6. Величина а© 6 по-
лучается на отдельном элементе И-ИЛИ-НЕ и используется как
в блоке переноса, так и в блоке суммы. Кроме того, в блоке суммы
используется входной г и выходной Р переносы сумматора. Сами
слагаемые а и Ь в блоке суммы не используются.
БОПЕРЕ
1 г-
&
1
(
Ц а
а®Ь
&
1
о
1с
а —
Ъ —
1
БОСУ/1
—i t*
&
1
1с
О
L.
Рис. 6. Одноразрядный СМ, использующий операции сложения по
модулю 2.
'as-Зт; 'г5=2Т; /вР-2Т; 'г,-1т; Q-21.
37
Схема на рис. 6 реализует соотношения
Р = аь\/ (афь)г; S = а® ь>г\/ (а® ь) Р.
При реализации на отдельных логических элементах, входящих
в серию К155, СМ на рис. 6 оказывается несколько экономичнее,
чем СМ на рис. 5, однако задержка tas у него немного больше.
Если в состав элементов серии входит сумматор по модулю 2 (их
может быть размещено до четырех штук в стандартном корпусе),
то кроме схемы на рис. 6 можно построить еще одну очень эко-
номичную по числу корпусов схему, реализующую соотношения
г) СУММАТОР, ИСПОЛЬЗУЮЩИЙ ТОЛЬКО ЭЛЕМЕНТЫ И-НЕ
Преобразуем ДСНФ функции переноса следующим образом:
Р = г (аф&) V аь= г-(а($ь)-аъ ^ г-al)-аь-а~ь,
или
Р — г- ab-ab-ab.
(7)
Проинвертируем (7), используя свойство самодвойственности
функции переноса:
р = г-аЬ-аЬ-аь.
(8)
Как видим, и перенос, и его инверсию можно представить в виде
конъюнкции двух членов. Основной принцип построения описывае-
мого СМ заключается -в
Г'ЮУмР том' что Указанная конъ-
[ юнкция выполняется не
! в данном разряде, а в
соседнем старшем. Схе-
ма, реализующая этот
принцип, показана на
рис. 7. Перенос ги яв-
ляющийся конъюнкцией
сигналов, присутствую-
щих на паре проводов
П, поступает на четырех-
входовой элемент И-НЕ
первого (и вообще —
Рис. 7. Одноразрядный
СМ на элементах И-НЕ
с задержкой 1т на раз-
ряд (tas — 4т; trs = Зт;
fap-2T; iVp-It; q=23)
и без последнего элемен-
та И-НЕ (tas=3т; iVe-
ss 2т; *ар = 2т; /гР = 1т;
й=21).
38
любого нечетного) разряда (элемент 3, рис. 7). С выхода этого
элемента снимается сигнал Гх*а\Ь\'а\Ъ\, являющийся первым чле-
ном конъюнкции выражения (7). Как видно из рисунка, сигнал
rva\b\-a{B\ в паре с сигналом ахЬ\ (элемент /) поступает на второй
(и вообще — любой четный) разряд, а согласно (7) конъюнкция
этих сигналов образует величину Pi=r2 (в общем случае J*2i-i=
=г2г). Во втором (любом четном) разряде на четырехвходовом
элементе И-НЕ (элемент 6) вырабатывается первый член конъюнк-
ции выражения (8), который в паре с сигналом а2Ь2 элемента 5
образует сигнал Р2=г3 (в общем случае P2i=r2t+i) и т. д.
Функция суммы в первом разряде (рис. 7) имеет вид:
Sj — rl 'CL\bx -albl -albl 'Cilb1 •r1 >a1bl *axbx >rx.
Используя выражение (7) и соотношение
aba~b = a@b, (9)
выражение для суммы легко привести к привычному виду. В опи-
санной схеме блок БОСУМ использует сразу три промежуточные
функции, одна из которых довольно сложная. При необходимости
подать на СМ входной перенос е, его можно завести сразу на оба
входа г. Если необходимо использовать выходной перенос из стар-
шего разряда, то на элемент И-НЕ схемы-приемника нужно подать
сразу два провода Епс.
Сумматор на рис. 7 построен только на элементах И-НЕ и име-
ет при использовании принципа ПОС переноса минимально воз-
можное время задержки, поскольку сигнал переноса проходит лишь
через одну логическую ступень — элемент И. В сумматорах на рис. 5
и 6 сигнал переноса проходит через две логические ступени: И и
ИЛИ. По аппаратурным затратам эта схема также стоит в ряду
самых экономичных. Заметим, что во многих случаях реального
конструирования последнюю конъюнкцию в выражении для суммы
можно выполнить на входном вентиле триггера регистра суммы,
т. е. можно исключить из состава СМ последний элемент И-НЕ
блока суммы БОСУМ (элементы 4 и 7 на рис. 7). В результате
схема станет лучшей среди построенных на элементах И-НЕ,
И-ИЛИ-НЕ и по аппаратурным затратам, и по величинам за-
держек.
д) СУММАТОР С ДВУХКОЛЕЙНЫМ ПЕРЕНОСОМ
Сумматор данного типа (рис. 7), как и предыдущие схемы,
вырабатывает разряды суммы с чередующейся инверсией. На рис. 8
показана модификация этой схемы, Схема на рис. 8 вырабатывает
сигналы суммы,. имеющие, .одинаковую фазность во всех, разрядах.
В ххеме, приведенной на рис. 8, перенос между разрядами пере-
дается парафазным кодом по двум трактам. Один тракт образован
выходами элементов / и 3. Он идентичен ,тракту переноса, образо-
ванному элементами / и 3 (см. рис. 7), и реализует выражение (7).
Другой т^акт _ переноса СМ, изображенного на рис. 8, образован
элементами 2< и 4 и реализует выражение (8), т. е. в известном
39
БОПЕРЕ ["* БОСУП 1
Рис. 8. Одноразрядный СМ, на
элементах И-НЕ с двухколейным
переносом.
'as=4* 'rs=3* 'ер-** 'гР"1Г'
смысле аналогичен тракту пере-
носа второго разряда СМ на'
рис. 7, образованному элементами
5 и 6. Из (7) и (8) следует, что
указанные тракты взаимно ин-
версны: если конъюнкция ригна-
лов на паре проводов одного из
них образует перенос Р, то конъ-
юнкция сигналов на другой паре
образует инверсию переноса Р.
Такой способ передачи переноса иногда называют двухколейным пе-
реносом. Наличие обеих фаз входного переноса дает возможность
в любом разряде выбрать именно ту, которая требуется для выра-
ботки выходного сигнала суммы всегда одной и той же фазности:
Используя (9) и правило де-Моргана, это выражение можно
привести к привычной форме. Схема на рис. 8 — интересный ва-
риант СМ: у него нет черезразрядной инверсии суммы, он построен
только на элементах И-НЕ, весьма экономичен по затратам обо-
рудования и имеет минимально возможную при ПОС переносе
задержку переноса 1т на разряд.
Как отмечалось в § 5,а, при работе с ОК используют СМ, скла-
дывающий числа по модулю 2П—1. Если в СМ применен ПОС
перенос между разрядами, то СМ ОК получается из СМ ДК путем
простого введения цепи циклического переноса, т. е. соединения вы-
хода переноса старшего разряда с входом переноса младшего раз-
ряда.
в) ГНЕЗДО СУММАТОРОВ С ПОСЛЕДОВАТЕЛЬНЫМ
ПЕРЕНОСОМ
С точки зрения вариантного синтеза схемы на рис. 5—8 — это
базовые фрагменты, различающиеся такими характеристиками, как
время задержки по различным трактам, величина Q, наличие или
отсутствие в составе схемы элементов И-ИЛИ-НЕ, выдача суммы
прямым или инверсным кодом и т. п. Перечисленные схемы, насколь-
ко это известно автору, — лучшие из опубликованных в рассматри-
ваемых базисах. Для удобства сравнения они представлены на
рис. 9 в виде точек на плоскости Т, Q. Исключить какую-либо из
них с тем, чтобы уменьшить число рассматриваемых фрагментов,
при принятой детализации рассмотрения не. представляется воз-
можным, поскольку все эти СМ различаются существенными для
заказчика характеристиками. Так, если заказчику важны только
величины Tas и Q, а все другие характеристики значения не имеют,
то ему, как.видно из рис. 9, нужно выбирать .СМ лишь из схем на
рис. 5 и- б, образующих группу оптимальных по Парето в простран-
стве характеристик Tas, Остальные- две схемы не принадлежат
г- г-аЬаЬ-г-аЬаЬ.
40
Рис. 9. Взаимное расположение
одноразрядных СМ на плоскости
Т, Q.
группе Парето в указанном про-
странстве. Если заказчику важны
только величины Trs и Q, то наи-
лучшей будет схема на рис. 6: все
множество Парето в пространстве
Тг8, Q вырождается в одну эту
точку (левый нижний треугольник
на рис. 9). Все остальные схемы
хуже. Если в базисе заказчика
отсутствуют элементы И-ИЛИ-НЕ,
т. е. базис состоит лишь из эле-
ментов И-НЕ, то схемы на рис. 5
и б будут запрещены фильтром заказчика, а из оставшихся схем,
изображенных на рис. 7 и 8, наилучшее будет схема на рис. 7. Она
одна представляет все множество Парето в пространстве Т, Q для
СМ, использующих только элементы И-НЕ. Если же недопустима
черезразрядная инверсия суммы, то единственно пригодной будет
схема на рис. 8, которая при других рассмотренных вариантах ТЗ
оставалась наихудшей. На рис. 9 наглядно показан отмечавшийся
в § 3 факт, что каждому конкретному сочетанию параметров мо-
жет соответствовать свое множество Парето.
Гнездо морфологического ящика, содержащее схемы на
рис. 5—8, представлено в табл. 2. Поле условий, нужное лишь при
совместном рассмотрении всех гнезд ящика, здесь опущено. Сумма-
торы 7' и 8' строятся по схемам на рис. 7 и 8, но не имеют по-
следнего элемента И-НЕ. Характеристики Xjl—Xj9 используются
в условиях стыковки со значениями других параметров, при обра-
ботке запретов заказчика, при модификации расчетных формул.
Таблица 2
Гнездо одноразрядных СМ с последовательным переносом
Параметр /. Имя параметра: Вид схемы одноярусного СМ
№
Значение
параметра
Характеристики
Xj2
XJ3
Х]4
Xj'5
Xj6
XJ7
Xj8
Xj9
<aP
frP
Q
1
Схема на
0
0
0
1
1
1
0
0
1
2
2
1
1
24
рис. 5
21
2
Схема на
•1
0
0
1
.1
1
0
l
1
3
2
2
1
рис. 6
23
3
Схема на
1
1
0
1
1
0
1
l
1
4
3
2
1
рис. 7
25
4
Схема на .
1
1
1
0
1
0
1
l
1
4
3 .
%2
1.
Р"С 8
г
Схема 7Г
1
1
0
1
0
0
i
l
1
3'
2
2
1
20
1
Схема 8'*
1
1
1
0
0
0
1
1
3
2.
2
1
22
41
a
7Puc.S
a
1 A^i
a
7Puc. 7
Y
Pit" с
/
rtl
и
1
L.
-
T
0 5
Смысл введения характеристик Xj2, Xj3, Xj7 и Xj8 станет ясен при
чтении § 8—11.
Xjl — необходимость парафазного представления слагаемых а
и Ь на входе одноразрядного CM; Xj2 — двухпроводное представ-
ление сигнала переноса; Xj3 — парафазное представление сигнала
переноса; Х]4 — черезразрядная инверсия сигнала суммы; Xj5 —
однопроводное представление сигнала суммы; Xj6 — в схеме СМ
имеются элементы И-ИЛИ-НЕ; Х\7 — схема 'вырабатывает функцию
y=ab; Xj8 — схема вырабатывает функцию л'=аф6 или я"=аБ;
Xj9— распространение переноса последовательное.
В этой книге не ставилось целью автоматизировать синтез схем
самих фрагментов типа показанных на рис. 5—8. Синтезом одно-
разрядных СМ в базисах И-НЕ и И-ИЛИ-НЕ занимаются очень
давно, и вряд ли можно ожидать появления новых схем в этих же
базисах, которые оказались бы существенно лучше уже известных.
При такой ситуации целесообразно, изучив литературу, выбрать
наиболее удачные схемы и ввести их в программу. Для тех логи-
ческих узлов, которые" исследованы не столь хорошо, как СМ, мож-
но создать двухэтапную систему автоматического синтеза, идея ко-
торой описана в § 4,ж. На первом этапе выполняется синтез самих
фрагментов путем перебора допустимых комбинаций логических
элементов, вычисления характеристик Т и Q и выделения группы
фрагментов, оптимальных по Парето.
7. ОДНОЯРУСНЫЕ СУММАТОРЫ С ПАРАЛЛЕЛЬНЫМ
ПЕРЕНОСОМ
Общая структурная схема сумматора с параллельным (ПАР)
переносом показана на рис. 10. Для сумматоров этого типа яв-
ляется характерной структура блока переноса, который будем обо-
значать Б1ПЕРЕПАР (вспомним, что блок ПОС переноса обозна-
чили Б1ПЕРЕПОС). В блоке Б1ПЕРЕПАР каждый разрядный
перенос Pt=/*i+l вырабатывается отдельной- разрядной логической
схемой БОПЕРЕ как функция слагаемых а и Ь и входного пере-
носа е..При подаче слагаемых все схемы БОПЕРЕ начинают рабо-
тать одновременно, что позволяет уменьшить время задержки полу-
чения суммы.
а) ФУНКЦИИ ГЕНЕРАЦИИ И ПРОЗРАЧНОСТИ
Для построения блока Б1ПЕРЕПАР введем две вспомогатель-
ные функции:
Y — функция генерации переноса, у» равна 1, когда слагаемые
данного разряда таковы, что перенос в соседний старший разряд
равен ,1 независимо от значения переноса гг в данной, i-й разряд,
х. е. Yt=l. если в• t-м разряде сумматора генерируется сигнал пе-
реноса P*=r»+i:
yi^aibi. (10)
я — функция прозрачности, я* равно 1, когда слагаемые дан-
ного разряда таковы, что при переносе в данный разряд riy равном
1, перенос в соседний старший разряд Р\ также равен 1, т. е. яг-=
= 1, если тракт переноса данного разряда сумматора прозрачен для
сигнала переноса г,-.
42
4г
h-f
ajL.
Б1 СУ tin АР
Б1 ПЕРЕПАР
аг>*г{.
Б0ПЕРЕ1
аг,ьг\-
БОПЕРЕг
- п
60ПЕРЕ(к-1А
Рк-1
а аЬ данного
и всех более
пладших
разрядоб
Г (а, Ъ) £
г
БОСУ/1 f
•
Г
S
rk-1
r
босу/iz
f
S
•
•
•
r
Б0СУП(Н-1)
f
S
r
БОСУПН
f
S
K1
37
4-1
Рис. Ю. Структурная схема одноярусного оумматора с параллель-
ным переносом (блока суммы Б1СУМПАР).
С помощью переменных у и я можно представить функциони-
рование блока переноса одного разряда:
Р*=г«+1ч=7*\/пя;*. (11)
Функция прозрачности, определенная указанным способом, мо-
жет быть представлена двумя различными функциями:
пг = а($Ь; «" = д V Ь = аь
(12
Дело в том, что значение Pi=ri+{ согласно (11) будет одним
и тем же независимо от того, используем мы функцию я' или я".
Эти функции имеют различные значения лишь при аЬ—\, а по-
скольку при таком сочетании слагаемых у=\, то перенос Pi ра-
вен 1 независимо от значения второго члена дизъюнкции пт'* или
г{л"{. В то же время в ряде логических базисов функции я" реа-
лизуется проще, чем я'. В дальнейшем в общих выражениях для
обозначения функции прозрачности будем пользоваться символом
я без штрихов, т. е. не будем различать я' и я" и только на по-
следнем этапе при построении функциональных схем будем выби-
рать тот вариант, который нам будет удобнее по каким-либо сооб-
ражениям.
б) БЛОК ПАРАЛЛЕЛЬНОГО ПЕРЕНОСА
Построим разрядные схемы БОПЕРЕ блока Б1ПЕРЕПАР для
СМ ДК, т. е. для СМ, у которого тракт переноса разомкнут. Вход-
ным переносом гх блока суммы первого, младшего разряда Б0СУМ1
43
будет, очевидно, входной перенос всего СМ, который обозначим е.
Итак, Ti—e.
Перенос Рь вырабатываемый блоком БОПЕРЕ 1 и поступающий
на вход Б0СУМ2 как сигнал г2, будет равен 1, если слагаемые
первого разряда а,\ тл Ь\ таковы, что в этом разряде генерируется
перенос, или если на вход всего СМ поступил перенос е, а слагае-
мые а\ и Ь\ таковы, что первый разряд прозрачен по тракту пере-
носа, т. е.
Pi=r2=YiV^i.
Аналогично рассуждая, приходим к выводу, что вырабатывае-
мый схемой БОПЕРЕ перенос Pi=n+l на входе блока суммы
БОСУМ (i+1) должен быть равен 1, если перенос генерируется
в i-м разряде; или если он генерируется в (i—1)-м разряде, при
этом х'-й разряд прозрачен; или... и т. д.; или если на СМ поступил
входной перенос е и при этом прозрачны все разряды от 1-го до
i-го включительно:
Pi=ri + l=yi\/yi-l-Tti\/yi-2'ni-rTCi\/. . .
• • • VYi 'Яг'Яз... -Tii\/e-ярп2... п*-\Яи (13)
В базисе И-НЕ схемы поразрядных переносов БОПЕРЕ будем
строить следующим образом. Применив формулу де-МоргаНа, за-
меним- в (13) операции дизъюнкции операциями конъюнкции,
а функции генерации у представим согласно (10), тогда
... X ••• Я/-i^-07^2... ni. (14)
Блок переноса для четырех разрядов, состоящий из трех схем
БОПЕРЕ, реализующих выражение (14), показан на рис. 11. На
вход каждой схемы разрядного переноса БОПЕРЕ* подаются вход-
ной перенос е и функции прозрачности и генерации t-го и всех бо-
лее младших разрядов. Функция прозрачности t-ro разряда полу-
чается на специальных элементах, входящих в состав схемы
БОПЕРЕ/ согласно выражению
n"i = aiV &/ = л>7. 05)
Последняя схема Б0ПЕРЕ4 состоит лишь из элементов, выра-
батывающих функции я,/4=а454 и у4> которые будут нужны для
объединения малоразрядных сумматоров Б1СУМПАР в многораз-
рядные структуры.
В базисах, имеющих кроме элементов И-НЕ еще и элементы
И-ИЛИ-НЕ, выражение (13) можно реализовать непосредственно
на элементах И-ИЛИ-НЕ. При этом получим инвертированное зна-
чение переноса Pt=ri+i. Трехразрядный сумматор, ПАР тракт пе-
реноса которого построен таким образом, показан на рис. 12. Опе-
рация получения суммы в этой схеме также реализована на эле-
ментах И-ИЛИ-НЕ в виде цепочки двух последовательных сложений
по модулю 2. При построении схемы типа, приведенной на рис. 12
могут, очевидно, использоваться не только законченные элементы
И-ИЛИ-НЕ,. но и элементы И-ИЛИ-НЕ, построенные методом
«монтажной логики» (см., например, [16]).
Весьма удачный СМ с ПАР перенЪсом получается, если схемы
выработки переносов Pi построить на И-НЕ, как на рис. 11, а схе-
44
Б1 СУМПАР
Б1ПЕРЕПАР
БОНЕ РЕZ azjji
Рис. И. Четырехразрядный СМ с ПАР переносом (блок суммы
Б1СУМПАР) на элементах И-НЕ.
мы выработки величин а06 и блоки суммы БОСУМ — на элемен-
тах И-ИЛИ-НЕ, как на рис. 12. Назовем такую схему «схема 12'».
Она вырабатывает инверсные значения суммы Si и имеет малое
время задержки при больших k.
В блоке ПАР переноса, чтобы получить сигнал г<, требуются
t-входовые элементы, следовательно, максимальная разрядность
блока ПАР переноса, построенного согласно схемам на рис. 11 и
12, не может превышать значений М, т. е. максимального числа
входов по И используемой серии элементов. Поэтому СМ с ПАР
переносом строят лишь для малых значений разрядности л, а при
больших п СМ набирают из нескольких малоразрядных СМ —
«групп» с ПАР переносом, и схемы типа, приведенных на рис. 11 и
45
61 СУ ППАР
Б1ПЕРЕПАР
Рис. 12. Трехразрядный СМ с ПАР переносом (блок Б1СУМПАР)
с трактом переноса на элементах И-ИЛИ-НЕ.
12 в дальнейшем будем использовать как базовые фрагменты для
синтеза более сложных СМ. Понятия «рис. 11», «рис. 12», «схема
12'» будут значениями одного из параметров сложного СМ. Учиты-
вая сказанное, будем говорить не об л-разрядном СМ с ПАР пе-
реносом, а о ^-разрядной группе с ПАР переносом. Для элементов
распространенных серий максимальное число входов М равно 8 и
максимальная разрядность группы &шах равна 8. Еще раз напом-
ним, что рис. 11. и 12 иллюстрируют принципы построения СМ
с ПАР переносом в базисах И-НЕ и И-ИЛИ-НЕ. При практиче-
ской работе с серией К155 набирать СМ с ПАР переносом из от-
дельных элементов нерационально, поскольку промышленность вы-
пускает совместимые с этой серией 4-разрядные СМ с ПАР пере-
носом, размещенные в одном корпусе и имеющие к тому же мень-
шее время задержки, чем СМ, набранные из россыпи.
в) УЧЕТ НАГРУЗОЧНОЙ СПОСОБНОСТИ
Из рис. 11 и 12 видно, что значения функций прозрачности я
поступают на много входов, и, начиная с некоторых значений k,
приходится для формирования функций л=аЬ или использовать
46
мощные элементы с повышенной нагрузочной способностью, или
ставить по 2—3 обычных элемента в параллель и разбивать на-
грузку по я на секции. Номера i перегруженных выходов я опре-
деляются разрядностью группы k. Так, при &=5 сверх допустимой
нагрузочной способности (10) перегружен лишь выход Яз, при &=6
в этом положении оказываются уже выходы я с индексами 2, 3, 4
и 5, при k=7—от 2 по 6 включительно. При подсчете аппаратур-
ных затрат эти дополнительные элементы должны учитываться. Для
каждого типа схем и значения разрядности программа должна так-
же вычислять нагрузку на источники входных сигналов слагаемых
Ui и Ъ\.
г) ХАРАКТЕРИСТИКИ СУММАТОРА С ПАРАЛЛЕЛЬНЫМ
ПЕРЕНОСОМ
Поскольку все схемы разрядных переносов работают парал-
лельно и имеют одинаковую структуру, время сложения группы не
зависит от числа разрядов, разумеется, в той мере, в какой время
задержки логических элементов блока переноса не зависит от числа
их входов. Время сложения группы определяется суммой задержек
блоков Б1 ПЕРЕ и БОСУМ по соответствующим трактам. Как видно
из схем на рис. 12,
Tas группы с ПАР переносом=Газ Б1СУМПАР=
=Тат Б1ПЕРЕПАР+Гг5 БОСУМ; (16)
TeS группы с ПАР переносом=Гев Б1СУМПАР=
=Гег Б1ПЕРЕПАР+ГГ5 БОСУМ. (17)
Для схем на рис. 11, 12 и схемы 12' Гая=(4-т-6)т, Tes=(3-z-
5) т.
Аппаратурные затраты ^-разрядной группы с ПАР переносом
определяются суммированием оборудования входящих в нее
блоков:
Q группы с ПАР переносом = Q Б1СУМПАР =
= Q БШЕРЕПАР-I-h.Q БОСУМ. (18)
Формулы для вычисления ОБШЕРЕПАР неудобны для про-
граммирования, поэтому как при ручном, так и при программном
синтезе сложных СМ рационально, вычислив эти величины один раз,
затабулировать их для всех возможных значений k. Для серии
К155 2^&^8. При этом нужно учесть и добавочное оборудование,
необходимое для увеличения мощности тех выходов я, нагрузка
которых превышает допустимую. При ориентировочных оценках
можно пользоваться эмпирическим соотношением
Q^7,2£2. (19)
Схемы на рис. 11, 12 и схема 12', как и схемы на рис. 5—8,
не сравнимы между собой, поскольку имеют разные сочетания
значений характеристик: схема на рис. 11 построена только на эле-
ментах И-НЕ, без И-ИЛИ-НЕ; схема на рис. 12 наиболее эконо-
мичная, а также наиболее быстродействующая, если число раз-
рядов не превышает 5: при больших k быстродействие уменьшают
подключаемые расширители по ИЛИ; схема 12' — наиболее быстро-
действующая при разрядности от 6 до 8 и вырабатывает инверсию
сигнала суммы. Характеристика «Тип переноса» для схем на рис. 5—8
имеет значение ПОС, а для схем на рис. 11, 12 и схемы 12' — ПАР.
47
В принципе на элементах серий типа К155 СМ с ПАР пере-
носом может быть построен и на число разрядов, большее 8. Для
этого многовходовые схемы И и ИЛИ блока переноса должны
строиться двухкаскадными на элементах И-НЕ и И-ИЛИ-НЕ по
аналогии с выражениями:
х1х2х3х4х8 — XiX3xa \/ х4х5; ^
Ух V Уг V Уъ V У* V У$ = Ух V Уш V V У*. J
Элемент И-ИЛИ-НЕ без подключения расширителей, т. е. без
увеличения времени задержки свыше 1т, может иметь до четырех
входов ИЛИ, что дает возможность строить на указанном прин-
ципе СМ разрядностью до 32 с временами задержки
Аппаратурные затраты такого СМ будут чрезвычайно велики.
д) ФОРМИРОВАНИЕ ВЫХОДНОГО ПЕРЕНОСА
От СМ обычно требуются не только значения разрядных сумм,
но и значение переноса из самого старшего разряда. В тактиро-
ванных устройствах при использовании ДК. т. е. когда в блоке
переноса нет циклической связи Рп—гь обычно не требуется полу-
чать значение переноса из старшего разряда раньше, чем получены
значения суммы во всех разрядах. В этом случае для получения
выходного переноса Рп нерационально строить сложную схему со-
гласно выражению (13). Выходной перенос Рп всего сумматора
с ПАР переносом можно получить проще с помощью одноразряд-
ного блока переноса БОПЕРЕ СМ с ПОС переносом типа пока-
занного на рис. 5. На входы этого БОПЕРЕ подаются перенос
в последний разряд гп и слагаемые последнего разряда ап и Ьп.
Время задержки получения выходного переноса при этом не пре-
высит время задержки получения суммы. Подчеркнем, что сказан-
ное о выходном переносе справедливо лишь для одноярусного СМ
с ПАР переносом, представляющего законченный узел, а об ис-
пользовании такого СМ как фрагмента более сложной структуры
(многоярусной) речь будет идти в § 9 и 10.
е) ПАРАЛЛЕЛЬНЫЙ СУММАТОР ОБРАТНОГО КОДА
Как следует из [14], СМ ОК работает по модулю 2n—1, для
чего тракт его переноса должен представлять собой однородное
кольцо без конца и без начала. Перенос, возникнув в любом i-м
разряде, может пройти по кольцу через все п разрядов и повлиять
на значение суммы этого же i-го разряда. Для иллюстрации по-
пробуйте выполнить операцию вычитания У=7—5 в ОК. Следова-
тельно, при использовании ПАР переноса в отличие от СМ ДК
у СМ ОК все схемы БОПЕРЕ/, вырабатывающие Pi, во всех раз-
рядах должны быть одинаковыми, причем каждая из них выра-
батывает перенос Рг- на основании анализа \ и я своего и всех
предыдущих по отношению к нему разрядов всего кольца, а не
только на основании анализа разрядов от своего, /-го, до первого,
как это делалось в СМ ДК. Эти схемы читатель при необходимости
построит самостоятельно по аналогии со схемами на рис. 11 и 12.
48
Сумматор ОК, построенный по описанному варианту, имеет значи-
тельно большие аппаратурные затраты, чем СМ ДК; время за-
держки Тав у него такое же, как и Тав у сумматора ДК. В прин-
ципе можно в качестве ПАР СМ ОК применить ПАР СМ ДК, замк-
нув в кольцо тракт переноса, но время задержки такой схемы
будет на 2т больше.
8. ДВУХЪЯРУСНЫЕ СУММАТОРЫ
Необходимость сократить время суммирования и неэффектив-
ность применения СМ с ПАР переносом при п>М заставили раз-
работчиков схем искать другие способы организации тракта пере-
носа. На сегодня известны два заслуживающих внимания способа
ускорения переноса — условный перенос и групповой. Условный пе-
ренос применим только для СМ ДК, требует больших аппаратурных
затрат и не дает выигрыша в скорости при малой и средней раз-
рядности по сравнению с рассматриваемым в книге групповым пе-
реносом. Сам принцип условного переноса достаточно подробно
описан, например, в [3] и в этой книге не рассматривается.
Наиболее эффективным в широком диапазоне разрядности яв-
ляется групповой перенос, который'и будем исследовать. Для реа-
лизации группового переноса весь СМ разбивается на m групп по
блоки
переноса
I яруса
Блок
переноса
Ляруса
Одноразрядный
Блок суммы
БОСУМ,
Одноярусные
SK Блоки суммы
(группы!
порядка)
S(k+1)
*(к+2)
Двухъярусный
Блок суммы
(группа Л
порядка)
smk
Pmk или />т/с
Рис. 13.
Б2СУМ).
4-1119
Структурная схема двухъярусного СМ (блока суммы
49
к разрядов в группе (рис. 13). Для простоты пбка будем полагать,
что число разрядов сумматора п кратно т и k, т. е. п—тк. Если
т£>л>(т—\)kt это значит, что последняя группа неполная. На-
личие неполной группы никаких осложнений не вызывает.
Каждая группа представляет собой автономный малоразряд-
ный СМ, имеющий тракт переноса между своими к разрядами. Этот
тракт будем теперь называть трактом переноса 1 яруса. Кроме
него создадим тракт переноса между группами, который назовем
трактом переноса II яруса. Этот тракт построим так, чтобы время
задержки распространения переноса между группами в тракте II
яруса оказалась меньше, чем если бы этот перенос распространял-
ся по цепям тракта I яруса, последовательно переходя из группы
в группу. В результате старшие разряды всего СМ будут вклю-
чаться в работу раньше, чем это получится в СМ с одноярусным
последовательным трактом переноса, и время сложения уменьшит-
ся. Сумматор, состоящий из нескольких групп, объединенных трак-
том переноса II яруса, будем называть двухъярусным сумматором,
или будем говорить, что СМ представляет собой группу II по-
рядка. На вход группы II порядка кроме слагаемых поступает так-
же входной" перенос, который обозначим g.
Одноярусные группы Б1СУМ имеют ^-разрядные входы сла-
гаемых а и b и вход переноса £> который является единственной
существенной в смысле времени задержки связью Б1СУМ с трак-
том переноса II яруса. С точки зрения тракта переноса II яруса
одноярусные группы Б1СУМ обладают теми же свойствами, чго и
одноразрядные блоки суммы БОСУМ с точки зрения тракта пере-
носа I яруса. Поэтому при построении тракта переноса II яруса
(блока Б2ПЕРЕ) удается использовать те же принципы, что и
при построении тракта переноса I яруса. Иначе говоря, блок
Б2ПЕРЕ может быть построен по параллельному принципу и вы-
рабатывать все групповые переносы е$ одновременно, а может быть
построен по последовательному принципу, тогда сигналы ej будут
появляться последовательно, со сдвигом во времени. Как в первом,
так и во втором случае тип переноса на I ярусе, внутри группы,
может быть как параллельным, так и последовательным. Учитывая
это, при построении различных трактов переноса II яруса исключим
из рассмотрения тип переноса на I ярусе и будем рассматривать
группу просто как ^-разрядный блок суммы I порядка Б1СУМ.
Входами блока Б1СУМ являются вход переноса е и к пар входов
для слагаемых аг- и bи выходами к выходов суммы Su а также к
выходов функций пи. которые используются при построении схем
блока переноса II яруса Б2ПЕРЕ. Как видно из рис. 13, выхода
переноса из каждой группы I порядка не требуется. Это справед-
ливо для большинства вариантов многоярусных СМ, и в большин-
стве случаев схема, вырабатывающая перенос из группы, может
отсутствовать. Случай, когда перенос из группы необходим, будет
оговорен особо в разделе о сквозном переносе. Тогда сигнал пере-
носа из группы I порядка будем обозначать ЕПС в отличие от пе-
реноса £, вырабатываемого в блоке переноса II яруса. Характери-
стиками блока суммы I порядка Б1СУМ, зная которые, можно вы-
числять характеристики двухъярусных СМ, являются Tes, Так, Q
и иногда ТаЕис. Схемы одноярусных ^-разрядных блоков суммы были
описаны в § 6 и 7.
В принятой системе деления двухъярусного СМ на блоки в це-
лях унификации принципов построения схем тракта переноса II яру-
50
са считается, что функции я вырабатываются в блоках I яруса
Б1СУМ. Это оправдано тем, что функции я, без которых нельзя
построить тракт II яруса, вырабатывают для своих внутренних
целей почти все быстрые и экономичные варианты блоков Б1СУМ.
Если же в состав двухъярусного СМ предполагается включить схе-
му ^-разрядного СМ, не вырабатывающего этих функций, то блок
Б1СУМ, включающий такой ^-разрядный СМ, должен включать и
элементы, отрабатывающие функции я. Такая ситуация возникает,
например, если в качестве блоков Б1СУМ используются 2-, 4-, k-
разрядные СМ, полученные методами интегральной технологии и
заключенные в один стандартный корпус. Интегральные СМ ча-
сто не имеют выводов из корпуса функций я, и эти функции при-
ходится получить на отдельных логических элементах. Не имеет
выходов я и схема на рис. 5, что отмечено в табл. 2 значением
характеристики Xj8. Условия, ссылающиеся на эту характеристику,
будут разрешать стыковку не имеющих выходов я одноярусных
СМ с блоками переноса II яруса только в том случае, если до-
бавлены двухвходовые И-НЕ, вырабатывающие функции я.
„Рассмотрим способы построения трактов переноса II яруса.
При этом будем иметь в виду, что аналогично II ярусу можно
ввести и III ярус тракта переноса, для которого двухъярусный СМ
будет играть роль m^-разрядного блока суммы, на который с блока
переноса III яруса будет поступать сигнал переноса g.
9. ПАРАЛЛЕЛЬНЫЙ ПЕРЕНОС НА II ЯРУСЕ
а) ПАРАЛЛЕЛЬНЫЙ ГРУППОВОЙ ПЕРЕНОС
Структура группы II порядка с трактом переноса II яруса ПАР
типа показана на рис. 14. Переносы Ej—ej+u поступающие на
вход групп Б1СУМ (/+1), вырабатываются параллельно блоком
фрагментов ПАР переноса II яруса Б2ФП как функции входного
переноса g всей группы II порядка и функции генерации Г и про-
зрачности Я /-й и. всех более младших групп I порядка. Сами
функции и 17} вырабатываются схемами ГП] как функции толь-
ко слагаемых а и Ь соответствующих групп. Таким образом, струк-
тура группы II порядка с ПАР переносом на II ярусе аналогична
структуре группы I порядка с ПАР переносом (см. § 7). Сигналу
Е в рассматриваемом случае соответствует сигнал Р, сигналу е —
сигнал г, функциям Г и 17 — функции у и я, блокам Б1СУМ/ —блоки
БОСУМ/, схемам Ф2П/ —схемы БОПЕРЕ, всему блоку Б2ПЕРЕ-
ПАР — блок Б1ПЕРЕПАР. Сравните с этой точки зрения схемы на
рис. 14 и 10. Блок Б2ПЕРЕПАР удобно представлять состоящим
из схем ГП/ и блока Б2ФП. В двухъярусном СМ ДК блок Б2ФП
состоит из схем Ф2П/, реализующих функцию (21), аналогичную
функции (13) тракта I яруса:
Е^еш^Т5уГ^хП}\/Г5.2П3.хП}\/...
... УГХП2ПЪ... ЯiVfifЯ1Я2... Я;, (21)
где g — входной перенос всей группы II порядка; Г,- и 77$— функ-
ции генерации и прозрачности ^-разрядных групп, которые входят
в состав данной группы II порядка под номером /.
Функции Г и Я ^-разрядной группы вводятся точно так же,
как и функции у и я одного разряда [см. § 7,а]. Если 1*5=1,
это значит, что k пар слагаемых /*-й группы таковы, что в группе
4* 51
Б2СУ11ПАР
Рис. 14. Структурная схема двухъярусного СМ с ПАР переносом
на II ярусе (блока суммы Б2СУМПАР).
генерируется сигнал переноса Ej=ej+\ в следующую группу неза-
висимо от того, поступил на вход /-й группы входной перенос в)
или нет. Если 77j=l, это значит, что к пар слагаемых группы та-
ковы, что при поступлении входного переноса е$ должен появить-
ся перенос Ej=ej+i в следующую группу. Функции Г$ и IJj выра-
батываются для каждой группы схемами ГП (генерация-прозрач-
ность) блока Б2ПЕРЕПАР согласно выражениям
Гз^У*VYa-i31*VYfc-2?U-irt*V • • • VYi^s .. • Лк\ (22)
/7;=Л1Л2Лз . . . nk-lJtk. (23)
52
Пример реализации схемы ГП на элементах И-НЕ для &=4
показан на рис. 15,а. Как видно из рисунка, время задержки схемы
m ТаГ = Тап + ТкГ составляет Зт, однако строить схемы с таким
временем задержки можно лишь для k^M—1, где М — максималь-
ное число входов по И элементов используемой серии. При необ-
ходимости иметь /г=М (например, байтную группу на элементах
серии К155) схему ГП придется дополнить, подключив добавочных
элементов, вырабатывающие функцию Yi (рис. 15,6). Это увеличит
время задержки ТаГ с Зт до 4т. Модифицированную таким обра-
зом схему назовем ГП8. Итак
ГкГГП = 7жЯГП = 2т; ?оГГП = Гв/7ГП = 3*; ГаГГП8 = 4г. (24)
Количество оборудования схемы ГП при реализации ее на
элементах серии К155 приведено в табл. 3. Вид схемы и аппара-
турные затраты схем ГП определяются только параметром к и
а)
Рис. 15. Пример базовой схемы
ГП блока ПАР переноса II яру-
са на элементах И-НЕ.
а —схема ГП для *-4 при *<М;
0 — добавка к схеме при Л-ЭД,
Рис. 16. Пример базового фраг-
мента Б2ФП блока ПАР пере-
носа II яруса на элементах
И-НЕ для m=3t
53
не зависят от /, т. е. все схемы ГО,,-, входящие в состав блока
Б2ПЕРЕПАР, одинаковы. Они лишь подключены к различным раз-
рядам слагаемых а и Ь. Как видно из (22) и рис. 15, с ростом
номера I растет требуемый коэффициент разветвления по выходу
источника я», а в базисе серии К155 при k, равном 7 и 8, в состав
схем ГП необходимо вводить дополнительные двухвходовые эле-
менты Й-НЕ для дублирования функций я7 и я8 по одному эле-
менту на каждую функцию. В табл. 3 оборудование этих элемен-
тов учтено.
Пример схемы Б2ФП, вырабатывающей групповые переносы
Ei согласно (21) в базисе И-НЕ для m=4, приведен на рис. 16.
На вход схем Ф2П;- поступают функции Г и П данной и всех бо-
лее младших групп.' Глубина схем равна 2, т. е.
ТЛЕ = 2х; 7^= 2т,
(25)
Входной перенос g группы II порядка ПАР типа поступает на
входы всех m—1 схем 02Uj и на вход переноса е первого блока
суммы Б1СУМ. Чтобы нагрузка источника g не превышала допу-
стимую при любых m и k, меньших восьми, в тракт ge\ включены
два двухвходовых элемента И-НЕ. Они не увеличивают время
задержки блока Б2ФП, поскольку по всем другим трактам g-Ej за-
держка также равна 2т. При подсчете оборудования два упомяну-
тых инвертора отнесем к схеме Ф2П1. Так и сделано в табл. 4,
Таблица 3
Аппаратурные затраты фрагментов блоков переноса II яруса
в двенадцатых долях корпуса элементов серии К155
Тип схемы
to
3
4
5
6
7
8
16
24
40
64
76
91
1061
25
33
49
73
85
100
115*
15
25
49
61
73
88
115*
19
21
25
37
37
37
37
14
17
25
31
31
31
37
Q ГП (рис. 15)
Q ЦГП (рис. 19, а и б)
Q Ц (рис. 19, в)
Q СП (рис. 21, б)
Q С (рис, 23 в)
Таблица 4
Аппаратурные затраты блока Б2ФП при реализации на элементах
серии К155
m
Тип схемы
» 1
со
4
5
6
7
8
<?Б2ФП (рис. 16)
(2Б2ФПОК1
15
18
29
42
5,
88
94
215
155
330
222
469
301
632
i Схема Б2ФПОК построена по принципу схемы Б2ФП на рчс. 1Q.
54
где приведены аппаратурные затраты блока Б2ФП в базисе серий
К155. В табл. 4 учтено также добавочное оборудование для уве-
личения мощности тех источников П,, у которых требуемый коэф-
фициент разветвления по выходу превышает 10.
б) ИНВЕРСНЫЙ ГРУППОВОЙ ПЕРЕНОС
Схемы одноярусных блоков суммы Б1СУМ, изображенные на
рисунках, подразумевают прямое значение сигнала входного пере-
носа е. Однако можно доказать, что свойством самодвойственностй
обладает не только логическая функция одноразрядного СМ (об
этом сказано в § 6,6), но и логическая функция сумматора с лю-
бым количеством разрядов, в том числе и 6-разрядная группа I по-
рядка Б1СУМ. Отсюда следует, что если схемы Ф2П переноса
II яруса реализованы на элементах И-ИЛИ-НЕ и вырабатывают
инверсию группового переноса Е3, то ставить после них инверторы
для согласования по тракту Е-е с блоками Б1СУМ и терять на
этом 1т не требуется. Достаточно на входах Б1СУМ поменять сиг-
налы слагаемых с прямых на инверсные »и наоборот и принять меры
для использования инвертированной суммы. При этом в тракте ge{
нужно оставить лишь один инвертор.. Ситуация аналогична той,
что возникала, когда применяли инвертирующие элементы в тракте
переноса одноразрядных СМ, построенных по рнс. 5—8. Использо-
вание элементов И-ИЛИ-НЕ даст некоторое сокращение оборудо-
вания, а при малых т — и времени задержки.
в) ВЫЧИСЛЕНИЕ ХАРАКТЕРИСТИК
Подсчитаем аппаратурные затраты группы II порядка для схе-
мы типа приведенной на рис. 14:
<ЭБ2СУМПАР=<2Б2ПЕРЕПАР+т. <ЭБ1СУМ. (26)
В случае единственной или последней группы II порядка для
ДК
(2Б2СУМПАР— (m— 1) • <2ГП+С?Б2ФП-|-т. QB1 СУМ. (27)
В случае не последней группы II порядка для ДК
0Б2СУМПАР=т. рГП+<ЗБ2ФП-Ь"г • QB 1 СУМ. (28)
Значения фБ2ФП, построенной на элементах И-НЕ, и QITI при-
ведены в табл. 3 и 4.
Времена задержки группы II порядка определяются выраже-
ниями
7,авБ2СУМПАР=ГаЯБ2ПЕРЕПАР+Ге5Б1СУМ; (29)
ТаЕ Б2ПЕРЕПАР = ГаГГП +;ГГ£Б2ФП;
Г*5Б2СУМПАР==Г*ЕБ2ПЕРЕПАР+Ге;5Б1СУМ. (30)
При реализации на элементах И-НЕ согласно схемам на
рис. 15 и 16
ТаГ = Зт для к < М\ ТаГ = 4г для к = М;
ТГЕ = 2с; TgE Б2ПЕРЕПАР = TgE Б2ФП = 2с.
Tes Б1СУМ зависит от типа блока ШСУМ.
55
г) ВЫХОДНОЙ ПЕРЕНОС ДВУХЪЯРУСНОГО СУММАТОРА
В двухярусном СМ, как и в одноярусном с ПАР переносном,
также нет смысла строить специальную сложную схему выработки
входного переноса. Если в качестве Б1СУМ использованы
Б1СУМПОС, то выходным переносом всего СМ будет перенос из
старшего разряда старшей m-й группы. Если в качестве Б1СУМ
использованы Б1СУМПАР, то выходной перенос СМ вырабатывает-
ся с помощью схемы БОПЕРЕ типа показанной на рис. 5. Из по-
следней пары слагаемых ап и Ьп и входного переноса гп блока
суммы БОСУМ последнего разряда последней группы. При обоих
типах Б1СУМ время задержки полученного таким образом вы-
ходного переноса не превышает времени задержки получения
суммы.
Если временная диаграмма цифрового устройства требует, что-
бы выходной перенос получался быстрее, чем значение суммы, то
для его отработки придется применить схему Ф2Пт, построенную
согласно (21) при \—т. Для работы СМ ДК при принятой системе
деления его на блоки организации быстрого переноса из самой
группы I или II порядка никогда не требуется, и схема выработки
переноса Рвых двухъярусного СМ не входит в состав группы II
порядка Б2СУМПАР, также как она не входила в состав
Б1СУМПАР. Схема выработки РВых является автономным базовым
фрагментом, подключаемым при необходимости к слагаемым и
входному переносу самого последнего, старшего разряда всего СМ
с любым числом ярусов.
д) ДВУХЪЯРУСНЫЙ СУММАТОР ОБРАТНОГО КОДА
При построении двухъярусного СМ ОК тракт переноса II яру-
са должен быть замкнут в кольцо. При этом принцип построения
блока Б2ПЕРЕПАРОК аналогичен- принципу построения блока ПАР
переноса одноярусного СМ, описанному в § 7,е. Блок Б2ПЕРЕПА-
РОК состоит из т обычных схем ГП и блока Б2ФПОК, в состав
которого входят т одинаковых схем Ф2ПОК. Схема Ф2ПОК; реа-
лизует выражение
. . . j-(m-i)#j-(m_2) • • • П}-ХП]. (31)
Схемы Ф2ПОК читатель легко построит самостоятельно по
аналогии со схемой рис. 16. Аппаратурные затраты блока Б2ФПОК
при реализации на элементах серии К155 приведены в табл. 4.
Аппаратурные затраты двухъярусного СМ ОК определяются вы-
ражением
<ЭБ2СУМПАРОК=т • <ЭГП+£Б2ФПОК+т QB1 СУМ. (32)
Время задержки двухъярусного СМ ОК совпадает с временем
задержки двухъярусного СМ ДК, т. е. определяется (29).
Рассматривая двухъярусные сумматоры ОК, обратим внимание
на то, что различия схем сумматоров ДК и ОК касаются только
тракта II яруса. Блоки Б1СУМ, являясь многоразрядными блоками
суммы, не участвуют в замыкании или размыкании кольца тракта
переноса. Блоки Б1СУМ одинаковы для двухъярусных СМ ДК и
ОК. Это еще одна положительная сторона принятого деления СМ на
блоки.
56
е) СВОЙСТВА ПП и ПЦ СУММАТОРОВ
Введем^ для последовательного переноса на I ярусе еще одно
название — цепной или ЦЕП, или Ц. Как будет видно из § 10 и И,
это будет способствовать унификации названий типов СМ. Тогда
двухъярусные СМ с ПАР переносом и на II, и на I ярусе будем на-
зывать параллельно-параллельными, или ПП, а СМ с ПАР перено-
сом на II ярусе и последовательным, т. е. цепным, переносом на I
ярусе — параллельно-цепным, или ПЦ. Рассмотрим свойства этих
классов СМ.
В ПП СМ при М=8, т. е. в большинстве современных серий эле-
ментов, максимальные значения т и k ргавны 8, а максимальная раз-
рядность ПП СМ «=8-8=64 разряда. До «=8-7=56 разрядов при
использовании в трактах переноса элементов И-НЕ и Б1СУМ типа
схемы 12' время сложения ПП CM Tas=9r. При 56<«^64 ras=10r.
ПП СМ обладают минимальным временем задержки среди СМ
с групповым переносом начиная, как увидим далее, с «=16. Весь
тракт получения разрядного переноса Р ПП сумматора содержит
три логические ступени И-ИЛИ (И-НЕ — И-НЕ): я-Я, П-Е и е-Р.
При заданной разрядности п можно составить несколько пар «г,
k, удовлетворяющих условию mk~n. Полученные варианты СМ бу-
дут одинаковыми или почти одинаковыми по быстродействию, но бу-
дут отличаться по затратам оборудования, причем наиболее эконо-
мичными будут решения с малыми k. Поэтому разработчику или про-
грамме можно не просматривать все возможные варианты разбие-
ний, а изучить лишь решения с двумя-тремя наименьшими значе-
ниями k. Ограничиваться только одним минимальным значением k
опасно: из-за существенной нелинейности пространства можно поте-
рять хорошее решение.
Таким образом, при работе в базисах типа К155 для СМ ПП
можно пользоваться такими соотношениями:
допустимые значения: 2^т^8; 2^6^8;
оптимальное значение k близко к минимально возможному;
7,as=10r при 6=8; Tas=9x при 5<£<7;
Tas^8t при &=2-г-4 и Б1СУМПАР типа изображенного на
рис. 12;
величина Q вычисляется по (26) — (28) и табл. 3 и 4.
В настоящее время промышленность выпускает набор схем сред-
ней интеграции, совместимых с серией К155 и позволяющих строить
СМ ПП типа. Набор состоит из уже знакомых нам базовых схем I
и II* яруса: в корпус 1-го типа заключены 4-разрядный СМ с ПАР
переносом (группа Б1СУМПАР с 6=4) и схема ГП данной группы,
построенная по принципу схемы на рис. 15 и имеющая выводы Г и
Я. В корпус 2-го типа заключена схема выработки групповых пере-
носов Б2ФП для четырех групп («г=4), аналогичная показанной на
рис. 16. Набор позволяет строить ЛП СМ с «=16 на четырех кор-
пусах 1-го типа и одном корпусе 2-го типа. Время задержки такого
СМ значительно меньше, чем ПП СМ, набранного из россыпи. Есть
серии, в состав которых входят заключенные в один корпус схемы Г
и П группы разрядов.
Параллельно-цепные сумматоры по сравнению с ПП СМ имеют
большее значение Tas и меньшее Q. При заданном « по мере уве-
личения k растет Tas и падает Q за счет уменьшения оборудования
тракта переноса II яруса, в результате среди множества ПЦ СМ поч-
ти все варианты с разными k оптимальны по Парето. Среди ПЦ СМ
5^1 Ц9 \>7
существует быстрый 16-разрядный СМ с т=8, &=2 и Б1СУМЦЕП
по рис. 6, Tas которого равно всего 8т.
Ориентировочные расчетные соотношения для СМ ПЦ типа на
серии К155 и Б1СУМ по рис. 6:
допустимые значения: 2^/л^8; 2^&^8; пробовать все значе-
ния k'
fa8(7+k)x при k^7\ ras=16T при k=B.
При использовании в качестве Б1СУМ схемы на рис. 22 (эта
схема описана в § 11) для 6^5 значение TaS уменьшается примерно
на 2т. При построении блока Б2ФП на элементах И-ИЛИ-НЕ и
2^т^С4 значение Tas уменьшится примерно на 1т. Если группы име-
ют различную длину, то величина Tas определяется значением k
самой длинной группы.
10. ЦЕПНОЙ ПЕРЕНОС НА I! ЯРУСЕ
а) БЛОК ЦЕПНОГО ПЕРЕНОСА
Цепной перенос между группами является одним из вариантов
последовательного межгруппового переноса в тракте II яруса.
Структурная схема группы II порядка такого типа показана на рис.
17. Перенос Ej==ej+i вырабатывается схемами Ф2Щ блока
Б2ПЕРЕЦЕП как функция слагаемых /-й группы- и входного пере-
носа в у'-ю группу е\. Схемы Ф2Ц/ включены последовательно по
тракту межгруппового переноса еЕ точно так же, как и в одно-
ярусном СМ с ПОС переносом (блоке Б1СУМПОС) включены
схемы разрядного переноса Б0ПЕРЕ1.
Блок Б2ПЕРЕЦЕП получается экономичнее по затратам обо-
рудования, чем блока ПАР переноса II яруса Б2ПЕРЕПАР. Одна-
ко в результате задержки распространения переноса в тракте
II яруса время сложения СМ с ЦЕП переноса обычно превышает
время сложения СМ с ПАР переносом на II ярусе.
Перенос из /-й и k-й разрядной группы Ej=Ej+l вырабаты-
вается по тому же принципу, что и перенос г г внутри группы с ПАР
переносом [см. (13)], поскольку перенос из ^-разрядной группы —
3-tq фактически перенос из k-то в следующий, (k-\-\)-Pi "разряд:
E = Ph=fh + lz=Clkbk\/uh-ibk-iJth\/Clh-2bk-2Rh-\7lh\/ • . .
... \/ахЬхп2Пъ ... 7ih\fenxn2 ... Пк=Г\/еП. (33)
С точки зрения организации тракта переноса II яруса
Е?=е1+1=ГМе}П}. (34)
Временные диаграммы работы блоков группы II порядка с раз-
личными типами переноса на II ярусе показаны на рис. 18. Времена
задержки одноразрядного СМ — tар, trp и trs, из которых состоит
временная диаграмма многоразрядного СМ, изображены на рисунке
линиями разного типа. Сравните диаграммы работы и различные со-
ставляющие общего времени задержки при ПАР (рис. 18,а) и ЦЕП
(рис. 18,6) переноса на II ярусе. Диаграммы на рис. 18,в—е станут
понятные после прочтения § 11.
Схемы Ф2Ц, из которых состоит блок ЦЕП переноса
Б2ПЕРЕЦЕП, должны реализовать выражение (33). Кроме того, за-
бегая вперед, отметим, что если в состав СМ входит не одна, а не.»
58
82СУНЦЕП
Рис. 17. Структурная схема двухъярус-
ного СМ с ЦЕП переносом на II ярусе
(блока суммы Б2СУМЦЕП).
сколько групп II порядка и потребуется тракт переноса III яруса, то
для его построения будут необходимы функции генерации и проз-
рачности каждой группы Г$ и FIj точно так же, как и для построе-
ния тракта переноса II яруса требовались функции Yi и я>з разря-
дов. Схему, полученную модификацией групповой схемы Ф2Ц и вы-
рабатывающую на основе одновременного анализа всех слагаемых
группы не только сигнал переноса из группы Е, но и функции Г и
Я, назовем схемой ЦГП («цепной, генерация, прозрачность»). При-
5* 59
Рис. 18. Временные диаграммы работы двухъярусных СМ с я=16,
т—4 с ПОС переносом на I ярусе и различными типами переноса
на II ярусе.
а — параллельным; б — цепным; в —сквозным; г — одноярусным СМ с после-
довательным переносом; д —цепной перенос с различной длиной групп; е-
сквозной перенос с различной длиной групп.
мер ее реализации для 3 показан на рис. 19,а. Схема фактически
является некоторым развитием схемы ГП, используемой при ПАР
переносе на II ярусе. Как и в случае схемы ГП, если k=My то к схе-
ме ЦГП подключаются два добавочных элемента, показанных на рис.
19,6. В сериях, для которых М=8, такую модификацию схемы будем
называть схемой ЦГП8. Она имеет увеличенную задержку: 7аЕ=6т,
ТаГ =4т.
Если СМ состоит всего из одной группы II порядка или если
в трехъярусном СМ рассматриваемая группа II порядка последняя,
то функции Г и Я не нужны и схема Ф2Ц должна вырабатывать
только значение переноса из группы Е. Такую модификацию назовем
схемой Ц (рис. 19,в). Она экономичнее по аппаратурным затратам и
имеет меньшее время задержки по тракту аЕ. При &=М вместо схе-
мы Ц приходится использовать схему типа ЦГП8.
Схемы Ц и ЦГП можно построить и на элементах И-ИЛИ-НЕ,
что повлечет инвертирование группового переноса Е. Чтобы не те-
рять 1т на дополнительном инверторе, следует инвертировать сла-
гаемые на входах тех групп, на которые поступает инверсия группо-
вого переноса Е, о чем уже говорилось в § 9,6. При этом, если k
невелико, время задержки тракта переноса II яруса ТвЕ, которое
равно 2т на группу при использовании элементов И-НЕ, в схеме на
элементах И-ИЛИ-НЕ будет составлять 1т на группу.
При работе в ДК, так же как и в случае блока Б2СУМПАР,
функции, вырабатываемые схемой Ф2П/ с номером /=т, внутри бло-
60
Рис. 19. Примеры базовых фрагментов Ф2Ц блока ЦЕП переноса
II яруса на элементах И-НЕ.
а — схема ЦГП для &=3 при &<М; б — добавка к схеме ЦГП при £ = М; в се-
рии К155 такую добавку имеет схема ЦГП8; в — схема Ц для & = 3 при &<М.
ка Б2СУМЦЕП не используются. Они нужны лишь для построения
тракта переноса II яруса. Поэтому, если СМ лишь двухъярусный
или если в трехъярусном СМ данная группа II порядка последняя,
то схему Ф2Цт можно не включать в состав группы II порядка.
Выходной перенос РВых двухъярусного СМ с ЦЕП переносом
получается тем же путем, что и в двухъярусном СМ с ПАР перено-
сом на II ярусе: в случае Б1СУМПОС—как естественный перенос из
последнего'разряда последней группы, а в случае Б1СУМПАР—
с помощью простой схемы БОПЕРЕ типа, приведенной на рис. 5.
Схема Рвых, вырабатывающая выходной перенос, является автоном-
ным блоком (самостоятельным базовым фрагментом) и не входит
в состав группы II порядка с ЦЕП переносом.
Полные затраты оборудования группы II порядка определяются
выражением
<2Б2СУМЦЕП=0Б2ПЕРЕЦЕП+т • QB1СУМ. (35)
В случае единственной или последней группы II порядка
С2Б2СУМЦЕП=(/л— 1)-QlX+m- <2Б1СУМ. (36)
В случае не последней группы II порядка
<2Б2СУМЦЕП=т • <ЭЦГП+т • QB 1 СУМ. (37)
Аппаратурные затраты блоков Ц и ЦГП при выполнении их на
элементах И-НЕ серии К155 приведены в табл. 3. Время задержки
61
группы II порядка с ЦЕП переносом вычисляется аналогично вре*
мени задержки СМ с ПОС переносом [ср. следующие выражения
с(3)-(5)]:
Тав Б2СУМЦЕП=Гая Ф2Ц+(т—2) -ТеЕ Ф2Ц+Те8 Б1СУМ; (38)
Тв8 Б2СУМЦЕП=(т—1) -ТеЕ Ф2Ц+Те8 Б1СУМ; (39)
Тав Б2СУМЦЕП=Га£ Ф2Ц-Н/П— 1) -ТеЕ Ф2Ц. (40)
При реализации схем, изображенных на рис. 19, на элементах
серии К155 Г«* Ф2Ц=(2-8-6)т, TeS Ф2Ц=(1-г-2)т в зависимости от
типа схемы Ф2Ц.
б) ПЕРЕМЕННАЯ ДЛИНА ГРУПП
Время задержки группы II порядка с ЦЕП переносом и на If,
и на 1 ярусе можно несколько сократить за счет введения перемен-
ной длины групп. Поскольку младшие группы включаются в работу
раньше старших (см. рис. 18,6), длина старших групп может быть
уменьшена за счет увеличения длины младших. Экономия во време-
ни здесь может достигнуть величины (0,5н-1)-тт. Пример оптималь-
ного подбора длин групп для ai=16, т=4 показан на рис. 18Д
Сумматор с неодинаковыми группами неудобен с точки зрения тех-
нологии производства, комплектации ЗИП и обслуживания аппара-
туры, поэтому в ремонтируемых изделиях массового выпуска такое
решение используется редко.
Для превращения двухъярусного СМ 'ДК с ЦЕП переносом
в СМ ОК нужно лишь замкнуть в кольцо цепь .межгруппового пере-
носа. Чтобы не вносить лишнего времени задержки, блок переноса II
яруса Б2ПЕРЕЦЕПОК должен иметь в своем составе схему Ф2Ц/
с /=т, вырабатывающую перенос из m-й группы, £m=Gnc, который
подается на вход переноса g того же блока Б2ПЕРЕЦЕПОК. Как
и в случае двухъярусного СМ с ПАР переносом, разница в схемах
ДК или ОК коснулась лишь тракта II яруса, но не схем Б1СУМ.
в) СВОЙСТВА ЦП И ЦЦ СУММАТОРОВ
Сумматоры с ЦЕП переносом на II ярусе и ПАР на I будем
называть сумматорами ЦП, а с ЦЕП на II ярусе и ЦЕП на I — ЦЦ.<
В отличие от сумматоров с ПАР переносом на II ярусе (классов ГШ
и ПЦ), где число групп I порядка ограничено величиной М (8 для
серии К155), в ЦП и ЦЦ СМ число групп может быть любое, одна-
ко хорошими оказываются не все значения т.
Сумматоры ЦП с гп^Ъ унаследовали от ближайших родствен-
ных схем ПП и ЦЦ типа их основные недостатки — большие затра-
ты оборудования и существенное время задержки. Эти схемы никог-
да не попадают в группу СМ, оптимальных по Парето. Сумматоры
ЦП с т=2, наоборот, обладают уникальным свойством: они имеют
минимальное время задержки среди всех двухъярусных СМ. Хотя
это и может показаться странным, но их время задержки примерно
на 2т меньше, чем ПП СМ (см. рис. 24). При использовании в схемах
Ф2Ц элементов И-ИЛИ-НЕ сумматор ЦП может оказаться конку-
рентоспособным с ПП СМ даже при /л=3-*-4.
Ориентировочные соотношения для ЦП СМ:
допустимые значения.т^2; 2^&^8;
оптимальное значение k лежит среди чисел 2—4;
-62
при ТеЕ—2х (схемы Ф2Ц выполнены на И-НЕ)—Tas=(2m-{-3)x
при 6<С7; Tas=(2m+6)T при 6=8;
при ТеЕ=1х (схема Ц выполнена на И-ИЛИ-НЕ; 6 мало) Tas=
= (т+4)т.
Время задержки СМ другого класса — ЦЦ — при одинаковой
длине групп I порядка определяется суммой задержек тракта пере-
носа II и I ярусов [см. (38) и рис. 18,6]. Подставив (4) в (38), по-
лучим, что переменной составляющей задержки Tas, зависящей от
способа разбиения на группы, является выражение т-ТеЕ-\-к-Тгр,
которое нужно минимизировать. Положив, что все группы одинако-
вы, т. е. m-k=nf и приравняв нулю производную этого выражения
по 6, получим соотношение, определяющее оптимальную с точки зре-
ния задержки длину группы ЦЦ СМ:
При 7гР=1т и TeE=(\-t-2)x 6опт=(1-*-1,4) • V п, однако зависи-
мость Tas=f(k) довольно пологая. Величина Q ЦЦ СМ почти не
зависит от 6.
11. СКВОЗНОЙ ПЕРЕНОС НА II ЯРУСЕ
а) ОРГАНИЗАЦИЯ СКВОЗНОГО ПЕРЕНОСА
Сквозной (СКВ) перенос между группами — это вторая разно-
видность последовательного переноса на II ярусе. Наличие двух ти-
пов последовательного межгруппового переноса и объясняет, почему
нельзя назвать ЦЕП перенос просто последовательным. Структурная
схема группы II порядка со СКВ переносом показана на рис. 20,
а упрощенная схема выработки группового переноса II "яруса Ф2С —
на рис. 21,а. Как видно из рисунков, СКВ перенос отличается от
ЦЕП тем, что в схемах Ф2С блока Б2ПЕРЕСКВ вырабатывается
только функция прозрачности Пj группы, обеспечивающая сквозное
прохождение переноса е через прозрачные группы. Специальной схе-
мы, вырабатывающей функцию генерации Г$ группового переноса,
нет. Роль схемы генерации играет тракт последовательного внутри-
группового переноса I яруса, формирующий выходной перенос из
группы Епс. Таким образом, перенос на II ярусе определяется выра-
жением
£/ = в/+1 = £усуЗД. (42)
Заметим, что ни для ПАР, ни для ЦЕП переноса на II ярусе
выхода Епс из группы I порядка не требовалось.
Время сложения СМ^ со СКВ переносом будет максимальным
при таком сочетании слагаемых, когда перенос возникает в самом
младшем разряде и влияет на сумму самого старшего разряда. При
этом он должен пройти первую группу по тракту I яруса, группы от
второй до предпоследней — по тракту II яруса и последнюю группу—
снова по тракту I яруса.
Если схемы Ф2С построены по простейшему варианту (рис.
21,а), то в случаях, когда группа прозрачна, в ней образуются два
чараллельных пути для сигнала переноса: один — быстрый, по тракту
63
б2сумскв
н
ч
I.
ЧЧ
15
<PZCZ
4>ZCJ
А сп
Z. или
Н о
(рисЯГ)
<PZCrn
St
sk+1
smk
нужно подавать не £пс,а функцию
Рис. 20. Структурная схе-
ма двухъярусного СМ
с СКВ переносом на
II ярусе (блока суммы
Б2СУМСКВ).
II яруса, другой — мед-
ленный, по тракту I яру-
са, и оба эти пути объ-
единяются на элементе
ИЛИ. Схема с парал-
лельным включением бы-
строго и медленного
трактов, оканчивающая-
ся элементом ИЛИ, быст-
ро проводит фронт еди-
ничного сигнала и мед-
ленно — фронт нулевого,
г. е. схема быстро воз-
буждается, но медленно
успокаивается даже пос-
ле поступления на вход
короткой помехи. - Этот
эффект состязаний при-
водит к тому, что двухъ-
ярусный СМ с трактом
переноса по схеме на
рис. 21,а практически
оказывается ничуть не
быстрее, чем простейший
одноярусный СМ с по-
следовательным перено-
сом. Это явление де-
тально разобрано в [15].
Чтобы избавиться
от нежелательных со-
стязаний, можно пред-
ложить перекрывать вы-
ход тракта переноса I
яруса в том случае, ко-
гда в группе нет ни од-
ного сигнала генерации
разрядного переноса уг,
т. е. когда этот выход
наверняка не нужен. Для
этого на вход 2 элемен-
та ИЛИ (рис. 21,а)
Очевидно, что это, с одной стороны, не помешает выходу из бло-
ка Б1СУМ зародившегося там переноса (при этом по крайней мере
одна уг будет равна 1), а с другой стороны, перекроет внутригруп-
повой тракт в опасном случае, когда Г=0, Я=1. Схемы Ф2С, pea-
64
Рис. 21. Примеры базовых фрагментов Ф2С блока СКВ переноса на
II ярусе.
а — упрощенная схема Ф2С/ с подключенным /-м блоком суммы I порядка;
б — схема СП для &=4; в — схема С для k=A.
лизующие принцип работы, показанный на рис. 21,а, и имеющие
блокировку тракта Епс при Г=0, Я=1, показаны на рис. 21,6 и в.
Схема СП («сквозной и прозрачность»), на рис. 21,6 используется,
если групп II порядка больше одной, т. е. когда для организации
переноса между ними на III ярусе требуется функция прозрачности
IJj групп. Следует иметь в виду, что функция Г* не тождествен-
на функции генерации Г и на III ярусе может использоваться лишь
в блоке переноса типа СКВ. Схема С (рис. 21,б) используется,
если весь СМ двухъярусный, т. е. состоит всего из одной группы II
порядка, или если в трехъярусном СМ данная группа II порядка
последняя. При k=M вместо схемы С используется схема СП. Схе-
мы СП и С можно строить и на основе элементов И-ИЛИ-НЕ с уче-
том замечания об инвертированном переносе в § 9,е. Для работы
совместно с Б1СУМ, имеющими двухпроводный тракт переноса, на-
пример см. рис. 7, в схемах С и СП предусмотрены два конъюнктив-
ных входа для Елс. Для работы с Б1СУМ, имеющими парафазный
тракт переноса типа,'Приведенного на рис. 8, схему С или СП легко
дополнить инвертором или элементом И-ИЛИ-НЕ, на котором из
полуфабрикатов £пс, е, П будет формироваться инверсия перено-
са Е.
Для схем СП и С функции я можно использовать лишь в форме
л/=аф Ь. Кроме этих функций необходимы еще функции у, которые
не были нужны для трактов переноса ПАР и ЦЕП типа, поэтому
совместно со СКВ переносом целесообразно использовать те типы
групп I порядка, которые вырабатывают эти функции для своих
65
внутренних нужд, как, например, Схемы на рис. 7 и 8. Ё связи с этим
мы и на I ярусе будем делить Б1СУМ с ПОС переносом на схемы
Б1СУМЦЕП, не вырабатывающие функций у и стыкующиеся на II
ярусе лишь с трактами ПАР и ЦЕП, и схемы Б1СУМСКВ, которые
непосредственно стыкуются с трактом СКВ переноса на II ярусе.
Это деление отражено в значении стыковочной характеристики
Xj7 табл. 2. Как следствие» будем полагать, что существует лишь
один класс двухъярусных СМ со СКВ переносом — класс СС.
Аппаратурные затраты при реализации схем СП и С на элемен-
тах серии К155 приведены в табл.*3. Как видно- из этой таблицы,
схемы, а "следовательно, и весь блок Б2ПЕРЕСКВ в среднем пример-
но вдвое экономичнее блока Б2ПЕРЕЦЕП особенно при больших k.
Времена задержки группы II порядка со СКВ переносом опре-
деляются выражениями
7flS Б2СУМСКВ = ТаЕПс Б1СУМ + Г£Пс^Ф2С +
+ (m — 2) • ТеЕФ2С + TeS Б1СУМ; (43)
TgS Б2СУМСКВ == (ж — 1).ТеВ Ф2С + TeS Б1СУМ; (44)
TaG^ Б2СУМСКВ = ТаЕПС Б1СУМ + T£ПС£ Ф2С + (m- 1)Тв£Ф2С.
(45;
При р"аботе в ДК и использовании, СКВ переноса, так же как и'
в случае ЦЕП, можно при некоторых значениях п несколько умень-
шить время задержки Tas за счет применения групп различной дли-
ны. Соотношение длин групп здесь иное, чем при ЦЕП переносе: при
СКВ переносе длины групп должна сначала увеличиваться от млад-
шей к средней, а затем снова уменьшаться. На рис. 18,0 показана
временная диаграмма группы II порядка со СКВ переносом и оди-
наковыми группами, позволяющая сравнить этот способ переноса
с ПАР и ЦЕП, а на рис. 18,е показан пример подбора длин групп
для л=16, /п=4. Ограничения на применение групп различной длины
те же, что и в случае ЦЕП переноса по соображениям унификации.
Сумматор с СКВ переносом — самый дешевый по затратам обо-
рудования, но и самый медленный из всех двухъярусных СМ. По
мере уменьшения разрядности п эффективность сумматоров со СКВ
переносом быстро падает, и при п меньше 16—24 применение их
практически теряет смысл.
Ориентировочные расчетные соотношения для СМ СС:
допустимые значения: т^2; 2^&^8;
при ТеЕ=2х (II ярус_построен на элементах И-НЕ) оптимальное
значение k близко к У л, экстремум пологий и Tas=(2k-\-2m-\-l)x.
При Ге£=1т (в тракте II яруса используются элементы И-ИЛИ-НЕ)
оптимальное значение k близко к V п/2 и Tas=(2k-\-m-^-2)x.
б) СУММАТОР С ПЕРЕМЕЖАЮЩИМСЯ ПЕРЕНОСОМ
На рис. 22 показана интересная модификация двухъярусного СМ
со СКВ переносом, в котором на II ярусе используются три идентич-
ных канала переноса. Для каждого канала длина групп равна 3
(&=3). Разбиение СМ на группы для разных каналов сделано со
сдвигом на один разряд — перемежающийся перенос. Каждый разряд
СМ оказывается первым в группе одного из трех каналов-переноса.
66
a
f"1
IPs
bi-
ts
°7
Ф7
be—
<l>8
*\1
1
&
&
Фв-
1
1
&
&
1
1
Рис. 22. Сумматор с перемежающимся переносом (с трехканальным
сквозным переносом на II ярусе при k = 3).
Я|?1 = а<ф&г; Q=27 на один разряд.
Для других каналов этот же разряд окажется соответственно вто-
рым и третьим. Для каждого разряда схема, вырабатывающая ПОС
перенос из данного разряда (схема I яруса), совмещена в одном эле-
менте И-ИЛИ-НЕ со схемой того канала переноса II яруса, для ко-
торого этот разряд — первый в группе. Каждая разрядная схема
тракта переноса состоит из одного элемента И-ИЛИ-НЕ, это Дает
экономию оборудования, но сигналы переносов, сумм и некоторые
входные сигналы оказываются взаимно инверсными в четных и не-
четных разрядах.
Рассмотрим работу схемы. Сигналы -фг==аг- @Ь{ вырабатываются
на элементах И-ИЛИ-НЕ уже знакомым способом:
Ъ = афь = аьу аь.
67
Значения суммы получаются согласно выражениям:
для нечетных i: St = г\/ ф,-/^; 1
для четных i: St = Ф^- г\/ Ф^-Р/. J
Эти выражения использовались при построении СМ по схеме на
рис. 6.
Значения переносов вырабатываются на элементах И-ИЛИ-НЕ:
для нечетных i: Pt = aibi\/ V Я/-8Ф}-2Ф/-,Ф/; )
^= = г= (47)
для четных /: Р{ =aibt V Pi-^i V ^i-a*/-2*/-i*/. J
Выражение для нечетных i очевидно: два первых его члена пред-
ставляют собой разрядный перенос P=y\Jrty, а третий член описы-
вает СКВ тракт переноса для 6=3, т. е. тракт, пропускающий груп-
повой перенос Pi-3, если все три разряда группы прозрачны. В спра-
ведливости выражения для четных i убеждает свойство самодвойст-
венности или прямой анализ таблицы соответствия. Чтобы показать
регулярные связи, на рис. 22 изображен фрагмент СМ без первых
разрядов. При построении полной схемы СМ на входы переносов
Pi-i первого разряда и Pi-z третьего разряда подается входной пе-
ренос CM gy на вход первого и, следовательно, г|)г-2 второго —
нуль. Сигналы на остальных входах, имеющих отрицательные номе-
ра, могут быть произвольными. В принципе можно подать на вхо-
ды значения переносов, обратные описанным, начав нумерацию раз-
рядов сумматора с номера f=0. В качестве выходного переноса СМ
используется перенос из последнего, старшего разряда.
Времена задержки СМ вычисляются согласно выражениям
TaS = 2т1 + 2т2 + [л/4]2т2+{1т2, если ост [я/4] = 3}; (48)
г л Пт2> если ост [п/4] = 2\
TeS=Ul + \i2 + [n/4]2x1 + { " 7 }, (49)
(2г2, если ост [/г/4] = 3 I
где [/г/4]—целая часть п/4; ост [п/4]—остаток от деления п/4;
Ti — задержка элемента И-ИЛИ-НЕ с М = 2, L = 2; т2 —задержка
элемента И-ИЛИ-НЕ с М=4, L=3, (М — число входов И, L — число
входов ИЛИ).
Введение индексов у т необходимо потому, что в ряде серий
элементов время задержки заметно зависит от L:
TaG — TaS—Ть TeG = TeS—Tj. (50)
При ориентировочных оценках можно пользоваться приближен-
ным выражением
Гав^(4+л/2)т2; 7^(24-/1/2)т2.
Задержка СМ пропорциональна п/2, а не /г/3, как это может
показаться с первого взгляда". Дело в том, что цепи СКВ переноса,
построенные на элементах И-ИЛИ-НЕ, ускоряют втрое лишь сигнал
переноса Е и совсем не ускоряют его инверсий Е. Поскольку знак
переноса изменяется после каждого элемента И-ИЛИ-НЕ, то на каж-
дой четверке соседних разрядов сумматора время задержки равно
2т2: Тг на первые три разряда и Тг на четвертый разряд.
Аппаратурные затраты этого СМ на один разряд составляют 27
двенадцатых долей корпуса серии К155, что немногим больше, чем
68
у обычных одноразрядных СМ, время задержки же его в среднем на
30% меньше.
К достоинствам СМ на рис. 22 относится и то, что все разряды
его схемно одинаковы и обращаться с ним так же просто, как и
с одноярусным СМ с ПОС переносом: требуется лишь соединить
в цепочку нужное число разрядов. Поэтому СМ на рис. 22 может
с успехом исполнить роль группы I порядка Б1СУМЦЕП в составе
двухъярусного СМ, тем более что при больших к схема имеет мень-
шую задержку, чем схемы на рис. 5—8. Строго говоря, получившийся
СМ будет уже трехъярусным, однако в силу особенностей схемы на
рис. 22 программа синтеза двухъярусных СМ формально может об-
ращаться с этой схемой точно так же, как и со схемами на рис. 5—8.
12. ТРЕХЪЯРУСНЫЕ СУММАТОРЫ
Сумматор может состоять не только из одной, но и из несколь-
ких групп II порядка. Такой СМ будем называть трехъярусным, или,
что то же самое, будем говорить, что СМ построен как группа III.
порядка. При этом каждая группа II порядка рассматривается как
m/г-разрядный блок суммы II порядка Б2СУМ, имеющий вход пере-
носа g. Для выработки g строится блок переноса III яруса. Тракт
переноса III яруса, как и тракт переноса II яруса, можно сделать
ПАР, ЦЕП или СКВ. К блоку переноса III яруса какого-либо типа
могут в качестве блоков суммы подключаться блоки Б2СУМ с раз-
личными способами распространения переноса на II ярусе*. Ситуация
полностью аналогична той, что возникала при компоновке блока
Б2СУМ из блока Б2ПЕРЕ и блоков Б1СУМ различных типов.
Аналогично можно увеличивать число ярусов СМ и дальше, од-
нако при наиболее распространенных значениях разрядности л^64 и
максимальном числе входов элементов М=8 увеличение ярусности
больше трех практически не дает выигрыша ни во времени задерж-
ки, ни в количестве оборудования. Поэтому будем рассматривать
лишь одно-, двух- и трехъярусные сумматоры. Структурные и функ-
циональные схемы и формулы, относящиеся к III ярусу тракта пере-
носа, полностью аналогичны схемам и формулам, относящимся ко II
Таблица 5
Взаимное соответствие обозначений в двухъярусных и
трехъярусных сумматорах
Базовые схемы, блоки
Сигналы
Индексу
Группа II
порядка
Группа III
порядка
Группа II
порядка
Группа III
порядка
Груша II
порядка
Группа III
порядка
Б2СУМ
Б1СУМ
Б2ПЕРЕ
Б2Ф
Ф2
ГП
Ц
С
БЗСУМ
Б2СУМ
БЗПЕРЕ
БЗФ
ФШ
ГПШ
ЩИ
"СШ
g
е
Е
Г
П
Y
ab, у
''вх
р
'вых
8
G
ГШ
//III
Г
П
Г
/
т
i
k
Группа I
порядка
Разряд
г
1
i
W
Группа II
порядка
Группа I
порядка
69
ярусу, и особых пояснений не требуют. При необходимости для ре-
шения конкретных вопросов, касающихся структуры трехъярусных
СМ ДК с ПАР, ЦЕП или СКВ переносом на III ярусе, можно поль-
зоваться структурными схемами на рис. 14, 17 или 20 групп II по-
рядка, произведя в них замену обозначений в соответствии с табл. 5.
В таблице слева стоят обозначения, используемые в рис. 14, 17
и 20 и относящиеся к группе II порядка, а справа — соответствую-
щие им обозначения для группы III порядка.
Поскольку считаем, что III ярус — последний и тракта переноса
следующего яруса нет, в состав блоков переноса III яруса БЗПЕРЕ
входят лишь схемы типа ГПШ, ЦШ, CIII. Схемы типа ЦГШП и
СП1И на III ярусе не применяются. Число схем ГПШ, ЦШ или СШ
при использовании ДК равно /—1, где / — число групп II порядка.
Пример реализации схем ГПШ и БЗФП на элементах И-НЕ приве-
ден на рис. 23. Схемы ЦШ и СШ аналогичны схемам Ц и С на
рис. 19 и 21. Схемы ГПШ, ЦШ, СШ в качестве входных величин
используют функции Г и Я, которые вырабатываются схемами, вхо-
дящими в состав тракта II яруса, точно так же, как в свое время
в тракте переноса II яруса были использованы функции л, выраба-
тываемые схемами I яруса.
Выходной перенос сумматора ДК получается так же, как и
в двухъярусном сумматоре.
Количество оборудования трехъярусного СМ вычисляется как
сумма затрат оборудования входящих в него блоков. Для СМ ДК
(ЭБЗСУМПАР=<ЭБЗПЕРЕПАР+/-ОБ2СУМ=
==QOIIin+(/-l) .QrmiI+/-QB2CyM; (51)
70
УБЗСУМЦЕП=.фБЗПЕРЕЦЕП-|-/ • <ЭБ2СУМ=:
=(/-1) .QmiI+/.QB2CyM; (52)
QB3CyMCKB==QB3nEPECKB+/ -QB2CyM=
= (/—1) .QCIII+/-QB2CyM. (53)
Времена задержки трехъярусных СМ ДК вычисляются по фор-
мулам
БЗСУМПАР = ТаГ Б2СУМ + ТггШ ГПШ + TflllG ФИШ +
+ TgS Б2СУМ; (54)
TaS БЗСУМЦЕП = ?аГБ2СУМ + ТгдЩ\\ + (/ - 2) .7^0ЦШ +
+ TgS Б2СУМ; (55)
БЗСУМСКВ = ГаоПс Б2СУМ + ТQncQ СШ + (/ - 2) • 7^0СШ +
+ 7'fSB2CyM. (56)
Для базиса серии К155, и элементов И-НЕ Тггш ГПШ = 2?
(рис. 23); TrlllQ ФИШ = 2т (рис. 23); 7*Г0ЦШ = 2* при / < 8;
TrQ ЦШ = 4т при / = 8 (аналогично рис. 19); Т аЦШ = TgG СШ=
Т0Пс0С1\1=2х (аналогично рис. 19 и 21).
Если т&^М, то функции, обычно получаемые на схемах ГПШ
или ЦШ, можно вырабатывать не из функций Г и Я, которые об-
разуются в тракте переноса II яруса, а непосредственно из величин
а, Ъ и я. Для этого в тракте переноса III яруса вместо схем ГПШ
или ЦШ можно использовать /поразрядные схемы ГП и Ц непо-
средственно по схемам на рис. 15 и 19. При этом исчезает время за-
держки Trrllj, поэтому время задержки всего трехъярусного сум-
матора Tas уменьшится на 2т по сравнению с обычным вариантом.
На рис. 24 показаны в форме, удобной для сравнение составляю-
щие времен задержки наиболее быстродействующих типов СМ.
Для построения трехъярусного СМ, работающего в ОК, "нужно,
как и в случае группы II порядка, в блоке БЗСУМ модифицировать
лишь блок переноса самого старшего, III яруса, превратив его
в БЗПЕРЕОК. Блоки суммы Б2СУМ остаются без изменения. При
использовании ПАР переноса на III ярусе блок БЗПЕРЕПАРОК со-
стоит из / схем ГПШ (при т£<М можно в качестве схем ГПШ
использовать т£-входовые схемы ГП) и / одинаковых схем
ФШПОК. Эти схемы строятся в соответствии с выражением (31)
после замены в нем букв в соответствии с табл. 5. В случае ЦЕП
или СКВ переноса на III ярусе блок БЗПЕРЕОК состоит из / схем
ЦШ или С1Ц (при mk<M вместо ЦШ можно использовать Ц),
а сигнал выходного переноса Gi заводится на вход переноса гвх всей
группы III порядка.
Выражения для подсчета Q трехъярусного СМ ОК можно полу-
чить из выражений (51) — (53), заменив в них коэффициенты (/—1)
на /. Значение времени задержки трехъярусных сумматоров ОК вы-
числяется аналогично времени задержки двухъярусных сумматоров
ОК.
71
Тип
сумматора
Пакси-
нальная
разряд-
ность
время задержки Т
1 2 J 4- 5 6 7 8 9 10 11 1Z 1
Одноразряднь/й
(puc.S)
£ — разрядный
(рис.6)
П(рис.П)
П двухкаскад-
ныи *
ЦП, /77 = 2
ПЦ, /с = 2*
ПП, /г $7
ПП, /г= 8
ЦПП, 1=2
ППП, тН<И
(тц,ш7,м**
ППП, тк>М,
т^77 /с$ 7
8
JZ
15
16
56
6±
98
' 56
11Z
J9Z
as
ГР
rS
rS
1 1 1 1
Ступень И-ИЛИ
(И-НЕ - И-НЕ )■
аР
гр
ах
i—i
ах
ХР
rs
ХР
аХ
I—1
ах
1—1
ах
1—1
а?
ХЕ
еР
r>s
хп
ПЕ
лг
хп
ПЕ
еР
rS
уп
ПЕ
еР
rS
ах
.аХ
Н—1
а%
хп
П6
gi
еР
rS
X
пш
ПШ
о
ПЕ
еР
rS
хп
ПП
ш
ПШ
а
ПЕ
es
ах
хп
ППл
ш
пшо
ОЕ
ер
PS
|
!
Рис. 24. Число логических ступеней некоторых быстрых типов СМ
(TrS принято равным 2т, как на рис. 12. * — ступени И-ИЛИ по-
строены в два каскада согласно выражениям (20); ** — Б1СУМЦЕН
по схеме на рис. 6).
13. СРАВНИТЕЛЬНЫЙ ОБЗОР КЛАССОВ
СУММАТОРОВ
Система классификации СМ, основанная на выделении характер-
ных типов переноса, которые можно по-разному комбинировать на
различных ярусах, позволяет очень компактно и просто описать все
удачные типы СМ с групповым переносом, рассмотренные в распро-
страненной технической литературе под различными специальными
названиями. Так, «сверхпараллельный СМ» [9]. по классификации
этой книги представляет класс ЦЦЦ с различной длиной групп; «па-
раллельно-параллельный СМ» [9], он же «СМ с одновременным пе-
реносом» [3], у нас обозначается как класс П, «сокращенный ва-
риант сверхпараллельного СМ» [9] относится к классу ССС; «СМ
с параллельным переносом» по [3], он же «СМ с обходными цепями»
по [8]-и [И], в данной книге обозначается как класс СС. Принятая
классификация по духу ближе всего классификации, используемой
в [13] и [7], но в [13] не предусмотрено существование ПЦ и ЦЦ
сумматоров, а в [7] — схем ЦП и ЦЦ классов, а также трехъярус-
ных СМ. Сумматор ЦЦ класса в [11] назван просто «СМ с форми-
рованием сигналов группового переноса». Такое обилие не согласую-
щихся друг с другом названий и побудило автора предложить спо-
соб наименования, использующий всего три термина — ПАР, ЦЕП и
СКВ — и позволяющий компактно назвать большое число классов
СМ.
72
Система классификации дает вбзможность начать систематиза*
Цию сведений о свойствах различных классов СМ. Программа авто-
матического синтеза [5] порождала СМ следующих классов: П, Ц,
ПП, ПЦ, ЦП, ЦЦ, СС, ППП, ППЦ, ПЦП, ПЦЦ, ЦПП, ЦПЦ, ЦЦЦ,
ССС. Другие классы или нереализуемы в рамках данной классифи-
кации, или, по мнению автора
этой книги, неконкурентоспособ-
ны с перечисленными. Приведем
некоторые результаты анализа и
программных экспериментов по
автоматическому синтезу сумма-
торов.
На рис. 25 показано усред-
ненное и несколько идеализиро-
ванное взаимное расположение
различных классов двухъярусных
СМ на плоскости TQ при средних
значениях разрядности — близких
к 32. Хотя зоны различных клас-
сов СМ взаимно перекрываются,
но среди множества двухъярус-
ных СМ наблюдается тенденция
к некоторому общему порядку, а
в группу СМ, оптимальных по Па-
рето, обычно попадают предста-
Рис. 25. Приблизительное вза-
имное расположение различных
классов двухъярусных СМ при
средней разрядности. Стрелка-
ми показана тенденция смеще-
ния точек при увеличении к.
вители всех классов. При увели-
чении разрядности между обла-
стями классов двухъярусных СМ
появляются разрывы. При умень-
шении разрядности времена ми-
нимальных задержек практиче-
ски не изменяются, а максимальных заметно уменьшаются, в ре-
зультате чего классы СМ, расположенные справа, начинают «напол-
зать» на левые. При /г<20 какое-либо подобие порядка среди двухъ-
ярусных СМ исчезает совершенно, и даже человеку, не говоря уже
о программе, приходится перебирать много вариантов, прежде чем
удастся найти наиболее дешевую схему при заданном ограничении
по времени.
Трехъярусных СМ значительно больше, чем двухъярусных, и об-
ласти их всегда перекрываются. На рис". 26 в качестве примера по-
казано расположение областей, Занимаемых СМ некоторых классов
при /г=32 на плоскости TQ. Каждая область включает СМ одного
класса по переносу при различных разбиениях разрядности /2=32 на
числа /, т, к: На рис. 27 изображены группы СМ, оптимальных по
Парето, для нескольких значений разрядности п. Чтобы оттенить
влияние именно типов переноса и по возможности исключить воздей-
ствие других факторов, на рис. 26 и 27 показаны результаты автома-
тического синтеза СМ лишь с целыми значениями /, т, к (произве-
дение Imk в точности равно п) и лишь с одним видом схемы каждого
фрагмента только на элементах И-НЕ. Поэтому данные, приведен-
ные на рисунках не претендуют на демонстрацию наилучших вариан-
тов, которые можно построить из приведенных в книге базовых фраг-
ментов. Их цель — продемонстрировать некоторые общие моменты.
В расположении областей трехъярусных СМ трудно выявить до-
статочно простые и удобные для практического использования зако-
номерности. На рис. 26 показаны лишь характерные представители
6—1119 73
Рис. 26. Расположение зон некоторых классов СМ при п=32 (точка-
ми показаны схемы, принадлежащие группе Парето по рис. 27).
классов двух- и трехъярусных СМ, но добавление недостающих клас-
сов ничего не проясняет, а лишь увеличивает впечатление хаоса.
В область оптимума по Парето различные зоны заходят довольно
беспорядочно. При росте п конфигурация областей меняется, в Мно-
жестве СМ, оптимальных по Парето, увеличивается удельный вес
трехъярусных. Это легко заметить, сравнивая на рис. 27 названия
классов СМ, оптимальных по Парето, при разных значениях п.
Области несколько сдвигаются также и при смене или расширении
списка базовых фрагментов, когда принимаются во внимание запре-
ты заказчика. В столь запутанном пространстве оказываются мало-
эффективными даже мощные человеческие методы поиска, основан-
ные на ассоциациях, формировании обраэов и т. п. Это видно хотя
бы из того, что за 30 лет интенсивного изучения сумматоров поле
трехъярусных СМ осталось практически неисследованным. Из всех
классов этих СМ в литературе чаще всего отмечается возможность
построения лишь класса ППП (например, [6, 9]), хотя, как следует
из экспериментов с программой синтеза (что видно и на рис. 27),
этот класс почти никогда не попадает в область оптимума по Паре-
то. Трудно согласиться с мнением, бытующим среди разработчиков
и высказанным в [7], стр. 327: «...априори можно утверждать о це-
лесообразности использования структур, имеющих однотипные вне-
групповые и внутригрупповые цепи переносов». Из рис. 27 видно,
что большинство схем, оптимальных по Парето, имеет на разных
ярусах как раз разнотипные цепи переносов.
Из-за большой нерегулярности пространства решений начать его
систематическое исследование удалось, лишь применив метод пол-
ного перебора с помощью ЭВМ. Именно программы автоматическо-
го, синтеза позволили обнаружить среди трехъярусных СМ средней
и особенно большой разрядности такие схемы, которые лишь на
(1—3)т медленнее широко распространенных в современных ЭВМ
сумматоров ПП класса, но на 20—30% дешевле их, а.при я=64
почти не уступают ив скорости, поскольку в этом случае из-за k=S
в ПП сумматоре возникают дополнительные задержки.
Поиск наиболее быстрых СМ облегчается таблицей на рис. 24.
Как видно из рисунка, каждому диапазону разрядности соответст-
вуют, как правило, лишь один —два класса СМ, обеспечивающих
минимальное время задержки, т. е. объем перебора при поиске са-
мых быстрых "схем невелик. При я>64 в большом диапазоне раз-
рядности некоторые СМ ЦПП и ППЦ классов оказываются быстрее
применяемых в больших машинах СМ ППП класса. В области
двухъярусных интересен ПЦ СМ для п=-Л6 с 6=2, имеющий время
сложения всего 8т иЦП СМ с п=15 и задержкой 7т. Не исключе-
но, что подобные находки удастся обнаружить и среди других функ-
циональных узлов, если поработать с программами их автоматиче-
ского синтеза, основанными на полном переборе вариантов.
Рис. 27. Сумматоры ДК, оптимальные по Парето (цифрами обозна-
чен числовой параметр Imk [для двухъярусных СМ — mk, одноярус-
ных — k]. Крестиками обозначен СМ с перемежающимся перено-
сом).
6* 75
14. МОРФОЛОГИЧЕСКИЙ ЯЩИК СУММАТОРОВ
а) ЧИСЛОВОЙ ПАРАМЕТР
Кроме способов распространения переноса на различных яру-
сах СМ характеризуется также числовыми показателями: / — число
групп II порядка в составе СМ; га— число групп I порядка в группе
II порядка; к— число разрядов в группе I порядка. В частном слу-
чае lmk—п, однако возможны разбиения, когда п не распадается на
одинаковые группы. Тогда последние группы будут неполными, по-
этому кроме чисел I, га, k СМ характеризуется еще га' — числом
групп I порядка в последней, неполной группе II порядка и к'—
числом разрядов в последней, неполной группе I порядка. При пол-
ных группах га', к' равны 0. Возможны и более сложные варианты
разбиения, в том числе и с неодинаковым числом разрядов в каж-
дой группе, которые здесь не рассматриваются.
Числовые параметры генерируются специальным модулем про-
граммы синтеза на основе заданной заказчиком разрядности. Прин-
цип генерации весьма прост. Программа начинает с одноярусного
СМ, т. ё. со значений /=1,.га=1, k=n. Затем она выполняет серию
делений п на га=2, га=3 ..., вплоть до получения &=2, определяя
тем самым серию значений к и к'. После этого / увеличивается на
1 й описанная серия делений повторяется снова до тех пор, пока
не будет порожден список всех возможных разбиений. Приведем
пример списка разбиений для п=\0, поясняющий процедуру гене-
рации:
/ т к тг к' I т к т' к' *■* / га к т 'к'
1 1 10 0 0
12 5 0 0
1 3 4 0 2 +|
1 4 3 0 1
1 5 2 0 0
>2 2 3 0 1
2 3 2 2 0
+ >3 2 2 10
1 1
Конец
Кроме того, выполняются необходимые проверки, не допускаю-
щие порождения запрещенных комбинаций, включающих, например,
к>8 при га^=1 и определяются стыковочные характеристики для
каждого варианта разбиения, такие как k=8, к ближайшее
к V п, которые являются условиями при выборе типа переноса,
вида схемы, расчетной формулы и т. п.
Конкретный набор чисел /, га, k, га', к' представляет собой
первый числовой параметр, а не пять различных параметров. Каж-
дое значение набора, например 14301, является одним из значений
числового параметра. Число возможных вариантов разбиения, т. е.
значений числового параметра, при средней разрядности составляет
примерно 50—70 (учитывая разбиения с' неполными группами) и
падает как при уменьшении, так и при увеличении п. Программа
синтеза порождает и оценивает СМ каждого класса для всех воз-
можных разбиений. Более сложная программа, а также человек,
синтезирующий схемы вручную или в интерактивном режиме, мо-
жет для сокращения перебора учитывать приведенные в § 9—11 со-
ображения о свойствах СМ различных классов (эвристики), позво-
ляющие отбросить сразу целый куст вариантов разбиения. К ним
относятся рекомендации использовать в ПП сумматорах лишь зна-
чения ky близкие к минимальным и т. п.
76
б) ПАРАМЕТРЫ СУММАТОРА И ИХ ЗНАЧЕНИЯ
Теперь можно перечислить все параметры и их значения, харак-
теризующие СМ с групповым переносом, т. е. построить морфоло-
гический ящик СМ. Те, кто не интересуется тонкостями структуры
сложных СМ, могут при чтении опустить приведенный ниже список
параметров СМ:
П1. Вид используемого кода:
1. ДК — дополнительный код. 2. ОК — обратный код.
П1 является внешним параметром, т. е. всегда задается заказ-
чиком. Он влияет на вид схем самого старшего тракта переноса.
П2. Числовой параметр Imkm'k'.
Список значений П2 порождается программой по значению за-
данной разрядности п. Числа /, га, к определяют ярусность данного
варианта СМ и сильно влияют на выбор типов переноса и видов
схем на всех ярусах.
ПЗ. Тип переноса на III ярусе:
1. ПАР. 2. ЦЕП. 3. СКВ. 4. О—ярус отсутствует. Значение ПЗ
влияет на выбор типов схем III и II ярусов. При значении О вместо
схем ЦГП и СП используются Ц и С.
П4. Вид схемы на III ярусе:
1. ПАР. Схемы ГПШ и ФШП на рис. 23. 2. ПАР. Схемы ГПШ
аналогичны схеме на рис. 23, а ФШП выполнена на элементах
И-ИЛИ-НЕ.
3. ПАР. Схемы аналогичны схеме на рис. 23, но на входы ГПШ
подаются не функции Г и Я, а величины a, b и я при т&<М. Схе-
мы ГПШ строятся согласно схемам ГП на рис. 15. 4. ПАР. Схемы
ГПШ для т£<М, как в 3, а схема ФШП построена на элементах
И-ИЛИ-НЕ, как в 2. 5—8 — схемы ПАР ОК, аналогичные 1—4, но
модифицированные для ОК. 9. ЦЕП. Схема ЦШ, аналогичная схе-
ме на рис. 19,в. 10. ЦЕП. Схема ЦШ, аналогичная схеме на рис. \9,в,
но на И-ИЛИ-НЕ. 11. СКВ. Схема CIII, аналогичная схеме на
рис. 21,6. 12. СКВ. Схема СШ, как в 11, но тракт переноса на
И-ИЛИ-НЕ. 13. О — схема переноса III яруса отсутствует.
П5. Тип переноса на II ярусе:
1. ПАР. 2. ЦЕП. 3. СКВ. О — ярус отсутствует. П5 влияет на
конкретный вид схемы II яруса.
П6. Вид схемы на II ярусе:
1. ПАР. Схема ГП на рис. 15, Ф2П — на рис. 16. 2. ПАР. Схема
ГП на рис. 15, Ф2П аналогична схеме на рис. 16, но на И-ИЛИ-НЕ.
3. ПАР. Схема II яруса БФ2П для т^4, выпускаемая в одном
корпусе. 4, 5. ПАР ОК. Схема, аналогичная 1 и 2, но модифициро-
ванная для двухъярусного СМ ОК. 6, 7. ЦЕП. Схемы ЦГП и Ц на
рис. 19. 8, 9. ЦЕП. Схемы ЦГП и Ц, аналогичные схемам на рис.
19, но на И-ИЛИ-НЕ. 10, 11. СКВ. Схемы СП и С на рис. 21. 12, 13.
СКВ. Схемы, аналогичные схемам на рис. 21, но с элементами
И-ИЛИ-НЕ. 14. О —схема II яруса отсутствует.
П7. Тип переноса на I ярусе:
1. ПАР. 2. ЦЕП. 3. СКВ. На I ярусе деление переноса на Ц и
С искусственно. Полагаем,4 что тракт переноса типа С приспособ-
лен, может специально вырабатывать вспомогательные функции для
стыковки с С-трактом II яруса.
П8. Вид схемы Б1СУМ на I ярусе:
1. ПАР. Схема типа схем на рис. 11.2. ПАР. Схема типа схемы
на рис. 12. 3. ПАР. Схема типа схемы 12'. 4, 5. ПАР. Схемы типа
схемы на рис. 11 и типа схемы 12х, но использующие выражения
77
(20). 6. ПАР. 4-разрядный СМ, выпускаемый в одном корпусе как
схема средней интеграции. 7—П. ПАР ОК. Схемы, аналогичные
1—5, но модифицированные для одноярусного СМ ОК. 12, 13. ЦЕП.
Схемы на рис. 5 и 6. 14, 15. ЦЕП и СКВ. Схемы на рис. 7 и 8. 16,
17. ЦЕП и СКВ. Схемы на рис. 7 и 8, но без последнего элемента
И-НЕ. 18. Схема на рис. 22. 19—21. ЦЕП и СКВ. Г-, 2- и 4-разряд-
ные СМ, выполненные в одном корпусе. Для использования в мно-
гоярусных СМ к ним нужно добавить элементы, вырабатываюГцие
функции я, а для СКВ — также и у.
Параметры П1—П8 однозначно описывают любой СМ с группо-
вым переносом, который можно составить из фрагментов, упоми-
навшихся в этой книге. Списки значений параметров могут быть со-
кращены или расширены в зависимости от возможностей снабжения,
номеров серий, требований к качеству синтезируемых схем, ограни-
чений на затраты труда по программированию и на машинное вре-
мя. Чтобы процесс синтеза не выходил на запрещенные ветви, зна-
чения параметров нужно снабдить условиями их применимости.
В качестве примера в табл. 6 и 7 приведены значения параметров
П5 и П6 вместе с их условиями применимости. Если содержатель-
ный смысл условий не совсем ясен, вернитесь к разделам, посвящен-
ным двухъярусным СМ.
Таблица 6
Гнездо параметра П5
П5. Имя параметра: Тип переноса на II ярусе
| Значение параметра
Условия применимости
1 No
содержание
на II
ярусе
1
п
III
ярусе
2
ц
III
ярусе
3
с
4
О
(2<т<8) Д(2<&<8) Л(пер<
НЕ С)
(т ^ 2) Д (2 < к < 8) Л (перенос
НЕ С)
(т> 2W\ (2<fc<8) Л (перенос
НЕ (П или Ц)
(/=1)Л> = 1)
Если у нескольких значений параметров выражения условий со-
держат одинаковые конъюнктивные члены, целесообразно поле усло-
вий этого параметра разбить на две части — групповые и частные
условия. В случае СМ это относится к параметрам П4—П6. При-
менение групповых условий проиллюстрируем на примере гнезда П6
(табл. 7). В процессе порождения вариантов на этапе, когда зна-
чения параметров П1—П5 уже выбраны и программа пробует
подставлять различные значения параметра П6, то сначала прове-
ряет групповые условия. Если групповое условие не выполняется,
программа сразу исключает из перебора значения всех параметров
данной группы и переходит к анализу следующего группового
условия. Это сокращает машинное время по сравнению с вариантом,
когда групповые условия не выделяются. Если групповое условие
выполнено, то начинается анализ частных условий всех значений
данной группы. Этот процесс также идет быстрее, поскольку каж-
дое частное условие за счет вынесения общей групповой части ста-
ло короче.
78
Таблица ?
£нездо параметра П6
П6. Имя параметра: Вид схемы на II ярусе
Условия применимости
1
No.
Значение параметра
групповые |
частные
П на
НЕ((ОК)Л(/=1))
1
ГП (рис. 15),
0
II ярусе
Ф2П(рис. 16)
НЕ((ОК) Д(/== 1))
2
ГП (рис. 15), Ф2П на
i
И-ИЛИ-НЕ
(/= 1)Л(Ж4)
3
Б2ФП в одном корпусе
0
(ОК)Л(/=1)
4
Аналогично № 1, но в
0
варианте для ОК
(ОК) Л(' = 1)Л
5
Аналогично № 2, но в
1
Д(/п — четное)
варианте для ОК
Ц на
(/>!)
6
ЦГП (рис. 19)
0
II ярусе
(/=1)
7
Ц (рис. 19)
0
С на
10
СП (рис. 21)
0
II ярусе
•
.
О на
14
Схема отсутствует
0
II ярусе
Примечание. Значения характеристики Х61: О — перенос Е прямой, 1 — пе-
ренос Е инвертирован. Х6\ определяет необходимость инвертирования слагаемых в чет -
ных группах.
Выделение типа переноса в качестве самостоятельного парамет-
ра — это в известной мере дань человеческому способу проектирова-
ния СМ. Возможна и другая структура морфологического ящика,
в которой тип переноса является не самостоятельным параметром,
выбираемым на одном из этапов синтеза, а лишь характеристикой
конкретного типа схемы (например, Xj9 в табл. 2). В этом случае
СМ будет описываться лишь пятью параметрами. Человеку не очень
удобно иметь дело с такой системой параметров, но время работы
программы при этом будет меньше.
Кроме гнезд параметров в состав морфологического ящика вхо-
дит еще гнездо расчетных* формул для определения Т и Q. Формулы
для СМ различных типов приведены в соответствующих параграфах.
Легко заметить, что как и сам СМ, они состоят из фрагментов, при-
чем структура формул полностью соответствует структуре самого
СМ. Применимость всей формулы и каждого ее фрагмента задается
условиями, опирающимися на уже выбранные в процессе порожде-
ния .каждого варианта СМ значения параметров и их характеристи-
79
ки. Таким образом, для каждого варианта СМ его расчетная фор-
мула компонуется самой программой. Аналогичную структуру имеет
гнездо для определения числа инверторов на входах слагаемых и на
выходах суммы в зависимости от вида фрагментов СМ и от ограни-
чений заказчика на вид входного и выходного кода (прямой, ин-
версный, возможен перемежающийся).
Перечисленные выше фрагменты были использованы в програм-
ме автоматического синтеза СМ, написанной и отлаженной
Л. М. Долматовой [5]. Слово, полностью описывающее один вари-
ант СМ вместе со всеми характеристиками на внутреннем языке си-
стемы, имеет длину 270 бит. Программный модуль порождения сум-
маторов-гипотез занимает объем около 2500 машинных команд ЭВМ
М-220, модули вычисления Т и Q в сумме состоят из 6500 команд.
Кроме них в состав программы входят ведущий модуль, информа-
ционный массив и ряд служебных модулей, в том числе модули,
дающие возможность работать с разными сериями микросхем, и
входные и выходные трансляторы, обеспечивающие диалог на языке
заказчика. Время синтеза СМ по любому варианту ТЗ (в том числе
и выделение группы Парето) обычно не превышает 1 ч.
ЗАКЛЮЧЕНИЕ
На примере СМ хорошо иллюстрировать все основные положе-
ния вариантного синтеза, изложенные в § 1—4. Объект проектиро-
вания описывается набором параметров, причем параметры могут
определять или конкретный вид материального фрагмента (вид трак-
та переноса на II ярусе), или числовой показатель (числовой пара-
метр Imkm'k'). На многие сочетания значений параметров СМ нало-
жены запреты (разрядность группы с ПАР переносом не более 8;
при ЦЕП переносе на II ярусе в двухъярусных СМ используется
схема Ц, а в трехъярусном — ЦГП и т. д.). В условия этих запре-
тов входят, как правило, значения не более двух-трех параметров,
и при разработке программы синтеза запись условий в поля мор-
фологического ящика не вызывает осложнений.
Задание на синтез СМ представляет собой анкету-таблицу,
в которой заказчик по установленной форхме фиксирует требуемые
ему данные из предлагаемого набора вариантов. Для целевой
функции проектирования в анкете предусмотрены следующие вари-
анты: минимальное значение Т; минимальное значение Q; Т не бо-
лее заданного заказчиком и при этом минимальное Q; Q не более
заданного заказчиком и при этом минимальное 7; минимальное зна-
чение произведения TQ; минимальное значение функции WiT-{-W2Q,
где W\ и W2 задает заказчик; вывод на печать множества объек-
тов, оптимальных по. Парето в пространстве характеристик Г, Q;
вывод на печать всего множества порожденных объектов (отладоч-
ный режим). В любом варианте целевой функции заказчик имеет
возможность запретить выдачу конкретной группы объектов, поиме-
нованных в специальном списке. Если в такой список внести груп-
пу Парето предыдущего сеанса работы с программой, то в очеред-
ном сеансе будет получена группа объектов «второго сорта» и т. д.
Это позволяет квалифицированному заказчику, не останавливаясь
вслепую на одном хорошем объекте, детально обследовать всю
область удачных решений, на которую 'вышла программа.
Раздел анкеты заказчика, в котором задаются характеристики
проектируемого объекта, состоит из двух частей: обязательной и
80
необязательной. На все вопросы первой части заказчик должен
ответить полностью. В программе синтеза СМ сюда входят той
пункта: разрядность (1—64), модуль суммирования (ДК или ОК)
и серия элементов заказчику предлагается список из нескольких
распространенных серий; этот список администратор программы мо-
жет менять в прцессе ее эксплуатации). Обязательная часть харак-
теризует необходимый минимум априорных сведений, которые заказ-
чик должен иметь о будущем объекте.
В необязательную часть анкеты заказчика входят значения всех
остальных параметров, приведенных в § 14,6, т. е. все компоненты,
которые участвуют в комбинаторном порождении вариантов СМ.
В этой части заказчик может обращать внимание лишь на те пара-
метры, которые считает для себя существенными, и диктовать про-
грамме свою волю, вычеркивая нежелательные значения этих пара-
метров. В процессе трансляции ТЗ (анкеты заказчика) эти
исключенные значения параметров не будут внесены в рабочий
дубль морфологического ящика и соответственно не будут участво-
вать в порождении вариантов объекта.
Заказчик может также вычеркнуть в анкете те значения пара-
метров, которые, по его мнению, не войдут в хорошие решения
поставленной им задачи. Например, можно запретить использование
третьего яруса переноса, если требуется синтезировать схему с ми-
нимально возможным временем задержки. В данном случае вычер-
кивание является опособом введения в систему эвристик, сокращаю-
щих объем перебора, т. е. удегцевляющих процесс синтеза схемы.
Однако заказчик может не иметь столь высокой квалификации
в области СМг Более того, он может даже не знать, что обозна-
чают многие параметры списка § 14,6, и вообще не отвечать ни
на один из пунктов необязательной части анкеты. В этом случае
недостающую информацию программа восполнит самл, методически
исследуя пространство значений параметров, и все равно выберет
наилучшее из возможных решений, но- времени на это затратит
больше. Дополнительное машинное время является платой за низ-
кую квалификацию заказчика.
В конце сеанса программа выдает на печать объект (или список
объектов), наилучший в смысле заданной заказчиком * целевой
функции. Каждый объект в выходном списке представлен в виде
строки, в которой перечисляются значения всех параметров и
внешних характеристик, например тип переноса на II ярусе: ПАР;
Вид схемы тракта переноса II яруса1; m = 6; k — \\ 7 = 220 не:
Q—76 корпусов серии К155;
Задача автоматического вычерчивания схемы из выбранных
стандартных фрагментов при разработке данной программы не ста-
вилась. В принципе эта задача аналогична задачам компоновки
и трассировки, возникающим при техническом проектировании ТЭЗ.
Основной целью работы была автоматизация поиска объекта с за-
данными характеристиками в пространстве дискретных параметров.
По данным проведенных программных экспериментов число реально
осуществимых вариантов СМ заданной разрядности обычно состав-
ляет несколько тысяч. Даже простое перечисление возможных ком-
бинаций и прослеживание в уме последствий, к которым приведут
через 3—4 яруса определенные сочетания запретов, оказывается для
человека очень сложной задачей: из жизненного опыта известно,
что число ошибочных поступков и необнаруженных хороших ходов
всегда намного превышает желаемый уровень. Тем более сложной
61
оказывается задача за разумное время оценить и сравнить эти
варианты по нескольким внешним характеристикам. Это все — чисто
машинные задачи, и ЭВМ среднего класса справляется с Ними
примерно за час. Сократить перебор можно, введя в программу
эвристики, выявленные специалистами в результате'изучения поля
характеристик СМ. Часть этих эвристик приведена в § 9—11.
При необходимости существенно сократить перебор можно вве-
сти многоэтапное проектирование. Применительно к СМ можно сна-
чала синтезировать все двухъярусные блоки суммы Б2СУМ, затем
для каждого значения их разрядности (произведения mk) выделить
группу Парето и на втором этапе при синтезе трехъярусных СМ
использовать только эти перспективные варианты Б2СУМ.
При близком знакомстве с СМ становится ясно, почему практи-
чески невозможно использовать для сокращения перебора традици-
онные математические методы, хорошо работающие в других обла-
стях, такие как линейцое или квадратичное программирование, по-
следовательное конструирование и т. д. Большинство этих методов
в явной или неявной форме требует взаимной независимости влия-
ния параметров на внешние характеристики (линейная модель) или
хотя бы упорядочения значений параметров по их влиянию на эти
характеристики. В случае функциональных схем, в частности СМ,
пространство существенно нелинейно, влияние параметров взаимно
зависимо и упорядочить их невозможно. Так, упорядочение схем на
рис. 6 и И по Tes или схем на рис. 8 и 12 по Q зависит от k; упо-
рядочение по Т принципов ПАР и ЦЕП переноса на II ярусе зави-
сит от т: ЦП СМ быстрее, чем ПП при т=2 и медленнее при
т=4; кроме того, это упорядочение зависит и от общей разрядно-
сти СМ, и от вида Б1СУМ, и от того, построены схемы Ф2П и Ф2Ц
на элементах И-НЕ или И-ИЛИ-НЕ, и т. д. Результат взаимной за-
висимости параметров хорошо виден на рис. 26.
Методом синтеза логических схем, способным работать в столь
сложных пространствах и совершенно не требовательным ни к виду
зависимости внешних характеристик от внутренних параметров, ни
к характеру формулирования целевой функции заказчика, ни к пол-
ноте априорного исследования свойств пространства параметров
и при этом обеспечивающим наибольшую простоту внесения изме-
нений, является метод полного перебора. Автор понимает, что пол-.
ный перебор применим далеко не везде, что существует множество
задач, где число вариантов непомерно велико. Однако разработчики
необоснованно запуганы призраком неосуществимых переборов, и
часто боятся даже сделать попытку использовать этот простой и
надежный метод. При условии разумного выбора числа этапов
синтеза этот метод во многих практических задачах технического
проектирования не требует слишком много машинного времени.
Проведенные программные эксперименты показали, что автома-
тическому синтезу вариантным методом успешно поддаются не толь-
ко схемы СМ, но и схемы счетчиков, быстрых многоярусных сдви-
гателей и узлов редактирования, узлов поиска левой единицы в* сло-
ве, дешифраторов и других функциональных узлов. Наибольшее
число экспериментов с программами синтеза было выполнено в ба-
зисах микросхем распространенных ТТЛ серий. Это позволило,
сравнивая продукцию программ с реально используемыми схемами,
т. е. с результатами труда квалифицированных разработчиков и
целых коллективов, постепенно совершенствовать структуру морфо-
логического ящика, методику его заполнения и обработки. Описав;-
ный метод можно применять для синтеза схем, построенных и rtf
более совершенной технологии, например для логических схем, со-
здаваемых непосредственно на кристалле. Роль типов корпусов
здесь будут играть различные маски логических элементов и кана-
лы для прокладки трасс связей; оценки аппаратных затрат нужно
вести в единицах площади кристалла. Изменятся некоторые . виды
схем, запреты на сочетания параметров, но грамматическая струк-
тура схем, а также структура морфологического ящика и способ
его программной обработки останутся в основном без изменений.
Изложенная методика вариантного синтеза использовалась автором
при разработке программ автоматического синтеза логических бло-
ков на элементах однородной вычислительной среды. В этой области
в силу ее новизны пространство решений изучено еще очень слабо,
опыт проектирования мал и схемы, полученные программой вари-
антного синтеза, в среднем оказываются лучше по качеству, чем- те,
которые проектировались инженерами, не говоря уже о скорости
их синтеза.
Итак, метод вариантного синтеза применим к проектированию
очень широкого класса объектов, которые описываются в основном
атрибутивными, а не числовыми параметрами. Наибольший эффект
будет получен, если объект проектирования удовлетворяет следую-
щим условиям:
1. Объект в достаточной степени формализован: уже суще-
ствуют установившиеся, четко очерченные фрагменты и не допу-
скающие произвольного толкования правила их взаимного соедине-
ния. В этом случае не потребуется большой предварительной рабо-
ты по отбору, формализации и классификации компонентов грамма-
тики. Те программы синтеза, у которых грамматики объекта по-
строены из слабо формализованных компонентов, работают заметно
хуже инженера, поскольку порождают намного меньше вариантов,
чем их может придумать специалист. Заметим, что работа по клас-
сификации и формализации компонентов'объекта оказывается, как
правило, еще и очень интересной.
2. Требуется построить много различных модификаций одного
и того же объекта. Разработка и программирование грамматики
объекта весьма трудоемки, и работа окупится тем быстрее, чем
больше объектов спроектировано. Уникальные объекты дешевле
синтезировать «вручную».
3. Объект должен быть достаточно сложным. Если число вари-
антов недостаточно велико (десятки или малое число сотен), то
инженер на освоение проектирования такого объекта затратит вре-
мени меньше на построение достаточно хорошей программы авто-
матического синтеза. Видимо, настало время для разработки стан-
дартных пакетов ^прикладных программ инвариантной части систе-
мы автоматического синтеза: программ загрузки и редактирования
гнезд морфологического ящика, программ проверки стандартного
набора условий стыковки, программ комбинирования фрагментов—
как путем полного перебора, так и стохастически, с задаваемыми
извне* вероятностями выбораг и т.'п. Подобные пакеты программ
могу оказаться очень удобным инструментом для быстрого построе-
ния систем автоматического синтеза в очень многих областях про-
ектирования.
83
СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ
ОП — объект проектирования;
БОПЕРЕ — одноразрядный блок переноса;
БОСУМ — одноразрядный блок суммы;
Б1ПЕРЕ — блок выработки переносов I яруса. Может быть па-
раллельным— Б1ПЕРЕПАР и последовательным — Б1ПЕРЕПОС;
Б1СУМ — одноярусный ^-разрядный блок суммы. В зависимости
от типа Б1ПЕРЕ и возможностей стыковки с другими схемами раз-
личают параллельный тип блока — Б1СУМПАР и два последова-
тельных: цепной—Б1СУМЦЕП и сквозной — Б1СУМСКВ;
Б2ПЕРЕ (БЗПЕРЕ) — блок выработки переносов Н(Ш) яруса.
Может быть ПАР типа — Б2ПЕРЕПАР (БЗПЕРЕПАР), ЦЕП типа—
Б2ПЕРЕЦЕП (БЗПЕРЕЦЕП) и СКВ типа — Б2ПЕРЕСКВ
(БЗПЕРЕСКВ);
Б2СУМ (БЗСУМ)—двухъярусный (трехъярусный) т/г-разряд-
ный (/т/г-разрядный) блок суммы. В зависимости от типа Б2ПЕРЕ
(БЗПЕРЕ) различают Б2СУМПАР, Б2СУМЦЕП и Б2СУМСКВ
(БЗСУМПАР, БЗСУМЦЕП и БЗСУМСКВ);
Б2СУМПАРОК — двухъярусный блок.суммы с ПАР переносом
обратного кода (складывающий по модулю 2П—1); /
у, (Г) — функция генерации переноса одного разряда (одной
группы);
п(П) — функция прозрачности одного разряда (одной группы);
Ф2 — фрагмент блока Б2ПЕРЕ, обслуживающий один блок
Б1СУМ. В зависимости от типа переноса II яруса (П, Ц или С) Ф2
может быть Ф2П, Ф2Ц или Ф2С;
Б2ФП — часть Б2ПЕРЕПАР, состоящая из фрагментов Ф2П;
ГП — схема «генерация — прозрачность», т схем ГП и блок
фрагментов Б2ФП образуют Б2ПЕРЕПАР;
Ц И ЦГП — типы фрагментов Ф2Ц;
С и СП — типы фрагментов Ф2С.
СПИСОК ЛИТЕРАТУРЫ
1. Борще в В. Б., Шрейдер Ю. А. Неалгоритмический язык про-
граммирования. Сер. Научно-техническая информация. — М.:
ВИНИТИ, 1964, № 12, с. 17—21.
2. Вопросы анЗлиза и процедуры принятия решений: Пер.
с англ./ Под ред. И. Ф. Шахнова. — М.: Мир, 1976. — 228 с.
3. Гаврилов Ю. В., Пучко А. Н. Арифметические устройства
быстродействующих ЭЦВМ. — М.: Советское радио, 1970. — 280 с.
4. Грис Д. Конструирование компиляторов для цифровых вы-
числительных машин.— М.: Мир, 1975. — 544 с.
5. Долматова Л. М. Вариантный метод автоматического син-
теза функциональных схем типовых операционных узлов ЭВМ:
Автореф. дис. на соиск. учен, степени канд. техн. наук. — М.: МЭИ,
1977.
6. Дроздов. Е. А. Анализ и синтез комбинационных устройств
с цепями групповых переносов. — Цифровая вычислительная техни-
ка и программирование, 1970, вып. 6, с. 136—149.
7. Дроздов Е. А. Оптимизация структур цифровых автоматов.—
М.: Советское радио, 1975. — 352 с.
8. Каган Б. М., Каневский М. М. Цифровые вычислительные ма-
шины и системы. Изд. 2. — М.: Энергия, 1974.— 680 с.
9. Карцев М. А. Арифметика цифровых машин. — М.: Наука,
1969. — 576 с.
10. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программи-
рование. — М.: Наука, 1969. —368 с.
И. Майоров С. А., Новиков Г. И. Принципы организации циф-
ровых машин. — Л.: Машиностроение, 1974. — 432 с.
12. Методы поиска новых технических решений/ Под ред.
А. И. Половинкина. — Йошкар-Ола: Марийское книжное изд-во,
1976. — 192 с.
13. Папернов А. А. Логические основы цифровой вычислитель-
ной техники. Изд. 3. — М.: Советское радио, 1972. — 572 с.
14. Поспелов Д. А. Арифметические основы вычислительных ма-
шин дискретного действия. — М.: Высшая школа, 1970. — 308 с.
15. Потемкин И. С. Сумматоры. — М.: МЭИ, 1975.— 66 с.
16. Потемкин И. С. Функциональные узлы на потенциальных
элементах. — М.: Энергия, 1976.— 104 с.
17. Селлерс Ф. Методы обнаружения ошибок в работе ЭЦВМ:
Пер. с англ./ Под ред. В. К. Левина. — М.: Мир, 1972. — 310 с.
18. Справочник по полупроводниковым диодам, транзисторам
и интегральным схемам/ Под ред. Н. Н. Горюнова. Изд. 4. — М.:
Энергия, 1976. — 744 с.
19. Каталог арифметических устройств ЦВМ/ А. Г. Шигин,
И. С. Потемкин, Г. Л. Кемельмахер, Н. К. Иванова. — В кн.: Ма-
териалы конференции молодых ученых и специалистов по пробле-
мам кибернетики — Л.: ЛД НТО, 1971, с. 37—38.
20. Шигин А. Г., Кемельмахер Г. Л. Информационно-логиче-
ская система проектирования операционных частей ЦВМ. Управ-
ляющие системы и машины, 1973, № 1, с. 52—58.
85
ОГЛАВЛЕНИЕ
Предисловие 3
Глава первая. Вариантный синтез 5
1. Принцип вариантного синтеза ....... 5
а) Алгоритмы и исчисления , 5
б) Комбинаторное порождение вариантов .... 8
в) Морфологический ящик 9
2. Процедура автоматического синтеза 12
а) Программная генерация вариантов . 0 12
б) Запрещенные аетви . 13
в) Ограничения заказчика 16
г) Синтаксис и семантика синтеза 18
д) О качестве порождаемых объектов 19
3. Оптимальность при нескольких критериях .... 20
а) Целевые функции заказчика 20
б) Оптимальность по Парето 20
4. Методы сокращения перебора 24
а) Влияние запрещенных ветвей 24
б) Сокращение перебора и априорные сведения . . 24
в) Особые свойства пространства параметров ... 25
г) Эвристики 25
д) Текущие оценки 26
в) Случайный поиск 27
ж) Структурирование объекта 28
Глава вторая. Автоматизация построения сумматоров . 30
5. Характеристики сумматора и его структура ... 30
а) Внешние характеристики сумматора ...... 30
б) Структурное деление сумматора ...... 33
6. Одноярусные сумматоры с последовательным переносом 34
а) Одноразрядный сумматор 34
б) Сумматор на элементах И-ИЛИ-НЕ ..... 36
в) Сумматор, использующий сложение по модулю 2 . 37
г) Сумматор, использующий только элементы И-НЕ . 38
д) Сумматор с двухколейным переносом .... 39
е) Гнездо сумматоров с последовательным переносом 40
7. Одноярусные сумматоры с параллельным переносом . 42
а) Функции генерации и прозрачности 42
б) Блок параллельного переноса 43
в) Учет нагрузочной способности 46
г) Характеристики сумматора с параллельным пере-
носом 47
д) Формирование выходного переноса 48
е) Параллельный сумматор обратного кода . . 48
86
8. Двухъярусные сумматоры 49
9. Параллельный перенос на II ярусе 51
а) Параллельный групповой перенос 51
б) Инверсный групповой перенос 54
в) Вычисление характеристик 55
г) Выходной перенос двухъярусного сумматора . . 55
д) Двухъярусный сумматор обратного кода ... 56
е) Свойства ПП и ПЦ сумматоров 56
10. Цепной перенос на II ярусе .58
а) Блок цепного переноса 58
б) Переменная длина групп 62
в) Свойства ЦП и ЦЦ сумматоров 62
11. Сквозной перенос на II ярусе 63
а) Организация сквозного переноса 63
б) Сумматор с перемежающимся переносом ... 66
12. Трехъярусные сумматоры -69
13. Сравнительный обзор классов сумматоров .... 72
14. Морфологический ящик сумматоров 76
а) Числовой параметр 76
б) Параметры сумматора и их значения .... 77
Заключение 80
Список основных сокращений 81
Список литературы 85
Игорь Семенович Потемкин
АВТОМАТИЗАЦИЯ СИНТЕЗА ФУНКЦИОНАЛЬНЫХ СХЕМ
(на примере сумматоров с групповым переносом)
Редактор Ю. Н. К о л о т о в
Редактор издательства Л. Д. Никулина
Технический редактор А. С. Давыдова
Корректор Г. Г. Желтова
ИБ № 1603 («Энергия»)
Сдано в набор 27.03.81 Подписано в печать 03.07.81 Т-20077
Формат 84X108V32 Бумага типографская № 3 Гарн. шрифта литературная
Печать высокая Усл. печ. л. 4,62 Уч.-изд. л. 6,35
Тираж 5000 экз. Заказ 1119 Цена 30 к.
Энергоиздат, 113114, Москва, М-114, Шлюзовая наб., 10
Московская типография № 10 Союзполиграфпрома при Государствен-,
ном комитете СССР по делам издательств, полиграфии и книжной
торговли. 113114, Москва, M-U4, Шлюзовая наб., 1Q