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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (ну блин)
м (rollbackEdits.php mass rollback)
 
(не показаны 33 промежуточные версии 4 участников)
Строка 1: Строка 1:
−
Рассмотрим один элемент полного сумматора:
+
{{Определение
−
[[Файл:Полный_сумматор_1.png‎|200px|left]] Где <tex>X_{i}, Y_{i}</tex> - i-ный разряд суммируемых чисел, <tex>C_{i}, C_{i+1}</tex> - Биты переноса, а <tex>F_{i}</tex> - Результат сложения.
+
|definition='''Двоичный каскадный сумматор''' (англ. ''Binary adder'') {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.
−
<Br/>
+
}}
−
<Br/>
+
 
−
<Br/>
+
== Принцип работы ==
−
<Br/>
+
[[Файл:Полный_сумматор_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|Полный сумматор]]]]
−
<Br/>
+
Используемые обозначения: <tex>X_{i}, Y_{i}</tex> {{---}} <tex>i</tex>-ый разряд суммируемых чисел, <tex>C_{i}, C_{i+1}</tex> {{---}} биты переноса, <tex>F_{i}</tex> {{---}} результат сложения.
−
Построим таблицу зависимости <tex>C_{i+1}</tex> от <tex>X_{i}, Y_{i}, C_{i}</tex>, и введем условные обозначения:
+
 
−
{| border="1"
+
Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора - Ripple-carry adder]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>:
−
| x || y || <tex> C_i \rightarrow C_{i+1} </tex> || Условные обозначения ||align="center" | Действие
+
* если <tex>X_{i} = Y_{i} = 1</tex>, то <tex>C_{i+1} = 1</tex>,
−
|- align="center"
+
* если <tex>X_{i} = Y_{i} = 0</tex>, то <tex>C_{i+1} = 0</tex>;
−
| 0 || 0 || 0 || k(kill) || Поглощение переноса
+
Иначе (<tex>X_i \neq Y_i</tex>) бит переноса не изменяется, то есть <tex>C_{i + 1} = C_i</tex>.
−
|- align="center"
+
 
−
| 0 || 1
+
Три случая называются следующим образом:
−
| rowspan="2"| <tex> P_1 </tex> ||rowspan="2"| p(propagate) ||rowspan="2"| Перенос переноса
+
* <tex> \mathbf{g} \mathtt{enerate}</tex> {{---}} ''порождение'' переноса,
−
|- align="center"
+
* <tex> \mathbf{k} \mathtt{ill}</tex> {{---}} ''уничтожение'' переноса,
−
| 1 || 0
+
* <tex> \mathbf{p} \mathtt{ropagate}</tex> {{---}} ''проталкивание'' переноса.
−
|- align="center"
+
 
−
| 1 || 1 || 1 || g(generate) || Порождение переноса
+
Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):
 +
[[Файл:Пример компазиции.png‎|right|450px|thumb|Пример композиции]]
 +
{| class="wikitable" align="center" style="color: blue; background-color:#ccffcc;" cellpadding="3"
 +
!colspan="20"|Таблица значений
 +
|-align="center"
 +
| <tex>\otimes</tex> || <tex> \mathbf{k} </tex> || <tex> \mathbf{p} </tex> || <tex> \mathbf{g} </tex>
 +
|-align="center"
 +
| <tex> \mathbf{k} </tex> || <tex>k</tex> || <tex>k</tex> || <tex>g</tex>
 +
|-align="center"
 +
| <tex> \mathbf{p} </tex> || <tex>k</tex> || <tex>p</tex> || <tex>g</tex>
 +
|-align="center"
 +
| <tex> \mathbf{g} </tex> || <tex>k</tex> || <tex>g</tex> || <tex>g</tex>
 +
|-align="center"
 
|}
 
|}
  
 +
Поскольку функция ассоциативна, то можно распространить её на любое количество аргументов. Более того, поскольку для любого действия <tex>x</tex> выполняется равенство <tex>x \otimes p = x</tex>, то функцию от нескольких действий можно определить как "последнее не <tex>p</tex>".
 +
 +
== Схема ==
 +
 +
Сумматор состоит из двух частей. Первая часть {{---}} это группа полных сумматоров, вычисляющих ответ. Вторая часть {{---}} [[Дерево_отрезков._Построение|дерево отрезков]], с помощью которого вычисляется бит переноса.
 +
[[Файл:Двоичный_каскадный_сумматор.png|450px|left|thumb|Схема двоичного каскадного сумматора]]
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
''' Обозначения '''
 +
* <tex>+  </tex> {{---}} полный сумматор, вычисляет результат сложения,
 +
* <tex>\bigotimes</tex> {{---}} блок вычисления композиции двух переносов,
 +
* <tex>\bigodot</tex> {{---}} блок вычисления <tex>C_{i}</tex>, старшего бита сумматора.
 +
 +
== Схемная сложность ==
 +
Дерево отрезков вычисляет биты переноса за <tex>O(\log N)</tex>, оставшиеся действия выполняются за <tex>O(1)</tex>. Суммарное время работы {{---}} <tex>O(\log N)</tex>.
 +
 +
== См. также ==
 +
*[[Каскадный сумматор]]
 +
*[[Сумматор]]
 +
*[[Троичный сумматор]]
 +
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Схемы из функциональных элементов]]
  
−
Обозначим композицию действий над переносами  значком <tex>\bigotimes</tex> и рассмотрим таблицу:
+
== Источники информации ==
−
{| border="1"
+
* [http://bookfi.net/book/556972  Е. Угрюмов "Цифровая схемотехника" 2001г.]  
−
!<tex>\bigotimes</tex>
 
−
!k
 
−
!p
 
−
!g
 
−
|-
 
−
!k
 
−
|k
 
−
|k
 
−
|g
 
−
|-
 
−
!p
 
−
|k
 
−
|p
 
−
|g
 
−
|-
 
−
!g
 
−
|k
 
−
|g
 
−
|g
 
−
|-
 
−
|}
 
−
<Br/>
 
−
Пример:
 
−
<Br/>[[Файл:Пример компазиции.png‎|430px]]
 
−
<Br/>
 
−
Таким образом функцию <tex>\bigotimes</tex> можно определить как последнее не "P".
 
−
<Br/><Br/>
 
−
Пусть <tex>f_{i}\epsilon \left \{k,p,g\right \}</tex>, тогда: <tex>C_{i}=(f_{1}\bigotimes f_{2}\bigotimes f_{3}\bigotimes...\bigotimes f_{i})_{(0)}</tex>.
 
−
<Br/>
 
−
<Br/>
 
−
Пусть элемент
 
−
[[Файл:Первый_элемент.png‎|130px]]
 
−
возвращает <tex>\bigotimes</tex> двух функций,<Br/> а элемент
 
−
[[Файл:Второй_элемент.png‎|130px]] возвращает <tex>C'</tex>, старший бит сумматора.
 
−
<Br/>
 
  
 +
* [http://bookfi.net/book/532753  Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.]
  
−
Схема двоичного каскадного сумматора выглядит следующим образом:
+
* [http://bookfi.net/book/637011 М.И. Богданович "Цифровые интегральные микросхемы" 1996г.]
−
[[Файл:Двоичный_каскадный_сумматор.png|560px]]
 
−
<Br/>
 
−
Сумматор состоит из двух частей. Первой частью является дерево отрезков [http://ru.wikipedia.org/wiki/Дерево_отрезков], с помощью которого, вычисляется бит переноса. Вторая часть это группа полных сумматоров, вычисляющих ответ.
 

Текущая версия на 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].

См. также

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

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