Телекоммуникации и Информатика и вычислительная техника Ульяновск 2007 2
 Скачать 1.77 Mb.
|
|
2.5. Минимизация логических функций Рассмотренные тождественные преобразования позволяют существенно упростить выражения логических функций. Каждая логическая функция реализуется с помощью определенного набора устройств. Чем меньше элементов содержит выражение, тем проще схема, реализующая соответствующую ему логическую функцию. Поэтому значительный интерес представляет рассмотрение методов минимизации логических функций. Наиболее распространенным является метод непосредственных тождественных преобразований. Этот метод, рассмотренный выше, состоит в последовательном применении к логической формуле законов и правил тождественных преобразований алгебры логики. Он пригоден для простых формул, когда последовательность преобразований очевидна. Наиболее часто этот метод применяется для окончательной минимизации выражений, полученных после минимизации их другими методами. Рассмотрим применение метода непосредственных преобразований на примере минимизации функции трех переменных, заданных ее СДНФ: 3 2 1 3 2 1 3 2 1 3 2 1 3 х х х х х х х х х х х х х х х у) Объединим попарно первое и третье, второе и третье, а также четвертое и пятое элементарные произведения 23 х х х ) х х ( х х х х х х х х х ) х х ( х х ) х х ( х х ) х х ( х х ) х х х х х х ( ) х х х х х х ( ) х х х х х х ( у 1 3 2 2 2 1 3 2 2 1 2 1 3 2 3 3 2 1 3 3 2 1 1 1 3 2 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 Эта формула гораздо проще исходной СДНФ. Здесь в формуле (2.4) в каждой паре объединяемые элементарные произведения различаются лишь одной переменной, которая входит в первое произведение с отрицанием, а во второе – без отрицания. Такие элементарные произведения называются соседними. К соседним произведениям применима операция склеивания, в результате которой уменьшается число суммируемых произведений и на единицу уменьшается число переменных. 2.6. Табличные методы минимизации. Карты Карно Стремление к алгоритмизации поиска соседних элементарных произведений привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно. Карты Карно – это графическое представление таблиц истинности логических функций. Они представляют собой таблицы, содержащие по 2 n прямоугольных ячеек, где n – число логических переменных. На рис. 2.1, 2.2 и 2.3 приведены структуры карт Карно для функции двух, трех и четырех переменных, а в таблицах 2.4 и 2.5 представлены таблицы истинности для функции двух, трех переменных соответственно. Таблица 2.4 х 1 х 2 f(x 1 , x 2 ) 0 0 f(0, 0) 0 1 f(0, 1) 1 0 f(1, 0) 1 1 f(1, 1) х х 0 1 0 f(0,0) f(0,1) 1 f(1,0) f(1,1) Рис. 2.1. Структура карты Карно для функции двух переменных 24 Таблица 2.5 х 1 х 2 х 3 f(x 1 , x 2 , х) 0 0 0 f(0,0,0) 0 0 1 f(0,0,1) 0 1 0 f(0,1,0) 0 1 1 f(0,1,1) 1 0 0 f(1,0,0) 1 0 1 f(1,0,1) 1 1 0 f(1,1,0) 1 1 1 f(1,1,1) х 2 х 3 х 00 01 11 10 0 f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0) 1 f(1,0,0) f(1,0,1) f(1,1,1) f(1,1,0) Рис. 2.2. Структура карты Карно для функции трех переменных х 3 х 4 х 1 х 2 00 01 11 10 00 f(0, 0, 0, 0) f(0, 0, 0, 1) f(0, 0, 1, 1) f(0, 0, 1, 0) 01 f(0, 1, 0, 0) f(0, 1, 0, 1) f(0, 1, 1, 1) f(0, 1, 1, 0) 11 f(1, 1, 0, 0) f(1, 1, 0, 1) f(1, 1, 1, 1) f(1, 1, 1, 0) 10 f(1, 0, 0, 0) f(1, 0, 0, 1) f(1, 0, 1, 1) f(1, 0, 1, 0) Рис. 2.3. Структура карты Карно для функции четырех переменных Карта Карно размечается системой координат, соответствующих значениям входных переменных, например, верхняя строка карты для функции трех переменных соответствует нулевому значению переменной ха нижняя – ее единичному значению. Каждый столбец этой карты характеризуется значениями двух переменных хи х. Комбинация цифр, которыми отмечается каждый столбец, показывает, для каких значений переменных хи х вычисляется функция, размещаемая в клетках этого 25 столбца. Так, в случае карты Карно для функции четырех переменных, функция, расположенная в ячейках столбца с координатами 01, вычисляется при значениях переменных х = 0, х = 1. Функция, расположенная в ячейке на пересечении этого столбца и строки с координатами 11, определяется при наборе входных переменных x 1 = l, x 2 = l, х = 0, х = 1. Если на указанном наборе функция равна 1, то ее СДНФ обязательно содержит элементарное произведение х х х х, принимающее при этом наборе единичное значение. Таким образом ячейки карты Карно, представляющие функцию, содержат столько единиц, сколько элементарных произведений содержится в ее СДНФ, причем каждой единице соответствует одно из элементарных произведений. Координаты строки столбцов в карте Карно следуют не в естественном порядке возрастания двоичных кодов, а в порядке 00; 01; 11; 10. Изменение порядка следования наборов кодов сделано для того, чтобы соседние наборы, отличающиеся между собой лишь цифрой какого-либо одного разряда, были соседними в геометрическом смысле. Рассмотрим таблицу истинности (таблица 2.6) и структуру карты Карно рис. 2.4) для функции 3 2 1 3 2 l х х х ) x , Таблица 2.6 х 1 х 2 х 3 f(x 1 , x 2 , х) 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 26 х 2 х 3 х 00 01 11 10 0 1 1 1 1 1 0 1 0 0 Рис. 2.4. Структура карты Карно для функции Ячейки, в которых функция принимает значение 1, заполняются единицами. Процесс минимизации заключается в формировании прямоугольников, содержащих по 2 k ячеек, где k – целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям. Например, на рис. 2.4 объединены ячейки с координатами 001 и 101. При объединении этих ячеек образовался прямоугольник, в котором х изменяет свое значение. Следовательно, оно исчезает при склеивании соответствующих элементарных произведений 3 х х х их х х . Ячейки, расположенные впервой строке, содержат 1 и являются соседними. Поэтому они объединяются в прямоугольник, содержащий 2 2 = 4 ячейки. Переменные хи х в пределах прямоугольника меняют свое значение, следовательно, они исчезнут из результирующего элементарного произведения. Переменная х является неизменной и равной нулю. Таким образом, элементарное произведение, полученное в результате объединения ячеек первой строки, содержит лишь элемент х. Это следует из того, что четырем ячейкам первой строки соответствует сумма четырех элементарных произведений х ) х х ( х х х х х ) х х ( х х ) х х ( х х х х х х х х х х х х х х 2 2 1 2 1 2 1 3 3 2 1 3 3 2 1 3 2 1 3 2 1 3 2 1 3 2 Совокупность прямоугольников, покрывающих все единицы, называют покрытием. Одна и та же ячейка может покрываться несколько раз. Итак, можно сделать следующие выводы 1. Формула, получающаяся в результате минимизации логической функции с помощью карт Карно, содержит сумму стольких элементарных произведений, сколько прямоугольников имеется в покрытии. 2. Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении. 27 Несмотря на то, что карты Карно изображаются на плоскости, соседство ячеек устанавливается на поверхности тора или цилиндра. Верхняя и нижняя границы карты Карно как бы склеиваются, образуя цилиндр. При склеивании боковых границ получается тороидальная поверхность. Поэтому в примере (рис. 2.5) ячейки с координатами и 0011 являются соседними и объединяются в прямоугольники. Действительно, указанным ячейкам соответствует сумма элементарных произведений 4 3 2 1 1 4 3 2 4 3 2 1 4 3 2 х х х ) х х ( х х х х х х х х х х х х 3 х 4 х 1 х 2 00 01 11 10 00 0 0 1 0 01 1 0 0 1 11 1 0 0 1 10 0 0 1 0 Рис. 2.5. Карта Карно для функции четырех переменных Аналогично объединяются и остальные четыре единичные ячейки. В результате их объединения получаем х х ) х х ( х х ) х х ( х х х ) х х ( х х х х х х х х х х х х х х х х х х х 4 2 3 3 4 2 1 1 4 3 2 1 1 4 3 2 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 Поэтому окончательно f(x 1 , x 2 , x 3 , x 4 ) = 4 2 4 х х х х х Рассмотренные примеры позволяют сформулировать последовательность действий, выполняемых при минимизации логических функций с использованием карт Карно. 1. Изображается таблица для n переменных и производится разметка ее сторон. 2. Ячейки таблицы, соответствующие набором переменных, обращающих функцию в 1, заполняются единицами, остальные ячейки – нулями. 3. Выбирается наилучшее покрытие таблицы правильными прямоугольниками. Наилучшим считается такое покрытие, которое образовано минимальным числом прямоугольников, а если таких вариантов несколько, то из них выбирается тот, который дает максимальную суммарную площадь прямоугольников. 28 Качество минимизации оценивается коэффициентом покрытия k = m/s, где m – общее количество прямоугольников s – суммарное количество покрытых ячеек. Покрытие считается тем лучше, чем меньше его коэффициент k. 2.7. Неполностью определенные логические функции При рассмотрении двоично-десятичных кодов мы отметили, что из 16 возможных комбинаций используются только 10, а остальные комбинации запрещены и возникать не должны. Если каждому разряду поставить в соответствие двоичную переменную, то для двоично-десятичных кодов получим шесть запрещенных комбинаций переменных. Они приведены в табл. 2.7. Если функция имеет запрещенные наборы переменных, то ее значения на указанных наборах не определены ив таблице истинности отмечаются знаком *. Например, в таблице для трех переменных представлена функция (табл. 2.8), имеющая три запрещенных набора переменных. Двоичные функции, значения которых определены не для всех наборов входных переменных, называются неполностью определенными. На карте Карно ячейки, соответствующие запрещенным наборам переменных, также отмечаются знаком * рис. 2.6). При минимизации неполностью определенной функции ее следует доопре- делить, те. неопределенные значения ячеек карты Карно произвольным образом заменить единицами или нулями. х 2 х 3 х 00 01 11 10 0 * 1 1 * 1 0 * 1 0 Рис. 2.6. Карта Карно для функции трех переменных На рис. 2.7 показана функция f 1 (x 1 , x 2 , x 3 ), все значения * которой заменены единицами. Доопределенная функция имеет вид f 1 (x 1 , x 2 , x 3 ) = хне зависит от х. 29 х 2 х 3 х 00 01 11 10 0 1 1 1 1 1 0 1 1 0 Рис. 2.7. Замена знаков * функции f1(x1,x2,x3) единицей Таблица 2.7 Цифрах 1х2х3х4Набор 0 0 0 0 0 Разрешенный 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 - 1 0 1 0 Запрещенный - 1 0 1 1 - 1 1 0 0 - 1 1 0 1 - 1 1 1 0 - 1 1 1 1 Если крайние ячейки верхней строки карты Карно дополнить нулями (рис. 2.8), то получим функцию f 2 , отличную от f 1 : f 2 (x 1 , x 2 , x 3 ) = x 3. х 2 х 3 х 00 01 11 10 0 0 1 1 0 1 0 1 1 0 Рис. 2.8. 3амена знаков * нулями в верхней строке 30 Таблица 2.8 х 1 х 2 х 3 f(x 1 , x 2 , х) 0 0 0 * 0 0 1 1 0 1 0 * 0 1 1 1 1 0 0 0 1 0 1 * 1 1 0 0 1 1 1 1 Эти примеры показывают возможности упрощения формулы неполностью определенной функции при ее соответствующем доопределении. Если функция имеет m запрещенных наборов переменных, то может быть выбран тот вариант, при котором формула минимизированной функции будет наиболее простой. 2.8. Логические элементы и логические операции Одной из основных операций цифровой обработки информации является реализация функциональных зависимостей y = х, х, ..., х n ), ставящих в соответствие каждой комбинации значений двоичных переменных х, х, ..., х n значение двоичной переменной у. Функция такого типа называется переключательной или логической. Переключательную функцию можно задать таблицей, в левой части которой перечисляются комбинации значений аргументов, а в правой значения функции. Переключательную функцию можно задать в аналитической форме, те. в виде некоторого выражения, описывающего последовательность элементарных операций над аргументами функций. Совокупность переключательных функций, определяющая набор элементарных операций, достаточных для реализации любой переключательной функции, называется базисом. В большинстве случаев необходимые логические преобразования двоичных сигналов выполняются на базе трех элементарных операций логического сложения, логического умножения и инверсии. 31 Логическое сложение (дизъюнкция либо операция ИЛИ обозначается или знаком «+»: ух х ... х n , = х + х + ... + х Читается так уесть х или х или, ..., или х n . Иначе говоря, уесть единица, если хотя бы одно из слагаемых равно единице. Логическое умножение (конъюнкция, либо операция И обозначается символом или знаком « »: ух х ... х n = х х ... х Читается так уесть хи хи. их. Другими словами, уесть единица только тогда, когда все сомножители равны единице. Логическое отрицание называемое также инверсией либо операцией НЕ, обозначается чертой над переменной ух, читается так уесть не х. Перечисленные операции образуют так называемую булеву алгебру. Известно, что любую переключательную функцию можно представить аналитическим выражением в булевой алгебре, те. совокупность логических функций, состоящая из логических сложения, умножения и отрицания, является базисом. Правила выполнения логических операций над двоичными переменными для случая двух входных сигналов представлены в таблице 2.9, называемой таблицей истинности. Аналогично определяются операции ИЛИ, И для n входных переменных. Логическим элементом (ЛЭ) или логической схемой называется устройство, реализующее заданную переключательную функцию. Обычно такое устройство имеет n 1 входов и один выход. Таблица 2.9 Операция ИЛИ Операция И Операция НЕ х 1 х 2 y х 1 х 2 y x y 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 32 На функциональных и структурных схемах ЛЭ условно изображается прямоугольником, внутри которого записана реализуемая им логическая функция (рис. 2.9). Функция логического сложения условно обозначается символом 1, умножения – символом, инверсия на выходе (входе) ЛЭ – кружком на выходе (входе) прямоугольника. Логический элемент, реализующий операцию ИЛИ (риса, называется либо дизъюнктором, либо элементом ИЛИ, либо сборкой. Логический элемент, реализующий операцию Ирис, б, называется либо конъюнктором, либо элементом И, либо схемой совпадения. Логический элемент, выполняющий операцию НЕ рис. 2.9, в, называется инвертором. Х Х … Х 1 Y Х Х … Ха б в Рис. 2.9. Функциональное обозначение логических элементов а – элемент ИЛИ б – элемент Ив элемент НЕ На практике широкое распространение получили комбинированные элементы, реализующие последовательно не одну, а две и более операции, например, элементы ИЛИ-НЕ (отрицание дизъюнкции, И-НЕ (отрицание конъюнкции. Логические функции, реализуемые этими элементами, записываются соответственно n 2 1 x x x y , n 2 1 x x x Условные обозначения этих элементов представлены на риса, б. Х Х … Х Y Х Х … Ха б Рис. 2.10. Функциональное обозначение логических элементов ИЛИ-НЕ (аи И-НЕ (б) Элементы ИЛИ-НЕ, И-НЕ являются универсальными, т. к. с помощью элементов одного из этих типов можно выполнить любую базисную функцию И, ИЛИ, НЕ. 33 2.9. Классификация логических элементов Развитие микроэлектроники позволило в последние годы вести крупносерийное производство самых различных интегральных схем (ИС). Их разработка и производство ведется, как правило, в виде серий. Серия – это комплект ИС с различными логическими и электрическими характеристиками, имеющий единые схемотехническое и конструкторско-технологическое исполнения. Существующие в настоящее время микросхемы могут быть классифицированы по многим признакам, но если выделить самое главное-различие топологии электрических схем основных (базовых) ЛЭ, то окажется, что все множество ИС может быть разделено на относительно небольшое число существенно различных систем. Большинство современных ЛЭ относится к элементам потенциального типа, характерными чертами которых являются гальваническая связь между входом ивы- ходом и возможность построения схемы без применения реактивных элементов или с использованием ограниченного числа конденсаторов малой емкости для вспомогательных целей. В современных ЛЭ находят применение как биполярные, таки МОП-транзисторы. Возможности и основные свойства активных цепей таковы, что наиболее просто в схемном отношении реализуются операции И-НЕ, ИЛИ-НЕ. Логические элементы такого вида являются базовыми ив зависимости от конфигурации их схем выделяют следующие основные системы РТЛ – резисторно-транзисторная логика ДТЛ – диодно-транзисторная логика НСТЛ – транзисторная логика с непосредственной связью ТТЛ – транзисторно-транзисторная логика ТТЛШ – транзисторно-транзисторная логика с диодом Шоттки; ЭСЛ – эмиттерно-связанная логика р-МОП – транзисторная логика на р-канальных МОП-транзисторах; n-МОП – транзисторная логика на канальных МОП-транзисторах; КМОП – транзисторная логика на комплементарных МОП-транзисторах. В вычислительных устройствах применяется система положительных и отрицательных логических уровней. При положительной системе логических уровней 34 высокий уровень сигнала соответствует логической единице, а низкий уровень – логическому нулю. Этой системой удобно пользоваться в устройствах, выполненных на транзисторах n-p-n типа. Эту систему условно называют положительной логикой. При отрицательной системе логических уровней высокий уровень напряжения соответствует логическому нулю, а низкий – более отрицательный – логической единице. Этой системой удобно пользоваться в устройствах, выполненных на транзисторах р-n-р типа. |