Привязка логической схемы к библиотеке (Привязка логической схемы к библиотеке.pdf)
Описание файла
PDF-файл из архива "Привязка логической схемы к библиотеке.pdf", который расположен в категории "". Всё это находится в предмете "математические модели и методы логического синтеза сверхбольших интегральных схем" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Поиск структурныхсоответствий.Осень 2015Представление библиотекиINVNAND2AND2INV(I)NAND2(N)I1vt1.1N1vN2vt2.1t2.2I1N1vI1N2vt3.1t3.2Terminal(v)Рекурсивный алгоритм поискаструктурных соответствийMatch (u, v)if u.isLeaf() return Trueelseif v.isLeaf() return Falseif u.degree() != v.degree() return Falseif v.degree() == 1u_c := u.get_child()v_c := v.get_child()return Match(u_c,v_c)elseu_l := u.get_left_child()u_r := u.get_right_child()v_l := v.get_left_child()v_r := v.get_right_child()m_1 := Match(u_l,v_l) and Match(u_r,v_r)m_2 := Match(u_l,v_r) and Match(u_r,v_l)return m_1 or m_2Построение автоматаN1vt1.1N2I1N1v t2.2N2I1N2v t2.2N1vN2vINV(I)NAND2(N)t2.1t2.2Terminal(v)Построение автомата0N1102v02304I050v120N1vt1.1N2I1N1v t2.2N2I1N2v t2.2t1.1t2.1160N7118104N1vN2v11t1.3t2.2v229t1.1t1.2t2.13v12t2.1t2.2Обход целевого дереваVisit_Node (G, n)if n – корень дереваn.state:=Next(0, n.symbol)elsen.state:=Next(Next(n.parent.state,k),n.symbol)//вершина n является k-ым потомком родительской//вершины n.parentforeach потомка с вершины nVisit_Node(G, c)Post_Process(G,n)Обход целевого дереваPost_Process (G, n)n.b(i):=0if n.state == “ACCEPT”Set_Partial(G, n, n.state)foreach шаблона n.b(i):=n.b(i) or ∈() .
/2//C(n) – множество всех дочерних вершин вершины nDo_Reduce(G, n)Set_Partial(G, n, s)foreach строки длины 2j+1 обнаруженных в sn.b(i):=n.b(i) or 2.