А.Д. Поспелов, В.Б. Алексеев - Дискретная математика, страница 8

А.]. Минимальная сложность универсального многополюсникаnпорядка n равна 2 2 − n .nДоказательство. 1) Очевидно, что L(U n ) ≥ 2 2 − n , так как всего функций алгебры логиnки от n переменных, отличных от входных переменных, ровно 2 2 − n .2) Докажем существование универсального многополюсника с числом элементов2n2 − n .

Для этого построим какую-нибудь схему из функциональных элементов, реализующую все функции алгебры логики. Затем оставим из каждой группы эквивалентных вершин(в которых реализуются одинаковые функции) лишь одну, наиболее близкую к входам, подсоединив выходы удалённых к выходу оставшейся. В результате получим, что в каждойвершине реализуется уникальная функция алгебры логики.

Но всего функций, отличных отnnвходных переменных — 2 2 − n . Следовательно, и вершин — 2 2 − n . Теорема доказана.1Теорема 7. L(n ) ≲ 6 ⋅ 2 n ⋅ .nДоказательство. Рассмотрим произвольную функцию f (x1, …, xn). Выберем некотороенатуральное k (1 ≤ k ≤ n) и рассмотрим разложение взятой функции по первым k переменным:f (x1 ,!, xn ) =∨(σ1 ,!,σ k )x1σ1 ⋅ x2σ 2 " xkσ k ⋅ f (σ 1 ,!, σ k , xk +1 ,!, xn ) .Построим схему из функциональных элементов из универсального многополюсника Un–k порядка n – k от базовых переменных xk + 1, …, xn и мультиплексора µn порядка n с адреснымипеременными x1, …, xk, на информационные входы которого подаются выходы Un – k.

Мульkтиплексор можно построить так, что его сложность не превзойдёт 3 ⋅ 2k + O k ⋅ 2 2 , а универ-( )n− kсальный многополюсник так, что его сложность будет не больше, чем 2 2 . Итак,( )L(n ) = L(µ n ) + L(U n−k ) ≤ 3 ⋅ 2 k + O k ⋅ 2 2 + 2 2 . Следовательно, полагаяkn−kk = n − log 2 (n − 2 log 2 n ) (при этом k ≤ n – log2(n – 2log2n) + 1, а n – k ≤ log2(n – 2log2n)),получим, что 2k ≤ 2 n−log 2 (n−2 log 2 n )+1 = 2 n+1 ⋅n−k 2n 12n2n~ 2 ⋅ , 2 2 ≤ 2n−2 log 2 n = 2 = o  и вn − 2 log 2 nnn nитоге n2   2 n 2n2nL(S ) ≲ 3 ⋅ 2 ⋅ + O n 2  + o  ~ 6 ⋅ .nn  n Теорема доказана.Определение 6.

Пусть γ (L, n) — число всех попарно неизоморфных схем из функциональных элементов с входными переменными x1, …, xn и выходной переменной z1, сложность которых не превосходит L.Лемма 5. В функциональном базисе {&, ∨, } γ (L, n) ≤ (L + n)2L + 4.Доказательство. Можно выбрать целые неотрицательные числа L1, L2, L3 так, чтобы ихсумма не превосходила L, не более, чем (L + 1)3 способами.

Можно взять L1 конъюнкций, L2дизъюнкций, L3 отрицаний, а затем каждый вход каждого из них «присоединить» к выходунекоторого другого функционального элемента или к входу схемы не более, чем (L + n)2Lспособами, и пометить в качестве выхода одну из не более, чем L + n точек.Тогда γ (L, n) ≤ (L + 1)3·(L + n)2L·(L + n) ≤ (L + n)2L + 4. Лемма доказана.301 2n⋅ .2 nnДоказательство. Очевидно, γ (L(n ), n ) ≥ 2 2 , но в то же время согласно лемме γ (L, n) ≤Теорема 8. Для функции Шеннона L (n) справедливо L(n ) ≳≤ (L + n)2L+4.

Следовательно,(L(n ) + n )2 L (n )+4 ≥ 2 2n⇒ (2 L(n ) + 4 )log 2 (L(n ) + n ) ≥ 2 n . Так какL(n )≲ 6 ⋅ 2 n ⋅ 1n ,то начиная с некоторого номера n, n + L (n) ≤ 2n и 2 L(n ) + 4 ≥L(n )≳2n, откудаn1 2n⋅ . Теорема доказана.2 n§27. Шифратор. Верхняя оценка сложности шифратора.Определение. Шифратором Dn порядка n называется схема из функциональных элементов с 2n входами x0 , x1 , !, x2n −1 и n выходами y1,y2,…,yn такая, что если на вход поступаетнабор с одной единицей по переменной xi, то на выходе образуется набор (β1, β2, …, βn)2 = i.Теорема 9. Существует шифратор Dn порядка n со сложностью, не превосходящейn·2n – 1.Доказательство. Задачу решает система функцийyj =∨x(σ1 ,!,σ j −1 ,1,σ j +1 ,!,σ n ) (σ1 ,!,σ j −1 ,1,σ j +1 ,!,σ n )(например, yn = x1 ∨ x3 ∨ x5 ∨ x7 ∨ ! ∨ x2n −1 ).

