Сумматор с упреждением - Carry-lookahead adder

4-битный сумматор с опережающим переносом

А сумматор с упреждением (CLA) или быстрый сумматор это тип сумматор электроники используется в цифровой логике. Сумматор с опережающим переносом увеличивает скорость за счет сокращения времени, необходимого для определения битов переноса. Его можно сравнить с более простым, но обычно более медленным, сумматор с волновым переносом (RCA), для которого бит переноса вычисляется вместе с битом суммы, и каждый этап должен ждать, пока не будет вычислен предыдущий бит переноса, чтобы начать вычисление своего собственного бита суммы и бита переноса. Сумматор с опережающим переносом вычисляет один или несколько битов переноса перед суммой, что сокращает время ожидания для вычисления результата битов большего значения сумматора. В Когге – Стоун гадюка (KSA) и Гадюка Брента-Кунга (BKA) являются примерами сумматора этого типа.

Чарльз Бэббидж признали снижение производительности, налагаемое переносом пульсации, и разработали механизмы для ожидание перевозки в его вычислительных машинах.^[1] Джеральд Б. Розенбергер из IBM подала заявку на патент на современный двоичный сумматор с упреждением в 1957 году.^[2]

Теория Операции

Сумматор с волновым переносом работает так же, как и карандашный и бумажный методы сложения. Начиная с самого правого (наименее значимый ) позиции цифры, две соответствующие цифры складываются и получается результат. Также возможно, что это положение цифры может быть перенесено (например, в карандашно-бумажном методе «9 + 5 = 4, перенос 1»). Соответственно, все позиции цифр, кроме самой правой, должны учитывать возможность добавления дополнительной единицы из переноса, который еще не поступил со следующей позиции справа.

Это означает, что никакая позиция цифры не может иметь абсолютно окончательного значения, пока не будет установлено, поступает перенос справа или нет. Более того, если сумма без переноса равна 9 (в методах карандаша и бумаги) или 1 (в двоичной арифметике), невозможно даже сказать, будет ли данная позиция цифры передавать перенос в положение слева. В худшем случае, когда вся последовательность сумм дойдет до… 99999999… (в десятичной системе) или… 11111111… (в двоичной системе), вообще ничего нельзя будет вывести, пока не станет известно значение переноса, приходящего справа, и это перенос затем продвигается влево, по одному шагу за раз, поскольку каждая позиция цифры оценивается как «9 + 1 = 0, перенос 1» или «1 + 1 = 0, перенос 1». Именно "рябь" переноса справа налево дала сумматору "рябь" название и его медленность. Например, при добавлении 32-битных целых чисел необходимо учитывать возможность того, что перенос может проходить через каждый из 32 однобитовых сумматоров.

Перенос вперед зависит от двух вещей:

1. Вычисление для каждой позиции цифры, будет ли эта позиция распространять перенос, если он входит справа.
2. Комбинируя эти вычисленные значения, можно быстро определить, будет ли эта группа распространять перенос, приходящий справа, для каждой группы цифр.

Предположим, что выбраны группы из четырех цифр, последовательность событий выглядит примерно так:

1. Все 1-битные сумматоры вычисляют свои результаты. Одновременно с этим модули прогнозирования выполняют свои вычисления.
2. Предполагая, что перенос возникает в определенной группе, этот перенос появится на левом конце группы в пределах не более пяти задержек гейта и начнет распространяться через группу слева от нее.
3. Если этот перенос будет распространяться на всю следующую группу, модуль просмотра вперед уже определил это. Соответственно, до того, как керри выйдет из следующей группы, модуль просмотра вперед немедленно (в пределах задержки одного строба) может сообщить Следующий группе слева, что он собирается получить перенос - и в то же время, чтобы сообщить следующему модулю просмотра слева, что переносится.

Чистый эффект заключается в том, что переносы начинаются с медленного распространения через каждую 4-битную группу, как в системе переноса с пульсацией, но затем перемещаются в четыре раза быстрее, перескакивая от одного блока упреждающего переноса к другому. Наконец, внутри каждой группы, которая получает перенос, перенос медленно распространяется внутри цифр в этой группе.

Чем больше битов в группе, тем сложнее становится логика упреждающего переноса, и тем больше времени тратится на «медленные пути» в каждой группе, а не на «быстрый путь» между группами (обеспечивается логикой упреждающего переноса) . С другой стороны, чем меньше битов в группе, тем больше групп нужно пройти, чтобы перейти от одного конца числа к другому, и в результате получается меньшее ускорение.

