Lectionc3 (С.А. Ложкин - Лекции по основам кибернетики (2007)), страница 4

[32, 14]), который позволяет установитьпорядок роста функций Шеннона LK (n) и LC (n) (см. §5).Метод Шеннона заключается в выборе некоторого параметра q, 1 6 q 6 n, и построении схемы Σf , реализующейпроизвольную ФАЛ f (x1 , . . . , xn ) на основе ее разложения§2. Метод каскадов для КС и СФЭ25по части переменных (см. равенство (2.5) из гл. 1):σq+1· · · xσnn · fσ00 x0 ,xq+1_f x0 , x00 =σ 00 =(σ(2.4)q+1 ,...,σn )где x0 = (x1 , . . . , xq ) , x00 = (xq+1 , . .

. , xn ) и fσ00 (x0 ) == f (x0 , σ 00 ) при всех σ 00 , σ 00 ∈ B n−q . При этом схема Σf представляет собой корректную суперпозицию вида Σ00 (Σ0 ), гдеΣ00 — мультиплексор порядка (n − q) от адресных БП x00 ,информационные входы которого при выполнении указанной суперпозиции присоединяются к выходам универсального многополюсника Σ0 порядка q от БП x0 в соответствиис (2.4).Полагаяq = blog (n − 2 log n)c ,построим для ФАЛ f (x1 , . . .

, xn ) указанным выше способомКС (СФЭ в базисе Б0 ) Σf , где Σ00 — (2n−q , 1)-КД порядка(n − q) из §6 главы 2 (соответственно формула Fn−q из леммы 1.3), а Σ0 — универсальный многополюсник из леммы 2.1(соответственно леммы 1.6). Корректность построенной суперпозиции в случае КС обеспечивается разделительностьюКД. Для сложности полученной схемы Σf будут справедливы оценки n2n+22qL (Σf ) 6 2 · 22 + 2 · 2n−q 6+O,n − 2 log nn2если Σf ∈ UK , иL (Σf ) 6 22qn−q+4·28 · 2n+O6n − 2 log n2nn2,если Σf ∈ UC . Таким образом, доказано следующее утверждение.26Глава 3. Синтез и сложность управляющих системТеорема 2.1. Для функций Шеннона LK (n) и LC (n) выполнены соотношения:LK (n) . 4§32n,nLC (n) . 82n.nРегулярные разбиения единичного куба и моделирование функций переменными.

