Каскадный сумматор — различия между версиями
Rybak (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 6 промежуточных версий 5 участников) | |||
| Строка 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-том разряде складываются <TeX>a_i</TeX>,<Tex>b_i</TeX> и входной бит переноса (carry-in bit) <TeX>c_i</TeX>. Младший разряд суммы записывается в i-й разряд ответа (<TeX>s_i</TeX>), а старший становится выходным битом переноса (carry-out bit) <TeX>c_{i+1}</TeX> и используется при сложении в следующем разряде. | ||
| − | + | При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы. | |
| + | Прежде чем сложить <tex>i</tex>-ые биты, надо ждать выходного бита переноса от сложения <tex> i-1 </tex> битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с помощью каскадного сумматора выполняется за время <tex>O(n)</tex>. | ||
| Строка 15: | Строка 19: | ||
*[[Двоичный каскадный сумматор]] | *[[Двоичный каскадный сумматор]] | ||
| − | == | + | ==Источники информации == |
| − | * [http://en.wikipedia.org/wiki/Adder_(electronics) | + | * [http://en.wikipedia.org/wiki/Adder_(electronics) Wikipedia {{---}} Adder (electronics)] |
| − | * [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm | + | * [http://rain.ifmo.ru/cat/view.php/vis/arithmetics/binary-addition-2002/algorithm Каскадное сложение] |
| + | |||
| + | [[Категория: Дискретная математика и алгоритмы]] | ||
| + | |||
| + | [[Категория: Схемы из функциональных элементов ]] | ||
Текущая версия на 19:26, 4 сентября 2022
| Определение: |
| Каскадный сумматор (англ. ripple-carry adder) — логическая схема, осуществляющая сложение многоразрядных двоичных чисел. |
Как известно, с помощью полного сумматора можно сложить 2 одноразрядных двоичных числа. Для сложения двух -разрядных двоичных чисел можно использовать полных сумматоров.
При сложении двух чисел в -том разряде складываются , и входной бит переноса (англ. carry-in bit) . Младший разряд суммы записывается в -й разряд ответа (), а старший становится выходным битом переноса (англ. carry-out bit) и используется при сложении в следующем разряде.
При этом в первый входной бит переноса подаётся ноль, а последний бит переноса даёт старший разряд суммы.
Прежде чем сложить -ые биты, надо ждать выходного бита переноса от сложения битов, то есть сумма в каждом разряде может зависеть от суммы предыдущих разрядов. Поэтому сложение с помощью каскадного сумматора выполняется за время .
