35
правок
Изменения
→Смотри также
==Принцип работы==
чисел (как в [[Матричный умножитель|матричном умножителе]]).
Однако, в отличие от [[Матричный умножитель|матричного умножителя]], дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его <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>
# Для каждой тройки применяется элемент <tex>3\to2</tex>.
# Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
На выходе имеем число, которое равно сумме чисел на всех входах.
===Элемент 3→2===
[[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>(i + 1)</tex>-ым второго.
Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Подсчитаем количество элементов <tex>3\to2</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> глубину каждого из элементов двоичного каскадного сумматора.
Тогда общая сложность равна
<tex>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </tex>
== Литература См. также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации==
* ''Кормен, Т. Кормен, Лейзерсон, Ч. Лейзерсон, Ривест, Р. Ривест'': Алгоритмы: построение и анализ, 1— 960 с. — ISBN 5-900916-37-е изд5
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
