книги / Автоматизация конструкторского проектирования в радиоэлектронике и вычислительной технике. Автоматизация конструкторского проектирования вычислительной техники
.pdfрэятности P<s/j;6buio замечено, что плохо проверяются те схе мы, в которых в ряце внутренних узлов относительные часто ты близки к *1" или "О", особенно если вследствие этого зна чения относительных частот на выходе становятся тоже близ кими к м\* или "О". Это можно объяснить тем, что на входы схемы поступают такие СТВ, которые вызывают однообразные значения сигналов во внутренних узлах схемы, из-за чего не могут быть созданы условия, обеспечивающие проявление а транспортировку многих возможных неисправностей. Поэтому основная идея предлагаемого ниже способа заключается в том, чтобы не допустить такого "однообразия" в схеме, т.е. стре миться к тому, чтобы количество комбинаций значений сигна лов во внутренних узлах было как можно большим в надежде на то, что среди них будет большее количество комбинаций,
тчшизирующих разные пути* Итак, пусть проверяется комбинационная древовидная схе
ма. Потребуем, чтобы значение Z на выходе |
логического эле |
мента (ЛЭ) последнего ранга U было равным |
0 ,5 , а входные |
вероятности этого ЛЭ были равны между |
собой. Кроме того, |
|
потребуем, чтобы входные вероятности каждого ЛЭ рангов |
||
1 тоже были равными между |
собой, причем выход |
|
ные вероятности ЛЭ рангов U- f |
/ определялись вход |
|
ными вероятностями элементов ранга и |
|
2 соответст |
венно. Такое распределение вероятностей обеспечит большое разнообразие комбинаций сигналов во входных и внутренних узлах схемы; и поэтому можно ожидать, что будет активизи ровано много путей, позволяющих обнаружить многие неисправ ности. «Действительно, если схема проверяется детерминирован ным способом путем активизации пути для каждой пары неис правностей типа постоянного сигнала "1" и "О" - X j,X £ (i =
= 12, ..v n)t* Y j, |
относительная частота "1" на |
выходе схемы тоже будет |
равна 0,5 . |
Когда выходная вероятность ЛЭ задана, входные вероят ности этого элемента легко определяются по формулам вычис ления выходных вероятностей ЛЭ, приведенным в [1]. Так как требуется, чтобы входные вероятности каждого ЛЭ были оди наковыми, то выходная вероятность элемента И согласно t i l :
откуда |
*— |
X * у Z |
|
|
U ) |
151
Аналогично цля элемента ИЛИ вхэцные вероятности, обес печивающие заданную выходную вероятность, вычисляются по формуле
'• /-К ЕТ |
( 2) |
Для элементов И-НЕ и ИЛИ-НЕ соответственно: |
|
X- VT^z |
( 3) |
|
(4) |
Вообще говоря, получить аналогичные формулы для других сложных ЛЭ несложно.
Итак, процедура вычисления входных вероятностей схемы сводится к следующим этапам:
- задается выходная вероятность схемы Z = 0,5 ;
-по формулам (1) - (4) вычисляются входные вероятности ЛЭ ранга и>}
-согласно структуре схемы, входные вероятности ЛЭ ран
га |
и принимаются за выходные вероятности ЛЭ ранга а - 1 |
||
и вычисляются входные вероятности элементов |
ранга и -1 ; |
||
|
- последовательность действий, описанных цля |
предыдуще |
|
го |
этапа, повторяется для ЛЭ рангов |
fj |
в результа |
те чего получаются входные вероятности схемы, обеспечиваю щие значение выходной вероятности 0,5.
Вышеописанный подход позволяет повысить вероятности об наружения неисправностей выбранной части схемы. Для этой цели необходимо потребовать, чтобы вероятность на выхо де выбранной подсхемы Ук приняла значение 0 ,5 , и исходя из этого описанным выше способом вычислить входные вероятно сти этой подсхемы. Кроме того, необходимо обеспечить высо кие вероятности условий транспортировки неисправностей от узла УА до выхода Z. Это обеспечивается опять же путем вы числения соответствующих значений входных вероятностей схемы.
Рассмотренный способ выбора входных вероятностей легко распространяется • на комбинационные схемы со сложными ком бинационными элементами, т.к. цля них по формулам ( 1 ) -
(4) легко получить соответствующие формулы. Однако для схем со многими выходами и сходящимися разветвлениями возникает проблема, заключающаяся в следующем. В таких схемах возни
кают ситуации, изображенные на рис. |
1, когда по заданному Z |
необходимо определить значения |
,у* д(2 2) |
15 2
Y -
При последовательном вычислении значений |
|
|
У<г,1Ъ У<2,2) |
в зависимости от функций Ffj |
F3 J |
выполняемых соответствующими ЛЭ, в общем случае окажется, что У а з)? #(2,7) -Такие ситуации решаются путем принятия зна чения .Хотя точность вычислений уменьшается, основная идея рассматриваемого эвристического способа опре
деления вектора Рх сохраняется.
Рассмотрим особенности применения рассмотренного поцхода для последовательностных ДУ. С этой целью условно обор вем все обратные связи рассматриваемой схемы, а места об рывов будем рассматривать как дополнительные входы
комбинационного эквивалента исходной схемы. Как и для комбинационных ДУ потребуем, чтобы выходные вероятно сти были равными 0,5. Отметим, что для вычисления выход ных вероятностей ЛЭ с памятью, как и для комбинационных ЛЭ, могут быть получены соответствующие формулы. Напри
мер, для |
триггера J И |
при независимых входных сигналах |
|||||
Z= |
; где / / - |
вероятность |
"1" на входе |
J j |
- ве |
||
роятность |
"1" |
на в х о д е .Z |
- |
вероятность "1* |
на выходе# |
||
Поэтому в |
комбинационном |
эквиваленте могут |
содержать |
ся ЛЭ с памятью, необходимо оборвать лишь глобальные об
ратные связи. Для вычисления |
|
px%J обеспечивающего выходные |
|
вероятности 0;5, должно быть |
учтено следующее. Значения |
||
вероятностей появления |
на |
тех входах ЛЭ, которые соеди |
нены обратными связями с выходами элементов старших ран гов, задаются их выходными вероятностями. Другие входные вероятности ЛЭ должны вычисляться с учетом всего этого.
Например, пусть вход ‘‘фрагмента схемы, изображенного на рис. 2, является дополнительным, возникшим из-за обрыва об
ратной связи. |
Тогда вероятность |
задается значением, опре |
|
деленным на |
одном из предыдущих этапов процедуры вычисле |
||
ния входных вероятностей |
схемы, а формула (1), принимае |
||
мая для вычисления *0^2 |
изменяется следующим образом: |
||
|
|
1 5 3 |
|
Or |
& |
|
х,- |
|
2 |
|
|
|
Х г |
|
Рис. 2 . |
Применение процедуры |
определения вектора p Xj обеспечива |
ющего высокие вероятности обнаружения неисправностей, про иллюстрируем следующим примером.
П рим ер. Пусть рассматривается последовательная схема и ее комбинациэнный эквивалент, приведенные на рис. 3. Не
обходимо |
|
о п р е д е л и т ь . у |
обеспечивающий высокие ве |
||||
роятности |
обнаружения неисправностей. |
|
|
|
|||
Для |
этого потребуем, чтобы Z - 0,5, Тогда |
по (4): |
|||||
|
|
|
* r ~ y e = t-V T s-0,2929 |
у, |
|
||
Так |
как для |
должно выполняться |
условие |
= 0 ,5 ,фор |
|||
мула (4) |
для вычисления / / |
меняется |
следующим |
образом: |
|||
|
|
£/= 0,4Г42 |
|
|
|
|
|
|
|
|
вычисляются по формуле |
(1): |
|||
|
|
|
хт~ f j = °'ш е |
|
|
|
|
Аналогично |
определяются |
другие внутренние и входные ве |
|||||
роятности, значения которых указаны на рис. 3. |
|
|
|||||
Добавим, что средствами |
системы технического |
проектиро |
вания "Каунас-З" было установлено, что 100 случайных набо ров, описываемых вектором р% = ^0 .6436, 0 ,7 0 2 6 , 0 .2 9 1 0 , 0 .4 5 2 1 , 0 . 2 9 2 9 обеспечивают полноту проверки схемы - 81%. Полнота проверки той же схемы рядом других случайных последовательностей той же длины, описываемых векторами/^ отличными от вычисленного выше колебалась в пределах 2 4 -
72%.
В заключение следует отметить, что предложенный подход: - не обеспечивает определения оптимального вектора в
смысле формулировки и решения задачи оптимизации; - на практике дает ощутимое повышение эффективности про
верки ДУ случайными наборами;
1 5 4
Рис. 3 .
—позволяет проверять ДУ со сложными комбинационными
ипоследовательностными ЛЭ;
-позволяет построить разные векторы />х для диагности
рования отдельных участков схемы, что в конечном результа те обеспечивает большую полноту проверки схемы.
|
|
Л и т е р а т у р а |
|
1. |
PA R K E R |
M cC L U S K E Y |
Е, P ro b a b ilistic |
T re a tm e n t of G e n e ra l C o m b in atio n al |
N e tw o rk s . |
||
IE E E |
T ra n s a c tio n s |
o n C o m p u ters, 1 9 7 5 , Ju n e voJ%c . 24. |
|
2. |
БЕРШТЕЙН M.C., РОМАНКЕВИЧ A.M. Метод статисти |
||
ческого |
контроля логических схем. - Кибернетика, 1974, N? 1. |
3. ЯРАМАЙТИС А,А. Вычисление вероятности обнаруже ния неисправности путем использования булевой разницы. - В кн.: Вычислительная техника. Материалы конф. ''Автоматизиро ванное техническое проектирование электронной аппаратуры?
Каунас, 1^82.
4. ЯРАМАЙТИС А.А. Вероятность активизации пути в по следовательностных схемах случайными входными наборами. - В кн.: Материалы конф. "Автоматизация технического проекти рования цифровой аппаратуры", Каунас, 1984 .
5. БЕРШТЕЙН М.С. О различимости неисправностей ком бинационных схем стохастическим методом. - Кибернетика, 1976, № 3.
УДК 6 8 1 .3 2 5 .6 5
Д.И. Батищев, В.Ф. Морозов. Гибкая трассировка пе чатных проводников с учетом метрических ограниче ний. - В межвузовском сб.: Автоматизация конструк торского проектирования в радиоэлектронике и вычис лительной технике; Вильнюс, 1985, т. 5, с. 3 -1 1 ,
Задача трассировки печатных проводников рассматривается как задача многокритериальной оптимизации. Предлагается ал горитм, сочетающий в себе эффективность алгоритмов гибкой трассировки и волновых алгоритмов в плане учета метрических ограничений. Приведен пример, иллюстрирующий работу алго ритма.
Ил. 4, библ. 5.
УДК 6 2 1 .8 .0 4 9 .7 5
В,Г. Марагин, Б.Н. Деньцэбренкэ. Оптимальное разме щение элементов на плате. - В межвузовском сб.: Ав томатизация конструкторского проектирования в радио электронике и вычислительной технике. Вильнюс, 1985, т. 5, с. 1 1 -1 8 ,
Предлагается новый метод глэбалыю-эптимальнэго разме щения элементов на плате по критерию суммы длин соединений. При размещении используются все рациональные списки оче редности, число которых не превышает N - числа элементов
в схеме. Для выбора места размещения формируется фронт раз мещения из ячеек, смежных с уже занятыми местами. Для уменьшения числа перебора вариантов используется метод вет вей и границ. Нижняя граница оценки определяется на каждом шаге размещения, как минимально возможная сумма длин со единений при самом благоприятном взаимном расположении эле ментов.
Ил. 1, библ. 2.
1 5 7
УДК 6 8 1 * 5 .0 0 1 .2 :6 2 1 .3 8
Ю.Н. Стрельников, И.В. Полыдикова, Г.Д. Дмитревич. Методические проблемы конструирования печатных плат в диалоговых САПР. - В межвузовском сб.: Автома тизация конструкторского проектирования в радноэл^кт^ ронике и вычислительной технике. Вильнюс, 1 9 8 5 , т. 5,
с.1 8 -2 6 .
Формулируются некоторые методические проблемы констру ирования печатных плат в диалоговых САПР, связанные с при менением в едином процессе автоматических и интерактивных графических процедур формирования проектных решений. Эти проблемы касаются выбора уровня интерактивного взаимодей ствия, формирования оптимальных маршрутов проектирования, обучения пользователя и системы. Предлагаются пути и мето ды их решения.
Еибл. 6.
УДК 6 8 1 .3 2 3 ;6 2 1
В.А. Жилявичюс, Р.Й. Балтрушайтис. Критерии равно мерного размещения. - В межвузовском сб.: Автома тизация конструкторского проектирования в радиоэлект ронике и вычислительной технике. Вильнюс, 1985, т. 5, с. 2 6 -4 3 .
Рассматриваются вопросы определения оценок загруженно сти и пропускных способностей отдельных участков монтажно го пространства. На основе этих оценок построены различные критерии равн омерного размещения. Приведены результаты экс периментального исследования разработанных критериев.
Ил. 4, библ, 9.
УДК 6 8 1 .3 .0 8 2
Е.Г. Ойхман. Математические оценки структур данных в оперативной памяти для интерактивных САПР, - В межвузовском сб.: Автоматизация конструкторского
1 5 8
проектирования в оациоэлектрэнике и вычислительной технике. Вильнюс, 1985, т. 5, с. 4 3 -4 8 .
Исследуются вопросы оценки структур данных на этапе создания ее модели. Основными критериями, по которым оце ниваются модели, являются объем занимаемой памяти, а так же время поиска и обновления данных.
Библ. 6.
УДК 5 1 9 .8
В.А. Штуйкис. Метод компоновки групп на основе мно гократного решения вспомогательной задачи о назна чениях, - В межвузовском сб.: Автоматизация конст рукторского проектирования в радиоэлектронике и вы -., числительной технике.Вильнюс, 1985, т. 5, с. 4 8 -5 7 .
Рассматриваются задача и метод компоновки групп, когда критерием является минимум (максимум) суммы типов элемен тов во всех группах. Приводятся этапы и обоснование метода, численный пример и некоторые результаты его эксперименталь ной проверки.
Ил. 1, библ. 3,
УДК 6 8 1 .3 2 5 .6 5
Р.П. Базилевич, Ю.М. Греськэ. Синтез топологических укладок с минимизацией числа межслойиых переходов.- В межвузовском сб.: Автоматизация конструкторского проектирования D радиоэлектронике и вычислительной технике. Вильнюс, 1985, т. 5, с. 5 7 -6 7 .
Для выделенной замкнутой области, пересекаемой множе ством электрических соединений, рассмотрена задача синтеза двух плоских укладок.
Представлены эффективные алгоритмы, испэльзуюшие топо логический подход с минимизацией как числа соединений, реа лизуемых с межслойными переходами, так и общего числа пе реходов. Дана оценка машинных решений.
Ил. С, библ. 3.
1 5 9
УДК 6 8 1 .3 0 2 :6 8 1 .3 * 0 6
А.М. Бершадский, Е.В. Карлов, И.В. Тужилов. Приме нение функции загруженности монтажного пространст ва при коммутационном проектировании матричных БИС и ТЭЗ. - В межвузовском сб.: Автоматизациг конструкторского проектирования в радиоэлектронике к вычислительной технике. Вильнюс, 198 5 , т. 5,*
с.67 -7 2 .
Встатье рассматривается метод размещения компонентов матричных БИС и ТЭЗ по критерию минимума функции загру женности монтажного пространства. Показано, что данный кри терий размещения позволяет обеспечить хорошие условия для полностью автоматической трассировки межсоединений, т.к. со гласует цели этапов размещения и трассировки.
Ил. 1, библ. 5.
УДК 6 8 1 .3 .0 8 2
Е.Г. Ойхман. Модели системных библиотек элементов для интерактивных САПР печатных плат. - В межву зовском сб.: Автоматизация конструкторского проекти рования в радиоэлектронику и вычислительной технике. Вильнюс, 1985, т. 5, с. 7 2 -7 8 .
Исследуются различные способы построения библиотек эле ментов на внешней памяти. Предлагаемся модель системной библиотеки, отличающейся простотой ее пополнения.
Библ, 4.
УДК 5 1 9 .8 :6 8 1 .5 1
Й.-К.Л. Матицкас, Г.С. Палубецкис. Генерирование тестзадач разрезания графа с заданным оптимальным решением. —В межвузовском сб.: Автоматизация кон структорского проектирования в радиоэлектронике и ., вычислительной технике. Вильнюс, 1985, т. 5, с. 7 8 - 84,
1 6 0