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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Carry-lookahead adder»  -  новости  · газеты  · книги  · ученый  · JSTOR ( август 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Перенос опережение сумматор (КЛК) или быстрый сумматор представляет собой тип электроники сумматора используется в цифровой логике. Сумматор с опережающим переносом увеличивает скорость за счет сокращения времени, необходимого для определения битов переноса. Его можно противопоставить более простому, но обычно более медленному сумматору с пульсационным переносом (RCA), для которого бит переноса вычисляется вместе с битом суммы, и каждый этап должен ждать, пока не будет вычислен предыдущий бит переноса, чтобы начать вычисление своего собственного. суммирующий бит и бит переноса. Сумматор с опережающим переносом вычисляет один или несколько битов переноса перед суммой, что сокращает время ожидания для вычисления результата битов большего значения сумматора. Kogge-камень сумматор (КСА) и Брент-кунг сумматор (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.

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

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

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

где - логическая конъюнкция (т. е. и ).${\ Displaystyle A \ cdot B}$

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

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

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

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

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

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

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

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

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

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

Детали реализации [ править ]

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

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

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

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

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}}$
• расчет производится во время 3,${\displaystyle C_{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 × 3 - 1 = 47 задержек затвора.

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

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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