Читать «Архитектура компьютера» онлайн - страница 147

Посмотрите на рис. 3.3, б. В этой книге мы будем использовать следующее соглашение: если две линии на рисунке пересекаются, связь подразумевается только в том случае, если на пересечении расположена жирная точка. Например, выход вентиля 3 пересекает все 6 вертикальных линий, но связан он только с линией С. Отметим, что в других книгах могут использоваться другие соглашения.

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

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

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

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

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

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

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

Рис. 3.4. Конструирование вентилей НЕ (а), И (б) и ИЛИ (в) только на базе вентилей НЕ-И или НЕ-ИЛИ

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

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

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

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

В качестве примера использования булевой алгебры рассмотрим схему и таблицу истинности для функции AB + AC (рис. 3.5, а). Хотя мы это еще не обсуждали, многие правила обычной алгебры имеют силу и в булевой алгебре. Например, выражение AB + AC по дистрибутивному закону может быть преобразовано в A(B + C). На рис. 3.5, б показана схема и таблица истинности для функции A (B + C). Две функции являются эквивалентными тогда и только тогда, если обе функции принимают одно и то же значение для всех возможных переменных. Из таблиц истинности на рис. 3.5 ясно видно, что функция A (B + C ) эквивалентна функции AB + AC. Несмотря на эту эквивалентность, схема на рис. 3.5, б проще, чем схема на рис. 3.5, а, поскольку содержит меньше вентилей.