Изменения

|definition='''Двоичный каскадный сумматор''' (англ. ''Binary adder'') {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.

'''ОбозначенияИспользуемые обозначения:'''* <tex>X_{i}, Y_{i}</tex> {{---}} <tex>i</tex>-ый разряд суммируемых чисел* , <tex>C_{i}, C_{i+1}</tex> {{---}} биты переноса* , <tex>F_{i}</tex> {{---}} результат сложения. Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора - Ripple-carry adder]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>: * если <tex>X_{i} = Y_{i} = 1</tex>, то <tex>C_{i+1} = 1</tex>,* если <tex>X_{i} = Y_{i} = 0</tex>, то <tex>C_{i+1} = 0</tex>;Иначе (<tex>X_i \neq Y_i</tex>) бит переноса не изменяется, то есть <tex>C_{i + 1} = C_i</tex>. Три случая называются следующим образом:* <tex> \mathbf{g} \mathtt{enerate}</tex> {{---}} ''порождение'' переноса,* <tex> \mathbf{k} \mathtt{ill}</tex> {{---}} ''уничтожение'' переноса,* <tex> \mathbf{p} \mathtt{ropagate}</tex> {{---}} ''проталкивание'' переноса. Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):[[Файл:Пример компазиции.png‎|right|450px|thumb|Пример композиции]]{| class="wikitable" align="center" style="color: blue; background-color:#ccffcc;" cellpadding="3"!colspan="20"|Таблица значений|-align="center"| <tex>\otimes</tex> || <tex> \mathbf{k} </tex> || <tex> \mathbf{p} </tex> || <tex> \mathbf{g} </tex>|-align="center"| <tex> \mathbf{k} </tex> || <tex>k</tex> || <tex>k</tex> || <tex>g</tex>|-align="center"| <tex> \mathbf{p} </tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>|-align="center"| <tex> \mathbf{g} </tex> || <tex>k</tex> || <tex>g</tex> || <tex>g</tex>|-align="center"|} Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия <tex>x</tex> выполняется равенство <tex>x \otimes p = x</tex>, то функцию от нескольких действий можно определить как "последнее не <tex>p</tex>". == Схема == Сумматор состоит из двух частей. Первая часть {{---}} это группа полных сумматоров, вычисляющих ответ. Вторая часть {{---}} [[Дерево_отрезков._Построение|дерево отрезков]], с помощью которого вычисляется бит переноса.[[Файл:Двоичный_каскадный_сумматор.png|450px|left|thumb|Схема двоичного каскадного сумматора]]                               

* <tex>"+" </tex> {{---}} полный сумматор, вычисляет результат сложения.,* <tex>\bigotimes</tex> вычисляет композицию {{---}} блок вычисления композиции двух переносов.,* <tex>\bigodot</tex> возвращает {{---}} блок вычисления <tex>C_{i}</tex>, старший бит старшего бита сумматора.

 == Ссылки См. также ==* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Дискретная математика: алгоритмы[Каскадный сумматор]]*[[Сумматор]]* [http://en.wikipedia.org/wiki/Adder_(electronics) Wikipedia[Троичный сумматор]]