В булевой алгебре любую булеву функцию можно преобразовать в каноническую дизъюнктивную нормальную форму ( CDNF ) [1] или в минтерм-каноническую форму и ее дуальную каноническую конъюнктивную нормальную форму ( CCNF ) или в макстерм-каноническую форму . Другие канонические формы включают полную сумму простых импликант или каноническую форму Блейка (и ее двойственную), а также алгебраическую нормальную форму (также называемую Жегалкин или Рид – Мюллер).
Minterms называются продуктами, потому что они являются логическим И для набора переменных, а maxterms называются суммами, потому что они являются логическим ИЛИ для набора переменных. Эти концепции двойственны из-за их отношения дополнительной симметрии, выраженной законами Де Моргана .
Две двойственные канонические формы любой булевой функции - это «сумма minterms» и «произведение maxterms». Термин « сумма произведений » ( SoP или SOP ) широко используется для обозначения канонической формы, которая представляет собой дизъюнкцию (OR) минтермов. Его дуал Де Моргана - это « произведение сумм » ( PoS или POS ) для канонической формы, которая является конъюнкцией (И) maxterms. Эти формы могут быть полезны для упрощения этих функций, что имеет большое значение при оптимизации булевых формул в целом и цифровых схем в частности.
Минтермс
Для булевой функции от переменные , термин продукта, в котором каждый изпеременные появляются один раз (либо в дополняемой, либо в незавершенной форме), это называется минтермом . Таким образом, minterm - это логическое выражение n переменных, в котором используются только оператор дополнения и оператор конъюнкции .
Например, , а также являются 3 примерами 8 minterms для булевой функции трех переменных , , а также . Обычно последнее из них читается как AND b AND NOT-c .
Существует 2 n minterms n переменных, поскольку переменная в выражении minterm может быть либо в своей прямой, либо в дополненной форме - два варианта для каждой переменной.
Индексирование минтермов
Минтермы часто нумеруются двоичным кодированием шаблона дополнения переменных, где переменные записываются в стандартном порядке, обычно в алфавитном порядке. Это соглашение присваивает значение 1 прямой форме () и 0 к дополненному виду (); тогда минтерм. Например, mintermпронумерован 110 2 = 6 10 и обозначается.
Функциональная эквивалентность
Данный minterm n дает истинное значение (т. Е. 1) только для одной комбинации входных переменных. Например, minterm 5, a b ' c , истинно только тогда, когда a и c оба истинны, а b ложно - расположение входных данных, где a = 1, b = 0, c = 1, приводит к 1.
Учитывая таблицу истинности логической функции, можно записать функцию как «сумму произведений». Это особая форма дизъюнктивной нормальной формы . Например, если дана таблица истинности для бита арифметической суммы u логики однобитовой позиции схемы сумматора, как функция x и y от слагаемых и входящего переноса, ci :
ci | Икс | у | и (ci, x, y) |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
Заметив, что строки, которые имеют на выходе 1, являются 2-й, 3-й, 5-й и 8-й, мы можем записать u как сумму minterms а также . Если мы хотим это проверить: оцененные для всех 8 комбинаций трех переменных будут соответствовать таблице.
Maxterms
Для логической функции от n переменных, термин суммы, в котором каждая из n переменных появляется один раз (либо в своей дополненной, либо в незаполненной форме), называется maxterm . Таким образом, maxterm - это логическое выражение n переменных, в котором используются только оператор дополнения и оператор дизъюнкции . Maxterms двойственны идее minterm (т. Е. Демонстрируют дополнительную симметрию во всех отношениях). Вместо использования И и дополнений мы используем ИЛИ и дополнения и действуем аналогичным образом.
Например, следующие два из восьми maxterms трех переменных:
- а + Ь ′ + с
- а '+ Ь + с
Снова существует 2 n maxterm от n переменных, поскольку переменная в выражении maxterm также может быть либо в своей прямой, либо в дополненной форме - два варианта для каждой переменной.
Индексирование maxterms
Каждому maxterm назначается индекс, основанный на противоположном традиционном двоичном кодировании, используемом для minterms. Соглашение maxterm присваивает значение 0 прямой форме и 1 к дополненной форме . Например, мы присваиваем maxterm индекс 6.(110) и обозначим maxterm как M 6 . Аналогично M 0 этих трех переменных равно(000) и M 7 равно (111).
Функциональная эквивалентность
Очевидно, что maxterm n дает ложное значение (т. Е. 0) только для одной комбинации входных переменных. Например, maxterm 5, a ′ + b + c ′, является ложным только тогда, когда a и c оба являются истинными, а b - ложным - расположение входных данных, где a = 1, b = 0, c = 1, приводит к 0.
Если дана таблица истинности логической функции, можно записать функцию как «произведение сумм». Это особая форма конъюнктивной нормальной формы . Например, если дана таблица истинности для бита переноса co логики однобитовой позиции схемы сумматора, как функция x и y от слагаемых и переноса, ci :
ci | Икс | у | co (ci, x, y) |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Заметив, что строки с выходом 0 являются 1-й, 2-й, 3-й и 5-й, мы можем записать co как произведение maxterms а также . Если мы хотим это проверить:
оцененные для всех 8 комбинаций трех переменных будут соответствовать таблице.
Дуализация
Дополнением minterm является соответствующий maxterm. В этом легко убедиться, используя закон де Моргана . Например:
Неканонические формы PoS и SoP
Часто каноническая форма minterm может быть упрощена до эквивалентной формы SoP. Эта упрощенная форма по-прежнему будет состоять из суммы условий продукта. Однако в упрощенной форме возможно иметь меньше терминов продукта и / или терминов продукта, которые содержат меньше переменных. Например, следующая функция с тремя переменными:
а | б | c | е (а, б, в) |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
имеет каноническое представление minterm: , но имеет эквивалентную упрощенную форму: . В этом тривиальном примере очевидно, что, но в упрощенной форме меньше терминов продукта и меньше переменных.
Наиболее упрощенное представление функции SoP называется минимальной формой SoP .
Аналогичным образом каноническая форма maxterm может иметь упрощенную форму PoS.
Хотя этот пример был упрощен за счет применения обычных алгебраических методов [], в менее очевидных случаях удобный метод поиска минимальной формы PoS / SoP функции с максимум четырьмя переменными - использование карты Карно .
Минимальные формы PoS и SoP важны для поиска оптимальных реализаций логических функций и минимизации логических схем.
Пример применения
Приведенных выше примеров таблиц истинности для minterms и maxterms достаточно, чтобы установить каноническую форму для позиции одного бита при сложении двоичных чисел, но их недостаточно для разработки цифровой логики, если ваш перечень логических элементов не включает AND и OR. Там, где производительность является проблемой (как в навигационном компьютере Apollo), доступные части, скорее всего, будут NAND и NOR из-за дополняющего действия, присущего транзисторной логике. Значения определяются как состояния напряжения, одно около земли, другое около напряжения питания постоянного тока V cc , например, +5 В постоянного тока. Если более высокое напряжение определяется как «истинное» значение 1, логический элемент ИЛИ-НЕ является простейшим из возможных полезных логических элементов.
В частности, затвор ИЛИ-НЕ с 3 входами может состоять из 3 транзисторов с биполярным переходом, все эмиттеры которых заземлены, а их коллекторы связаны вместе и связаны с V cc через сопротивление нагрузки. Каждая база подключена к входному сигналу, а общая точка коллектора представляет выходной сигнал. Любой вход, который имеет 1 (высокое напряжение) на его базе, закорачивает эмиттер своего транзистора на его коллектор, заставляя ток течь через сопротивление нагрузки, что приближает напряжение коллектора (выход) к земле. Этот результат не зависит от других входных данных. Только когда все 3 входных сигнала равны 0 (низкое напряжение), импедансы эмиттер-коллектор всех 3 транзисторов остаются очень высокими. Тогда протекает очень небольшой ток, и эффект делителя напряжения с импедансом нагрузки накладывает на точку коллектора высокое напряжение, очень близкое к V cc .
Свойство дополнения этих схем вентилей может показаться недостатком при попытке реализовать функцию в канонической форме, но есть компенсирующий бонус: такой вентиль только с одним входом реализует функцию дополнения, которая часто требуется в цифровой логике.
В этом примере предполагается наличие запасных частей Apollo: только вентили NOR с 3 входами, но обсуждение упрощается, если предположить, что также доступны вентили NOR с 4 входами (в Apollo они были составлены из пар 3-входных NOR).
Канонические и неканонические последствия ворот NOR
Набор из 8 вентилей ИЛИ-НЕ, если их входные данные являются комбинациями прямых и дополнительных форм трех входных переменных ci, x и y , всегда производит minterms, никогда maxterms, то есть 8 вентилей, необходимых для обработки всех комбинаций. из 3 входных переменных только одна имеет выходное значение 1. Это потому, что вентиль ИЛИ-ИЛИ, несмотря на его название, лучше рассматривать (используя закон Де Моргана) как логическое И дополнений его входных сигналов.
Причина, по которой это не проблема, заключается в двойственности minterms и maxterm, т.е. каждый maxterm является дополнением minterm с одинаковым индексом, и наоборот.
В приведенном выше примере minterm мы написали но чтобы выполнить это с 4-входным вентилем ИЛИ-НЕ, нам нужно пересчитать его как произведение сумм (PoS), где суммы являются противоположными максимальными терминами. Это,
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
В приведенном выше примере maxterm мы написали но чтобы выполнить это с 4-входным вентилем ИЛИ-НЕ, мы должны заметить равенство ИЛИ-НЕ тех же минтермов. Это,
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Компромиссы дизайна рассматриваются в дополнение к каноническим формам
Можно было бы предположить, что работа по проектированию стадии сумматора завершена, но мы не учли тот факт, что все 3 входные переменные должны присутствовать как в прямой, так и в дополнительной форме. В этом отношении нет никаких сложностей с слагаемыми x и y , потому что они статичны на протяжении всего сложения и, таким образом, обычно удерживаются в схемах защелок, которые обычно имеют как прямой, так и дополнительный выходы. (Простейшая схема защелки, состоящая из вентилей ИЛИ-НЕ, представляет собой пару вентилей, перекрестно связанных, чтобы образовать триггер: выход каждого соединен как один из входов с другим.) Также нет необходимости создавать форму дополнения суммы u . Однако перенос одной битовой позиции должен передаваться как перенос в следующую битовую позицию как в прямой, так и в дополнительной форме. Самый простой способ сделать это - пропустить co через вентиль ИЛИ-НЕ с 1 входом и пометить выход co ', но это добавит задержку гейта в худшем из возможных мест, замедляя колебание переносов справа налево. Дополнительный вентиль ИЛИ-НЕ с четырьмя входами, создающий каноническую форму co '(из противоположных терминов co ), решает эту проблему.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Компромисс для поддержания полной скорости таким образом включает неожиданные затраты (в дополнение к необходимости использовать более крупные ворота). Если бы мы просто использовали этот вентиль с 1 входом для дополнения co , в minterm не было бы никакого смысла., и ворота, которые его породили, могли быть устранены. Тем не менее, это все еще хорошая сделка.
Теперь мы могли бы реализовать эти функции в точном соответствии с их каноническими формами SoP и PoS, превратив вентили NOR в указанные функции. Элемент ИЛИ-НЕ превращается в элемент ИЛИ, пропуская его выход через элемент ИЛИ-НЕ с 1 входом; и он превращается в логический элемент И, пропуская каждый из его входов через вентиль ИЛИ-НЕ с 1 входом. Однако этот подход не только увеличивает количество используемых вентилей, но также удваивает количество задержек вентилей, обрабатывающих сигналы, сокращая скорость обработки вдвое. Следовательно, всякий раз, когда производительность жизненно важна, стоит выйти за рамки канонических форм и использовать булеву алгебру, чтобы неусиленные вентили NOR выполняли свою работу.
Нисходящий и восходящий дизайн
Теперь мы увидели, как инструменты minterm / maxterm можно использовать для разработки каскада сумматора в канонической форме с добавлением некоторой булевой алгебры, требующей всего 2 задержки для каждого из выходов. Это нисходящий способ разработки цифровой схемы для этой функции, но лучший ли это способ? Обсуждение было сосредоточено на определении «самого быстрого» как «лучшего», и расширенная каноническая форма безупречно соответствует этому критерию, но иногда преобладают другие факторы. У проектировщика может быть основная цель минимизировать количество вентилей и / или минимизировать разветвления сигналов к другим вентилям, поскольку большие разветвления снижают устойчивость к ухудшенному источнику питания или другим факторам окружающей среды. В таком случае дизайнер может разработать дизайн канонической формы в качестве базового, затем попробовать восходящую разработку и, наконец, сравнить результаты.
Восходящая разработка включает в себя замечание, что u = ci XOR ( x XOR y ), где XOR означает исключающее ИЛИ [истинно, когда любой вход истинен, но не когда оба истинны], и что co = ci x + xy + y ci . Одна такая разработка требует всего двенадцать вентилей ИЛИ-НЕ: шесть вентилей с 2 входами и два входа с 1 входом для создания u с 5 задержками ворот, плюс три элемента с 2 входами и один вентиль с 3 входами для создания co 'с задержками 2 ворот. Для канонической базовой линии потребовалось восемь вентилей ИЛИ-НЕ с 3 входами плюс три логических элемента ИЛИ-НЕ с 4 входами для создания u, co и co 'с задержками 2 гейтов . Если инвентарь схемы действительно включает 4-входные вентили ИЛИ-НЕ, нисходящий канонический дизайн выглядит победителем как по количеству ворот, так и по скорости. Но если (вопреки нашему удобному предположению) схемы на самом деле представляют собой вентили ИЛИ-НЕ с 3 входами, из которых два требуются для каждой функции ИЛИ-НЕ с 4 входами, то канонический дизайн требует 14 вентилей по сравнению с 12 для восходящего подхода, но по-прежнему производит цифру суммы u значительно быстрее. Сравнение разветвлений представлено в виде таблицы:
Переменные | Низходящий | Вверх дном |
---|---|---|
Икс | 4 | 1 |
Икс' | 4 | 3 |
у | 4 | 1 |
y ' | 4 | 3 |
ci | 4 | 1 |
ci ' | 4 | 3 |
М или м | 4 @ 1,4 @ 2 | N / A |
x XOR y | N / A | 2 |
Разное | N / A | 5 @ 1 |
Максимум | 4 | 3 |
Описание восходящей разработки упоминает co 'как результат, но не co . Разве этот дизайн просто никогда не нуждается в прямом исполнении? Ну и да, и нет. На каждом этапе вычисление co 'зависит только от ci ', x 'и y ', что означает, что распространение переноса колеблется по позициям долота так же быстро, как и в канонической схеме, без развития co . Вычисление u , которое требует, чтобы ci было произведено из ci ′ с помощью NOR с 1 входом, происходит медленнее, но для любой длины слова конструкция выплачивает этот штраф только один раз (когда отображается крайняя левая цифра суммы). Это потому, что эти вычисления перекрываются, каждый в своем собственном небольшом конвейере, не влияя на то, когда можно вычислить итоговый бит позиции следующего бита. И, конечно же, co 'вне крайнего левого положения бита, вероятно, придется дополнить как часть логики, определяющей, не произошло ли переполнение при сложении. Но при использовании вентилей ИЛИ-НЕ с 3 входами, восходящая конструкция почти так же быстро выполняет параллельное сложение на нетривиальной длине слова, сокращает количество вентилей и использует меньшие разветвления ... так что выигрывает, если количество гейтов и / или разветвление имеют первостепенное значение!
Мы оставим точную схему восходящего дизайна, в которой все эти утверждения верны, в качестве упражнения для заинтересованного читателя, которому поможет еще одна алгебраическая формула: u = ci ( x XOR y ) + ci ′ ( x XOR y) ) ′] ′. Разделение распространения переноса от формирования суммы таким образом - это то, что повышает производительность сумматора с упреждающим переносом по сравнению с сумматором с пульсационным переносом .
Чтобы увидеть, как логика логического элемента ИЛИ-НЕ использовалась в ALU управляющего компьютера Apollo, посетите http://klabs.org/history/ech/agc_schematics/index.htm , выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указателе чертежей и разверните изображения по желанию.
Применение в проектировании цифровых схем
Одно из применений булевой алгебры - это разработка цифровых схем, одна цель - минимизировать количество вентилей, а другая - минимизировать время установления.
Существует шестнадцать возможных функций двух переменных, но в аппаратном обеспечении с цифровой логикой простейшие схемы вентилей реализуют только четыре из них: конъюнкция (И), дизъюнкция (включая ИЛИ) и соответствующие их дополнения (И-НЕ и ИЛИ-ИЛИ).
Большинство схем затвора принимают более 2 входных переменных; например, космический управляющий компьютер Apollo , который впервые применил интегральные схемы в 1960-х годах, был построен только с одним типом затвора - ИЛИ-ИЛИ с 3 входами, выход которого истинен только тогда, когда все 3 входа ложны. [2] [ необходима страница ]
Смотрите также
Рекомендации
- ^ Питер Дж. Пал; Рудольф Дамрат (2012-12-06). Математические основы вычислительной техники: Справочник . Springer Science & Business Media. С. 15–. ISBN 978-3-642-56893-0.
- ^ Холл, Элдон С. (1996). Путешествие на Луну: История Навигационного компьютера Аполлона . AIAA. ISBN 1-56347-185-X.
дальнейшее чтение
- Бендер, Эдвард А .; Уильямсон, С. Гилл (2005). Краткий курс дискретной математики . Минеола, Нью-Йорк: ISBN Dover Publications, Inc. 0-486-43946-1.
Авторы демонстрируют доказательство того, что любая булева (логическая) функция может быть выражена либо в дизъюнктивной, либо в конъюнктивной нормальной форме (см. Страницы 5–6); доказательство просто продолжается путем создания всех 2 N строк из N логических переменных и демонстрирует, что каждая строка («minterm» или «maxterm») имеет уникальное логическое выражение. Любая логическая функция от N переменных может быть получена из композиции строк, minterm или maxterm которых являются логическими единицами ("истины"). - Маккласки, EJ (1965). Введение в теорию коммутационных схем . Нью-Йорк: Книжная компания Макгроу-Хилла. п. 78. LCCN 65-17394 .
Определены и описаны канонические выражения.
- Хилл, Фредрик Дж .; Петерсон, Джеральд Р. (1974). Введение в теорию переключения и логический дизайн (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. п. 101. ISBN 0-471-39882-9.
Обозначение функций minterm и maxterm
Внешние ссылки
- Буль, Джордж (1848). Перевод Уилкинса, Дэвид Р. "Исчисление логики" . Кембриджский и Дублинский математический журнал . III : 183–198.