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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Принцип работы)
Строка 5: Строка 5:
 
== Принцип работы ==
 
== Принцип работы ==
 
[[Файл:Полный_сумматор_1.png‎|right|200px|thumb|[[Cумматор#.D0.9F.D0.BE.D0.BB.D0.BD.D1.8B.D0.B9_.D1.81.D1.83.D0.BC.D0.BC.D0.B0.D1.82.D0.BE.D1.80|Полный сумматор]]]]
 
[[Файл:Полный_сумматор_1.png‎|right|200px|thumb|[[Cумматор#.D0.9F.D0.BE.D0.BB.D0.BD.D1.8B.D0.B9_.D1.81.D1.83.D0.BC.D0.BC.D0.B0.D1.82.D0.BE.D1.80|Полный сумматор]]]]
−
'''Обозначения:'''
+
Используемые обозначения: <tex>X_{i}, Y_{i}</tex> {{---}} <tex>i</tex>-ый разряд суммируемых чисел, <tex>C_{i}, C_{i+1}</tex> {{---}} биты переноса, <tex>F_{i}</tex> {{---}} результат сложения.
−
* <tex>X_{i}, Y_{i}</tex> {{---}} i-ый разряд суммируемых чисел
 
−
* <tex>C_{i}, C_{i+1}</tex> {{---}} биты переноса
 
−
* <tex>F_{i}</tex> {{---}} результат сложения.
 
  
 
Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>:  
 
Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>:  
−
* Generate(g): если <tex>X_{i} = Y_{i} = 1</tex>,&nbsp;&nbsp;то <tex>C_{i+1} = 1</tex>
+
* если <tex>X_{i} = Y_{i} = 1</tex>, то <tex>C_{i+1} = 1</tex>
−
* Kill(k): если <tex>X_{i} = Y_{i} = 0</tex>,&nbsp;&nbsp;то <tex>C_{i+1} = 0</tex>,
+
* если <tex>X_{i} = Y_{i} = 0</tex>, то <tex>C_{i+1} = 0</tex>
−
* Propagate(p): если <tex>X_{i} \ne Y_{i}</tex>,&nbsp;&nbsp;то <tex>C_{i+1} = C_{i}</tex>, 
+
Иначе (<tex>X_i \neq Y_i</tex>) бит переноса не изменяется, то есть <tex>C_{i + 1} = C_i</tex>.
  
 +
Три случая называются следующим образом:
 +
* '''G'''enerate {{---}} "порождение" переноса
 +
* '''K'''ill {{---}} "уничтожение" переноса
 +
* '''P'''ropagate {{---}} "проталкивание" переноса
  
−
Обозначим композицию действий над переносами значком <tex>\bigotimes</tex> и построим таблицу значений(в столбце первый аргумент, в строке — второй):
+
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
 +
[[Файл:Пример компазиции.png‎|right|430px|thumb|Пример композиции]]
 
{| border="1" cellpadding="5"
 
{| border="1" cellpadding="5"
−
  !<tex>\bigotimes</tex>
+
  !<tex>\otimes</tex>
 
  !k
 
  !k
 
  !p
 
  !p
Строка 40: Строка 42:
 
  |}
 
  |}
  
−
 
+
Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия <tex>x</tex> выполняется равенство <tex>x \otimes p = x</tex>, то функцию от нескольких действий можно определить как "последнее не <tex>p</tex>".
−
 
 
−
'''Пример'''
 
−
 
 
−
[[Файл:Пример компазиции.png‎|430px|Пример композиции]]
 
−
 
 
−
''' Замечание: ''' так как значение <tex>x \otimes p = x</tex>, функцию <tex>\bigotimes</tex> можно определить как последнее не "p".
 
−
 
 
  
 
== Схема ==
 
== Схема ==

Версия 13:56, 12 января 2012

Определение:
Двоичный каскадный сумматор — цифровая схема, осуществляющая сложение двух многоразрядных двоичных чисел.


Принцип работы

Полный сумматор

Используемые обозначения: [math]X_{i}, Y_{i}[/math] — [math]i[/math]-ый разряд суммируемых чисел, [math]C_{i}, C_{i+1}[/math] — биты переноса, [math]F_{i}[/math] — результат сложения.

Рассмотрим один элемент линейного каскадного сумматора. В некоторых случаях бит переноса [math]C_{i+1}[/math] зависит только от значений [math]X_{i}[/math] и [math]Y_{i}[/math]:

  • если [math]X_{i} = Y_{i} = 1[/math], то [math]C_{i+1} = 1[/math]
  • если [math]X_{i} = Y_{i} = 0[/math], то [math]C_{i+1} = 0[/math]

Иначе ([math]X_i \neq Y_i[/math]) бит переноса не изменяется, то есть [math]C_{i + 1} = C_i[/math].

Три случая называются следующим образом:

  • Generate — "порождение" переноса
  • Kill — "уничтожение" переноса
  • Propagate — "проталкивание" переноса

Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком [math]\otimes[/math] и построим таблицу значений (в столбце первый аргумент, в строке — второй):

Пример композиции
[math]\otimes[/math] k p g
k k k g
p k p g
g k g g

Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия [math]x[/math] выполняется равенство [math]x \otimes p = x[/math], то функцию от нескольких действий можно определить как "последнее не [math]p[/math]".

Схема

Схема двоичного каскадного сумматора

Сумматор состоит из двух частей. Первая часть — это группа полных сумматоров, вычисляющих ответ. Вторая часть — дерево отрезков, с помощью которого вычисляется бит переноса.

Обозначения

  • [math]"+"[/math] — полный сумматор, вычисляет результат сложения.
  • [math]\bigotimes[/math] вычисляет композицию двух переносов.
  • [math]\bigodot[/math] возвращает [math]C_{i}[/math], старший бит сумматора.

Схемная сложность

Дерево отрезков вычисляет биты переноса за [math]O(\log N)[/math], оставшиеся действия выполняются за [math]O(1)[/math]. Суммарное время работы — [math]O(\log N)[/math].


Ссылки

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