От логических элементов к сумматорам

Компьютеры не «занимаются арифметикой» — они лишь строят блоки слой за слоем с помощью логических элементов. В этой лекции мы вручную построим схему, которая может складывать числа с помощью элементов XOR, AND и OR, от полусумматора к полному сумматору и к 4-битному сумматору, шаг за шагом.


Сложение в повседневной жизни — вдохновлено сложением столбиком

Вспомните процесс сложения на бумаге. Вычислите37 + 58:

Сначала вычислите разряд единиц:7 + 8 = 15, запишите5,, увеличьте на 1。

Затем вычислите разряд десятков:3 + 5 + перенос 1 = 9, запишите9, результат —95。

Этот процесс выявляет три ключевых момента:

1. Поразрядное вычисление: каждый бит учитывает только два своих слагаемых и перенос из младшего бита.

2. Распространение переноса: после вычисления младшего бита может возникнуть перенос, и этот перенос необходимо передать в старший бит.

3. Особенность младшего бита: у самого младшего бита нет переноса из ещё более младшего бита; ему нужно обработать только два слагаемых.

Компьютеры выполняют сложение по той же идее: разбивают большую задачу (многоразрядное сложение) на множество маленьких задач (1-битное сложение), а затем решают их одну за другой.

Полусумматор — 1-битное сложение для самого младшего бита

У самого младшего бита нет входного переноса; ему нужно только сложить два 1-битных двоичных числа. Схема, которая справляется с этой ситуацией, называетсяполусумматором。

У полусумматора есть два входа, A и B, и два выхода:бит суммыиперенос。

Таблица истинности полусумматора:

ABСумма (sum)Перенос
0000
0110
1010
1101

Глядя на таблицу истинности, обнаруживается удивительное совпадение:

Sum = A XOR B. Когда A и B различны, Sum=1; когда одинаковы, Sum=0 — это в точности таблица истинности элемента XOR.

Carry = A AND B. Перенос формируется только тогда, когда оба входа равны 1 — это в точности таблица истинности элемента AND.

Полусумматор требует лишь1 элемент XOR + 1 элемент ANDЭто можно реализовать. Джордж Буль, вероятно, и не представлял, что изобретённая им алгебраическая система однажды станет математической основой сумматоров.

Полный сумматор — полное сложение с обработкой переноса

У полусумматора есть фатальный недостаток:он не может принимать перенос из младшего разряда.. За исключением самого младшего разряда, каждый разряд должен обрабатывать три числа: A, B и входной перенос Cin из младшего разряда.

Схема, которая может одновременно обрабатывать два слагаемых и один вход переноса, называетсяполным сумматором。

Таблица истинности полного сумматора:

ABCinSumCout
00000
00110
01010
01101
10010
10101
11001
11111

Остроумное решение:Полный сумматор можно собрать из двух полусумматоров。

Шаг 1: полусумматор 1 обрабатывает A и B, выдавая промежуточную сумму S1 и перенос C1.

Шаг 2: полусумматор 2 обрабатывает S1 и Cin, выдавая итоговую сумму Sum и перенос C2.

Шаг 3: Итоговый переносCout = C1 OR C2(Если любой из полусумматоров формирует перенос, итоговый выход — перенос.)

Структура схемы полного сумматора:2 полусумматора + 1 элемент OR. Наложенные друг на друга, каждый полусумматор внутри представляет собой XOR + AND. Эта идея иерархического построения проходит через всю компьютерную архитектуру.

Каскадирование полных сумматоров — 4-битный сумматор с последовательным переносом

С полными сумматорами многоразрядное сложение становится простым:Соедините несколько полных сумматоров последовательно, при этом выход переноса младшего разряда подключается к входу переноса старшего разряда。

Каскадная структура 4-битного сумматора:

Бит 0 (младший разряд): полный сумматор обрабатывает A0, B0, вход переноса = 0, формируя сумму S0 и перенос C0.

Бит 1: полный сумматор обрабатывает A1, B1, вход переноса = C0, формируя сумму S1 и перенос C1.

