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

(53) 6813 (08 Р 45Л.И,Раппопорт урейчик ственное объеи выпуску сред машин Бюп, вски ВМ изво анию орны ст(56) 1, кл, 2352, А Р 48275 (протот3. В рования 1978. т США Р 25679 г, 1971ое свидетельс С 06 Р 15/34 Натен 151.1 торсккл, и). просы интег во СССР 1975втоматизациальных схем. роектиев,ю ДАРСТВЕННЫЙ КОМИТЕТ СССЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ОПИСАНИЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54)(57) 1, УСТРОЙСТВО ДЛЯ РЕШЕНИЯКОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ ПРИПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ, содержащее блок памяти, блок кодированияразмера планарной части, дешифратор,выходы которого подключены к входамблока кодирования планарной части,блок вывода информации, блок управления, первая группа выходов которого подключена к входам дешифратора, э вторая - к первой группе входов блока вывода информации, о тл и ч а ю щ е е с я тем, что, сцелью повышения его быстродействияи расширения области применения путем обеспечения воэможности выделения планарной части схемы с заданным числом соединений, в него введены блок формирования схемных ограничений, первая группа входов которого соединена с выходами блока памяти, вторая группа входов - с выходами блока кодирования размера планарной части, и блок определенияперестановок, входы которого подклчены к выходам блока формированиясхемных ограничений, первая группавыходов - к входам блока управления, вторая группа выходов - к второй группе входов блока вывода информации, причем блок формирования схемных ограничений содержит матрицу размером п(п)/2 п(п"1) элементов И-НЕ, где иразмер планарной части схемы, первые входы элементов И-НЕ каждого столбца матрицы соединены между собой и образуют первую группу входов блока, вторые входы элементов И-НЕ каждой строки матрицы соединены между собой и образуют вторую группу входов блока, выходы элементов И-НЕ являются выходами бло ка, блок определения перестановок со держит первую матрицу ячеек размером ип, элемент И, вторую матрицуячеек размером п(п)/2п(п), причем в первой матрице каждая ячейка состоит из элемента ИЛИ-НЕ и эле мента И, выход которого является выходомячейки, первый вход элемента И соединен с выходом элемента ИЛИ-НЕ, входы которого соединены с выходами ячеек всей строки и всего столбца первой матрицы, на пересечении которых он находится, второй входэлемента И каждой ячейки соединен с выходом элемента И блока определения перестановок, каждая ячейка второй матрицы состоит из элемента И-НЕ и . элемента ИЛИ, первый вход элемента ИЛИ соединен с выходом элемента И-НЕ, вторые входы элементов ИЛИ каждой ячейки второй матрицы образуют входы блока определения перестановок, первый вход элемента И-НЕ ячейки из 1-ой строки и )-го столбца второй матрицы сое динен с выходом ячейки из 1-ой строки и 1 с-го столбца первой матрицы, где 1-1)/и+1, гх 1 - целая часть числа х, (-1)с/2 (1 Зс(3 с+1)/2 второй вход элемента И-НЕ ячейки из 1-й строки и -го столбца второй матрицы соединен с выходом ячейки из пс-й строки и .1 -го столбца1059579 первой матрицы, где еа(3+я),1 Ф(5-1)(п-)) ( 1+5(п)-1 р (х)остаток от деления х на и, с1- (1-1) 12 + 1выходы ячеек первой строки и первого столбца первойматрицы соединены с первой группойвыходов блока определения перестановок, выходы всех ячеек первойматрицы соединены с второй группойвыходов блока,2. Устройство по и, 1, о т л ич а ю щ е е с я тем, что блок управления содержит переключатель задания размера планарной части, выходы которого являются первыми выходами блока, генератор одиночногоимпульса, однополосный переключательтри элемента И, два триггера, причем вход однополюсного переключателя соединен с выходом генератораодиночного импульса, первый выходс первыми выходами первого и второго элементов И, второй выход " с прямым входом первого триггера и инверсным входом второго триггера, вы 1Изобретение относится к автоматикеи вычислительной технике и можетбыть использовано для решения за"дачи выделения планарной части схемы при автоматизированном проектировании радиоэлектронных схемИзвестна система автоматическогоизготовления, печатных плат, содержащая ЭВМ общего назначения и технологическое оборудование для производства печатных. плат Г 13.Наиболее близким к предлагаемомупо технической сущности являетсяустройство для решения комбинаторнологических задач, содержащее блокуправления, блок ввода информацииблок моделирования Матрицы смежности, блок анализа матрицы, блок выводаинформации, входы которогосоединены с выходами блока управления и блока анализа матрицы, выходы которого. соединены с входамиблока управления и блока моделирования матрицы смежности графа,входы которого соединены с выходами блока управления, блока анализа 25и блока ввода ИнФормации, входкоторого соединен с выходом блокауправления 21,Недостатками известных устройствявляются невозможность выделенияпланарной части схемы с заданнымчислом соединений и невысокое ход второго элемента И соединен спряьым входом второго триггера,прямой выход первого триггера соединен с вторым входом первого элемента И, входы третьего элемента Иявляются входами блока управления,выход третьего элемента И соединенс инверсным входом первого триггераи вторым входом второго элемента И,выходы первого элемента И и второго триггера являются вторыми выходами блока управления.1 3. Устройство по п, 1, о т л и ч а ю щ е е с я тем, что блок кодирования размера планарной части содержит треугольную матрицу размером (и) (и) элементов И, причем первые входы .элементов И каждой строки матрицы соединены между собой, вторые входы элементов И каждого столбца матрицы соединены между собой и сбразуют входы блока, выходы элементов И являются выходами блока,2быстродействие вследствие последовательной обработки. данных,Цель изобретения - повышениебыстродействия и расширение областиприменения устройства за счет обеспечения возможности выделять планарную часть схемы с заданным числом соединений,ПостаВленная цель достигается тем, что в устройство, содержащее блок памяти, блок кодирования размера планарной части, дешифратор, выходы которого подключены к входам блока кодирования планарной части, блок вывода информации, блок управления, первая группа выходов которого подключена к входам дешифратора, а вторая - к первой группе входов блоха вывода информации, введены блок формирования схемных ограничений, первая группа входов которого соединена с выходами блока памяти, вторая группа входов с выходами блока кодирования размера планарной части, и блок определения перестановок, входы которого подключены к выходам блока формирования схемных ограничений, первая группа выходов - к входам блока управления, вторая группа выходов - к второй группе входов блока вывода информации, причем блок формирования схемных ограничений содержит матрицу размером п(п)/2п(п) элеме 1 атов И-НЕ, где и в . размер планарной части схема, первые входы элементов И-НЕ каждого столбца матрицысоединены между собой и образуют,первую группу входов блока, вторыевходы элементов И-НЕ каждой строки 5матрицы соединены между собой и образуют вторую группу входов блока,выходы элементов И-НЕ являются выходами блока, блок определения перестановок содержит первую матрицу 1 Оячеек размером и и, элемент И,вторую матрицу ячеек размером.и(п)/2и(и), причем в первойматрице каждая ячейка состоит изэлемента ИЛИ-НЕ и элемента И, выход 15которого является выходом ячейки,первый вход элемента И соединен свыходом элемента ИЛИ-НЕ, входы которого соединены с выходами ячееквсей строки и всего столбца первой .матрицы, на пересечении которых оннаходится, второй вход элемента Икаждой ячейки соединен с выходом элемента И блока определения перестановок, каждая ячейка второй матрицысостоит из элемента И-НЕ и элемента ИЛИ, первый вход элемента ИЛИсоединен с выходом элемента И-НЕ,вторые входы элементов ИЛИ каждойячейки второй матрицы образуют входы блока определения перестановок,первый вход элемента И-НЕ ячейки из1-й строки и -го столбца второйматрицы соединен с выходом ячейкииз 1-й строки и 1-го столбца первой матрицы, где 1=1-1)/и 1 + 1, 35Гх 1 в целая часть числа х,(М)1 с/2 (1 (1 с(1 с + 1)/2, второй входэлемента И-НЕ ячейки из 1-й строки и )-го столбца второй матрицысоединен с выходом ячейки из в-й , 40сроки и й-го столбца первой матрицы,где в=( ч з),1+(в)(и)4,)1+я(п 1)-1, (х )и- остаток от деления хна и, й = 1-1(к) 1 с/2 +1, выхода ячеек первой строки и первого столбца 45первой матрицы соединены с первойгруппой выходов блока определенияперестановок, выходы всех ячеекпервой матрицы соединены с второйгруппой выходов блока,Блок управления содержит переключатель задания размера планарнойчасти, выходы которого являются первыми выходами блока, генератор одиночного импульса, однополюсный переключатель, три элемента И, два 55триггера, причем вход однополюсногопереключателя соединен с выходомгенератора одиночного импульса, первый выход - с первыми выходами первого и второго элементов И, второй 60выход - с прямым входом первого триггера и инверсным входом второго триггера, прямой выход первого триггерасоединен с вторым входбм первогоэлемента И входы третьего элемента И являются входами блока управления, выход третьего элемента И соединен с инверсным входом первоготриггера и вторым входом второгоэлемента И, выходы первого элемента И и второго триггера являются твторыми выходами блока управления,Блок кодирования размера планар-,ной части содержит треугольную матрицу размером (и)(и) элементов И,причем первые входы элементов И каждой строки матрицы соединены между собой;вторые входы элементов И каждогостолбца матрицы соединены между собой и образуют входы блока, выходыэлементов И являются выходами блока,На фиг. 1 представлена структурная схема устройства, на фиг, 2схема блока элементов И-НЕ) на фиг,Зсхема блока определения перестано-.вок; на фиг. 4 - схема блока управпения; на фиг, 5 - схема блока элеиентов И,устройство (фиг 1 1 содерт блок1 памяти, блок 2 формирования схем.ных ограничений, блок 3 определенияперестановок, блок 4 вывода информации, блок 5 управления, дешифратор б и блок 7 кодирования размера планарной части.Блок 1 памяти предназначен дляхранения матрицы пересечений и пред ставляет из себя матрицу триггеровразмером и - п, в которой по главнойдиагонали триггеры отсутствуют ввидуих ненадобности по свойствам мат =рицы пересечений,Блок 2 формирования схемныхограничений (фиг, 2) Формирует схемные ограничения, позволяет определить систему ограничений для выде"ления планарной части схемы с числом соединений не менее заданногои представляет собой матрицу размером и(п)/2 . п(п) элементовИ-НЕ 8, Входы первой группы соединены с выходами матрицы триггеровблока 1 памяти в порядке сканирования матрицы по строчкам слева направо сверху вниз,Блок 3 определения перестановокфиг. 3 позволяет определить перестановку двухполюсных соединенийдля выделения планарной части схема,удовлетворяющую сформированным схемным ограничениям. Блок 3 содержитэлементы И 9, элементы ИЛИ-НЕ 10,элемент И 11, элементы ИЛИ 12 и элементы И-НЕ 13. Входы блока определения перестановок соединены свыходами соответствующих элементовИ-НЕ блока 2 элементов И-НЕ,Блок 4 вывода информации слу-.жит для вывода результатов решениязадачи выделения планарной частиБлок 5 управления управляет работой устройства, позволяет эада 1059579вать размер выделяемой планарнойчасти схемы, Блок управления содержит переключатели 14 для заданияразмера планарной части схемы, генератор 15 одиночного импульса,однополюсный переключатель 16 режима работы, элементы И 17 и триггеры 18,Деши фр атор 6 прои з водит деши фрацию десятичного кода,Блок 7 кодирования размера планарной части (фиг. 5) формируетинформацию о размере планарнойчасти схемы, передает ее в блок 2формирования схемных ограничений исостоит из треугольной матрицы размером (п) (и) элементов И 19,Зачада проектирования печатныхплат может быть поставлена следующим образом,На коммутационной поверхностизадано множество конструктивных эле.ментов В = 1 г , г г. Выводыэтих элементов образуют некотороемножество из 1 связных подмножеств, с, с, , причемКаждое 0 -е подмножество С объединяет М выводов конструктивныхэлементов из множеств В в соответ.ствии с принципиальной схемой,Кроме того, заданы расположениегрупп контактных площадок разъемови монтажных отверстий, а также рядтребований, предъявляемых к технологии платы,Решение задачи выделения планарной части схемы с числом двухполюсных соединений не менее заданногопозволит равномерно расположить соединения на слоях печатных плат, атакже за ограниченное число цикловприводит к решению задачи выделениянаибольшего планарного подмножества.Выделение плайарной части схемы, сводится к удалению некоторой частицепей с одного слоя на другой, Удобной формой представления информациио системе взаимного пересечения является матрица пересечений, Каждыйстолбец матрицы пересечений представляет одну связь схемы, каждаястрока - также одну связь схемы,В каждом столбце матрицы пересечений индексом + 1 отмечены связи,которые пересекают рассматриваемыесвязи. Индексом 0 отмечены в каждомстолбце те связи, которые не пересекаются ГЗ .1, Матрица пересеченийесть квадратная матрица, так каки строки и столбцы соответствуютэлементам одного и того же тождества связи.С помощью конгруэнтного преобразования матрицей В линейного регулярного представления группы исходную матрицу пересечений Р можнопривести к матрице Р имеющей блочную структуру, где ненулевые блоки расположены на побочной диагонали, что отражает факт выделения планарных частей схемы, причем.и игде и - размерность, исходной матрицы пересечений,10 . Для поиска планарной частипре -образованной матрицы Р необходимо потребовать равенство нулю элементов этой планарной части,т,е,П 0Р"=-- ЬА Ри =0")- 1 ) Игде и, - размерность планарногоподмножества связей, кото 2 О рое должно быть выделено.Причем161 ЬпИ)1 с с и25Таким образом, для того, чтобывыделить планарную часть схемы,необходймо определить элементы матрицы В из следующих условий ЗО,к 1 Ь. ЫСь,ь .:о, ь .ь,=о. (ц 35 Кф 1Поскольку расположение строк (столбцов ) связей, принадлежащих планарному подмножеству, внутри нулевого .диагонального блока матрицы безразЩО лично, номера строк (столбцов ) связей нулевого диагонального блока( планарного подмножества связей)всегда могут быть упорядочены такимобразом, чтобы45приОграничения (4 ) - ( 7 ) определяются природой задачи и свойствамиматриц регулярного представлениягруппы перестановок, Они не зависятот свойств схемы, для которой оп ределяется планарное подмножествосвязей.,Преобразованная в соответствиис (1 ) матрица пересечений обладаетбО теми же общими свойствами, что иисходная.В каждую из сумм (,1 ) входят парыслагаемых, которые отличаются перестановкой индексов, так как и Кб 5 и 9 определены на одинаковых множествах. Отличаются эти слагаемыетолько знаками Так как согласно ( 4 15Ьк 1 Ье 1 = Ото в каждой паре слагаемых суммы 1)вида 18только одно может отличаться от О, еслиЪ. Ье,. ф.О,.тоЬ, Ьк=оИ, нао 3 оро 1, еслиЬЕ-К Ф О,.) 15Поэтому в сумме (1) ограниченияфактически могут накладываться лишьна одну половину слагаежх а величина Р может оказаться равной нулю.лишь тогда, когда каждое из слагаемых равно йулюЬ,.Ъ .Р =о,и екеВ сумма (,11 входят только слагае.-мыеЬьедля которых РКЕ = -Р ЕКО и, какуказайо выше, должно равняться нулюкаждое Нз слагаемых, Поэтому система ограничений может быть записана ввиде набора равенств.ЬЬе = О, (9)где пара .индексов , ) определяется элементом преобразованной матрицы Р, а пара индексовК, Е - ненулевыми элементами исходной матрицы РУстройство работает следующим 40образом,Пусть в блоке 1 памяти записанаинформация о матрице пересечений, вблоке 5 управления однополюсный переключатель находится в состоянии"Пуск", а переключателями заданиязадано число соединений в определяемой планарной части, схемы, тогдана выходе блока 7 кодирования раз,мера планарной части формируютсясигналы, определяющие размер отыскиваемой .планарной части схем,По сигналам, сформированным в блоках 7 и 1, блоком 2 формируются схемные ограничения и передаются вблок 3 определения перестановок.По сформированным в блоке 2 схемнымограничениям блоком 3 определяетсяодна из возможных перестановок ирезультаты вычислений передаютсяв блок 5, где они анализируются,т,е, определяется появление единиц .одновременно на выходах аа 1а 11ап 1 Если требуемая перестановка ойределена, т.е. отсутствуютодновременно единичйые сигналы навыходах аа 1, а,ав блок4 выдаются управляющие сигналы навывод информации, а если требуемая перестановка не .определена,формируется сигнал о том, что необходимо уменьшить размер отыскиваеМой планарной части схемы,Как указано выше, совокупностьиндивидуальных и общих ограничений образуют систему уравнений, которыми определяются элементы искомойматрицы переСтановок. Совместностьэтих уравнений определяется размерами требуемого диагонального нулевого блока. требуемым числом связейв планарном подмножестве ). Если размер требуемого диагонального блокабольше, чем число связей в наибольшем планарном подмножестве, то система становится несовместной и всхеме блока 3 определения перестановок возникают состояния, когдавыходы а а, , а+ а,переходятгиз нулевого в единичное состояние,что контролируется третьим элементом И блока 5 управления, и единичный сигнал на прямом выходе второго триггера блока 5 управления соответствует тому, Что необходимо изменить размер отыскиваемого планарного блока, Если в схеме такого состояния не возникает, на выходе пер-вого элемента И блока 5 управлениявозникает управляющий сигнал, соответствующий тому, чте задача отыскивания планарной части решена. Таким образом, введение новых блоков и связей позволяет повысить быстродействие устройотва и расширить область его .применения за счет обеспечения возможности выделять планарную часть схема с заданным числом соединений.