Элемент однородной среды

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советски кСоциапистичесиикРесттубпии пи 978139(22) Заявлено 31.10. 80 (21). 2998967/18-24 с присоединением заявки6 06 Г 7/00 Рюудерстеанаыб кемнтет СССР аф делам наебретеннй н отерытнйДата опубликования описания 30. 11.82 Л.С. Берштейн, А.А. Михайлова, А.И, Ндточтй и В.А. Сапрыкин(72) Авторы изобретения Таганрогский радиотехнический институт .им; 8,Д.КалмыковаФ(54) фЛЕИЕНТ ОДНОРОДНОЙ СРЕДЫ 1Изобретение относится к вычислительной технике и предназначено для моделирования комбинаторных задач ттроектирования радиоэлектронной аппаратуры и АСУ. По основному авт, св, к 646328 известно устройство, содержащее блок обработки входных сигналов, триггер записи трасс, блок запоминания признака конечной точки и блок выходной логики, первые четыре входа которого соединены с выходами блока обработки входных сигналов, пятый - с выходом .триггера записи трасс, первый и второй входы которого соединены соот" ветственно с первым и вторым входами элемента, первый и второй входы блока запоминания признака конечной точки, подключены соответственно к второму и третьему входам элемента, а выходы - к первому и второму выходам элемента, первый вход блока обра" ботки входных сигналов подключен к. Управляющему входу элемента, входы с второго по пятый - к информационным входам элемента, шестой - к выходу триггера записи трасс, а выходы блока выходной логики подключены к 5информационным выходам элемента 113. Недостатком известного устройстваявляется то, что оно решает лишь 1 Оодну из комбинаторных задач проектиФрования радиоэлектронных схем - задачу построения связывающих сетей, являющейся, в частности одной из основных задач проектирования печатныхплат. Вместе с тем, при проектировании радиоэлектронной аппаратуры важное значение имеют такие комбинаторные задачи, как покрытие элементовсхемы заданным набором микросхем, 2 о распределение микросхем по платам иразмещение микросхем на платах. Следует заметить, что математические модели перечисленных комбинаторных задач широко используются также при19 97813 блока вторые входы элементов И-НЕ подключены к управляющему входу бло" ка, первый дополнительный вход блока подключей к третьим входам первого и второго элементов И-НЕ, второй дополнительный вход блока подключен к четвертому входу первого и к третьему входу третьего элементов И-НЕ, треий дополнительный вход подключен к четвертому входу второго и к треть- ф ему входу четвертого элементов И-НЕ.3. Устройство по и. 1, о т л иц а ю щ е е с .я тем, что блок запоминания признака конечной точки содержит триггер и элементы И-НЕ, причем 1 ф первые единичный и нулевой входы триггера подключены к управляющим вхо" дам блока соответственно, вторые еди 9 20ничный и нулевой входы триггера подключены к дополнительным управляющимвходам блока, выход триггера подключен к первым входам элементов И-НЕи к первому дополнительному выходублока, второй дополнительный выходкоторого подключен к выходу первогоэлемента И-НЕ, к первому выходу блока и к второму входу второго элементаИ"НЕ, выход которого подключен квторому выходу блока, дополнительныйуправляющий вход которого подключенк второму входу первого элемента И-НЕ.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССРУ 61632 В, кл. 6 06 Г 7/00, 1979978139 оставитель В, Кайданехред И,Коштура Редактор О. Сере рректор НКор ака д Ч 5 лиал ППП "Патент", г, Ужгород, ул,Тираж 731 Подписно ВНИИПИ Государственного комитета ССС по,делам изобретений и открытий 13035, Иосква, Ж, Рауаская наб.,3 97813 решении оптимизационных задач ЛСУ, сетей связи, социологических сетей, планирования научных исследований и ряде других областей. Основной процедурой решения указанных комбинатор- Б ных задач является процедура преобра- зования модели проектируемого объекта. Ряд изоморфных моделей порождает ряд решений задач, из которых по заданным критериям выбираетсяоптимальное. Та- О ким образом, введя режим изоморфных преобразований, можно расширить функциональные возможности устройства.Цель изобретения - расширение области применения за счет реализации изоморфных преобразований. Поставленная цель достигается тем, что элемент однородной среды дополнительно содержит блок передачи информации, информационные входы которого20 подключены к информационным входам элемента, управляющие входы подключены к входам импульсов запуска элемента, обмена информацией по строкам, обмена информацией по столбцам переключения режимов, записи информации элемента, к выходу триггера и выходу блока запоминания признака конечной точки соответственно, а выходы под 30 ключены к трем дополнительным входам блока выходной логики элементу, к дополнительным входам установки триггера в единичное и нулевое состояния блока запоминания признака конечной точки элемента, к дополнительному вхо З ду установки в единичное состояние триггера записи трасс элемента и к дополнительному управляющему входу блока запоминания признака конечной точки элемента соответственно, при этом блок передачи информации содержит дешифратор, триггер, элементы И, ИЛИ, И-НЕ и И-ИЛИ, причем информационные входы блока подключены к входам элементов И-НЕ, первый управляю- ф щий вход блока подключен к первым входам элементов И и к первому единичному и нулевому входам триггера, выход первого элемента И подключен к первому входу элемента ИЛИ, второй 50 и третий управляющие входы блока подключены к входам дешифратора, четвертый управляющий вход блока подключен к вторым входам второго и третьего элементов И, к первым входам первого Я и второго элементов И ИЛИ и к первому выходу блока, пятый управляющий вход блока подключен к второму входу перво 9 фго элемента И, шестой управляющий вход блока подключен к вторым входам .первого и второго элементов И-ИЛИ, седьмой управляющий вход блока подключен к второму входу элемента ИЛИ, выходы первого и второго элементов И-ИЛИ подключены к второму и третьему выходам блока соответственно, выходы второго и третьего элементов И подключены к четвертому и пятому выходам блока соответственно, выход элемента ИЛИ подключен к третьим входам первого и второго элементов И-ИЛИ и к шестому выходу блока, выходы дешифратора подключены к четвертым входам первого и второго элементов И-ИЛИ, к пятому входу второго и к первому входу третьего элементов И-ИЛИ, к пятому входу первого и к второму входу третьего элементов И-ИЛИ соответственно, выход первого элемента И-НЕ подключен к третьему входу элемента ИЛИ, к шестому входу первого и к третьему входу третьего элементов И-ИЛИ, выход второго элемента И-НЕ подключен к четвертому входу элемента ИЛИ, к шестому входу второго .и к четвертому входу третьего элементов И-ИЛИ, выход которого подключен к вторым единичному и нулевому входам триггера, единичный и нулевой выходы которого подключены к третьим входам второго и третьего элементов И соответственно.Кроме того, блок выходной логики содержит элементы И-НЕ, причем первые входы элементов И-НЕ подключены к информационным входам блока, вторые входы элементов И-НЕ подключены к управляющему входу блока, первый дополнительный вход блока подключен к третьим входам первого и второго элементов И-НЕ, второй дополнительный вход блока подключен к четвертому входу первого и к третьему входу третьего элементов И-НЕ, третий дополнительный вход подключен к четвер- тому входу второго и к третьему входу четвертого элементов И-НЕ. Кроме того, блок запоминания признака конечной точки содержит триггер и элементы И-НЕ, причем, первые единичный и нулевой входы триггера. подключены к управляющим входам блока соответственно, вторые единичный и нулевой входы триггера подключены к дополнительным управляющим входам блока, выход триггера подключен к5 9781 первым входам элементов,И-НЕ и к первому дополнительному выходу блока, второй дополнительный выход которого . подключен к выходу первого элемента И-НЕ, к первому выходу блока и к вто- ю рому входу второго элемента И-НЕ, выход которого подключен к второму выходу блока, дополнительный управляющий вход которого подключен к второму входу первого элемента И-НЕ. 1 оЭто позволяет реализовать в функцию изоморфного преобразования модели объекта проектирования.На чертеже приведена функциональная схема предлагаемого элемента од нородной среды для моделирования комбинаторных задач проектиррвания.Элемент содержит блок 1 обработки входных сигналов, блок 2 запоминания признака конечной точки, блок 3 выход-го ной логики, триггер 4 записи трасс, блок 5 передачи инФормации, управляющий вход 6, информационные входы 7-10, выходные элементы И-НЕ .11-14 блока 3 выходной логики, подключенные своими 25 выходами к информационным выходам 15- 18 элемента, выходы 19 и 20 элемента и входы 21-27 элемента, Блок 2 запоминания признака конечной точки содержит триггер 28 и элементы И-НЕ 29 Зо и 30, В нем хранится информация о элементе моделируемой матрицы и осуществляется связь с устройством управления средой. Блок 5 передачи информации осуществляет связь соответ- у ствующих и нформационных выходов с инФормационными входами и триггером 28 блока 2 запоминания признака конечной точки в зависимости от сигналов управления и содержит элементы И 3 Т, 40 И-НЕ 32 и 33, ИЛИ 34, дешифратор 35, триггер 36 промежуточной записи, элементы И-ИЛИ 37-39, элементы И 40 и 41, Блок 1 обработки входных сигналов служит дпя приема информационных сиг- п налов, выбора одного из направлений приема информационного сигнала, запоминания выбранного направления приема и передачи информационного сигнала в зависимости от управляющего сиг- о нала на определенные выходы блока, Блок 3 выходной логики служит для формирования выходного информационного сигнала. ходной логики. Входы триггера 28 блока 2 запоминания признака конечной точки соединены с входами 21 и 23 элемента и с выходами элементов И 40 и 41 блока 5, Выход триггера 28 соединен с входами элементов И-НЕ 29 и 30, а также с входами элемен.ов И-ИЛИ 37 и И-ИЛИ 38 блока 5. Входы элемента И-НЕ 29 блока 2 соединены с выходами элемента ИЛИ 34 блока 5, с выходом триггера 28, а выход элемента И-НЕ 29 соединен с выходом 19 элемента и с инверсным входом элемента ИЛИ 34 блока 5. Входы элемента И-НЕ 30 блока 2 соединены с выходом триггера 28, .с выходом элемента И-НЕ 29, а. выход элемента И-НЕ 30 соединен с выходом 20 элемента. Входы элемента И-НЕ 11 блока 3 соединены с выходами блока 1, с вхо"дом 25 элемента, с выходом элемента И-ИЛИ 37 блока 5, с выходом триггера 4, а выход элемента И-НЕ 11 соединен с выходом 15 элемента. Входы элемента И-НЕ 12 блока 3 соединены с ,выходами блока 1, с входом 25 эле,мента, с выходом элемента И-ИЛИ 38 В режиме изоморфных преобразований (ИП) на управляющем входе 6 постоянно присутствует единичный потенциал, в режиме трассировки (Т еди" 39 Ь ничный потенциал .подается при распространении волны поиска, а нулевойпри выделении искомой ветви трассы. Информационные входы 7- 10, которыми данный элемент среды присоединяется к информационным выходам соседних элементов. Вход 21 - вход сброса, 22 - вход записи трассы, После окончания трассировки на этот вход подается импульс, который переводит в единичное состояние триггер 4 в элементах среды, принадлежащих построенной трассе, вход 23 является входом записи информации. В режиме ИП через него записывается значение элемента матрицы, а в режиме Т - признак конечной точки, 24 - вход импульсов в режиме Т, в режиме ИП, синхронизирующих момент изменения состояния триггера 28 в конце каждого обмена информацией.Вход 25 - вход переключения режимов Т (единичный сигнал) и ИП (нулевой сигнал). Вход 26 - вход обмена информацией по строкам. Вход 27 обозначает вход обмена информацией по столбцам.Входы блока 1 обработки входных сигналов соединены с входами 6-10 и с выходами триггера 4 записи трассы, а выходы блока 1 соединены с входами элементов И-НЕ 11-14 блока 3 вы"7 9781 блока 5, с выходом триггера 4, а выход элементаИ-НЕ 12 соединен с выходом 16 элемента. Входы элементов И-НЕ 13 блока 3 .соединены с выходами блока 2, с выходом элемента 5 И-ИЛИ 37 блока 5 с выходом триггера 4, а выход элемента И-НЕ 13 соединен с выходом 17 элемента. Входы элемента И-НЕ блока 3 соединены с выходами блока 1, с выходами элемента 10 И"ИЛИ 38 блока 5, с входом триггера 4, а выход элемента И-НЕ 14 соединен с выходом 18 элемента.Входы триггера 4 записи трасс соединены с входами 21 и 22 элемента, 15 с выходом элемента ИЛИ 34 блока 5, а инверсный выход триггера 4 соединен с входами элементов И-НЕ 11 и И-НЕ 14 блока 3.Входы элемента Иблока 5 передаЮ чи информации соединены с входами 23 и 24 элемента, а выход элемента И 31 соединен с входом эпемента ИЛИ 34. Входы элемента И-НЕ 32 блока 5 соединены с входами 8 и 10 эле мента, а выход элемента И-НЕ 32 соединен с входом элемента ИЛИ 34, с входом элемента И-ИЛИ 38, с входом элемента И-ИЛИ 39. Входы элемента И-НЕ 33 блока 5 соединены с входами 30 7 и 9 элемента, а выход элемента И-Ю 33 соединен с входом эле 4 ята ИЛИ 34, с входом элемента И-ИЛИ 37, с входом элемента И-ИЛИ 39.Входы элемента ИЛИ 34 блока 5 сое- э . динены с выходами элементов И 31, И-НЕ 32 и 33 с выходом элемента И-НЕ 29 блока 2, а выход элемента ИЛИ 34 соединен с входами элементов И-ИЛИ 37 и 38, с входом триггера 4, 0 с входом элемента И-НЕ блока 2. Входы дешифратора 35 блока 5 соединены с входами 26 и 27 элемента, а выходы дешифратора 35 соединены с входами элементов И-ИЛИ 37 и 39,Входы триггера 36 блока 5 соединены с выходом элемента И-ИЛИ 39, с входом 24 элемента. Выходы тригге,ра 36 соединены с входами элементов И 40 и 41.Входы элемента И-ИЛИ 37 блока 5 соединены с выходом элемента ИЛИ 34, с выходом дешифратора 35 с выходом триггера 28, с выходом элемента И-ИЛИ 37 соединен с входами элемен"И . тов И-НЕи 13.Входы элемента И"ИЛИ 38 блока 5 соединены с входом 25 элемента, с выходом элемента ИЛИ 34, с выходомэлемента И-НЕ 32 с выходами дешифратора 35, с выходом триггера 28.Выход элемента И-ИЛИ 38 соединен свходами элементов И-НЕ 12 и 14.Входы элемента И-ИЛИ 39 блока 5соединены с выходами элементов И-НЕ 32и 33, с выходами дешифратора 35, авыход элемента И-ИЛИ 39 соединен свходами триггера 36.Входы элемента И 40 блока 5 соединены с входами 24 и 25 элемента, спрямым выходом триггера 36, а выходэлемента И 40 соединен с входом триггера 28,Входы элемента И 41 блока 5 соединены с входами 24 и 25 эл мента,с инверсным выходом триггера 36, авыход элемента И 41 соединен с входом триггера 28.Элемент однородной среды для моделирования комбинаторных задач проектирования работает в двух основныхрежимах, в режиме трассировки (построения кратчайших связывающих сетей)и в режиме изоморфных преооразованиймоделируемого объекта. Задача трассировки заключается в нахождении кратчайшего связывающего пути для некоторого множества точек, раСположенных на плоскости или в пространстве. Применительно к проектированию радиоэлектронной аппаратуры задача трассировки сводится к нахождению кратчайшего пути прохождения печатных проводников конструкторской плоскости платы) в соответствии с заданной таблицей соединений. Конструкторская плоскость представляет собой плоскость нанесенной на нее прямоугольной решеткой с заданным шагом. В общепринятой терминологии каждая элементарная ячейка конструкторской плоскости или решетки называется дискретом. Для решения зада" чи трассировки широко используется волновой алгоритм с различными модификациями, При этом реализуются две основйые модели: конструкторской плоскости, как множества дискретов, и распространение на множестве дискретов числовой волны поиска кратчайших связывающих путей. Распространение волны поиска на множестве дискретов означает следующее. Выбирается один из дискретов, который считается источником. волны. В.ряд других дискретов записываются признаки конечных,9 9781 точек, т.е. тех точек, которые вместе с дискретом - источником должны объединяться связывающей сетью. Дискреты, соседние с дискретом-источником, помечаются меткой, будем называть его возбуждением, которое указывает на дискрет, от которого получено возбуждение. Дискреты, соседние с дискретом-источником, образуют первый фронт волны. Затем возбужденные 1 О дискреты первого фронта становятся дискретами-источниками и процесс повторяется до тех пор, пока в очередной фронт возбуждения не попадет дискрет с признаком конечной точки. 15 На этом распространение волны поиска прекращается, производится считывание найденного пути. Затем все дискреты построенного пути считываются дискретами-источниками и процедура повто ряется до присоединения следующего дискрета с признаком конечной точки. и тд, до тех пор, пока не будут присоединены все дискреты с признаками конечных точек. Затем строятся сле дующие кратчайшие связывающие сети.Элемент однородной перестраиваемой среды является схемным аналогом дискрета. Если элементы однородной среды объединить между собой по типу зо прямоугольной решетки, то получится однородная сеть, которая будет являться схемным аналогом конструкторской плоскости, а передача возбуждения от элемента к элементу однородной среды и запоминание направления прихода возбуждения моделирует волновую процедуру.Второй основной режим работы элемента - изоморфные преобразования моделируемого объекта. Этот режим работы соответствует реализации основной процедуры при решении комбинаторных задач проектирования.Например, при решении задач проектирования радиоэлектронной аппаратуры принципиальная (функциональная) схема представляется в виде матричного эквивалента, При данной нумерации столбцов и строк матрицы можно вычислить значение целевой функции оптимизации. Если поменять местами некоторые строки и столбцы матрицы, то за счет изменений локальных свойств матрицы изменится и значение целе" вой функции оптимизации. Такой обмен приводит к изменение суммарной длины всех цепей и, следо" вательно, к изменению качества реще ния задачи размещения. В табл. 1 приведена матрица исходного размещения элементов с указанием длин каждой це" пи и суммарной длины всех цепей. В табл. 2 приведена матрица, эквивалентная исходной, полученная путем перестановки первого и третьего элементов. Как видно из табл. 2 это привело к увеличению суммарной длины цепей. Лучшее линейное размещение приведено в табл. 3, Для среды, состоя-. щей, из данных элементов, могут быть разработаты специальные алгоритмы,Таким образом, решение (нахождениеэкстремума целевой Функции) сводится 39 1 О к перестановке строк и столбцов матрицы, т.е. к ее изоморфному преобра" зованию с оценкой текущего значения целевой функции. Эта циклическая процедура прерывается в момент получения оптимального значения целевой функции.Рассмотрим реализацию этого режи" ма на примере решения задачи линейного размещения радиоэлектронных элементов. В этом случае элементу однородной среды взаимно-однозначно ставится в сс ответствие элемент матрицы цепей, в которой строки отмечаются элементами схемы,а столбцы - цепями, соединяющими эти элементы. Таким образом, однородная среда, содержащая ив элементов, физически отображает матрицу цепей электрической схемы, содержащей и элементов и в соединяющих их цепей, На пересечении 1-ой строки и 1-го столбца ставится еди" ница, если 1-ый элемент входит в 1-ую цепь, и ноль в противном случае. Длиной-ой цепи называется разность между номерами самой нижней строки, в которой стоит единица в-ом столбце, и номером самой верхней строки, в которой стоит единица в 1-ом столбце (табл. 1). Каждое размещение характеризуется суммой длин входящих в него цепей. Номера столбцов соответствуют порядку размещения элементов в линейке, Обмен информацией, записанной в строках с номерами 1 и(перестановка местами строк 1 и 0 ), соответствует обмену местами к-го и 2 -го элементов размещаемой линейки схемы. В результате обмена получаем матрицу, изоморфную данной, т.е. описывающую исходную электрическую схему при другом порядке нумерации ее элементов.11, 9781 с помощью которых приведенная задача, и ряд других решаются значительно быстрее, чем на универсальных вычислительных .машинах, поскольку обмен информацией между строками осуществляется параллельно но строкам (или ,столбцам). Указанные изоморфные преобразования являются основной процедуррй при решении таких комбинаторнологических задач, как покрытие,. ком в поновка, размещение и т.д,. Однако сами алгоритмы покрытия, компоновки, размещения и составляющие как компоненты, такие как выбор переставляемых строк, подсчет значений целевых 13 функций, сравнение и выбор максимальных значений и т.д., не могут быть реализованы в элементе однород" ной среды. Они реализуются в специальном устройстве, содержащем одно родную среду из предлагаемых элементов и ряд специальных блоков.Таблица 39 12Табли цаНомера эле 5 мента 4 1 1 1 1 1 1 1 1 11 1 11 1 Длинацепи Длина Таким образом, наличие в предлагаемом элементе однородной среды, которая в этом режиме является схемноймоделью матрицы блока передачи информации, который позволяет реализовать режим изоморфных преобразованийматрицы, значительно расширяет функциональные возможности элемента.Элемент работает следующим образом.Режим трассировки,На вход 21 подается единичный импульс сброса. В дальнейшем на этомвходе присутствует нулевой потенциал.На входы 25-27 подается единичный потенциал, Запрещается передача сигнала с выхода триггера 36 промежуточнойзаписи на вход триггера 28. На входыэлементов, подлежащих соединению связывающей сетью, подаются единичныеимпульсы. Этим в соответствующие элементы записываются признак конечнойточки (ПКТ). Ка входе 23 одного изэлементов выбранного в качестве источника, остается единичный потенциал, подготавливающий к открыванию .элемента И 31. На входы 24 всех элементов среды подается единичный импульс, который через элемент И 31возбуждает только элемент-источник.В среде начинает распространятьсяволна возбуждения. Признаком возбуждефф ния элемента является появление навыходе элемента ИЛИ 34 единичногопотенциала. Вначале, на выходе элемента И-НЕ 29, т.е, на выходе 19 Номераэле- мента 1 111 11 1 ДлинацепиОбщаядлина Таблица 2 ю щ жж е Номера цепи Номера эле- мента 1 4 11 1,6Длинацепи9781элемента среды, устанавливается единичный потенциал, а на выходе элемента ИЛИ 34 - нулевой, т.е. на выходах элементов 31-33 сигналы равны О. Запись единицы в триггер 28 не меняет состояния триггера, состоящего из элементов 29 и 34. Указанное состояние меняется при возбуждении заявляемого элемента среды. Если в триггере 28 записана едини О ца, как признак конечной точки трассы, то возбужденное состояние элемента подтверждается через элемент И-НЕ 29.Элементы среды, кроме элемента з источника, возбуждаются только с приходом нулевого сигнала на информационные входы 7-10. В блоке 1 обработки входных сигналов осуществляется запоминание номера направления, по 20 которому приходит первый сигнал возбуждения. Если сигнал вобуждения приходит одновременно на несколько входов, то запоминается произвольный номер одного из возбужденных информа-ционных входов. В режиме распространения волны на управляющий вход 6 всех элементов подается единичный потенциал.При этом выходы блока 1 обработки ЗО входных сигналов разрешают передачу возбуждения через элементы И-НЕ 11-14 на все информационные выходы элемента. С выходов элементов И-ИЛИ 37 и 38 сигнал возбуждения через элементы з И-НЕ 11"14.поступает на информацион" ные выходы 15-18, возбуждая соседние элементы.При достижении волной возбуждения элемента, в триггере 2 о которого за писывается признак конечной точки трассы, на выходе 19 этого элемента появляется нулевой потенциал, а на выходе 20 единичный, которыепоступают на устройство управлений одно- з родной средой. Устройство управления выдает на входы 6 всех элементов среды нулевой потенциал. При этом возбуждение передается только на тот информационный выход элемента, кото- у рый запоминается блоком обработки входных сигналов на этапе распространения волны. Этим достигается выделение искомых участков трассы.Затем элементы, принадлежащие к построенному участку трассы, становятся источниками волны и процесс поиска продолжается аналогично пока 39 14все элементы, в триг ере 28 которыхзаписываются признаки конечных. точек,не присоединяются к одной связывающей сети, Это определяется по наличию единичного потенциала на выходах20 всех элементов среды.,Запоминание трассы 1 и запрет распространения волны возбуждения через,элемент осуществляется подачей импульса на вход 22, который устанавливает триггер 4 записи трассы вединичное состояние. При этом триггер 4 записи трассы устанавливаетсяв единичное положение только в техэлементах, которые принадлежат построенному участку трассы. Выходыназванных триггеров запрещают прохождение сигнала возбуждения на выходы этих элементов. Аналогично строят"ся другие связывающие сети.Режим изоморфных преобразований,На примере перестановки, приведенной в табл. 1 и 2, покажем функцио" нирование введенных элементов. В режиме изоморфных преобразований на ,вход 6 управления подается единичный потенциал, а на вход 25 - нулевой, При этом из четырех разрешенных в режиме трассировки направлений пере" дачи сигнала возбуждения ячейкой разрешается два. В нашем примере разрешенными будем считать направления вдоль строк в строку возрастания номеров столбцов и вдоль столбцов в сторону возрастания номеров строк. Это достигается подачей нулевого потенциала на входы схем И-НЕ 11 и 12. На фиг. 3 приведена схема соединения предлагаемых элементов в однородную среду в режиме изоморфных преобразо" ваний. Цифры внутри элемента обозначают номера входов и выходов, указанных на, функциональной схеме. Кро" ме того, запрещается прохождение сигнала с выхода схемы ИЛИ 34 через элементы И-ИРИ 37 и 38, цто необходимо в режиме трассировки для одновременной передачи сигнала возбуждения по всем направлениям. Значение элементов матрицы записывается через входы 23 в триггер 28 элементов среды. В нашем примере (табл. 1) в первой строке эта запись производится в элементы, находящиеся в 1, 2 и 4-ом столбцах, во 2-ой строке, в 1, 21 5 и 7-ом столбцах и т.д.Далее в нашем примере на вход 26 всех элементов, находящихся а первой8139 16 15 97 и третьей строках, подается единичный потенциал, Сигналами с выхода дешифратора 35 запрещается прохождение сигнала с выхода элемента И-НЕ 32 через элемент И-ИЛИ 38 и с выхода элемента И-НЕ 33 через элемент И-ИЛИ 37. Это необходимо для того, чтобы информационный сигнал не проходил на выход элементов, уцаствующих в обмене информацией, Кроме того разрешается прохождение информации, записываемой в триггере 28, через элементы И-ИЛИ 38 и И-НЕ 14 на выход 18, а также прохождение информации, пришедшей на вход 8 элемента среды, через элементы И"НЕ 32 и И-ИЛИ 39 на входы триггера 36 предварительной записи. Таким образом, информация с выходов триггеров 28 элементов, на ходящихся в первой строке (табл. 1) проходит через элементы, находящиеся во второй строке, записывается в триггер 36 промежуточной записи элементов среды, находящиеся в третьей строке. В тоже время информация с выхода триггера 28 элементов среды, находящихся в третьей строке, беспрепятственно проходит через элементы 4-6 строк и записывается в триггер 3 б промежуточной записи элементов среды, находящихся в первой строке, т,е. при выполнении процедуры изоморфного преобразования в нашем примере выходы элементов среды 6-ой строки соединены с входами элементов среды 1-ой строки, находящихся в одноименных столбцах, а входы 7 элементов среды столбца соединены с входами элементов среды 1-го столбца, находящихся.в одноименных строках.Вход 24 в режиме трассировки выполняет функцию ввода импульсов за. пуска, а в режиме изоморфных преобразований - функцию ввода импульсов записи. С приходом единичного импульса на вход 24 в триггер 28 записывается через элементы И 40 и 41 новое состояние, соответствующее за писанной ранее в триггер 36 промежуточной записи. На этом обмен информацией между строками (перестановка двух строк в матрице) заканчивается. э 1 О 1 го а зо 33 ао 45 Я М При обмене информацией между двумя столбцами единичный потенциал.подается на вход 27. При этом также запрещается прохождение сигнала с выхода элемента ИЛИ 34 через элементы И-ИЛИ 37 и 38. Информационный сигнал приходит на вход 7 и через элементы И-НЕ 33 и И-ИЛИ 39 поступает на входы триггера 36 предварительной записи. С выхода триггера 28 сигнал проходит через элементы И-ИЛИ 37 и И-НЕ 13 и поступает на выход 17. В остальном элементы работают как и при обмене информацией между строками.В режиме изоморфного преобразования информационный сигнал на входы 9 и 10 не поступает,так как разрешены только две из четырех направлений распространения сигнала. Поскольку информационный сигнал не проходит церез элементы, участвующие в обмене, то в среде из предлагаемых элементов можно осуществлять одновременную циклическую перестановку более чем одной строки или столбца, Например, одновременно можно переписать информацию из 1-ой строки по 2-ю, из 2-ой в 3-ю, а из 3-Й в 4-ю. Для этого единичный потенциал необходимо подать на вход 26 элементов, находящихся в 1-3 строке. На входы 26 и 27 элементов среды, не участвующих в обмене информацией (например элементы, находящиеся во 2, 4, 5 и 6 строках) подается нулевой потенциал. Единичный потенциал с выхода дешифратора 35 разрешает прохождение сигнала с выходов элементов И-НЕ 32 и 33 через элементы И-ИЛИ 37 и 38Таким образом, сигналы, пришедшие на вход этих элементов среды, беспрепятственно проходят на выход. Нулевые потенциалы с выходов дешифратора 35 запрещают прохождение на вы" ход среды сигнала с выхода триггера 28, а также прохождение сигнала с входа элемента среды на входы триггера 36 промежуточной записи. Память этих элементов среды не участвует в данном обмене. Поскольку вертикальный и горизонтальный каналы передачи информации черев элементы среды, не участвующие в обмене, не пересекаются, то в среде из данных элементов может быть осуществлен обмен информацией между строками и между столбцами одновременно (обмен строки с столбцами и ,наоборот осуществляться не может). В элементах среды, находящихся на пересечении,обмениваемых строк и столбцов, на всех выходах дешифратора 35 устанавливается нулевой потенциал,17 9781 запрещающий прохождение сигнала через.этот элемент как в горизонтальном, так и в вертикальном направлениях, а также запрещающий участие памяти этих элементов среды в данном з обмене.Предлагаемый элемент однородной среды является основой специального устройства, содержащего однородную среду из элементов. На такой однородной среде эффективно моделируются параллельно по строкам и столбцам изоморфные преобразования матриц, причем выигрыш во времени тем больше, чем больше размерность матриц, так как перестановки строк и столбцов не зависят от их длины, Это позволяет значительно повысить эффективность решения комбинаторно-логических заго дач автоматизации проектирования и АСУ. Однородная среда из предлагаемых элементов может служить основой как самостоятельного специализированного устройства, так и использоваться в виде структурной реализации операто. ров, трассировка и изоморфное преобразование универсальных ЭВМ.30Формула изобретения1. Элемент однородной среды по авт. св. Ю 646328, о т л и ч а ющ и й с я тем, что, с целью расширения области применения за счет реализм зации изоморфных преобразований; он дополнительно содержит блок передачи информации, информационные входы которых подключены к информационным вхо 40дам элемента, управляющие входы подключены к входам импульсов запуска элемента, обмена информацией по строкам, обмена информацией по столбцам переключения режимов, записи инфор 45 мации элемента, к выходу триггера и к выходу блока запоминания признака конечной точки соответственно, а выходы подключены к трем дополнительным входам блока выходной логики элемента, к дополнительным входам установки триггера в единичное и нулевое состояния блока запоминания признака конечной точки элемента, к дополнительному входу установки в единичное состояние триггера записи трасс элемен-тов и к дополнительному управляющему входу блока запоминания признака конечной точки элемента соответственно,18при этом блок переда и информации содержит дешифратор, триггер, элемен" ты И, ИЛИ, И-НЕ и И-ИЛИ, причем информационные входы блока подключены к входам элементов И-НЕ, первый уг.- равляащий вход блока подключен к первым входам элементов И и к первому единичному и нулевому входам триггера, выход первого элемента И подклю" чен к первому входу элемента ИЛИ, второй и третий управляющие входы блока подключены к входам дешифратора, четвертый упрзвляющий вход блока подключен к вторым входам второго и третьего элементов И, к первым входам первого и второго элементов И-ИЛИ и к первому выходу блока, пятый управляющий вход блока подключен к второму входу первого элемента И, шестой управляющий вход блока подключен к вторым входам первого и второго элементов И-ИЛИ, седьмой управляющий вход блока подключен к второму входу элемента ИЛИ, выходы первого и второго элементов И-ИЛИ подключены к второму и третьему выходам блока соответственно, выходы второго и третьего элементов И подключены к четвертому и пятому выходам блока соответственно, выход элемента ИЛИ подключен к третьим входам первого и второго элементов И-ИЛИ и к шестому вы- . ходу блока, выходы дешифратора подключены к четвертым входам первого и второго элементов И-ИЛИ, к пятому входу второго и к первому входу третьего элементов И-ИЛИ, к пятому входу ,первого и к второму входу третьего элементов И-ИЛИ соответственно, выход первого элемента И-НЕ подключен к третьему входу элемента ИЛИ, к шестому входу первого и к третьему входу третьего элементов И-ИЛИ, выход второго элемента И-НЕ подключен к четвертому входу элемента ИЛИ, к шестому входу второго и к четвертому входу третьего элементов И-ИЛИ, выход которого подключен к вторым единичному и нулевому входам триггера, единичный и нулевой выходы которого подключены к третьим входам второго и третьего элементов И соответственно. 2. Устройство по и. 1, о т л и " ч а ю щ е е с я тем, что блок выходной логики содержит элементы И-НЕ, причем первые входы элементов И-НЕ подключены к информационным входам