Русская Википедия:Схема ускоренного переноса
Схе́ма уско́ренного перено́са — комбинационная логическая схема, входит в арифметико-логическое устройство большинства современных ЭВМ микропроцессоров и микроконтроллеров.
Предназначена для параллельного формирования битов переноса при сложении двоичных чисел в сумматоре. Обычно строится каскадным способом, состоит из нескольких схем ускоренного переноса меньшей разрядности, обычно равной натуральной степени числа 2, но существуют и однокаскадные схемы ускоренного переноса, формирующие сигналы переноса для всех битов слова одновременно.
Преимущество этой схемы в сравнении с последовательным соединением двоичных сумматоров — существенное ускорение арифметических операций. Недостаток — используется большее количество логических элементов.
Принцип работы
Шаблон:Заготовка раздела
Термины:
Carry Lookahead Unit (CLU) — схема ускоренного переноса.
Carry Look-ahead Adder (CLA) — схема сумматора с ускоренным переносом.
Group propagate (PG) — групповой сигнал распространения переноса.
Group generate (GG) — групповой сигнал генерации переноса.
При использовании схемы ускоренного переноса (LCU) каждый одинарный разряд сумматора вырабатывает сигнал генерации переноса (<math>g_n</math>) и сигнал распространения переноса (<math>p_n</math>).
4-битная схема
Одинарные разряды сумматора объединяются в группы по четыре одинарных разряда в каждой группе. Схема ускоренного переноса вырабатывает сигналы переноса <math>C_1, C_2, C_3, C_4,</math> групповой сигнал генерации переноса (GG) и групповой сигнал распространения переноса (PG).
Выведем схему ускоренного переноса. Условимся точкой (<math>\cdot</math>) обозначать логическое И (AND), знаком сложения (+) — логическое ИЛИ (OR), символом <math>\oplus</math> — сложение по модулю 2 ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR).
Выражение переноса полного двоичного сумматора записывается в виде:
- <math>C_{i+1} = a_i \cdot b_i + b_i \cdot C_i + C_i \cdot a_i</math>
Вынесем <math>C_i</math> за скобки:
- <math>C_{i+1} = a_i \cdot b_i + (a_i + b_i) \cdot C_i</math>
Таблица истинности этого выражения эквивалентна следующему:
- <math>C_{i+1} = a_i \cdot b_i + (a_i \oplus b_i) \cdot C_i</math>
Последнее выражение удобно для построения полного суммирующего элемента, так как переиспользуется операция <math>\oplus</math>, необходимая для вычисления суммы. Исходное удобно для построения отдельной схемы с ускоренным переносом, так как логическое или проще в реализации чем исключающее или.
Для удобства записи сделаем замену <math>a_i \cdot b_i = G_i</math>; <math>a_i + b_i = P_i</math> либо <math>a_i \oplus b_i = P_i</math>:
- <math>C_{i+1} = G_i + P_i \cdot C_i</math>
Распишем выражения переноса для первых четырёх разрядов:
- <math>C_1 = G_0 + P_0 \cdot C_0</math>
- <math>C_2 = G_1 + P_1 \cdot C_1</math>
- <math>C_3 = G_2 + P_2 \cdot C_2</math>
- <math>C_4 = G_3 + P_3 \cdot C_3</math>
Подставим <math>C_1</math> в <math>C_2</math>, <math>C_2</math> в <math>C_3</math>, <math>C_3</math> в <math>C_4</math>:
- <math>C_1 = G_0 + P_0 \cdot C_0</math>
- <math>C_2 = G_1 + G_0 \cdot P_1 + P_0 \cdot P_1 \cdot C_0</math>
- <math>C_3 = G_2 + G_1 \cdot P_2 + G_0 \cdot P_1 \cdot P_2 + P_0 \cdot P_1 \cdot P_2 \cdot C_0</math>
- <math>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 + P_0 \cdot P_1 \cdot P_2 \cdot P_3 \cdot C_0</math>
Групповой сигнал генерации переноса <math>GG</math> и групповой сигнал распространения переноса <math>PG</math> формируются следующим образом:
- <math>PG = P_0 \cdot P_1 \cdot P_2 \cdot P_3</math>
- <math>GG = 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</math>
4-битная схема ускоренного переноса выпускается в интегральном исполнении, например: SN74182 (ТТЛ), MC10179 (ЭСЛ) и MC14582, 564ИП4[1] (выполненная по технологии КМОП).
16-битная схема
16-разрядный сумматор может быть создан путём объединения четырёх 4-битных сумматоров с четырьмя схемами ускоренного переноса (4-bit CLA Adder), дополненных пятой схемой ускоренного переноса, которая используется для обработки групповых сигналов генерации переноса — GG и распространения переноса — PG.
Принимаемые на входе сигналы распространения переноса (<math>PG</math>) и генерируемые каждой их четырёх схем сигналы (GG). Затем, схема ускоренного переноса генерирует соответствующие сигналы.
Предположим, что <math>P_i</math> это сигналы PG и <math>G_i</math> это GG из iй, то выходные биты устанавливаются следующим образом:
- <math>C_{4} = G_0 + P_0 \cdot C_0</math>
- <math>C_{8} = G_{4} + P_{4} \cdot C_{4}</math>
- <math>C_{12} = G_{8} + P_{8} \cdot C_{8}</math>
- <math>C_{16} = G_{12} + P_{12} \cdot C_{12}</math>
Подставляя <math>C_{4}</math> сперва в <math>C_{8}</math>, затем <math>C_{8}</math> в <math>C_{12}</math>, затем <math>C_{12}</math> в <math>C_{16}</math> получаем следующее выражение:
- <math>C_{4} = G_0 + P_0 \cdot C_0</math>
- <math>C_{8} = G_4 + G_0 \cdot P_4 + P_0 \cdot P_4 \cdot C_0</math>
- <math>C_{12} = G_8 + G_4 \cdot P_8 + G_0 \cdot P_4 \cdot P_8 + P_0 \cdot P_4 \cdot P_8 \cdot C_0</math>
- <math>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} + P_0 \cdot P_4 \cdot P_8 \cdot P_{12} \cdot C_0</math>
<math>C_{4}</math> соответственно генерирует бит переноса на вход второй схемы; <math>C_{8}</math> на вход третьей; <math>C{12}</math> на вход четвёртой; и <math>C_{16}</math> генерирует бит переполнения.
Кроме того, можно указать сигналы распространения переноса и генерации переноса для схемы ускоренного переноса:
- <math>P_{LCU} = P_0 \cdot P_4 \cdot P_8 \cdot P_{12}</math>
- <math>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</math>
64-битная схема
Объединив четыре схемы сумматора и схему ускоренного переноса вместе, получим 16-битный сумматор. Четыре таких блока могут быть объединены в 64-разрядный сумматор. Дополнительные схемы ускоренного переноса (второго уровня) необходимы, чтобы принимать сигналы распространения переноса (<math>P_{LCU}</math>) и сигналы генерации переноса(<math>G_{LCU}</math>) от каждой схемы сумматора.
Достоинства и недостатки
Достоинства:
- Высокая скорость работы.
Недостатки:
- Бо́льшие затраты оборудования
Схемы формирования параллельного переноса имеют существенное преимущество в скорости перед схемами последовательного переноса.
См. также
Литература
Ссылки
Источники
- Воробьев Н. Сумматоры. Определения, классификация, уравнения, структуры и применение. Часть 2
- Сумматоры. Повышение быстродействия параллельных сумматоров. Принцип построения БУП (блок ускоренного переноса).
- Цифровая электроника. Курс лекций. Тема 4. Комбинационные цифровые устройства. 4-3. Сумматоры.
- Сумматор с ускоренным переносом.
- Дискретная математика: Алгоритмы. Многоразрядный сумматор.
- Сумматоры. Комбинационный сумматор с параллельным переносом.
- ↑ Справочник по низкочастотным цифровым КМОП микросхемам. ИП4 — схема ускоренного переноса 564ИП4 = MC14582A http://www.rlocman.ru/comp/koz/cd/cdh39.htm Шаблон:Wayback
