Учебное пособие -> Глава 8. Цифровой логический уровень. Вентили и булева алгебра

Глава 8. Цифровой логический уровень. Вентили и булева алгебра.

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

Вентили

Цифровая схема — это схема, в которой есть только два логических значения. Обычно сигнал от 0 до 1 В представляет одно значение (например, 0), а сигнал от 2 до 5 В — другое значение (например, 1). Напряжение за пределами указанных величин недопустимо. Крошечные электронные устройства, которые называются вентилями, позволяют получать различные функции от этих двузначных сигналов. Вентили лежат в основе аппаратного обеспечения, на котором строятся все цифровые компьютеры. Вся современная цифровая логика основывается на том, что транзистор может работать как очень быстрый бинарный переключатель.

Рисунок  1 – Транзистрорный инвертор

Транзистор имеет три соединения с внешним миром: коллектор, базу и эмиттер. Если входное напряжение Vin ниже определенного критического значения, транзистор выключается и действует как очень большое сопротивление. Это приводит к выходному сигналу Vout, близкому к Vcc (напряжению, подаваемому извне), — для данного типа транзистора это обычно +5 В. Если Vin превышает критическое значение, транзистор включается и действует как проводник, вызывая заземление сигнала Vout (по соглашению — это 0 В). Важно отметить, что если напряжение Vin низкое, то Vout высокое, и наоборот. Эта схема, таким образом, является инвертором, превращающим логический 0 в логическую 1 и логическую 1 в логический 0. Резистор (ломаная линия) нужен для ограничения тока, проходящего через транзистор, чтобы транзистор не сгорел. На переключение из одного состояния в другое обычно требуется несколько наносекунд.

Рисунок – Вентиль НЕ И

На рисунке два транзистора соединены последовательно. Если и напряжение V1 и напряжение V2 высокое, то оба транзистора становятся проводниками и снижают Vout. Если одно из входных напряжений низкое, то соответствующий транзистор выключается и напряжение на выходе становится высоким. То есть, напряжение Vout является низким тогда и только тогда, когда и напряжение V1 и напряжение V2 высокое.

Рисунок 3 – Вентиль НЕ ИЛИ

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

Данные три схемы образуют три простейших вентиля: НЕ, НЕ-И и НЕ-ИЛИ соответственно. Вентили НЕ часто называют инверторами.

Определим высокое напряжение (Vcc) как логическую 1, а низкое напряжение («земля») — логический 0. Тогда можно выражать значение на выходе как функцию от входных значений. Значки, которые используются для изображения этих трех типов вентилей, показаны на рисунке. Там же показаны режимы работы функции для каждой схемы. На этих рисунках А и В — входные сигналы, X — выходной сигнал. Каждая строка таблицы определяет выходной сигнал для различных комбинаций входных сигналов.

Рисунок 4 – Вентили НЕ, НЕ-И, НЕ-ИЛИ  

Если выходной сигнал вентиля НЕ-И подать в инвертор, то можно получить другую схему, противоположную вентилю НЕ-И, у которой выходной сигнал равен 1 тогда и только тогда, когда оба входных сигнала равны 1. Такая схема называется вентилем И. Ее изображение и описание соответствующей функции даны на рисунке:

Рисунок – Вентиль И

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

Рисунок – Вентиль ИЛИ  

Маленькие кружочки в схемах инвертора, вентиля НЕ-И и вентиля НЕ-ИЛИ называются инвертирующими выходами. Они также могут использоваться в другом контексте для указания на инвертированный сигнал.

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

Две основные технологии производства ветилей:

-       биполярная;

-       МОП (металл, оксид, полупроводник).

Среди биполярных технологий можно выделить:

-       ТТЛ (транзисторно-транзисторная логика), которая служила основой цифровой электроники на протяжении многих лет,

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

В отношении вычислительных схем более распространена технология МОП. МОП-вентили работают медленнее, чем ТТЛ и ЭСЛ, но потребляют гораздо меньше энергии и занимают гораздо меньше места, поэтому можно компактно расположить большое количество таких вентилей. Вентили МОП имеют несколько разновидностей: р-канальный МОП, n-канальный МОП и комплиментарный МОП. Современные процессоры и память чаще всего производятся с использованием технологии комплиментарных МОП, которая работает при напряжении +3,3 В.

Булева алгебра

Чтобы описать схемы, получаемые сочетанием различных вентилей, нужен особый тип алгебры, в которой все переменные и функции могут принимать только два значения: 0 и 1. Такая алгебра называется булевой (названа в честь английского математика Джорджа Буля 1815-1864).

В булевой алгебре есть свои функции. Булева функция на входе получает одну или несколько переменных и выдает результат, который зависит только от значений этих переменных. Можно определить простую функцию f, сказав, что f(A) = 1, если А = 0, и f(А) = 0, если А = 1. Такая функция будет функцией НЕ. Так как булева функция от п переменных имеет только  возможных комбинаций значений переменных, то такую функцию можно полностью описать в таблице с  строками. В каждой строке будет даваться значение функции для разных комбинаций значений переменных. Такая таблица называется таблицей истинности.

Cтроки таблицы истинности располагаются по порядку номеров, то есть для двух переменных в порядке 00, 01, 10, 11. Булеву функцию можно полностью описать -разрядным двоичным числом, которое получается, если считывать по вертикали колонку результатов в таблице истинности. Таким образом, НЕ-И - это 1110, НЕ-ИЛИ - 1000, И - 0001 и ИЛИ - 0111.

