Полный одноразрядный сумматор.
Связь между двоичной арифметикой и алгеброй логики позволяет реализовать логические схемы основных элементов процессора и памяти компьютера.
Сумматор - это устройство, предназначенное для сложения двоичных чисел.
Рассмотрим сначала более простое устройство – полусумматор.
Построим таблицу истинности для устройства реализующего арифметическую операцию сложения. Операция «+» бинарная, поэтому полусумматор должен иметь два входа (A и B). В результате сложения двух одноразрядных двоичных чисел может получиться двухразрядное число (с переносом в следующий разряд). Значит, устройство должно иметь два выхода (P - перенос в следующий разряд, S - результат, остающийся в текущем разряде).
| A | B | P | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
По данной таблице истинности построим СДНФ (см. алгоритм построения СДНФ):
- Для переноса в старший разряд: P = A ∧ B
- Для текущего разряда: S = ¬ A ∧ B ∨ A ∧ ¬ B
Преобразуем логическую формулу для S:
(¬ A • B) + (A • ¬ B) = (¬ A • A) + ( ¬ A • B) + (A • ¬ B) + (¬ B • B) =
= ¬ A • (A + B) + ¬ B • (A + B) = (A + B) • ¬ (A • B)
С учетом формулы для переноса имеем:
S = (A + B) • ¬ (A • B) = (A + B) • ¬ P
Таким образом, полусумматор можно построить, используя четыре простейших логических элемента: два конъюнктора, дизъюнктор и инвертор (см. рис.1, слева показано условное обозначение полусумматора):
Итак, получено устройство, реализующее суммирование одноразрядных двоичных чисел без учета переноса из младшего разряда.
Для реализации полного одноразрядного сумматора необходимо учесть перенос из младшего разряда (P0). Поэтому сумматор должен иметь три входа. Построим таблицу истинности для устройства с учетом третьего входа:
| A | B | P0 | P | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Построим СДНФ для выхода P (перенос в старший разряд):
P =(¬ A ∧ B ∧ P0) ∨ (A ∧ ¬ B ∧ P0) ∨ (A ∧ B ∧ ¬ P0) ∨ (A ∧ B ∧ P0)
Преобразуем:
1) (A ∧ B ∧ ¬ P0) ∨ (A ∧ B ∧ P0) = (A ∧ B) ∧ (¬ P0 ∨ P0) = A ∧ B
Имеем, P = (¬ A ∧ B ∧ P0) ∨ (A ∧ ¬ B ∧ P0) ∨ (A ∧ B)
2) (¬ A ∧ B ∧ P0) ∨ (A ∧ B) = B ∧(¬ A ∧ P0 ∨ A) = B ∧ (¬ A ∨ A ) ∧ (P0 ∨ A) =
= B ∧ (P0 ∨ A) = (B ∧ P0) ∨ (A ∧ B)
Имеем, P = (A ∧ ¬ B ∧ P0) ∨ (B ∧ P0) ∨ (A ∧ B)
3) (A ∧ B) ∨ (A ∧ ¬ B ∧ P0) = A ∧ (B ∨ ¬ B ∧ P0) = A ∧ (B ∨ ¬ B)(B ∨ P0) =
= A ∧ (B ∨ P0) = (A ∧ B) ∨ (A ∧ P0)
Таким образом, для переноса в старший разряд получили:
P = A ∧ B ∨ A ∧ P0 ∨ B ∧ P0
Проанализируем таблицу истинности для выхода S. Значение S отлично от нуля в том случае, если единица поступает ровно на один вход (при этом на двух других входах фиксируется ноль), или на все три входа сразу, т. е.:
S = ¬ (A ∧ B ∨ A ∧ P0 ∨ B ∧ P0) ∧ (A ∨ B ∨ P0) ∨ (A ∧ B ∧ P0)
С учетом формулы для переноса в старший разряд, имеем:
S = ¬ P ∧ (A ∨ B ∨ P0) ∨ (A ∧ B ∧ P0)
Таким образом, одноразрядный двоичный сумматор можно реализовать с помощью следующей схемы (см. рис. 2, слева показано условное обозначение сумматора), которая соответствует полученным логическим формулам (1) и (2).
Заметим, что логические функции P и S можно выразить с помощью других формул. В таком случае для одноразрядного двоичного сумматора потребуется другая логическая схема.