Каноническая нормальная форма - Canonical normal form

В Булева алгебра, любой Логическая функция можно поместить в каноническая дизъюнктивная нормальная форма (CDNF)^[1] или же минтерм каноническая форма и его двойная каноническая конъюнктивная нормальная форма (CCNF) или же каноническая форма maxterm. Другой канонические формы включать полную сумму простых импликант или Каноническая форма Блейка (и его двойник), и алгебраическая нормальная форма (также называемый Жегалкин или Рид – Мюллер).

Минтермс называются продуктами, потому что они логическое И набора переменных, и maxterms называются суммами, потому что они логическое ИЛИ набора переменных. Эти концепции двойственны из-за их взаимосвязи комплементарной симметрии, выраженной Законы де Моргана.

Две двойственные канонические формы любой Логическая функция - это «сумма minterms» и «произведение maxterms». Период, термин "Сумма продуктов" (SoP или же СОП) широко используется для канонической формы, которая представляет собой дизъюнкцию (ИЛИ) минтермов. Его Де Морган двойной это "Произведение сумм" (PoS или же POS) для канонической формы, которая является соединением (И) maxterms. Эти формы могут быть полезны для упрощения этих функций, что имеет большое значение при оптимизации булевых формул в целом и цифровых схем в частности.

Резюме

Одно из применений булевой алгебры - проектирование цифровых схем. Целью может быть минимизация количества ворот, минимизация времени установления и т. Д.

Существует шестнадцать возможных функций двух переменных, но в аппаратных средствах с цифровой логикой простейшие схемы вентилей реализуют только четыре из них: соединение (И), дизъюнкция (включая OR) и соответствующие дополнения к ним (NAND и NOR).

Большинство схем затвора принимают более 2 входных переменных; например, космический Компьютер наведения Apollo, которая впервые применила интегральные схемы в 1960-х годах, была построена только с одним типом затвора, 3-входным ИЛИ-НЕ, выход которого истинен только тогда, когда все 3 входа ложны.^{[2][страница нужна ]}

Минтермс

Для логическая функция из ${\displaystyle n}$ переменные ${\displaystyle {x_{1},\dots ,x_{n}}}$, а срок продукта в котором каждый из ${\displaystyle n}$ переменные появляются однажды (в дополненной или незавершенной форме) называется минтерм. Таким образом, минтерм является логическим выражением п переменные, которые используют только дополнять оператор и соединение оператор.

Например, ${\displaystyle abc}$, ${\displaystyle ab'c}$ и ${\displaystyle abc'}$ это 3 примера 8 minterms для булевой функции трех переменных ${\displaystyle a}$, ${\displaystyle b}$, и ${\displaystyle c}$. Обычно последнее из них читается так: а И б И НЕ-В.

Есть 2^п термины п переменных, поскольку переменная в выражении minterm может быть как в прямой, так и в дополненной форме - два варианта для каждой переменной.

Индексирование минтермов

Минтермы часто нумеруются с помощью двоичного кодирования шаблона дополнения переменных, где переменные записываются в стандартном порядке, обычно в алфавитном порядке. Это соглашение присваивает значение 1 прямой форме (${\displaystyle x_{i}}$) и 0 к дополненному виду (${\displaystyle x'_{i}}$); Минтерм тогда ${\displaystyle \sum \limits _{i=1}^{n}2^{i}\operatorname {value} (x_{i})}$. Например, minterm ${\displaystyle abc'}$ пронумерован 110₂ = 6₁₀ и обозначен ${\displaystyle m_{6}}$.

Функциональная эквивалентность

Данный минтерм п дает истинное значение (т.е. 1) только для одной комбинации входных переменных. Например, minterm 5, а б' c, верно только тогда, когда а и c оба верны и б ложно - расположение ввода, где а = 1, б = 0, c = 1 приводит к 1.

Учитывая таблица истинности логической функции можно записать функцию как «сумму произведений». Это особая форма дизъюнктивная нормальная форма. Например, если дана таблица истинности для бита арифметической суммы ты логики однобитовой позиции сумматора в зависимости от Икс и у от добавлений и переноса, 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-й, мы можем написать ты как сумма минтермов ${\displaystyle m_{1},m_{2},m_{4},}$ и ${\displaystyle m_{7}}$. Если мы хотим это проверить: ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)}$ оцененные для всех 8 комбинаций трех переменных будут соответствовать таблице.

Maxterms