Cуществуют только 16 булевых функций от двух переменных, которым соответствуют 16 возможных 4-разрядных цепочек.

На рисунке показана таблица истинности для булевой функции от трех переменных: М = f(A, B,C). Это функция большинства, которая принимает значение 0, если большинство переменных равны 0, или 1, если большинство переменных равны 1.

Рисунок – Схема реализации функции большинства 

Таблица истинности для функции большинства

С возрастанием количества переменных описание булевой функции с помощью таблицы истинности становится громоздким. Поэтому вместо таблиц истинности часто используется другой вариант записи.

Любую булеву функцию можно определить, указав, какие комбинации значений входных переменных приводят к единичному значению функции. Для функции большинства существует 4 комбинации переменных, которые дают единичное значение функции. Для того, чтобы показать что значение переменной инвертируется, над переменной ставят черту. Отсутствие черты означает, что значение переменной не инвертируется.

Для обозначения булевой функции И используется знак умножения (точка, ·).

Для обозначения булевой функции ИЛИ используется знак сложения (+). Например,  принимает значение 1, только если A = 1, B = 0 и С = 1. Кроме того,  принимает значение 1, только если (А = 1 и В = 0) или (В = 1 и С = 0). В таблице истинности функция принимает значение 1 в четырех строках: . Функция М принимает значение истины (то есть 1), если одно из этих четырех условий истинно. Следовательно:

.

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

Реализация булевых функций

Ппредставление булевой функции в виде суммы максимум  произведений делает возможной реализацию этой функции. На рисунке схемы функции большинства входные сигналы А, В и С показаны с левой стороны, а функция М, полученная на выходе, - с правой. Поскольку необходимы дополнительные величины (инверсии) входных переменных, для их получения сигнал проходит через инверторы 1, 2 и 3.

Например, вентили 5, 6 и 7 на входе получают сигнал А. Схема содержит четыре вентиля И, по одному для каждого члена в уравнении для М (то есть по одному для каждой строки в таблице истинности с результатом 1). Каждый вентиль И вычисляет одну из указанных строк таблицы истинности. Все данные произведения суммируются (операция ИЛИ) для получения конечного результата.

Алгоритм получения схемы для любой булевой функции:

1.     Составить таблицу истинности для данной функции.

2.     Включить в схему инверторы, чтобы иметь возможность инверсии каждого входного сигнала.

3.     Нарисовать вентиль И для каждой строки таблицы истинности с результатом 1.

4.     Соединить вентили И с соответствующими входными сигналами.

5.     Вывести выходы всех вентилей И и направить их на вход вентиля ИЛИ.

Построение схемы с использованием одного типа вентилей.

Можно легко преобразовать схемы, построенные по представленному алгоритму, в форму НЕ-И или НЕ-ИЛИ. Чтобы осуществить такое преобразование необходимо реализовать вентили НЕ, И и ИЛИ с помощью какого-нибудь одного типа вентилей. На рисунке показано, как это сделать на базе вентиля НЕ-И или НЕ-ИЛИ.

Построение вентиля НЕ только на базе вентиля НЕ-И или НЕ-ИЛИ

Построение вентиля НЕ-И только на базе вентиля НЕ-И или НЕ-ИЛИ

Построение вентиля НЕ-ИЛИ только на базе вентиля НЕ-И или НЕ-ИЛИ

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

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

Эквивалентность схем

Разработчики схем часто стараются сократить число вентилей, чтобы снизить цену, уменьшить занимаемое схемой место, сократить потребление энергии и т. д. Чтобы упростить схему, разработчик должен найти другую схему, которая может вычислять ту же функцию, но при этом требует меньшего количества вентилей (или может работать с более простыми вентилями, например, двухвходовыми вместо четырехвходовых). Булева алгебра является ценным инструментом в поиске эквивалентных схем.

Например,  рассмотрим схему и таблицу истинности для функции .

Выражение  по дистрибутивному закону может быть преобразовано в . На рисунке показана схема и таблица истинности для функции .

 Две функции являются эквивалентными тогда и только тогда, когда обе функции принимают одно и то же значение для всех возможных переменных.

Из таблиц истинности на рисунках ясно видно, что функция  эквивалентна функции . Несмотря на эту эквивалентность, схема функции  проще, поскольку содержит меньше вентилей.

Обычно разработчик исходит из определенной булевой функции, а затем применяет к ней законы булевой алгебры, чтобы найти более простую функцию, эквивалентную исходной. На основе полученной функции можно конструировать схему.

Чтобы использовать данный подход, нужно знать некоторые соотношения (законы) булевой алгебры:

Все соотношения можно легко доказать, составив для них таблицы истинности.

Соотношение Де Моргана может быть расширено на выражения с более чем двумя переменными. (например, ).

Важно отметить, что один и тот же вентиль может вычислять разные функции в зависимости от используемых соглашений.

Если принимается соглашение, что 0 В — это логический ноль, а 3,3 В или 5 В — логическая единица, то получаем соглашение,  называемое позитивной логикой.

Если принимается условие, что 0 В — это логическая единица, а 3,3 В или 5 В — логический ноль, то получаем соглашение,  называемое негативной логикой.