Логические элементы компьютера

Вентили И, ИЛИ, НЕ, полусумматор и сумматор, триггер как элемент памяти

От логической операции к электронной схеме

Всё, что делает компьютер, в конечном счёте сводится к обработке электрических сигналов, каждый из которых принимает одно из двух устойчивых состояний — высокий уровень напряжения (условно 1, «истина») и низкий уровень (условно 0, «ложь»). Логические операции И, ИЛИ, НЕ, рассмотренные ранее как абстрактные операции над высказываниями, физически реализуются в виде электронных схем — логических элементов (вентилей, от англ. gate). Из миллиардов таких элементов, соединённых между собой, устроен любой современный процессор.

Базовые логические элементы

Логический элемент — это электронная схема с одним или несколькими входами и одним выходом, на выходе которой появляется сигнал, вычисленный по правилам соответствующей логической операции от входных сигналов. Три базовых элемента — НЕ (инвертор), И (конъюнктор) и ИЛИ (дизъюнктор) — образуют полный набор, из которого можно собрать схему для вычисления любой, сколь угодно сложной, логической функции.

Элемент НЕ (инвертор)

Элемент НЕ имеет один вход и один выход и инвертирует входной сигнал: если на вход подан 0, на выходе появляется 1, и наоборот. Условное обозначение на схемах — треугольник с маленьким кружком (инверсионным «пузырьком») на выходе; кружок как раз и обозначает инверсию. Таблица истинности элемента НЕ:

Элемент И (конъюнктор)

Элемент И имеет два (или более) входа и один выход; на выходе появляется 1 тогда и только тогда, когда единица подана на все входы одновременно. На схемах обозначается фигурой с плоской стороной со входов и округлой — с выхода (без кружка на выходе — инверсии нет). Таблица истинности двухвходового элемента И:

Элемент ИЛИ (дизъюнктор)

Элемент ИЛИ имеет два (или более) входа и один выход; на выходе появляется 1, если хотя бы на одном входе присутствует единица. На схемах обозначается фигурой с вогнутой стороной со входов и заострённой — с выхода. Таблица истинности:

Комбинируя элементы И, ИЛИ, НЕ, можно строить более сложные производные элементы: И-НЕ (NAND, конъюнкция с инверсией на выходе), ИЛИ-НЕ (NOR), исключающее ИЛИ (XOR, сумма по модулю 2, дающая 1 только когда входы различны). На практике элементы И-НЕ и ИЛИ-НЕ особенно важны: каждый из них сам по себе образует функционально полный набор, то есть из одних только элементов И-НЕ (или одних ИЛИ-НЕ) можно собрать схему для любой логической функции, включая НЕ, И и ИЛИ.

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

Простейшая арифметическая схема компьютера — полусумматор (half adder) — складывает два одноразрядных двоичных числа A и B и выдаёт результат в виде двух сигналов: суммы S (бит результата) и переноса P (бит переноса в следующий разряд). Полусумматор строится всего из двух логических элементов: элемента исключающее ИЛИ для вычисления суммы и элемента И для вычисления переноса:

$S=A\oplus B,P=A\wedge B$

Название «полусумматор» связано с тем, что схема не умеет учитывать перенос, пришедший из предыдущего (младшего) разряда — то есть складывает только два бита, а не три. Именно поэтому полусумматор используется лишь для сложения самого младшего разряда чисел, а для всех остальных разрядов нужна более сложная схема.

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

Полный сумматор (full adder) складывает уже три одноразрядных сигнала: слагаемые A и B и перенос C_in, пришедший из младшего разряда, — и выдаёт сумму S и перенос P в старший разряд. Полный сумматор можно собрать из двух полусумматоров и одного дополнительного элемента ИЛИ: первый полусумматор складывает A и B (получая промежуточную сумму S₁ и перенос P₁), второй полусумматор складывает S₁ и C_in (получая итоговую сумму S и перенос P₂), а итоговый перенос вычисляется как P = P₁∨P₂ (оба переноса не могут появиться одновременно, поэтому дизъюнкция здесь работает корректно).

Соединяя друг за другом n полных сумматоров (перенос с выхода каждого разряда подаётся на вход переноса следующего), получают n-разрядный сумматор, способный складывать два n-битных двоичных числа целиком — именно такая схема (в развитом виде) лежит в основе арифметико-логического устройства (АЛУ) процессора.

