Схемотехника / Учебники и методички / potehin

Часть 1

Основы цифровых устройств

Глава1. Логические основы цифровых устройств

1.1. Введение

Математический аппарат, описывающий действия дискретных устройств, базируется на алгебре логики, автором которой считается английский математик Дж. Буль (1815 – 1864г.). В практических целях первым применил его американский ученый К. Шеннон в 1938 г. при исследовании электрических цепей с контактными выключателями.

Булева алгебра оперирует двоичными переменными (logic values), которые условно обозначают, как 0 и 1 и называют двоичной цифрой (binary digit)

или битом (bit). В ее основе лежит понятие переключательной, или булевой

функции вида f(xn- 1, xn-2 … x1, х0) относительно аргументов xn-1, x n-2 … x1, х0, которая также может принимать лишь два значения – 0 и 1. Логическая функция может быть задана словесно, алгебраическим выражением, и таблицей, которая называется таблицей истинности (truth table). Аналитический способ предусматривает запись функции в форме логического выражения, показывающего, какие логические операции над аргументами функции должны выполняться и в какой последовательности. Сложные функции от многих аргументов (переменных) могут быть представлены в форме функций от функций, последние из которых выражаются через меньшее число аргументов. Следует отметить, что для обозначения аргументов используются наиболее популярные знаки латинского греческого и русского алфавитов.

В булевой алгебре различают положительную и отрицательную логику. В положительной логике (positive logic) логической единице (лог. 1) соответствует «высокий уровень» напряжения – H (H – High), логическому нулю (лог. 0) – «низкий уровень» – L (L – Low). Отрицательная логика (negative logic используется не часто и в ней, естественно, противоположные соответствия логических уровней: 1 – низкий уровень, 0 – высокий уровень.

При табличном задании функции (state table) в строках таблицы записываются возможные двоичные значения аргументов xn-1, x n-2 … x1, х0 и указываются значения функцииf (xn-1 – х0), которые она принимает на данном наборе (лог. 0 или лог. 1). При числе аргументов n максимальное число различных состояний в таблице 2n.

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

11

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1.2. Простейшие логические операции

В алгебре логики имеется три простейшие логические операции: отрица-

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

полняются на логических схемах, именуемых «логическими вентилями».

Инвертор

Операция отрицания (NOT gate) выполняется над одним аргументом или функцией и обозначается чертой над обозначением аргумента (переменной)

или функции: y = x – (не x), f (a,b) обозначает (не f (a,b)). Таким образом, инверсия единицы равна нулю, инверсия нуля – единице; а двойная инверсия не изменяет значения переменной:

А = 1, = 0, А = 0, = 1, = А.

Таблица истинности инвертора для одного аргумента дана на рис. 1.1, а. Операция инвертирования сигнала на условном графическом обозначении (УГО) обозначается кружком на выводе выходного сигнала (inversion bubble) , как показано на рис. 1.1, а. эпюры напряжений входного и выходного сигналов показаны на рис. 1.1, в. Инверторы, как ключевые усилительные элементы

а) б) в)

Рис. 1.1. Таблиц истинности – а, условное графическое обозначение – б и эпюры напряжений инвертора –в

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

Дизъюнкция

Под дизъюнкцией понимается логическое сложение сигналов двух или нескольких переменных (операция логическое ИЛИ – OR gate). Логическая сумма двух переменных а и b равна лог. 1, если значения или a, или b равны лог. 1. Обозначают дизъюнкцию знаками + (плюс) или символом (от лат. Vel

– «или»), например: y = a + b либо y = a b. Второй способ предпочтителен, так как позволяет отличить логическое сложение от арифметического.

Для двух переменных справедливы следующие соотношения: 0 0 = 0; 0 1 = 1; 1 0 = 1; 1 1 = 1,

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

12

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

На функциональных схемах дизъюнктор обозначается цифрой 1 в правом верхнем углу (рис. 1.2, б). Эпюры напряжений входного и выходного сигналов дизъюнктора приведены на рис. 1.2, в.

а) б) в)