Асимптотика сложности контактного дешифратораПостроенное в §4 для синтеза СФЭ ДУМ G будем использовать и далее (см. §5–§7), хотя прямая реализация представления (4.1) в других классах схем не всегда возможна. Так, при синтезе формул (КС) все ФАЛ (соответственночасть ФАЛ) множества G должны быть «промоделированы» переменными или их отрицаниями. Для реализации такого моделирования в данном параграфе строятся специальные разбиения единичного куба, а затем рассматриваютсясвязанные с ними разложения ФАЛ, на основе которых синтезируются формулы в базисе {&, ∨, ¬}, являющиеся асимптотически оптимальными и по сложности, и по глубине дляпочти всех функций.Множество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q , если m < q, |δ| = 2m и всепрефиксы1 длины m наборов из δ различны. Заметим, чтоm-регулярному множеству δ, δ ⊆ B q , можно взаимнооднозначно сопоставить систему ФАЛ ψ = (ψ1 , .

. . , ψq−m ) изP2q−m (m) так, что набор α = (β, γ), где β ∈ B m и γ ∈ B q−m ,принадлежит δ тогда и только тогда, когда ψ (β) = γ. Заметим также, что любая ФАЛ g, g ∈ P2 (q), совпадает наm-регулярном множестве наборов δ, δ ⊆ B q , с некоторойФАЛ из P2 (m), если рассматривать P2 (m) как множество1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).§3. Регулярные разбиения единичного куба27всех ФАЛ из P2 (q) с несущественными БП xm+1 , . . . , xq . Приэтом любая ФАЛ из связанной с δ системы функций совпадает на δ с соответствующей БП куба B q .Для наборов β = (β1 , . . . , βq ) и α = (α1 , .

. . , αq ) черезβ ⊕ α будем обозначать набор вида (β1 ⊕ α1 , . . . , βq ⊕ αq ).Для множества δ, δ ⊆ B q , и набора α, α ∈ B q , определиммножество δ ⊕ α как множество различных наборов видаβ ⊕ α, где β ∈ δ, то есть множество, получающееся из множества δ сдвигом (параллельным переносом) на набор α.Заметим, что для m-регулярного множества δ, δ ⊆ B q , илюбого набора α, α ∈ B q , множество δ ⊕ α также являетсяm-регулярным. Если при этом ν (α) < 2q−m , то естьα = (0, . . . , 0, γ),| {z }mгде γ = (γ1 , . . . , γq−m ) и ν (γ) = ν (α), а множество наборовδ соответствует системе ФАЛ g = (g1 , .

. . , gq−m ), то множество наборов δ ⊕ α будет соответствовать системе ФАЛ(g1 ⊕ γ1 , . . . , gq−m ⊕ γq−m ), получающейся из системы g инвертированием некоторых ФАЛ.Лемма 3.1. Для любых натуральных m, λ и q = m + λ идля любой системы ФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ = (δ1 , . .

. , δ2q−m ) куба B qтакое, что любая ФАЛ gi на любой компоненте δj совпадает либо с одной из БП xm+1 , . . . , xq , либо с её отрицанием.Доказательство. Пусть δ = δ1 — m-регулярное множество,соответствующее системе ФАЛ g = (g1 , . . . , gλ ), и пусть δi =δ1 ⊕ α, где ν(α) = i − 1, для всех i, i = 1, . . . , 2q−m . Из построения системы множеств ∆ = (δ1 , . . . , δ2q−m ) следует, чтокаждое из них обладает требуемым свойствами, связаннымис можелированием ФАЛ из g с помощью БП.Покажем теперь, что ∆ — покрытие куба B q . Для этоговозьмем произвольный набор из B q вида (β, γ), где β ∈ B m28Глава 3. Синтез и сложность управляющих системи γ ∈ B q−m , а по нему найдем в множестве δ набор вида(β, γb), который имеется в δ в силу m-регулярности этогомножества. Следовательно,(β, γ) = (β, γb) ⊕ (0, . .

. , 0, γb ⊕ γ) = (β, γb) ⊕ α,| {z }mгде ν (α) < 2q−m . Таким образом, система ∆ образует покрытие куба B m .С другой стороны, из m-регулярности δ следует m-регулярность любого из множеств δi , i = 1, . . . , 2q−m , и поэтомуq−m2X|δi | = 2m 2q−m = 2q .i=1Следовательно, система ∆ образует разбиение куба B q .Лемма доказана.→−Лемма 3.2 (ср. [14]). Для системы ФАЛ Q n при n = 1, 2, 3, . . .выполняется неравенство n→ 2nК −Qn 6 2 + OL(3.1)nДоказательство. Выберем параметры m, q и λ так, чтоλ = 2n ,q = m + λ и q 6 n,(3.2)а затем рассмотрим m-регулярное множество наборов δ1 куба B q от БП x0 = (x1 , .

. . , xq ), связанное с системой ФАЛ→−Q m (x1 , . . . , xm ), которая состоит из всех ЭК вида xσ1 1 · · · xσmm ,где ν(σ1 , . . . , σm ) = j − 1, j ∈ [1, λ]. Построим для этойсистемы по лемме ?? разбиение ∆ = (δ1 , . . . , δ2q−m ) кубаσB q и заметим, что любая ЭК K(x0 ) = xσ1 1 · · · xq q , где σ 0 =(σ1 , . . . , σq ) ∈ δi , совпадает на множестве δi с одной из ЭК§3. Регулярные разбиения единичного куба29→−α 0системы Q m , то есть совпадет на нем с буквой xj σ0 , гдеσm + 1 6 jσ0 6 q, ασ0 ∈ B.Пусть, далее (1, 2λ )-КС Σ0 реализует столбец из ФАЛχ1 , . .