Решение о размере группы, которым должна управлять логика упреждающего переноса, требует подробного анализа задержек затвора и распространения для конкретной используемой технологии.

Возможно иметь более одного уровня логики упреждающего переноса, и это обычно обычно делается. Каждая единица упреждающего переноса уже выдает сигнал, в котором говорится: «Если перенос идет справа, я буду распространять его влево», и эти сигналы можно объединить так, чтобы каждая группа, скажем, из четырех единиц предпросмотра стала частью "супергруппы", управляющей всего 16 битами добавляемых чисел. Логика упреждающего переноса "супергруппы" сможет сказать, будет ли перенос, входящий в супергруппу, будет распространяться через нее, и, используя эту информацию, он сможет распространять переносы справа налево в 16 раз быстрее, чем наивный рябь нести. При такой двухуровневой реализации перенос может сначала распространяться по «медленной дороге» отдельных сумматоров, а затем, достигнув левого конца своей группы, распространяться по «быстрой дороге» 4-битного просмотра вперед. логика переноса, затем, достигнув левого конца своей супергруппы, распространяются по "сверхбыстрой дороге" 16-битной логики упреждающего переноса.

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

Для очень больших чисел (сотни или даже тысячи битов) логика упреждающего переноса не становится более сложной, потому что при необходимости можно добавить больше уровней супергрупп и супергрупп. Увеличение числа логических элементов также является умеренным: если все размеры группы равны четырем, то в итоге получится одна треть от количества модулей упреждающего переноса, чем имеется сумматоров. Однако «медленные дороги» на пути к более быстрым уровням начинают оказывать тормозящее воздействие на всю систему (например, 256-битный сумматор может иметь до 24 задержек при обработке переноса), а простая физическая передача сигналов с одного конца длинного номера на другой становится проблемой. В этих размерах сумматоры предпочтительны, так как они вообще не тратят времени на распространение переноса.

Метод опережающего просмотра

Логика переноса вперед использует концепции создание и распространение несет. Хотя в контексте сумматора с предварительным просмотром наиболее естественно думать о генерации и распространении в контексте двоичного сложения, эти концепции можно использовать и в более общем плане. В описаниях ниже слово цифра можно заменить на немного когда речь идет о двоичном сложении 2.

Добавление двух 1-значных входов А и B говорят генерировать если добавление всегда будет переноситься, независимо от того, есть ли перенос ввода (эквивалентно, независимо от того, переносятся ли какие-либо менее значащие цифры в сумме). Например, в десятичном сложении 52 + 67 сложение десятков цифр 5 и 6 генерирует потому что результат переносится в разряд сотен независимо от того, переносятся ли цифры единиц (в примере, цифры единиц не переносят (2 + 7 = 9)).

В случае двоичного сложения ${\displaystyle A+B}$ генерируется тогда и только тогда, когда оба А и B равны 1. Если мы напишем ${\displaystyle G(A,B)}$ для представления бинарного предиката, который истинен тогда и только тогда, когда ${\displaystyle A+B}$ генерирует, у нас есть

${\displaystyle G(A,B)=A\cdot B}$

где ${\displaystyle A\cdot B}$ это логическое соединение (т.е. и).

Добавление двух однозначных входов А и B говорят размножаться если добавление будет переноситься всякий раз, когда есть входной перенос (эквивалентно, когда переносится следующая менее значимая цифра в сумме). Например, в десятичном сложении 37 + 62 сложение десятков цифр 3 и 6 размножаться потому что результат будет равен сотням если те, которые должны были нести (чего в этом примере нет). Обратите внимание, что распространение и генерация определены относительно одной цифры сложения и не зависят от каких-либо других цифр в сумме.

В случае двоичного сложения ${\displaystyle A+B}$ распространяется тогда и только тогда, когда хотя бы один из А или B равно 1. Если ${\displaystyle P(A,B)}$ написан для представления двоичного предиката, который истинен тогда и только тогда, когда ${\displaystyle A+B}$ распространяется, есть

${\displaystyle P(A,B)=A+B}$

где ${\displaystyle A+B}$ в правой части уравнения стоит логическая дизъюнкция (т.е. или).

Иногда несколько иное определение размножаться используется. По этому определению А + В считается распространяющимся, если добавление будет переноситься всякий раз, когда есть входной перенос, но не будет переноситься, если входного переноса нет. Из-за того, что логика упреждающего переноса использует способ генерирования и распространения битов, не имеет значения, какое определение используется. В случае двоичного сложения это определение выражается следующим образом:

${\displaystyle P'(A,B)=A\oplus B}$

где ${\displaystyle A\oplus B}$ является Эксклюзивный или (т.е. xor).

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle C_{i}}$	${\displaystyle C_{o}}$	Тип переноски
0	0	0	0	Никто
0	0	1	0	Никто
0	1	0	0	Никто
0	1	1	1	Распространять
1	0	0	0	Никто
1	0	1	1	Распространять
1	1	0	1	Генерировать
1	1	1	1	Создать / распространить

Таблица, показывающая когда переносчики распространяются или генерируются.

Для двоичной арифметики или быстрее чем xor и требует меньше транзисторов. Однако для многоуровневого сумматора с прогнозированием проще использовать ${\displaystyle P'(A,B)}$.

С учетом этих концепций создания и распространения цифра сложения переносится именно тогда, когда либо добавление порождает или переносится следующий менее значимый бит, и сложение распространяется. Написано в логической алгебре, с ${\displaystyle C_{i}}$ бит переноса цифры я, и ${\displaystyle P_{i}}$ и ${\displaystyle G_{i}}$ распространять и генерировать биты цифры я соответственно,

${\displaystyle C_{i+1}=G_{i}+(P_{i}\cdot C_{i}).}$

Детали реализации

Для каждого бита в двоичной последовательности, которая должна быть добавлена, логика упреждающего переноса будет определять, будет ли эта битовая пара генерировать перенос или распространять перенос. Это позволяет схеме «предварительно обработать» два добавляемых числа для определения переноса заранее. Затем, когда выполняется фактическое добавление, нет задержки от ожидания эффекта переноса пульсации (или времени, необходимого для переноса с первого полный сумматор передается последнему полному сумматору). Ниже приведена простая 4-битная обобщенная схема упреждающего переноса, которая сочетается с 4-битным сумматором переноса пульсации, который мы использовали выше, с некоторыми небольшими корректировками:

В приведенном примере логика генерации (${\displaystyle G}$) и размножаются (${\displaystyle P}$) значения приведены ниже. Числовое значение определяет сигнал из схемы выше, начиная с 0 справа и заканчивая 3 слева:

${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0},}$

${\displaystyle C_{2}=G_{1}+P_{1}\cdot C_{1},}$

${\displaystyle C_{3}=G_{2}+P_{2}\cdot C_{2},}$

${\displaystyle C_{4}=G_{3}+P_{3}\cdot C_{3}.}$

Подстановка ${\displaystyle C_{1}}$ в ${\displaystyle C_{2}}$, тогда ${\displaystyle C_{2}}$ в ${\displaystyle C_{3}}$, тогда ${\displaystyle C_{3}}$ в ${\displaystyle C_{4}}$ дает следующие расширенные уравнения:

${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0},}$

${\displaystyle C_{2}=G_{1}+G_{0}\cdot P_{1}+C_{0}\cdot P_{0}\cdot P_{1},}$

${\displaystyle C_{3}=G_{2}+G_{1}\cdot P_{2}+G_{0}\cdot P_{1}\cdot P_{2}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2},}$

${\displaystyle C_{4}=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{2}\cdot P_{3}+G_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}+C_{0}\cdot P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}.}$

Чтобы определить, будет ли битовая пара генерировать перенос, работает следующая логика:

${\displaystyle G_{i}=A_{i}\cdot B_{i}.}$

Чтобы определить, будет ли битовая пара распространять перенос, работает любой из следующих логических операторов:

${\displaystyle P_{i}=A_{i}\oplus B_{i},}$

${\displaystyle P_{i}=A_{i}+B_{i}.}$

Причина, по которой это работает, основана на оценке ${\displaystyle C_{1}=G_{0}+P_{0}\cdot C_{0}}$. Единственная разница в таблицах истинности между (${\displaystyle A\oplus B}$) и (${\displaystyle A+B}$) когда оба ${\displaystyle A}$ и ${\displaystyle B}$ равны 1. Однако если оба ${\displaystyle A}$ и ${\displaystyle B}$ равны 1, то ${\displaystyle G_{0}}$ член равен 1 (так как его уравнение ${\displaystyle A\cdot B}$), а ${\displaystyle P_{0}\cdot C_{0}}$ термин становится неактуальным. XOR обычно используется в базовой схеме полного сумматора; OR - альтернативный вариант (только для предварительного просмотра), который намного проще с точки зрения количества транзисторов.

