Устройство для решения комбинаторно-логических задач при проектировании печатных плат Советский патент 1983 года по МПК G06F17/16 

первой матрицы, где ma(J-fs), li(s-lHn- j) j 4 l + s.(n-1)-1 , (x)остаток от деления х на n, t i-(k-1)k/2 + 1 , выходы ячеек первой строки и первого столбца первой матрищл соединены с первой группой выходов блока определения перестановок, выходы всех ячеек первой матрицы соединены с второй группой выходов блока,

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

).3. Устройство по Пе Ij о т л и чающееся тем, что блок кодирования размера планарной части содержит треугольную матрицу размером (п-1) (п-1) элементов И, причем первые входы -элементов И каждой строки матрицы соединены ме5кду собой , вторые входы элементов И как;дого столбца матрицы соединены ме}кд собой и образуют входы блока, выхо,ды элементов И являются выходами блока.

1. УСТРОЙСТВО ДЛЯ РЕШЕНИЯ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ, содержащее блок памяти, блок кодирования размера планарной части, дешифратор, выходы которого подключены к входам блока кодирования планарн.ой части, блок вывода информации, блок управления, первая группа выходов которого подключена к входам дешифратора, а вторая - к первой группе входов .блока вывода информации, отличающееся тем, что, с целью повышения его быстродействия и расширения области применения путем обеспечения возможности выделения Планерной части схемы с заданным числом соединений, в него введены блок формирования схемных ограничений, первая, группа входов которого соединена с выходами блока памяти , вторая группа входов - с выходами бл.ока кодирования размера планарной части, и блок определения перестановок, входы которого подключены к выходам блока формирования схемных ограничений, первая группа выходов - к входам блока управления, вторая группа выходов - к второй группе входов блока вывода информа1щи, причем блок формирования схемных ограничений содержит матрицу размером п(п-1)/2- п(п-1) элементов И-НЕ, где п 1 размер планарной части cxeNbi, первые входы элементов И-НЕ каждого столбца матрицы соединены между собой и образуют первую группу входовблока, вторые входы элементов И-НЕ каждой строки матрицы соединены между собой и образуют вторую группу входов блока, выходы элементов И-НЕ являются выходами блока, блок определения -перестановок содержит первую матрицу ячеек размером п . п, элемент И, вторую матрицу ячеек размером п(п-1)/2 п(п-1), (Л причем в первой матрице каждая ячейка состоит из элемента ИЛИ-НЕ и эле мента И, выход которого является выходомячейки, первый вход элемента И соединен с выходом элемента ИЛИ-НЕ, входы которого соединены с выходами ячеек всей строки и всего столбца первой матрицы, на пересечении которых он находится, втоел со ел рой вход элемента И каждой ячейки соединен с выходом элемента И блока определения перестановок, каждая ячейка второй матрицы состоит из элемента И-НЕ и . элемента ИЛИ, первый вход элемента ИЛИ соединен с (Г) выходом элемента И-НЕ, вторые входы элементов ИЛИ каждой ячейки второй матрицы образуют входы блока определения перестановок, первый вход элемента И-НЕ ячейки из i-ой строки и J-ro столбца второй матрицы сое- динен с выходом ячейки из 1-ой строки и k-ro столбца первой матрицы, где t(j-1), t } целая часть числа х, (R-l)k/2 i 3k()/2 второй вход элемента И-НЕ ячейки из i-й строки и j-ro столбца второй матрицы соединен с выходом ячейки из т-й строки и .t -го столбца

