Устройство для решения задачи размещения Советский патент 1996 года по МПК G06F17/00 G06F17/50 

fS

00 00

с

ТГ

Изобретение относится к вычислительной технике и может быть использовано для автоматизированного построения радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является повышение быстродействия. Устройство содержит генератор тактовых импульсов, регистры сдвига, коммутаторы, блок памяти топологии графа, узел коммутации, группы элементов ИЛИ, группы триггеров, группы элементов И, шифратор, схемы сравнения, буферные регистры, элементы И, триггеры, элементы задержки, элемент НЕ, элементы ИЛИ, блок сложения-вычитания, группы регистров, группы дифференцирующих элементов, блок формирования перестановок, элемент ЗАПРЕТ, вычислитель, сумматор, блок индикации. 5 ил. СО С н- ON {х Is) 00 Оо Is)

р

ел

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

Целью изобретения является повышение быстродействия.

На фиг. 1-3 приведена структурная схема устройства; на фиг.4 - пример построения коммутатора; на фиг.5 - обобщенная структурная схема.

Устройство содержит генератор 1 тактовых импульсов (ГТИ), регистр 2 сдвига, коммутатор 3, блок 4 памяти топологии графа, регистр 5 сдвига, узел 6 коммутации, группу 7 элементов ИЛИ, группу 8 триггеров, груп- пуЭэлементов ИЛИ, группу ЮэлементовИ, группу 11 триггеров, группу 12 элементов И, группу 13 триггеров, группу 14 элементов ИЛИ, группу 15 элементов И, коммутатор 16, шифратор 17, схему 18 сравнения, буферный регистр 19, группу 20 элементов И, буферный регистр 21, регистр 22 сдвига, коммутатор 23, элемент И 24, регистр 25 сдвига, группу 26 элементов И, триггер 27, элемент 28 задержки, элемент НЕ 29, элемент 30 задержки, элемент ИЛИ 31, группу 32 элементов И, элемент ИЛИ 33, блок 34 сложения-вычитания, элемент И 35, схему 36 сравнения, буферный регистр 37, группу 38 регистров, группу 39 регистров, регистр 40 сдвига, регистр 41 сдвига, группу 42 элементов W. группу 43 дифференцирующих элементов, элемент ИЛИ 44, элемент 45 задержки, элемент ИЛИ 46, элемент 47 задержки, группу 48 элементов ИЛИ, элемент ИЛИ 49, регистр 50 сдвига, триггер 51, элемент И 52, группу 53 элементов И, элементы И 54,55, элемент 56 задержки, элемент ИЛИ 57, блок 58 формирования перестановок, элемент И 59, элемент И 60, элемент ЗАПРЕТ 61, группу 62 регистров, коммутатор 63, вычитатель 64, сумматор 65, группу 66 элементов И, группу 67 элементов ИЛИ, элемент ИЛИ 68, элемент 69 задержки, триггер 70, группу 71 элементов И, элемент И 72, элемент 73 задержки, элемент И 74, элемент ИЛИ 75, элемент ИЛИ 76, буферный регистр 77, схему 78 сравнения, группу 79 регистров, группу 80 элементов И, группу 81 элементов ИЛИ, блок 82 индикации, регистр 83 сдвига, связи 84-88, вход 89 установки исходного состояния устройства, связи 90- 109, элемент ИЛИ 110, группу 111 элементов И, элемент ИЛИ 112, группу 113 элементов И, группу 114 дифференцирующих элементов.

На фиг.5 показаны блок 115 синхронизации (БС), блок 116 коммутации (БК), блок 117 запоминания матрицы смежности

(ВЗМС), блок 118 выбора наилучшего варианта (БВНВ), блок 119 блокировки вершин (Б Б В), блок 120 регистрации (БР), блок 121 перестановок (БП), блок 122 вычисления

критерия размещения (БВКР).

В состав блока 115 синхронизации входят регистр 2 сдвига, ГТИ 1, регистр 22 сдвига, элементы ИЛИ 49 и 75, элементы И 52, 59, 74, 60.

О В блок 116 коммутации входят коммутаторы 3, 16 и 23, каждый из которых состоит из двух групп элементов И 15, 71, буферный регистр 21, узел 6 коммутации, регистр 5,25, 50. элементы И 24, 55, 35, группы 26, 12, 53,

5 ю и 32 элементов И, группы 7, 9, 14, 48 элементов ИЛИ, группы 8,11 триггеров, элементы 30, 47, 56 задержки, элементы ИЛИ 31,33, 46, триггер 51.

В блок 119 блокировки вершин входят

0 регистры 40,41 сдвига, группа 42 элементов И, группа 13 триггеров, группа 43 дифференцирующих элементов, элементы 28, 45 задержки, элемент НЕ 29, триггер 27, элементы И 54, ИЛИ 44.

5 в блок 118 выбора наилучшего варианта входят шифратор 17, схемы 18, 36 сравнения, буферные регистры 19, 37, группа 20 элементов И, блок 34 сложения-вычитания. В блок 120 регистрации входят группы

0 38,39,79 регистров, регистр сдвига 83, группа 67 элементов ИЛИ, блок 82 индикации.

В блок 122 вычисления критерия размещения входят элементы ИЛИ 57, 68,76,110, 112, элементы И 60. 72, элементы 69, 73

5 задержки, триггер 70, группа 62 регистров, коммутатор 63, вычитатель 64, сумматор 65, буферный регистр 77, схема 78 сравнения, группы 66, 80, 111, 113 элементов И, группа 81 элементов ИЛИ, группа 114 дифференци0 рующих элементов.

Позициями 123-130 обозначены связи.

Каждому входу блока памяти топологии

графа поставлена в соответствие вершина

графа, а каждому выходу - ребро между

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