4-битный сумматор с опережающим переносом также может использоваться в схеме более высокого уровня, если каждая логическая схема CLA выдает сигнал распространения и генерирования для логической схемы CLA более высокого уровня. Группа размножается (${\displaystyle PG}$) и группа генерируют (${\displaystyle GG}$) для 4-битного CLA:

${\displaystyle PG=P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3},}$

${\displaystyle GG=G_{3}+G_{2}\cdot P_{3}+G_{1}\cdot P_{3}\cdot P_{2}+G_{0}\cdot P_{3}\cdot P_{2}\cdot P_{1}.}$

Затем их можно использовать для создания переноса для этой конкретной 4-битной группы:

${\displaystyle CG=GG+PG\cdot C_{in}.}$

Видно, что это эквивалентно ${\displaystyle C_{4}}$ в предыдущих уравнениях.

Объединение четырех 4-битных CLA вместе дает четыре групповых распространения и четыре групповых генерации. опережающий отряд (LCU) принимает эти 8 значений и использует идентичную логику для вычисления ${\displaystyle C_{i}}$ Затем LCU генерирует вход переноса для каждого из 4 CLA и пятый, равный ${\displaystyle C_{16}}$.

Расчет задержка ворот 16-битного сумматора (с использованием 4 CLA и 1 LCU) не так прост, как сумматор с переносом пульсации.

Начиная с нуля:

• расчет ${\displaystyle P_{i}}$ и ${\displaystyle G_{i}}$ выполняется в момент 1,
• расчет ${\displaystyle C_{i}}$ выполняется во время 3,
• расчет ${\displaystyle PG}$ выполняется во время 2,
• расчет ${\displaystyle GG}$ выполняется во время 3,
• Расчет входов для CLA из LCU выполняется по адресу:
  • время 0 для первого CLA,
  • время 5 для второго, третьего и четвертого CLA,
• расчет ${\displaystyle S_{i}}$ выполняются по адресу:
  • время 4 для первого CLA,
  • время 8 для второго, третьего и четвертого CLA,
• расчет последнего бита переноса (${\displaystyle C_{16}}$) выполняется во время 5.

Максимальное время - 8 задержек гейта (для ${\displaystyle S_{[8-15]}}$).

Стандартный 16-битный сумматор с волновым переносом потребует 16 × 3 - 1 = 47 задержек гейта.

Манчестерская цепочка для переноски

Цепочка переноса Manchester - это вариант сумматора с упреждающим переносом^[3] который использует общую логику для уменьшения количества транзисторов. Как можно увидеть выше в разделе реализации, логика для генерации каждого переноса содержит всю логику, использованную для генерации предыдущих переносов. Цепочка переноса в Манчестере генерирует промежуточные переносы путем отвода узлов в вентиле, который вычисляет наиболее значимое значение переноса. Тем не менее, не все логические семьи имеют эти внутренние узлы, CMOS являясь главным примером. Динамическая логика может поддерживать общую логику, как и ворота передачи логика. Одним из основных недостатков манчестерской цепи переноса является то, что емкостная нагрузка всех этих выходов вместе с сопротивлением транзисторов заставляет задержку распространения увеличиваться намного быстрее, чем при обычном опережающем переносе. Секция Manchester-carry-chain обычно не превышает 4 бита.

Смотрите также

• Сумматор-скип
• Оператор перевозки
• Спекулятивное исполнение

использованная литература

1. Бэббидж, Чарльз (1864). Отрывки из жизни философа. Лондон: Longman, Green, Longmand Roberts & Green. стр.59 –63, 114–116.
2. Розенбергер, Джеральд Б. (1960-12-27). «Сумматор одновременного переноса». Патент США 2,966,305.
3. "Манчестерский сумматор для переноски - WikiChip". en.wikichip.org. Получено 2017-04-24.

дальнейшее чтение

• Аппаратные алгоритмы для арифметических модулей, Исследовательская группа ARITH, лаборатория Аоки, Университет Тохоку
• Кац, Рэнди (1994). Современный логический дизайн. Издательство "Бенджамин / Каммингс". стр.249–256. Дои:10.1016/0026-2692(95)90052-7. ISBN  0-8053-2703-7.
• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.

внешние ссылки

• Симулятор JavaScript Carry Look Ahead Adder