Изобретение относится к автомат и вычислительной технике и может быть использовано для решения задачи выделения планарной части схе при автоматизированном проектировании радиоэлектронных схем. Известна система автоматическог изготовления,печатных плат, содержащая ЭВМ общего назначения и техн логическое оборудование для производства печатных, плат ITll. Наиболее близким к предлагаемом по технической сущности является устройство для решения комбинаторн логических задач, содержащее блок управления, блок вврда информации блок моделирования Матрицы смежнос ти , блок анализа матрицы, блок вывода информации , входы которого соединены с выходами блока управления и блока ан.ализа матрицы, выходы которого, соединены с входами блока управления и блока моделирования матрицы смежности графа, входы которого соединены с выхода ми блока управления, блока анализа и блока ввода информации, вход которого соединен с выходом блока управления С21. Недостатками известных устройств являются невозможность выделения планарной части схемы с заданным числом соединений и невысокое быстродействие вследствие после-довательной обработки.данных. Цель изобретения - повышение быстродействия и расширение области применения устройства за счет обеспечения возможности выделять планарную часть схемы с заданным числом соединений. Поставленная цель достигается тем, что в устройство,, содержащее блок памяти, блок кодирования размера планарной части, дешифратор, выходы которого подключены к входам блока кодирования планарной части, блок вывода информации, блок управления, первая группа выходов которого- подключена к входам дешифратора, а вторая - к первой группе входов блока вывода информации, введены блок формирования схемных ограничений, первая группа входов которого соединена с выходами блока памяти, вторая- группа входов с выходами блока кодирования размера планарной части, и блок определения перестановок, входы которого подключены к выходам блока формирования схемных ограничений, первая группа выходов - к входам блока управления, вторая группа выходов к второй rjpynne входов блока вывода информации, причем блок формирования схемных ограничений содержит матрицу размером п(п-1)/2-- п(п-1) элемецтов И-НЕ, где п - размер планарной части cxeNM, первые входы элементов И-НЕ каждого столбца матрицы соединены между собой и образуют .первую группу входов-блока, вторые входы элементов И-НЕ каждой, строки матрицы соединены между собой и образуют вторую группу входов блока, выходы элементов И-НЕ являются выходами блока, блок определения перестановок содержит первую матрицу ячеек размером п п, элемент И, вторую матрицу ячеек . размером n(n-1)/2vn(n-1), причем в первой матрице каждая ячейка состоит из элемента ИЛИ-НЕ и элемента И, выход которого является выходом ячейки, первый вход элемента И соединен с выходом элемента ИЛИ-НЕ, входы которого соединены с выходами ячеек всей строки и всего столбца первой матрицы, на пересечении которых он находится, второй вход элемента И каждой ячейки соединен с выходом эл мента И блока определения перестановок, каждая ячейка второй матрицы состоит из элемента И-НЕ и элемента ИЛИ, первый вход элемента ИЛИ соединен с выходом элемента И-НЕ, вторые входы элементов ИЛИ каждой ячейки второй матрицы образуют входы блока определения перестановок, первый вход элемента И-НЕ ячейки из i-й строки и J-ro столбца второй матрицы соединен с выходом ячейки из 1-й строки и k-ro столбца первой матрицы, где 1 (J -1) / п + 1 , Сх 3 - целая часть числа х, (k-1)k/2 (k+l)/2, второй вход элемента И-НЕ ячейки из i-и строки и j-ro столбца второй матрицы соединен с выходом ячейки из т-й . сроки и t-ro столбца первой матрицы где 4-s),,,l4-(s-1)(n-1)ijil-4-s(n1)-1, (х )- остаток от деления х на n,t i-1(k-1)k/2 -fl, выходаз ячек первой строки и первого столбца первой матрицы соединены с первой группой выходов блока определения перестановок, выходы всех ячеек первой матрицы соединены с второй группой выходов блока.

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

и являются входами блока управления, выход третьего элемента И соединен с инверсным входом первого триггера и вторым входом второго элемента И, выходы первого элемен5 та И и второго триггера являются т вторыми выходами блока управления.

Блок кодирования размера планарт ной части содержит, треугольную матрицу ра.змером (п-1 )ч (п-1 ) элементов И, O причем перчне входы элементов И каждой строки матрицы соединены между собой вторые входы элементов И каждого ртолбца матрицы соединены между собой и образуют входы блока, выходы 5 элементов И являются выходами блока.

На фиг, 1 представлена структурная схема устройства на фиг, 2 схема блока элементов И-НЕ) на фиг.З- схема блока определения перестано-г вок; на фиг, 4 - схема блока управления f на фиг, 5 - схема блока элементов И, ,

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

Блок 1 памяти предназначен для хранения-матрицы пересечений и пред-ставляет из себя матрицу триггеров размером п - п, в которой по главной диагонали триггеры отсутствуют ввиду 5 их ненадобности по свойствам мат рицы пересечений,

