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

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

Текущая версия на 19:26, 4 сентября 2022

Определение:
Каскадный сумматор (англ. 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


См. также

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