Алексеев В.Б. Лекции по дискретной математике, страница 7

Теорема доказана.()§24. Метод Карацубы построения схемы для умножения,верхняя оценка её сложности.Определение 1. Умножителем Mn порядка n называется схема с 2n входами x1, x2, …,xn, y1, y2, …, yn и 2n выходами z1, …, z2n такая, что ~z = M n (~x, ~y) = ~x⋅~y . При этом0 ≤0 ≤~x ≤ 2n − 1 < 2 nx⋅~y < 22 n .⇒~nn~y ≤ 2 −1 < 2Определение 2. Через M (n) обозначим наименьшую сложность умножителя порядка nв базисе {∨, &, }.Утверждение. Существует схема из функциональных элементов для умножения nразрядного числа X на 1-разрядное число y с числом элементов n.Доказательство.

Действительно, если X = |(x1, x2, …, xn)| и Xy = Z = |(z1, z2, …, zn)|, то zi == xiy для всех i = 1, 2, …, n. Следовательно, для реализации такой схемы понадобится ровно nэлементов, реализующих конъюнкцию. Утверждение доказано.При умножении двух n-разрядных чисел X и Y «в столбик» можно n раз умножить X на1-разрядное число (всего n2 конъюнкций) и затем n – 1 раз сложить числа длиной не более2n. Для реализации такой схемы необходим также n – 1 сумматор порядка 2n.

Согласно теореме 1, сложность сумматора порядка 2n равна L (S2n) = 9 · 2n – 5 = 18n – 5, и сложность подобного умножителя составит n2 + (n – 1) · (18n – 5) = 19n2 – 23n + 5. Такой алгоритм (схема)имеет сложность по порядку n2. Следующая теорема показывает, что такой алгоритм умножения «в столбик» не оптимален по порядку.Лемма 1. Существует такая константа C1 > 0, что M (n + 1) ≤ M (n) + C1 n для всех n.Доказательство. Пусть требуется перемножить два (n + 1)-разрядных числа~x = (x0 x1 ! xn ) и ~y = ( y0 y1 ! yn ) .

Тогда~x~y =  x0 ⋅ 2 n + x1 ! xn  y0 ⋅ 2 n + y1 ! yn  = x0 y0 ⋅ 2 2 n + (x0 ⋅ Y + y0 ⋅ X )⋅ 2 n + X ⋅ Y .&#%#$ &#%#$XYПоэтому для вычисления ~x~y достаточно использовать умножитель Mn со сложностью M (n)для вычисления XY, 2n элементов конъюнкции для вычисления x0Y и y0X, 1 элемент конъюнкции для вычисления x0y0 и 3 сумматора порядка не более 2n + 2, так как ~x~y < 22 n + 2 . Отметим, что числа x0y0, x0Y и y0X надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды 0. При этом 0 можно предварительно получить подсхемой с 2 элементами, реализующей x0 x0 = 0 . Так как сложность каждого сумматора можно сделать неболее 9(2n + 2), а сложность Mn равна M (n), то сложность полученной схемы будет не больше, чем M (n) + C1n для некоторой константы C1.

Лемма доказана.Лемма 2 (основная) [Карацуба А. А.]. Существует константа C2 такая, чтоM (2n) ≤ 3M (n) + C2nдля всех n.Доказательство. Пусть нужно перемножить два 2n-разрядных числа ~y . Разобьёмx и ~их на части, содержащие по n разрядов:26~x =  x1 x2 ! xn xn+1 ! x2 n  , ~y =  y1 y2 ! yn yn+1 ! y2 n  .&#%#$ &#%#$&#%#$ &#%#$X1X2Y1Y2Тогда ~y = Y1·2n + Y2 иx = X1·2n + X2, ~~x~y = X1Y1 · 22n + (X1Y2 + X2Y1) · 2n + X2Y2 = X1Y1 · 22n + [(X1 + X2)(Y1 + Y2) – X1Y1 – X2Y2] · 2n + X2Y2.Так как X1Y2 + X2Y1 ≥ 0, то при вычитании в квадратной скобке не возникнет отрицательныхчисел. Таким образом, схему для умножения ~x~y можно построить, используя два умножителя Mn с числом элементов M (n) в каждом для вычисления X1Y1 и X2Y2, умножитель Mn+1 счислом элементов M (n + 1) для вычисления (X1 + X2)(Y1 + Y2), 4 сумматора порядка не более4n (так как ~x~y < 24 n ) и два вычитателя порядка 2n + 2. В некоторых сумматорах опять намладшие разряды надо подавать 0, который реализуем подсхемой с 2 элементами: 0 = xx ,где x — любая входная переменная.