0 ребрам, соединяющих вершины, на которые были поданы единичные сигналы. Это позволяет в каждом такте работы устройства осуществлять выбор той вершины графа, которая имеет наибольшее (наименьшее) чис5 ло связей с множеством вершин, выбранных D предыдущем такте. Кроме того, в исходном состоянии с помощью узла коммутации выбирается некоторое число вершин, равное заданному числу подграфов, каждая из которых является базовой в соответствующем подграфе и к которой в процессе работы устройства будут присоединяться другие вершины графа. Процесс формирования каждого из подграфов графа заканчивается в тот момент, когда в подграф будет включено заданное число вершин, которые должны быть объединены в один подграф. Формирование всех подграфов графа осуществляется последовательно и после окончания процесса исходный граф будет разбит на заданное число подграфов с локально-минимальным числом связей между ними. Полученный результат разбиения графа на подграфы будет записан в регистры. На следующем шаге оптимизации из рассмотрения исключаются те вершины каждого из подграфов, которые были выбраны на первом шаге оптимизации в качестве вершин, имеющих максимальное число связей с базовой вершиной каждого из подграфов. В качестве новой вершины для каждого из подграфов выбирается следующая По максимальной связности с базовой вершиной. Далее процесс формирования подграфов полностью аналогичен описанному выше.

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

- Е

п

Е

С d U pU)p(J)

где Cij - элемент матрицы смежности С, равный 1, если 1-я и j-я вершины смежны, и равен О в противном случае;

o p(i)pO) - элемент матрицы расстояний D, равный числу шагов координатной сетке между позициями Р() и P(J) при i j и dp(i)pO) 0 при I j;

п - число вершин подграфа.

Значение величин С|| матрицы смежности формируются на выходах блока 4 памяти топологии графа аналогично тому, как это делалось при декомпозиции исходного гра- 5 фа. В регистры заносятся двоичные коды позиций: в один регистр записывается двоичный код первой позиции - 100..О, во второй регистр - двоичный код второй позиции -010...О и т.д. Величина dp(|)py определяется 10 с помощью вычитателя как разность двоичных кодов позиций Р()и P(j). Накопление же суммы длин расстояний L осуществляется с помощью коммутатора и сумматора. Перебор всех возможных размещений вершин 15 подграфа в узлах решетки (позициях) осуществляется с помощью блока формирования перестановок (БФП). При этом каждая перестановка соответствует определенному перемещению вершин в узлы координат- 0 ной сетки. Так, перестановке 312 соответствует размещение первой вершины подграфа во второй узел (вторую позицию), второй вершины - и первую позицию. Единичный сигнал в каждый тактовый момент 5 времени появляется только на одном выходе блока. Последовательность же появления единичных сигналов на всех его выходах определяется каждой новой перестановкой. Так, перестановке 312 соответ- 0 ствует появление единичного сигнала по первому тактовому импульсу на втором выходе БФП (нумерация выходов БФП - сверху вниз), по второму тактовому импульсу 1 появляется на третьем выходе БФЛ и по 5 третьему - на первом выходе. Смена перестановок осуществляется подачей сигнала на вход БФП с выхода регистра сдвига, когда закончится анализ смежности каждой вершины подграфа с каждой и произойдет 0 накопление суммарной взвешенной длины связей L при данной перестановке (размещение вершин подграфа в координатной сетке). С помощью регистров сдвига производится распределение импульсов на блок 5 памяти топологии графа и осуществляется последовательный периодический перебор всех вершин подграфа и проверка смежности первой вершины со всеми остальными, второй - со всеми остальными вершинами 0 этого же подграфа и т.д. Синхронно с этим БФП для каждой вершины определяет позицию (узел) в соответствии со сформированной перестановкой. После завершения формирования всех возможных перестано- 5 вок, их обсчета, выбора и запоминания лучшего варианта в регистрах сигналом с выхода БФП осуществляется перевод работы устройства на поиск оптимального размещения оершин следующего подграфа Р позиции (узлы) координатной сетки. Проце /рл осуществляется аналогично описанной янше Таким образом, производится оптимальное размещение вершин каждого из подграфов исходного графа. Результирую- щре размещение графа в координатной сет- представляет собой совокупность слабосвязанных локально-оптимально размещенных вершин подграфов.

Рассмотрим сначала подготовку устройства и его работу по обобщенной структурной схеме, представленной на фиг,5.

Перед началом работы все блоки устройства устанавливаются в исходное состояние. По входу Уст. в блок 117 вводится информация об исходном графе. При подаче сигнала на вход 89 установки исходного состояния блока 116 на все информационные входы блока 117 поступят единичные сигналы блока 116 и на соответствующих информационных выходах блока 117, в зависимости от конкретной топологии графа, появятся единичные сигналы, поступающие через блок 116 на вход 128 блока 118. Эти сигналы преобразуются в код, используемый в дальнейшем для вычитания кода чис- лз внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. В конце решения задачи и IN- f /icr e останется (будет храниться) ход минимального числа связей между под- рт br.im графа На выходе Т (транзит) бло- , а 116 устанавливается единичный сигнал, п исутстзуюший до окончания работы устройства в режиме декомпозиции.

Кахдый тактовый импульс с блока 115 jpp-°j олг 116 поочередно подключает пару Ьормч ;ионных кодов блока 117, т.е. поо- грелчо подает на все пары входов блока - г потенциалы. В соответствии лим нэ информационных выходах блока 117 будет формироваться определенный од подаваемый через вход 128 на блок 118, который выберет и запомнит пару вершин, соответствующих максимальному коду, т.е. перу сильносвязанных вершин. Эта пара аершин включается {заносится) в первый подграф путем перезаписи их номеров через входы 96 из блока 116 в блок 120 по сигналу разрешения из блока 118, поступающему на вход 127 блока 120. Аналогичная шоцедура повторяется до тех пор, пока в подграф не войдет заданное количество вершин, признаком чего является появление единичного сигнала на входе 94 блока 113, по которому произойдет вычитание кода суммарного числа внутренних ребер сформированного подграфа из кода суммарного числа ребер исходного графа.

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

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

формирование по следующих подграфов, пока не будут сформированы все подграфы. Признаком этого является появление единичного сигнала на выходе 92 блока 116. По этому сигналу в блоке 118 запомнится код

0 числа, соответствующий наилучшей декомпозиции графа (минимум суммарного числа связей между подграфами), блоке 120 будут храниться номера вершин, вошедших в каждый из подграфов. Этот же сигнал, по5 ступивший на вход 92 блока 119, обеспечивает выбор новой ветви разбиения для того, чтобы процесс разбиения во втором цикле разбиения не пошел по уже проделанному пути. Для этого из блока 119 поступает еди0 ничный сигнал на вход 97 блока 118, который блокирует вершину, выбранную в предыдущем варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов.

