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

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

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

Взгляд вперед

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

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

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

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

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

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

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

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

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

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

Метод переноса вперед

Логика Carry-lookahead использует концепции генерации и распространения переносов. Хотя в контексте сумматора с Carry-lookahead наиболее естественно думать о генерации и распространении в контексте двоичного сложения, эти концепции могут использоваться более широко. В описаниях ниже слово цифра может быть заменено на бит при ссылке на двоичное сложение 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}$

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

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

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

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

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

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

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

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

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

Для двоичной арифметики or быстрее, чем 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 (поскольку его уравнение равно ), и член становится нерелевантным. XOR обычно используется в базовой схеме полного сумматора; 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}}$

Для приведенного примера логика для значений generate ( ) и propagate ( ) приведена ниже. Числовое значение определяет сигнал из схемы выше, начиная с 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}}$

Четырехбитный сумматор с опережением переноса может также использоваться в схеме более высокого уровня, если каждая логическая схема CLA будет производить сигнал распространения и генерации для логической схемы CLA более высокого уровня. Групповое распространение ( ) и групповая генерация ( ) для четырехбитной 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 XOR B1) XOR ((A0 И B0) ИЛИ ((A0 XOR B0) И Cin)) '4dt S2 = (A2 XOR B2) XOR ((A1 И B1) ИЛИ ((A1 XOR B1) И (A0 И B0)) ИЛИ ((A1 XOR B1) И (A0 XOR B0) И Cin)) '4dtS3 = (A3 XOR B3) XOR ((A2 И B2) ИЛИ ((A2 XOR B2) И (A1 И B1)) ИЛИ ((A2 XOR B2) И (A1 XOR B1) И (A0 И B0)) ИЛИ ((A2 XOR B2) И (A1 XOR B1) И (A0 XOR B0) И Cin)) '4dtCout = (A3 И B3) ИЛИ ((A3 XOR B3) И (A2 И B2)) ИЛИ ((A3 XOR B3) И (A2 XOR B2) И (A1 И B1)) ИЛИ ((A3 XOR B3) И (A2 XOR B2) И (A1 XOR B1) И (A0 И B0)) ИЛИ ((A3 XOR B3) И (A2 XOR B2) И (A1 XOR B1) И (A0 XOR B0) И Cin) '3dt

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

«Шаг 0»Джин = Син '0дтP00 = A0 XOR B0 '1dtG00 = A0 И B0 '1dtP10 = A1 XOR B1 '1dtG10 = A1 И B1 '1dtP20 = A2 XOR B2 '1dtG20 = A2 И B2 '1dtP30 = A3 XOR B3 '1dtG30 = A3 И B3 '1dt«Шаг 1»G01 = G00 ИЛИ_ P00 И Gin '3dt, C0, валентность-2G11 = G10 ИЛИ_ P10 И G00 ИЛИ_ P10 И P00 И Gin '3dt, C1, валентность-3G21 = G20 ИЛИ_ P20 И G10 ИЛИ_ P20 И P10 И G00 ИЛИ_ P20 И P10 И P00 И Gin '3dt, C2, валентность-4G31 = G30 ИЛИ_ P30 И G20 ИЛИ_ P30 И P20 И G10 ИЛИ_ P30 И P20 И P10 И G00 ИЛИ_ P30 И P20 И P10 И P00 И Gin '3dt, C3, валентность-5«Сумма»S0 = P00 XOR Джин '2dtS1 = P10 XOR G01 '4dtS2 = P20 XOR G11 '4dtS3 = P30 XOR G21 '4dtS4 = G31 '3dt, Cout

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

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

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

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

Ссылки

1. «Аналитическая машина – История аналитической машины Чарльза Бэббиджа». history-computer.com . 4 января 2021 г. . Получено 19 июня 2021 г. .
2. Бэббидж, Чарльз (1864). Отрывки из жизни философа. Лондон: Longman, Green, Longmand Roberts & Green. С. 59–63, 114–116.
3. Рохас, Рауль (2014-06-07). "Z1: Архитектура и алгоритмы первого компьютера Конрада Цузе". arXiv : 1406.1886 [cs.AR].
4. Розенбергер, Джеральд Б. (1960-12-27). «Сумматор с одновременным переносом». Патент США 2,966,305.
5. "Manchester carry-chain adder - WikiChip". en.wikichip.org . Получено 24.04.2017 .

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

• Аппаратные алгоритмы для арифметических модулей, исследовательская группа ARITH, лаборатория Аоки, Университет Тохоку
• Katz, Randy (1994). Contemporary Logic Design . Том 26. The Benjamin/Cummings Publishing Company . С. 249–256. doi :10.1016/0026-2692(95)90052-7. ISBN 0-8053-2703-7. {{cite book}}: |journal=проигнорировано ( помощь )
• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .

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

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