Для построения схемы M2n с учётом леммы 1 получимдля некоторых констант C и C2:M (2n) ≤ 2 M (n) + M (n + 1) + Cn ≤ 3 M (n) + C1n + Cn = 3 M (n) + C2n.Лемма доказана.Лемма 3. Существует такая константа C3 > 0, что для любого натурального k верноM (2k) ≤ C33k.kДоказательство. Положим f (k ) = M3(2k ) . Тогда из леммы 2 имеем( )( )M 2kM 2 k −1 C2  2 ≤+  3k3k −13 3C  2f (k ) ≤ f (k −1) + 2  3  3k −1C  2≤ f (k − 2) + 2  3  3k −2C  2+ 2 3  3k −1k −1и2k −1C2  2  2  2 ≤ ! ≤ f (1) +  +   + ! +    ≤ C33  3  3  3  для некоторой константы C3, поскольку сумма в квадратных скобках не превосходит сумму 2бесконечно убывающей геометрической прогрессии с первым членом 23 и знаменателем 23 .Таким образом,( ) ≤ C и M (2k) ≤ C 3k.

Лемма доказана.33M 2k3kТеорема 3. Существует схемный умножитель в базисе {∨, &, } с числом элементов()O nlog 2 3 .Доказательство. Пусть n — любое натуральное число и n>1. Тогда существует натуральное k такое, что 2k–1 < n ≤ 2k. Для умножения n-разрядных чисел будем использовать схему M 2 k с числом элементов M (2k), подавая на старшие 2k – n разрядов обоих сомножителей 0,предварительно реализованный подсхемой из 2 элементов. Тогда имеем, исходя из леммы 3( )M (n ) ≤ M 2 k + 2 ≤ C3 3k + 2 = 3C3 3k −1 + 2 = 3C3 2(k −1)log 2 3 + 2 < 3C3n log 2 3 + 2 ≤ Cn log 2 3для некоторой константы C. Теорема доказана.Замечание.

Существует практически применимый метод Шёнхаге-Штрассена умножения с оценкой сложности O (n log n · log log n).27§25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценкасложности реализации произвольной функции алгебры логики.Определение. Дешифратором Qn порядка n называется схема из функциональных элементов с n входами x1, x2, …, xn и 2n выходами z0 , z1 ,!, z 2n −1 такая, что если |x1x2…xn| = i, то1, x1 ! xn = izi = 1 и zj = 0 при i ≠ j: zi (x1 ,!, xn ) = .0, x1 ! xn ≠ iЗаметим, что если i = (i1, i2, …, in)2, то zi (x1 ,!, xn ) = x1i1 x2i2 " xnin .Лемма 4. Существует дешифратор Qn с числом элементов, не превосходящим n2n + 1.Доказательство. Для реализации каждой zi достаточно взять ровно n–1 конъюнкций ине более n отрицаний, то есть всего менее, чем 2n функциональных элементов.

Всего различных конъюнкций ровно 2n, и сложность дешифратора не превосходит n2n + 1. Лемма доказана.Теорема 4. Сложность минимального схемного дешифратора порядка n не меньше, чем( )n2n и асимптотически не больше, чем 2n + O n ⋅ 2 2 .Доказательство. 1) Поскольку у дешифратора Qn ровно 2n выходов, на которых реализуются различные функции, не равные входным переменным, сложность минимального дешифратора не меньше, чем 2n.x1…xkxk + 1…xnQk′Qn′′− ky0 y1 … Q′[j] … y 2k −1y′0 y′1 … Q′′[l] … y ′2n − k −1&&Qn [1]Qn [i]( )n2) Докажем существование дешифратора со сложностью 2 n + O n ⋅ 2 2 .

