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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советски к

Социапистичесиик

Рес убп пи 978139 (51)М. Кл. (61) Дополнительное к авт. санд-ву к 646328 (22) Заявлено 31. 10. 80 (21). 2998967/18-24 с присоединением заявки .%

G 06 F 7/00

9юуднрстаанныб камнтет

СССР ао аелам наебретеннй н отнрытнй (23) П риоритет

Опубликовано 30.11 82. Бюллетень № 44 (53) УДК 681..3(088.8) Дата опубликования описания 30. 11.82

Л.С. Берштейн, А.А. Михайлова, А.И. Н дточ 1й и В.А. Сапрыкин (72) Авторы изобретения

Таганрогский радиотехнический институт -им; Ь.Д.:Калмыкова

1 (71) Заявитель (54) фЛЕИЕНТ ОДНОРОДНОЙ СРЕДЫ

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

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

5 информационным выходам элемента С13.

Недостатком известного устройства является то, что оно решает лишь

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

3 97813 решении оптимизационных задач ЛСУ, сетей связи, социологических сетей, планирования научных исследований и ряде других областей. Основной процедурой решения указанных комбинаторных задач является процедура преобра- зования модели проектируемого объекта.

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

Цель изобретения - расширение области применения за счет реализации изоморфных преобразований.

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

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

И-ИЛИ подключены к второму и третьему выходам блока соответственно, выходы второго и третьего элементов И подключены к четвертому и пятому выходам блока соответственно, выход элемента ИЛИ подключен к третьим входам первого и второго элементов И-ИЛИ и к шестому выходу блока, выходы дешифратора подключены к четвертым входам первого и второго элементов И-ИЛИ, к пятому входу второго и к первому входу третьего элементов И-ИЛИ, к пятому входу первого и к второму входу третьего элементов И-ИЛИ соответственно, выход первого элемента И-НЕ подключен к третьему входу элемента

ИЛИ, к шестому входу первого и к третьему входу третьего элементов

И-ИЛИ, выход второго элемента И-HE подключен к четвертому входу элемента ИЛИ, к шестому входу второго и к четвертому входу третьего элементов

И-ИЛИ, выход которого подключен к вторым единичному и нулевому входам триггера, единичный и .нулевой выходы которого подключены к третьим входам второго и третьего элементов И соответственно.

Кроме того, блок выходной логики содержит элементы И-НЕ, причем первые входы элементов И"HE подключены к информационным входам блока, вторые входы элементов И-НЕ подключены к управляющему входу блока, первый дополнительный вход блока подключен к третьим входам первого и второго элементов И-НЕ, второй дополнительный вход блока подключен к четвертому входу первого и к третьему входу третьего элементов И-НЕ, третий дополнительный вход подключен к четвер- тому входу второго и к третьему входу четвертого элементов И-НЕ.

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

5 9781 первым входам элементов,И-НЕ и к первому дополнительному выходу блока, второй дополнительный выход которого . подключен к выходу первого элемента

И-НЕ, к первому выходу блока и к вто- рому входу второго элемента И-НЕ, выход которого подключен к второму выходу блока, дополнительный управляющий вход которого подключен к второму входу первого элемента И-НЕ. 10

Это позволяет реализовать в функцию изоморфного преобразования модели объекта проектирования.

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

Элемент содержиt блок 1 обработки входных сигналов, блок 2 запоминания приэнака крнечной точки, блок 3 выход 20 ной логики, триггер 4 записи трасс, блок 5 передачи информации, управляющий вход 6, информационные входы 7-10, выходные элементы И-НЕ 11-l4 блока 3 выходной логики, подключенные своими 25 выходами к информационным выходам 1518 элемента, выходы 19 и 20 элемента и входы 21-27 элемента. Блок 2 запоминания признака конечной точки содержит триггер 28 и элементы И-НЕ 29 30 и 30. В нем хранится информация о элементе моделируемой матрицы и осуществляется связь с устройством управления средой. Блок 5 передачи информации осуществляет связь соответствующих информационных выходов с информационными входами и триггером 28 блока 2 запоминания признака конечной точки в зависимости от сигналов управления и содержит элементы И 3Т, 40

И-HE 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 соединены с входами элементов И-НЕ l 1-14 блока 3 вы"

7 9781 блока 5, с выходом триггера 4, а выход элемента И-НЕ 12 соединен с выходом 16 элемента. Входы элементов

И-HE 13 блока 3 .соединены с выходами блока 2, с выходом элемента S

