35
правок
Изменения
→Смотри также
==Принцип работы==
[[file:wallace_tree.png|thumb|200px|Иллюстрация работы дерева для суммирования 9 чисел]]
С помощью этого элемента на каждом шаге производятся следующие операции:
# Берутся тройки чисел <mathtex>(x_1, x_2, x_3)</mathtex>, <mathtex>(x_4, x_5, x_6)</mathtex>, <mathtex>\ldots</mathtex>. При этом какие-то числа могут остаться.# Для каждой тройки применяется элемент <mathtex>3\to2</mathtex>.# Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
На выходе имеем число, которое равно сумме чисел на всех входах.
===Элемент 3→2===
[[file:3→23v2.png|thumb|200px300px|Элемент 3→2]]Теперь о томДля того, как устроен элемент чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <mathtex>3\to2i</mathtex>. Для построения элемента направим <mathtex>3\to2x_i</mathtex> нам потребуется элемент, который умеет складывать 3 бита <tex>y_i</tex> и возвращать 2 бита результата<tex>z_i</tex> на вход полного сумматора.Основная идея реализации Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>- отдельная обработка переносов и остатковым второго.
==Схемная сложность==
Определим схемную сложность этого элементаколичество элементов и глубину схемы для умножения двух чисел из <tex>n</tex> бит.
Каждый элемент <mathtex>3\to2</mathtex> имеет глубину <mathtex>O(1)</mathtex> и размер <mathtex>O(n)</mathtex>.
Подсчитаем количество элементов <mathtex>3\to2</mathtex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на <math>1/3</math>в полтора раза. Тогда глубина дерева будет равна <mathtex>\log_{\frac{3/}{2}}n</mathtex>, и в нём будет <mathtex>n + \frac23n dfrac{2}{3} n + \left(\frac23dfrac{2}{3}\right)^2n + \ldots = O(n)</mathtex> элементов <tex>3\to2</tex>. Обозначим за <tex>size</tex> общее количество элементов в цепи; за <tex>size_{3\to2}</tex> количество элементов <mathtex>3\to2</mathtex>; за <tex>size_{sum}</tex> количество элементов двоичного каскадного сумматора в схеме; за <tex>depth</tex> глубину схемы; за <tex>depth_{3\to2}</tex> глубину каждого из элементов <tex>3\to2</tex>; за <tex>depth_{sum}</tex> глубину каждого из элементов двоичного каскадного сумматора.
Тогда общая сложность равна
<mathtex>depth = depth_{3\to2} \cdot \log_{3/2}n + depth_{sum} = O(\log n)</mathtex> <tex>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </tex> == См. также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации== * Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5 [[Категория: Дискретная математика и алгоритмы]]