От логических элементов к сумматорам
Компьютеры не «занимаются арифметикой» — они лишь строят блоки слой за слоем с помощью логических элементов. В этой лекции мы вручную построим схему, которая может складывать числа с помощью элементов 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, и два выхода:бит суммыиперенос。
Таблица истинности полусумматора:
| A | B | Сумма (sum) | Перенос |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Глядя на таблицу истинности, обнаруживается удивительное совпадение:
Sum = A XOR B. Когда A и B различны, Sum=1; когда одинаковы, Sum=0 — это в точности таблица истинности элемента XOR.
Carry = A AND B. Перенос формируется только тогда, когда оба входа равны 1 — это в точности таблица истинности элемента AND.
Полусумматор требует лишь1 элемент XOR + 1 элемент ANDЭто можно реализовать. Джордж Буль, вероятно, и не представлял, что изобретённая им алгебраическая система однажды станет математической основой сумматоров.
Полный сумматор — полное сложение с обработкой переноса
У полусумматора есть фатальный недостаток:он не может принимать перенос из младшего разряда.. За исключением самого младшего разряда, каждый разряд должен обрабатывать три числа: A, B и входной перенос Cin из младшего разряда.
Схема, которая может одновременно обрабатывать два слагаемых и один вход переноса, называетсяполным сумматором。
Таблица истинности полного сумматора:
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Остроумное решение:Полный сумматор можно собрать из двух полусумматоров。
Шаг 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 (старшего значащего бита)., или используйте «Авто-демо», чтобы посмотреть весь процесс.