И-ИЛИ 37 блока 5 с выходом триггера 4, а выход элемента И-НЕ 13 соединен с выходом 17 элемента. Входы элемента И-НЕ блока 3 соединены с выходами блока 1, с выходами элемента

И"ИЛИ 38 блока 5, с входом триггера

4, а выход элемента И-НЕ t4 соединен с выходом 18 элемента.

Входы триггера 4 записи трасс соединены с входами 21 и 22 элемента, с выходом элемента ИЛИ 34 блока 5, а инверсный выход триггера 4 соединен с входами элементов И-НЕ 11 и

И-НЕ 14 блока 3.

Входы элемента И-31 блока 5 переда О чи информации соединены с входами

23 и 24 элемента, а выход элемента

И 31 соединен с входом эпемента

ИЛИ 34. Входы элемента И-НЕ 32 блока 5 соединены с входами 8 и 10 элемента, а выход элемента И-НЕ 32 соединен с входом элемента ИЛИ 34, с входом элемента И-ИЛИ 38, с входом элемента И-ИЛИ 39. Входы элемента

И-НЕ 33 блока 5 соединены с входами Зо

7 и 9 элемента, а выход элемента

И-HE 33 соединен с входом элемента

ИЛИ 34, с входом элемента И-ИЛИ 37, с. входом Элемента И-ИЛИ 39.

Входы элемента ИЛИ 34 блока 5 сое- 3S динены с выходами элементов И 31, И-НЕ 32 и 33 с выходом элемента

И-НЕ 29 блока 2, а выход элемента

ИЛИ 34 соединен с входами элементов

И-ИЛИ 37 и 38, с входом триггера 4, gy с входом элемента И-НЕ блока 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.

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

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

Конструкторская плоскость представляет собой плоскость нанесенной на нее прямоугольной решеткой с заданным шагом. В общепринятой терминологии каждая элементарная ячейка конструкторской плоскости или решетки называется дискретом. Для решения задачи трассировки широко используется волновой алгоритм с различными модификациями. При этом реализуются две основйые модели: конструкторской плоскости, как множества дискретов, и распространение на множестве дискретов числовой волны поиска кратчайших связывающих путей. Распространение волны поиска на множестве дискретов означает следующее. Выбирается один из дискретов, который считается источником. волны. 8-ряд других дискретов записываются признаки конечных.9 9781 точек, т.е. тех точек, которые вместе с дискретом - источником должны объединяться связывающей сетью. Дискреты, соседние с дискретом-источником, помечаются меткой, будем называть его возбуждением, которое указывает на дискрет, от которого получено возбуждение. Дискреты, соседние с дискретом-источником, образуют первый фронт волны. Затем возбужденные 10 дискреты первого фронта становятся дискретами-источниками и процесс повторяется до тех пор, пока в очередной фронт возбуждения не попадет дискрет с признаком конечной точки. 15

На этом распространение волны поиска прекращается, производится считывание найденного пути. Затем все дискреты построенного пути считываются дискретами-источниками и процедура повто- 20 ряется до присоединения следующего дискрета с признаком конечной точки. и т ° д. до тех пор, пока не будут присоединены все дискреты с признаками конечных точек. Затем строятся сле- 25 дующие кратчайшие связывающие сети.

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

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

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

Такой обмен приводит к изменение суммарной длины всех цепей и, следовательно, к изменению качества реше» ния задачи размещения. В табл. 1 приведена матрица исходного размещения элементов с указанием длин каждой цепи и суммарной длины всех цепей. В табл. 2 приведена матрица, эквивалентная исходной, полученная путем перестановки первого и третьего эле ментов. Как видно из табл. 2 это привело к увеличению суммарной длины цепей. Лучшее линейное размещение приведено в табл. 3. Для среды, состоя-щей, из данных элементов, могут быть разработаты специальные алгоритмы, Таким образом, решение (нахождение экстремума целевой Функции) сводится

39 10 к перестановке строк и столбцов матрицы, т.е. к ее изоморфному преобра" зованию с оценкой текущего значения целевой функции. Эта циклическая процедура прерывается в MQMEнт получения оптимального значения целевой функции.

