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

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

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

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

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

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

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

4-битная схемаПравить

 

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

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

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

$C_{i+1}=a_i\cdot <!--\; \cdot \; -->b_i+(a_i\oplus <!--\; \oplus \; -->b_i)C_i=G_i+P_i\cdot <!--\; \cdot \; -->C_i$$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\cdot <!--\; \cdot \; -->b_i$$G_{i}=a_{i}\cdot b_{i}$ 

$P_i=a_i\oplus <!--\; \oplus \; -->b_i$$P_{i}=a_{i}\oplus b_{i}$ 

Здесь точка ($\cdot <!--\; \cdot \; -->$$\cdot$ ) означает логическое И (AND), знак сложения (+) - логическое ИЛИ (OR) и символ $\oplus <!--\; \oplus \; -->$$\oplus$  сложение по модулю 2 ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

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

$C_1=G_0+P_0\cdot <!--\; \cdot \; -->C_0$$C_{1}=G_{0}+P_{0}\cdot C_{0}$ 

$C_2=G_1+P_1\cdot <!--\; \cdot \; -->C_1$$C_{2}=G_{1}+P_{1}\cdot C_{1}$ 

$C_3=G_2+P_2\cdot <!--\; \cdot \; -->C_2$$C_{3}=G_{2}+P_{2}\cdot C_{2}$ 

$C_4=G_3+P_3\cdot <!--\; \cdot \; -->C_3$$C_{4}=G_{3}+P_{3}\cdot C_{3}$ 

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

$C_1=G_0+P_0\cdot <!--\; \cdot \; -->C_0$$C_{1}=G_{0}+P_{0}\cdot C_{0}$ 

$C_2=G_1+G_0\cdot <!--\; \cdot \; -->P_1+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_1$$C_{2}=G_{1}+G_{0}\cdot P_{1}+C_{0}\cdot P_{0}\cdot P_{1}$ 

$C_3=G_2+G_1\cdot <!--\; \cdot \; -->P_2+G_0\cdot <!--\; \cdot \; -->P_1\cdot <!--\; \cdot \; -->P_2+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_1\cdot <!--\; \cdot \; -->P_2$$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\cdot <!--\; \cdot \; -->P_3+G_1\cdot <!--\; \cdot \; -->P_2\cdot <!--\; \cdot \; -->P_3+G_0\cdot <!--\; \cdot \; -->P_1\cdot <!--\; \cdot \; -->P_2\cdot <!--\; \cdot \; -->P_3+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_1\cdot <!--\; \cdot \; -->P_2\cdot <!--\; \cdot \; -->P_3$$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}$ 

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

$PG=P_0\cdot <!--\; \cdot \; -->P_1\cdot <!--\; \cdot \; -->P_2\cdot <!--\; \cdot \; -->P_3$$PG=P_{0}\cdot P_{1}\cdot P_{2}\cdot P_{3}$ 

$GG=G_3+G_2\cdot <!--\; \cdot \; -->P_3+G_1\cdot <!--\; \cdot \; -->P_3\cdot <!--\; \cdot \; -->P_2+G_0\cdot <!--\; \cdot \; -->P_3\cdot <!--\; \cdot \; -->P_2\cdot <!--\; \cdot \; -->P_1$$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.

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

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

$C_4=G_0+P_0\cdot <!--\; \cdot \; -->C_0$$C_{4}=G_{0}+P_{0}\cdot C_{0}$ 

$C_8=G_4+P_4\cdot <!--\; \cdot \; -->C_4$$C_{8}=G_{4}+P_{4}\cdot C_{4}$ 

$C_{12}=G_8+P_8\cdot <!--\; \cdot \; -->C_8$$C_{12}=G_{8}+P_{8}\cdot C_{8}$ 

$C_{16}=G_{12}+P_{12}\cdot <!--\; \cdot \; -->C_{12}$$C_{16}=G_{12}+P_{12}\cdot C_{12}$ 

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

$C_4=G_0+P_0\cdot <!--\; \cdot \; -->C_0$$C_{4}=G_{0}+P_{0}\cdot C_{0}$ 

$C_8=G_4+G_0\cdot <!--\; \cdot \; -->P_4+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_4$$C_{8}=G_{4}+G_{0}\cdot P_{4}+C_{0}\cdot P_{0}\cdot P_{4}$ 

$C_{12}=G_8+G_4\cdot <!--\; \cdot \; -->P_8+G_0\cdot <!--\; \cdot \; -->P_4\cdot <!--\; \cdot \; -->P_8+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_4\cdot <!--\; \cdot \; -->P_8$$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\cdot <!--\; \cdot \; -->P_{12}+G_4\cdot <!--\; \cdot \; -->P_8\cdot <!--\; \cdot \; -->P_{12}+G_0\cdot <!--\; \cdot \; -->P_4\cdot <!--\; \cdot \; -->P_8\cdot <!--\; \cdot \; -->P_{12}+C_0\cdot <!--\; \cdot \; -->P_0\cdot <!--\; \cdot \; -->P_4\cdot <!--\; \cdot \; -->P_8\cdot <!--\; \cdot \; -->P_{12}$$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$$C_{4}$  соответственно генерирует бит переноса на вход второй схемы; $C_8$$C_{8}$  на вход третьей; $C12$$C{12}$  на вход четвёртой; и $C_{16}$$C_{16}$  генерирует бит переполнения.

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

$P_{LCU}=P_0\cdot <!--\; \cdot \; -->P_4\cdot <!--\; \cdot \; -->P_8\cdot <!--\; \cdot \; -->P_{12}$$P_{LCU}=P_{0}\cdot P_{4}\cdot P_{8}\cdot P_{12}$ 

$G_{LCU}=G_{12}+G_8\cdot <!--\; \cdot \; -->P_{12}+G_4\cdot <!--\; \cdot \; -->P_{12}\cdot <!--\; \cdot \; -->P_8+G_0\cdot <!--\; \cdot \; -->P_{12}\cdot <!--\; \cdot \; -->P_8\cdot <!--\; \cdot \; -->P_4$$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_{LCU}$$P_{LCU}$ ) и сигналы генерации переноса($G_{LCU}$$G_{LCU}$ ) от каждой схемы сумматора.

 

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

Достоинства и недостаткиПравить

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

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

Недостатки:

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

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

См. такжеПравить

• Сумматор

ЛитератураПравить

• Титце У., Шенк К. Глава 19. Комбинационные логические схемы. 19.5 Сумматоры. 19.5.3. Сумматоры с параллельным переносом // Полупроводниковая схемотехника = Halbleiter-Schaltungstechnik / Пер. с нем. Г. Карабашев. — Додэка XXI, 2008. — 1784 с. — (Схемотехника). — 3000 экз. — ISBN 978-5-94120-200-3, 978-5-94120-201-0, 3-540-42849-6.

ИсточникиПравить

• Воробьев Н. Сумматоры. Определения, классификация, уравнения, структуры и применение. Часть 2
• Сумматоры. Повышение быстродействия параллельных сумматоров. Принцип построения БУП (блок ускоренного переноса).
• Цифровая электроника. Курс лекций. Тема 4. Комбинационные цифровые устройства. 4-3. Сумматоры.
• Сумматор с ускоренным переносом.
• Дискретная математика: Алгоритмы. Многоразрядный сумматор.
• Сумматоры. Комбинационный сумматор с параллельным переносом.