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

Перейти к навигации Перейти к поиску
Строка 44: Строка 44:
'''Структура оптимальных по глубине K-покрытий'''
'''Структура оптимальных по глубине K-покрытий'''


Обозначим за M(v) K-покрытие (или эквивалентное решение отображения на K-LUT) исходной сети Nv вершины v. Если v является первичным входом, M(v) состоит только из самой вершины v. (Для простоты далее M(v) будет называться K-покрытием v). Имеет место следующая лемма.
Обозначим за M(v) K-покрытие (или эквивалентное решение отображения на K-LUT) исходной сети <math>N_v \;</math> вершины v. Если v является первичным входом, M(v) состоит только из самой вершины v. (Для простоты далее M(v) будет называться ''K-покрытием v''). Имеет место следующая лемма.




Лемма 1. Если Cv является K-допустимым конусом вершины v в K-покрытии M(v), то M(v) = fCvg+SfM(u): u 2 input(Cv)g, где M(u) – определенное K-покрытие вершины u. Соответственно, если Cv K-допустимым конусом вершины v и для каждой вершины u 2 input(Cv) множество M(u) является K-покрытием u, то M(v) = fCvg + SfM(u): u 2 input(Cv)g является K-покрытием v.
'''Лемма 1'''. Если <math>C_v \;</math> является K-допустимым конусом вершины v в K-покрытии M(v), то <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math>, где M(u) – определенное K-покрытие вершины u. Соответственно, если <math>C_v \;</math> является K-допустимым конусом вершины v и для каждой вершины <math>u \in input(C_v) \;</math> множество M(u) является K-покрытием u, то <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math> является K-покрытием v.




Источник — http://pco.iis.nsk.su/wega/index.php/Технологическое_отображение_ППВМ