Рассмотрим реализацию этого режи" ма на примере решения задачи линейного размещения радиоэлектронных элементов. В этом случае элементу однородной среды взаимно-однозначно ставится в сс ответствие элемент матрицы цепей, в которой строки отмечаются элементами схемы, а столбцы - цепями, соединяющими эти элементы. Таким образом, однородная среда, содержащая и m элементов, физически отображает матрицу цепей электрической схемы, содержащей и элементов и m соединяющих их цепей. На пересечении i-ой строки и j-го столбца ставится единица, если i-ый элемент входит в j-ую цепь, и ноль в противном случае. Длиной j--ой цепи называется разность между номерами самой нижней строки, в которой стоит единица в j-ом столбце, и номером самой верхней строки, в которой стоит единица в j-ом столбце (табл. 1). Каждое размещение характеризуется суммой длин входящих в него цепей. Номера столбцов соответствуют порядку размещения элементов в линейке. Обмен информацией, записанной в строках с номерами k u F (перестановка местами строк k и Р ), соответствует обмену местами k-co и Я -ro элементов размещаемой линейки схемы.

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

12

Табли ца 3 !

Номера эле$ мента

1 1

1 1

1 1 1 1

1 1 1 1 1

1 1

Длина цепи

Длина

Номера элемента

„3

1 1

1 1 1

Длина цепи

Общая длина

Таблица 2

Номера элемента

1

Длина цепи ,Общая длина

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

Таблица

Номера цепи

1 2 3 4 5 6 7

3 5 2 5 4 3 2

I1 t "Г1Т

4$

3 1 1 1 1

2 1:1 1 1

2 3 4 5 5 5 2

Номера цепи

1 2 3 4 5 6 7

2 3 1 2 3 2

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

Элемент работает следующим образом.

Режим трассировки.

На вход 21 подается единичный импульс сброса. В дальнейшем на этом входе присутствует нулевой потенциал.

На входы 25-27 подается единичный потенциал. Запрещается передача сигнала с выхода триггера 36 промежуточной записи на вход триггера 28. На входы элементов, подлежащих соединению связывающей сетью, подаются единичные импульсы. Этим в соответствующие элементы записываются признак конечной точки (ПКТ). Ка входе 23 одного из элементов выбранного в качестве источника, остается единичный потенциал, подготавливающий к открыванию элемента И 31. На входы 24 всех элементов среды подается единичный импульс, который через элемент И 31 возбуждает только элемент-источник.

В среде начинает распространяться волна возбуждения. Признаком возбуждения элемента является появление на выходе элемента ИЛИ 34 единичного потенциала. Вначале, на выходе элемента И-НЕ 29, т.е. на выходе 19

9781

55

Затем элементы, принадлежащие к построенному участку трассы, становятся источниками волны и процесс поиска продолжается аналогично пока элемента среды, устанавливается единичный потенциал, а на выходе элемента ИЛИ 34 - нулевой, т.е. на выходах элементов 31-33 сигналы равны О. Запись единицы в триггер 28 не меняет состояния триггера, состоящего из элементов 29 и 34. Указанное состояние меняется при возбуждении заявляемого элемента среды.

Если в триггере 28 записана едини- IВ ца, как признак конечной точки трассы, то возбужденное состояние элемента подтверждается через элемент

И-НЕ 29.

Элементы среды, кроме элементаисточника, возбуждаются только с приходом нулевого сигнала на информационные входы 7-10. В блоке 1 обработки входных сигналов осуществляется запоминание номера направления, по 20 которому приходит первый сигнал возбуждения. Если сигнал вобуждения приходит одновременно на несколько входов, то запоминается произвольный номер одного из возбужденных информа- >> ционных входов. В режиме распространения волны на управляющий вход 6 всех элементов подается единичный потенциал.

При этом выходы блока 1 обработки ЗО входных сигналов разрешают передачу возбуждения через элементы И-НЕ 11-14 на все информационные выходы элемента. С выходов элементов И-ИЛИ 37 и 38 сигнал возбуждения через элементы

И-НЕ 11-14.поступает на информационные выходы 15-18, возбуждая соседние элементы.

При достижении волной возбуждения элемента, в триггере 28 которого за- ао писывается признак конечной точки трассы, на выходе 19 этого элемента появляется нулевой потенциал, а на выходе 20 единичный, которые поступают на устройство управления однородной средой. Устройство управления выдает .на входы 6 всех элементов среды нулевой потенциал. При этом возбуждение передается только на тот информационный выход элемента, кото- у рый запоминается блоком обработки входных сигналов на этапе распространения волны. Этим достигается выделение искомых участков трассы.

39 14 все элементы, в триггере 28 которых записываются признаки конечных точек, не присоединяются к одной связывающей сети. Это определяется по наличию единичного потенциала на выходах

20 всех элементов среды..

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

Режим изоморфных преобразований, На примере перестановки, приведенной в табл. 1 и 2, покажем функцио" нирование введенных элементов. В режиме изоморфных преобразований на ,вход 6 управления подается единичный потенциал, а на вход 25 — нулевой.

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