5 В результате такой блокировки получаем новый вариант разбиения графа, который сравнивается с уже имеющимся вариантом (по единичному сигналу на входе 92 блока 118 с выхода 92 блока 116) и запоминаем

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

Единичный сигнал на выходе П блока 116 обеспечивает установку элементов уст0 ройства в исходное состояние, а блок 121 устанавливается в состояние, соответствующее первой перестановке. Очередной тактовый импульс, поступающий с блока 115, возбудит единичный сигнал на его втором

5 выходе. С этого момента начинается подсчет длины связей в блоке 122 между 1-й вершиной графа и остальными вершинами первого подграфа. Для этого в блок 122 на вход 106 поступает информация из блока

0 120 о номерах вершин, включенных в данный подграф, а из блока 117 через блок 116 поступает следующая информация: на вход 101 - информация о смежности вершин (наличие хотя бы одной единицы в коде), на

5 входы 99 и 100 - текущие коды перебора вершин. Если в коде, поступающем на вход 101 блока 122, имеется единичный сигнал, то в блоке 122 из кода номера второй позиции вычитается (по модулю) код номера третьей позиции, а результат вычитания будет суммироваться с предыдущей разностью и накапливаться. Следующий тактовый импульс блока 115 возбудит очередной выход блока 121. и если рассматриваемые вершины смежны, то аналогично будет подсчитано расстояние между ними и просуммировано с уже накопленной суммой (накопление численного значения критерия размещения).

При более детальном рассмотрении работы устройства в соответствии с фиг.1...3 необходимо учесть, что для подготовки устройства к работе выходы переполнения регистров 2 и 22 устанавливаются на тот разряд, который соответствует заданному числу вершин в исходном графе, выход переполнения регистра 25 сдвига устанавливается на тот разряд, который соответствует числу вершин подграфа с максимальной их мощностью, выход переполнения регистра 50 сдвига устанавливается на разряд, соответствующий числу различных вариантов разбиения графа на подграфы, выходы переполнения регистров 5 и 83 устанавливаются на тот разряд, который соответствует числу подграфов, на которое разбивается исходный граф. Блок 4 настраивается на заданную топологию графа, для чего на входы блока 4 подаются соответствующие коды, формируя топологию исходного графа, отображающего заданную схему. Входы блока 4 соответствуют вершинам графа, а выходы - ребрам. Число входов и выходов остальных многоразрядных узлов и блоков рассчитывается на максимальное число вершин и ребер в графе и соединяются между собой жестко.

Перед началом работы в регистры блока 62 записываются двоичные коды номеров позиций (в первый регистр код - 100. во второй - 010, в третий 011), регистры 38,39, 79 устанавливаются в нулевое состояние, триггер 70 устанавливается в единичное состояние, регистры 2,22,40,5,25,41, триггеры группы 8, буферные регистры 77 и 19 устанавливаются в нулевое состояние. В буферный регистр 37 записывается код (11...1). Триггеры 11 устанавливаются в единичное состояние, а сбрасываются только триггеры, соответствующие базовым вершинам. Узлом 6 коммутации выходы регистра 5 сдвига в соответствующем порядке подключаются к единичным входам соответствующих триггеров группы 8. обеспечения выбор по одной базовой вершине для каждого подграфа. Порядок подключения К выходов регистра 5 к триггерам группы 8 определяется тем, какие вершины графа должны быть базовыми для соответствующих подграфов и в каком порядке будут формироваться подграфы. Например, если граф с числом вершин, равным 30, необходимо разбить на три подграфа (т.е. К 3), а базовыми вершинами должны быть 5-я, 11-я и 5 15-я. то последовательно будут формироваться первый подграф с 5-й боковой вершиной, второй подграф с 11-й базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии 10 единичный потенциал будет только на одном, первом 1ыходе регистра 5 сдвига, т.е. формируется первый подграф и перед началом работы только первый выход регистра 5 сдвига подключен к одному из триггеров 15 группы 8 (в соответствии с примером к пятому триггеру группы 8).

При подаче сигнала на вход установки исходного состояния одновременно на все входы блока 4 поступят единичные сигналы 0 и на соответствующих выходах, в зависимости от конкретной топологии графа, появятся единичные сигналы, число которых будет равно общему числу ребер, входящих в данный граф. Это число преобразуется шифра- 5 тором 17 в соответствующий код и записывается в блок 34 по сигналу, подаваемому на вход Сложение, т.е. этот код складывается с нулевым кодом блока 34. По окончании формирования очередного под- 0 графа из кода этого числа вычитается код числа внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. На выходе триггера 51 устанавливается единичный сигнал, который, 5 поступая на соответствующие входы коммутаторов 3, 16 и 23, осуществляет их включение на передачу информации, поступающей на их входы в прямом, транзитном направлении (для коммутаторов 3 и 16 это передача 0 слева направо, а для коммутатора 23 - сверху вниз, согласно фиг.1).

Устройство работает следующим образом.

Каждый тактовый импульс, поступая с 5 генератора 1 на регистр 2 сдвига, поочередно подключает каждый его выход через коммутатор 3 к соответствующему входу блока 4, то есть подает поочередно на все вершины графа единичный потенциал. В соответ- 0 ствии с этим в первом такте единичный потенциал будет подан на 5-ю вершину (пятый вход блока 4) как базовую для первого подграфа с Ьго выхода регистра 5 сдвига через узел 6 коммутации, пятый элемент 5 ИЛИ группы 7, взведенный пятый триггер группы 8, пятый элемент ИЛИ группы 9, пятый элемент И группы 10, на входе которого постоянно присутствует единичный потенциал с пятого триггера группы 11, далее, через пятый элемент И группы 12, на вход

