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

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition='''Двоичный каскадный сумматор - Binary adder''' {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.
+
|definition='''Двоичный каскадный сумматор''' (англ. ''Binary adder'') {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.
 
}}
 
}}
  
Строка 13: Строка 13:
  
 
Три случая называются следующим образом:
 
Три случая называются следующим образом:
* <math> generate</math> {{---}} "порождение" переноса,
+
* <tex> \mathbf{g} \mathtt{enerate}</tex> {{---}} ''порождение'' переноса,
* <math>kill</math> {{---}} "уничтожение" переноса,
+
* <tex> \mathbf{k} \mathtt{ill}</tex> {{---}} ''уничтожение'' переноса,
* <math>propagate</math> {{---}} "проталкивание" переноса;
+
* <tex> \mathbf{p} \mathtt{ropagate}</tex> {{---}} ''проталкивание'' переноса.
  
 
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
 
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
Строка 22: Строка 22:
 
!colspan="20"|Таблица значений
 
!colspan="20"|Таблица значений
 
|-align="center"
 
|-align="center"
| <tex>\otimes</tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>
+
| <tex>\otimes</tex> || <tex> \mathbf{k} </tex> || <tex> \mathbf{p} </tex> || <tex> \mathbf{g} </tex>
 
|-align="center"
 
|-align="center"
| <tex>k</tex> || <tex>k</tex> || <tex>k</tex> || <tex>g</tex>
+
| <tex> \mathbf{k} </tex> || <tex>k</tex> || <tex>k</tex> || <tex>g</tex>
 
|-align="center"
 
|-align="center"
| <tex>p</tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>
+
| <tex> \mathbf{p} </tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>
 
|-align="center"
 
|-align="center"
| <tex>g</tex> || <tex>k</tex> || <tex>g</tex> || <tex>g</tex>
+
| <tex> \mathbf{g} </tex> || <tex>k</tex> || <tex>g</tex> || <tex>g</tex>
 
|-align="center"
 
|-align="center"
 
|}
 
|}
Строка 83: Строка 83:
 
* <tex>+  </tex> {{---}} полный сумматор, вычисляет результат сложения,
 
* <tex>+  </tex> {{---}} полный сумматор, вычисляет результат сложения,
 
* <tex>\bigotimes</tex> {{---}} блок вычисления композиции двух переносов,
 
* <tex>\bigotimes</tex> {{---}} блок вычисления композиции двух переносов,
* <tex>\bigodot</tex> {{---}} блок вычисления <tex>C_{i}</tex>, старшего бита сумматора;
+
* <tex>\bigodot</tex> {{---}} блок вычисления <tex>C_{i}</tex>, старшего бита сумматора.
  
 
== Схемная сложность ==
 
== Схемная сложность ==
 
Дерево отрезков вычисляет биты переноса за <tex>O(\log N)</tex>, оставшиеся действия выполняются за <tex>O(1)</tex>. Суммарное время работы {{---}} <tex>O(\log N)</tex>.
 
Дерево отрезков вычисляет биты переноса за <tex>O(\log N)</tex>, оставшиеся действия выполняются за <tex>O(1)</tex>. Суммарное время работы {{---}} <tex>O(\log N)</tex>.
 
  
 
== См. также ==
 
== См. также ==
 
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
 +
*[[Сумматор]]
 +
*[[Троичный сумматор]]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]

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

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


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

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

Рассмотрим один элемент линейного каскадного сумматора - Ripple-carry adder. В некоторых случаях бит переноса [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].

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

  • [math] \mathbf{g} \mathtt{enerate}[/math]порождение переноса,
  • [math] \mathbf{k} \mathtt{ill}[/math]уничтожение переноса,
  • [math] \mathbf{p} \mathtt{ropagate}[/math]проталкивание переноса.

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

Пример композиции
Таблица значений
[math]\otimes[/math] [math] \mathbf{k} [/math] [math] \mathbf{p} [/math] [math] \mathbf{g} [/math]
[math] \mathbf{k} [/math] [math]k[/math] [math]k[/math] [math]g[/math]
[math] \mathbf{p} [/math] [math]k[/math] [math]p[/math] [math]g[/math]
[math] \mathbf{g} [/math] [math]k[/math] [math]g[/math] [math]g[/math]

Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия [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].

См. также

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