19
правок
Изменения
м
==Каскадный сумматор ={{Определение|definition='''Каскадный сумматор''' (англ. ''ripple-carry adder'') {{- --}} логическая цепь[[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение многоразрядных двоичных чисел.}}Как известно, с помощью [[Сумматор|полного сумматора]] можно сложить 2 одноразрядных двоичных числа. Для сложения двух <tex>n</tex>-разрядных двоичных чисел можно использовать <tex>n</tex> полных сумматоров.
Сложение Прежде чем сложить <tex>i</tex>-ые биты, надо ждать выходного бита переноса от сложения <tex> i-1 </tex> битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с предвычислением переносовпомощью каскадного сумматора выполняется за время <tex>O(n)</tex>.
В каскадном сумматоре бит переноса ci вычисляется в момент времени i. Значения ai и bi, однако, известны с самого начала. В некоторых случаях они определяют бит переноса ci:
если ai = bi = 0, то ci = 0 (перенос "поглощается" (kill))
если ai = bi = 1, то ci = 1 (перенос "порождается" (generate))
Однако если один из битов ai и bi равен 1, а другой 0, то ci-1 существен; именно,
если ai != bi, то ci = ci-1 (перенос "распространяется" (propagate))
Каждому разряду, следовательно, соответствует один из трёх типов переноса (carry statuses): k (kill), g (generate) или p (propagate). Этот тип известен заранее, что позволяет уменьшить время работы схемы сложения.
Зная типы переноса для соседних сумматоров ((i - 1)-го и i-го), можно определить тип переноса для их соединения, считая ci-1 входным битом, а ci+1 — выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит ci+1 от ci-1. Если i-й разряд имеет тип k или g, то соединение имеет тот же тип переноса. Если же i-й разряд имеет тип переноса p, то тип переноса для соединения совпадает с типом (i - 1)-го разряда.
Таким образом, вычисление битов переноса ci сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время O(1): достаточно подать биты переноса на входы сумматоров.
Добавил англ. терминов; правильно оформил источники информации.
При сложении двух чисел в <tex>i</tex>-том разряде складываются <TeX>a_i</TeX>, <Tex>b_i</TeX> и входной бит переноса (англ. ''carry-in bit'') <TeX>c_i</TeX>. Младший разряд суммы записывается в <tex>i</tex>-й разряд ответа (<TeX>s_i</TeX>), а старший становится выходным битом переноса (англ. ''carry-out bit'') <TeX>c_{i+1}</TeX> и используется при сложении в следующем разряде.
При сложении двух чисел этом в i-том разряде складываются a[i],b[i] и первый входной бит переноса (carry-in bit) c[i]. Младший разряд суммы записывается в i-й разряд ответа (s[i])подаётся ноль, а последний бит переноса даёт старший становится выходным битом переноса (carry-out bit) c[i+1] и используется при сложении в следующем разрядеразряд суммы.
[[Файл:Ripple_carry_adder.png]]
*[[Сумматор]]
*[[Двоичный каскадный сумматор]]
==Источники информации ==
* [http://en.wikipedia.org/wiki/Adder_(electronics) Wikipedia {{---}} Adder (electronics)]
* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Каскадное сложение]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