которого постоянно подается единичный потенциал с пятого триггера группы 13 и, далее, через пятый элемент ИЛИ группы 14 на пятый вход блока 4. Кроме того, в первом такте единичный потенциал будет подан и на первый вход блока 4 с первого выхода регистра 2 сдвига через коммутатор. 3, элемент ИЛИ 9 и далее по описанной выше цепочке, только с индексом 1. Поэтому единичный потенциал присутствует на 1-м и 5-м входах блока 4, на соответствующих выходах блока 4 появляются единичные потен- циалы, т.е. соответствующих ребрах, которые связывают 1-ю и 5-ю вершины. Число ребер, идентичных 1-й и 5-й вершинам, пройдя через открытые элементы И 15 коммутатора 16, преобразуется шифратором 17 в соответствующий код, который сравнивается с кодом, поступающим на схему 18 сравнения с буферного регистра 19. В первом такте в регистре 19 записан код 000...0. Если код шифратора 17 больше кода регистра 19, то схема 18 сравнения вырабатывает на своем выходе единичный сигнал, по которому код шифратора 17 через элементы И 20 переписывается в буферный регистр 19, а в буферный регистр 21 из регистра 22 через коммутатор 23 переписывается код номера вершины, в данном случае первой вершины (код 000...01), Во втором такте единичный потенциал подается на 5-ю и на 2-ю вершину. Если число ребер, связывающих 2-ю и вершины, будет меньше числа ребер, связывающих 1-ю и 5-ю вершины, то на выходе схемы 18 сравнения единичный сигнал не вырабатывается и содержимое регистра 22 и регистра 19 не изменяется. В противном случае сигнал вырабатывается, в буферный регистр 19 переписывается код, соответствующий числу ребер, связывающих 2-ю и 5-ю вершины, а в буферный регистр 21 переписывается код 00...10.

Таким образом, последовательно все выходы регистра 2 сдвига оказываются поочередно подключенными к входам блока 4, а в буферный регистр 21 записывается код номера вершины, имеющей с базовой (в примере - с 5-й) вершиной наибольшее число ребер. Следующий тактовый импульс сформирует на выходе переполнения регистра 2 сдвига единичный сигнал, который через открытый элемент И 24 продвигает единицу в регистре 25 сдвига и подает сигнал разрешения на элементы И группы 26, так как на другой вход элемента И 24 подается инверсный сигнал с установленного в исходное состояние триггера 27 через элемент 28 задержки и элемент НЕ 29. В результате этого единичный сигнал с того выхода буферного регистра 21, который соответствует вершине, максимальным числом ребер связанной с 5-й вершиной, поступает на соответствующий триггер группы 8 и переводит его в единичное состояние до

окончания формирования первого варианта разбиения графа на подграфы.

Это означает, что в первый подграф включены уже две вершины: базовая (5-я вершина) и вершина, связанная с ней наи0 большим числом ребер.

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

0 предыдущем цикле.

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

5 регистра сдвига 25, который поступает на регистр сдвига 5 и продвигает единицу на его второй выход, к которому подключен одиннадцатый триггер группы 8 базовой вершины второго подграфа. Сигнал с выхо0 да регистра 25 поступает через элемент 30 задержки и элемент ИЛИ 31 на входы элементов И группы 32, через элемент ИЛИ 13 (обнуляет) устанавливает в исходное состояние буферный регистр 19, поступает на

5 вход Вычитание (В) блока 34 сложения- вычитания, в котором хранится код суммарного числа связей исходного графа. Из этого кода вычитается код числа связей, соединяющих вершины, выбранные (включенные) в

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

При поступлении сигналов входы элементов И группы 32, на первые входы которых поданы единичные сигналы с триггеров 8, соответствующих вершинам, ото0 бранным в первый подграф, на выходах соответствующих элементов И группы 32 появляется единичный сигнал, который перебрасывает соответствующие триггеры группы 11. Поэтому закрываются соответст5 вугащие им элементы И группы 10 и на связанные с этими элементами входы блока 4 через соответствующие открытые элементы И группы 12 и элементы ИЛИ группы 14 единичные сигналы поступать не будут, то есть отобранные в первый подграф вершины блокируются до конца получения первого варианта разбиения и не участвуют в формировании оставшихся подграфов.

Так как единичный сигнал присутствует уже на втором выходе регистра 5 сдвига, то он будет подаваться на вторую базовую вершину и аналогично рассмотренному выше формируется второй подграф. После окончания формирования второго подграфа на выходе регистра 25 появится сигнал, который продвигает единицу в регистр 5 на третий выход. По следующему тактовому импульсу начинается формирование третьего подграфа и т.д. до тех пор, пока не будут сформированы все подграфы. Это значит, что каждая вершина графа включена в какой-либо из подграфов, т.е. на выходе каждого из триггеров группы 8 присутствует единица, поэтому появляется сигнал на выходе элемента И 35, который поступает на вход схемы 36 сравнения. Этот сигнал разрешает сравнение кода, записанного в буферном регистре 36 (перед сравнением, после окончания первого разбиения, в нем записан максимально возможный код 11...1), с кодом, находящимся в блоке сложения-вычитания 34 и соответствующим числу связей между подграфами графа. Если код буферного регистра 37 больше кода блока сложения-вычитания 34, то схема 36 сравнения вырабатывает сигнал, по которому код блока сложения-вычитания 34 переписывается в буферный регистр 37, а содержимое регистров группы 38 переписывается в регистры группы 39. Это означает, что запомнилось лучшее из предшествующих разбиений, т.е. какие вершины вошли в какой подграф и число связей между подграфами при таком разбиении. Если же содержимое буферного регистра 37 меньше содержимого блока сложения-вычитания 34, то на выходе схемы сравнения сигнал не появляется и содержимое блоков 37 и 39 не изменится.

Группа элементов, в которую входят регистры 40 и 41. группа 42 элементов И, группа 13 триггеров, группа 43 дифференцирующих элементов, элемент ИЛИ 44, триггер 27, элементы 28, 45 задержки и элемент НЕ 29, обеспечивает выбор новой ветви разбиения графа на подграфы с тем, чтобы процесс разбиения на втором цикле разбиения не пошел по уже проделанному пути. Это достигается путем блокировки вершины, которая была выбрана в первом варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в начале формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой, будет выбрана другая вершина, имеющая с базовой максимальное число связей, за исключением вершины, которая была выбрана в первом 5 варианте разбиения как максимально связанная, но которая в начале формирования второго варианта заблокирована. По окончании формирования первого варианта разбиения сигнал с элемента И 35 прежде, чем 1,0 поступать на вход элемента ИЛИ 46 и привести все устройство в исходное состояние перед началом формирования второго варианта разбиения, поступает на вход регистра 4 сдвига и продвигает единицу на его пер- 15 вый выход (верхний по схеме), взводит триггер 27 и через элемент 45 задержки поступает на регистр 40 сдвига, по которому происходит перезапись информации из регистра 41 в регистр 40, но уже в инверсном 0 коде. В регистре 41 по-прежнему остается код 100...О, а в регистре 40 будет код 00...01, который определяет время блокировки перезаписи информации из буферного регистра 21 в триггеры группы 8, так как эта 5 блокировка обеспечивается отсутствием сигнала на входе элемента И 24 через последовательно соединенные триггер 27, элемент 28 задержки и элемент НЕ 29.