Разобьём наборвходных переменных x = (x1, …, xn) на поднаборы x′ = (x1, …, xk) и x′′ = (xk + 1, …, xn), где k —некоторый параметр и 1 ≤ k ≤ n – 1. Пусть Q′ и Q′′ —функциональные дешифраторы порядкаk и n – k от базовых переменных x′ и x′′, а Σ′ и Σ′′ — соответствующие им схемные дешифраторы, построенные по лемме. Легко видеть, что любую конъюнкцию Qn [i], 1 ≤ i ≤ 2n, можнопредставить в виде Qn [i] = Q ′[j]·Q′′ [l], где i = 2n – k(j – 1) + l и 1 ≤ j ≤ 2k, 1 ≤ l ≤ 2n – k.

Дешифратор Σ порядка n от базовых переменных x содержит дешифраторы Σ′ и Σ′′ в качестве подсхем и реализует каждую функцию алгебры логики Qn [i], 1 ≤ i ≤ 2n, с помощью одногофункционального элемента &, входы которого присоединены к выходам Σ′ и Σ′′ в соответствии с формулой Qn [i] = Q′ [j]·Q′′ [l].

Из построения Σ следует, что L (Σ) = 2n + L (Σ′) + L (Σ′′) ≤n≤ 2n + k·2k + 1 + (n – k)2n – k + 1, и поэтому при k = n2  получим: L(Σ ) ≤ 2 n + O n ⋅ 2 2 . Теоремадоказана.Следствие. Для любой функции алгебры логики f(x1,…,xn) существует реализация еёсхемой из функциональных элементов в базисе {∨,&, } со сложностью, не превосходящей( )( )n2 ⋅ 2n + O n ⋅ 2 2 .Доказательство.

Если f ≡ 0, то реализуем f = x1 ⋅ x1 . Если f ≠ 0, тоf (x1 ,!, xn ) =∨(σ1 ,!,σ n )( )x1σ1 " xnσ n , и L ≤ L(Qn ) + 2 n − 1 ≤ 2 ⋅ 2n + O n ⋅ 2 2 .nf (σ~ )=1Следствие доказано.28§26. Мультиплексор. Верхняя оценка сложности мультиплексора.Метод Шеннона.Определение 1. Мультиплексором µn порядка n называется схема из функциональныхэлементов с n + 2n входами x1 ,! xn , y0 , y1 ,!, y2n −1 и 1 выходом z такая, что если на входы&%$ &##%##$адресные входы информационные входыx1, …, xn поступает набор (α1, …, αn), то z = y(α1 ,!,α n )2 .Теорема 5. Существует мультиплексор µn порядка n с числом элементов( )L(µ n ) ≤ 3 ⋅ 2 n + O n ⋅ 2 2 .nДоказательство.

Заметим, что задачу решает функцияz=∨(α1 ,!,α n )x1α1 ⋅ x2α 2 " xnα n ⋅ y(α1!α n )2 .Для её вычисления достаточно использовать один дешифратор, 2n конъюнкций и 2n – 1дизъюнкций и( )L(µ n ) ≤ L(Qn ) + 2 n + 2 n − 1 ≤ 3 ⋅ 2n + O n 2 2 .nТеорема доказана.x1 … xny0y1… y 2 n −1Qn&&"&2n∨∨2n – 1'∨Определение 2. Сложностью L (S) схемы S называется число элементов в ней.Определение 3. Сложностью функции алгебры логики f (x1, …, xn) называетсяL( f ) = min L(S ) .S реализует fОпределение 4. Функцией Шеннона L(n) для схемы из функциональных элементов называется L(n ) = max L( f ) .f от x1 ,!, xnОбозначения: g (n) ≲h (n) ⇔ g (n) ≤ h (n)·(1 +o(1)); g (n) ≳ h (n) ⇔ g (n) ≥ h (n)·(1 +o(1)).Определение 5.

Универсальным многополюсником Un порядка n называется схема изnnфункциональных элементов с n входами и 2 2 выходами, на которых реализуются все 22функций от x1, …, xn.29Теорема 6 [Ложкин С. А.]. Минимальная сложность универсального многополюсникаnпорядка n равна 2 2 − n .nДоказательство. 1) Очевидно, что L(U n ) ≥ 2 2 − n , так как всего функций алгебры логиnки от n переменных, отличных от входных переменных, ровно 2 2 − n .2) Докажем существование универсального многополюсника с числом элементов2n2 − n . Для этого построим какую-нибудь схему из функциональных элементов, реализующую все функции алгебры логики. Затем оставим из каждой группы эквивалентных вершин(в которых реализуются одинаковые функции) лишь одну, наиболее близкую к входам, подсоединив выходы удалённых к выходу оставшейся.