Э. Таненбаум - Архитектура компьютера (1127755), страница 43
Текст из файла (страница 43)
3.3. Таблица истинности для функции большинства от трех переменных (з); схема реализации етой функции (б) Чтобы увидеть этот другой тип записи, отметим, что любую булеву функцию можно определить, указав, какие комбинации значений входных переменных приводят к единичному значению функции. Для функции, приведенной иа рис. 3.3, а, существует 4 комбинации переменных, которые дают единичное значение функции. Мы будем рисовать черту иад переменной, показывая, что ее значение иивертируется. Отсутствие черты означает, что значение переменной 166 Глава 3. Цифровой логический уровень не инвертируется.
Кроме того, мы будем использовать знак умножения (точку) для обозначения булевой функции И (этот знак может опускаться) и знак сложения (ч.) для обозначения булевой функции ИЛИ. Например, АВС принимает значение 1, только если А = 1, В = 0 и С = 1. Кроме того, АВ ч- ВС принимает значение 1, только если (А = 1 и В = 0) или (В = 1 и С = 0). В таблице на рис. 3.3, а функция принимает значение 1 в четырех строках: АВС, АВС, АВС и АВС. Функция М принимает значение истины (то есть 1), если одно из этих четырех условий истинно, Следовательно, мы можем написать М = АВС ч- АВС ч- АВС ч- АВС. Это компактная запись таблицы истинности.
Таким образом, функцию от п переменных можно описать суммой максимум 2" произведений, при этом в каждом произведении будет по п множителей. Как мы скоро увидим, такая формулировка особенно важна, поскольку она позволяет реализовать данную функцию с использованием стандартных вентилей. Важно понимать различие между абстрактной булевой функцией и ее реализацией с помощью электронной схемы. Булева функция состоит из переменных, например, А, В и С, а также из операторов И, ИЛИ и НЕ.
Булева функция описывается с помощью таблицы истинности или специальной записи, например: Г = АВС ч- АВС. Булева функция может быть реализована электронной схемой (часто различными способами) с использованием сигналов, которые представляют входные и выходные переменные, и вентилей, например, И, ИЛИ и НЕ. Реализация булевых функций Как было отмечено ранее, представление булевой функции в виде суммы максимум 2" произведений делает возможной реализацию этой функции. На рис. 3.3, б входные сигналы А, В и С показаны с левой стороны, а функция М, полученная на выходе, — с правой.
Поскольку необходимы дополнительные величины (инверсии) входных переменных, для их получения сигнал проходит через инверторы 1, 2 и 3. Чтобы сделать рисунок понятней, мы нарисовали 6 вертикальных линий, 3 из которых связаны с входными переменными, 3 другие — с их инверсиями. Эти линии обеспечивают передачу входного сигнала к вентилям. Например, вентили 5, 6 и 7 на входе получают сигнал А. В реальной схеме эти вентили, вероятно, будут непосредственно соединены проводом с А без каких-либо промежуточных вертикальных проводов. Схема содержит четыре вентиля И, по одному для каждого члена в уравнении для М (то есть по одному для каждой строки в таблице истинности с результатом 1).
Каждый вентиль И вычисляет одну из указанных строк таблицы истинности. В конце концов, все данные произведения суммируются (имеется в виду операция ИЛИ) для получения конечного результата. Посмотрите на рис. 3.3, б. В этой книге мы будем использовать следующее соглашение: если две линии на рисунке пересекаются, связь подразуме- Вентили и булева алгебра 167 вается только в том случае, если на пересечении расположена жирная точка. Например, выход вентиля 3 пересекает все 6 вертикальных линий, но связан он только с линией С. Отметим, что другие авторы могут использовать другие соглашения.
Из рис. 3.3 должно быть ясно, как получить схему для любой булевой функции: Е Составить таблицу истинности для данной функции. 2. Включить в схему инверторы, чтобы иметь возможность инверсии каждого входного сигнала. 3. Нарисовать вентиль И для каждой строки таблицы истинности с результа- том (.
4. Соединить вентили И с соответствующими входными сигналами. 5. Вывести выходы всех вентилей И и направить их на вход вентиля ИЛИ. Мы показали, как реализовать любую булеву функцию с помощью вентилей НЕ, И и ИЛИ. Однако гораздо удобнее строить схемы с использованием одного типа вентилей. К счастью, можно легко преобразовать схемы, построенные по предыдущему алгоритму, в форму НЕ-И или НЕ-ИЛИ. Чтобы осуществить такое преобразование, все, что нам нужно, — это реализовать вентили НЕ, И и ИЛИ с помощью какого-нибудь одного типа вентилей. На рисунке 3.4 показано, как зто сделать на базе вентиля НЕ-И или НЕ-ИЛИ.
Отметим, что существуют и другие варианты подобного преобразования. Рис. 3.4. Конструирование вентилей НЕ (а), И (б) и ИЛИ (в) только на базе вентиля НЕ-И или НЕ-ИЛИ 168 Глава 3. Цифровой логический уровень Для того чтобы реализовать булеву функцию только на базе вентиля НЕ-И или НЕ-ИЛИ, можно сначала следовать описанному алгоритму, сконструировав схему с вентилями НЕ, И и ИЛИ. Затем нужно заменить многовходовые вентили эквивалентными схемами на двухвходовых вентилях.
Например, А + В + С + Р можно поменять на (А + В) + (С + Р), использовав три двухвходовых вентиля. Затем вентили НЕ, И и ИЛИ заменяются схемами, изображенными на рис. 3А. Хотя такая процедура и не приводит к оптимальным схемам с точки зрения минимального числа вентилей, она демонстрирует, что подобное преобразование осуществимо. Вентили НЕ-И и НЕ-ИЛИ считаются полными, потому что каждый из них позволяет вычислить любую булеву функцию.
Ни один другой вентиль не обладает таким свойством, вот почему именно эти два типа вентилей предпочтительнее при построении схем. Эквивалентность схем Разработчики схем часто стараются сократить число вентилей, чтобы снизить цену, уменьшить занимаемое схемой место, сократить потребление энергии и т. д. Чтобы упростить схему, разработчик должен найти другую схему, которая может вычислять ту же функцию, но при этом требует меньшего количества вентилей (или может работать с более простыми вентилями, например, двухвходовыми вместо четырехвходовых). Булева алгебра является ценным инструментом в поиске эквивалентных схем.
В качестве примера использования булевой алгебры рассмотрим схему и таблицу истинности для функции АВ ч- АС (рис. 3.5, а). Хотя мы это еще не обсуждали, многие правила обычной алгебры имеют силу и в булевой алгебре. Например, выражение АВ + АС по дистрибутивному закону может быть преобразовано в А(В + С).
На рис. 3.5, 6 показана схема и таблица истинности для функции А(В + С). Две функции являются эквивалентными тогда и только тогда, когда обе функции принимают одно и то же значение для всех возможных переменных. Из таблиц истинности на рис. 3.5 ясно видно, что функция А(В + С) эквивалентна функции АВ + АС. Несмотря на эту эквивалентность, схема на рис. 3.5, б проще, чем схема на рис. 3.5, а, поскольку содержит меньше вентилей. Обычно разработчик исходит из определенной булевой функции, а затем применяет к ней законы булевой алгебры, чтобы найти более простую функцию, эквивалентную исходной. На основе полученной функции можно конструировать схему. Чтобы использовать данный подход, нужно знать некоторые соотношения (законы) булевой алгебры, которые показаны в табл.
3.1. Интересно отметить, что каждое соотношение имеет две формы. Одну форму можно получить из другой, меняя И на ИЛИ и О на 1. Все соотношения можно легко доказать, составив для них таблицы истинности. Почти во всех случаях результаты очевидны, за исключением соотношения Де Моргана, соотношения поглощения и дистрибутивного соотношения. Соотношение Де Моргана может быть расширено на выражения с более чем двумя переменными, например, АВС = А + В+ С.
Вентили и булева алгебра 169 А Рис. 3.5. Две эквивалентные функции; АВ + АС (в); А(В + С) (б) Таблица 3.1. Некоторые соотношения булевой алгебры И ИЛИ Я+ ВС= (А+ В)(Я+ С) А(В+ С) =АВ+АС Я(А+ В) = А ЯВ =Я+ В А + АВ = Я А+ В =АВ Соотношение Де Моргана предполагает альтернативную запись. На рис. 3.6, а форма И дается с отрицанием, которое показывается с помошью инвертируюших входов и выходов. Таким образом, вентиль ИЛИ с инвертированными входными сигналами эквивалентен вентилю НЕ-И.
Из рис. 3.6, б, который иллюстрирует вторую форму соотношения Де Моргана, ясно, что вместо вентиля НЕ-ИЛИ можно нарисовать вентиль И с инвертированными входами. Путем отрицания обеих форм соотношения Де Моргана мы приходим к эквивалентным представлениям вентилей И и ИЛИ (рис. 3.6, в и г). Аналогичные символиче- Соотношение Соотношение тождества Соотношение нуля Соотношение идемпотентности Соотношение инверсии Соотношение коммугативности Ассоциативное соотношение Дистрибутивное соотношение Соотношение поглощения Соотношение Де Моргана 1Я =А ОА = О АА=А АА = О АВ=ВА (АВ)С = Я(ВС) О+А=Я 1+А=! А+А=А АвЯ= 1 А+В=В+А (А+ В) + С =Я+ (В+ С) 170 Глава 3.
Цифровой логический уровень ские изображения существуют для разных форм соотношения Де Моргана (например, и-входовый вентиль НЕ-И становится вентилем ИЛИ с инвертированными входами). Рис. 3.6. Альтернативные представления некоторых вентилей: НЕ-И (а); НЕ-ИЛИ (б); И (в); ИЛИ (г) Использовав уравнения, указанные на рис. 3.6, и аналогичные уравнения для многовходовых вентилей, можно легко преобразовать сумму произведений в форму только из вентилей НЕ-И или только из вентилей НЕ-ИЛИ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