Рис.1.2. Таблица истинности логическогоэлемента ИЛИ – а), условное графическое обозначение – б, эпюрынапряжений – в

Конъюнкция

Под конъюнкцией понимается логическое умножение сигналов двух или нескольких переменных (операция логическое И – AND gate).

Конъюнкция переменных a и b равна лог. 1 в том случае, когда и a, и b равны лог. 1. Операция И в буквенных выражениях обозначается точкой (·), символом или никак не обозначается: y= a b = a b.

Для двух переменных справедливы следующие соотношения: 0 0 = 0; 0 1 = 0; 1 0 = 0; 1 1 = 1,

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

На функциональной схеме (УГО) логическое И обозначается знаком & в правом верхнем углу, как показано рис. 1.3, б.

а) б) в)

Рис. 1.3. Таблица истинности логическогоэлемента И – а), условное графическое обозначение – б, эпюры напряжений – в

Эпюры напряжений, поясняющие работу вентиля И, приведены на рис. 1.3, в.

13

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1.3. Основные положения алгебры логики

Основные законы алгебры логики

В алгебре логики имеется четыре основных закона:

1. Переместительный, или закон коммутативности для операций сложе-

ния и умножения, соответственно:

A B = B A;

A B = B A.

2. Сочетательный, или закон ассоциативности для сложения и умноже-

ния, соответственно:

(A B) C = A (B C);

(A B) C = A (B C).

3. Распределительный, или закон дистрибутивности для сложения и ум-

ножения, соответственно:

(A B) C = A C B·C;

(A B) C = (A C) (B C).

4. Закон двойственности или инверсии (правило де Моргана) для логиче-

ских операций сложения и умножения, соответственно:

сложение Α Β Α Β, Α Β Α Β, Α Β Α Β, Α Β Α Β

умножение Α Β Α Β, Α Β Α Β, Α Β Α Β, Α Β Α Β. Благодаря этим правилам появилась возможность выражать дизъюнкцию

через конъюнкцию и отрицание, а конъюнкцию – через дизъюнкцию и отрицание. Законы двойственности справедливы для любого числа переменных.

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

Эти правила широко используют для преобразования переключательных функций с целью их упрощения.

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

Y AB CD

двойственной функцией будет

YДВ = AB CD=AB CD= A B(C D).

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

Тождества и правила

Для преобразований логических выражений пользуются легко доказываемыми тождествами (таблица 1.1):

14

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

С помощью законов алгебры логики и тождеств могут быть доказаны со-

Доказать справедливость этих соотношений можно путем следующих преобразований:

А A B = A – доказательство A + A B = А (1 + В) = А·1 = А;

A (A B) = A – A (A B) = А А + А В = А + А В = А;

(А· В )(А + В ) = А – (А· В )(А +В ) = А А + АВ +В А +ВВ = = А (1 +В + В + 0) = А.

Эти правила широко используют для преобразования переключательных функций с целью их упрощения.

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

F =(a b) c d = (a b) c d =

((a b) c) d =((a b) c) d =(ab c) d .

Двойственная функция FДВ =(ab c) d

Рис. 1.4. Функциональная схема по заданному выражению – а; функциональная схема двойственной функции – б

Первыми, как и в арифметике, выполняются действия внутри скобок. В булевой алгебре при отсутствии в выражении скобок вводится следующий порядок действий: первыми выполняются операции отрицания, далее конъюнкции, затем – дизъюнкции. Наличие в выражении скобок изменяет обычный порядок действий: в первую очередь должны выполняться операции внутри скобок.

15

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

1.4. Элементарные логические функции.

Совокупность различных значений переменных называют набором. Булева функция n аргументов может иметь до N = 2n наборов. Поскольку функция принимает только два значения, общее число булевых функций n аргументов равно 2N = 22n. Таким образом, функция одного аргумента может иметь четыре значения:

f1 = А, f2= , f3 = 1 (константа 1), f4 = 0 (константа 0).

