Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры
Аннотация
Рассмотрено решение задачи верификации связности электрических соединений в топологии сверхбольших интегральных схем (СБИС). Эффективное использование вычислительных ресурсов базируется на построении квазилинейных алгоритмов вычислительной (временной и емкостной) сложности. Рассматриваются следующие алгоритмы: заметания плоскости прямой для построения графа электрических соединений; выделения подмножеств связанных вершин в компонентах связности неориентированного графа большой размерности для определения электрически связанных контактов; установления изоморфизма компонентно-полных раскрашенных графов для сравнения восстановленного списка с исходным списком электрических соединений. Предложенное решение имеет временную сложность O(N + N log2 N ) и емкостную сложность O(s + N ), где N – число элементов топологии и s – число контактов в исходной электрической схеме.
Об авторе
Г. Н. Брусникин
НИУ «Московский институт электронной техники»
Россия
Россия
Брусникин Геннадий Николаевич, кандидат технических наук, старший научный сотрудник, доцент
124498, Москва, Зеленоград, пл. Шокина, д. 1
Список литературы
1. Sharathkumar R., Maheshwari P., Gupta P. A practical algorithm for connectivity extraction for very large VLSI layouts. Conference Proceedings: 49th IEEE International Midwest Symposium on Circuits and Systems, San Juan, 2006.
2. Bentley J. L., Ottmann T. A. Algorithms for reporting and counting geometric intersections // IEEE Transactions on Computers. 1979. C 28 (9). P. 643–647.
3. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989. 478 с.
4. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ / 2 е изд. М.: Вильямс, 2005. 1296 с.
5. Потопахин В. В. Искусство алгоритмизации. М.: ДМК Пресс, 2011. 320 с.
6. Брусникин Г. Н., Замордуев С. А. Алгоритмы контроля топологии матричных БИС на соответствие электрической схеме // Электронная техника. 1984. № 6. С. 34–36.
7. Brusnikin G. N., Loshakov V. N. Methods and algorithms for hierarchical layout synthesis of VLSI circuits. Proceedings of a joint Symposium Information processing and Software Systems Design Automation, 1990. P. 348–353.
8. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. М.: Вильямс, 2007. 824 с.
Для цитирования:
Брусникин Г.Н. Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры. Вопросы радиоэлектроники. 2019;(8):21-25. https://doi.org/10.21778/2218-5453-2019-8-21-25
For citation:
Brusnikin G.N. Verification of connectivity of electrical connections in topology of radio electronic equipment products. Issues of radio electronics. 2019;(8):21-25. (In Russ.) https://doi.org/10.21778/2218-5453-2019-8-21-25
Просмотров: 33
Послать статью по эл. почте 