OK-metodichka-2010-part3 (С.А. Ложкин - Лекции по основам кибернетики (2009)), страница 5

Àñèìïòîòè÷åñêè íàèëó÷øèéìåòîä Î. Á. Ëóïàíîâà äëÿ ñèíòåçàñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîââ áàçèñå {&, ∨, ¬}Ðàññìîòðèì ìåòîä ñèíòåçà ñõåì èç êëàññà UC , êîòîðûé áûëïðåäëîæåí Î.Á. Ëóïàíîâûì [14] è ïîçâîëèë âïåðâûå óñòàíîâèòü àñèìïòîòèêó ôóíêöèè Øåííîíà LC (n). Ýòîò ìåòîä,êàê è ìåòîä Øåííîíà (ñì. Ÿ3), îñíîâàí íà ïðåäñòàâëåíèèðåàëèçóåìîé ÔÀË f, f ∈ P2 (n), â âèäå (3.4) è ïîñòðîåíèèèñêîìîé ÑÔÝ Σf , ðåàëèçóþùåé ÔÀË f , êàê ñóïåðïîçèöèèñõåì âèäà Σf = Σ00 (Σ0 ). Ïðè ýòîì ñõåìà Σ00 ïî-ïðåæíåìó ÿâëÿåòñÿ ìóëüòèïëåêñîðîì ïîðÿäêà (n − q) îò àäðåñíûõ ÁÏx00 = (xq+1 , .

. . , xn ), à ñõåìà Σ0 ðåàëèçóåò âñå ÔÀË âèäàfσ00 (x0 ), ãäå x0 = (x1 , . . . , xq ) , σ 00 ∈ B n−q , è fσ00 (x0 ) = f (x0 , σ 00 ).Îäíàêî, â îòëè÷èå îò ìåòîäà Øåííîíà, êàæäàÿ ÔÀË fσ00 (x0 )áåðåòñÿ íå ñ âûõîäà óíèâåðñàëüíîãî ìíîãîïîëþñíèêà îò ÁÏx0 , à ðåàëèçóåòñÿ íà âûõîäå Σ0 êàê äèçúþíêöèÿ íåêîòîðûõÔÀË, âûáðàííûõ èç ñïåöèàëüíîãî ìíîæåñòâà G, G ⊆ P2 (q),ðåàëèçîâàííîãî íà âûõîäàõ ñîîòâåòñòâóþùåé ïîäñõåìû ñõåìûΣ0 .Ìíîæåñòâî ÔÀË G, G ⊆ P2 (m), íàçûâàåòñÿ äèçúþíêòèâíî-óíèâåðñàëüíûì ìíîæåñòâîì (ÄÓÌ) ïîðÿäêà m è ðàíãà p, åñëè ëþáàÿ ÔÀË g, g ∈ P2 (m), ìîæåò áûòü ïðåäñòàâëåíà â âèäåg = g1 ∨ .

. . ∨ gp ,ãäå gi ∈ G ïðè âñåõ i, i = 1, . . . , p. Ñòàíäàðòíûé ñïîñîá ïîñòðîåíèÿ òàêèõ ìíîæåñòâ ñâÿçàí ñ ðàçáèåíèÿìè åäèíè÷íîãîêóáà.Ïóñòü Π = (π1 , . . . , πp ) ðàçáèåíèå êóáà B m , è ïóñòü äëÿâñåõ i, i = 1, . . . , p, ÔÀË ψi (x1 , . . . , xm ) õàðàêòåðèñòè÷åñêàÿ ÔÀË ìíîæåñòâà πi , à G(i) ìíîæåñòâî âñåõ òåõ ÔÀË36Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìg, g ∈ P2 (m), êîòîðûå îáðàùàþòñÿ â 0 âíå πi . Çàìåòèì, ÷òîìíîæåñòâî ÔÀË G âèäàG = G(1) ∪ . . .