Бит 2: полный сумматор обрабатывает A2, B2, вход переноса = C1, формируя сумму S2 и перенос C2.

Бит 3 (старший разряд): полный сумматор обрабатывает A3, B3, вход переноса = C2, формируя сумму S3 и перенос C3 (итоговый перенос).

Перенос распространяется, как волны по воде, от младшего разряда к старшему уровень за уровнем, поэтому эта структура называетсясумматор с последовательным переносом (Ripple Carry Adder)。

Сумматор с последовательным переносом прост и интуитивно понятен, но имеет узкое место по производительности: в худшем случае перенос должен распространяться от бита 0 до самого старшего бита, проходя через N каскадов задержек полного сумматора. Современные CPU используют методы вроде ускоренного переноса (carry lookahead) для оптимизации, но понимание последовательного переноса — необходимое условие для понимания всех оптимизаций сумматоров.

Демонстрация кода Python

Пример

# ============================================
# Лекция 8: От логических элементов к сумматорам — демонстрация на Python
# пример серии обучающих руководств
# ============================================

def half_adder(a, b):
    """
Полусумматор: складывает два 1-битных двоичных числа, игнорируя вход переноса.

Параметры:
a, b: каждое равно 0 или 1

Возвращает:
(sum_bit, carry_out): бит суммы и выход переноса

Реализация схемы:
sum_bit = a XOR b (элемент XOR)
carry_out = a AND b (элемент AND)
    """

    sum_bit = a ^ b      # XOR: одинаковые дают 0, разные — 1
    carry_out = a & b    # AND: перенос только когда оба равны 1
    return sum_bit, carry_out


def full_adder(a, b, carry_in):
    """
Полный сумматор: сложение двух 1-битных двоичных чисел с учётом входного переноса.

Параметры:
a, b, carry_in: каждое значение равно 0 или 1

Возвращает:
(sum_bit, carry_out): бит суммы и выход переноса

Совет по реализации — каскадно соедините два полусумматора:
Шаг 1: half_adder(a, b) → (s1, c1)
Шаг 2: half_adder(s1, carry_in) → (sum_bit, c2)
Итоговый перенос: carry_out = c1 OR c2
    """

    s1, c1 = half_adder(a, b)
    sum_bit, c2 = half_adder(s1, carry_in)
    carry_out = c1 | c2   # OR gate: если хотя бы у одного есть перенос, итоговый перенос устанавливается
    return sum_bit, carry_out


def adder_4bit(a_bits, b_bits):
    """
4-битный сумматор с последовательным переносом: 4 полных сумматора, соединённых каскадно.

Параметры:
a_bits: список из 4 бит, a_bits[0] — младший значащий бит (LSB)
b_bits: список из 4 бит, b_bits[0] — младший значащий бит (LSB)

Возвращает:
(sum_bits, final_carry): 4-битная сумма (сначала младший значащий бит) и итоговый перенос

Вывести полный процесс распространения переноса, демонстрируя, как работает последовательный перенос.
    """

    carry_in = 0
    sum_bits = []

    print("=" * 55)
    print(4-битный сумматор с последовательным переносом — процесс распространения переноса)
    print("=" * 55)
    # Отображать старшие биты первыми, для удобства чтения
    print(f" Слагаемое A: {list(reversed(a_bits))} (сначала старшие биты)")
    print(f" Слагаемое B: {list(reversed(b_bits))} (сначала старшие биты)")
    print()

    for i in range(4):
        s, carry_out = full_adder(a_bits[i], b_bits[i], carry_in)
        sum_bits.append(s)

        print(f" [бит {i}] (младший значащий бит — это бит 0)")
        print(f" Вход: A[{i}]={a_bits[i]}, B[{i}]={b_bits[i]}, enterbits入={carry_in}")
        print(fВывод: бит суммы={s}, перенос на выходе={carry_out})

        if carry_out:
            print(f>> Перенос сгенерирован! Перенос={carry_out} будет передан в бит {i+1})

        carry_in = carry_out  # Текущий перенос становится входным переносом следующего бита
        print()

    print(fРезультат вычисления: {list(reversed(sum_bits))} (сначала старшие биты))
    print(fИтоговый перенос: {carry_in})
    print("=" * 55)

    return sum_bits, carry_in


