Изменения

<div style{{Определение|definition="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text'''Двоичный каскадный сумматор''' (англ. ''Binary adder'') {{-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div><includeonly>}} цифровая [[Категория: В разработкеРеализация булевой функции схемой из функциональных элементов|схема]]</includeonly>, осуществляющая сложение двух многоразрядных двоичных чисел, с ускоренным формированием разрядов переноса.}}

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