Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
ЭЛЕМЕНТЫ ТЕОРИИ БУЛЕВЫХ ФУНКЦИЙ
Для описания работы ЦЭУ используется математический аппарат алгебры логики, разработку которого связывают с известным английским математиком середины XIX в. Дж.Булем. Функцией алгебры логики (булевой функцией) п-переменных называют функцию F(xi), однозначно сопоставляющую каждому конкретному набору значений 0 или 1 переменных (хn-1,... Х1, Х0) одно из двух возможных значений 0 или 1 самой, функции. Каждый конкретный набор значений переменных xi может рассматриваться в виде /^-битного двоичного кода, поэтому общее количество таких наборов т-2п. В свою очередь, совокупность значений функции F(xi), также можно представить w-битным двоичным кодом, откуда заключаем, что общее число различных булевых функций n-переменных равно 2т. В простейшем случае функция F(xt) может быть задана словесным описанием. Например, функция равна 1, если все три ее переменные или любая пара.из них равны 1, в противном случае . По принципу работы некоторых цифровых электронных устройств отдельные конкретные наборы переменных могут быть исключены (запрещенные наборы), что трактуется как наличие факультативных условий. Обычно на факультативных наборах булевую функцию доопределяют таким образом, чтобы получить наиболее простую ее запись. Любая булева функция п переменных может быть полностью задана таблично, если перечислить все возможные наборы переменных х, и указать соответствующие им значения функции . Построенную таким образом таблицу называют таблицей истинности. Как правило, в таблице истинности наборы переменных располагаются £ порядке нарастания десятичного эквивалента их двоичного кода. В качестве примера на рис.6.1 представлена таблица истинности некоторых булевых функций трех переменных и в том числе функции , описанной выше словесно. Строго говоря, для полного определения булевой функции не обязательно задавать ее значения на всех возможных наборах, достаточно перечислить номера наборов, на которых она обращается в нуль, или только наборов, на которых она равна 1. Например, в соответствии с таблицей истинности на рис.6.1. имеем два варианта описания предыдущей функции: (6.2а) или . (6.26)
Рис.6.1. Таблица истинности некоторых булевых функций трех переменных Конечно, из этих двух вариантов задания функции F( ) стремятся выбрать наиболее компактный, в котором перечислено меньшее количество наборов переменных . Задание булевых функций таблицей истинности не всегда удобно, так как при больших п она становится слишком громоздкой и трудно обозримой. В этом смысле наиболее привлекателен аналитический способ задания булевых функций в виде так называемых структурных формул, показывающих какие логические операции необходимо выполнить над входящими в них переменными х чтобы получить качения данной функции. Для определения основных типов логических операций достаточно Рассмотреть булевы функции одной и двух переменных. При п=1 имеем всего 4 типа булевых функций, таблица истинности для которых приведена на рис.6.2. Заметим, что функция принимает значение 0 независимо от значения аргумента и называется генератором нуля. Аналогично. независимо от и называется генератором единицы. Функция повторяет значение аргумента , что соответствует записи . Наконец, функция принимает инверсные значения аргумента и определяет операцию инверсии (отрицания), которую обозначают чертой сверху аргумента . Операции повторения и инверсии выполняются простейшими цифровыми элементами — соответственно повторителем и инвертором, обозначения которых показаны на рис.6.3, а, б. Инверсия, наряду с другими элементарными логическими операциями широко используется для аналитической записи произвольных булевых функций.
Рис.6.2 Таблица истинности совокупности булевых функций одной переменной
Рис.6.3. Обозначения простейших логических элементов: а- повторитель; б инвертор; в - элемент неравнозначности (сумматор по модулю 2); г - элемент И; д — элемент И—НЕ (Шеффера); е- элемент ИЛИ; ж - элемент ИЛИ НЕ (Пирса)
При п=2 получаем уже 16 различных булевых функций, таблица истинности которых приведена на рис.6.4. Среди булевых функций двух переменных встречаются уже знакомые нам функции генераторов 0 и 1 , а также повторения и инверсии переменных: ; ; ; . Далее отметим пару взаимно инверсных функций . Функция принимает значение 1, если входящие в нее переменные имеют различные значения, и называется функцией неравнозначности (суммы по модулю 2). Операция суммы по модулю 2 обозначает' ся символом 0 и выполняется по следующим правилам:
; ; , что записывают в виде .
Рис.6.4. Булевы функции двух переменных
Заметим, что значения совпадают с содержимым младшего разряда при суммировании двух одноразрядных двоичных чисел, поэтому соответствующий цифровой элемент (сумматор по модулю 2), обозначение которого дано на рис.6.3в часто используют при построении сумматоров двоичных чисел. Оставшиеся восемь попарно инверсных булевых функций обладают таким замечательным свойством, что они принимают значение 1 (либо 0) на одном единственном наборе переменных и равны 0 (соответственно 1) на всех остальных наборах. Среди этих функций отметим функции , инверсную ей , а также и инверсную ей функцию Функцию , принимающую значение 1, если все входящие в нее переменные равны 1, называют конъюнкцией (операцией И). Поскольку значения совпадают с произведением ее аргументов, ее также называют логическим умножением и записывают с использованием знака операции умножения ( × ) либо символа пересечения (∩ ): . Обозначение элемента И, реализующего операцию конъюнкции, приведено нарис. 6.3, г. Элемент, реализующий функцию , инверсную конъюнкции, называют элементом И — НЕ (элементом Шеффера). Его обозначение дано на рис. 6.3, д. Функцию . принимающую значение 0, если все входящие в нee переменные равны 0, называют дизъюнкцией. Иными словами, Дизъюнкция равна 1, если хотя бы одна из ее переменных равна 1. По этой причине функцию часто также называют логическим сложением (операцией ИЛИ) и записывают с использованием знака операции суммирования (+) либо символа объединения (U): . Обозначение элемента ИЛИ показано на Рис.6.3, е. Функцию , инверсную дизъюнкции, записывают в виде и называют операцией ИЛИ — НЕ. Обозначение реализующего эту операцию элемента ИЛИ — НЕ (Элемент Пирса) дано на рис. 6.3, ж. При помощи операций инверсии (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) можно получить аналитическую запись произвольной булевой функции. Вначале покажем, что с помощью операций И, НЕ можно описать любую функцию, принимающую значение 1 на единственном наборе переменных, и равную 0 на всех остальных наборах. Запишем, например, выражение для функции (см. рис.6.4), равную 1 на единственном наборе с номером 1 ( ). Для этого рассмотрим произведение , в которое переменная входит с инверсией, так как в этом наборе = 0, а переменная — без инверсии (так как в этом наборе ). По определению конъюнкции, функция равна 1; если оба сомножителя равны 1, что соответствует набору с номером 1, откуда получаем запись Подобным образом с помощью операций ИЛИ, НЕ можно записать любую функцию, принимающую значение 0 на единственном наборе переменных и 1 — на всех остальных, например, (см.рис.6.4), принимающую единственное значение 0 на наборе с номером 2 ( l, ). Для этого свяжем операцией дизъюнкции переменную , так как в этом наборе , и инверсию (так как в этом наборе =1). Поскольку дизъюнкция равна 0, если каждое из ее слагаемых равно 0, приходим к выводу, что принимает единственное значение 0 именно на наборе с номером 2. Если данная функция равна 1 на нескольких наборах переменных, для каждого из этих наборов запишем соответствующую конъюнкцию, как это было показано выше, а затем все эти конъюнкции свяжем операцией дизъюнкции. Поскольку дизъюнкция равна 1, если хотя бы одно из слагаемых равно 1, получаем аналитическую запись данной функции, равной 1 на всех перечисленных наборах. Аналогично, если функция равна 0 на нескольких наборах, то, записав для каждого из них соответствующую дизъюнкцию, все эти дизъюнкции надо связать операцией конъюнкции. Конечно, из этих двух вариантов записи одной и той же данной функции всегда предпочитают более компактную запись с меньшим количеством входящих в нее членов (конъюнкций или дизъюнкций). Задача 6.2. Составить аналитическую запись булевой функции трех переменных в соответствии с таблицей истинности, приведенной на рис.6.1. Решение. В соответствии с формулой (6.2) эта булева функция равна 1 на наборах 3, 5, 6 и 7. Двоичные коды этих наборов . Каждому из этих наборов сопоставим конъюнкцию, в которой переменную берем без инверсии, если она входит в набор со значением 1 или с инверсией, если в данном наборе она равна 0. Указанные конъюнкции объединяем операцией дизъюнкции, что дает запись
Задача 6.3*. Составить аналитическую запись булевых функций трех переменных F1(x2xix0), F2(x2xlx0), /г3(х2х1х0), F4(x2x{x0), таблица истинности которых представлена на рис.6.1. Ответ: ;
Задача 6.4. Получить аналитическое выражение булевой функции четырех переменных, принимающей значение 0 на наборах с номерами 2, 9, 15 и значение 1 — на остальных наборах. Ответ: . УПРОЩЕНИЕ БУЛЕВЫХ ФУНКЦИЙ Аналитические выражения булевых функций, применяя алгебраические преобразования, как правило, приводят к более простому виду. Для характеристики сложности выражения булевой функции вводят понятие ранга. Рангом булевой функции (или ее отдельного члена) называют общее число входящих в ее выражение переменных (с инверсией или без нее). Смысл дальнейших алгебраических преобразований заключается в том, чтобы, используя соотношения булевой алгебры, получить выражение данной функции с минимальным количеством членов наименьшего ранга, так как для его реализации потребуется не только меньшее количество, но и более простые цифровые элементы (с наименьшим числом входов). Большинство правил алгебраических преобразований булевых функций совпадают с правилами обычной алгебры, но вместе с ними имеют место следующие специфические свойства введенных ранее логических операций: 1) 2)х = 0 3)х + =1 4)хх=х (6.3) 5)х+х = х 6) х + 1 = 1 7) 8) Последнюю пару соотношений называют теоремой двойcтве-нности (де Моргана) и формулируют так: отрицание конъюнкции (дизъюнкции) равно дизъюнкции (конъюнкции) отрицаний входящих в неё членов. Путем многократного применения этой теоремы версию сложных булевых выражений обычно опускают до уровня инверсии отдельных переменных. Как правило, для упрощения булевых выражений используют приемы склеивания и поглощения. В склеивании, как минимум, участвует пара, так называемых, соседних членов, представляющих собой члены одинакового ранга, содержащие общую часть Fи некоторую переменную л, которая в один из соседних членов входит с отрицанием, а в другой — без него. При объединении соседних членов операцией дизъюнкции или конъюнкции соответственно получаем т.е. в любом случае за счет исключения переменной x ранг окончательного выражения уменьшается на единицу. В поглощении участвуют члены различного ранга, причем член меньшего ранга должен обязательно входить в качестве составной части в член более старшего ранга. Объединение таких членов операцией дизъюнкции или конъюнкции дает , т.е. происходит своеобразное «поглощение» члена старшего ранга членом F меньшего ранга. Задача 6.5. Упростить выражение булевой функции Решение. Заметим, что в данном выражении последний член является соседним для трех остальных членов, поэтому его можно с ними склеить попарно. В соответствии со свойством номер 5 из (6.3) допишем еще два слагаемых вида . Теперь для каждой полученной пары соседних слагаемых используем прием склеивания, окончательно получаем Количество слагаемых этого выражениям также их ранг на единицу меньше исходных значений. Задача 6.6. Записать упрощенное выражение булевой функции трех переменных, принимающих значение 0 на наборах с номером 1, 4, 5 и значение 1 — на всех остальных наборах. Ответ: Задача 6.7.* Упростить булевы функции трех переменных, выражения которых записаны в ответах задачи 6.3. Ответ: Задана 6.8. Привести выражение булевой функции трех переменных удобному для ее реализации на элементах И—НЕ. Решение. Применим к данной функции двойную инверсию, после чего для внутренней инверсии воспользуемся теоремой Моргана. Окончательно получаем выражение, содержащее только операции И— НЕ. Задача 6.9.* Привести выражения булевых функций трех переменных, записанных в ответе к задаче 6.7, к виду, содержащему только операции И— НЕ. Ответ: Стремление сделать процедуру минимизации более наглядной привело к поиску таких форм табличного задания булевых функций, чтобы соседние члены располагались рядом, образуя компактные области, выделение которых упрощало бы их склеивание. Удовлетворяющие этому условию таблицы получили название карт м и н и м и з а ц и и, их применение особенно эффективно при относительно небольшом числе аргументов (n < 5). На рис.6.5 представлены карты минимизации для булевых функций двух, трех и четырех аргументов, а также даны примеры их заполнения. Каждая клетка карты соответствует определенному набору переменных. Заметим, что для всех карт на рис. 6.5 клетка в левом верхнем углу соответствует набору 0, номера остальных наборов указаны на картах (смрис.6.5, а, б) Однако при некотором навыке этого можно не делать, Достаточно лишь пометить чертой строки и столбцы, сопоставленные переменным без инверсии (в данном наборе их значения равны 1). Очевид но, остальные строки и столбцы будут определяться их инверсиями, так как на соответствующих наборах значения этих переменных равны 0.
Рис.6.5. Карты минимизации булевых функций двух (а), трех (б) и четырех (в) аргументов
При заполнении карты для данной булевой функции, как правило, заносят 1 в клетки с наборами, на которых эта функция равна единице. Затем все клетки, содержащие единицы, охватываются совокупностью замкнутых прямоугольных областей с числом клеток в каждой, равным степени двойки. Указанные области могут пересекаться, причем одни и те же клетки могут входить в несколько различных областей. Также допускается сворачивание карты в цилиндр как по горизонтальной, так и по вертикальной осям с объединением противоположных граней. Мини- мизированное выражение булевой функции представляет собой дизъюнкцию членов, сопоставленных каждой из замкнутых областей. Поскольку выделение замкнутой области соответствует операции группового склеивания входящих в нее соседних членов, каждая такая область описывается конъюнкцией только тех аргументов, которые для всех членов в ее пределах имеют общие значения (только с инверсией, либо без нее). Например, для области I (рис.6.5, в) имеем минимизированную запись , а область II, соответствующая объединению четырех угловых единиц при сворачивании карты по обеим осям, приводит к записи . При выделении замкнутых областей всегда стремятся к тому, чтобы их число было минимальным и чтобы каждая из них включала в себя возможно большее количество единиц. При наличии факультативных наборов в соответствующие им клетки обычно заносят буквы Ф, а затем рассматривают все возможные варианты размещения в них нулей и единиц, выбирая тот из них, который обеспечивает максимально возможные размеры склеиваемых замкнутых областей. Задача 6.10. Записать минимизированное выражение булевой функции трех переменных, карта которой представлена на рис. 6.5, б. Решение. На карте рис. 6.5, б можно выделить две замкнутые области. Область 1 образуется из четырех единиц в клетках с номерами 2, 3, 7, 6 Для этой области общим значением будет . Вторая область II образуется при объединении соседних членов в клетках 0 и 2 и соответствует записи . Окончательно получаем минимизированную запись .
Задача 6.11. Получить минимизированное выражение булевой функции трех переменных , таблица истинности которой приведена на рис.6 1. Ответ: .
6.4. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ Двоичный логический элемент представляет собой электронную Цепь, выходное состояние которой описывается одной из основных булевых функций. Принципиально безразлично, какое из двух возможных входных и выходных состояний логического элемента принимается за 0, а какое — за 1, но чаще всего применяют положительную (прямую) логик у, при которой единица кодируется наличием (высоким уровнем) напряжения, а нуль — его отсутствием (низким уровнем). Выполненные на диодах и транзисторах в микроэлектронном исполнении двоичные логические элементы называют интегральными логическими элементами (ИЛЭ)и широко используют в качестве элементной базы для построения любых, даже самых сложных, современных ЦЭУ.
Рис.6.6. Схемы элементов диодной логики: а —трехвходовый элемент И б — трехвходовый элемент ИЛИ Логические элементы классифицируют по типам электронных приборов, с помощью которых выполняются основные логические функции. В диодной логике (ДЛ ) для этих целей применяют диоды (рис.6.6). В схеме рис.6.6, а при низком уровне на любом из входов (x2xjx0) соответствующий диод отпирается, и на выходе также будет низкий уровень. Если на всех входах присутствует высокий уровень, все диоды будут закрыты, и на выходе также будет высокий уровень. Для положительной логики такое описание соответствует операции конъюнкции, поэтом) рис.6.6, а представляет схему трехвходового ДЛ-элемента И. Рассуждая аналогично, приходим к выводу, чго схема на рис. 6.6, 6 реализует операцию дизъюнкции (ДЛ-элемент ИЛИ).
Рис.6.7. Базовая схема ТТЛ элемента
инвертор, чаще всего используют каскад на биполярном транзисторе, включенном по схеме с общим эмиттером. Объединение диодной логики с транзисторным инвертором позволило создать схемы диоднотранзисторной логики (ДТЛ- э л е м е н т ы), на основе которых строились первые ЦЭУ в интегральном исполнении. Однако при переходе к массовому выпуску цифровых микросхем на основе ДТЛ-элемен- тов выяснилось, что для получения высокого быстродействия входную диодную логику выгоднее заменить интегральным много- эмиттерным транзистором. Так называют транзистор, у которого имеется обычный переход база — коллектор и несколько переходов база — эмиттер с электрически разделенными областями эмиттеров и общей областью базы. Построенные на его основе ИЛЭ стали называть элементами транзисторно — транзисторной логики (ТТЛ- элементы). На рис.6.7 приведена схема трехвходового ТТЛ-элемента И—НЕ. В этой схеме многоэмиттерный транзистор VT1 выполняет логическую операцию И над входными сигналами, а транзистор VT2 обеспечивает инверсию выходного сигнала. При низком уровне напряжения на любом из входов соответствующий переход база — эмиттер трехэмиттерного транзистора VT1 (п-р-п) оказывается смещенным в прямом направлении, и в нем возникает значительный ток логического нуля, направленный из эмиттера в сторону входа. Значение этого тока определяется сопротивлением резистора RБ в цепи базы, а также прямым сопротивлением перехода (типичное значение тока составляет единицы миллиампер). Однако напряжения одного смещенного в прямом направлении перехода база-эмиттер транзистора VT1 оказывается недостаточным для отпирания двух переходов (база — коллектор транзистора VT1 и база — эмиттер транзистора VT2), в результате чего транзистор VT2 запирается, и на его коллекторе устанавливается высокий уровень напряжения. При высоком уровне напряжения на всех трех входах ( ) из-за падения напряжения на резисторе RБ потенциал базы транзистора VT1 оказывается ниже потенциалов эмиттеров, и все три его перехода эмиттер-база запираются, так как оказываются смещенными в обратном направлении. В свою очередь, переход база—коллектор VT1 отпирается, так как оказывается смещенным в прямом направлении. Через каждый обратносмещенный переход эмиттер—база VT1 проходит небольшой ток логической единицы I ! вх, направленный от соответствующего входа в сторону эмиттера VT1 (типичное значение этого тока составляет около 40 мкА). Коллекторный ток VT1 образует ток базы транзистора VT2, открывая его переход эмиттер — база. На коллекторе VT2 устанавливается низкий Уровень напряжения, причем потенциал базы VT2 оказывается выше потенциала его коллектора, и переход коллектор — база VT2 также открывается. Транзистор VT2 входит в режим насыщения, характеризующийся весьма малым напряжением между его коллектором и эмиттером. Таким образом, уровень 0 на выходе TTJl-элемента (см.рис.6.7) устанавливается при единицах на всех его входах, во всех остальных случаях на выходе будет высокий уровень напряжения. Для положительной логики это соответствует булевой функции И — НЕ. До недавнего времени ТТЛ-элементы были ИЛЭ массового применения. Вместе с тем все более жесткие требования, предъявляемые к современным разработкам, постоянно ставили перед разработчиками все более сложные задачи и, в первую очередь, по поиску путей существенного повышения быстродействия, экономичности и надежности ИЛЭ. Было установлено, что быстродействие ТТЛ-элементов в значительной степени ограничивается из-за насыщенного режима работы транзистора VT2, а их надежность и экономичность во многом определяется схемой инвертора. В соответствии с этим постепенно складывалось и представление о ТТЛ-элементах, как об ИЛЭ среднего быстродействия и значительного потребления энергии источника питания, Довольно длительные поиски в области совершенствования технологии производства интегральных схем (ИС) и новых физических эффектов, используя которые можно было бы повысить быстродействие электронных приборов, увенчались успехом и привели к разработке так называемых ТТЛШ-элементов (транзисторно-транзисторная логика с использованием эффекта Шоттки). Смысл этого эффекта заключается в том, что при создании вблизи p-n-перехода области с избыточным количеством свободных носителей заряда (барьер Шоттки) существенно снижается время восстановления обратного сопротивления перехода при его переводе из открытого в закрытое состояние. ВАХ кремниевых диодов с барьером Шоттки отличаются почти втрое меньшим прямым падением напряжения (примерно 0, 2 — 0, 3 В вместо 0, 6 — 0, 7 В у обычных диодов). Особенно эффективным оказалось применять переходы с барьером Шоттки в качестве переходов база — коллектор интегральных транзисторов, что позволило избежать глубокого насыщения транзисторов и за счет этого существенно повысить их быстродействие. По принципу работы ТТЛШ-элементы. в основном, подобны обычным ТТЛ-элементам, но выгодно отличаются от них помимо применения транзисторов с барьером Шоттки более сложной схемой инвертора (рис.6.8), что позволило увеличить его нагрузочную способность и снизить влияние технологического разброса параметров транзистороъ на эксплуатационные характеристики ТТЛШ-элементов при их массовом выпуске.
Рис 6 8 Схема базового ТТЛШ-элемента ЗИ — НЕ
На рис.6.8 транзисторы VT3 и VT 4, включенные по схеме составного транзистора, играют роль управляемой коллекторной нагрузки основного транзистора VT5. Сложный инвертор работает таким образом, что при отпирании основного транзистора VТ5 составной транзистор VT3 и VT4 запирается и наоборот. Необходимые для управления выходными транзисторами противофазные сигналы снимаются с коллектора и эмиттера транзистора и VT 2, играющего роль расщепителя фаз (парафазный усилитель). Основной транзистор VT5 должен пропускать на землю значительные от всех входов других микросхем, подключенных к выходу данного элемента. Резистор ограничивает сквозной ток от источника питания Еп на землю в моменты переключения инвертора, когда на короткое время все его выходные транзисторы оказываются открытыми. При частых переключениях принимает на себя значительную долю выделяющейся при этом мощности, защищая выходные транзисторы от перегрева. Через этот резистор также проходит суммарный ток логической единицы, который, как отмечалось ранее, направлен от выхода данного элемента ко всем входам других ТТЛШ-элементов, подключенных к нему. Поскольку при размещении ТТЛШ-элементов на печатных платах больших размеров на длинных проводниках могут накапливаться значительные паразитные заряды, диоды VD1 -VD3 открываясь, поглощают их энергию и тем самым защищают эмиттерные переходы транзистора VT1 от пробоя. Все описанные схемотехнические приемы позволили в Рачительной мере повысить эксплуатационную надежность ТТЛШ-микросхем, что особенно важно при их массовом применении За счет использования транзисторов с барьером Шоттки удалось почти на порядок повысить быстродействие ТТЛШ-элементов, а благодаря Последним достижениям в технологии производства ИС и несколько снизить их энергопотребление. Однако существенному повышению экономичности всех ТТЛ-схем препятствует то, что по принципу работы они в статических состояниях потребляют входные токи и . Применение полевых транзисторов, обладающих высоким входным сопротивлением, позволило разработать весьма экономичные логические элементы, потребляющие энергию источников питания только в режиме переключения и практически не потребляющие ее в статических состояниях (0 и 1), Из всех возможных типов полевых транзисторов в современных схемах ИЛЭ наибольшее распространение получили МОП-транзисторы с индуцированным каналом, а из многочисленных серий цифровых ИС — КМОП-м икросхемы. Сокращение КМОП означает применение в схемах инверторов взаимодополняющих (комплементарных) пар транзисторов со структурой металл — окисел — полупроводник, но с каналами различных типов проводимости. Более простая по сравнению с биполярными транзисторами технология получения МОП-транзисторов с индуцированным каналом и КМОП-схе- мотехника позволили создать весьма экономичные микросхемы высокой степени интеграции. |
Последнее изменение этой страницы: 2017-05-05; Просмотров: 899; Нарушение авторского права страницы