Preview

Вопросы радиоэлектроники

Расширенный поиск

Верификация связности электрических соединений в топологии изделий радиоэлектронной аппаратуры

https://doi.org/10.21778/2218-5453-2019-8-21-25

Полный текст:

Аннотация

Рассмотрено решение задачи верификации связности электрических соединений в топологии сверхбольших интегральных схем (СБИС). Эффективное использование вычислительных ресурсов базируется на построении квазилинейных алгоритмов вычислительной (временной и емкостной) сложности. Рассматриваются следующие алгоритмы: заметания плоскости прямой для построения графа электрических соединений; выделения подмножеств связанных вершин в компонентах связности неориентированного графа большой размерности для определения электрически связанных контактов; установления изоморфизма компонентно-полных раскрашенных графов для сравнения восстановленного списка с исходным списком электрических соединений. Предложенное решение имеет временную сложность O(log2 и емкостную сложность O(), где 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


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2218-5453 (Print)
ISSN 2686-7680 (Online)