Сигнал с элемента И 35 через элемент 0 47 задержки поступает на вход элемента ИЛИ 46, который приводит в исходное состояние регистр 5 сдвига (как описано ранее, записывается код 100...00), сбрасывает триггеры группы 8, через элементы ИЛИ 5 группы 48 сбрасывает триггеры группы 11 и через элемент ИЛИ 49 обнуляет регистры сдвига 2 и 22 и буферный регистр 19. Устройство приведено в исходное состояние и готово к формированию очередного варианта 0 разбиения

Второй вариант разбиения начинается по очередному импульсу генератора 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В ка- 5 честве этой вершины будет выбрана та же вершина, что и в первом разбиении (признак окончания выбора этой вершины - сигнал с выхода переполнения регистра сдвига 2), однако, она не будет включена в первый 0 подграф (не будет взведен соответствующий триггер группы 8), так как элемент И 24 по одному из входов будет заблокирован инверсным сигналом с нулевого выхода триггера 27. По этому же сигналу с регистра 5 2 сдвига продвигается единица на выход переполнения регистра 40 сдвига, в результате чего перебросится триггер 27 и разблокирует элемент И 24, т.е. после выбора следующей вершины (появления импульса на выходе регистра 2 сдвига) она будет включена в подграф. Во время выбора этой вершины выбранная вершима на предыдущем шаге, как максимальным числом связанная с базовой, должна быть заблокирована на входе блока 4, т.е. не должна участвовать в переборе вершин при поиске максимально связанной с базовой-во втором варианте разбиения, для того, чтобы она вновь не была выбрана в подграф и процесс разбиения не пошел бы по той же ветви, что и при первом разбиении, т.е. чтобы не повторилось первое разбиение. Блокировка этой вершины осуществляется следующим образом.

Перед началом поиска второго варианта разбиения будет включена (взведен триггер 27) только блокировка включения в подграф максимально связанной вершины с базовой, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вер- шины будет находиться в буферном регистре 21, а ее код будет подан на входы соответствующих элементов И группы 42, на другие входы которых подается сигнал с триггера 27. Поэтому после окончания первого просмотра по сигналу с выхода переполнения регистра 2 сдвига происходит установка соответствующего триггера в нулевое состояние, таким образом эта вершина не участвует в процессе перебора вершин на втором шаге второго варианта разбиения. После окончания этого шага в буферный регистр 21 записывается код вершины, максимальным числом связей соединенной с базовой, за исключением заблокированной. Однако, код этой вершины не проходит через группу 42 элементов И, так как уже продвинута единица на выход переполнения регистра 40 сдвига и, перебросив триггер в нулевое состояние, разблокирует цепь перезаписи о триггеры группы 8 и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины. Поэтому на выходе элемента И 24 появится сигнал, который взводит все триггеры группы 13, разблокировав тем самым заблокированную вершину. Кроме того, по появлении хотя бы одного импульса на выходах элементов И группы 42 сигналом с выхода элемента ИЛИ 44 происходит обнуление буферного регистра 19, для того, чтобы на втором шаге второго варианта разбиения сравнение происходило с кодом 00...О, а не с кодом числа связей заблокированной вершины,

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

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

