Каскадный сумматор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Добавил англ. терминов; правильно оформил источники информации.)
(не показано 14 промежуточных версий 6 участников)
Строка 1: Строка 1:
−
==Каскадный сумматор ==
+
{{Определение
−
'''Каскадный сумматор''' - логическая цепь, осуществляющая сложение многоразрядных двоичных чисел.
+
|definition=
 +
'''Каскадный сумматор''' (англ. ''ripple-carry adder'') {{---}} логическая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение многоразрядных двоичных чисел.
 +
}}
 +
Как известно, с помощью [[Сумматор|полного сумматора]] можно сложить 2 одноразрядных двоичных числа. Для сложения двух <tex>n</tex>-разрядных двоичных чисел можно использовать <tex>n</tex> полных сумматоров.
  
 +
При сложении двух чисел в <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] и используется при сложении в следующем разряде.
+
При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.
  
−
Сложение с предвычислением переносов
+
Прежде чем сложить <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 существен; именно,
+
[[Файл:Ripple_carry_adder.png]]
−
если 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): достаточно подать биты переноса на входы сумматоров.
+
==Источники информации ==
−
+
* [http://en.wikipedia.org/wiki/Adder_(electronics) Wikipedia {{---}} Adder (electronics)]
 +
* [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Каскадное сложение]
  
 +
[[Категория: Дискретная математика и алгоритмы]]
  
−
== См. также ==
+
[[Категория: Схемы из функциональных элементов ]]
−
*[[Сумматор]]
 
−
*[[Двоичный каскадный сумматор]]
 

Версия 20:25, 5 января 2017

Определение:
Каскадный сумматор (англ. ripple-carry adder) — логическая схема, осуществляющая сложение многоразрядных двоичных чисел.

Как известно, с помощью полного сумматора можно сложить 2 одноразрядных двоичных числа. Для сложения двух [math]n[/math]-разрядных двоичных чисел можно использовать [math]n[/math] полных сумматоров.

При сложении двух чисел в [math]i[/math]-том разряде складываются [math]a_i[/math], [math]b_i[/math] и входной бит переноса (англ. carry-in bit) [math]c_i[/math]. Младший разряд суммы записывается в [math]i[/math]-й разряд ответа ([math]s_i[/math]), а старший становится выходным битом переноса (англ. carry-out bit) [math]c_{i+1}[/math] и используется при сложении в следующем разряде.

При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.

Прежде чем сложить [math]i[/math]-ые биты, надо ждать выходного бита переноса от сложения [math] i-1 [/math] битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с помощью каскадного сумматора выполняется за время [math]O(n)[/math].


Ripple carry adder.png


См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Каскадный_сумматор&oldid=58836»