Устройство для решения комбинаторно-логических задач при проектировании печатных плат

 

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 -го столбца

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

3(5D G 06 F 15/347

I ,/

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3386033/18-24 (22) 22.01.82 (46) 07.12.83. Бюл, Р 45 (72) Б.Н.Мороговский, Л.И.Раппопорт, С.А,Поливцев и В.М.Курейчик (71) Научно-производственное объединение по созданию и выпуску средств автоматизации горных машин (53) 681 ° 3 (088. B) (56) 1. Патент США Р 2567914, кл. 235-151.11, 1971 °

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

Р 482751, кл. Q Об F 15/347, 1975 (прототип).

3. Вопросы автоматизации проектирования интегральных схем. Киев, 1978. (54)(57) 1. УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ ПРИ

ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ, содержащее блок памяти, блок кодирования размера планарной части, дешифратор, выходы которого подключены к входам блока кодирования планарной части, блок вывода информации, блок управления, первая группа выходов которого подключена к входам дешифратора, э вторая — к первой группе входов .блока вывода информации, о т л и ч а ю щ е е с я тем, что, с целью повышения его быстродействия и расширения области применения путем обеспечения воэможности выделения планарной части схемы с заданным числом соединений, в него введены блок формирования схемных ограничений, первая группа входов которого соединена с выходами блока памяти, вторая группа входов — с выходами блока кодирования размера планарной части, и блок определения перестановок, входы которого подключены к выходам блока формирования схемных ограничений, первая группа выходов — к входам блока управле„„SU„„3059579 А ния, вторая группа выходов — к второй группе входов блока вывода информации, причем блок формирования схемных ограничений содержит матрицу размером п(п-1)/2 - п(п-1) элементов

И-НЕ, где и размер план арной части схемы, первые входы элементов

И-НЕ каждого столбца матрицы соединены между собой и образуют первую группу входов блока, вторые входы элементов И-HE каждой строки матрицы соединены между собой и образуют вторую группу входов блока, выходы элементов И-НЕ являются выходами блока, блок определения перестановок содержит первую матрицу ячеек размеЯ ром n ° и, элемент И, вторую матрицу ю ячеек размером n(n-1)/2 п(п-1), причем в первой матрице каждая ячейка состоит из элемента ИЛИ-НЕ и эле мента И, выход которого является С: выходом ячейки, первый вход элемента И соединен с выходом элемента

ИЛИ-НЕ, входы которого соединены с выходами ячеек всей строки и всего столбца первой матрицы, на пересечении которых он находится, второй вход элемента И каждой ячейки соединен с выходом элемента И бло- (ф ка определения перестановок, каждая ячейка второй матрицы состоит из элемента И-НЕ и . элемента ИЛИ, пер- М,) вый вход элемента ИЛИ соединен с выходом элемента И-НЕ, вторые входы элементов ИЛИ каждой ячейки второй матрицы образуют входы блока определения перестановок, первый вход элемента И-НЕ ячейки из i-ой строки ф и J-ro столбца второй матрицы сое» динен с выходом ячейки из 1-ой строки и k-ro столбца первой матрицы, где 1 $(J -1)/г )+1, 1 х ) - целая часть числа х, (f -1)k/2 (.i <1с(М+1)/2 второй вход элемента И-НЕ ячейки из i-й строки и j-го столбца второй матрицы соединен с выходом ячейки из m-й строки и + -го столбца

1059579 первой матрицы, где ва(jiя)„, 14 (5 1J(0 )(J + 1+8(П 1) 1 р (Х) остаток от деления х на и с

i - (k-1) k/2 + 1 > выходы ячеек первой строки и первого столбца первой матрицы соединены с первой группой выходов блока определения перестановок, выходы всех ячеек первой матрицы соединены с второй группой выходов блока, 2. Устройство по и, 1, о т л ич а ю щ е е с я тем, что блок управления содержит переключатель задания размера планарной части, выходы которого являются первыми выходами блока, генератор одиночного импульса, однополосный переключатель три элемента И, два триггера, причем вход однополюсного переключа.теля соединен с выходом генератора одиночного импульса, первый выход с первыми выходами первого и второго элементов И, второй выход - с пря мым входом первого триггера и инверсным входом второго триггера, вы1

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задачи выделения планарной части схемы ?Ipse> автоматизированном проекти- 5 ровании радиоэлектронных схем„

Известна система автоматического изготовления, печатных плат, содержащая ЭВМ общего назначения и технологическое оборудование для производства печатных. плат Г1 J.

Наиболее близким к предлагаемому по технической сущности является устройство для решения комбинаторнологических задач, содержащее блок управления, блок ввода информации блок моделирования Матрицы смежности, блок анализа матрицы, блок вывода информации, входы которого соединены с выхоДами блока управления и блока анализа матрицы, выходы которого. соединены с входами блока управления и блока моделирования матрицы смежности графа, входы которого соединены с выходами блока управления, блока анализа и блока ввода Информации, вход которого соединен с выходом блока управления (2.1.

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

3. Устройство по п, 1, о т л и ч а ю щ е е с я тем, что блок кодирования размера планарной части содержит треугольную матрицу размером (n=l) ° (n-1) элементов И, причем первые входы .элементов И каждой строки матрицы соединены между собой, вторые входы элементов И каж-. дого столбца матрицы соединены между собой и сбразуют входы блока, выходы элементов И являются выходами блока, 2 быстродействие вследствие последовательной обработки. данных.

Цель изобретения - повышение быстродействия и расширение области применения устройства за счет обеспечения возможности выделять планарную часть схемы с заданным числом соединений, Поставленная цель .достигается тем, что в устройство, содержащее блок памяти, блок кодирования размера планарной части, дешифратор, выходы которого подключены к входам блока кодирования планарной части, блок вывода информации, блок управления, первая группа выходов которого-подключена к входам дешифратора, а вторая — к первой группе входов блоха вывода информации, введены блок формирования схемных ограничений, первая группа входов которого соединена с выходами блока памяти, вторая группа входов с выходами блока кодирования размера планарной части, и блок определения перестановок, входы которого подключены к выходам блока формирования схемных ограничений, первая группа выходов — к входам блока управления, вторая группа выходов— к второй группе входов блока вывода информации, причем блок формирования схемных ограничений содержит матрицу размером n(n-1)/2 ° n(n-1) эле1059579 ме1атов И-НЕ, где n †. размер планарной части схема, первые входы элементов И-НЕ каждого столбца матрицы

- соединены между собой и образуют ,первую группу входов блока, вторые входы элементов И-НЕ каждой строки матрицы соединены между собой и образуют вторую группу входов блока, выходы элементов И-НЕ являются выходами блока, блок определения перестановок содержит первую матрицу () ячеек размером n n элемент И, вторую матрицу ячеек размером и(и-1)/2 и(n-1), причем в первой матрице каждая ячейка состоит из элемента ИЛИ-НЕ и элемента И, выход 15 которого является выходом ячейки, первый вход элемента И соединен с выходом элемента ИЛИ-НЕ, входы которого соединены с выходами ячеек всей строки и всего столбца первой . матрицы, на пересечении которых он находится, второй вход элемента И каждой ячейки соединен с выходом элемента И блока определения перестановок, каждая ячейка второй матрицы состоит из элемента И-НЕ и элемента ИЛИ, первый вход элемента ИЛИ соединен с выходом элемента И-HE вторые входы элементов ИЛИ каждой ячейки второй матрицы образуют входы блока определения перестановок, первый вход элемента И-НЕ ячейки из

i-й строки и j-ro столбца второй матрицы соединен с выходом ячейки из 1-й строки и k-ro столбца первой матрицы, где l= ((j -t)/ri j + 1, 35

Cx g - целая часть числа х, (k-1) k/2 (i c k(k + 1)/2, второй вход элемента И-НЕ ячейки из i é строки и j-ro столбца второй матрицы соединен с выходом ячейки из m-й . 4() сроки и t-ro столбца первой матрицы, где m =(j ч. s )» l +(s - 1 ) (n-1 ) < ) 1+ ь (и1)-1, (х )>- остаток от деления х на и, t = i-1(k-1) k/2 +1, выхода ячеек первой строки и первого столбца 45 первой матрицы соединены с первой группой выходов блока определения перестановок, выходы всех ячеек первой матрицы соединены с второй группой выходов блока.

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

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

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

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

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

И-HE 8, Входы первой группы соединены с выходами матрицы триггеров блока 1 памяти в порядке сканирования матрицы по строчкам слева направо сверху вниз.

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

И-HE блока 2 элементов И-НЕ, Блок 4 вывода информации слу-. жит для вывода результатов решения задачи выделения планарной части °

Блок 5 управления управляет работой устройства, позволяет эада1059579 вать размер выделяемой планарной части схемы. Блок управления содержит переключатели 14 для задания размера планарной части схемы, генератор 15 одиночного импульса, однополюсный переключатель 16 режима работы, элементы И 17 и триггеры 18, Деши фр a Top 6 произ водит дешифрацию десятичного кода, Блок 7 кодирования размера планарной части (фиг. 5) формирует информацию о размере планарной части схемы, передает ее в блок 2 формирования схемных ограничений и состоит из треугольной матрицы размером (п-1) (n-1) элементов И 19, Зачада проектирования печатных плат может быть поставлена следующим образом.

Hà коммутационной поверхности задано множество конструктивных элементов R = г, г,..., г„). Выводы этих элементов образуют некоторое множество из L связных подмножеств (с„, с . .. с,, причем каждое Р -e подмножество C объедиР н яет 1 выводов .конструктивных элементов из множеств R в соответ. ствии с принципиальной схемой.

Кроме того, заданы расположение групп контактных площадок разъемов и монтажных отверстий, а также ряд требований, предъявляемых к технологии платы.

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

Выделение плайарной части схемы, сводится к удалению некоторой части цепей с одного слоя на другой, Удобной формой представления информации о системе взаимного пересечения является матрица пересечений, Каждый столбец матрицы пересечений представляет одну связь схемы, каждая строка — также одну связь схемы, В каждом столбце матрицы пересечений индексом + 1 отмечены связи, которые пересекают рассматриваемые связи. Индексом 0 отмечены в каждом столбце те .связи, которые не пересекаются ГЗ ), Матрица пересечений есть квадратная матрица, так как и строки и столбцы соответствуют элементам одного и того же тождества связи.

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

Р, =E ) 1„.1,.P, (I

Ц 1 = P- К" Й где и — размерность, исходной матрицы пересечений, Для поиска планарной части пре— образованной матрицы Р необходимо потребовать равенство нулю элементов этой планарной части, т. е, по п0

p..= ) Ъ .S:P =0, (Ч

1) ь„— =1 Х1 gj kq где и,„- размерность планарного подмножества связей, кото2О рое должно быть выделено.

Причем

1(1 «(ll0 (3)

1<3 <по

Ъ. Ь., -Q (6) 1М j1

Ограничения (4 ) — (7 ) определяются природой задачи и свойствами матриц регулярного представления группы перестановок. Они не зависят от свойств схемы, для которой оп55 ределяется планарное подмножество связей., Преобразованная в соответствии с (1 ) матрица пересечений обладает бО теми же общими свойствами, что и исходная.

В каждую из сумм (1 ) входят пары слагаемых, которые отличаются перестановкой индексов, так как и К б5 и 9 определены на одинаковых мно25

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

ЗО

К1 1 б, >,=О, Ь .Ь .=0 (Й

35 =1

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

1059579 жествах. Отличаются эти слагаемые только знаками (81

: (0к е; Рке е к Рек ) то

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

Ь„„. Ье; то в каждой паре слагаемых суммы (1) вида (8 олько одно может отличаться от О, если „,„. е; Ф то ь, як=о, И, наоборот, если е - к.Ф О, 1,) 15 ь„; ье„= о.

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

Ъ.„.Ъ . Р =о, ti Е1 КЕ

В сумма J,,1tâõoäÿò только слагае.мые

Ь„; для которых РКЕ = -Р ЕК ф 0 и, как указайо выше, должно равняться нулю каждое Нз слагаемых, Поэтому систе- З0 ма ограничений может. быть записана в виде набора равенств.

Ък,. ъе = 0, (9) где пара .индексов (, 3 определяет- 35 ся элементом преобразованной матрицы Р, а пара индексов k, e — ненулевыми элементами исходной матрицы Р °

Устройство работает следующим А0 образом, Пусть в блоке 1 памяти записана информация о матрице пересечений, в блоке 5 управления однополюсный переключатель находится в состоянии

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

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

4 выдаются управляющие сигналы на вывод информации, а если требуемая перестановка не определена, формируется сигнал о том, что необходимо уменьшить размер отыскиваеМой планарной части схемы, Как указано выше, совокупность индивидуальных и общих ограничений образуют систему уравнений, которыми определяются элементы искомой матрицы переСтановок. Совместность этих уравнений определяется размерами требуемого диагонального нулевого блока. (требуемым числом связей в планарном подмножестве ). Если размер требуемого диагонального блока больше, чем число связей в наибольшем планарном подмножестве, то система становится несовместной и в схеме блока 3 определения перестановок возникают состояния, когда выходы а ...а,, а+„... а„,„переходят 1 pl из нулевого в единичное состояние, что контролируется третьим элементом И блока 5 управления, и единичный сигнал на прямом выходе второго триггера блока 5 управления соответствует тому, Что необходимо изменить размер отыскиваемого планарного блока, Если в схеме такого состояния не возникает, на выходе пер- вого элемента И блока 5 управления возникает управляющий сигнал, соответствующий тому, чте задача отыскивания планарной части решена.

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

1059579 4 м -е ф ю -е - s м

I I I I I 1 I I I I I t I l l I I I I I I i.l l I в ил м а ю ж ж 4F авивавмоЗтат@Ю400

ВНИИПИ . Заказ 9842/53 Тираж 706 Подписное

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