Пример: сложение двух двузначных двоичных чисел

Задача. С помощью цепочки сумматоров нужно сложить числа A=11₂ (3 в десятичной) и B=01₂ (1 в десятичной). Проследим работу разрядов.

Решение. Младший разряд (разряд 0): a₀=1, b₀=1, входного переноса нет (0). Полусумматор даёт S₀=1⊕1=0, P₀=1∧1=1. Старший разряд (разряд 1): a₁=1, b₁=0, входной перенос C_in=P₀=1. Полный сумматор: сначала складываем a₁ и b₁ — получаем промежуточную сумму 1⊕0=1 и перенос 1∧0=0; затем складываем эту промежуточную сумму 1 с C_in=1 — получаем S₁=1⊕1=0 и второй перенос 1∧1=1; итоговый перенос старшего разряда P₁=0∨1=1.

Итог: биты результата S₁S₀=0 0, и есть выходной перенос P₁=1, значит результат — 100₂. Проверка в десятичной системе: 3+1=4=100₂. Ответ совпадает.

Триггер — элемент памяти

Рассмотренные до сих пор схемы (И, ИЛИ, НЕ, сумматоры) называют комбинационными: их выходной сигнал в любой момент однозначно определяется только текущими входными сигналами, без какой-либо «памяти» о прошлом. Но компьютеру необходимо не только вычислять, но и хранить информацию — для этого служат последовательностные схемы, простейшая и важнейшая из которых — триггер (flip-flop).

Триггер — это схема с обратной связью (выход одного элемента подан на вход другого и наоборот), способная устойчиво находиться в одном из двух состояний (хранить один бит — 0 или 1) сколь угодно долго, пока на неё подано питание, и менять это состояние только по специальному управляющему сигналу. Простейший RS-триггер (Reset-Set) строится из двух элементов ИЛИ-НЕ (или И-НЕ), выходы которых перекрёстно поданы на входы друг друга: подача единицы на вход S («установка») переводит триггер в состояние 1, подача единицы на вход R («сброс») — в состояние 0, а при отсутствии сигналов на обоих входах триггер сохраняет предыдущее записанное состояние — в этом и заключается эффект памяти.

Соединяя множество триггеров в группы (по числу битов), строят регистры процессора и ячейки оперативной памяти — так из простейших логических элементов, объединённых по определённым правилам, вырастает вся архитектура вычислительного устройства: от единичного вентиля до процессора, способного выполнять миллиарды операций в секунду.

Сводная таблица логических элементов

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

Частая ошибка — путать полусумматор и полный сумматор: полусумматор не имеет входа переноса и не годится для суммирования средних и старших разрядов многоразрядного числа. Другая ошибка — забывать, что перенос в старший разряд при сложении может возникнуть на двух разных этапах внутри полного сумматора (при сложении A и B и при добавлении входного переноса), поэтому итоговый перенос вычисляется как дизъюнкция двух промежуточных переносов, а не берётся с одного из полусумматоров. Также путают комбинационные схемы (без памяти) и последовательностные (с памятью, вроде триггера) — триггер отличается именно наличием обратной связи и способностью сохранять состояние без входного сигнала.

Краткий словарь терминов

Логический элемент (вентиль) — электронная схема, реализующая одну логическую операцию над входными сигналами.

Полусумматор — схема сложения двух одноразрядных двоичных чисел без учёта входного переноса.

Полный сумматор — схема сложения двух одноразрядных чисел с учётом входного переноса из младшего разряда.

Триггер — простейший элемент памяти, способный устойчиво хранить один бит информации.

Комбинационная схема — схема, выход которой зависит только от текущих значений входов.

Регистр — группа триггеров, хранящая многобитное двоичное число внутри процессора.

Заключение

Логические элементы И, ИЛИ, НЕ — физическая, «железная» реализация логических операций алгебры логики, а сумматоры и триггеры показывают, как из этих простейших кирпичиков строятся сначала арифметические устройства, а затем и элементы памяти компьютера. Понимание этой связи между абстрактной логикой и электронными схемами завершает раздел «Логика» и служит мостом к следующему разделу курса — «Начала программирования», где мы перейдём от аппаратной реализации вычислений к алгоритмам и их записи на языке программирования.