∪ G(p)ÿâëÿåòñÿ ÄÓÌ ïîðÿäêà m è ðàíãà p. Äåéñòâèòåëüíî, ëþáàÿÔÀË g, g ∈ P2 (m), ìîæåò áûòü ïðåäñòàâëåíà â âèäå(5.1)g = g1 ∨ . . . ∨ gp ,ãäå gi = ψi g è, ñëåäîâàòåëüíî, gi ∈ G(i) äëÿ âñåõ i, i = 1, . . . , p.Çàìåòèì òàêæå, ÷òî ìîùíîñòü ìíîæåñòâà G(i) , i = 1, . . . , p,ðàâíà 2si , ãäå si = |πi |, è ÷òî ìíîæåñòâî G(i) ∩ G(j) ñîñòîèò èç ÔÀË, òîæäåñòâåííî ðàâíîé 0, åñëè 1 6 i < j 6 p.Ñëåäîâàòåëüíî,p ¯p¯XX¯ (i) ¯λ = |G| =2si 6 p2s ,¯G ¯ − (p − 1) 6i=1i=1ãäås = max si .16i6pÓêàçàííîå ÄÓÌ G áóäåì íàçûâàòü ÄÓÌ, ñâÿçàííûì ñðàçáèåíèåì Π, êîòîðîå áóäåì ñ÷èòàòü ñòàíäàðòíûì ÄÓÌïîðÿäêà m è âûñîòû s, ãäås 62m ,(5.2)åñëè âûïîëíåíû ñîîòíîøåíèÿ1.»p=¼2m,ss1 = s2 = · · · = sp−1 = s,sp = 2m − (p − 1) s 6 s.(5.3)Ÿ5. Ìåòîä Ëóïàíîâà ñèíòåçà ÑÔÝg1 g2 . .

.g2s g2s +1. . .g2s+1 −1 . . . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...0 1 ... 10...0...0...00 0 ... 10...0...0...0. . .. . .. . ......................0...0...0...00 0 ... 01...1...0...00 0 ... 00...1...0...00......0 0 ... 0...0.....................1.........O...0 0 ... 1. . .. . .. . ....37s=s1²O...s=s20²...O...0 0 ... 00...0...0...0πp−1 ...0 0 ...

00...0...0...0πp .... . .. . .. . ............................0 0 ... 00...0...0...0...0 0 ... 00...0...1...1...0 0 ... 00...0...0...1. . .. . .. . ..........0 0 ... 0...o2s/o0......2s −1............0/......o02sp−1s=sp−1²O...sp 6s0/²Ðèñ. 5.1: ê îïðåäåëåíèþ äèçúþíêòèâíî-óíèâåðñàëüíîãîìíîæåñòâà2. Π = (π1 , .

. . , πp ) ðàçáèåíèå êóáà B m íà ïîñëåäîâàòåëüíûå îòðåçêè, òî åñòü òàêîå ðàçáèåíèå, ÷òî íîìåðëþáîãî íàáîðà èç ìíîæåñòâà πi ìåíüøå íîìåðà ëþáîãî íàáîðà èç ìíîæåñòâà πj , åñëè i < j .Êîìïîíåíòû ðàçáèåíèÿ Π áóäåì ïðè ýòîì íàçûâàòü ïîëîñàìè ÄÓÌ G, à ÔÀË ψ1 , . . . , ψp åãî õàðàêòåðèñòè÷åñêèìè ÔÀË. Çàìåòèì, ÷òî õàðàêòåðèñòè÷åñêèå ÔÀË ïîïàðíîîðòîãîíàëüíû, òî åñòü îäíîâðåìåííî â 1 íå îáðàùàþòñÿ, èïðèíàäëåæàò G. Çàìåòèì òàêæå, ÷òî ïðåäñòàâëåíèå (5.1) â38Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìñëó÷àå ñòàíäàðòíîãî ÄÓÌ G ðàâíîñèëüíî ïðåäñòàâëåíèþ:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(5.4)Òàáëèöà çíà÷åíèé ÔÀË ñòàíäàðòíîãî ÄÓÌ G ïðèâåäåíà íàðèñ. 5.1.Èç ïðîâåäåííûõ ïîñòðîåíèé è îòìå÷åííûõ âûøå ñâîéñòâñòàíäàðòíîãî ÄÓÌ âûòåêàåò ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ.Ëåììà5.1.

Äëÿ ëþáûõ íàòóðàëüíûõ p, m è s, ãäå p =§ ¨2ms, ñóùåñòâóåò ÄÓÌ G ïîðÿäêà m è ðàíãà p òàêîå, ÷òî:1. λ = |G| 6 p2s ;2. â G èìååòñÿ ñèñòåìà èç p îðòîãîíàëüíûõ ÔÀË ψ1 , . . . , ψp ,îáëàäàþùèõ òåì ñâîéñòâîì, ÷òî äëÿ ëþáîé ÔÀË g ,g ∈ P2 (m), è íåêîòîðûõ ÔÀË g1 , . . . , gp èç G ñïðàâåäëèâî íå òîëüêî ïðåäñòàâëåíèå (5.1), íî è ïðåäñòàâëåíèå (5.4).Òåîðåìà 5.1. Äëÿ ëþáîé ÔÀË f, f ∈ P2 (n), ñóùåñòâóåòðåàëèçóþùàÿ åå ÑÔÝ Σf , Σf ∈ UC , òàêàÿ, ÷ò5 log n + O (1)2n1+.L (Σf ) 6nn(5.5)Äîêàçàòåëüñòâî.