Два аргумента дают 16 значений функции. Любая из этих функций обращается в единицу (конституента единицы) только на своем наборе, во всех остальных случаях (2n – 1) она равна нулю. Функции взаимно инверсны, если на том же наборе функции обращается в нуль (конституента нуля), а в остальных случаях она равна единице.

В число шестнадцати функций входят и вырожденные функции:

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Логическое ИЛИ-НЕ

Функции «дизьюнция с отрицанием» это логическое ИЛИ-НЕ (NOR gate)

f1 =a b (стрелка Пирса, функция Вебба). Судя по таблице (рис. 1.5, а), низкий уровень напряжения устанавливается на выходе в том случае, если на любом из входов присутствует высокий уровень. Там же, на рис. 1.5, б приведено УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис 1.5, в). Формально количество входов можно наращивать до любой величины, на практике эти значения могут быть только 2-3-4-8.

Рис. 1.5. Таблица истинности ИЛИ-НЕ – а; УГО – б; эпюры напряжений – в

Особенностью функции является то, что высокий уровень H на выходе устанавливается лишь при наличии низких уровней L на всех входах.

Логическое И-НЕ

Следующая функциональная схема – логическое И-НЕ (штрих Шеффера,

NAND gate) f7 = a b . Если на любой из входов подан низкий уровень напряжения, то на выходе устанавливается высокий уровень напряжения (табл. на рис. 1.6, а). Там же приведены УГО логическое И-НЕ и эпюры напряжений входах и выходах схемы (рис. 1.6, а и 1.6, б, соответственно).

Рис. 1.6. Таблица истинности И-НЕ – а; условное обозначение – б; эпюры напряжений – в

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

Запрет по В

Функция «запрет по b» логическая конъюнкция a и b f4 = a b . На рис. 1.7, а представлена таблица истинности, условное графическое обозначение

17

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

показано на рис. 1.7, б и на рис. 1.7, в – эпюры напряжений. В связи с тем, что сигнал b приходит на вход схемы логического умножения в инверсном виде, то сигналы а высокого уровня проходя на выход ЛЭ только при низком уровне управляющего сигнала b, что отражено наэпюрах (рис. 1.7, в).

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

Логический ноль на выходе устанавливается лишь в одном случае, когда a

и b принимают низкий уровень.

Рис. 1.8. Таблица истинности «импликация от В кА»– а; условное обозначение– б; эпюры напряжений – в

Равнозначность А и В

Равнозначность указывает на то, что оба аргумента имеют одинаковый (высокий H или низкий L) уровень. Таблица истинности, и зпюры напряжений приведены на рис. 1.9, а, в, соотвтственно. На основании табл. нетрудно записать логическое выражение для равнозначности

R = a b a b.

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

18

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Функция Шеффера f7 = a b инверсна по отношению к конъюнкции f8 = a b:

f7 f8 .

Функции запрета и импликации также инверсны по отношению друг к другу:

Для функции «запрет по b» f4 = a b инверсной является «импликация от b

В свою очередь «запрет по b» f2 = a bсвоей инверсной функцией имеет

«импликацию от a к b» f13 = a b:

f2 f13 .

Взаимно инверсны функция неравнозначности (сложения по модулю два) f6 = ab ab и функция равнозначности f9 =

ab ab = ab ab .

Для доказательства этого равенства воспользуемся правилом де Моргана:

ab ab = a b ab = (a b) (a b) = aa ab ba bb = ab ab .

С помощью одного и двух переменных, называемых элементарными ло-

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

1.5. Представление переключательных функций

Логические функции, представляющие собой дизъюнкции отдельных членов, каждый из которых, есть некоторая функция, содержащая только конъюнкции, называют логическими функциями дизъюнктивной нормальной формы (ДНФ), например:

fСДНФ = (a b c) (a c).

Если же каждый член дизъюнкции нормальной формы от n аргументов содержит все эти аргументы, часть которых входит в него с инверсией, а часть

– без нее, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ):

fСДНФ = (a b c) (a b c) (a b c).

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

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

циями конъюнктивной нормальной формы (КНФ), например:

fСДНФ = (a b c)(b c).

20

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)