Это достигается подачей нулевого потенциала на входы схем И-НЕ 11 и l2.

На фиг. 3 приведена схема соединения предлагаемых э,ементов в однородную среду в режиме изоморфных преобразо" ваний. Цифры внутри элемента обозначают номера входов и выходов, указанных на. функциональной схеме. Кро" ме того, запрещается прохождение сигнала с выхода схемы ИЛИ 34 через элементы И-ИЛИ 37 и 38, что необходимо в режиме трассировки для одновременной передачи сигнала возбуждения по всем направлениям. Значение элементов матрицы записывается через входы 23 в триггер 28 элементов. среды.

В нашем примере (табл. 1) в первой строке эта запись производится в элементы, находящиеся B 1, 2 и 4-ом столбцах, во 2-ой строке, в 1, 2, 5 и 7-ом столбцах и т.д.

Далее в нашем примере на вход 26 всех элементов, находящихся а первой

8139 16

15 97 и третьей строках, подается единичный потенциал. Сигналами с выхода дешифратора 35 запрещается прохождение сигнала с выхода элемента И-НЕ 32 через элемент И-ИЛИ 38 и с выхода элемента И-НЕ 33 через элемент

И-ИЛИ 37. Это необходимо для того, чтобы информационный сигнал не проходил на выход элементов, участвующих в обмене информацией. Кроме того разрешается прохождение информации, записываемой в триггере 28, через элементы И-ИЛИ 38 и И-НЕ 14 на выход

18, а также прохождение информации, пришедшей на вход 8 элемента среды, через элементы И"НЕ 32 и И-ИЛИ 39 на входы триггера 36 предварительной записи. Таким образом, информация с выходов триггеров 28 элементов, на ходящихся в первой строке (табл. 1) проходит через элементы, находящиеся во второй строке, записывается в триггер 36 промежуточной записи элементов среды, находящиеся в третьей строке. 8 то же время информация с выхода триггера 28 элементов среды, находящихся в третьей строке, беспрепятственно проходит через элементы 4-6 строк и записывается в триггер 36 промежуточной записи элементов среды, находящихся в первой строке, т.е. при выполнении процедуры изоморфного преобразования в нашем примере выходы элементов среды

6-ой строки соединены с входами элементов среды 1-ой строки, находящихся в одноименных столбцах, а входы 7 элементов среды столбца соединены с входами элементов среды 1-го столбца, находящихся.в одноименных строках.

Вход 24 в режиме трассировки выполняет функцию ввода импульсов за. пуска, а в режиме изоморфных преобразований - функцию ввода импульсов записи. С приходом единичного импульса на вход 24 в триггер 28 записывается через элементы И 40 и 41 новое состояние, соответствующее за писанной ранее в триггер 36 промежуточной записи. На этом обмен информацией между строками (перестановка двух строк в матрице) заканчивается.

1О

15 го

Зо

35 ао

5О

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

И-ИЛИ 37 и 38. Информационный сигнал приходит на вход 7 и через элементы

И-НЕ 33 и И-ИЛИ 39 поступает на входы триггера 36 предварительной записи. С выхода триггера 28 сигнал проходит через элементы И-ИЛИ 37 и

И-НЕ 13 и поступает на выход 17. В остальном элементы работают как и при обмене информацией между строками.

В режиме изоморфного преобразования информационный сигнал на входы 9 и 10 не поступает,так как разрешены только две из четырех направлений распространения сигнала. Поскольку информационный сигнал не проходит через элементы, участвующие в обмене, то в среде из предлагаемых элементов можно осуществлять одновременную циклическую перестановку более чем одной строки или столбца. Например, одновременно можно переписать информацию из 1-ой строки по 2-ю, из 2-ой в З-ю, а из 3-й в 4-ю. Для этого единичный потенциал необходимо подать на вход 26 элементов, находящихся s

1-3 строке.

На входы 26 и 27 элементов среды, не участвующих в обмене информацией (например элементы, находящиеся во

2, 4, 5 и 6 строках) подается нулевой потенциал. Единичный потенциал с выхода дешифратора 35 разрешает прохождение сигнала с выходов элементов

И-НЕ 32 и 33 через элементы И-ИЛИ 37 и 38. Таким образом, сигналы, пришедшие на вход этих элементов среды, беспрепятственно проходят на выход.

Нулевые потенциалы с выходов дешифратора 35 запрещают прохождение на вы" ход среды сигнала с выхода триггера