Ïóñòü x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn )è fσ00 (x0 ) = f (x0 , σ 00 ) äëÿ âñåõ σ 00 èç B n−q . Ïóñòü, äàëåå,Σ00 ìóëüòèïëåêñîð ïîðÿäêà (n − q) îò àäðåñíûõ ÁÏ x00 èèíôîðìàöèîííûõ ÁÏ y = (y0 , . . . , y2n−q −1 ), êîòîðûé ïîñòðîåí â ñîîòâåòñòâèè ñ ëåììîé 1.4, ïðåäñòàâëÿåò ñîáîé ôîðìóëóFn−q è ðåàëèçóåò ìóëüòèïëåêñîðíóþ ÔÀË µn−q (x00 , y).Ïóñòü s íåêîòîðûé ïàðàìåòð, óäîâëåòâîðÿþùèé (5.2),à G ñòàíäàðòíîå ÄÓÌ ïîðÿäêà m = q è âûñîòû s, óäîâëåòâîðÿþùåå òðåáîâàíèÿì ëåììû 5.1.

Îáîçíà÷èì ÷åðåç ΣGŸ5. Ìåòîä Ëóïàíîâà ñèíòåçà ÑÔÝ39−→ÑÔÝ, êîòîðàÿ ðåàëèçóåò ñèñòåìó ÔÀË G è ïðåäñòàâëÿåòñîáîé îáúåäèíåíèå ñõåì, ïîñòðîåííûõ äëÿ êàæäîé èç íèõ âñîîòâåòñòâèè ñ ëåììîé 1.2. Çàìåòèì, ÷òî, â ñèëó ëåììû 1.4,(1.3) è ëåììû 5.1, âûïîëíåíû íåðàâåíñòâà¡ ¢L Σ00 6 4 · 2n−q ,L (ΣG ) 6 3p2s+q .(5.6)Ñõåìà Σ0 ñîäåðæèò ÑÔÝ ΣG â êà÷åñòâå ïîäñõåìû è ðåàëèçóåò êàæäóþ ÔÀË fσ00 (x0 ), ãäå σ 00 ∈ B n−q , íà îäíîì èç ñâîèõ âûõîäîâ êàê ÔÀË g (x0 ) âèäà (5.1) ñ ïîìîùüþ ÑÔÝ èç(p − 1) ÔÝ ∨, âõîäû êîòîðîé ïðèñîåäèíåíû ê ñîîòâåòñòâóþùèì âûõîäàì ΣG .