. , χ2λ , где χi (x0 ) — характеристическая ФАЛ множества δi , i ∈ 1, 2λ и получается из (1, 2q )-КД от БП x0 в результате соответствующего отождествления выходов (см. рис. ??).Заметим, что в силу указанных выше свойств разбиения ∆любая ЭК K = xσ1 1 · · · xσnn , где σ 0 = (σ1 , . . . , σq ) ∈ δi , 1 6 i 62λ , может быть представлена в видеαK = χi (x0 ) · xj σ0 · Kσ00 (x00 ),0σ(3.3)где x00 = (xq + 1, .

. . , xn ), σ 00 = (σq+1 , . . . , σn ).→−(&)Искомая (1, 2n )-КС Σn реализует каждую ЭК из Q m всоответствии с (3.3) и имеет вид, показанный на рис. ??.Пологаяm = blog (n − 3 log n)cполучим, чтоλ = 2m 6 n − 3 log n,2mq = m + λ 6 n − 2 log n,n − 3 log n>,2(&)то сложность построенной (1, 2n )-КС Σn , являющейся контактным дешифратором порядка n, удовлетворяет неравенствам: n2(&)n−mn−m+1q+1nL Σn6 λ2+2+262 +O,nиз которых вытекает неравенство 3.1.Лемма доказана.Следствие. Оценки леммы 3.2 и следствия из леммы 1.5дают асимптотическое равенствоLК (Qn ) ∼ 2n30Глава 3.

Синтез и сложность управляющих систем•appp 0ppffkk •pfNpNfpfff • a1~kkkkNNxNm+2 ..~kkkN .k~~ NNNN xk~kxm+p NN•YYYYYNYNYN k1 kkkk~~.00~kSe..eeeepepepp•SSSSS КД(x )~~~SSSxm+1 ppp•~~SSSpppp~SSSSpNfpfpxffff•~~Nfp•S~SNNNm+2 ..~~N .~xm+p NN~~•.~..@@a •~КД(x0 )@@xm+1 ppp•@@ppfff•@@kkfNpNfpNfxfm+2@@kk•pkkk@@NNN ...NNNkk@@kkkxm+p NNNkkN@@•YYYYYYNYN kkk..@@eeepSk•SКД(x00 ).@@ eeepepppx SSSSSSxm+1 ppp•SSS@@ pp2pppfff•SSS@@SSS •pfNpNfpfxfm+2SNNN ..N .{z}|xm+p NN a• p·2n−m −1xm+1b 00ΣРис. 3.1: к доказательству леммы 3.2Замечание. Используя представление (3.3) построим формулуF̂n (x1 , .

. . , xn , y0 , . . . , y2n −1 ) =λ___α 0=Ai x0 Kσ00 (x00 ) · xj σ0 yν(σ0 ,σ00 ) i=1σ 00 ∈B n−qσ 0 ∈δiσ(3.4)где Ai — совершенная ДНФ ФАЛ χi , i = 1, . . . , λ, котораяреализует мультиплексорную ФАЛ µn , бесповторна по БПy0 , . . . , y2n −1 и для которой при указанных выше значенияхпараметровn+2n log nR(F̂n ) 6 2+O 2, Alt (F̂n ) 6 6(3.5)n§4. Операция суперпозиции. Лемма Шеннона§431Операция суперпозиции и ее корректностьдля некоторых типов схем. Разделительныеконтактные схемы, лемма ШеннонаВ основе большинства структурных преобразований схемлежит ряд операций, которые обобщают операцию суперпозиции функций и используются для построения сложныхсхем из более простых.