2.1. Лекция. Проектирование комбинационной логики 1Введени 2Булевы уравнения
 Скачать 2.3 Mb.
|
|
Раздел 2.6.1 ). Старайтесь понять из контекста, о каком варианте использования идет речь. Чтобы избежать такой двусмысленности, некоторые авторы используют символы «D» или «?» для обозначения сигналов, состояние которых нам безразлично. Обратите внимание, что если в схеме приоритета подается сигнал А 3 , то выходы схемы не будут зависеть от того, какие сигналы присутствуют на остальных входах. Мы используем символ Х для описания состояния входов, которые нам безразличны, так как не оказывают влияния на выход. На Рис. 2.29 показано, что таблица Глава 2 Проектирование комбинационной логики 186 истинности четырехвходовой приоритетной схемы становится гораздо меньше, если убрать значения входов, которыми можно пренебречь. Из этой таблицы истинности мы можем легко получить булевы уравнения в дизъюнктивной форме, опуская входы с Х. Значения, которыми можно пренебречь, также могут возникнуть на выходах в таблице истинности, как мы увидим в разделе 2.7.3 2.5 МНОГОУРОВНЕВАЯ КОМБИНАЦИОННАЯ ЛОГИКА Комбинационная логика, построенная как дизъюнкция конъюнкций (сумма произведений), называется двухуровневой, потому что состоит из литералов, соединенных с элементами И (образующими первый уровень), выходы которых соединены с элементами ИЛИ (образующими второй уровень). Разработчики часто создают схемы с большим числом уровней логических элементов. Такая многоуровневая комбинационная схема может использовать меньше логических элементов, чем ее двухуровневая реализация. Эквивалентные преобразования по законам де Моргана и перемещение инверсии особенно полезны при анализе и разработке многоуровневых схем. Глава 2 Проектирование комбинационной логики 187 2.5.1 Минимизация аппаратуры Некоторые логические функции требуют огромного количества аппаратуры, если строить их с использованием двухуровневой логики. Показательный пример – это функция ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR) нескольких переменных. Например, рассмотрим построение трехвходового элемента XOR, используя двухуровневую технику, которую мы изучали до сих пор. Вспомним, что N-входовой XOR выдает на выход значение ИСТИНА, если нечетное число входных операндов имеют значение ИСТИНА. На Рис. 2.30 (a) показана таблица истинности трехвходового элемента XOR. В таблице обведены строки, для которых значение выхода будет ИСТИНА. Из таблицы истинности мы понимаем форму логического выражения, соответствующую дизъюнкции конъюнкций (сумме произведений) уравнения (2.6) . К сожалению, это выражение невозможно упростить в меньшее количество импликант. Y = A¯ B C¯ + A¯ BC¯ + AB¯ C¯ + ABC (2.6) С другой стороны, A ⊕ B ⊕ C = (A ⊕ B) ⊕ C (если вы сомневаетесь, докажите это самостоятельно с помощью совершенной индукции). Следовательно, трехвходовой элемент XOR можно реализовать каскадом двухвходовых элементов XOR, как показано на Рис. 2.31 Глава 2 Проектирование комбинационной логики 188 Рис. 2.30 Трехвходовой элемент XOR: функциональная спецификация (a) и реализация с двумя уровнями логики (b) Аналогично, восьмивходовой XOR потребует 128 восьмивходовых элементов И и одного 128-входового элемента ИЛИ для двухуровневой реализации дизъюнкции конъюнкций. Гораздо лучшей альтернативой будет использовать дерево двухвходовых элементов XOR, как показано на Рис. 2.32 Глава 2 Проектирование комбинационной логики 189 Рис. 2.31 Трехвходовой элемент XOR, собранный из двух двухвходовых элементов XOR Рис. 2.32 Восьмивходовой элемент XOR, собранный из семи двухвходовых Выбор наилучшей многоуровневой реализации заданной логической функции – это непростой процесс (выбирать наилучшую многоуровневую реализацию заданной логической функции непросто). Кроме того, «наилучшее» имеет много значений: наименьшее количество элементов, лучшее быстродействие, кратчайшее время разработки, наименьшая стоимость, наименьшее энергопотребление. В главе 5 вы увидите, что «наилучшая» схема для одной технологии не обязательно является наилучшей для другой. Например, мы использовали элементы И и ИЛИ, но для КМОП-технологии более эффективны элементы И-НЕ и ИЛИ-НЕ. С опытом, вы увидите, что для Глава 2 Проектирование комбинационной логики 190 большинства схем вы сможете находить хорошую многоуровневую реализацию, просто рассматривая эти схемы (и действуя по интуиции). Некоторый опыт вы наработаете, изучая примеры схем остальной части книги. По мере того, как вы учитесь, исследуйте различные варианты разработки и думайте о компромиссах. Сейчас также доступны системы автоматизированного проектирования (САПР), которые позволяют рассматривать огромное пространство возможных многоуровневых реализаций (осуществлять поиск в многомерном пространстве решений) и находить такое, которое наилучшим образом удовлетворяет вашим критериям оптимальности с учетом имеющихся строительных блоков. 2.5.2 Перемещение инверсии Как вы помните из раздела 1.7.6 для КМОП-схем лучше подходят элементы И-НЕ и ИЛИ-НЕ, а не И и ИЛИ. Однако чтение уравнений многоуровневых схем с элементами И-НЕ и ИЛИ-НЕ может оказаться довольно трудным. На Рис. 2.33 показан пример многоуровневой схемы, функция которой не очевидна непосредственно из схемы. Путем перемещения инверсии можно преобразовать подобные схемы так, что инверсия сократится, и функция может стать более понятной. Построенные на принципах из раздела 2.3.3 , правила для перемещения инверсии таковы: Глава 2 Проектирование комбинационной логики 191 Начинайте с выхода цепи и двигайтесь назад к входам. Переместите инверсию с общего выхода на входы так, чтобы вы могли читать выражение в терминах выхода (например, Y), а не инвертированного выхода Y¯ . Продвигаясь в обратном направлении, меняйте каждый элемент так, чтобы число инверсий оказалось четным и их можно было сократить. Если текущий элемент имеет входные отрицания, рисуйте предшествующий элемент с выходным отрицанием. Если текущий элемент не имеет входного отрицания, рисуйте предшествующий элемент без выходного отрицания. Рис. 2.33 Многоуровневая схема на элементах И-НЕ и ИЛИ-НЕ Рис. 2.34 показывает, как перерисовать схему из Рис. 2.33 , следуя изложенным правилам. Начинаем с выхода Y. Элемент И-НЕ имеет отрицание на выходе, которое мы хотим устранить. Мы переставляем выходное отрицание «назад», формируя элемент И с инверсными Глава 2 Проектирование комбинационной логики 192 входами, показанный на Рис. 2.34 (a) . Двигаясь налево по схеме, мы замечаем, что самый правый элемент теперь имеет входное отрицание, которое может быть отброшено вместе с выходным отрицанием среднего элемента И-НЕ так, что инверсий в этом пути не останется, как показано на Рис. 2.34 (b) . Средний элемент не имеет входных инверсий, поэтому мы трансформируем самый левый элемент так, чтобы он не имел выходного отрицания, как показано на Рис. 2.34 (c) Сейчас все отрицания в схеме убраны, за исключением входов, так что функция может быть прочитана в терминах элементов И и ИЛИ с действительными или комплементарными входами: Y = A¯ B¯ C + D¯ . Чтобы подчеркнуть этот последний пункт, на Рис. 2.35 показана схема, логически эквивалентная схеме на Рис. 2.34 . Функции внутренних соединений отмечены синим цветом. Поскольку последовательные отрицания могут быть отброшены, мы можем игнорировать инверсии на выходе среднего и на входе самого правого элементов, получив логически эквивалентную схему на Рис. 2.35 Глава 2 Проектирование комбинационной логики 193 Рис. 2.34 Схема с удаленными инверсиями Глава 2 Проектирование комбинационной логики 194 Рис. 2.35 Логически эквивалентная схема Пример 2.8 ПЕРЕМЕЩЕНИЕ ИНВЕРСИИ В КМОП-ЛОГИКЕ Большинство разработчиков думают в терминах элементов И и ИЛИ, но предположим, что вы хотели бы реализовать схему из Рис. 2.36 в КМОП-логике, для которой предпочтительны элементы И-НЕ и ИЛИ-НЕ. Используйте перемещение инверсии, чтобы преобразовать схему в элементы И-НЕ, ИЛИ-НЕ и НЕ. Решение: прямолинейное решение заключается в простой замене каждого элемента И на И-НЕ с инвертором, а каждого элемента И – на И-НЕ с инвертором, как это показано на Рис. 2.37 . Такая схема потребует 8 элементов. Заметьте, что инверторы изображены с отрицанием на входе, а не на выходе, чтобы подчеркнуть, что последовательное двойное отрицание не меняет логику работы схемы и может быть отброшено. Обратите внимание, что отрицания могут быть добавлены на выход элемента и на вход следующего элемента без изменения функции, как показано на Рис. 2.38 (a) . Выходной элемент И преобразовывается в элемент И-НЕ и инвертор, как показано на Рис. 2.38 (b) . Это решение требует только пять элементов. Глава 2 Проектирование комбинационной логики 195 Рис. 2.36 Схема на элементах И и ИЛИ Рис. 2.37 Плохая схема на элементах И-НЕ и ИЛИ-НЕ Рис. 2.38 Улучшенная схема на элементах И-НЕ и ИЛИ-НЕ Глава 2 Проектирование комбинационной логики 196 2.6 ЧТО ЗА X И Z? Булева алгебра ограничена значениями 0 и 1. Однако реальные схемы могут также иметь недопустимое и плавающее состояния, представляемые символами X и Z соответственно. 2.6.1 Недопустимое значение: Х Символ X обозначает неизвестное логическое значение или недопустимое значение физического напряжения в соединении, не соответствующее уровням логических 0 и 1. Это обычно происходит, если к соединению подключены выходы других элементов схемы, выдающие значения 0 и 1 одновременно. На Рис. 2.39 показан такой случай, когда выход Y подключен к элементам, имеющим на выходе ВЫСОКИЙ и НИЗКИЙ уровни. Рис. 2.39 Схема с недопустимым значением на выходе Эта ситуация, называемая состязанием или конфликтом (contention), считается ошибкой, и её необходимо избегать. Реальное (физическое) напряжение на выходе с конфликтом может быть где-то между нулем и Глава 2 Проектирование комбинационной логики 197 напряжением питания, в зависимости от соотношения мощностей элементов, выдающих в цепь ВЫСОКОЕ и НИЗКОЕ напряжения. Часто, но не всегда, значение напряжения оказывается в «запрещенной» зоне. Состязание также может стать причиной повышенного потребления энергии конфликтующими элементами, в результате чего схема нагревается и может быть повреждена. Значение X также иногда используется программами моделирования для обозначения неинициализированного значения. Например, если вы забыли определить входное значение, симулятор присвоит ему значение X для того, чтобы предупредить вас о проблеме. Как уже упоминалось в разделе 2.4 , разработчики цифровых схем также используют символ X для обозначения в таблицах истинности безразличных переменных, от которых не зависит состояние выходов. Не путайте эти два смысла. Когда X появляется в таблицах истинности, он показывает, что значение этой переменной может быть и нулем, и единицей. Когда X появляется в схеме, это означает, что цепь имеет неизвестное или запрещенное значение. Глава 2 Проектирование комбинационной логики 198 2.6.2 Третье состояние: Z Символ Z указывает, что напряжение в цепи не определяется ни источником ВЫСОКОГО, ни источником НИЗКОГО напряжения. Говорят, что такая цепь отключена, находится в состоянии высокого импеданса или в третьем состоянии. Типично неправильное представление – это что неподключенная, или плавающая цепь имеет значение логического 0. В реальности логическое состояние неподключенной цепи может быть как 0, так и 1, а напряжение на ней может принять некое промежуточное значение в зависимости от истории изменения состояния системы. Неподключенная цепь не обязательно означает наличие ошибки в схеме. Например, какой-нибудь другой элемент схемы может задать цепи допустимый логический уровень именно в тот момент, когда эта цепь влияет на работу схемы. Один из распространенных способов получить неопределенное значение – это забыть подключить вход схемы к источнику напряжения логического уровня или предположить, что неподключенный вход – то же самое, что вход со значением 0. Эта ошибка может привести к тому, что поведение цепи будет хаотичным, так как неопределенные значения на входе могут случайно меняться из 0 в 1. Действительно, касания схемы может быть достаточно, чтобы привести к изменению из- за слабого статического электричества тела. Мы видели схему, которая Глава 2 Проектирование комбинационной логики 199 корректно работала, только до тех пор, пока студент держал палец на микросхеме. Буфер с тремя состояниями, показанный на Рис. 2.40 , имеет три возможных выходных значения: ВЫСОКОЕ (1), НИЗКОЕ (0) и отключенное или плавающее (Z) состояние (прим. переводчика: именно поэтому плавающее состояние называют третьим). Буфер с тремя состояниями имеет вход A, выход Y и сигнал управления E. Когда сигнал разрешения (управления) имеет значение ИСТИНА, буфер с тремя состояниями работает как простой буфер, передавая входное значение на выход. Когда сигнал управления имеет значение ЛОЖЬ, выход буфера переключается в третье состояние и становится плавающим (Z). Буфер с тремя состояниями на Рис. 2.40 имеет активный высокий уровень. Это значит, что когда сигнал разрешения ВЫСОКИЙ (1), передача разрешена. На Рис. 2.41 показан Буфер с тремя состояниями с активным низким уровнем. Когда сигнал управления НИЗКИЙ (0), передача разрешена. Мы видим, что сигнал имеет активный низкий уровень из-за отрицания, поставленного на его входной цепи. Мы часто обозначаем вход с активным низким уровнем, рисуя черточку (символ отрицания) над его именем (E¯ ), или добавляя букву "b" или "bar" после имени, Eb или Ebar. Глава 2 Проектирование комбинационной логики 200 Рис. 2.40 Буфер с тремя состояниями Рис. 2.41 Буфер с тремя состояниями с активным низким уровнем Буферы с третьим состоянием обычно используются в шинах, соединяющих несколько микросхем. Например, микропроцессор, видеоконтроллер и Ethernet-контроллер могут нуждаться во взаимодействии с подсистемой памяти в персональном компьютере. Каждая микросхема может подключаться к общей шине памяти, используя буферы с третьим состоянием, как показано на Рис. 2.42 При этом только одна микросхема имеет право выставить свой сигнал разрешения, чтобы выдать значение на шину. Выходы других микросхем должны находиться в третьем состоянии, чтобы не стать причиной коллизии с микросхемой, осуществляющей обмен данными с Глава 2 Проектирование комбинационной логики 201 памятью. Однако, любая микросхема может читать информацию с общей шины в любое время. Такие шины на основе буферов с тремя состояниями когда-то были очень распространенными. Однако, в современных компьютерах высочайшие скорости возможны только при соединении микросхем друг с другом напрямую (point-to-point), а не с помощью общей шины. Рис. 2.42 Шина с третьим состоянием, соединяющая несколько микросхем Глава 2 Проектирование комбинационной логики 202 2.7 КАРТЫ КАРНО После того, как Вы осуществите несколько преобразований по минимизации булевых уравнений, используя булеву алгебру, Вы поймете, что без соблюдения должной аккуратности, иногда можно получить решение, совершенно отличное от требуемого упрощенного уравнения. Карты Карно представляют собой наглядный метод для упрощения булевых уравнений. Они были изобретены в 1953-м году Морисом Карно, телекоммуникационным инженером из фирмы Bell Labs. Карты Карно очень удобны в случаях, когда уравнение содержит до четырёх переменных. Но, что более важно, они дают понимание сути при манипулировании логическими выражениями. Морис Карно родился в 1924 году. Получил степень бакалавра по физике в Городском колледже Нью-Йорка в 1948 году, а в 1952 получил степень доктора философии по физике (Ph.D., аналог степени кандидата наук) в Йельском университете. С 1952 по 1993 годы работал в Bell Labs и IBM. С 1980 по 1999 год являлся профессором информатики в Политехническом университете Нью-Йорка. Как мы помним, логическая минимизация осуществляется путем склейки термов. Два терма, включающие в себя импликанту P и два логических значения некоторой переменной A, объединяются, при этом Глава 2 Проектирование комбинационной логики 203 переменная A исключается. Карты Карно позволяют легко находить термы, которые можно склеить, располагая их в виде таблицы. На Рис. 2.43 показана таблица истинности и карта Карно для функции трех переменных. Верхняя строка дает 4 возможных значения для переменных A и B. Левая колонка дает 2 возможных значения переменной C. Каждая клетка карты Карно соответствует строке таблицы истинности и содержит значение функции Y из этой строки. Например, верхняя левая клетка соответствует первой строке таблицы истинности и показывает, что значение функции Y будет равно 1, когда ABC=000. Как и каждая строка в таблице истинности, каждая клетка карты Карно представляет собой отдельный минтерм. Для лучшего понимания, на Рис. 2.43 (с) показаны минтермы, соответствующие каждой клетке карты Карно. Каждая клетка, или минтерм, отличается от соседней изменением только одной переменной. Это значит, что соседние клетки различаются только в значении одного литерала, значение которого «истинно» в одной клетке и «ложно» в соседней. Например, клетки, представляющие минтермы A¯ B¯ C¯ и A¯ B¯ C – соседние и различается только в переменной C. Вы, наверное, также отметили, что переменные A и B комбинируются в верхней строке в особом порядке: 00, 01, 11, 10. Этот порядок называется кодом Грея (Gray code). В отличие от битового порядка по возрастанию величины (00, 01, 10, 11), в коде Грея Глава 2 Проектирование комбинационной логики 204 соседние записи отличаются только на один разряд. Например, 01 : 11 отличается только изменением A с 0 на 1, тогда как 01 : 10 требует изменения A из 1 в 0 и B из 0 в 1. Таким образом, обычный последовательный побитный порядок не дает требуемого нам свойства соседних ячеек, который должны различаться только в одной переменной. Код Грея был запатентован Фрэнком Греем, исследователем из Bell Labs, в 1953 году (патент США номер 2,632,058). Этот код особенно полезен для электромеханических преобразователей (например, датчиков угла поворота – прим. переводчика), так как он позволяет избавиться от ложных срабатываний. Код грея может быть любой разрядности. Например, трехбитный код Грея выглядит так: 000, 001, 011, 010, 110, 111, 101, 100. Льюис Кэрролл опубликовал похожую загадку в журнале Vanity Fair в 1879 году.«Правила просты. Даны два слова одинаковой длины. Нужно соединить их цепочкой слов, в которой два соседних слова отличаются лишь одной буквой» – написал он. Например, слово SHIP можно превратить в слово DOCK так: SHIP, SLIP, SLOP, SLOT, SOOT, LOOT, LOOK, LOCK, DOCK. Можете ли вы найти более короткую цепочку? Карты Карно так же «закольцованы». Клетка с самого правого края таблицы является соседней с самой левой, так как они отличаются Глава 2 Проектирование комбинационной логики 205 только в одной переменной (A). Можно свернуть карту в цилиндр, соединив края, и даже в этом случае соседние клетки также будут отличаться только в одной переменной. 2.7.1 Думайте об овалах На карте Карно на Рис. 2.43 содержится только две единицы, что соответствует числу минтермов в уравнении (A¯ B¯ C¯ и A¯ B¯ C). Чтение минтермов из карт Карно в точности соответствует чтению дизъюнктивной нормальной формы (ДНФ) из таблицы истинности. Рис. 2.43 Функция трех переменных: таблица истинности (a), карта Карно (b), карта Карно с минтермами (c) Глава 2 Проектирование комбинационной логики 206 Как и раньше, мы могли бы использовать булеву алгебру для минимизации: Y = A¯ B¯ C¯ + A¯ B¯ C + A¯ B¯ (C¯ + C) = A¯ B¯ (2.7) Рис. 2.44 Минимизация при помощи карты Карно Карты Карно помогают нам делать это упрощение графически, обводя единицы в соседних клетках овалами, как показано на Рис. 2.44 . Для каждого овала мы пишем соответствующую ему импликанту. Вспомните из раздела 2.2 , что импликанта является произведением одного или нескольких литералов. Переменные, для которых прямая и комплементарная формы попадают в один овал, исключаются из импликанты. В нашем случае обе формы переменной C попадают в овал, так что мы не включаем ее в импликанту. Другими словами, Y = ИСТИНА когда A = B = 0 вне зависимости от C. Так что импликантой Глава 2 Проектирование комбинационной логики 207 будет A¯ B¯ : карта Карно дает тот же самый ответ, какой мы получили, используя булеву алгебру. 2.7.2 Логическая минимизация на картах Карно Карты Карно обеспечивают простой визуальный способ минимизации логических выражений. Просто обведите все прямоугольные блоки с единицами на карте, используя наименьшее возможное число овалов. Каждый овал должен быть максимально большим. Затем прочитайте все импликанты, которые обведены. Напомним, что формально уравнения булевой алгебры являются минимальными, только когда записаны как сумма наименьшего числа первичных импликант. Каждый овал на карте Карно представляет собой импликанту. Максимально возможный овал является первичной импликантой. Например, на карте Карно на Рис. 2.44 A¯ B¯ C¯ и A¯ B¯ C импликанты, но не первичные. На этой карте только A¯ B¯ является первичной импликантой. Правила для нахождения минимального уравнения из карт Карно следующие: Использовать меньше всего овалов, необходимых для покрытия всех 1; Глава 2 Проектирование комбинационной логики 208 Все клетки в каждом овале обязаны содержать 1; Каждый овал должен охватывать блок, число клеток которого в каждом направлении равно степени двойки (то есть 1, 2 или 4); Каждый овал должен настолько большим, насколько это возможно; Овал может связывать края карты Карно; Единица на карте Карно может быть обведена сколько угодно раз, если это позволяет уменьшить число овалов, которые будут использоваться. Пример 2.9 МИНИМИЗАЦИЯ ФУНКЦИИ ТРЕХ ПЕРЕМЕННЫХ ПРИ ПОМОЩИ КАРТЫ КАРНО Предположим, у нас есть функция Y = F (A, B, C) с картой Карно, показанной на Рис. 2.45 . Упростим это выражение, используя карту Карно. Решение: Обведем единицы на карте Карно, используя наименьшее возможное количество овалов, как показано на Рис. 2.46 . Каждый овал на карте Карно представляет собой первичную импликанту, а его размер кратен степени двойки (2 × 1 и 2 × 2). Мы сформируем первичную импликанту для каждого выделенного овала, выписывая только те переменные, которые появляются в нем только в прямой или в комплементарной формах. Например, овал размером 2 × 1 включает в себя прямую и комплементарную формы переменной B, так что мы не включаем Глава 2 Проектирование комбинационной логики 209 B в первичную импликанту. Однако, в этом овале есть только прямая форма переменной A (A¯ ) и комплементарная форма переменной C (C¯ ), так что мы включаем эти переменные в первичную импликанту A (A¯ ). Подобным же образом овал размером 2 × 2 покрывает все клетки, где B = 0, так что первичная импликанта будет B¯ . Обратите внимание, что правая верхняя клетка (минтерм) используется дважды, чтобы сделать овалы первичных импликант как можно большими. Как мы видели в булевой алгебре, это эквивалентно совместному использованию минтерма для уменьшения размера импликанты. Также обратите внимание на то, что овал, покрывающий четыре клетки, оборачивается через края карты Карно. Рис. 2.45 Карта Карно для примера 2.9 Рис. 2.46 Рис. 2.46 Решение примера 2.9 Глава 2 Проектирование комбинационной логики 210 Пример 2.10 ДЕШИФРАТОР СЕМИСЕГМЕНТНОГО ИНДИКАТОРА Дешифратор семисегментного индикатора получает на вход четырехбитные данные D[3:0] и формирует семь выходов для управления светодиодами для показа цифр от 0 до 9. Семь выходов часто называют сегментами от a до g, или S a –S g , как показано на Рис. 2.47 . Сами цифры показаны на Рис. 2.48 . Составим таблицу истинности для выходов и используем карты Карно для нахождения логического уравнения для выходов S a и S b . При этом предположим, что запрещенные входные значения (10-15) ничего не выводят на индикатор. Рис. 2.47 Семисегментный индикатор Глава 2 Проектирование комбинационной логики 211 Рис. 2.48 Цифры на семисегментном индикаторе Решение: Таблица истинности дана в Табл. 2.1 Например, вход 0000 должен включать все сегменты, за исключением S g Табл. 2.6 Таблица истинности дешифратора семисегментного индикатора D 3:0 S a S b S c S d S e S f S g 0000 1 1 1 1 1 1 0 0001 0 1 1 0 0 0 0 0010 1 1 0 1 1 0 1 0011 1 1 1 1 0 0 1 0100 0 1 1 0 0 1 1 0101 1 0 1 1 0 1 1 0110 1 0 1 1 1 1 1 0111 1 1 1 0 0 0 0 1000 1 1 1 1 1 1 1 1001 1 1 1 0 0 1 1 Прочие 0 0 0 0 0 0 0 Глава 2 Проектирование комбинационной логики 212 Каждый из семи выходов является независимой функцией от четырех переменных. Карты Карно для выходов S a и S b показаны на Рис. 2.49 . Помните, что соседние клетки могут отличаться только одной переменной, так что мы промаркируем строки и столбцы в коде Грея: 00, 01, 11, 10. Будьте осторожны и помните этот порядок, когда будете вписывать значения выходов в клетки. Рис. 2.49 Карты Карно для S a и S b Затем обведем первичные импликанты. При этом используем минимально необходимое количество овалов для покрытия всех единиц. Овалы могут связывать края (вертикальные и горизонтальные), а каждая единица может быть выделена несколько раз. На Рис. 2.50 показаны первичные импликанты и упрощенные логические уравнения. Глава 2 Проектирование комбинационной логики 213 Рис. 2.50 Решение упражнения 2.10 Заметьте, что минимальный набор первичных импликант – не единственно возможный. Например, запись 0000 на карте Карно для S a может быть выделена вместе с записью 1000, получая минтерм D¯ 2 D¯ 1 D¯ 0 . Но вместо этого овал может включать в себя запись 0010, получая минтерм D¯ 3 D¯ 2 D¯ 0 , как показано пунктирной линией на Рис. 2.51 Рис. 2.52 иллюстрирует распространенную ошибку, когда не первичная импликанта выбирается для покрытия 1 в левом верхнем углу. Этот минтерм D¯ 3 D¯ 2 D¯ 1 D¯ 0 дает дизъюнкцию конъюнкций (сумму произведений), которая не минимизирована. Его можно было бы скомбинировать с любым из двух соседних Глава 2 Проектирование комбинационной логики 214 минтермов для получения овала большего размера, как было сделано на предыдущих двух рисунках. Рис. 2.51 Альтернативная карта Карно для S a , использующая другой набор первичных импликант Рис. 2.52 Карта Карно для S a , использующая некорректную импликанту Глава 2 Проектирование комбинационной логики 215 2.7.3 Безразличные переменные Вспомните, что безразличные переменные в таблице истинности были введены в разделе 2.4 для уменьшения числа ее строк в тех случаях, когда соответствующие переменные не влияют на выход. Они обозначаются символом X, который означает, что значение входной переменной может быть или 0, или 1. Не только входы, но и выходы могут быть безразличными, если состояние выхода не важно или соответствующая комбинация входов никогда не возникает. Такие выходы могут трактоваться или как 0, или как 1, в зависимости от того, как решит разработчик. В картах Карно безразличные переменные позволяют провести еще большую логическую минимизацию. Их можно включать в овалы, если это помогает покрыть единицы или меньшим количеством овалом, или овалами, большими по размеру, но их можно и не покрывать, если это не помогает минимизации. Пример 2.11 ДЕШИФРАТОР СЕМИСЕГМЕНТНОГО ИНДИКАТОРА С БЕЗРАЗЛИЧНЫМИ ПЕРЕМЕННЫМИ Повторим пример 2.10 для случая, когда нас не интересуют значения выходов при запрещенных входных значениях от 10 до 15. Глава 2 Проектирование комбинационной логики 216 Решение: Карта Карно с безразличными элементами, отмеченными как «X», представлена на Рис. 2.53 . Поскольку такие элементы могут быть равны как 0, так и 1, мы используем их там, где это поможет покрыть единицы или меньшим количеством овалов, или овалами, большими по размеру. Обведенные значения X трактуются как 1, не обведенные – как 0. Посмотрите, как для сегмента S a можно выделить овал размером 2 × 2, объединяющий все четыре угла. Используйте клетки с безразличными значениями для упрощения логики. Рис. 2.53 Карта Карно с безразличными переменными Глава 2 Проектирование комбинационной логики 217 2.7.4 Подводя итоги Булева алгебра и карты Карно – два метода логического упрощения. В конечном счете, целью является нахождение наименее затратного метода реализации конкретной логической функции. В современной инженерной практике компьютерные программы, называемые синтезаторами логики (logic synthesizers), проводят упрощение схем по описанию логический функций, как мы увидим в главе 4 . Для больших задач программы логического синтеза намного эффективнее людей. Для маленьких же задач человек с некоторым опытом может найти хорошее решение «на глаз». Никто из авторов книги, тем не менее, никогда не использовал карты Карно в реальной жизни для решения практических задач. Но понимание принципов, лежащих в основе карт Карно, крайне важно. Кроме того, знание карт Карно часто спрашивают на собеседованиях! Глава 2 Проектирование комбинационной логики 218 2.8 БАЗОВЫЕ КОМБИНАЦИОННЫЕ БЛОКИ Комбинационные логические элементы часто группируются в «строительные блоки», используемые для создания сложных систем. Это позволяет абстрагироваться от излишней детализации уровня логических элементов и подчеркнуть функцию «строительного блока». Мы уже изучили три таких блока: полный сумматор (см. |