Èñêîìàÿ ÑÔÝ Σf èìååò âèä Σf = Σ00 (Σ0 )è ðåàëèçóåò ÔÀË f â ñîîòâåòñòâèè ñ ðàçëîæåíèåì (3.4). Äëÿíåå, â ñèëó (5.6), áóäóò âûïîëíÿòüñÿ íåðàâåíñòâà¡ ¢L (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,èç êîòîðûõ, âûáðàâ çíà÷åíèÿ ïàðàìåòðîâs = dn − 5 log ne ,m = q = d2 log ne ,óäîâëåòâîðÿþùèå (5.2), â ñîîòâåòñòâèè ñ ëåììîé 5.1 ïîëó÷èì2n+OL (Σf ) 6n − 5 log nµ2nn2¶=2n=nÒåîðåìà äîêàçàíà.µ¶5 log n + O (1)1+.n40Ãëàâà 3. Ñèíòåç è ñëîæíîñòü óïðàâëÿþùèõ ñèñòåìÑëåäñòâèå. Èç (5.5) è (2.13) (ñì. òàêæå ñëåäñòâèå 1 èçòåîðåìû 2.1) âûòåêàåò, ÷òîLC (n) ∼2n.nÎòìåòèì, â çàêëþ÷åíèå, ÷òî â ñîîòâåòñòâèè ñ (5.5) èñëåäñòâèåì 2 èç òåîðåìû 2.1 ñëîæíîñòü LC (f ) äëÿ ïî÷òèâñåõ ÔÀË f, f ∈ P2 (n), àñèìïòîòè÷åñêè ðàâíà ôóíêöèèØåííîíà LC (n), òî åñòü ñëîæíîñòè ñàìîé ñëîæíîé ÔÀË èçP2 (n).

Òåì ñàìûì, â îòëè÷èå îò êëàññà ÄÍÔ (ñì. Ÿ7 ãëàâû 1), â êëàññå ñõåì UC èìååò ìåñòî ò. í. ýôôåêò Øåííîíà àñèìïòîòè÷åñêîå ðàâåíñòâî ñëîæíîñòè ïî÷òè âñåõ ÔÀËè ñëîæíîñòè ñàìîé ñëîæíîé ÔÀË îò çàäàííîãî ÷èñëà ÁÏ,ñòðåìÿùåãîñÿ ê áåñêîíå÷íîñòè.Ÿ6 Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçàêîíòàêòíûõ ñõåìÇàìåòèì ñíà÷àëà, ÷òî àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ÑÔÝ èç Ÿ5 áåç ñóùåñòâåííûõ èçìåíåíèé ïåðåíîñèòñÿ íàêëàññ êîíòàêòíî-âåíòèëüíûõ ñõåì (ÊÂÑ), â êîòîðûõ íàðÿäóñ êîíòàêòàìè ìîæíî èñïîëüçîâàòü ¾âåíòèëè¿, òî åñòü îðèåíòèðîâàííûå ðåáðà, ïðîâîäÿùèå òîëüêî â íàïðàâëåíèè ñâîåéîðèåíòàöèè.

Äåéñòâèòåëüíî, äëÿ ëþáîé ÔÀË f , f ∈ P2 (n),e f ìîæåò áûòü ïîëó÷åíà íà îñðåàëèçóþùàÿ åå (1, 1)-ÊÂÑ Σíîâå ðàçëîæåíèÿ (3.4) òàê æå, êàê è ÑÔÝ Σf èç òåîðåìû 5.1.Îíà ÿâëÿåòñÿ ðåçóëüòàòîì êîððåêòíîé ñóïåðïîçèöèè (ñì. Ÿ9e f = Σ00 (Σ0 ), ãäå Σ00 (2n−q , 1)-ÊÄ îò ÁÏãëàâû 2) âèäà Σ00n−qx , à (1, 2 )-ÊÂÑ Σ0 ðåàëèçóåò ñèñòåìó âñåõ ÔÀË âèäàfσ00 (x0 ) , σ 00 ∈ B n−q .

Ïðè ýòîì ñõåìà Σ0 ïî-ïðåæíåìó ñîäåðæèò â êà÷åñòâå ïîäñõåìû (1, λ)-ÊÑ ΣG , ðåàëèçóþùóþ ñèñòå−→ìó ÔÀË G íà îñíîâå ëåììû 1.2, è ðåàëèçóåò êàæäóþ ÔÀËg (x0 ) òèïà fσ00 (x0 ) íà îñíîâå åå ïðåäñòàâëåíèÿ (5.1) â âèäå äèçúþíêöèè g = g1 ∨ · · · ∨ gp ñ ïîìîùüþ ïðèñîåäèíåíèÿŸ6. Àñèìïòîòè÷åñêè íàèëó÷øèé ìåòîä ñèíòåçà ÊÑqqqqqqqqqqqqqqΣG1 •MqMMMMMMMMMMMMMM41gN1• NNNNNN..

NNNr•9& g. rrrrrrrrr•...gpa)qqqqqqqqqqqqqqΣG1 •MqMMMMMMMMMMMMMMgN1• NNNNψNN1.. NNNr• g. rrrrrrrψprr•...gpb)Ðèñ. 6.1: Êîððåêòíàÿ ðåàëèçàöèÿ äèçúþíêöèè ÔÀËg1 , . . . , gp â êëàññàõ ÊÂÑ è ÈÊÑâõîäîâ âåíòèëüíîé çâåçäû ïîðÿäêà p ê ñîîòâåòñòâóþùèì âûõîäàì ÊÑ ΣG (ñì. ðèñ. 6.1a, à òàêæå ðèñ. 9.2c èç ãëàâû 2),êîòîðîå ÿâëÿåòñÿ êîððåêòíîé ñóïåðïîçèöèåé. Ñëîæíîñòü ïîe f ïðè òåõ æå çíà÷åíèÿõ ïàðàìåòðîâ, ÷òî èñòðîåííîé ÊÂÑ Σâ òåîðåìå 5.1, áóäåò óäîâëåòâîðÿòü íåðàâåíñòâó 5.5.Íàïîìíèì (ñì.

Ÿ5), ÷òî â ñèëó ñïåöèôèêè ñòàíäàðòíîãî ÄÓÌ G âìåñòî ïðåäñòàâëåíèÿ (5.1) äëÿ ÔÀË g ìîæíîèñïîëüçîâàòü ýêâèâàëåíòíîå (5.1) ïðåäñòàâëåíèå (5.4) âèäàg = ψ1 · g1 ∨ · · · ∨ ψp · gp(6.1)è íà åãî îñíîâå ðåàëèçîâàòü ÔÀË g ñ ïîìîùüþ êîððåêòíîé ñóïåðïîçèöèè ò.í. èòåðàòèâíî-êîíòàêòíûõ ñõåì, ïîêàçàííîé íà ðèñ. 6.1b, ãäå ÔÀË ψ1 , . .