Описанная выше процедура формирования очередного варианта разбиения гра0 фа на подграфы и выбор среди них наилучшего будет продолжаться до тех пор, пока на выходе переполнения регистра 50 сдвига не появится сигнал. Число вариантов разбиения определяется содержимым реги5 стра 50. Единичный сигнал с выхода переполнения регистра 50 поступает на триггер 51 установки режима и перебрасывает его из состояния Транзит (сигнал 1 на выходе Т) в состояние Переключение (сигнал

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

5 выхода Т триггера 51 заблокирует пути прохождения сигналов через элемент И 52, элементы И группы 15 управляемого коммутатора 16, элементы И группы 53. Этот же сигнал, поступив на вход элементов И 54 и

0 55, обеспечит блокировку прохождения сигналов через группу 12 элементов И на входы блока 4. Единичный сигнал с выхода П триггера 51 обеспечивает разрешение прохождения сигналов через элементы И груп5 пы 71 коммутатора 16с выходов блока 4 на элемент ИЛИ 57. Аналогично осуществляется коммутация выходов регистров 2 и 22 с входами блока 4 через элементы ИЛИ группы 14 при помощи соответственно коммута0 торов 3 и 23. на входы П которых поданы единичные сигналы. Кроме того, по единичному сигналу с регистра 50, прошедшему через элементы ИЛИ 46 и 49, осуществляется сброс регистров 2 и 22 и запись еди5 ницы соответственно в нулевой и первый разряды, блок 58 формирования перестановок устанавливается в состояние, соответствующее первой формируемой перестановке. Для определенности положим, что осуществляется размещение трех

элементов схемы (вершина графа), составляющих первую часть схемы (первый подграф) с момента времени, когда сигнал с выхода переполнения регистра 22 через открытый элемент И 59 установит в блоке 58 перестановку 312 (ей предшествовали перестановки 123, 213, 231 и 321). Очередной тактовый импульс с выхода генератора 1 продвигает единицу на последний выход регистра 2 сдвига и, поступая через элемент И 60 и элемент ЗАПРЕТ 61 на вход блока 58 формирования перестановок, возбудит единичный сигнал на его втором выходе. С этого момента начинается подсчет длины связей между 1-й вершиной графа и осталь- ными двумя вершинами первого подграфа. Поэтому двоичный код 010 с выходов второго регистра группы 62 через коммутатор 63 (верхний выход) в качестве уменьшаемого по сигналу, поступающему на вход вычита- теля 64 и сумматора 65 с первого выхода регистра 2 сдвига, перепишется в вычита- тель 64, а в сумматор 65 из вычитателя 64 перепишется нулевой код. На первом элементе И группы 66 произойдет совпадение единичных сигналов с регистров 2 и 22 через коммутаторы соответственно 3 и 23, а также с элементов ИЛИ группы 67, через которые поступает информация с регистров группы 39 о номерах вершин, включенных в подграф. В результате совпадения этих трех сигналов на выходе первого (верхнего) элемента И группы 66 появится единичный сигнал, который через элемент ИЛИ 68 и элемент 69 задержки поступит на нулевой вход триггера 70. Вследствие этого коммутатор 63 подключит регистры группы 62 к входам (нижним по схеме) вычитателя 64. Второй тактовый импульс продвинет единицу на второй выход регистра 2 сдвига и возбудит единичный сигнал на 3- м выходе блока 58 формирования перестановок, который через коммутатор 63 подключает третий регистр группы 62 к вычитателю 64. При этом единичный сигнал поступает на пер- вый вход блока 4 с выхода регистра 22 сдвига через коммутатор 23 и элемент ИЛИ 14 и на второй вход блока 4 с выхода регистра 2 сдвига через второй элемент ИЛИ группы 14 (т.е. на 1-ю и 2-ю вершины первого подгра- фа).

Если первая и вторая вершины подграфа смежны, то на первом выходе блока 4 появится единичный сигнал (может возникнуть ситуация, при которой вершины одного подграфа не связаны между собой), который через открытый элемент И 71 группы коммутатора 16, элемент ИЛИ 57 и элемент И 72 поступит на вход вычитателя 64. В результате этого из кода 010 номера второй позиции

вычитается (по модулю) код 011 номера третьей позиции и по сигналу с элемента 73 задержки результат вычитания поступит на сумматор 65 и сложится с его содержимым. Третий тлктовый импульс передвинет единичное значение на третий выход регистра 2 сдвига и возбудит первый выход блока 58 формирования перестановок. Если первая и третья вершины смежны, то на соответствующем выходе блока 4 появится сигнал, который через элементы И группы 71, ИЛИ 57 и И 72 поступит на вычитатель 64. к которому подключается первый регистр группы 62 и из кода 010 вычитается код 100. Результат вычитания по сигналу с элемента задержки 73 аналогично описанному выше сложится с содержимым сумматора 65. Четвертый тактовый импульс ни один из выходов блока 58 не возбуждает, а лишь подготавливает его к следующему циклу формирования перестановки 312, но появляется на выходе переполнения регистра 2 сдвига и, пройдя через открытый элемент И 74 и элемент ИЛИ 75, продвигает единицу на второй выход регистра 22 сдвига, а пройдя через элемент ИЛИ 76, переведет триггер 70 в единичное состояние. Содержимое сумматора 65 при этом не меняется. Пятым тактовым импульсом начинается новый цикл формирования перестановки 312. Но подсчет длины связей будет производиться только от 2-й вершины до 3-й, так как длина связи от 1-й вершины до 2-й была уже подсчитана в предыдущем цикле. Таким образом исключается двойной учет одних и тех же связей. Реализуется это тем. что после первого цикла просмотра смежности 1-й вершины со всеми вершинами, вошедшими в первый подграф (что определяется наличием единиц на соответствующих элементах И группы 66 с соответствующего регистра группы 39 через элементы ИЛИ группы 67), перевод триггера 70 в нулевое состояние осуществляется не первым тактовым импульсом в новом цикле (т.е. 5-м при сквозном счете), а вторым, когда произойдет совпадение единичных сигналов на втором элементе И группы 66. Поэтому на протяжении двух тактов коммутатором 63 к входу вычитателя 64 будут подключены регистры группы 62 и код последнего из подключаемых регистров (в данном случае код 011 3-го регистра, соответствующий размещению 2-й вершины в 3-ю позицию) зафиксируется в вычитателе 64 в качестве уменьшаемого. Только после этого задержанным на элементе 69 вторым тактовым импульсом (т.е. 6-м при сквозном счете) триггер 70 переведется в нулевое состояние и коммутатором 63 регистры группы 62 будут подключены к входу вычитателя 64.

Аналогично четвертому тактовому импульсу по восьмому импульсу блок 58 подготовится к формированию нового цикла перестановки 312, а единичное значение перейдет на третий вход регистра 92 сдвига. Следующие 9-й, 10-й и 11-й тактовые импульсы подсчет длины связей производить не будут, так как эти длины были уже подсчитаны в предыдущих циклах и просуммированы сумматором 65.

По 12-у тактовому импульсу единичный сигнал появится на выходах переполения регистров 2 и 22, что вызовет перевод триггера 70 в единичное состояние, подготовку блока 58 к формированию новой переста- новки 321 и сравнение кодов в сумматоре 65 и в буферном регистре 77, Предположим, что код в сумматоре 65 меньше кода в регистре 77 (это означает, что последнее размещение элементов в позиции дает меньшую суммарную длийу связей, поэтому его нужно запомнить), тогда на выходе схемы сравнения 78 появляется сигнал, по которому содержимое сумматора 65 переписывается в буферный регистр 77, а соотвв1ствующая перестановка переписывается из блока 58 в регистры 79, ...

Запоминание лучшего варианта размещения в регистрах группы 79 осуществляется следующим образом.

В момент времени, когда единичный сигнал имеется на последнем (нижнем) выходе регистра 2 сдвига, он имеется и на втором выходе блока 58. Поэтому будет открыт соответствующий элемент И группы 80 (четвертый элемент И группы 80), к которому подключен второй регистр группы 62, и код 010 этого регистра через первый элемент ИЛИ группы 81 переписывается в первый регистр группы 38. В момент времени, когда единичный сигнал будет на втором выходе регистра 2 сдвига, он будет и на третьем выходе блока 56. Поэтому код третьего регистра группы 62 через открытый элемент И группы 80 и второй элемент ИЛИ группы 81 перепишется во второй регистр группы 38. Аналогичным образом код первого регистра группы 62 через открытый третий элемент И

Формула изобретения 50

55

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ, содержащее генератор тактовых импульсов, блок памяти топологии графа, три группы регистров, первый коммутатор, элементы И, группы элементов И, элементы задержки, группы элементов ИЛИ, первый буферный регистр, два регистра сдвига, блок формирования перестановок, первый триггер, вычитатель, суммагруппы 80 и третий элемент ИЛИ группы 81 запишется в третий регистр группы 38. В момент же поступления сигнала со схемы сравнения 78 на регистры группы 79 произойдет, как было описано выше, перепись информации из регистров группы 38 в регистры группы 79.

После этого начинается процесс формирования нового размещения и анализ суммарной длины связей между вершинами. Если новое размещение будет иметь меньшую суммарную длину связей, то этот вариант размещения запомнится в регистрах группы 79. После перебора всех перестановок и их анализа на выходе окончания формирования перестановок блока 58 появится единичный сигнал, являющийся признаком окончания оптимального размещения элементов первой группы вершин (первого подграфа) на плоскости. Этот же сигнал приведет в исходное состояние регистры 2 и 22 (т.е. записываются единичные значения соответственно в нулевой и первый разряды), блок 58 устанавливается в состояние, соответствующее первой перестановке, в регистры группы 62 записываются двоичные коды номеров позиций, триггер 70 устанавливается в единичное состояние, буферный регистр 77 и регистры групп 38 и 79. Этот же сигнал осуществляет вывод результатов очередного размещения на индикацию в блок 82 и, продвинув в регистре 83 сдвига единицу на следующий выход, разрешит передачу информации с очередного регистра группы 39 через элемент ИЛИ группы 67 на элементы И группы 66, тем самым, подав информацию об элементах, включенных во вторую группу (вершинах, вошедших во второй подграф), и процедура оптимального размещения повторится аналогично описанному выше.

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

тор, первую схему сравнения, элемент ЗАПРЕТ, причем информационные входы устройства соединены с установочными входами блока памяти топологии графа, выход генератора тактовых импульсов соединен с входом управления сдвигом первого регистра сдвига, выход элемента ЗАПРЕТ соединен с синхронизирующим входом блока формирования перестановок, информационные выходы блока формирования перестановок сое21164288222

динены с информационными входами коммутаторов и с первыми входами первой группы первого .коммутатора, четвертого и пятого элементов И, выход информационные входы второй группы третьего элемента И соединен с пря- первого коммутатора подключены к вы- . Мым входом элемента ЗАПРЕТ и через ходам регистров первой группы соот- 5 второй элемент задержки с синхронизи- ветственно. выход первой схемы срав- рующим входом сумматора, нулевой вы- нения подключен к входам записи ход второго триггера соединен с вторы- регистров второй группы и первого бу- ми управляющими входами второго, ферного регистра, информационный третьего и четвертого коммутаторов, с вход которого и первый инфор- Ю вторым входом второго элемента И, с мационный вход первой схемы сравне- первыми входами шестого и седьмого ния соединены с выходом сумматора, элементов И и с первыми входами эле- втооой информационный вход первой ментов И первой группы, выход второ- схемы сравнения соединен с выходом го элемента И соединен с первым вхо- первого буферного регистра, инфор- 1Ь дом четвертого элемента ИЛИ, второй мационные выходы первого регистра ВХОд которого соединен с выходом пя- сдвига соединены с информационными того элемента И и с -первым входом входами второго коммутатора, выход второго элемента ИЛИ, второй вход первого элемента И подключен к синх- 20 второго элемента ИЛИ, первый вход ронизирующему входу вычитателя, а пятого элемента ИЛИ, входы установки первый вход соединен с выходом пер- исходного состояния блока формиро- вого элемента ИЛИ. выход переполне- вания перестановок, входы регистров ния первого регистра сдвига подключен первой группы, управляющий вход пер- к информационному входу второго реги- 25 вого буферного регистра и вход управ- стра сдвига, единичный вход первого ления сдвигом третьего регистра сдвига триггера соединен с выходом второго соединены с выходом переполнения элемента ИЛИ, а нулевой вход через блока формирования перестановок, вы- первый элемент задержки соединен с ходы регистров второй группы являются выходом третьего элемента ИЛИ. еди- 30 информационным выходом устройства, ничный выход первого триггера подклю- разрешающие входы регистров третьей чен к первому управляющему входу группы соединены с выходами третьего первого коммутатора, нулевой выход регистра сдвига соответственно, выходы первого триггера соединен с вторым регистров третьей группы соединены с управляющим входом первого коммута- 35 входами элементов ИЛИ первой группы тора и с вторым входом первого эле- соответственно, выходы элементов ИЛИ мента И, входы уменьшаемого и вычи- первой группы соединены с первыми таемого вычитателя соединены с входами элементов И второй группы выходами первого коммутатора соответ- соответственно, второй вход каждого из ственно, выход вычитателя подключен к которых соединен с соответствующим информационному входу сумматора, от- информационным выходом первой груп- лтающееся тем, что, с целью повыше- Пы второго коммутатора, третий вход ния быстродействия, в него введены каждого элемента И второй группы сое- два коммутатора, узел коммутации. 45 динен с соответствующим выходом пер- группы элементов ИЛИ, группы тригге- Вой группы третьего коммутатора, пер- ров, группы элементов И, элементы 8ый информационный вход которого ИЛИ, регистры сдвига, группа регист- соединен с выходом четвертого регистров, схемы сравнения, буферные регист- Ра сдвига, выход переполнения первого ры, элементы И, элементы задержки. 50 регистра сдвига соединен с первым триггеры. группы дифференцирующих входом восьмого элемента И. с вторы- элементов. блок сложения-вычитания, ми входами пятого и шестого элемен- элемент НЕ и шифратор, причем выход тов И. выход четвертого элемента ИЛИ генераторов тактовых импульсов соеди- соединен с входом управления сдвигом нен с первыми входами второго и 55 четвертого регистра сдвига, выход перетретьего элементов И, вторые входы полнения которого соединен с вторым второго и третьего элементов И соеди- входом четвертого элемента И, выходы нены с единичным выходом второго второй группы третьего коммутатора со- триггера, с первыми управляющими вхо- единены с информационными входами дами второго, третьего и четвертого второго буферного регистра, выходы

23164288224

разрядов второго буферного регистра вятого элемента И, выход девятого эле- соединены с первыми входами элемен- мента И соединен с управляющим тов И третьей группы и с первыми входом третьей схемы сравнения, с ну- входами элементов И четвертой группы, левым входом третьего триггера, с ехо- вход записи второго буферного регист- 5 дом управления сдвигом пятого регистра соединен с выходом второй схемы ра сдвига и через четвертый элемент сравнения и с первыми входами эле- задержки с установочным входом второ- ментов И пятой группы, вторые входы го регистра сдвига, входы рязрадов ко- элементов И третьей группы соединены торого соединены с выходами разрядов с выходом восьмого элемента И и с 10 пятого регистра сдвига, а выход перевторым входом седьмого элемента И, полнения подключен к единичному вхо- выход которого соединен с единичными ду третьего триггера, нулевой выход ко- входами триггеров первой группы, нуле- торого соединен с вторыми входами вые входы которых соединены с выхо-. элементов И четвертой группы, а через дами элементов И четвертой группы и последовательно соединенные пятый с входами дифференцирующих элемен-: элемент задержки и элемент НЕ - с тов первой группы, нулевые выходы вторым входом восьмого элемента И, триггеров первой группы соединены с выход шестого элемента И соединен с, первыми входами элементов И шестой «п третьими входами элементов И четвер- группы, выходы которых соединены с той группы, выходы дифференцирующих первыми входами элементов .ИЛИ вто- элементов первой группы соединены с рой группы, вторые входы которых сое- входами седьмого элемента ИЛИ, выход динены с входом установки исходного которого соединен с первым входом состояния устройства, соединенного с 25 восьмого элемента ИЛИ, второй вход первым входом шестого элемента ИЛИ, которого и установочные входы пер- с нулевым входом второго триггера, с вого, четвертого и восьмого регистров установочным входом пятого регистра сдвига соединены с выходом пятого сдвига, а через второй элемент задерж- элемента ИЛИ, выход восьмого элемен- ки с установочным входом третьего бу-30 та ИЛИ соединен с установочным вхо- ферного регистра и с входом управле- дом четвертого буферного регистра, ниясложениемблока входы разрядов которого соединены с

сложения-вычитания, выходы разрядов выходами элементов И пятой группы, шестого регистра сдвига через узел выход четвертого буферного регистра коммутации соединены с первыми вхо- 35 соединен с первым информационным дами элементов ИЛИ третьей группы, входом второй схемы сравнения, выход вторые входы которых соединены с вы- шифратора соединен с вторым инфор-, ходами элементов И третьей группы. мационным входом второй схемы срав- выходы элементов ИЛИ третьей группы 4Q нения, с вторыми входами элементов И| соединены с единичными входами триг- пятой группы и с информационным BXO-I геров второй группы и с вторыми вхо- дом блока сложения-вычитания, вход дами элементов И первой группы, вы- управления вычитанием которого соеди- ходы элементов И первой группы нен с выходом переполнения восьмого соединены с первыми входами элемен- 45 регистра сдвига, с входом шестого эле- тов ИЛИ четвертой группы, выход шее- мента задержки, с третьим входом того элемента ИЛИ соединен с нулевы- восьмого элемента ИЛИ и с входом уп- ми входами триггеров второй группы, с равления сдвигом шестого регистра вторым входом пятого элемента ИЛИ, с сдвига, выход блока сложения-вычита-, первыми входами элементов ИЛИ пятой 50 ния соединен с информационным вхо- группы и с установочными входами ше- дом третьего буферного регистра и с стого и седьмого регистров сдвига, вы- первым информационным входом ход переполнения шестого регистра третьей схемы сравнения, второй ин- сдвига соединен с информационным формационный вход которой соединен с входом седьмого регистра сдвига, выход 55 информационным выходом третьего бу- переполнения которого соединен с еди- ферного регистра, а выход соединен с ничным. входом второго триггера и с управляющим входом третьего буферно- вторым входом шестого элемента ИЛИ, го регистра и с управляющими входами третий вход которого через третий эле- регистров третьей группы, единичные мент задержки соединен с выходом де- выходы триггеров второй группы соеди25164288226

йены с вторыми входами соответствую- мационный выход подключен к входам щих элементов ИЛИ пятой группы, с первого элемента ИЛИ. выход четверго- .первыми входами соответствующих эле- го элемента И соединен с управляю- ;ментов ИЛИ шестой группы, с первыми - ЩИм входом блока формирования входами элементов И седьмой группы и 5 перестановок, с инверсным входом эле- с входами девятого элемента И соот- мента ЗАПРЕТ и с разрешающим вхо- ветственно. вторые входы элементов дом первой схемы сравнения, ИЛИ шестой группы соединены с ин- информационные выходы блока форми- формационными выходами второй труп- рования перестановок соединены с пер- пы второго коммутатора, вторые входы 10 выми входами элементов И девятой элементов И седьмой группы соединены группы, вторые входы которых соедине- с выходом девятого элемента ИЛИ, ны с выходами соответствующих регист- лервый вход которого соединен с выхо- ров первой группы, выход каждого дом шестого элемента задержки, второй ч элемента И девятой группы соединен с вход соединен с входом установки ис- 15 входами соответствующих элементов ходного состояния устройства, выходы ИЛИ четвертой группы, выходы которых элементов И седьмой группы соединены соединены с информационными входами с единичными входами соответствующих соответствующих регистров второй и триггеров третьей группы, нулевой вход . четвертой групп, выход каждого элемен- каждого из которых соединен с выхо- та и второй группы через дифференци- дом соответствующего элемента ИЛИ рующий элемент второй группы пятой группы, нулевые выходы тригге- соединен с соответствующим входом ров третьей группы соединены с первы- третьего элемента ИЛИ, инфор- ми входами соответствующих элементов 25 мационные входы блока памяти тополо- И восьмой группы, второй вход каждого гии графа соединены с выходами из которых соединен с выходом соот- элементов ИЛИ второй группы, входы ветствующего элемента ИЛИ шестой записи регистров четвертой группы сое- группы, выход каждого элемента И динены с выходами первой группы восьмой группы соединен с вторым 30 третьего коммутатора, а выходы под- входом соответствующего элемента И ключены к информационным входам ре- шестой группы, выходы блока памяти гистров третьей группы, третьи входы топологии графа соединены с инфор- элементов И девятой группы соединены мационными входами четвертого комму- с соответствующими информационными татора, первый информационный выход 35 ВЫХодами первой группы второго ком- которого соединен с информационным мутатора. входом шифратора, второй инфорФиг1

w

лСЛ.м

«

Фиг. 2