Технологическое отображение ППВМ: различия между версиями

В качестве входных данных для алгоритма технологического отображения для ППВМ на основе таблицы поиска является булева сеть общего вида, которая может моделироваться ориентированным ациклическим графом N = (V, E). Вершина v 2 V может представлять либо источник логического сигнала вне сети, в таком случае она не имеет входящего ребра и называется первичным входом (primary input, PI); либо логический вентиль, в таком случае она имеет одно или несколько входящих ребер от первичных входов и других вентилей, являющихся логическими входами. Если логический выход вентиля также используется вне сети, соответствующая вершина является первичным выходом (primary output, PO) и может не иметь исходящих ребер, если ее результат используется только вне сети.

Если hu; vi 2 E, u называется разветвлением на входе (fanin) вершины v, и v – разветвлением на выходе (fanout) вершины u. Для вершины v обозначим за input(v) множество ее fanin; аналогичным образом для подграфа H обозначим за input(H) множество отдельных вершин вне H, являющихся fanin для вершин из H. Если существует прямой путь в N из вершины u в вершину v, u называется предком v, а v – потомком u. Входной сетью вершины v, обозначаемой Nv, является подграф, содержащий вершину v и всех ее предков. Конусом не являющейся первичным входом вершины v, обозначаемым Cv, является подграф Nv, содержащий v и, возможно, некоторых из ее предков, не являющихся первичными входами, таких, что для любой вершины u 2 Cv существует путь из u в v по Cv. Если |input(Cv)| < K, Cv называется K-допустимым конусом. Сеть N является K-ограниченной, если каждая вершина, не являющаяся первичным входом, имеет K-допустимый конус. Разрез по не являющейся первичным входом вершине v представляет собой биразбиение (X, X0) вершин из Nv, такое, что X0 является конусом v; input(X0) называется сечением (X, X0), и n(X;X0) = |input(X0)| – размером разреза. Если n(X; X0) < K, то (X, X0) является K-допустимым разрезом. Обозначим мощность разреза (X, X0) как vol(X, X0) = |X0|.

Топологический порядок вершин в сети N представляет собой линейное упорядочение вершин, в котором каждая вершина встречается после всех своих предков перед любым из своих потомков. Подобное упорядочение всегда возможно для ациклического графа.