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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Каскадный сумматор ==
 
==Каскадный сумматор ==
'''Каскадный сумматор''' - логическая цепь, осуществляющая сложение много разрядных двоичных чисел.
+
'''Каскадный сумматор''' - логическая цепь, осуществляющая сложение многоразрядных двоичных чисел.
  
  
 
При сложении двух чисел в 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): достаточно подать биты переноса на входы сумматоров.
  
  

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

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

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


При сложении двух чисел в 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): достаточно подать биты переноса на входы сумматоров.


См. также

Сумматор

Двоичный каскадный сумматор