Схема ускоренного переноса

Схема ускоренного переноса — комбинационная логическая схема, входит в арифметико-логическое устройство большинства современных ЭВМ микропроцессоров и микроконтроллеров.

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

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

Принцип работы

Термины:
Carry Lookahead Unit (CLU) — схема ускоренного переноса.
Carry Look-ahead Adder (CLA) — схема сумматора с ускоренным переносом.
Group propagate (PG) — групповой сигнал распространения переноса.
Group generate (GG) — групповой сигнал генерации переноса.

При использовании схемы ускоренного переноса (LCU) каждый одинарный разряд сумматора вырабатывает сигнал генерации переноса ( g n {displaystyle g_{n}} ) и сигнал распространения переноса ( p n {displaystyle p_{n}} ).

4-битная схема

4-битный сумматор со схемой ускоренного переноса.

Одинарные разряды сумматора объединяются в группы по четыре одинарных разряда в каждой группе. Схема ускоренного переноса вырабатывает сигналы переноса C 1 , C 2 , C 3 , C 4 , {displaystyle C_{1},C_{2},C_{3},C_{4},} групповой сигнал генерации переноса (GG) и групповой сигнал распространения переноса (PG).

Логическое выражение для переноса в одном разряде:

C i + 1 = a i ⋅ b i + ( a i ⊕ b i ) C i = G i + P i ⋅ C i {displaystyle C_{i+1}=a_{i}cdot b_{i}+(a_{i}oplus b_{i})C_{i}=G_{i}+P_{i}cdot C_{i}} , где G i = a i ⋅ b i {displaystyle G_{i}=a_{i}cdot b_{i}} P i = a i ⊕ b i {displaystyle P_{i}=a_{i}oplus b_{i}}

Здесь точка ( ⋅ {displaystyle cdot } ) означает логическое И (AND), знак сложения (+) - логическое ИЛИ (OR) и символ ⊕ {displaystyle oplus } сложение по модулю 2 ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Для переносов в четырёх разрядах:

C 1 = G 0 + P 0 ⋅ C 0 {displaystyle C_{1}=G_{0}+P_{0}cdot C_{0}} C 2 = G 1 + P 1 ⋅ C 1 {displaystyle C_{2}=G_{1}+P_{1}cdot C_{1}} C 3 = G 2 + P 2 ⋅ C 2 {displaystyle C_{3}=G_{2}+P_{2}cdot C_{2}} C 4 = G 3 + P 3 ⋅ C 3 {displaystyle C_{4}=G_{3}+P_{3}cdot C_{3}}

Подставив C 1 {displaystyle C_{1}} в C 2 {displaystyle C_{2}} , затем C 2 {displaystyle C_{2}} в C 3 {displaystyle C_{3}} , затем C 3 {displaystyle C_{3}} в C 4 {displaystyle C_{4}} получим окончательные выражения:

C 1 = G 0 + P 0 ⋅ C 0 {displaystyle C_{1}=G_{0}+P_{0}cdot C_{0}} C 2 = G 1 + G 0 ⋅ P 1 + C 0 ⋅ P 0 ⋅ P 1 {displaystyle C_{2}=G_{1}+G_{0}cdot P_{1}+C_{0}cdot P_{0}cdot P_{1}} C 3 = G 2 + G 1 ⋅ P 2 + G 0 ⋅ P 1 ⋅ P 2 + C 0 ⋅ P 0 ⋅ P 1 ⋅ P 2 {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}} C 4 = G 3 + G 2 ⋅ P 3 + G 1 ⋅ P 2 ⋅ P 3 + G 0 ⋅ P 1 ⋅ P 2 ⋅ P 3 + C 0 ⋅ P 0 ⋅ P 1 ⋅ P 2 ⋅ P 3 {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}}

Групповой сигнал генерации переноса G G {displaystyle GG} и групповой сигнал распространения переноса P G {displaystyle PG} формируются следующим образом:

