Изменения

==Определение== '''Дерево Уоллеса ''' (англ. ''Wallace tree'') {{---}} [[Реализация булевой функции схемой из функциональных элементов|схема]] для умножения двух чисел. Время работы <tex>O(\log n)</tex>.

Однако, в отличие от [[Матричный умножитель|матричного умножителя]], дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его <tex>3\to2</tex>), преобразующего <tex>3 </tex> числа <tex>x</tex>, <tex>y</tex> и <tex> z </tex> в числа <tex>a</tex> и <tex>b</tex> такие, что <tex>x + y + z = a + b</tex>.

# Берутся тройки чисел <tex>(x_1, x_2, x_3)</tex>, <tex>(x_4, x_5, x_6)</tex>, <tex>\ldots</tex>. При этом какие-то числа могут остаться.

# Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].

[[file:3→23v2.png|thumb|200px300px|Элемент 3→2]]Теперь о томДля того, чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <tex>i</tex> направим <tex>x_i</tex>, <tex>y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, как устроен элемент а старший {{---}} <tex>3\to2(i + 1)</tex>-ым второго.

Для построения элемента Очевидно, полученные числа в сумме дают <tex>3\to2x + y + z</tex> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.Основная идея реализации {{---}} отдельная обработка переносов и остатков.

Тогда первое число ответа На иллюстрации изображён элемент <tex>a</tex> может быть получена так:<tex>a_i = x_i 3\oplus y_i \oplus z_i</tex> ,где <tex>x</tex>, <tex>y</tex> и <tex>zto2</tex> {{---}} входные числадля четырёхбитных чисел, а <tex>x_i</tex>в верхнем прямоугольнике изображены четыре полных сумматора, <tex>y_i</tex> выходы которых и <tex>z_i</tex> {{---}} соответствующие их <tex>i</tex>-е битыявляются разрядами результатов.

Второе же число <tex>b</tex> можно получить так:<tex> \begin{cases}b_0 & = 0\\b_{i + 1} & = \langle x_i, y_i, z_i \rangle\end{cases}</tex> ,где <tex>\langle xПоскольку все полные сумматоры работают параллельно (выходы на каждом из них зависят только от собственных входов), y, z\rangle</tex> {{---}} функция медианы то глубина такой схемы есть константа (она же "голосование 2 из 3"не зависит от количества бит). С помощью этой функции считается перенос. Очевидно, полученные числа <tex>a</tex> и <tex>b</tex> дадут в сумме <tex>x + y + z</tex>

Определим схемную сложность этого элементаколичество элементов и глубину схемы для умножения двух чисел из <tex>n</tex> бит.

Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в <tex>1{,}5</tex> полтора раза. Тогда глубина дерева будет равна <tex>\log_{\frac{3/}{2}}n</tex>, и в нём будет <tex>n + \frac23n dfrac{2}{3} n + \left(\frac23dfrac{2}{3}\right)^2n + \ldots = O(n)</tex> элементов <tex>3\to2</tex>. Обозначим за <tex>size</tex> общее количество элементов в цепи; за <tex>size_{3\to2}</tex> количество элементов <tex>3\to2</tex>; за <tex>size_{sum}</tex> количество элементов двоичного каскадного сумматора в схеме; за <tex>depth</tex> глубину схемы; за <tex>depth_{3\to2}</tex> глубину каждого из элементов <tex>3\to2</tex>; за <tex>depth_{sum}</tex> глубину каждого из элементов двоичного каскадного сумматора.

== Литература См. также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации== * Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5 [[Категория: Дискретная математика и алгоритмы]]

* ''Т. Кормен, Ч. Лейзерсон, Р. Ривест''[[Категория: Алгоритмы: построение и анализ, 1-е издСхемы из функциональных элементов ]]