Всего в каждой дизъюнкции 2n – 1 слагаемых, следовательно, необходимо 2n – 1 – 1 дизъюнкторов, всего таких функций надо реализовать n, тоесть получаем оценку сложности шифратора L (Dn) ≤ (2n – 1 – 1) · n < n · 2n – 1. Теоремадоказана.31Глава IV. Основы теории кодирования§28. Алфавитное кодирование.Теорема Маркова о взаимной однозначности алфавитного кодирования.Определение 1. Пусть A = {a1, a2, …, ar} — исходный алфавит, B = {b1, b2, …, bm} —кодирующий алфавит иA* = ∅ ∪ A ∪ A2 ∪ A3 ∪ … ∪ An ∪ …, B* = ∅ ∪ B ∪ B2 ∪ B3 ∪ … ∪ Bn ∪ ….Тогда алфавитным кодированием A* → B* назовём отображение ϕ : A → B* такое, что ai → Bi.Множество {B1, B2, …, Br} при этом называется множеством кодовых слов (или просто кодом).

При этом ϕ : ai1 ai2 ! ais → Bi1 Bi2 ! Bis .Определение 2. Кодирование A* → B* называется взаимно однозначным (декодируемым,разделимым), если для любых слов a1 ∈ A∗ и a2 ∈ A∗ a1 ≠ a2 ⇒ ϕ a1 ≠ ϕ a2 .Определение 3. Код называется равномерным, если длины всех его кодовых словодинаковы.Утверждение 1. Любой равномерный код является взаимно однозначным.Определение 4.

Код называется префиксным, если никакое кодовое слово не являетсяначалом другого.Утверждение 2. Любое префиксное кодирование является взаимно однозначным.Определение 5. Код называется постфиксным (суффиксным), если никакое кодовоеслово не является концом другого.Утверждение 3. Любое постфиксное кодирование является взаимно однозначным.Определение 6. Слово b ∈ B ∗ называется неприводимым, если b декодируется неоднозначно, однако, при выбрасывании из b любого связного непустого куска получается слово,которое декодируется не более, чем одним способом.Теорема 1 [Марков А. А.]. Пусть ϕ: ai → Bi (i = 1, 2, …, r) — некоторое кодирование.Пусть W — максимальное число кодовых слов, которые «помещаются» подряд внутри кодо-( ) ( )rвого слова.

Пусть li — длина слова Bi и L = ∑ li . Тогда если кодирование ϕ не взаимно одноi =1значно, то существуют два различных слова a' ∈ A*, a'' ∈ A*,длина(a′) ≤ (W +1)(2L−r +2 )  , длина(a′′) ≤ (W +1)(2L−r + 2 )  и ϕ (a') = ϕ (a'').Доказательство. Пусть ϕ не является взаимно однозначным. Тогда существует некоторое слово b1 , которое допускает две расшифровки. Если слово b1 не является неприводимым, то выбрасывая из b1 куски несколько раз, получим неприводимое слово b ; иначе, положим b = b1 . Очевидно, это всегда можно сделать. Рассмотрим любые две декодировкислова b .

Разрежем слово b в концевых точках кодовых слов каждого из разбиений. Слованового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).Лемма.

Если b — неприводимое слово, то все слова β1, β2, …, βm II класса различны.Доказательство. Пусть β' = β''. Тогда, очевидно, слово b не будет неприводимым, поскольку при выкидывании отрезка между β' и β'', вместе с любым из этих слов, получим снова две различные расшифровки этого слова (проверьте). Лемма доказана.32Таким образом, все β1, β2, …, βm разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит(l1 – 1) + (l2 – 1) + … + (lr – 1) = L – r.Слова из второго класса разбивают слово не более чем на L – r + 1 кусков. Рассмотрим парысоседних кусков. Тогда согласно одному разбиению в одной половинке уложится не болееодного кодового слова, а в другой — не более W (согласно второму разбиению ситуация симметрична).

Всего пар кусков не больше, чемL −2r +1  ≤ L −2r + 2 ,а в каждом из них укладывается слов не более чем W + 1. Отсюда число кодовых слов в любом разбиении не превосходит L−2r + 2 (W + 1) , а поскольку число целое, то не превосходит и целой части(W +1)(L − r + 2 )2. Теорема доказана.§29. Неравенство Макмиллана.Теорема 2 (неравенство Макмиллана). Пусть задано кодирование ϕ : ai → Bi(i = 1, 2, …, r) и пусть в кодирующем алфавите B — q букв и длина (Bi) = li (i = 1, 2, …, r). Тогда если ϕ взаимно однозначно, тоr1∑qi =1rДоказательство.

Положим x = ∑i =1 r 1x n =  ∑ li1 i1 =1 q r 1 ∑ l i =1 q i2 2li≤ 1.1. Тогда для любого натурального nq li  r 1" ∑ l  i =1 q in nr r r = ∑∑ ! ∑ l +l 1+!+l . i =1 i =1 i =1 q i1 i2 inn 1 2Обозначая lmax = max li , получим, что эта сумма равна1≤i ≤ rn ⋅l maxck∑qk =1k.Лемма. ck ≤ qk (∀k).Доказательство. За ck обозначено, очевидно, число наборов (i1, …, in) (1 ≤ ij ≤ r), для которых li1 + li2 + ! + lin = k . Но такой сумме соответствует слово Bi1 Bi2 ! Bin и()длина Bi1 Bi2 ! Bin = li1 + li2 + ! + lin = k .В силу того, что кодирование взаимно однозначно, различным наборам, соответствуют различные сообщения, а различных сообщений длины k в алфавите из q букв не более qk ⇒ ck ≤ qk (∀k).Лемма доказана.nl maxnl maxcСогласно лемме x n = ∑ kk ≤ ∑1 = nlmax ⇔ x ≤ n nlmax , ∀n .