Розв’язання задач функціональної компоновки і верифікації при проектуванні конструктивів цифрової апаратури

Abstract

В дисертації отримав свій подальший розвиток метод оптимальної (паралельної) редукції стосовно задач функціональної декомпозиції схем і верифікації проектних рішень на етапі проектування конструктивів цифрової (радіоелектронної) апаратури. Особливу увагу приділено шляхам розв’язання центральної з розглянутих задач – встановленню еквівалентності схем. В роботі досліджено два типи моделей для розв’язання задач: графові і теоретико-множинні, що мають ієрархічну структуру, яка дозволяє вибирати необхідний степінь деталізації опису схем, представлених як описом множини елементів, класифікацією яких встановлюється існування необхідних умов еквівалентності схем, так і описом множини ланцюгів, по якому визначається степінь перекриття схем, що дозволило вирішити такі задачі функціональної компоновки, як типізація і покриття схем підсхемами із заданого набору. Для графових моделей схем запропоновано нові алгоритми встановлення ізоморфізму графів і пошуку в графі ізоморфних підграфів на основі формування ізоморфних бінарних дерев редукції графових моделей. Диссертация посвящена разработке методов, моделей и алгоритмов установления эквивалентности схем с целью их использования при решении задач функциональной компоновки и верификации результатов проектирования. Исследованы существующие методы решения задач, включая решение задачи установления изоморфизма графов. Обосновано использование метода оптимальной редукции, имеющего полиномиальную вычислительную сложность, что является существенным ввиду NP-полного характера решаемых задач. Метод оптимальной редукции получил своё дальнейшее развитие применительно к задачам установления изоморфизма графов и функциональной декомпозиции схем; он позволяет, в отличие от других методов, за счёт параллелизма процесса редукции алгоритмически решать задачи типизации и выделения в графе изоморфных подграфов. Усовершенствованы теоретико-множественные и графовые модели элементов и схем, а также впервые предложена и реализована модель схемы в виде множества цепей, каждая из которых описана регламентированным кортежом параметров, что, в отличие от существующих моделей позволяет установить степень перекрытия пары схем. Предложен алгоритм установления изоморфизма простих графов, который, в отличие от существующих, для уменьшенияи нструментальной погрешности метода исследует как изоморфизм пары графов, так и их дополнений, что оказалось эффективным, в том числе, и для регулярних структур. Для установления изоморфизма графов (мультиграфов, сетей) использованы инварианты в виде бинарных деревьев оптимальной редукции, что позволяет свести задачу установления изоморфизма графов к задаче установления изоморфизма их деревьев редукции. Для решения задачи типизации обоснован и предложен алгоритм выделения в графе изоморфных подграфов с весовой функцией на вершинах, значение которой опредиляется предварительной классификацией элементов схем. Приводится формальная постановка задачи установления эквивалентности схем и путие её решения. Исследованы и развиты теоретико-множественные модели схем на основе описаний множества элементов и множестав цепей, каждое из которых имеет несколько уровней, отличающихся детализацией представления элементов и цепей схем на основе типов элементов и типов задействованных контактов элементов. Разработаны и реализованы классификаторы элементов и цепей, позволяющие установить наличие необходимых условий решения поставленных задач и степень взаимного перекрытия двух схем. Разработано и описано информационное обеспечение для решения поставлених задач.In dissertation the method of optimal (parallel) reduction has got the further development applying to the tasks of scheme functional decomposition and verification of project decisions on the stage of digital (radio and electronic) devices construction design. The special attention is paid to ways of decision of central of the examined tasks − setting the scheme equivalence. Two types of tasks decision models are studied in the work: (a) graph and (b) theoretic-and-set which have a hierarchical structure and allow choosing necessary degree of scheme description detalization presented by description of elements set, classification of which is set the existence of necessary terms of scheme equivalence as well as description of chains set by which the degree of scheme covering is determined. This has allowed the decision of the following tasks of functional decomposition: typification and coverage of scheme with subscheme from a given set. For the scheme’s graph models the new algorithms of isomorphousness of graph setting and selection of isomorphous subgraphs in the graph are offered on the base of isomorphous binary trees of graph models reduction forming.