В булевой алгебре любая булева функция может быть выражена в канонической дизъюнктивной нормальной форме ( CDNF ) [1] или минтермной канонической форме , а также в двойственной ей канонической конъюнктивной нормальной форме ( CCNF ) или макстермной канонической форме . Другие канонические формы включают полную сумму простых импликант или каноническую форму Блейка (и двойственную ей форму) и алгебраическую нормальную форму (также называемую Жегалкиным или Ридом – Мюллером).
Минтермы называются продуктами, потому что они представляют собой логическое «И» для набора переменных, а макстермы называются суммами, потому что они представляют собой логическое «ИЛИ» для набора переменных. Эти концепции двойственны из-за их взаимодополняющей симметрии, выраженной законами Де Моргана .
Две двойственные канонические формы любой булевой функции — это «сумма минтермов» и «произведение макстермов». Термин « Сумма произведений » ( SoP или SOP ) широко используется для обозначения канонической формы, которая представляет собой дизъюнкцию (ИЛИ) минтермов. Его двойник Де Моргана — это « Произведение сумм » ( PoS или POS ) для канонической формы, которая представляет собой соединение (И) максимальных терминов. Эти формы могут быть полезны для упрощения этих функций, что имеет большое значение при оптимизации булевых формул вообще и цифровых схем в частности.
Для булевой функции переменных термин- продукт , в котором каждая из переменных встречается один раз (либо в дополненной, либо в недополненной форме), называется минтермом . Таким образом, минтерм — это логическое выражение n переменных, в котором используются только оператор дополнения и оператор соединения .
Например, и являются 3 примерами 8 минтермов для булевой функции трех переменных , и . Обычное чтение последнего из них — a AND b AND NOT-c .
Существует 2 n минтермов из n переменных, поскольку переменная в выражении минтерма может быть либо в прямой, либо в дополненной форме — два варианта выбора для каждой переменной.
Минтермы часто нумеруются с помощью двоичной кодировки образца дополнения переменных, где переменные записываются в стандартном порядке, обычно в алфавитном порядке. Это соглашение присваивает значение 1 прямой форме ( ) и 0 — дополненной форме ( ); тогда минтерм . Например, минтерм имеет номер 110 2 = 6 10 и обозначается .
Данный минтерм n дает истинное значение (т. е. 1) только для одной комбинации входных переменных. Например, минтерм 5, a b ' c , является истинным только тогда, когда a и c оба истинны, а b является ложным — расположение входных данных, где a = 1, b = 0, c = 1, приводит к 1.
Учитывая таблицу истинности логической функции, можно записать функцию как «сумму произведений». Это особая форма дизъюнктивной нормальной формы . Например, если дана таблица истинности для арифметической суммы бита u логики позиции одного бита сумматорной схемы, как функция x и y от слагаемых и переноса, ci :
Заметив, что строки с выходным значением 1 — это 2-я, 3-я, 5-я и 8-я строки, мы можем записать u как сумму минтермов и . Если мы хотим это проверить: оценка всех 8 комбинаций трех переменных будет соответствовать таблице.
Для логической функции от n переменных термин суммы, в котором каждая из n переменных встречается один раз (либо в дополненной, либо в недополненной форме), называется maxterm . Таким образом, макстерм — это логическое выражение n переменных, в котором используются только оператор дополнения и оператор дизъюнкции . Макстермы представляют собой двойственную идею минтерма (т. е. демонстрируют дополнительную симметрию во всех отношениях). Вместо использования AND и дополнений мы используем OR и дополнения и действуем аналогичным образом.
Например, ниже приведены два из восьми максимальных терминов трех переменных:
Снова имеется 2 n maxterms из n переменных, поскольку переменная в выражении maxterm также может быть либо в прямой, либо в дополненной форме — два варианта выбора для каждой переменной.
Каждому макстерму присваивается индекс, основанный на противоположной традиционной двоичной кодировке, используемой для минтермов. Соглашение maxterm присваивает значение 0 прямой форме и 1 — дополненной форме . Например, мы присваиваем индекс 6 maxterm (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 :
Заметив, что строки с выходным значением 0 — это 1-я, 2-я, 3-я и 5-я строки, мы можем записать co как произведение maxterms и . Если мы хотим это проверить:
оцененное для всех 8 комбинаций трех переменных, будет соответствовать таблице.
Дополнением минтерма является соответствующий макстерм. В этом легко убедиться, воспользовавшись законом де Моргана . Например:
Часто каноническую форму минтерма можно упростить до эквивалентной формы SoP. Эта упрощенная форма по-прежнему будет состоять из суммы условий продукта. Однако в упрощенной форме возможно иметь меньше терминов продукта и/или терминов продукта, которые содержат меньше переменных. Например, следующая функция с тремя переменными:
имеет каноническое представление минтерма: , но имеет эквивалентную упрощенную форму: . В этом тривиальном примере очевидно, что , но в упрощенной форме меньше терминов-продуктов, а сам термин имеет меньше переменных.
Наиболее упрощенное представление функции SoP называется минимальной формой SoP .
Аналогично, каноническая форма maxterm может иметь упрощенную форму PoS.
Хотя этот пример был упрощен за счет применения обычных алгебраических методов [ ], в менее очевидных случаях удобным методом нахождения минимальной формы PoS/SoP функции с числом до четырех переменных является использование карты Карно .
Минимальные формы PoS и SoP важны для поиска оптимальных реализаций логических функций и минимизации логических схем.
Приведенные выше примеры таблиц истинности для минтермов и макстерммов достаточны для установления канонической формы для однобитовой позиции при сложении двоичных чисел, но недостаточны для разработки цифровой логики, если ваш инвентарь вентилей не включает И и ИЛИ. Там, где производительность является проблемой (как в управляющем компьютере Apollo), доступными частями, скорее всего, будут NAND и NOR из-за дополняющего действия, присущего транзисторной логике. Значения определяются как состояния напряжения: одно около земли, другое около напряжения питания постоянного тока V cc , например +5 В постоянного тока. Если более высокое напряжение определяется как «истинное» значение 1, логический элемент ИЛИ-НЕ является самым простым и полезным логическим элементом.
В частности, вентиль ИЛИ-НЕ с 3 входами может состоять из 3 биполярных переходных транзисторов, все эмиттеры которых заземлены, а коллекторы соединены вместе и связаны с V cc через сопротивление нагрузки. Каждая база подключена к входному сигналу, а точка общего коллектора представляет выходной сигнал. Любой вход, который имеет значение 1 (высокое напряжение) по отношению к своей базе, замыкает эмиттер транзистора на коллектор, вызывая протекание тока через сопротивление нагрузки, что приводит к тому, что напряжение коллектора (выход) становится очень близким к земле. Этот результат не зависит от других входных данных. Только когда все три входных сигнала равны 0 (низкое напряжение), импедансы эмиттер-коллектор всех трех транзисторов остаются очень высокими. Тогда ток течет очень мало, и эффект делителя напряжения с сопротивлением нагрузки налагает на точку коллектора высокое напряжение, очень близкое к V cc .
Дополняющее свойство этих вентильных схем может показаться недостатком при попытке реализовать функцию в канонической форме, но есть компенсирующий бонус: такой вентиль только с одним входом реализует дополняющую функцию, которая часто требуется в цифровой логике.
В этом примере предполагается наличие запасных частей Apollo: только вентили NOR с 3 входами, но обсуждение упрощается, если предположить, что также доступны вентили NOR с 4 входами (в Apollo они были составлены из пар вентилей NOR с 3 входами).
Набор из 8 вентилей ИЛИ-НЕ, если их входные данные представляют собой все комбинации прямых и дополнительных форм трех входных переменных ci, x и y , всегда создают минтермы, а не макстермы, то есть из 8 вентилей, необходимых для обработки всех комбинаций. из трех входных переменных только одна имеет выходное значение 1. Это потому, что вентиль ИЛИ-НЕ, несмотря на его название, лучше рассматривать (используя закон Де Моргана) как И дополнений его входных сигналов.
Причина, по которой это не является проблемой, заключается в двойственности минтермов и макстермов, т. е. каждый макстерм является дополнением минтерма с аналогичным индексом, и наоборот.
В приведенном выше примере минтерма мы написали, но чтобы выполнить это с помощью вентиля ИЛИ-НЕ с 4 входами, нам нужно переформулировать его как произведение сумм (PoS), где суммы являются противоположными максимальными термомами. То есть,
В примере с maxterm выше мы написали, но чтобы выполнить это с 4-входовым вентилем NOR, нам нужно заметить равенство NOR тех же minterms. То есть,
Можно было бы предположить, что работа по проектированию сумматора на этом завершена, но мы не учли тот факт, что все три входные переменные должны присутствовать как в прямой, так и в дополнительной форме. В этом отношении нет никаких сложностей с слагаемыми x и y , поскольку они статичны на протяжении всего сложения и, таким образом, обычно удерживаются в схемах-защелках, которые обычно имеют как прямой, так и дополняющий выходы. (Простейшая схема-защелка, состоящая из вентилей ИЛИ-НЕ, представляет собой пару вентилей, перекрестно связанных в триггер: выход каждого подключен как один из входов к другому.) Также нет необходимости создавать дополнительную форму. суммы u . Однако перенос одной битовой позиции должен передаваться как перенос в следующую битовую позицию как в прямой, так и в дополнительной форме. Самый простой способ сделать это — пропустить co через вентиль ИЛИ-НЕ с 1 входом и пометить выход co ', но это добавит задержку вентиля в худшем возможном месте, замедляя пульсацию переносов справа налево. Дополнительный вентиль ИЛИ-НЕ с 4 входами, создающий каноническую форму co ′ (из противоположных минтермов, таких как co ), решает эту проблему.
Компромисс для поддержания полной скорости таким образом включает в себя неожиданные затраты (помимо необходимости использовать ворота большего размера). Если бы мы просто использовали этот вентиль с 1 входом для дополнения co , минтерм был бы бесполезен , и вентиль, который его сгенерировал, можно было бы устранить. Тем не менее, это по-прежнему хорошая сделка.
Теперь мы могли бы реализовать эти функции точно в соответствии с их каноническими формами 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 значительно быстрее. Сравнение разветвлений представлено в таблице:
В описании развития снизу вверх в качестве результата упоминается co ′, но не co . Неужели этот дизайн просто никогда не нуждается в прямой форме выполнения? Ну и да и нет. На каждом этапе вычисление co ′ зависит только от ci ′, x ′ и y ′, что означает, что распространение переноса колеблется вдоль битовых позиций так же быстро, как и в каноническом проекте, без какого-либо развития co . Вычисление u , которое действительно требует, чтобы ci было сделано из ci ' с помощью NOR с 1 входом, происходит медленнее, но для любой длины слова схема платит этот штраф только один раз (когда появляется самая левая цифра суммы). Это связано с тем, что эти вычисления перекрываются, каждый в своем маленьком конвейере, не влияя на то, когда может быть вычислен суммарный бит следующей битовой позиции. И конечно, co ' из крайней левой позиции бита, вероятно, придется дополнить как часть логики, определяющей, произошло ли сложение. Но при использовании вентилей ИЛИ-НЕ с 3 входами схема «снизу вверх» почти так же быстро выполняет параллельное сложение при нетривиальной длине слова, сокращает количество вентилей и использует меньшие разветвления... так что она выигрывает, если количество вентилей и/или разветвление имеют первостепенное значение!
Мы оставим точную схему восходящей схемы, в которой все эти утверждения верны, в качестве упражнения для заинтересованного читателя, опираясь на еще одну алгебраическую формулу: u = ci ( x XOR y ) + ci ′( x XOR y )']'. Такое отделение распространения переноса от формирования суммы повышает производительность сумматора с упреждающим переносом по сравнению с сумматором со пульсирующим переносом .
Одним из применений булевой алгебры является проектирование цифровых схем, цель которого – минимизировать количество вентилей, а другая – минимизировать время установления.
Существует шестнадцать возможных функций двух переменных, но в цифровых логических аппаратах простейшие вентильные схемы реализуют только четыре из них: конъюнкцию (И), дизъюнкцию (включающее ИЛИ) и соответствующие дополнения к ним (И-НЕ и ИЛИ-НЕ).
Большинство вентильных схем принимают более двух входных переменных; например, космический управляющий компьютер «Аполлон» , который стал пионером в применении интегральных схем в 1960-х годах, был построен только с одним типом вентиля, ИЛИ-НЕ с тремя входами, выходной сигнал которого истинен только тогда, когда все три входа ложны. [2] [ нужна страница ] [3]
Чтобы увидеть, как логика вентиля ИЛИ использовалась в АЛУ управляющего компьютера Apollo, выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указатель чертежей и разверните изображения по желанию.
Авторы демонстрируют доказательство того, что любая булева (логическая) функция может быть выражена как в дизъюнктивной, так и в конъюнктивной нормальной форме (см. стр. 5–6); доказательство просто продолжается путем создания всех 2 N строк из N логических переменных и демонстрирует, что каждая строка («минтерм» или «максимтер») имеет уникальное логическое выражение. Любая булева функция от N переменных может быть получена из совокупности строк, минимальный или максимальный термин которых равен логическим единицам («истина»).
Канонические выражения определены и описаны
Обозначение функций Minterm и maxterm