P G = P 0 ⋅ P 1 ⋅ P 2 ⋅ P 3 {displaystyle PG=P_{0}cdot P_{1}cdot P_{2}cdot P_{3}} G G = G 3 + G 2 ⋅ P 3 + G 1 ⋅ P 3 ⋅ P 2 + G 0 ⋅ P 3 ⋅ P 2 ⋅ P 1 {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-битная схема ускоренного переноса выпускается в интегральном исполнении, например: SN74182 (ТТЛ), MC10179 (ЭСЛ) и MC14582, 564ИП4 (выполненная по технологии КМОП).

16-битная схема

16-разрядный сумматор может быть создан путём объединения четырёх 4-битных сумматоров с четырьмя схемами ускоренного переноса (4-bit CLA Adder), дополненных пятой схемой ускоренного переноса, которая используется для обработки групповых сигналов генерации переноса — GG и распространения переноса — PG.

Принимаемые на входе сигналы распространения переноса ( P G {displaystyle PG} ) и генерируемые каждой их четырёх схем сигналы (GG). Затем, схема ускоренного переноса генерирует соответствующие сигналы.

Предположим, что P i {displaystyle P_{i}} это сигналы PG и G i {displaystyle G_{i}} это GG из iй, то выходные биты устанавливаются следующим образом:

C 4 = G 0 + P 0 ⋅ C 0 {displaystyle C_{4}=G_{0}+P_{0}cdot C_{0}} C 8 = G 4 + P 4 ⋅ C 4 {displaystyle C_{8}=G_{4}+P_{4}cdot C_{4}} C 12 = G 8 + P 8 ⋅ C 8 {displaystyle C_{12}=G_{8}+P_{8}cdot C_{8}} C 16 = G 12 + P 12 ⋅ C 12 {displaystyle C_{16}=G_{12}+P_{12}cdot C_{12}}

Подставляя C 4 {displaystyle C_{4}} сперва в C 8 {displaystyle C_{8}} , затем C 8 {displaystyle C_{8}} в C 12 {displaystyle C_{12}} , затем C 12 {displaystyle C_{12}} в C 16 {displaystyle C_{16}} получаем следующее выражение:

C 4 = G 0 + P 0 ⋅ C 0 {displaystyle C_{4}=G_{0}+P_{0}cdot C_{0}} C 8 = G 4 + G 0 ⋅ P 4 + C 0 ⋅ P 0 ⋅ P 4 {displaystyle C_{8}=G_{4}+G_{0}cdot P_{4}+C_{0}cdot P_{0}cdot P_{4}} C 12 = G 8 + G 4 ⋅ P 8 + G 0 ⋅ P 4 ⋅ P 8 + C 0 ⋅ P 0 ⋅ P 4 ⋅ P 8 {displaystyle C_{12}=G_{8}+G_{4}cdot P_{8}+G_{0}cdot P_{4}cdot P_{8}+C_{0}cdot P_{0}cdot P_{4}cdot P_{8}} C 16 = G 12 + G 8 ⋅ P 12 + G 4 ⋅ P 8 ⋅ P 12 + G 0 ⋅ P 4 ⋅ P 8 ⋅ P 12 + C 0 ⋅ P 0 ⋅ P 4 ⋅ P 8 ⋅ P 12 {displaystyle C_{16}=G_{12}+G_{8}cdot P_{12}+G_{4}cdot P_{8}cdot P_{12}+G_{0}cdot P_{4}cdot P_{8}cdot P_{12}+C_{0}cdot P_{0}cdot P_{4}cdot P_{8}cdot P_{12}}

C 4 {displaystyle C_{4}} соответственно генерирует бит переноса на вход второй схемы; C 8 {displaystyle C_{8}} на вход третьей; C 12 {displaystyle C{12}} на вход четвёртой; и C 16 {displaystyle C_{16}} генерирует бит переполнения.

Кроме того, можно указать сигналы распространения переноса и генерации переноса для схемы ускоренного переноса:

P L C U = P 0 ⋅ P 4 ⋅ P 8 ⋅ P 12 {displaystyle P_{LCU}=P_{0}cdot P_{4}cdot P_{8}cdot P_{12}} G L C U = G 12 + G 8 ⋅ P 12 + G 4 ⋅ P 12 ⋅ P 8 + G 0 ⋅ P 12 ⋅ P 8 ⋅ P 4 {displaystyle G_{LCU}=G_{12}+G_{8}cdot P_{12}+G_{4}cdot P_{12}cdot P_{8}+G_{0}cdot P_{12}cdot P_{8}cdot P_{4}} 16-разрядный сумматор со схемой ускоренного переноса.

64-битная схема

Объединив четыре схемы сумматора и схему ускоренного переноса вместе, получим 16-битный сумматор. Четыре таких блока могут быть объединены в 64-разрядный сумматор. Дополнительные схемы ускоренного переноса (второго уровня) необходимы, чтобы принимать сигналы распространения переноса ( P L C U {displaystyle P_{LCU}} ) и сигналы генерации переноса( G L C U {displaystyle G_{LCU}} ) от каждой схемы сумматора.

64-разрядный сумматор со схемой ускоренного переноса второго уровня.

Достоинства и недостатки

Достоинства:

• Высокая скорость работы.

Недостатки:

• Большие затраты оборудования

Схемы формирования параллельного переноса имеют существенное преимущество в скорости перед схемами последовательного переноса.