Рассмотрим один элемент полного сумматора:{{Определение|definition='''Двоичный каскадный сумматор''' {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел.}} == Принцип работы ==[[Файл:Полный_сумматор_1.png|right|200px|leftthumb|[[Cумматор#.D0.9F.D0.BE.D0.BB.D0.BD.D1.8B.D0.B9_.D1.81.D1.83.D0.BC.D0.BC.D0.B0.D1.82.D0.BE.D1.80|Полный сумматор]] Где ]]'''Обозначения:'''* <tex>X_{i}, Y_{i}</tex> {{-- -}} i-ный ый разряд суммируемых чисел, * <tex>C_{i}, C_{i+1}</tex> {{- Биты --}} биты переноса, а * <tex>F_{i}</tex> {{- Результат --}} результат сложения. Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора]]. В некоторых случаях бит переноса <tex>C_{i+1}<Br/tex> зависит только от значений <tex>X_{i}<Br/tex>и <tex>Y_{i}<Br/tex>: * Generate(g): <Br/tex>X_{i} = Y_{i} = 1<Br/tex>Построим таблицу зависимости , тогда <tex>C_{i+1}= 1</tex> от * Kill(k): <tex>X_{i}, = Y_{i}, C_{i}= 0</tex>, и введем условные обозначения:{| border="1"| x || y || тогда <tex> C_i \rightarrow C_{i+1} = 0</tex> || Условные обозначения ||align="center" | Действие, |- align="center"| 0 || 0 || 0 || k* Propagate(killp) || Поглощение переноса|- align="center"| 0 || 1| rowspan="2"| : <tex> P_1 X_{i} \ne Y_{i}</tex> ||rowspan="2"| p(propagate) ||rowspan="2"| Перенос переноса|- align="center"| , тогда <tex>C_{i+1 || 0|- align} ="center"| 1 || 1 || 1 || g(generate) || Порождение переноса|C_{i}</tex>,
Обозначим композицию действий над переносами значком <tex>\bigotimes</tex> и рассмотрим таблицу:
{| border="1" cellpadding="5"
!<tex>\bigotimes</tex>
!k
|-
|}
<Br/>
Пример:
<Br/>[[Файл:Пример компазиции.png|430px]]
<Br/>
Таким образом функцию <tex>\bigotimes</tex> можно определить как последнее не "P".
<Br/><Br/>
Пусть <tex>f_{i}\epsilon \left \{k,p,g\right \}</tex>, тогда: <tex>C_{i}=(f_{1}\bigotimes f_{2}\bigotimes f_{3}\bigotimes...\bigotimes f_{i})_{(0)}</tex>.
<Br/>
<Br/>
Пусть элемент
[[Файл:Первый_элемент.png|130px]]
возвращает <tex>\bigotimes</tex> двух функций,<Br/> а элемент
[[Файл:Второй_элемент.png|130px]] возвращает <tex>C'</tex>, старший бит сумматора.
<Br/>
'''Пример''' [[Файл:Пример компазиции.png|430px|Пример композиции]] Таким образом, функцию <tex>\bigotimes</tex> можно определить как последнее не "P". == Схема двоичного каскадного сумматора выглядит следующим образом:==[[Файл:Двоичный_каскадный_сумматор.png|560px|thumb|Схема двоичного каскадного сумматора]]<Br/>Сумматор состоит из двух частей. Первой частью является Первая часть {{---}} это группа полных сумматоров, вычисляющих ответ. Вторая часть {{---}} [[Дерево_отрезков._Построение|дерево отрезков ]], с помощью которого вычисляется бит переноса. === Обозначения ===* <tex>"+"</tex> {{---}} полный сумматор, вычисляет результат сложения.* <tex>\bigotimes</tex> вычисляет композицию двух переносов.* <tex>\bigodot</tex> возвращает <tex>C_{i}</tex>, старший бит сумматора. == Схемная сложность ==Дерево отрезков вычисляет биты переноса за <tex>O(\log N)</tex>, оставшиеся действия выполняются за <tex>O(1)</tex>. Суммарное время работы {{---}} <tex>O(\log N)</tex>. == Ссылки ==* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Дискретная математика: алгоритмы]* [http://en.wikipedia.org/wiki/Дерево_отрезковAdder_(electronics) Wikipedia] [[Категория:Дискретная математика и алгоритмы]][[Категория:Схемы из функциональных элементов]], с помощью которого, вычисляется бит переноса. Вторая часть это группа полных сумматоров, вычисляющих ответ.