28, а также прохождение сигнала с входа элемента среды на входы триггера

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

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

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

АСУ. Однородная среда из предлагаемых элементов может служить основой как самостоятельного специализированного устройства, так и использоваться в виде структурной реализации операторов, трассировка и изоморфное преобразование универсальных ЭВМ.

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

1. Элемент однородной среды по авт. св. N 646328, о т л и ч а юшийся тем, что, с целью расширения области применения за счет реализм зации изоморфных преобразований. он дополнительно содержит блок передачи информации, информационные входы которых подключены к информационным вхо40 дам элемента, управляющие входы подключены к входам импульсов запуска элемента, обмена информацией по строкам, обмена информацией по столбцам переключения режимов, записи инфор45 мации элемента, к выходу триггера и к выходу блока запоминания признака конечной точки соответственно, а выходы подключены к трем дополнительным входам блока выходной логики элемента, к дополнительным входам установки триггера в единичное и нулевое состояния блока запоминания признака конечной точки элемента, к дополнительному входу установки в единичное состояние триггера записи трасс элемен- тов и к дополнительному управляющему входу блока запоминания признака конечной точки элемента соответственно, i8

39 при этом блок переда и информации содержит дешифратор, триггер, элементы И, ИЛИ, И-НЕ и И-ИЛИ, причем информационные входы блока подключены к входам элементов И-НЕ, первый уг.равляащий вход блока подключен к первым входам элементов И и к первому единичному и нулевому входам триггера, выход первого элемента И подклю" чен к первому входу элемента ИЛИ, второй и третий управляющие входы блока подключены к входам дешифратора, четвертый управляющий вход блока подключен к вторым входам второго и третьего элементов И, к первым входам первого и второго элементов И-ИЛИ и к первому выходу блока, пятый управляющий вход блока подключен к второму входу первого элемента И, шестой управляющий вход блока подключен к вторым входам первого и второго элементов И-ИЛ11, седьмой управляющий вход блока подключен к второму входу элемента ИЛИ, выходы первого и второго элементов И-ИЛИ подключены к второму и третьему выходам блока соответственно, выходы второго и третьего элементов И подключены к четвертому и пятому выходам блока соответственно, выход элемента ИЛИ подключен к третьим входам первого и второго элементов И-ИЛИ и к шестому вы- . ходу блока, выходы деыифратора подключены к четвертым входам первого и второго элементов И-ИЛИ, к пятому входу второго и к первому входу третьего элементов И-ИЛИ, к пятому входу ,первого и к второму входу третьего элементов И-ИЛИ соответственно, вы,ход первого элемента И-НЕ подключен .к третьему входу элемента ИЛИ, к шестому входу первого и к третьему входу третьего элементов И-ИЛИ, выход второго элемента И-HE подключен к четвертому входу элемента ИЛИ, к шестому входу второго и к четвертому входу третьего элементов И-ИЛИ, выход которого подключен к вторым единичному и нулевому входам триггера, единичный и нулевой выходы которого подключены к третьим входам второго

< и третьего элементов И соответственно.

2. Устройство по и. 1, о т л и " ч а ю щ е е с я тем, что блок выходной логики содержит элементы И-НЕ, причем первые входы элементов И-НЕ подключены к информационным входам

19 97813 блока вторые входы элементов И-НЕ подключены к управляющему входу блока, первый дополнительный вход блока подключей к третьим входам первого и второго элементов И-НЕ, второй до- 5 полнительный вход блока подключен к четвертому входу первого и к третьему входу третьего элементов И-НЕ, тре ий дополнительный вход подключен к четвертому входу второго и к треть- <4 ему входу четвертого элементов И-HE.

3. Устройство по и. 1, о т л ич а ю щ е е с .я тем, что блок запоминания признака конечной точки содержит триггер и элементы И-НЕ, причем первые единичный и нулевой входы триггера подключены к управляющим входам блока соответственно, вторые еди9 20 ничный и нулевой входы триггера подключены к дополнительным управляющим входам блока, выход триггера подключен к первым входам элементов И-HE и к первому дополнительному выходу блока, второй дополнительный выход которого подключен к выходу первого элемента И-НЕ, к первому выходу блока и к второму входу второго элемента И-НЕ, выход которого подключен к второму выходу блока, дополнительный управляющий вход которого подключен к второму входу первого элемента И-HE.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

N 646328, кл. G 06 F 7/00, 1979 (прототип).

978139 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по.делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 9786

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель В. Кайданов

Редактор О. Середа Техред И.Коштура Корректор Н. Король