Обучение › Тема 7

Двоичные сумматоры: полусумматор, полный сумматор и каскадное соединение

8 мин чтения · Команда bitGateLab

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

Двоичное сложение вручную

Правил сложения двух битов четыре: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 и 1 + 1 = 10₂, то есть 0 и перенос 1 в следующий столбец. Если к тому же приходит перенос, 1 + 1 + 1 = 11₂: результат 1 и перенос 1. Как и в десятичной системе, складывают столбец за столбцом справа налево, передавая перенос влево.

Полусумматор

Простейшая схема, полусумматор, складывает два бита, A и B, и имеет два выхода: сумму S и перенос C.

Столбец S — это таблица элемента XOR, а столбец C — таблица элемента AND. Следовательно:

S = A ⊕ B    C = AB

Он называется «полу-», потому что у него нет входа для переноса из предыдущего столбца, так что годится он только для младшего бита.

Полный сумматор

А вот полный сумматор складывает три бита: A, B и входной перенос C_in. Он выдаёт сумму S и выходной перенос C_out. Обратите внимание, что пара (C_out, S) — это записанное в двоичном виде количество единиц на входах.

S равна 1 при нечётном количестве единиц: S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in. C_out равен 1, когда единиц две или больше: C_out = Σm(3, 5, 6, 7), а после упрощения это мажоритарная функция:

C_out = AB + AC_in + BC_in

Если на карте Карно для S вы попробуете объединить клетки, то увидите, что ни у одной клетки с 1 нет соседа с 1: это «шахматный» узор, типичный для XOR, который в виде суммы произведений не упрощается.

Полный сумматор из двух полусумматоров

Практичный способ его собрать — соединить в цепочку два полусумматора и один элемент OR:

1. Первый полусумматор: P = A ⊕ B и G = AB.
2. Второй полусумматор, на входах P и C_in: S = P ⊕ C_in и частичный перенос P·C_in.
3. C_out = G + P·C_in = AB + (A ⊕ B)C_in.

Это выражение эквивалентно мажоритарной функции: если A и B равны 1, перенос даёт уже AB; если ровно один из них равен 1, перенос зависит от C_in. Сигнал G называют сигналом генерации переноса, а P — сигналом распространения.

Сумматор с последовательным переносом

Чтобы складывать числа из n бит, соединяют в ряд n полных сумматоров: выход C_out каждого разряда подаётся на вход C_in следующего. На C_in первого разряда подаётся 0, а C_out последнего — это выходной перенос всего сумматора. Такая структура называется сумматором с последовательным переносом, по-английски ripple carry, потому что перенос «прокатывается» от разряда к разряду, как волна. В семействе 74HC есть микросхема, которая содержит четыре полных сумматора, уже соединённых таким образом (74HC283).

Цена — время. Разряд 3 не может выдать окончательный результат, пока к нему не придёт перенос из разряда 2, который, в свою очередь, ждёт перенос из разряда 1. Если каждому разряду нужно два уровня логических элементов, чтобы сформировать перенос, то сумматору из n бит в худшем случае требуется порядка 2n задержек элемента. Для 64 бит это слишком медленно, поэтому в процессорах используют сумматоры с ускоренным переносом, которые вычисляют переносы параллельно по сигналам G и P. На временной диаграмме симулятора видно, как выходы меняются ступенями, пока не установятся.

Вычитание на том же сумматоре

Как объясняется в теме «системы счисления», в дополнительном коде число, противоположное B, равно B + 1. Значит:

A − B = A + B + 1

Чтобы это получить, достаточно поставить на каждый бит числа B элемент XOR, второй вход которого соединён с линией управления M, и подать M также на C_in первого разряда. При M = 0 элементы XOR пропускают B без изменений и C_in = 0: схема складывает. При M = 1 элементы XOR инвертируют B, а C_in = 1 добавляет «+1»: схема вычитает.

Типичные ошибки

• Ставить полусумматор в промежуточные разряды. Любому разряду, принимающему перенос, нужен полный сумматор.
• Оставлять «висящим» вход C_in первого разряда. Его нужно подключить к 0 для сложения или к M в сумматоре-вычитателе.
• Путать выходной перенос с переполнением. Для чисел со знаком выходной перенос отбрасывается, а переполнение обнаруживается по C₃ ⊕ C₄.
• Забывать «+1» при вычитании и подключать только инверторы: результат получается на единицу меньше.
• Записывать S = A + B + C_in через OR. Одноразрядная сумма — это XOR, а не OR.

Попробуйте в симуляторе

Собрать сумматор в редакторе — лучший мост между логическими элементами и арифметикой. Начните с одного бита и дорастите до четырёх.

1. Поместите два входа, элементы XOR и AND и соедините их, как на схеме полусумматора. Постройте его таблицу истинности.
2. Соберите полный сумматор из двух полусумматоров и элемента OR и сверьте его 8 строк с таблицей из этой статьи.
3. Скопируйте полный сумматор четыре раза и соедините переносы в цепочку. На первый C_in подайте 0.
4. Установите на входах 1011 и 0110 и убедитесь, что на выходе 0001 с выходным переносом 1.
5. Откройте временную диаграмму, измените вход так, чтобы переносу пришлось пройти через все четыре разряда (например, 1111 + 0001), и понаблюдайте, как устанавливаются выходы.

Упражнения

1. Найдите S и C_out полного сумматора при A = 1, B = 0, C_in = 1.
   Ответ

   Единиц две: S = 0 и C_out = 1 (1 + 0 + 1 = 10₂).

2. Сложите 0111 + 0101 на 4-битном сумматоре и укажите переносы каждого разряда.
   Ответ

   Разряд 0: 1 + 1 = 0, перенос 1. Разряд 1: 1 + 0 + 1 = 0, перенос 1. Разряд 2: 1 + 1 + 1 = 1, перенос 1. Разряд 3: 0 + 0 + 1 = 1, перенос 0. Результат 1100 = 12 (7 + 5).

3. На 4-битном сумматоре-вычитателе вычислите 6 − 3 и запишите, чему равно M.
   Ответ

   M = 1. 0110 + 1100 + 1 = 1 0011. Перенос отбрасывается: 0011 = 3.

4. Если рассматривать числа как 4-битные со знаком, есть ли переполнение в 0111 + 0101?
   Ответ

   Да. 7 + 5 = 12 не помещается в диапазон от −8 до +7. Результат 1100 прочитался бы как −4. Переносы равны C₃ = 1 и C₄ = 0, и V = 1 ⊕ 0 = 1.