С.А. Ложкин - Элементы теории синтеза дискретных управляющих систем (1160764), страница 4
Текст из файла (страница 4)
Из (4.14) с учётом нижней оценки §3 вытекает соотношениеLИКС(n) ∼ ρ̂ББ§52n.nАсимптотически наилучший метод синтеза формул и контактныхсхем в произвольном базисеПри синтезе СФЭ в базисе Б = {Ei }bi=1 мы использовали некоторые формулы F& , F∨и F¬ из UФБ , реализующие ФАЛ x1 · x2 , x1 ∨ x2 и x1 соответственно, для моделированияконъюнктивных и дизъюнктивных представлений ФАЛ. При этом возможность такогомоделирования и его сложность не налагали на данные формулы каких-либо структурныхили параметрических ограничений. В то же время при использовании формул F& , F∨ , F¬для аналогичного моделирования конъюнктивных и дизъюнктивных представлений ФАЛв классе UФБ необходимо обеспечить отсутствие «внутренних» ветвлений в получающихсясхемах за счёт определенных ограничений на их структуру.Напомним, что БП, встречающаяся в записи формулы только один раз, считается бесповторной БП этой формулы и что формула, все БП (соответственно, все существенные БП)которой бесповторны, называется бесповторной (соответсвенно, квазибеспоторной).
В [3]было доказано следующее утверждение.Лемма 5.1. Существуют квазибесповторные формулы F¬ , F& и F∨ над базисом Б, которыереализуют ФАЛ x1 , x1 · x2 и x1 ∨ x2 соответственно.16Глава 1.Напомним, далее, что (см., например, [3]) множество δ, δ ⊆ B q называется m-регулярныммножеством наборов куба B q , если m < q, |δ| = 2m и все префиксы1 длины m наборов из δразличны. Заметим, что m-регулярному множеству δ, δ ⊆ B q , можно взаимнооднозначносопоставить систему ФАЛ g = (g1 , .
. . , gq−m ) из P2q−m (m) так, что набор α = (β, γ), гдеβ ∈ B m и γ ∈ B q−m , принадлежит δ тогда и только тогда, когда g(β) = γ. Заметим также,что любая ФАЛ g, g ∈ P2 (q), совпадает на m-регулярном множестве наборов δ, δ ⊆ B q , снекоторой ФАЛ из P2 (m), если рассматривать P2 (m) как множество всех ФАЛ из P2 (q) снесущественными БП xm+1 , . . .
, xq . При этом любая ФАЛ из связанной с δ системы функцийсовпадает на δ с соответствующей БП куба B q .Распространим операцию сложения двоичных наборов (слов) по модулю 2 на тот случай,когда длина второго слагаемого может быть больше длины первого. Для наборов α == (α1 , . . . , αm ) ∈ B m и β = (β1 , . .
. , βn ) ∈ B n , где n > m, определим их сумму α ⊕ β какнабор γ = (γ1 , . . . , γn ) ∈ B n , который представляет собой поразрядную сумму по модулю 2префикса длины n набора (α, . . . , α) ∈ B a , где a = dn/me, с набором β и заметим, чтопри этом уравнение α ⊕ β = γ имеет единственное относительно β решение при любых α,α ∈ B m , и γ, γ ∈ B n .На основе введённой операции при любых β, β ∈ B t , и λ 6 t обычным образомопределяется сумма δ ⊕ β, где δ ⊆ B λ , а также сумма g ⊕ β, где g = (g1 , .
. . , gλ ) ∈ P2λ (m).При этом последняя сумма является набором длины t, который по-прежнему состоит из ФАЛсистемы g или их отрицаний и задаёт m-регулярное множество наборов куба B t . Заметимтакже, что любая ФАЛ системы g хотя бы один раз входит в систему g ⊕ β без отрицания,если для каждого i, i = 1, . . . , λ, хотя бы один из разрядов набора β с номером i + λ · j, где0 6 j 6 dt/λe и λ · j 6 t, равен 0.Пусть G ⊆ P2 (m) и |G| = λ, а ∆ = (δ1 , . . .
, δ2q−m ), где q > m, — разбиение куба B qна m-регулярные компоненты. Будем говорить, что разбиение ∆ моделирует ФАЛ из Gс помощью БП или их отрицаний, если для любого i, i ∈ [1, 2q−m ], любая ФАЛ g, g ∈ G,совпадает на δi с некоторой буквой xσj , где 1 6 j 6 q и σ ∈ B. Компонента δi считается приэтом хорошей компонентой разбиения ∆ (относительно множества G) в том случае, когдадля любой ФАЛ g, g ∈ G, указанное совпадение имеет место при σ = 1.Лемма 5.2.
Пусть G ⊆ P2 (m), |G| = λ, q = m + aλ и пусть δi , i = 1, . . . , 2q−m , — m-регу→−лярное разбиение куба B q , которое соответствует системе ФАЛ G ⊕ β, где β ∈ B q−mи ν(β) = i − 1. Тогда система множеств ∆ = (δ1 , . . . , δ2q−m ) образует m-регулярное разбиение куба B q , которое моделирует ФАЛ из G с помощью БП или их отрицаний и имеет приэтом долю «плохих» компонент не больше, чемλ.2aДоказательство. Покажем сначала, что система множеств ∆ является разбиением куба B q .Для этого в силу того, что мощность каждого из них равна 2m , достаточно убедиться втом, что ∆ — покрытие куба B q , то есть любой набор γ, γ ∈ B q , входит хотя бы в одно измножеств δi , i ∈ [1, 2q−m ].1Для слова (набора) α вида α = βγ слово β (γ) считается его префиксом (соответственно суффиксом).§5.17Действительно, представим набор γ в виде γ = (α, γ̂), где α ∈ B m , и найдём набор β, β ∈→−B q−m , который является единственным решением уравнения G (α) ⊕ β = γ̂. Следовательно,γ ∈ δi , где ν(β) = i − 1, и система множеств ∆ является разбиением куба B q .Заметим, что в силу отмеченных выше свойств операции сложения по модулю 2, разбиение ∆ обладает всеми необходимыми для моделирования множества ФАЛ G свойствами, ичто при этом число его «плохих» компонент не больше, чем λ · 2q−m−a .Лемма доказана.Теорема 5.1.
Для любой ФАЛ f , f ∈ P2 (n) существует реализующая её формула Ff ,Ff ∈ UФБ , такая, что2n log log n ± O(1) L Ff 6 ρБ1+.log nlog n(5.1)Доказательство. Выберем ФЭ Ej , введём натуральные параметры m, s, t, p, l, λ и определим разбиение Π, формулу Ft , ФАЛ ψ, ψ-УМ G порядка m так, как это было сделано вдоказательстве теоремы 4.1 и так, чтобы выполнялись соотношения (4.5)–(4.9).Выберем, далее, натуральные параметры q и r так, чтоq = m + aλ 6 n(5.2)и построим по лемме 5.2 для множества ФАЛ G соответствующее m-регулярное разбиение ∆ = (δ1 , .
. . , δ2q−m ) куба B q от БП x0 = (x1 . . . xq ). Заметим, что для произвольнойФАЛ g(x0 ) и любого i, i ∈ [1, 2q−m ], в силу ψ-универсальности множества G, m-регулярности разбиения ∆ и возможности моделировать ФАЛ из G на компонентах ∆ с помощью БПили их отрицаний всегда найдутся такие натуральные числа j1 , . . . , jp из [m + 1, q] и булевы константы α1 , . . . , αp , которые равны 1, если δi — «хорошая» компонента, и для которыхравенствоα g x0 = ψ xαj11 , . .
. , xjpp(5.3)выполняется на любом наборе из δi .Возьмём (см. (4.10)) разложение ФАЛ f по БП x00 = (xq+1 . . . xn ) и продолжим его наоснове (5.3) так, чтоq−m _ 2_ _αp,i,σ00 1,i,σ 00000000f x ,x =Kσ00 x · fσ00 x =x xi · Kσ00 x00 · ψ xαj1,i,σ,...,xjj,i,σ00 ,00σ 00 ∈B n−qгдеx (x0 ) — характеристическаяii=1i(5.4)σ 00 ∈B n−qФАЛ компоненты δi разбиения ∆. Искомая формула Ffполучается из последнего представления (5.4) ФАЛ f следующим образом:1) характеристическая ФАЛ x , i ∈ [1, 2q−m ], реализуется по своей совершенной ДНФ;i2) мультиплексорная ФАЛ µn−q порядка (n − q) от адресных БП x00 , связанная с разложением f по этим БП, реализуется с помощью бесповторной по информационным БПформулы из UC сложности не больше, чем 4 · 2n−q (см. [3]);18Глава 1.3) каждая ФАЛ вида (5.3) реализуется одной формулой Fp с необходимыми инверсиямиеё БП в случае «плохой» компоненты δi ;4) все используемые при реализации формул из пунктов 1-3 элементы базиса Б0 заменяются соответствующими им бесповторными формулами F& , F∨ , F¬ из леммы 5.1.Для сложности построенной таким образом формулы Ff будет (ср.
с (4.12)) справедливонеравенствоt · λL Ff 6 Lj · t · 2n−m + O 2n−m 1 + a + q · 2q ,2которое при значениях параметровm = b3 log log nc ,s = blog n − 3 log log nc − 1,(5.5)a = dlog ne − 1удовлетворяющих при достаточно больших n условиям (5.2), даёт оценку (5.1).Теоремa доказана.Теорема 5.2. Для любой ФАЛ f , f ∈ P2 (n), существует реализующая её КС Σf , Σf ∈ UКБ ,такая, что2nL(Σf ) 6 πБnlog n.1+O √n(5.6)Доказательство.
Найдём среди ФПЭ базиса Б, Б = {Ki }bi=1 , элемент Kj , для которогоLj = πБ (см. §2), то естьLj = min Li = πБ .16i6bПусть для определённости, из базисной ФАЛ ϕj (см. §2) подстановкой констант можноb и Ǩ получающиесяполучить ФАЛ x1 , а из ФАЛ ϕr , 1 6 r 6 b, — ФАЛ x1 . Обозначим через Kпри этом из Kj и Kr замыкающий и размыкающий контакты соответственно и положимb = Lj , Ľ = Lr .Lb и Ǩ в соответствии с асимптотически наилучшимБудем строить КС Σf из контактов Kметодом синтеза КС в стандартном базисе (см. [3, Гл. 4, §7]) с использованием леммы 5.2,для того, чтобы долю контактов Ǩ в Σf можно было сделать бесконечно малой.Пусть m, s и t — натуральные числа такие, чтоms62 ,2m,t=s(5.7)а Π = (π1 , . . . , πt ) — разбиение куба B m на последовательные отрезки длины не большечем s.
Обозначим через G стандартное ДУМ порядка m и ранга t от БП (x1 , . . . , xm ), котороесвязано с разбиением Π, и пустьλ = |G| 6 t · 2s ,(5.8)а h1 , . . . , ht — входящие в него характеристические ФАЛ отрезков π1 , . . . , πt соответственно.Напомним, что при этом G = G(1) ∪ . . . ∪ G(t) , где G(i) , i = 1, . . . , t, состоит из всех ФАЛ g,для которых g 6 hi .§5.19Введёнм натуральный параметр a, положимq =m+a·λ6n(5.9)и рассмотрим разбиение ∆ = (δ1 , .
. . , δ2q−m ) куба B q от БП x0 = (x1 , . . . , xq ) на m-регулярныекомпоненты, построенное по лемме 5.2 для системы ФАЛ h = (h1 , . . . , ht ).b t — (t, 1)-КС из t контактов Kb от БП y (0) = (y1 , . . . , yt ),Пусть по-прежнему (см. §4) Fсоответствующих её «проводящим» входам и БП y (1) = (yt+1 , . . . , y2t ), управляющих еёконтактами, которая реализует ФАЛψb y (0) , y (1) = y1 yt+1 ∨ . . . ∨ yt y2t .Заметим, что любая ФАЛ g(x0 ) на любой компоненте δi разбиения ∆ совпадает с ФАЛτi,1τi,t gi (x0 ) = ψb gi,1 , . . . , gi,t , xji,1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