Блок 2 формирования схемных ограничений (фиг, 2 формирует схемные ограничения, позволяет опреде0 лить систему ограничений для выделения пл&нарной части схемы с числом соединений не менее заданного и представляет собой матрицу размером п(п-1 ) /2 - п(п-1). элементов 5 И-НЕ 8, Входы первой группы соединены с выходами матрицы триггеров блока 1 памяти в порядке сканирования матрицы по строчкам слева направо сверху вниз,

Блок 3 определения перестановок фиг, 3 позволяет определить перестановку двухполюсных соединений для выделения планарной части схема, удовлетворяющую сформированным схемным ограничениям. Блок 3 содержит 5 элементы И 9, элементы ИЛИ-НЕ 10,

элемент И 11, элементы ИЛИ 12 и элементы И-НЕ 13, Входы блока определения перестановок соединены свыходами соответствующих элементов 0 И-НЕ блока 2 элементов И-НЕ,

Блок 4 вывода информации слугжит для вывода результатов решения Зсвдачи выделения планарной части.

Блок 5 управления управляет ра5 ботой устройства, позволяет задавать размер выделяемой планарной части cxeivsj. Блок управления содержит переключатели 14 для задания размера планарной части схемы, генератор 15 одиночного импульса, однополюсный переключатель 16 режима работы, элементы И 17 и триггеры 18..

Дешифратор б производит дешифрацию десятичного кода.

Блок 7 кодирования размера планарной части (фиг. 5 формирует информацию о размере планарной части схемы, передает ее в блок 2 формирования схемных ограничений и состоит из треугольной матрицы размером (n-l)-(n-l) элементов И 19,

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

Н-а коммутационной поверхности адано множество конструктивных элеентов R (г , Г2 , . . . f Гр, Выводы тих элементов некоторое ножество из L связных подмножеств (-1 f с ,.;;VC -| , причем аждое Е -е подмножество (Ср объедияет N выводов -конструктивных лементов из множеств R в соответтвии с принципиальной схемой, . роме того, заданы расположение ; групп контактных площадок разъемов монтажных отверстий, а также ряд требований, предъявляемых к техноогии платы.

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

Выделение планарной части cxeNtj сводится к удалению некоторой части цепей с одного слоя на другой. Удобной формой представления информации о системе взаимного пересечения явяется матрица пересечений. Каждый столбец матрицы пересечений представляет одну связь схемы каждая строка - также одну связь схемы, В каждом столбце матрицы пересечений индексом tl отмечены связи, которые пересекают рассматриваемые связи. Индексом О отмечены в каждом столбце те связи, которые не пересекаются СЗ 3. Матрица пересечений есть квадратная матрица, так как и строки и столбцы соответствуют элементам одного и того же тождества связи,

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

р;г&Ь 1.вЛг

()

где п - размерность, исходной матрицы пересечений,

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

;гёё- «

где Пр.-- размерность планарного

подмножества связей, кото рое должно быть выделено, Причем

U 1 i п

о

U

UJ По .

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

0 .И.

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

(61

Uj , . (7)

.при

Ограничения ( 4 ) - ( 7 I определяются природой задачи и свойствами матриц регулярного представления группы переустановок. Они не зависят от свойств схемы,, для которой определяется планарное подмножество cвязeй,J

Преобразованная в соответствии с (1 ) матрица пересечений обладает теми же общими свойствами, что и исходная,

В каждую из сумм (1 ) входят пары слагаемых, которые отличаются перестановкой индексов, так как и К и 8 определены на одинаковых множествах. Отличаются эти сл только знаками

i{4ibej Pice-Si 4jPev)

Так как согласно (4)

bici be, О,

то в каждой паре слагаемых вида (8 I дольно одно может чаться от О, если

Ъ.Ър/.О,.

то

bg; bi,j О,

наоборот, если

bg.b. О,

то

Hi , , ,. Поэтому в сумме (1 / ограничения

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

Ы-°

В сумма Х. 1 /входят только слагаемые

О,

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

(9)

О,

. -ki °EJ

где пара индексов i , j определяется элементом преобразованной матрицы Р , а пара индексов k, В - ненулевы1|4и элементами исходной матрищл Р.

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

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

схемные ограничения и передаются в блок 3 определения перестановок. По сформированным в блоке 2 схемным ограничениям блоком 3 определяется одна из возможных перестановок и результаты вычислений передаются в блок 5, где они анализируются, т.е. определяется появление единиц . одновременно на выходах а, ,.а а.., . а,. Если требуемая перестановка определена, т,е, отсутствуют одновременно единичйые сигналы на

выходах а.,, ,. а;,, а. ,,,а в блок

Ц-т

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

Как указано выше, совокупность индивидуальных и общих ограничений образуют систему уравнений, которыми Определяются элементы искомой матрицы перестановок. CoBN.ecTHOCTb этих уравнений определяется размерами требуемого диагонального нуле- вого блока (требуемым числом связей в планарном подмножестве). Если размер требуемого диагонального блока больше, чем число связей в наибольшем планарном подмножестве, то система становится несовместной и в схеме блока 3 определения перестановок возникают состояния, когда

выходы а,.

переходят

.а

1п

m иэ нулевого

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

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

«

ffJV

fm

fn

/

L

i

r:

ДГ li

Hril

rllj

LXp

4/

5

r;

ffViL

E;%J -6-11

jsp/«r

I .

I

, .7I2W

flWlF

К Г I I i I I I I I I I I I I I- I I I ю гох езово 7090 аотзоо апоо - -

C,г

-f

-/.

Sj

4/