Для логическая функция из п переменные ${\displaystyle {x_{1},\dots ,x_{n}}}$, сумма, в которой каждый из п переменные появляются однажды (в дополненной или неполной форме) называется maxterm. Таким образом, maxterm является логическим выражением п переменные, которые используют только дополнять оператор и дизъюнкция оператор. Maxterms двойственны идее minterm (т. Е. Демонстрируют дополнительную симметрию во всех отношениях). Вместо использования И и дополнений мы используем ИЛИ и дополнения и действуем аналогичным образом.

Например, следующие два из восьми maxterms трех переменных:

а + б′ + c

а′ + б + c

Снова 2^п maxterms из п переменных, поскольку переменная в выражении maxterm также может быть как в прямой, так и в дополненной форме - два варианта для каждой переменной.

Индексирование maxterms

Каждому maxterm назначается индекс на основе противоположного обычного двоичного кодирования, используемого для minterms. Соглашение maxterm присваивает значение 0 прямой форме ${\displaystyle (x_{i})}$ и 1 к дополненной форме ${\displaystyle (x'_{i})}$. Например, мы присваиваем maxterm индекс 6. ${\displaystyle a'+b'+c}$ (110) и обозначим maxterm как M₆. по аналогии M₀ из этих трех переменных ${\displaystyle a+b+c}$ (000) и M₇ является ${\displaystyle a'+b'+c'}$ (111).

Функциональная эквивалентность

Очевидно, что maxterm п дает ложный значение (т.е. 0) только для одной комбинации входных переменных. Например, maxterm 5, а′ + б + c′, Ложно только тогда, когда а и c оба верны и б ложно - расположение входных данных, где a = 1, b = 0, c = 1, приводит к 0.

Если дать таблица истинности логической функции можно записать функцию как «произведение сумм». Это особая форма конъюнктивная нормальная форма. Например, если дана таблица истинности для бита переноса co логики позиции одного бита сумматора в зависимости от Икс и у от добавлений и переноса, 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 ${\displaystyle M_{0},M_{1},M_{2}}$ и ${\displaystyle M_{4}}$. Если мы хотим это проверить:

${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}=(ci+x+y)(ci+x+y')(ci+x'+y)(ci'+x+y)}$

оцененные для всех 8 комбинаций трех переменных будут соответствовать таблице.

Дуализация

Дополнением к minterm является соответствующий maxterm. В этом легко убедиться, используя закон де Моргана. Например:${\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}$

Неканонические формы 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:${\displaystyle f=a'bc+abc}$, но имеет эквивалентную упрощенную форму:${\displaystyle f=bc}$В этом тривиальном примере очевидно, что ${\displaystyle bc=a'bc+abc}$, но в упрощенной форме меньше терминов продукта и меньше переменных. Наиболее упрощенное представление функции SoP называется минимальная форма SoP.

Аналогичным образом каноническая форма maxterm может иметь упрощенную форму PoS.

Хотя этот пример можно легко упростить, применив обычные алгебраические методы [${\displaystyle f=(a'+a)bc}$], в менее очевидных случаях удобный метод поиска минимальной формы 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

Факт №1: набор из 8 вентилей ИЛИ-НЕ, если все их входы являются комбинациями прямой и дополнительной форм трех входных переменных. ci, x, и у, всегда производят minterms, никогда maxterms - то есть из 8 вентилей, необходимых для обработки всех комбинаций 3 входных переменных, только один имеет выходное значение 1. Это потому, что вентиль ИЛИ-НЕ, несмотря на его имя, мог бы лучше просматриваться (используя De Закон Моргана) как логическое И дополнений его входных сигналов.

Факт №2: причина, по которой факт №1 не является проблемой, заключается в двойственности minterm и maxterm, т.е. каждый maxterm является дополнением minterm с одинаковым индексом, и наоборот.

В приведенном выше примере minterm мы написали ${\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}}$ но чтобы выполнить это с 4-входным вентилем ИЛИ-НЕ, нам нужно пересчитать его как произведение сумм (PoS), где суммы являются противоположными максимальными терминами. То есть,

${\displaystyle u(ci,x,y)=\mathrm {AND} (M_{0},M_{3},M_{5},M_{6})=\mathrm {NOR} (m_{0},m_{3},m_{5},m_{6}).}$

Таблицы истинности

ci Икс у M0 M3 M5 M6 И и (ci, x, y) 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1

ci Икс у м0 м3 м5 м6 НИ и (ci, x, y) 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1

В приведенном выше примере maxterm мы написали ${\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}$ но чтобы выполнить это с 4-входным вентилем ИЛИ-НЕ, нам нужно заметить равенство ИЛИ-НЕ тех же самых minterms. То есть,

${\displaystyle co(ci,x,y)=\mathrm {AND} (M_{0},M_{1},M_{2},M_{4})=\mathrm {NOR} (m_{0},m_{1},m_{2},m_{4}).}$

Таблицы истинности

ci Икс у M0 M1 M2 M4 И co (ci, x, y) 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

ci Икс у м0 м1 м2 м4 НИ co (ci, x, y) 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1

Компромиссы дизайна учитываются в дополнение к каноническим формам

Можно было бы предположить, что работа по проектированию этапа сумматора завершена, но мы не учли тот факт, что все 3 входные переменные должны присутствовать как в прямой, так и в дополнительной форме. С дополнениями нет никаких сложностей Икс и у в этом отношении, потому что они статичны на протяжении всего сложения и, таким образом, обычно удерживаются в схемах защелок, которые обычно имеют как прямой, так и дополнительный выходы. (Простейшая схема защелки, состоящая из вентилей ИЛИ-НЕ, представляет собой пару вентилей, перекрестно связанных, чтобы образовать триггер: выход каждого соединен как один из входов с другим.) Также нет необходимости создавать форму дополнения суммы ты. Однако перенос одной битовой позиции должен передаваться как перенос в следующую битовую позицию как в прямой, так и в дополнительной форме. Самый простой способ сделать это - передать co через вентиль ИЛИ-НЕ с 1 входом и пометьте выход co′, Но это добавило бы задержку ворот в худшем из возможных мест, замедляя колебания переносов справа налево. Дополнительный 4-входной вентиль ИЛИ-НЕ, создающий каноническую форму co′ (Из противоположных минтермов как co) решает эту проблему.

${\displaystyle co'(ci,x,y)=\mathrm {AND} (M_{3},M_{5},M_{6},M_{7})=\mathrm {NOR} (m_{3},m_{5},m_{6},m_{7}).}$

Таблицы истинности

ci Икс у M3 M5 M6 M7 И co '(ci, x, y) 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0

ci Икс у м3 м5 м6 м7 НИ co '(ci, x, y) 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0

Компромисс для поддержания полной скорости таким образом включает неожиданные затраты (в дополнение к необходимости использовать более крупные ворота). Если бы мы просто использовали этот вентиль с 1 входом для дополнения co, минтерм был бы бесполезен ${\displaystyle m_{7}}$, и ворота, которые его породили, могли быть устранены. Тем не менее, это по-прежнему хорошая сделка.

Теперь мы могли бы реализовать эти функции в точном соответствии с их каноническими формами SoP и PoS, превратив вентили NOR в указанные функции. Элемент ИЛИ-НЕ превращается в элемент ИЛИ, пропуская его выход через вентиль ИЛИ-НЕ с 1 входом; и он превращается в логический элемент И, пропуская каждый из его входов через вентиль ИЛИ-НЕ с 1 входом. Однако этот подход не только увеличивает количество используемых вентилей, но также удваивает количество задержек вентилей, обрабатывающих сигналы, сокращая скорость обработки вдвое. Следовательно, всякий раз, когда производительность жизненно важна, стоит выйти за рамки канонических форм и выполнить булеву алгебру, чтобы неулучшенные вентили NOR выполняли свою работу.

Нисходящий и восходящий дизайн

Теперь мы увидели, как инструменты minterm / maxterm могут быть использованы для разработки каскада сумматора в канонической форме с добавлением некоторой булевой алгебры, требующей всего 2 задержки гейта для каждого из выходов. Это нисходящий способ разработать цифровую схему для этой функции, но лучший ли это способ? Обсуждение было сосредоточено на определении «самого быстрого» как «лучшего», и расширенная каноническая форма безупречно соответствует этому критерию, но иногда преобладают другие факторы. У проектировщика может быть основная цель минимизировать количество ворот и / или минимизировать разветвления сигналов к другим воротам, поскольку большие разветвления снижают устойчивость к ухудшенному источнику питания или другим факторам окружающей среды. В таком случае дизайнер может разработать дизайн в канонической форме в качестве основы, затем попробовать разработку снизу вверх и, наконец, сравнить результаты.

Развитие снизу вверх предполагает замечание, что u = ci XOR (Икс XOR у), где XOR означает исключающее ИЛИ [истина, когда любой вход верен, но не когда оба верны], и что co = ci x + х у + y ci. Для одного такого развития требуется двенадцать вентилей ИЛИ-НЕ: шесть вентилей с 2 ​​входами и два шлюза с 1 входом для создания ты с 5 задержками ворот, плюс три затвора с 2 входами и один вентиль с 3 входами для получения co′ В 2 задержки ворот. Для создания канонической базовой линии потребовалось восемь вентилей ИЛИ-НЕ с 3 входами плюс три логических элемента ИЛИ-НЕ с 4 входами. ты, компания и co′ В 2 задержки ворот. Если инвентарь схемы на самом деле включает в себя вентили ИЛИ-НЕ с 4 входами, нисходящий канонический дизайн выглядит победителем как по количеству ворот, так и по скорости. Но если (вопреки нашему удобному предположению) схемы на самом деле представляют собой вентили ИЛИ-НЕ с 3 входами, из которых два требуются для каждой функции ИЛИ-НЕ с 4 входами, то канонический дизайн требует 14 вентилей по сравнению с 12 для восходящего подхода, но по-прежнему производит цифру суммы ты значительно быстрее. Сравнение разветвлений представлено в виде таблицы:

Переменные	Сверху вниз	Вверх дном
Икс	4	1
Икс'	4	3
у	4	1
y '	4	3
ci	4	1
ci '	4	3
М или м	4@1,4@2	Нет данных
x XOR y	Нет данных	2
Разное	Нет данных	5@1
Максимум	4	3

Что делать лицу, принимающему решение? Наблюдательный человек заметит, что в описании восходящего развития упоминается co′ Как выход, но не co. Неужели этот дизайн просто никогда не нуждается в прямом исполнении? Ну да и нет. На каждом этапе производится расчет co'Зависит только от ci′, Икс' и у′, Что означает, что распространение переноса колеблется по позициям долота так же быстро, как в канонической конструкции, без каких-либо изменений co. Расчет ты, что требует ci быть изготовленным из ci′ При использовании NOR с 1 входом, работает медленнее, но для любой длины слова дизайн платит этот штраф только один раз (когда отображается крайняя левая цифра суммы). Это потому, что эти вычисления перекрываются, каждый в своем собственном небольшом конвейере, не влияя на то, когда может быть вычислен бит суммы следующей битовой позиции. И, конечно же, co'Вне крайнего левого бита, вероятно, придется дополнить как часть логики, определяющей, переполнено ли добавление. Но при использовании вентилей ИЛИ-ИЛИ с 3 входами, восходящая конструкция почти так же быстро выполняет параллельное сложение на нетривиальной длине слова, сокращает количество вентилей и использует меньшие разветвления ... так что выигрывает, если количество гейтов и / или разветвление имеют первостепенное значение!

Мы оставим точную схему восходящего проектирования, в которой все эти утверждения верны, в качестве упражнения для заинтересованного читателя, которому поможет еще одна алгебраическая формула: ты = ci(Икс XOR у) + ci′(Икс XOR у) ′] ′. Разделение распространения переноса и формирования суммы таким образом - вот что повышает производительность сумматор с упреждением по сравнению с гадюка.

Чтобы увидеть, как логика ворот NOR использовалась в ALU компьютера управления Apollo, посетите http://klabs.org/history/ech/agc_schematics/index.htm, выберите любую из записей 4-БИТНОГО МОДУЛЯ в Указателе чертежей и при необходимости разверните изображения.

Смотрите также

• Список тем по булевой алгебре

Рекомендации

1. Питер Дж. Пал; Рудольф Дамрат (2012-12-06). Математические основы вычислительной техники: справочник. Springer Science & Business Media. С. 15–. ISBN  978-3-642-56893-0.
2. Холл, Элдон С. (1996). Путешествие на Луну: история навигационного компьютера Apollo. AIAA. ISBN  1-56347-185-X.

дальнейшее чтение

• Бендер, Эдвард А .; Уильямсон, С. Гилл (2005). Краткий курс дискретной математики. Минеола, Нью-Йорк: Dover Publications, Inc. ISBN  0-486-43946-1.
  Авторы демонстрируют доказательство того, что любая булева (логическая) функция может быть выражена либо в дизъюнктивной, либо в конъюнктивной нормальной форме (см. Стр. 5–6); доказательство просто продолжается созданием всех 2^N ряды N Логические переменные и демонстрирует, что каждая строка («minterm» или «maxterm») имеет уникальное логическое выражение. Любая логическая функция N переменные могут быть получены из комбинации строк, minterm или maxterm которых являются логическими единицами ("истины")
• Маккласки, Э. Дж. (1965). Введение в теорию коммутационных схем. Нью-Йорк: Книжная компания Макгроу-Хилла. п. 78. LCCN  65-17394. Определены и описаны канонические выражения.
• Хилл, Фредрик Дж .; Петерсон, Джеральд Р. (1974). Введение в теорию переключения и логический дизайн (2-е изд.). Нью-Йорк: Джон Уайли и сыновья. п. 101. ISBN  0-471-39882-9. Обозначение функций minterm и maxterm

внешняя ссылка

• Буль, Джордж (1848). Перевод Уилкинса, Дэвид Р. «Исчисление логики». Кембриджский и Дублинский математический журнал. III: 183–198.