Изменения

Рассмотрим один элемент полного сумматора:{{Определение[[Файл:Полный_сумматор_1|definition='''Двоичный каскадный сумматор''' (англ.png‎|200px|left]] Где <tex>X_''Binary adder'') {i}, Y_{i}</tex> - i-ный разряд суммируемых чисел, <tex>C_{i}, C_{i+1}</tex> - Биты переноса, а <tex>F_{i}</tex> - Результат сложения.<Br/><Br/><Br/><Br/><Br/>Построим таблицу зависимости <tex>C_{i+1}</tex> от <tex>X_{i}, Y_{i}, C_{i}</tex>, и введем условные обозначения:<Br/>[[Файл:Таблица_истиности_для_полного_сумматора.png‎|350px]]<Br/>Обозначим композицию действий над переносами значком <tex>\bigotimes</tex> и рассмотрим таблицу:{| border="1" !<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/>

Схема двоичного Рассмотрим один элемент [[Каскадный сумматор|линейного каскадного сумматора выглядит - Ripple-carry adder]]. В некоторых случаях бит переноса <tex>C_{i+1}</tex> зависит только от значений <tex>X_{i}</tex> и <tex>Y_{i}</tex>: * если <tex>X_{i} = Y_{i} = 1</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}</tex> {{---}} ''порождение'' переноса,* <tex> \mathbf{k} \mathtt{ill}</tex> {{---}} ''уничтожение'' переноса,* <tex> \mathbf{p} \mathtt{ropagate}</tex> {{---}} ''проталкивание'' переноса. Поскольку последовательное применение этих трёх действий над переносами принадлежит также одному из этих типов, то можно определить композицию действий над переносами. Обозначим композицию значком <tex>\otimes</tex> и построим таблицу значений (в столбце первый аргумент, в строке — второй):[[Файл:Двоичный_каскадный_сумматорПример компазиции.pngpng‎|right|450px|thumb|560pxПример композиции]]{| 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<Br/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>. == См. также ==*[[Каскадный сумматор]]*[[Сумматор]]*[[Троичный сумматор]] [[Категория:Дискретная математика и алгоритмы]][[Категория:Схемы из функциональных элементов]] == Источники информации ==* [http://rubookfi.net/book/556972 Е.wikipediaУгрюмов "Цифровая схемотехника" 2001г.org]  * [http:/wiki/Дерево_отрезковbookfi.net/book/532753 Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.], с помощью которого, вычисляется бит переноса * [http://bookfi.net/book/637011 М.И. Вторая часть это группа полных сумматоров, вычисляющих ответБогданович "Цифровые интегральные микросхемы" 1996г.]