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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
При сложении двух чисел в i-том разряде складываются a[i],b[i] и входной бит переноса (carry-in bit) c[i]. Младший разряд суммы записывается в i-й разряд ответа (s[i]), а старший становится выходным битом переноса (carry-out bit) c[i+1] и используется при сложении в следующем разряде.
 
При сложении двух чисел в i-том разряде складываются a[i],b[i] и входной бит переноса (carry-in bit) c[i]. Младший разряд суммы записывается в i-й разряд ответа (s[i]), а старший становится выходным битом переноса (carry-out bit) c[i+1] и используется при сложении в следующем разряде.
  
Сложение с предвычислением переносов
 
  
В каскадном сумматоре бит переноса ci вычисляется в момент времени i. Значения ai и bi, однако, известны с самого начала. В некоторых случаях они определяют бит переноса ci:
 
если ai = bi = 0, то ci = 0 (перенос "поглощается" (kill))
 
если ai = bi = 1, то ci = 1 (перенос "порождается" (generate))
 
  
Однако если один из битов ai и bi равен 1, а другой 0, то ci-1 существен; именно,
 
если 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): достаточно подать биты переноса на входы сумматоров.
 
 
[[Файл:Ripple_carry_adder.png]]  
 
[[Файл:Ripple_carry_adder.png]]  
  

Версия 18:08, 15 октября 2010

Каскадный сумматор

Каскадный сумматор - логическая цепь, осуществляющая сложение многоразрядных двоичных чисел.


При сложении двух чисел в i-том разряде складываются a[i],b[i] и входной бит переноса (carry-in bit) c[i]. Младший разряд суммы записывается в i-й разряд ответа (s[i]), а старший становится выходным битом переноса (carry-out bit) c[i+1] и используется при сложении в следующем разряде.



Ripple carry adder.png


См. также