def decimal_to_4bit(n):
    """Преобразовать десятичные числа 0-15 в 4-битные двоичные списки (сначала младший значащий бит)"""
    return [(n >> i) & 1 for i in range(4)]


def bits_to_decimal(bits):
    """Преобразует список двоичных битов (младший значащий бит первым) в десятичное целое число"""
    return sum(bit * (2 ** i) for i, bit in enumerate(bits))


# ============================================
# Тестовый случай
# ============================================

print(>>> пример теста полусумматора <<<)
for a in (0, 1):
    for b in (0, 1):
        s, c = half_adder(a, b)
        print(f" half_adder({a}, {b}) => sum={s}, carry={c}")
print()

print(>>> пример теста полного сумматора <<<)
test_cases = [
    (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
    (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)
]
for a, b, cin in test_cases:
    s, c = full_adder(a, b, cin)
    print(f" full_adder({a}, {b}, carry_in={cin}) => sum={s}, carry={c}")
print()

print(>>> пример теста 4-битного сумматора: 7 + 5 <<<)
a_dec, b_dec = 7, 5
a_bits = decimal_to_4bit(a_dec)
b_bits = decimal_to_4bit(b_dec)
result_bits, final_carry = adder_4bit(a_bits, b_bits)
result_dec = bits_to_decimal(result_bits)
print(fОжидается: {a_dec} + {b_dec} = {a_dec + b_dec})
print(fРезультат: {result_dec} (перенос={final_carry}))
print(f" пример проверки: {'Успех!' if result_dec == a_dec + b_dec else 'Ошибка!'}")
print()

print(>>> пример дополнительного теста: 10 + 6 (возможное переполнение) <<<)
a_bits2 = decimal_to_4bit(10)
b_bits2 = decimal_to_4bit(6)
result_bits2, carry2 = adder_4bit(a_bits2, b_bits2)
result_dec2 = bits_to_decimal(result_bits2)
full_result = result_dec2 + (carry2 * 16)
print(f" Ожидалось: 10 + 6 = 16")
print(f" 4-битный результат: {result_dec2}, входные биты: {carry2}, Полное 5-битное значение: {full_result}")
print(fпроверка примера: {'Pass!' if full_result == 16 else 'Fail!'})

Запустите код и посмотрите, как перенос распространяется между каждым битом — сначала вычисляется младший значащий бит, и после формирования переноса он передаётся следующему биту; затем вычисляется следующий бит, и если формируется перенос, он передаётся дальше. Отсюда и название «ripple carry».


Интерактивная демонстрация: каскадная анимация 4-битного сумматора (пример демонстрации распространения переноса)

Ниже 4-битный сумматор с последовательным переносом моделируется на чистом div+SVG.Нажмите кнопку, чтобы пошагово увидеть, как перенос распространяется от бита 0 (младшего значащего бита) к биту 3 (старшего значащего бита)., или используйте «Авто-демо», чтобы посмотреть весь процесс.

4-битный сумматор с последовательным переносом — анимация распространения переноса

Вход A (сначала старший значащий бит)
Слагаемое A (сначала старший значащий бит)
Слагаемое B (старший разряд первым)
4 полных сумматора, соединённых каскадно (упорядочены от старшего к младшему: FA3 ← FA2 ← FA1 ← FA0)
Полный сумматор #3 (старший бит)
A=0 B=0
Вход переноса Cin=0
Сумма =?
Выход переноса Cout=?
←
Полный сумматор #2
A=0 B=0
Вход переноса Cin=0
Сумма =?
Выход переноса Cout=?
←
Полный сумматор #1
A=0 B=0
Вход переноса Cin=0
Сумма =?
Выход переноса Cout=?
←
Полный сумматор #0 (младший бит)
A=0 B=0
Вход переноса Cin=0
Сумма =?
Выход переноса Cout=?
Кнопка управления
Результат вычисления: -
Нажмите 'Next', чтобы запустить демонстрацию распространения переноса
Другие расширения