Сумматор с переносом вперед

Арифметико-логическая схема

Сумматор с упреждающим переносом (CLA) или быстрый сумматор — это тип электронного сумматора , используемого в цифровой логике. Сумматор с прогнозом переноса повышает скорость за счет сокращения времени, необходимого для определения битов переноса. Его можно противопоставить более простому, но обычно более медленному сумматору со пульсирующим переносом (RCA), в котором бит переноса вычисляется вместе с битом суммы, и каждый этап должен ждать, пока не будет вычислен предыдущий бит переноса, чтобы начать вычисление своего собственного. бит суммы и бит переноса. Сумматор с опережением переноса вычисляет один или несколько битов переноса перед суммой, что сокращает время ожидания для вычисления результата старших битов сумматора.

Уже в середине 1800-х годов Чарльз Бэббидж осознал снижение производительности, вызванное пульсирующим переносом, используемым в его разностной машине , и впоследствии разработал механизмы упреждения переноса для своей так и не созданной аналитической машины . ^{[1] [2] Считается, что} Конрад Цузе реализовал первый сумматор с упреждающим переносом в своем двоичном механическом компьютере 1930-х годов Zuse Z1 . ^[3] Джеральд Б. Розенбергер из IBM подал заявку на патент на современный двоичный сумматор с переносом и прогнозированием в 1957 году. ^[4]

Двумя широко используемыми реализациями этой концепции являются сумматор Когге-Стоуна (KSA) и сумматор Брента-Кунга (BKA).

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

Добавление пульсации

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

Это означает, что ни одна цифровая позиция не может иметь абсолютно окончательного значения до тех пор, пока не будет установлено, идет ли перенос справа. Более того, если сумма без переноса является самым высоким значением в базе (9 в методе с карандашом и бумагой по основанию 10 или 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.

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

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

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

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

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

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

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

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

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

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

где — исключающее или (т. е. xor ). ${\displaystyle A\oplus B}$

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

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

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

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

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

Частичный полный сумматор с выводами распространения и генерации.

Реализация логического элемента 4-битного сумматора с упреждающим переносом.

Блок-схема 4-битного сумматора с упреждающим переносом.

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

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

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

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

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

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

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

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

${\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}}$

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

${\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 значений и использует идентичную логику для вычислений в CLA. Затем LCU генерирует вход переноса для каждого из 4 CLA и пятого, равного . ${\displaystyle C_{i}}$ ${\displaystyle C_{16}}$

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

Начиная с нулевого времени:

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

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

Стандартный 16-битный сумматор с пульсирующим переносом потребует 16 × 2 − 1 = 31 задержку вентиля.

Расширение

Этот пример представляет собой 4-битный сумматор с упреждением переноса, имеет 5 выходов. Ниже представлено расширение:

S0 = (A0 XOR B0) XOR Cin '2dt (dt - время задержки)S1 = (A1 исключающее ИЛИ B1) Исключающее ИЛИ ((A0 И B0) ИЛИ ((A0 XOR B0) И Cin)) '4dt S2 = (A2 исключающее ИЛИ B2) Исключающее ИЛИ ((A1 И B1) ИЛИ ((A1 исключающее ИЛИ B1) И (A0 И B0)) ИЛИ ((A1 исключающее ИЛИ B1) И (A0 исключающее ИЛИ B0) И Cin)) '4dtS3 = (A3 исключающее ИЛИ B3) Исключающее ИЛИ ((A2 И B2) ИЛИ ((A2 исключающее ИЛИ B2) И (A1 И B1)) ИЛИ ((A2 исключающее ИЛИ B2) И (A1 исключающее ИЛИ B1) И (A0 И B0)) ИЛИ ((A2 исключающее ИЛИ B2) И (A1 исключающее ИЛИ B1) И (A0 исключающее ИЛИ B0) И Cin)) '4dtCout = (A3 И B3) ИЛИ ((A3 исключающее ИЛИ B3) И (A2 И B2)) ИЛИ ((A3 исключающее ИЛИ B3) И (A2 исключающее ИЛИ B2) И (A1 И B1)) ИЛИ ((A3 исключающее ИЛИ B3) И (A2 исключающее ИЛИ B2) И (A1 исключающее ИЛИ B1) И (A0 И B0)) ИЛИ ((A3 исключающее ИЛИ B3) И (A2 исключающее ИЛИ B2) И (A1 исключающее ИЛИ B1) И (A0 исключающее ИЛИ B0) И Cin) '3dt

Более простой 4-битный сумматор с переносом и прогнозированием:

'Шаг 0Джин = Cin '0dtP00 = A0 исключающее ИЛИ B0 '1dtG00 = A0 И B0 '1dtP10 = A1 исключающее ИЛИ B1 '1dtG10 = A1 И B1 '1dtP20 = A2 исключающее ИЛИ B2 '1dtG20 = A2 И B2 '1dtP30 = A3 исключающее ИЛИ B3 '1dtG30 = A3 И B3 '1dt'Шаг 1G01 = G00 ИЛИ_ P00 И Джин'3дт, С0, валентность-2G11 = G10 ИЛИ_ P10 И G00 ИЛИ_ P10 И P00 И Джин'3дт, С1, валентность-3G21 = G20 ИЛИ_ P20 И G10 ИЛИ_ P20 И P10 И G00 ИЛИ_ Р20 И Р10 И Р00 И Джин'3дт, С2, валентность-4G31 = G30 ИЛИ_ P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00 ИЛИ_ П30 И П20 И П10 И П00 И Джин'3дт, С3, валентность-5'СуммаS0 = P00 XOR Gin '2dtS1 = P10 исключающее ИЛИ G01 '4dtS2 = P20 исключающее ИЛИ G11 '4dtS3 = P30 исключающее ИЛИ G21 '4dtS4 = G31 '3dt, Cout

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

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

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

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

Рекомендации

1. «Аналитическая машина - История аналитической машины Чарльза Бэббиджа» . история-компьютер.com . 4 января 2021 г. Проверено 19 июня 2021 г.
2. Бэббидж, Чарльз (1864). Отрывки из жизни философа. Лондон: Лонгман, Грин, Лонгманд Робертс и Грин. стр. 59–63, 114–116.
3. Рохас, Рауль (07.06.2014). «Z1: Архитектура и алгоритмы первого компьютера Конрада Цузе». arXiv : 1406.1886 [cs.AR].
4. Розенбергер, Джеральд Б. (1960-12-27). «Сумматор одновременного переноса». Патент США 2966305.
5. "Манчестерский сумматор с цепочкой переноса - WikiChip" . ru.wikichip.org . Проверено 24 апреля 2017 г.

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

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

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

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