Устройство для решения задачи размещения
Изобретение относится к вычислительной технике и может быть использовано для автоматизированного построения радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является повышение быстродействия. Устройство содержит генератор тактовых импульсов, регистры сдвига, коммутаторы, блок памяти топологии графа, узел коммутации, группы элементов ИЛИ, группы триггеров, группы элементов И, шифратор, схемы сравнения, буферные регистры, элементы И, триггеры, элементы задержки, элемент НЕ, элементы ИЛИ, блок сложения-вычитания, группы регистров, группы дифференцирующих элементов, блок формирования перестановок, элемент ЗАПРЕТ, вычислитель, сумматор, блок индикации. 5 ил.
Изобретение относится к вычислительной технике и может быть использовано для автоматизированного конструирования радиоэлектронной и электронно-вычислительной аппаратуры. Целью изобретения является повышение быстродействия. На фиг. 1-3 приведена структурная схема устройства; на фиг.4 пример построения коммутатора; на фиг.5 обобщенная структурная схема. Устройство содержит генератор 1 тактовых импульсов (ГТИ), регистр 2 сдвига, коммутатор 3, блок 4 памяти топологии графа, регистр 5 сдвига, узел 6 коммутации, группу 7 элементов ИЛИ, группу 8 триггеров, группу 9 элементов ИЛИ, группу 10 элементов И, группу 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 элементов И, группу 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, 10 и 32 элементов И, группы 7, 9, 14, 48 элементов ИЛИ, группы 8, 11 триггеров, элементы 30, 47, 56 задержки, элементы ИЛИ 31, 33, 46, триггер 51. В блок 119 блокировки вершин входят регистры 40, 41 сдвига, группа 42 элементов И, группа 13 триггеров, группа 43 дифференцирующих элементов, элементы 28, 45 задержки, элемент НЕ 29, триггер 27, элементы И 54, ИЛИ 44. В блок 118 выбора наилучшего варианта входят шифратор 17, схемы 18, 36 сравнения, буферные регистры 19, 37, группа 20 элементов И, блок 34 сложения-вычитания. В блок 120 регистрации входят группы 38, 39, 79 регистров, регистр сдвига 83, группа 67 элементов ИЛИ, блок 82 индикации. В блок 122 вычисления критерия размещения входят элементы ИЛИ 57, 68, 76, 110, 112, элементы И 60, 72, элементы 69, 73 задержки, триггер 70, группа 62 регистров, коммутатор 63, вычитатель 64, сумматор 65, буферный регистр 77, схема 78 сравнения, группы 66, 80, 111, 113 элементов И, группа 81 элементов ИЛИ, группа 114 дифференцирующих элементов. Позициями 123-130 обозначены связи. Каждому входу блока памяти топологии графа поставлена в соответствие вершина графа, а каждому выходу ребро между любой парой вершин. Топология исходного графа задается блоком памяти топологии графа таким образом, что при подаче на его входы единичного сигнала он появится на тех выходах, то есть соответствующих им ребрам, соединяющих вершины, на которые были поданы единичные сигналы. Это позволяет в каждом такте работы устройства осуществлять выбор той вершины графа, которая имеет наибольшее (наименьшее) число связей c множеством вершин, выбранных в предыдущем такте. Кроме того, в исходном состоянии с помощью узла коммутации выбирается некоторое число вершин, равное заданному числу подграфов, каждая из которых является базовой в соответствующем подграфе и к которой в процессе работы устройства будут присоединяться дpугие вершины графа. Процесс формирования каждого из подграфов графа заканчивается в тот момент, когда в подграф будет включено заданное число вершин, которые должны быть объединены в один подграф. Формирование всех подграфов графа осуществляется последовательно и после окончания процесса исходный граф будет разбит на заданное число подграфов с локально-минимальным числом связей между ними. Полученный результат разбиения графа на подграфы будет записан в регистры. На следующем шаге оптимизации из рассмотрения исключаются те вершины каждого из подграфов, которые были выбраны на первом шаге оптимизации в качестве вершин, имеющих максимальное число связей с базовой вершиной каждого из подграфов. В качестве новой вершины для каждого из подграфов выбирается следующая по максимальной связности с базовой вершиной. Далее процесс формирования подграфов полностью аналогичен описанному выше. Получив разбиение после второго шага оптимизация происходит сравнение результатов первого и второго шагов, по суммарному числу связей между подграфами графа. В блок запоминания матрицы смежности записываются результаты лучшего из двух полученных разбиений по минимуму указанного критеpия. Далее процесс оптимизации протекают аналогично до тех пор, пока не будет проделано заранее заданное количество различных вариантов разбиения, из которых и будет выбран самый оптимальный по минимуму суммарного числа связей между подграфами. Затем последовательно для каждого из подграфов полученного наилучшего разбиения осуществляется оптимальное размещение вершин в координатной сетке. Оптимизируемым критерием качества L является суммарная длина связей между вершинами в узлы Р координатной сетки. Формализованно суммарная длина связей определяется из выражения L
Cijdp(i)p(j) где Сij элемент матрицы смежности С, равный "1", если i-я и j-я вершины смежны, и равен "0" в противном случае; dp(i)p(j) элемент матрицы расстояний D, равный числу шагов координатной сетке между позициями Р(i) и Р(j) при i 
j и dp(i)p(j) 0 при i j; n' число вершин подграфа. Значение величин Сij матрицы смежности формируются на выходах блока 4 памяти топологии графа аналогично тому, как это делалось при декомпозиции исходного графа. В регистры заносятся двоичные коды позиций: в один регистр записывается двоичный код первой позиции 100.0, во второй регистр двоичный код второй позиции 010.0 и т.д. Величина dp(i)p(j) определяется с помощью вычитателя как разность двоичных кодов позиций Р(i) и Р(j). Накопление же суммы длин расстояний L осуществляется с помощью коммутатора и сумматора. Перебор всех возможных размещений вершин подграфа в узлах решетки (позициях) осуществляется с помощью блока формирования перестановок (БФП). При этом каждая перестановка соответствует определенному перемещению вершин в узлы координатной сетки. Так, перестановкe 312 соответствует размещение первой вершины подграфа во второй узел (вторую позицию), второй вершины и первую позицию. Единичный сигнал в каждый тактовый момент времени появляется только на одном выходе блока. Последовательность же появления единичных сигналов на всех его выходах определяется каждой новой перестановкой. Так, перестановке 312 соответствует появление единичного сигнала по первому тактовому импульсу на втором выходе БФП (нумерация выходов БФП сверху вниз), по второму тактовому импульсу "1" появляется на третьем выходе БФП и по третьему на первом выходе. Смена перестановок осуществляется подачей сигнала на вход БФП с выхода регистра сдвига, когда закончится анализ смежности каждой вершины подграфа с каждой и произойдет накопление суммарной взвешенной длины связей L при данной перестановке (размещение вершин подграфа в координатной сетке). С помощью регистров сдвига производится распределение импульсов на блок памяти топологии графа и осуществляется последовательный периодический перебор всех вершин подграфа и проверка смежности первой вершины со всеми остальными, второй со всеми остальными вершинами этого же подграфа и т.д. Синхронно с этим БФП для каждой вершины определяет позицию (узел) в соответствии со сформированной перестановкой. После завершения формирования всех возможных перестановок, их обсчета, выбора и запоминания лучшего варианта в регистрах сигналом с выхода БФП осуществляется перевод работы устройства на поиск оптимального размещения вершин следующего подграфа в позиции (узлы) координатной сетки. Процедура осуществляется аналогично описанной выше. Таким образом, производится оптимальное размещение вершин каждого из подграфов исходного графа. Результирующее размещение графа в координатной сетке представляет собой совокупность слабосвязанных локально-оптимально размещенных вершин подграфов. Рассмотрим сначала подготовку устройства и его работу по обобщенной структурной схеме, представленной на фиг.5. Перед началом работы все блоки устройства устанавливаются в исходное состояние. По входу "Уст." в блок 117 вводится информация об исходном графе. При подаче сигнала на вход 89 установки исходного состояния блока 116 на все информационные входы блока 117 поступят единичные сигналы блока 116 и на соответствующих информационных выходах блока 117, в зависимости от конкретной топологии графа, появятся единичные сигналы, поступающие через блок 116 на вход 128 блока 118. Эти сигналы преобразуются в код, используемый в дальнейшем для вычитания кода числа внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. В конце решения задачи в этом блоке останется (будет храниться) код минимального числа связей между подграфами графа. На выходе "Т" (транзит) блока 116 устанавливается единичный сигнал, присутствующий до окончания работы устройства в режиме декомпозиции. Каждый тактовый импульс с блока 115 через блок 116 поочередно подключает пару информационных кодов блока 117, т.е. поочередно подает на все пары входов блока 117 единичные потенциалы. В соответствии с этим на информационных выходах блока 117 будет формироваться опpеделенный код, подаваемый через вход 128 на блок 118, который выберет и запомнит пару вершин, соответствующих максимальному коду, т. е. пару сильносвязанных вершин. Эта пара вершин "включается" (заносится) в первый подграф путем перезаписи их номеров через входы 96 из блока 116 в блок 120 по сигналу разрешения из блока 118, поступающему на вход 127 блока 120. Аналогичная процедура повторяется до тех пор, пока в подграф не войдет заданное количество вершин, признаком чего является появление единичного сигнала на входе 94 блока 118, по которому произойдет вычитание кода суммарного числа внутренних ребер сформированного подграфа из кода суммарного числа ребер исходного графа. Аналогичным образом осуществляется формирование следующего подграфа с той лишь разницей, что в его формировании уже не участвует часть вершин, отобранных в первый подграф, что обеспечивается блоком 116. Таким же образом осуществляется формирование последующих подграфов, пока не будут сформированы все подграфы. Признаком этого является появление единичного сигнала на выходе 92 блока 116. По этому сигналу в блоке 118 запомнится код числа, соответствующий наилучшей декомпозиции графа (минимум суммарного числа связей между подграфами), блоке 120 будут храниться номера вершин, вошедших в каждый из подграфов. Этот же сигнал, поступивший на вход 92 блока 119, обеспечивает выбор новой ветви разбиения для того, чтобы процесс разбиения во втором цикле разбиения не пошел по уже проделанному пути. Для этого из блока 119 поступает единичный сигнал на вход 97 блока 118, который блокирует вершину, выбранную в предыдущем варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. В результате такой блокировки получаем новый вариант разбиения графа, который сравнивается с уже имеющимся вариантом (по единичному сигналу на входе 92 блока 118 с выхода 92 блока 116) и запоминаем лучший из этих вариантов. Таким образом, осуществляется "просмотр" нескольких вариантов разбиения и выбор наилучшего, пока на выходе "П" (переключение) блока 116 не появится единичный сигнал, являющийся сигналом окончания декомпозиции графа и начала размещения элементов каждого из его подграфов. Единичный сигнал на выходе "П" блока 116 обеспечивает установку элементов устройства в исходное состояние, а блок 121 устанавливается в состояние, соответствующее первой перестановке. Очередной тактовый импульс, поступающий с блока 115, возбудит единичный сигнал на его втором выходе. С этого момента начинается подсчет длины связей в блоке 122 между i-й вершиной графа и остальными вершинами первого подграфа. Для этого в блок 122 на вход 106 поступает информация из блока 120 о номерах вершин, включенных в данный подграф, а из блока 117 через блок 116 поступает следующая информация: на вход 101 информация о смежности вершин (наличие хотя бы одной единицы в коде), на входы 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-я и 15-я, то последовательно будут формироваться первый подграф с 5-й боковой вершиной, второй подграф с 11-й базовой вершиной и третий подграф с 15-й базовой вершиной. Причем в исходном состоянии единичный потенциал будет только на одном, первом выходе регистра 5 сдвига, т.е. формируется первый подграф и перед началом работы только первый выход регистра 5 сдвига подключен к одному из триггеров группы 8 (в соответствии с примером к пятому триггеру группы 8). При подаче сигнала на вход установки исходного состояния одновременно на все входы блока 4 поступят единичные сигналы и на соответствующих выходах, в зависимости от конкретной топологии графа, появятся единичные сигналы, число которых будет равно общему числу ребер, входящих в данный граф. Это число преобразуется шифратором 17 в соответствующий код и записывается в блок 34 по сигналу, подаваемому на вход "Сложение", т.е. этот код складывается с нулевым кодом блока 34. По окончании формирования очередного подграфа из кода этого числа вычитается код числа внутренних (между вершинами, входящими в данный подграф) связей каждого из подграфов. На выходе триггера 51 устанавливается единичный сигнал, который, поступая на соответствующие входы коммутаторов 3, 16 и 23, осуществляет их включение на передачу информации, поступающей на их входы в прямом, транзитном направлении (для коммутаторов 3 и 16 это передача слева направо, а для коммутатора 23 сверху вниз, согласно фиг. 1). Устройство работает следующим образом. Каждый тактовый импульс, поступая с генератора 1 на регистр 2 сдвига, поочередно подключает каждый его выход через коммутатор 3 к соответствующему входу блока 4, то есть подает поочередно на все вершины графа единичный потенциал. В соответствии с этим в первом такте единичный потенциал будет подан на 5-ю вершину (пятый вход блока 4) как базовую для первого подграфа с 1-го выхода регистра 5 сдвига через узел 6 коммутации, пятый элемент ИЛИ группы 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-ю и 5-ю вершины, будет меньше числа ребер, связывающих 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-я вершина) и вершина, связанная с ней наибольшим числом ребер. В следующем цикле перебора всех вершин единичный сигнал подается в каждом такте уже на три вершины: постоянно на две выбранную в предыдущем цикле и базовую и поочередно на каждую из всех оставшихся. По окончании этого цикла, аналогично предыдущему циклу, выбирается вершина, имеющая максимальное число ребер с двумя вершинами, выбранными в предыдущем цикле. Процесс формирования первого подграфа окончится, когда в него войдет заданное число вершин. Признаком этого будет появление единичного сигнала на выходе регистра сдвига 25, который поступает на регистр сдвига 5 и продвигает единицу на его второй выход, к которому подключен одиннадцатый триггер группы 8 базовой вершины второго подграфа. Сигнал с выхода регистра 25 поступает через элемент 30 задержки и элемент ИЛИ 31 на входы элементов И группы 32, через элемент ИЛИ 13 (обнуляет) устанавливает в исходное состояние буферный регистр 19, поступает на вход "Вычитание" ("В") блока 34 сложения-вычитания, в котором хранится код суммарного числа связей исходного графа. Из этого кода вычитается код числа связей, соединяющих вершины, выбранные (включенные) в первый подграф. Элемент 30 задержки необходим для того, чтобы успеть произвести описанную выше операцию вычитания прежде, чем произойдет сброс сигналов с входом блока 4, соответствующих вершинам, включенным в первый подграф. При поступлении сигналов на входы элементов И группы 32, на первые входы которых поданы единичные сигналы с триггеров 8, соответствующих вершинам, отобранным в первый подграф, на выходах соответствующих элементов И группы 32 появляется единичный сигнал, который перебрасывает соответствующие триггеры группы 11. Поэтому закрываются соответствующие им элементы И группы 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, обеспечивает выбор новой ветви разбиения графа на подграфы с тем, чтобы процесс разбиения на втором цикле разбиения не пошел по уже проделанному пути. Это достигается путем блокировки вершины, которая была выбрана в первом варианте разбиения в качестве вершины, имеющей максимальное число связей с базовой для каждого из подграфов. Это значит, что в начале формирования каждого из подграфов графа в качестве первой вершины, присоединяемой к базовой, будет выбрана другая вершина, имеющая с базовой максимальное число связей, за исключением вершины, которая была выбрана в первом варианте разбиения как максимально связанная, но которая в начале формирования второго варианта заблокирована. По окончании формирования первого варианта разбиения сигнал с элемента И 35 прежде, чем поступать на вход элемента ИЛИ 46 и привести все устройство в исходное состояние перед началом формирования второго варианта разбиения, поступает на вход регистра 4 сдвига и продвигает единицу на его первый выход (верхний по схеме), взводит триггер 27 и через элемент 45 задержки поступает на регистр 40 сдвига, по которому происходит перезапись информации из регистра 41 в регистр 40, но уже в инверсном коде. В регистре 41 по-прежнему остается код 100.0, а в регистре 40 будет код 00.01, который определяет время блокировки перезаписи информации из буферного регистра 21 в триггеры группы 8, так как эта блокировка обеспечивается отсутствием сигнала на входе элемента И 24 через последовательно соединенные триггер 27, элемент 28 задержки и элемент НЕ 29. Сигнал с элемента И 35 через элемент 47 задержки поступает на вход элемента ИЛИ 46, который приводит в исходное состояние регистр 5 сдвига (как описано ранее, записывается код 100.00), сбрасывает триггеры группы 8, через элементы ИЛИ группы 48 сбрасывает триггеры группы 11 и через элемент ИЛИ 49 обнуляет регистры сдвига 2 и 22 и буферный регистр 19. Устройство приведено в исходное состояние и готово к формированию очередного варианта разбиения Второй вариант разбиения начинается по очередному импульсу генератора 1 с выбора вершины, максимально связанной с базовой вершиной первого подграфа. В качестве этой вершины будет выбрана та же вершина, что и в первом разбиении (признак окончания выбора этой вершины сигнал с выхода переполнения регистра сдвига 2), однако, она не будет включена в первый подграф (не будет взведен соответствующий триггер группы 8), так как элемент И 24 по одному из входов будет заблокирован инверсным сигналом с нулевого выхода триггера 27. По этому же сигналу с регистра 2 сдвига продвигается единица на выход переполнения регистра 40 сдвига, в результате чего перебросится триггер 27 и разблокирует элемент И 24, т.е. после выбора следующей вершины (появления импульса на выходе регистра 2 сдвига) она будет включена в подграф. Во время выбора этой вершины выбранная вершина на предыдущем шаге, как максимальным числом связанная с базовой, должна быть заблокирована на входе блока 4, т.е. не должна участвовать в переборе вершин при поиске максимально связанной с базовой во втором варианте разбиения, для того, чтобы она вновь не была выбрана в подграф и процесс разбиения не пошел бы по той же ветви, что и при первом разбиении, т.е. чтобы не повторилось первое разбиение. Блокировка этой вершины осуществляется следующим образом. Перед началом поиска второго варианта разбиения будет включена (взведен триггер 27) только блокировка включения в подграф максимально связанной вершины с базовой, но в переборе она будет принимать участие. Это необходимо для того, чтобы определить, какую именно вершину нужно исключить (заблокировать) из процесса просмотра. Поэтому номер этой вершины будет находиться в буферном регистре 21, а ее код будет подан на входы соответствующих элементов И группы 42, на другие входы которых подается сигнал с триггера 27. Поэтому после окончания первого просмотра по сигналу с выхода переполнения регистра 2 сдвига происходит установка соответствующего триггера в нулевое состояние, таким образом эта вершина не участвует в процессе перебора вершин на втором шаге второго варианта разбиения. После окончания этого шага в буферный регистр 21 записывается код вершины, максимальным числом связей соединенной с базовой, за исключением заблокированной. Однако, код этой вершины не проходит через группу 42 элементов И, так как уже продвинута "единица" на выход переполнения регистра 40 сдвига и, перебросив триггер в нулевое состояние, разблокирует цепь перезаписи в триггеры группы 8 и не дает заблокировать эту вершину на следующий шаг выбора следующей вершины. Поэтому на выходе элемента И 24 появится сигнал, который взводит все триггеры группы 13, разблокировав тем самым заблокированную вершину. Кроме того, по появлении хотя бы одного импульса на выходах элементов И группы 42 сигналом с выхода элемента ИЛИ 44 происходит обнуление буферного регистра 19, для того, чтобы на втором шаге второго варианта разбиения сравнение происходило с кодом 00.0, а не с кодом числа связей заблокированной вершины. В результате получают новый вариант разбиения графа на подграфы, лучший из которых запоминается в регистрах группы 39. По окончании формирования второго варианта разбиения в регистр 41 сдвига будет записана и сдвинута еще одна единица. Инверсный код регистра 41 переписывается в регистр 40 и определяет время блокировки включения вершины в подграф (взведение одного из триггеров группы 8), а также число вершин, которое необходимо блокировать на входе блока 4 (исключить их из просмотра). Таким образом осуществляется выбор новой ветви разбиения и каждое последующее разбиение никогда не повторяет предыдущее, а выбор из них лучшего варианта разбиения по критерию минимума суммарного числа связей между подграфами графа осуществляется по описанному выше принципу схемой сравнения 36. Описанная выше процедура формирования очередного варианта разбиения графа на подграфы и выбор среди них наилучшего будет продолжаться до тех пор, пока на выходе переполнения регистра 50 сдвига не появится сигнал. Число вариантов разбиения определяется содержимым регистра 50. Единичный сигнал с выхода переполнения регистра 50 поступает на триггер 51 установки режима и перебрасывает его из состояния "Транзит" (сигнал "1" на выходе "Т") в состояние "Переключение" (сигнал "1" на выходе "П"). Сигналы "Т" и "П" автоматически переключают устройство в режиме размещения элементов на плоскости последовательно для каждой из частей схемы (каждого подграфа). Нулевой сигнал с выхода "Т" триггера 51 заблокирует пути прохождения сигналов через элемент И 52, элементы И группы 15 управляемого коммутатора 16, элементы И группы 53. Этот же сигнал, поступив на вход элементов И 54 и 55, обеспечит блокировку прохождения сигналов через группу 12 элементов И на входы блока 4. Единичный сигнал с выхода "П" триггера 51 обеспечивает разрешение прохождения сигналов через элементы И группы 71 коммутатора 16 с выходов блока 4 на элемент ИЛИ 57. Аналогично осуществляется коммутация выходов регистров 2 и 22 с входами блока 4 через элементы ИЛИ группы 14 при помощи соответственно коммутаторов 3 и 23, на входы "П" которых поданы единичные сигналы. Кроме того, по единичному сигналу с регистра 50, прошедшему через элементы ИЛИ 46 и 49, осуществляется сброс регистров 2 и 22 и запись единицы соответственно в нулевой и первый разряды, блок 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, а соответствующая перестановка переписывается из блока 58 в регистры 79. Запоминание лучшего варианта размещения в регистрах группы 79 осуществляется следующим образом. В момент времени, когда единичный сигнал имеется на последнем (нижнем) выходе регистра 2 сдвига, он имеется и на втором выходе блока 58. Поэтому будет открыт соответствующий элемент И группы 80 (четвертый элемент И группы 80), к которому подключен второй регистр группы 62, и код 010 этого регистра через первый элемент ИЛИ группы 81 переписывается в первый регистр группы 38. В момент времени, когда единичный сигнал будет на втором выходе регистра 2 сдвига, он будет и на третьем выходе блока 56. Поэтому код третьего регистра группы 62 через открытый элемент И группы 80 и второй элемент ИЛИ группы 81 перепишется во второй регистр группы 38. Аналогичным образом код первого регистра группы 62 через открытый третий элемент И группы 80 и третий элемент ИЛИ группы 81 запишется в третий регистр группы 38. В момент же поступления сигнала со схемы сравнения 78 на регистры группы 79 произойдет, как было описано выше, перепись информации из регистров группы 38 в регистры группы 79. После этого начинается процесс формирования нового размещения и анализ суммарной длины связей между вершинами. Если новое размещение будет иметь меньшую суммарную длину связей, то этот вариант размещения запомнится в регистрах группы 79. После перебора всех перестановок и их анализа на выходе окончания формирования перестановок блока 58 появится единичный сигнал, являющийся признаком окончания оптимального размещения элементов первой группы вершин (первого подграфа) на плоскости. Этот же сигнал приведет в исходное состояние регистры 2 и 22 (т.е. записываются единичные значения соответственно в нулевой и первый разряды), блок 58 устанавливается в состояние, соответствующее первой перестановке, в регистры группы 62 записываются двоичные коды номеров позиций, триггер 70 устанавливается в единичное состояние, буферный регистр 77 и регистры групп 38 и 79. Этот же сигнал осуществляет вывод результатов очередного размещения на индикацию в блок 82 и, продвинув в регистре 83 сдвига единицу на следующий выход, разрешит передачу информации с очередного регистра группы 39 через элемент ИЛИ группы 67 на элементы И группы 66, тем самым, подав информацию об элементах, включенных во вторую группу (вершинах, вошедших во второй подграф), и процедура оптимального размещения повторится аналогично описанному выше. Признаком окончания оптимального размещения элементов последней группы (последнего подграфа), на которые разбит исходный граф и, следовательно, окончания работы устройства, является единичный сигнал на выходе переполнения регистра 83 сдвига.
Формула изобретения
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ, содержащее генератор тактовых импульсов, блок памяти топологии графа, три группы регистров, первый коммутатор, элементы И, группы элементов И, элементы задержки, группы элементов ИЛИ, первый буферный регистр, два регистра сдвига, блок формирования перестановок, первый триггер, вычитатель, сумматор, первую схему сравнения, элемент ЗАПРЕТ, причем информационные входы устройства соединены с установочными входами блока памяти топологии графа, выход генератора тактовых импульсов соединен с входом управления сдвигом первого регистра сдвига, выход элемента ЗАПРЕТ соединен с синхронизирующим входом блока формирования перестановок, информационные выходы блока формирования перестановок соединены с информационными входами первой группы первого коммутатора, информационные входы второй группы первого коммутатора подключены к выходам регистров первой группы соответственно, выход первой схемы сравнения подключен к входам записи регистров второй группы и первого буферного регистра, информационный вход которого и первый информационный вход первой схемы сравнения соединены с выходом сумматора, второй информационный вход первой схемы сравнения соединен с выходом первого буферного регистра, информационные выходы первого регистра сдвига соединены с информационными входами второго коммутатора, выход первого элемента И подключен к синхронизирующему входу вычитателя, а первый вход соединен с выходом первого элемента ИЛИ, выход переполнения первого регистра сдвига подключен к информационному входу второго регистра сдвига, единичный вход первого триггера соединен с выходом второго элемента ИЛИ, а нулевой вход через первый элемент задержки соединен с выходом третьего элемента ИЛИ, единичный выход первого триггера подключен к первому управляющему входу первого коммутатора, нулевой выход первого триггера соединен с вторым управляющим входом первого коммутатора и с вторым входом первого элемента И, входы уменьшаемого и вычитаемого вычитателя соединены с выходами первого коммутатора соответственно, выход вычитателя подключен к информационному входу сумматора, отличающееся тем, что, с целью повышения быстродействия, в него введены два коммутатора, узел коммутации, группы элементов ИЛИ, группы триггеров, группы элементов И, элементы ИЛИ, регистры сдвига, группа регистров, схемы сравнения, буферные регистры, элементы И, элементы задержки, триггеры, группы дифференцирующих элементов, блок сложения-вычитания, элемент НЕ и шифратор, причем выход генераторов тактовых импульсов соединен с первыми входами второго и третьего элементов И, вторые входы второго и третьего элементов И соединены с единичным выходом второго триггера, с первыми управляющими входами второго, третьего и четвертого коммутаторов и с первыми входами четвертого и пятого элементов И, выход третьего элемента И соединен с прямым входом элемента ЗАПРЕТ и через второй элемент задержки с синхронизирующим входом сумматора, нулевой выход второго триггера соединен с вторыми управляющими входами второго, третьего и четвертого коммутаторов, с вторым входом второго элемента И, с первыми входами шестого и седьмого элементов И и с первыми входами элементов И первой группы, выход второго элемента И соединен с первым входом четвертого элемента ИЛИ, второй вход которого соединен с выходом пятого элемента И и с первым входом второго элемента ИЛИ, второй вход второго элемента ИЛИ, первый вход пятого элемента ИЛИ, входы установки исходного состояния блока формирования перестановок, входы регистров первой группы, управляющий вход первого буферного регистра и вход управления сдвигом третьего регистра сдвига соединены с выходом переполнения блока формирования перестановок, выходы регистров второй группы являются информационным выходом устройства, разрешающие входы регистров третьей группы соединены с выходами третьего регистра сдвига соответственно, выходы регистров третьей группы соединены с входами элементов ИЛИ первой группы соответственно, выходы элементов ИЛИ первой группы соединены с первыми входами элементов И второй группы соответственно, второй вход каждого из которых соединен с соответствующим информационным выходом первой группы второго коммутатора, третий вход каждого элемента И второй группы соединен с соответствующим выходом первой группы третьего коммутатора, первый информационный вход которого соединен с выходом четвертого регистра сдвига, выход переполнения первого регистра сдвига соединен с первым входом восьмого элемента И, с вторыми входами пятого и шестого элементов И, выход четвертого элемента ИЛИ соединен с входом управления сдвигом четвертого регистра сдвига, выход переполнения которого соединен с вторым входом четвертого элемента И, выходы второй группы третьего коммутатора соединены с информационными входами второго буферного регистра, выходы разрядов второго буферного регистра соединены с первыми входами элементов И третьей группы и с первыми входами элементов И четвертой группы, вход записи второго буферного регистра соединен с выходом второй схемы сравнения и с первыми входами элементов И пятой группы, вторые входы элементов И третьей группы соединены с выходом восьмого элемента И и с вторым входом седьмого элемента И, выход которого соединен с единичными входами триггеров первой группы, нулевые входы которых соединены с выходами элементов И четвертой группы и с входами дифференцирующих элементов первой группы, нулевые выходы триггеров первой группы соединены с первыми входами элементов И шестой группы, выходы которых соединены с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с входом установки исходного состояния устройства, соединенного с первым входом шестого элемента ИЛИ, с нулевым входом второго триггера, с установочным входом пятого регистра сдвига, а через второй элемент задержки с установочным входом третьего буферного регистра и с входом управления сложением блока сложения-вычитания, выходы разрядов шестого регистра сдвига через узел коммутации соединены с первыми входами элементов ИЛИ третьей группы, вторые входы которых соединены с выходами элементов И третьей группы, выходы элементов ИЛИ третьей группы соединены с единичными входами триггеров второй группы и с вторыми входами элементов И первой группы, выходы элементов И первой группы соединены с первыми входами элементов ИЛИ четвертой группы, выход шестого элемента ИЛИ соединен с нулевыми входами триггеров второй группы, с вторым входом пятого элемента ИЛИ, с первыми входами элементов ИЛИ пятой группы и с установочными входами шестого и седьмого регистров сдвига, выход переполнения шестого регистра сдвига соединен с информационным входом седьмого регистра сдвига, выход переполнения которого соединен с единичным входом второго триггера и с вторым входом шестого элемента ИЛИ, третий вход которого через третий элемент задержки соединен с выходом девятого элемента И, выход девятого элемента И соединен с управляющим входом третьей схемы сравнения, с нулевым входом третьего триггера, с входом управления сдвигом пятого регистра сдвига и через четвертый элемент задержки с установочным входом второго регистра сдвига, входы рязрадов которого соединены с выходами разрядов пятого регистра сдвига, а выход переполнения подключен к единичному входу третьего триггера, нулевой выход которого соединен с вторыми входами элементов И четвертой группы, а через последовательно соединенные пятый элемент задержки и элемент НЕ - с вторым входом восьмого элемента И, выход шестого элемента И соединен с третьими входами элементов И четвертой группы, выходы дифференцирующих элементов первой группы соединены с входами седьмого элемента ИЛИ, выход которого соединен с первым входом восьмого элемента ИЛИ, второй вход которого и установочные входы первого, четвертого и восьмого регистров сдвига соединены с выходом пятого элемента ИЛИ, выход восьмого элемента ИЛИ соединен с установочным входом четвертого буферного регистра, входы разрядов которого соединены с выходами элементов И пятой группы, выход четвертого буферного регистра соединен с первым информационным входом второй схемы сравнения, выход шифратора соединен с вторым информационным входом второй схемы сравнения, с вторыми входами элементов И пятой группы и с информационным входом блока сложения-вычитания, вход управления вычитанием которого соединен с выходом переполнения восьмого регистра сдвига, с входом шестого элемента задержки, с третьим входом восьмого элемента ИЛИ и с входом управления сдвигом шестого регистра сдвига, выход блока сложения-вычитания соединен с информационным входом третьего буферного регистра и с первым информационным входом третьей схемы сравнения, второй информационный вход которой соединен с информационным выходом третьего буферного регистра, а выход соединен с управляющим входом третьего буферного регистра и с управляющими входами регистров третьей группы, единичные выходы триггеров второй группы соединены с вторыми входами соответствующих элементов ИЛИ пятой группы, с первыми входами соответствующих элементов ИЛИ шестой группы, с первыми входами элементов И седьмой группы и с входами девятого элемента И соответственно, вторые входы элементов ИЛИ шестой группы соединены с информационными выходами второй группы второго коммутатора, вторые входы элементов И седьмой группы соединены с выходом девятого элемента ИЛИ, первый вход которого соединен с выходом шестого элемента задержки, второй вход соединен с входом установки исходного состояния устройства, выходы элементов И седьмой группы соединены с единичными входами соответствующих триггеров третьей группы, нулевой вход каждого из которых соединен с выходом соответствующего элемента ИЛИ пятой группы, нулевые выходы триггеров третьей группы соединены с первыми входами соответствующих элементов И восьмой группы, второй вход каждого из которых соединен с выходом соответствующего элемента ИЛИ шестой группы, выход каждого элемента И восьмой группы соединен с вторым входом соответствующего элемента И шестой группы, выходы блока памяти топологии графа соединены с информационными входами четвертого коммутатора, первый информационный выход которого соединен с информационным входом шифратора, второй информационный выход подключен к входам первого элемента ИЛИ, выход четвертого элемента И соединен с управляющим входом блока формирования перестановок, с инверсным входом элемента ЗАПРЕТ и с разрешающим входом первой схемы сравнения, информационные выходы блока формирования перестановок соединены с первыми входами элементов И девятой группы, вторые входы которых соединены с выходами соответствующих регистров первой группы, выход каждого элемента И девятой группы соединен с входами соответствующих элементов ИЛИ четвертой группы, выходы которых соединены с информационными входами соответствующих регистров второй и четвертой групп, выход каждого элемента И второй группы через дифференцирующий элемент второй группы соединен с соответствующим входом третьего элемента ИЛИ, информационные входы блока памяти топологии графа соединены с выходами элементов ИЛИ второй группы, входы записи регистров четвертой группы соединены с выходами первой группы третьего коммутатора, а выходы подключены к информационным входам регистров третьей группы, третьи входы элементов И девятой группы соединены с соответствующими информационными выходами первой группы второго коммутатора.РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5
