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