2.1. Лекция. Проектирование комбинационной логики 1Введени 2Булевы уравнения
 Скачать 2.3 Mb.
|
|
Проектирование комбинационной логики 2.1 Введение 2.2 Булевы уравнения 2.3 Булева алгебра 2.4 От логики к логическим элементам 2.5 Многоуровневая комбинационная логика 2.6 Что за x и z? 2.7 Карты карно 2.8 Базовые комбинационные блоки 2.9 Временные характеристики 2.10 Резюме Упражнения Вопросы для собеседования 2 Глава 2 Проектирование комбинационной логики 145 2.1 ВВЕДЕНИЕ В цифровой электронике под схемой понимают электрическую цепь, которая обрабатывает дискретные сигналы. Такую схему можно рассматривать как «черный ящик», как показано на Рис. 2.1 , при этом схема имеет: Один или более дискретных входов; Один или более дискретных выходов; Функциональную спецификацию (functional specification), описывающую взаимосвязь между входами и выходами; Временнýю спецификацию (timing specification), описывающую задержку между изменением сигналов на входе и откликом выходного сигнала. Рис. 2.1 Схема как «черный ящик» с входами, выходами и спецификациями Если заглянуть внутрь такого «черного ящика», мы увидим, что схемы состоят из соединений, также называемых узлами (nodes), и элементов. Глава 2 Проектирование комбинационной логики 146 Элемент также представляет собой схему с входами, выходами и спецификацией. Соединение – это проводник, напряжение на котором соответствует дискретной переменной. Соединения подразделяются на входы, выходы и внутренние соединения. Входы получают сигналы извне. Выходы отправляют сигналы во внешний мир. Соединения, которые не являются входами или выходами, называются внутренними соединениями. На Рис. 2.2 показана электронная схема с тремя элементами E1, E2 и E3 и шестью соединениями. Соединения A, B и C – входы, Y и Z – выходы, а n1 – внутреннее соединение между E1 и E3. Рис. 2.2 Элементы и соединения Цифровые схемы разделяются на комбинационные (combinational) и последовательностные (sequential). Выходы комбинационных схем зависят только от текущих значений на входах; другими словами, такие схемы комбинируют текущие значения входных сигналов для вычисления значения на выходе. Например, логический элемент – это Глава 2 Проектирование комбинационной логики 147 комбинационная схема. Выходы последовательностных схем зависят и от текущих, и от предыдущих значений на входах, то есть зависят от последовательности изменения входных сигналов. У комбинационных схем, в отличие от последовательностных схем, память отсутствует. Данная глава посвящена комбинационным схемам, а в главе 3 мы рассмотрим последовательностные схемы. Функциональная спецификация комбинационной схемы описывает зависимость значений на выходах от текущих входных значений. Временная спецификация комбинационной схемы состоит из нижней и верхней граничных значений задержки сигнала по пути от входа к выходу. В этой главе мы сначала рассмотрим функциональную спецификацию, а потом вернемся к временной. На Рис. 2.3 показана комбинационная схема с двумя входами и одним выходом. Входы A и B расположены слева, справа изображен выход Y. Символ в прямоугольнике означает, что этот элемент реализован с использованием исключительно комбинационной логики. В этом примере функция F определена как «ИЛИ»: Y = F (A, B) = A + B. Другими словами, мы говорим, что выход Y – это функция двух входов A и B, а именно Y = A ИЛИ B. На Рис. 2.4 показаны два возможных способа построения комбинационной логической схемы, приведенной на Рис. 2.3 . Как мы неоднократно увидим в этой книге, зачастую Глава 2 Проектирование комбинационной логики 148 существует множество способов реализации одной и той же функции. Вы сами выбираете, как реализовать требуемую функцию, исходя из имеющихся в распоряжении «строительных блоков», а также ваших проектных ограничений. Эти ограничения часто включают в себя занимаемую на кристалле микросхемы площадь, скорость работы, потребляемую мощность и время разработки. На Рис. 2.5 показана комбинационная схема с несколькими выходами. Данная комбинационная схема называется полным сумматором, мы ещё вернёмся к ней в разделе 5.2.1 . Два уравнения определяют значения на выходах S и C out как функции входных сигналов A, B и C in Рис. 2.3 Комбинационная логическая схем Рис. 2.4 Два варианта схемы ИЛИ Глава 2 Проектирование комбинационной логики 149 Для упрощения чертежей мы часто используем перечеркнутую косой чертой линию и число рядом с ней для обозначения шины (bus), то есть группы сигналов. Число показывает, сколько сигналов в шине (прим. переводчика: это число обычно называется шириной шины). Например, на Рис. 2.6 (a) показан блок комбинационной логики с тремя входами и двумя выходами. Если количество разрядов не имеет значения или очевидно из контекста, то косая черта может быть без числа рядом. Рис. 2.5 Многовыходная комбинационная схема Рис. 2.6 Обозначение шин на схемах На Рис. 2.3 (b) показаны два блока комбинационной логики с произвольным числом выходов одного блока, которые являются входами для другого блока. Правила комбинационной композиции говорят нам, как мы можем построить большую комбинационную схему из более маленьких Глава 2 Проектирование комбинационной логики 150 комбинационных элементов. Схема является комбинационной, если она состоит из соединенных между собой элементов и выполнены следующие условия: Каждый элемент схемы сам является комбинационным; Каждое соединение схемы является или входом, или подсоединено к одному-единственному выходу другого элемента схемы; Схема не содержит циклических путей: каждый путь в схеме проходит через любое соединение не более одного раза. Правила комбинационной композиции схем являются достаточными, но не строго необходимыми. Некоторые схемы, не подчиняющиеся этим правилам, все же являются комбинационными, поскольку значения их выходов зависят только от текущих значений на входах. Однако бывает довольно сложно определить, являются ли некоторые нетипичные схемы комбинационными или нет, поэтому обычно при разработке комбинационных схем мы ограничиваем себя правилами комбинационной композиции. Пример 2.1 КОМБИНАЦИОННЫЕ СХЕМЫ Какие из схем на Рис. 2.7 являются, согласно правилам комбинационной композиции, комбинационными? Глава 2 Проектирование комбинационной логики 151 Рис. 2.7 Примеры схем Решение: Схема (а) – комбинационная. Она составлена из двух комбинационных элементов (инверторы I1 и I2). В ней три соединения: n1, n2 и n3. Соединение n1 – вход схемы и вход для I1; n2 – внутреннее соединение, являющееся выходом для I1 и входом для I2; n3 – выход схемы и выход I2. Схема (b) – это не комбинационная схема, поскольку в ней есть циклический путь: выход элемента «исключающее ИЛИ» подключен к одному из его собственных входов, то есть циклический путь, начинаясь в n4, проходит через «исключающее ИЛИ» к n5, который ведет обратно к n4. Схема (с) – комбинационная, а (d) – не комбинационная, поскольку соединение n6 подключено к выходам двух элементов (I3 и I4). Схема (e) – комбинационная, представляющая собой две комбинационные схемы, соединенные между собой Глава 2 Проектирование комбинационной логики 152 и образующие более крупную комбинационную схему. Схема (f) не отвечает правилам комбинационной композиции, поскольку в ней есть циклический путь через два элемента. В зависимости от функций этих элементов эта схема может быть, а может и не быть комбинационной. Большие схемы, такие как микропроцессоры, могут быть очень сложными, поэтому мы будем применять принципы, описанные в главе 1 , чтобы справится со сложностью. Рассмотрение схемы как «черного ящика» с тщательно определенными интерфейсом и функцией есть применение принципов абстракции и модульности. Построение схемы из более мелких элементов является применением иерархического подхода к разработке. Правила комбинационной композиции суть применение дисциплины. Функциональная спецификация комбинационной схемы обычно задается в виде таблицы истинности или булева уравнения. В следующих разделах будет описано, как вывести булево уравнение из любой таблицы истинности и как применять булеву алгебру и карты Карно для упрощения уравнений. Мы рассмотрим, как реализовывать эти уравнения, используя логические элементы, и как анализировать скорость работы таких схем. Глава 2 Проектирование комбинационной логики 153 2.2 БУЛЕВЫ УРАВНЕНИЯ Булевы уравнения используют переменные, имеющие значение ИСТИНА или ЛОЖЬ, поэтому они идеально подходят для описания цифровой логики. В этом разделе сначала будет приведена терминология, часто используемая в булевых уравнениях, а затем будет показано, как записать булевы уравнения для любой логической функции по её таблице истинности. 2.2.1 Терминология Дополнение (complement) переменной А – это ее отрицание A¯ . Переменная или ее дополнение называются литералом. Например, А, A¯ , В и B¯ – литералы. Мы будем называть А прямой формой переменной, а A¯ – комплементарной формой; «прямая форма» не подразумевает, что значение А равно ИСТИНЕ, а говорит лишь о том, что у А нет черты сверху. Операция «И» над одним или несколькими литералами называется конъюнкцией, произведением (product) или импликантой. A¯ B, AB¯ C¯ и B являются импликантами для функции трех переменных. Минтерм (minterm, элементарная конъюнктивная форма) – это произведение, включающее все входы функции. AB¯ C¯ – это минтерм для функции трех переменных A, B и C, а A¯ B – не минтерм, поскольку он не включает в Глава 2 Проектирование комбинационной логики 154 себя С. Аналогично, операция «ИЛИ» над одним или более литералами называется дизъюнкцией или суммой. Макстерм (maxterm, элементарная дизъюнктивная форма) – это сумма всех входов функции. A + B¯ + C является макстермом функции трех переменных A, B и C. Порядок операций важен при анализе булевых уравнений. Означает ли Y = A + BC, что Y = (A ИЛИ B) И C или Y = A ИЛИ (B И C)? В булевых уравнениях наибольший приоритет имеет операция НЕ, затем идет И, затем ИЛИ. Как и в обычных уравнениях, произведения вычисляются до вычисления сумм. Таким образом, правильно уравнение читается как Y = A ИЛИ (B И C). уравнение (2.1) – ещё один пример, показывающий порядок операций. A¯ B + BCD¯ = ((A¯ )B + (BC(D¯ )) (2.1) 2.2.2 Дизъюнктивная форма Таблица истинности для функции N переменных содержит 2 N строк, по одной для каждой возможной комбинации значений входов. Каждой строке в таблице истинности соответствует минтерм, который имеет значение ИСТИНА для этой строки. На Рис. 2.8 показана таблица истинности функции двух переменных А и В. В каждой строке показан соответствующий ей минтерм. Например, минтерм для первой строки – Глава 2 Проектирование комбинационной логики 155 это A¯ B¯ , поскольку A¯ B¯ имеет значение ИСТИНА тогда, когда А = 0 и В = 0. Минтермы нумеруют начиная с 0; первая строка соответствует минтерму 0 (m 0 ), следующая строка – минтерму 1 (m 1 ), и так далее. Рис. 2.8 Таблица истинности и минтермы Можно написать булево уравнение для любой таблицы истинности путем суммирования всех тех минтермов, для которых выход Y имеет значение ИСТИНА. Например, на Рис. 2.8 есть только одна строка (минтерм), для которой выход Y имеет значение ИСТИНА, она отмечена синим цветом. Таким образом, Y = A¯ B. На Рис. 2.9 показана таблица, в которой выход имеет значение ИСТИНА для нескольких строк. Суммирование отмеченных минтермов дает Y = A¯ B + AB. Такая сумма минтермов называется совершенной дизъюнктивной нормальной формой функции (sum-of-products canonical form). Она представляет собой сумму (операцию «ИЛИ») произведений (операций «И», образующих минтермы). Хотя существует много Глава 2 Проектирование комбинационной логики 156 способов записать одну и ту же функцию, такую как Y = A¯ B + AB, мы будем записывать минтермы в том же порядке, как в таблице истинности, чтобы всегда получать одно и то же булево выражение для одной и той же таблицы истинности. Совершенная дизъюнктивная нормальная форма также может быть записана через символ суммы Σ. При использовании такого обозначения функция на Рис. 2.9 будет выглядеть так: F(A, B) = Σ(m 1 , m 3 ) (2.2) или F(A, B) = Σ(1, 3) Рис. 2.9 Таблица истинности с несколькими минтермами, равными ИСТИНЕ Глава 2 Проектирование комбинационной логики 157 Пример 2.2 ДИЗЪЮНКТИВНАЯ ФОРМА У Бена Битдидла намечается пикник. Он не обрадуется, если пойдёт дождь или появятся муравьи. Постройте схему, в которой выход будет принимать значение ИСТИНА только в том случае, если Бену пикник понравится. Решение: Сначала определим входы и выходы. Входами будут переменные A и R, что означает муравьев (ants) и дождь (rain). Значение А принимает значение ИСТИНА, когда муравьи есть, и ЛОЖЬ, когда муравьев нет. Аналогично, R имеет значение ИСТИНА, когда идёт дождь, и ЛОЖЬ, когда Бену светит солнце. Выход E (enjoyment, радость) показывает настроение Бена. E имеет значение ИСТИНА, когда Бен радуется пикнику, и ЛОЖЬ, когда он страдает. На Рис. 2.10 показана таблица истинности впечатлений Бена от пикника. Используя дизъюнктивную форму, запишем уравнение так: E = A¯ R¯ или E = Σ(0). Мы можем реализовать соответствующую схему, используя два инвертора и двухвходовой элемент И, как показано на Рис. 2.11 (а) Вы могли заметить, что эта таблица является точно такой же, как и таблица для функции «ИЛИ-НЕ», рассмотренной в разделе 1.5.5 : E = A ИЛИ-НЕ R = R A + Глава 2 Проектирование комбинационной логики 158 На Рис. 2.11 (b) показана реализация на базе элемента ИЛИ-НЕ. В разделе 2.3 мы покажем, что выражения R A + и R A + эквивалентны. Рис. 2.10 Таблица истинности Бена Рис. 2.11 Схема Бена Совершенная дизъюнктивная нормальная форма позволяет записать булево уравнение для любой таблицы истинности с любым количеством переменных. На Рис. 2.12 показана произвольная таблица истинности для трехвходового элемента. Совершенная дизъюнктивная нормальная форма соответствующей логической функции выглядит так: Y = A¯ B¯ C¯ + AB¯ C¯ + AB¯ C (2.3) или Y = Σ(0, 4, 5) Глава 2 Проектирование комбинационной логики 159 Рис. 2.12 Произвольная таблица истинности с тремя входами К сожалению, совершенная дизъюнктивная нормальная форма не всегда позволяет получить простое уравнение. В разделе 2.3 мы покажем, как записать одну и ту же функцию, используя меньшее число членов уравнения. 2.2.3 Конъюнктивная форма Альтернативный способ выражения булевых функций – это совершенная конъюнктивная нормальная форма (products-of-sum forms). Каждая строка таблицы истинности соответствует макстерму, который имеет значение ЛОЖЬ для этой строки. Например, макстерм для первой строки для двухвходовой таблицы истинности – это (A + B), поскольку (A + B) имеет значение ЛОЖЬ, когда A = 0 и B = 0. Для любой схемы, заданной таблицей истинности, мы можем записать ее булево Глава 2 Проектирование комбинационной логики 160 уравнение как логическое «И» всех макстермов, для которых выход имеет значение ЛОЖЬ. Совершенная конъюнктивная нормальная форма также может быть записана с использованием символа Π. Пример 2.3 КОНЪЮНКТИВНАЯ ФОРМА Запишите уравнение в совершенной конъюнктивной нормальной форме для таблицы истинности на Рис. 2.13 Решение: Таблица истинности имеет две строки, в которых выход имеет значение ЛОЖЬ. Следовательно, функция может быть записана в конъюнктивной форме так: Y = (A + B)( + B). Также функция может быть записана как Y = Π(M 0 , M 2 ) или Y = Π(0, 2). Первый макстерм, (A + B), гарантирует, что Y = 0 для A = 0 и B = 0, так как логическое «И» любого значения и нуля дает нуль. Аналогично, второй макстерм (A¯ + B) гарантирует, что Y = 0 для комбинации A = 1 и B = 0. На Рис. 2.13 показана такая же таблица истинности, как и на Рис. 2.9 , чтобы продемонстрировать, что одна и так же функция может быть записана более чем одним способом. Рис. 2.13 Таблица истинности с макстермами Глава 2 Проектирование комбинационной логики 161 Аналогично, булево уравнение для пикника Бена ( Рис. 2.10 ) может быть записано в совершенной конъюнктивной нормальной форме, если обвести три строки с нулями для того, чтобы получить E = (A + R¯ )(A¯ + R)(A¯ + R¯ ) или E = Π(1, 2, 3). Это не такая красивая запись, как дизъюнктивное уравнение, E = , но эти два уравнения логически эквивалентны. Дизъюнктивная форма дает более короткое уравнение, когда выход имеет значение ИСТИНА только в нескольких строках таблицы истинности; конъюнктивная же форма проще, когда выход имеет значение ЛОЖЬ только в нескольких строках таблицы истинности. 2.3 БУЛЕВА АЛГЕБРА В предыдущем разделе мы изучили, как записывать булевы выражения при наличии таблицы истинности. Однако, выражение, получаемое таким способом, не обязательно приводит к простейшему набору логических элементов. Вы можете использовать булеву алгебру для упрощения булевых уравнений точно так же, как вы используете алгебру для упрощения математических уравнений. Правила булевой алгебры очень похожи на правила обычной алгебры, но в некоторых случаях они проще, потому что переменные имеют только два возможных значения: 0 или 1. Глава 2 Проектирование комбинационной логики 162 Булева алгебра основана на наборе аксиом, которые мы считаем верными. Аксиомы являются недоказуемыми в том смысле, что определение не может быть доказано. С помощью этих аксиом мы доказываем все теоремы булевой алгебры. Эти теоремы имеют огромную практическую значимость, потому что с их помощью мы учимся тому, как упрощать логические уравнения, чтобы получать более дешевые и компактные схемы. Аксиомы и теоремы булевой алгебры подчиняются принципу двойственности. Если взаимно заменить символы 0 и 1, а так же взаимно заменить операторы • (И) и + (ИЛИ), то булево выражение останется верным. Мы используем символ «штрих» (’) для обозначения двойственного выражения. 2.3.1 Аксиомы В Табл. 2.1 приведены аксиомы булевой алгебры. Эти пять аксиом и двойственные им аксиомы определяют булевы переменные и значения операторов НЕ, И, ИЛИ. Аксиома А1 показывает, что булева переменная B имеет значение 0, если она не имеет значение 1. Двойственное выражение для этой аксиомы А1’ утверждает, что переменная принимает значение 1, если она не имеет значение 0. Вместе аксиомы А1 и А1’ говорят нам, что мы работает в булевом, то есть бинарном поле, состоящем из значений нулей и единиц. Аксиомы Глава 2 Проектирование комбинационной логики 163 А2 и А2’ определяют операцию НЕ. Аксиомы с А3 по А5 определяют операцию И, а их двойственные аксиомы (А3’ – А5’) определяют операцию ИЛИ. Табл. 2.1 Аксиомы булевой алгебры Аксиома Двойственная аксиома Название A1 B = 0 если B ≠1 A1′ B = 1 если B ≠0 Бинарное поле A2 0¯ = 1 A2′ 1¯ = 0 НЕ A3 0 • 0 = 0 A3′ 1 + 1 = 1 И/ИЛИ A4 1 • 1 = 1 A4′ 0 + 0 = 0 И/ИЛИ A5 0 • 1 = 1 • 0 = 0 A5′ 1 + 0 = 0 + 1 = 1 И/ИЛИ 2.3.2 Теоремы одной переменной Теоремы с Т1 по Т5 в Табл. 2.2 описывают, как упростить уравнения, содержащие одну переменную. Теорема идентичности Т1 утверждает, что для любой булевой переменной В выполнено В И 1 = В. Двойственная ей теорема говорит о том, что В ИЛИ 0 = В. В аппаратуре, как показано на Рис. 2.14 , Т1 означает, что если уровень сигнала на одном из входов двухвходового элемента И всегда равен 1, то мы можем удалить этот элемент и заменить его проводом, соединяющим выход этого элемента с входом В, значение которого может меняться. Точно так же теорема Глава 2 Проектирование комбинационной логики 164 Т1’ говорит о том, что если один вход двухвходового элемента ИЛИ всегда равен 0, мы можем заменить этот элемент на провод, соединенный с входом В. Как правило, элементы имеют определенную стоимость, энергопотребление и задержку прохождения сигнала, поэтому замена элемента на провод является целесообразной. Табл. 2.2 Булевы теоремы для одной переменной Теорема Двойственная теорема Название T1 B • 1 = B T1′ B + 0 = B Идентичность T2 B • 0 = 0 T2′ B + 1 = 1 Нулевой элемент T3 B • B = B T3′ B + B = B Идемпотентность T4 = B Инволюция T5 B • B¯ = 0 T′ B + B¯ = 1 Дополнительность Теорема о нулевом элементе Т2 говорит, что B И 0 всегда равно 0. Следовательно, 0 называют нулевым элементом для операции И, потому что он обнуляет эффект любого другого входа. Двойственная ей теорема говорит о том, что В ИЛИ 1 всегда равно 1. Таким образом, 1 – это нулевой элемент для операции ИЛИ. В аппаратуре, как показано на Рис. 2.15 , если один вход элемента И равен 0, мы можем заменить элемент И проводом, подключенным к низкому логическому уровню (0). Точно так же, если один из входов элемента ИЛИ равен 1, мы можем Глава 2 Проектирование комбинационной логики 165 заменить элемент ИЛИ на провод, который подключен к высокому логическому уровню (1). Рис. 2.14 Теорема идентичности в аппаратуре: (a) T1, (b) T1’ Рис. 2.15 Теорема о нулевом элементе в аппаратуре: (a) T2, (b) T2’ Теорема о нулевом элементе приводит к нелепым утверждениям, которые при этом оказываются верными! Эта теорема становится особенно опасной, когда её применяют те, кто делает рекламу: «ВЫ ПОЛУЧИТЕ МИЛЛИОН ДОЛЛАРОВ или мы пришлём вам по почте зубную щётку» (скорее всего, вы получите зубную щётку по почте). Теорема об идемпотентности Т3 утверждает, что операция логического «И» двух равных друг другу переменных имеет значение, равное этой переменной. Аналогичное утверждение верно для операции «ИЛИ» с двумя одинаковыми значениями на входах. Глава 2 Проектирование комбинационной логики 166 Название теоремы происходит от латинских слов «idem» – тот же, такой же и «potent» – сила. Операции возвращают те же значения, которые вы подаете им на вход. На Рис. 2.16 показано, как идемпотентность позволяет заменить элемент схемы на провод. Теорема об инволюции Т4 – это забавный способ описания того, что двойное отрицание переменной дает её исходное значение. Два последовательно включенных инвертора логически отменяют друг друга, то есть они эквивалентны проводу, как показано на Рис. 2.17 Двойственной ей теоремой является она сама. Рис. 2.16 Теорема об идемпотентности в аппаратуре: (a) T3, (b) T3' Рис. 2.17 Теорема о дополнительности в аппаратуре: (a) T5, (b) T5 Теорема о дополнительности Т5 ( Рис. 2.18 ) утверждает, что операция И над переменной и её инверсным значением дает 0 (потому что одна Глава 2 Проектирование комбинационной логики 167 из них всегда будет равна нулю). И, согласно принципу двойственности, операция ИЛИ над переменной и её инверсным значением всегда дает 1 (так как одна из них всегда будет равна единице). Рис. 2.18 Теорема инволюции в аппаратуре: (a) T4, (b) T4' 2.3.3 Теоремы с несколькими переменными Теоремы с Т6 по Т12 в Табл. 2.3 описывают, как упростить уравнения, включающие в себя более одной булевой переменной. Теоремы Т6 о коммутативности и Т7 об ассоциативности работают так же, как и в традиционной алгебре. В соответствии с принципом коммутативности порядок входов для функций И или ИЛИ не влияет на значение выхода. Согласно принципу ассоциативности любое группирование входов не влияет на значение выхода. Глава 2 Проектирование комбинационной логики 168 Теорема о дистрибутивности Т8 является точно такой же, как и в традиционной алгебре, а двойственная ей теорема Т8‘ – нет. Согласно теореме Т8 оператор И дистрибутивен относительно операции ИЛИ. Т8‘ говорит, что оператор ИЛИ дистрибутивен относительно операции И. В традиционной алгебре оператор умножения дистрибутивен относительно операции сложения, но не наоборот, то есть (B + C) × (B + D) ≠ B + (C × D). Теоремы поглощения, склеивания и согласованности Т9 – Т11 позволяют нам удалять излишние переменные. Если вы немного подумаете, вы сможете убедиться, что эти теоремы справедливы. Табл. 2.3 Булевы теоремы для нескольких переменных Теорема Двойственная теорема Название T6 B • C = C • B T6′ B + C = C + B Коммутативность T7 (B • C) • D = B • (C • D) T7′ (B + C) + D = B + (C + D) Ассоциативность T8 (B • C) + (B • D) = B • (C + D) T8′ (B + C) • (B + D) =B + (C • D) Дистрибутивность T9 B • (B + C) = B T9′ B + (B • C) = B Поглощение T10 (B • C) + (B • C¯ ) = B T10′ (B + C) • (B + C¯ ) = B Склеивание T11 (B • C) + (B¯ • D) + (C • D) = B • C + B¯ • D T11′ (B + C) • (B¯ + D) • (C + D) = (B + C) • (B¯ +D) Согласованность T12 ( ) 2 1 0 2 1 0 B B B B B B + + = • • T12′ ( ) 2 1 0 2 1 0 B B B B B B • • = + + Теорема де Моргана Глава 2 Проектирование комбинационной логики 169 Теорема де Моргана Т12 является особенно мощным инструментом при разработке цифровых устройств. Эта теорема поясняет, что дополнение результата умножения всех термов равно сумме дополнений каждого терма. Аналогично дополнение суммы всех термов равно результату умножения дополнений каждого терма. В соответствии с теоремой де Моргана, элемент И-НЕ эквивалентен элементу ИЛИ с инвертированными входами. Аналогично, ИЛИ-НЕ эквивалентен элементу И с инвертированными входами. На Рис. 2.19 показаны эквивалентные по де Моргану элементы И-НЕ и ИЛИ-НЕ. Каждая пара символов, приведенная для каждой функции, называется двойственной. Они логически эквивалентны и взаимозаменяемы. Рис. 2.19 Эквивалентные по де Моргану элементы Глава 2 Проектирование комбинационной логики 170 Кружочек на графическом обозначении элементов является обозначением отрицания (инверсии). Интуитивно вы можете представить, что если «вдавить» этот кружочек с одной стороны логического элемента, то он «выскочит» на другой, при этом тип элемента изменится с И на ИЛИ (и наоборот). Это называется «перемещением инверсии». Например, элемент И-НЕ на Рис. 2.19 состоит из элемента И с отрицанием на выходе. Перемещение инверсии влево приводит к получению элемента ИЛИ с двумя отрицаниями на входах. Базовые правила для перемещения инверсии таковы: Перемещение инверсии назад (от выхода) или вперед (от входов) меняет тип элемента с И на ИЛИ и наоборот; Перемещение инверсии с выхода назад ко входам приводит к тому, что на всех входах появляется инверсия; Перемещение инверсии со всех входов элемента к выходу приводит к появлению инверсии на выходе. В разделе 2.5.2 принцип перемещения инверсии используется для анализа схем. Глава 2 Проектирование комбинационной логики 171 Август де Морган Август де Морган, умер в 1871 г. Британский математик, родился в Индии. Был слепым на один глаз. Его отец умер, когда ему было 10 лет. Поступил в Тринити Колледж в Кембридже, и был назначен профессором математики в возрасте 22 лет в только что открытом в то время Лондонском университете. Много писал на различные математические темы, включая логику, алгебру и парадоксы. В честь де Моргана был назван кратер на Луне. Он придумал загадку про год своего рождения: «Мне было Х лет в году Х 2 ». Пример 2.4 ПОЛУЧИТЕ КОНЪЮНКТИВНУЮ ФОРМУ На Рис. 2.20 приведена таблица истинности для булевой функции Y и её дополнения Y. Используя теорему де Моргана, получите конъюнктивную нормальную форму функции Y из дизъюнктивной формы Y. Глава 2 Проектирование комбинационной логики 172 Решение: На Рис. 2.21 обведены минтермы, содержащиеся в функции Y. Дизъюнктивная нормальная форма функции Y имеет следующий вид: Y¯ = A¯ B¯ + A¯ B (2.4) Применяя операцию инверсии к обеим частям уравнения и дважды используя теорему де Моргана, получаем: ) )( ( ) )( ( ) ( B A B A B A B A B A B A Y Y + + = = + = = (2.5) Рис. 2.20 Таблица истинности, показывающая Y и Y' Рис. 2.21 Таблица истинности, показывающая Y и Y' 2.3.4 Правда обо всем этом Любопытный читатель может задать вопрос о том, как же доказать правильность теоремы. В булевой алгебре доказательство теорем с конечным числом переменных является простым: нужно показать, что Глава 2 Проектирование комбинационной логики 173 теорема верна для всех возможных значений этих переменных. Этот метод называется совершенной индукцией и может быть выполнен с использованием таблицы истинности. Пример 2.5 ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ СОГЛАСОВАННОСТИ МЕТОДОМ ПОЛНОГО ПЕРЕБОРА Докажите теорему согласованности Т11 из Табл. 2.3 Решение: проверьте обе части уравнения для всех восьми комбинаций переменных B, C и D. Таблица истинности на Рис. 2.22 иллюстрирует все эти комбинации. Поскольку равенство BC + B¯ D + CD = BC + B¯ D верно для всех случаев, теорема доказана. Рис. 2.22 Таблица истинности, доказывающая Т11 Глава 2 Проектирование комбинационной логики 174 2.3.5 Упрощение уравнений Теоремы булевой алгебры помогают нам упрощать булевы уравнения. Например, возьмём дизъюнктивную форму выражения из таблицы истинности на Рис. 2.9 : Y = A¯ B¯ + AB¯ . В соответствии с теоремой Т10, уравнение можно упростить до Y = B¯ . Возможно, это очевидно при взгляде на таблицу истинности. В общем случае может потребоваться несколько шагов для упрощения более сложных уравнений. Основной принцип упрощения дизъюнктивных уравнений – это комбинирование термов с использованием отношения PA + PA¯ = P, где P может быть любой импликантой. Насколько может быть упрощено уравнение? По определению уравнение дизъюнктивной формы является минимизированным, если оно включает в себя минимально возможное количество импликант. Если есть несколько уравнений с одинаковым количеством импликант, минимальным будет то уравнение, в котором меньше литералов. Импликанта называется простой (prime implicant), если она не может быть объединена с другими импликантами в уравнении для того, чтобы образовать новую импликанту с меньшим количеством литералов. Все импликанты в минимальном уравнении должны быть простыми. Иначе, они могут быть объединены, чтобы уменьшить количество литералов. Глава 2 Проектирование комбинационной логики 175 Пример 2.6 МИНИМИЗАЦИЯ УРАВНЕНИЯ Минимизируйте уравнение (2.3) : A¯ B¯ C¯ + AB¯ C¯ + AB¯ C Решение: Мы начинаем с исходного уравнения и применяем булевы теоремы шаг за шагом, как показано в Табл. 2.4 Упростили ли мы полностью уравнение на этой стадии? Давайте посмотрим внимательно. В оригинальном уравнении минтермы A¯ B¯ C¯ и AB¯ C¯ отличаются только переменной А. Поэтому мы объединяем минтермы и получаем B¯ C¯ . Однако, если мы посмотрим на исходное уравнение, мы заметим, что последние два минтерма AB¯ C¯ и AB¯ C также отличаются одним литералом (C и C¯ ). Таким образом, используя тот же самый метод, мы могли бы объединить эти два минтерма и получить минтерм АB¯ . Можно сказать, что импликанты B¯ C¯ и AB¯ делят между собой минтерм AB¯ C¯ . Итак, остановились ли мы на упрощении только одной пары минтермов, или мы можем упростить обе? Используя теорему об идемпотентности, мы можем дублировать минтермы столько раз, сколько нам нужно: B = B + B + B + B… Используя этот принцип, мы полностью упрощаем уравнение до его простых импликант, B¯ C¯ + AB¯ , как показано в Табл. 2.5 Глава 2 Проектирование комбинационной логики 176 Табл. 2.4 Минимизация выражения Шаг Выражение Объяснение A ¯ B ¯ C ¯ + AB ¯ C ¯ + AB ¯ C 1 B ¯ C ¯ (A ¯ + A) + AB ¯ C T8: дистрибутивность 2 B ¯ C ¯ (1) + AB ¯ C T5: дополнительность 3 B ¯ C ¯ + AB ¯ C T1: идентичность Табл. 2.5 Улучшенная минимизация выражения Шаг Выражение Объяснение A ¯ B ¯ C ¯ + AB ¯ C ¯ + AB ¯ C 1 A ¯ B ¯ C ¯ + AB ¯ C ¯ + AB ¯ C ¯ + AB ¯ C T3: идемпотентность 2 B ¯ C ¯ (A ¯ + A) + AB ¯ (C ¯ + C) T8: дистрибутивность 3 B ¯ C ¯ (1) + AB ¯ (1) T5: дополнительность 4 B ¯ C ¯ + AB ¯ T1: идентичность Хотя это немного нелогично, расширение импликанты (например, превращение AB в ABC + ABC¯ ) иногда полезно при минимизации уравнений. Делая так, вы можете повторять один из расширенных минтермов для его объединения с другим минтермом. Вы могли заметить, что полное упрощение булевых уравнений при помощи теорем булевой алгебры может потребовать нескольких попыток, Глава 2 Проектирование комбинационной логики 177 некоторые из которых будут ошибочными. В разделе 2.7 описана методика, позволяющая упростить процесс минимизации – карты Карно. Зачем же трудиться над упрощением булева уравнения, если оно остается логически эквивалентным? Упрощение уменьшает количество элементов, используемых при физическом воплощении функции в аппаратуре, тем самым делая схему меньше, дешевле и, возможно, быстрее. В следующем разделе рассказывается, как воплощать булевы уравнения при помощи логических элементов. Глава 2 Проектирование комбинационной логики 178 2.4 ОТ ЛОГИКИ К ЛОГИЧЕСКИМ ЭЛЕМЕНТАМ Принципиальная схема – это изображение цифровой схемы, показывающее элементы и соединяющие их проводники. Например, схема на Рис. 2.23 показывает возможную аппаратную реализацию нашей любимой логической функции ( уравнение (2.3) ): Y = A¯ B¯ C¯ + AB¯ C¯ + AB¯ C Рис. 2.23 Схема Y = A¯ B¯ C¯ + A B¯ C¯ + A B¯ C Глава 2 Проектирование комбинационной логики 179 Изображая принципиальные схемы в унифицированном виде, нам становится легче читать их и отлаживать. В большинстве случаев мы будем придерживаться следующих правил: Входы изображаются на левой (или верхней) части схемы; Выходы изображаются на правой (или нижней) части схемы; Всегда, когда это возможно, элементы необходимо изображать слева направо; Проводники лучше изображать прямыми линиями, чем линиями с множеством углов (неровные рваные линии отвлекают внимание: приходится следить за тем, куда ведут провода, а не думать о том, что делает схема); Проводники всегда должны соединяться в виде буквы «Т»; Точка в месте пересечения проводников обозначает их соединение; Проводники, пересекающиеся без точки, не имеют соединения друг с другом. Три последних правила показаны на Рис. 2.24 Глава 2 Проектирование комбинационной логики 180 Любое булево уравнение в дизъюнктивной форме может быть изображено в виде принципиальной схемы с использованием систематического подхода, как показано на Рис. 2.23 . Сначала нарисуйте вертикальные проводники для входов. Поместите инверторы на соседних вертикальных линиях для получения комплементарных входов, если это необходимо. Нарисуйте горизонтальные линии, ведущие к элементам И, для каждого минтерма. Затем для каждого выхода нарисуйте элемент ИЛИ, соединенный с минтермом, соответствующим этому выходу. Такой стиль изображения называется программируемой логической матрицей (ПЛМ, PLA), потому что инверторы, элементы И и элементы ИЛИ систематически объединены в массивы. Программируемые логические матрицы будут рассмотрены в разделе 5.6 На Рис. 2.25 показана реализация упрощенного уравнения, которое мы получили при помощи булевой алгебры в Примере 2.6. Заметьте, что упрощенная схема имеет значительно меньше аппаратных элементов, Рис. 2.24 Wireconnections Глава 2 Проектирование комбинационной логики 181 чем схема на Рис. 2.23 . Также ее быстродействие может быть выше, поскольку она использует элементы с меньшим количеством входов. Мы даже можем ещё уменьшить количество элементов (пусть хотя бы на один инвертор), если воспользуемся преимуществом инвертирующих логических элементов. Заметьте, что B¯ C¯ – это элемент И с инвертированными входами. На Рис. 2.26 показана схема, которая использует эту оптимизацию для исключения инвертора на входе С. Вспомните, что согласно теореме де Моргана логический элемент И с инвертированными входами эквивалентен элементу ИЛИ-НЕ. В зависимости от технологии реализации, использование наименьшего числа элементов или использование элементов определенного типа взамен других может быть выгоднее. Например, в технологии КМОП элементы И-НЕ и ИЛИ-НЕ более предпочтительны, чем И или ИЛИ. У многих схем имеется несколько выходов, каждый из которых вычисляет независимые булевы функции для входов. Мы можем записать отдельные таблицы истинности для каждого выхода, но часто удобно записать все выходы в одну таблицу истинности и начертить одну схему для всех выходов. Глава 2 Проектирование комбинационной логики 182 Рис. 2.25 Схема реализации функции Y = B ¯ + C ¯ + AB ¯ Рис. 2.26 Схема, использующая меньше элементов Пример 2.7 СХЕМЫ С НЕСКОЛЬКИМИ ВЫХОДАМИ Декан, заведующий кафедрой, аспирант и председатель совета общежития время от времени используют одну аудиторию. К сожалению, иногда аудитория нужна им одновременно, что приводит к катастрофам, как, например, когда встреча декана с пожилыми и уважаемыми членами попечительского совета была запланирована на то же время, что и пивная вечеринка студентов общежития. Алиса Хакер была приглашена для того, чтобы разработать систему резервирования комнаты. Глава 2 Проектирование комбинационной логики 183 Система имеет четыре входа (A 3 , …, A 0 ) и четыре выхода (Y 3 , …, Y 0 ). Эти сигналы также могут быть записаны в виде A 3:0 и Y 3:0 . Каждый пользователь активирует свой вход, когда запрашивает аудиторию на следующий день. Система активирует только один выход, подтверждая пользование аудиторией самым высокоприоритетным пользователем. Декан, который оплачивает систему, требует наивысший приоритет (3). Заведующий кафедрой, аспирант и председатель совета общежития имеют приоритеты по убыванию. Запишите таблицу истинности и булевы уравнения для этой системы. Начертите схему, которая будет выполнять эту функцию. Решение: Данная функция называется четырехвходовой схемой приоритета. Её обозначение и таблица истинности показаны на Рис. 2.27 . Мы могли бы записать каждый выход в дизъюнктивной форме и упростить уравнения, используя булеву алгебру. Однако достаточно посмотреть на функциональное описание (таблицу истинности), чтобы понять, каковы могут быть упрощенные уравнения: Y 3 имеет значение ИСТИНА всегда, когда подается сигнал А 3 , таким образом Y 3 = A 3 . Y 2 равен ИСТИНЕ, если подан сигнал А 2 и не подан сигнал А 3 , таким образом Y 2 = A¯ 3 A 2 . Y 1 имеет значение ИСТИНА, если подан сигнал А 1 и ни на какой из более высокоприоритетных входов сигнал не подан: Y 1 = A¯ 3 A¯ 2 А 1 Y 0 имеет значение ИСТИНА при поданном сигнале А 0 и когда ни один из других выходов не активирован: Y 1 = A¯ 3 A¯ 2 А¯ 1 А 0 . Схема показана на Рис. 2.28 . Опытный разработчик часто может реализовать логическую схему, непосредственно глядя в исходные данные. При наличии четко заданной спецификации, просто преобразуйте слова в уравнения, а уравнения в логические элементы схемы. Глава 2 Проектирование комбинационной логики 184 Рис. 2.27 Схема приоритета Глава 2 Проектирование комбинационной логики 185 Рис. 2.28 Принципиальная схема Рис. 2.29 Таблица истинности схемы приоритета Символ «X» используется не только для обозначения переменных, чье состояние нам безразлично, но и для обозначения недопустимых состояний сигналов при симуляции логических схем (см. |