В ряде программ синтеза комбинационных схем реализуются алгоритмы, совокупность которых соответствует классическому методу Квайна-Мак-Класки или его модификациям. В этом методе синтез нацелен на получение схем минимальной сложности. При этом сложность оценивается числом используемых логических элементов или суммарным числом входов этих элементов.
В синтезе комбинационных схем используются следующие понятия и определения.
элементарная конъюнкцияконъюнкция входных для схемы переменных и (или) их отрицаний;
дизъюнктивная нормальная форма (ДНФ) логической функции переменных — представление функции в виде дизъюнкции конечного числа элементарных конъюнкций (аналогично конъюнктивная нормальная форма — конъюнкция элементарных дизъюнкций);
конституента единицы — элементарная конъюнкция, в которую входят все входных переменных (в прямом или инверсном виде);
совершенная ДНФ (ДСНФ) — ДНФ, в которой все элементарные конъюнкции являются конституентами единицы;
простая импликанта — конъюнкция, упрощение которой в составе ДНФ логической функции путем исключения какой-либо переменной невозможно без потери правильности отображения заданной функции с помощью этой ДНФ;
сокращенная ДНФ (СДНФ) —ДНФ, в которую входят только простые импликанты;
минимальная ДНФ (МДНФ) — ДНФ, состоящая из минимально возможного числа вхождений в нее переменных или их отрицаний (числа букв);
тупиковая СДНФ — СДНФ, в которой нет ни одной лишней импликанты, т. е. такой импликанты, наличие которой не сказывается на значениях функции.
Конъюнктивная нормальная форма (КНФ) логической функции я переменных — представление этой функции в виде конъюнкции конечного числа элементарных дизъюнкций. Разновидности КНФ (совершенная, сокращенная, тупиковая, минимальная) определяются аналогично соответствующим разновидностям ДНФ.
Использование ДНФ и КНФ ориентировано на синтез комбинационных схем из логических элементов И, ИЛИ, НЕ с последующим возможным переходом в другие базисы, например, И—НЕ, ИЛИ—НЕ. Возможно использование знака Шеффера или стрелки Пирса, ориентированных на непосредственный синтез в базисах И—НЕ или ИЛИ—НЕ.
В таблице истинности, отображающей логическую функцию , имеется столбцов по числу аргументов , один столбец для функции и строк по числу комбинаций значений аргументов. Каждая строка, в которой , порождает одну конституенту единицы в совершенной ДНФ функции . Эта конституента состоит из переменных , имеющих в этой строке значения , и из отрицаний переменных, имеющих в этой строке .
В методе Квайна-Мак-Класки полученную из таблицы истинности ДСНФ преобразуют в МДНФ в требуемом элементном базисе с учетом ограничений на коэффициенты нагружения и разветвления. Коэффициент нагружения определяется числом букв в элементарной конъюнкции, а коэффициент разветвления — числом конъюнкций в ДНФ. Если ограничения нарушены, то выполняют факторизацию — разделение конъюнкции (дизъюнкции) на части с объявлением каждой части промежуточной переменной и выполнением операции конъюнкции (дизъюнкции) над промежуточными переменными. Переход к заданному базису И-НЕ или ИЛИ-НЕ осуществляется добавлением цепочек из двух последовательно включенных элементов НЕ во входные цепи схемы. После этого заменяя элементы НЕ-ИЛИ на элементы И-НЕ (или элементы НЕ-И на элементы ИЛИ-НЕ), переходят к заданному базису.
Например, синтез одновыходных комбинационных автоматов по методу Квайна — Мак-Класки включает следующие процедуры:
1) запись логической функции в ДСНФ;
2) преобразование ДСНФ в СДНФ на основе операции склеивания;
3) получение тупиковых СДНФ и выбор среди них МДНФ;
4) получение минимальной формы функции в заданном элементном базисе с учетом ограничений выбранной системы элементов; основу этой процедуры составляет факторизация — выделение факторов.
Фактором называют некоторое логическое выражение, которое целесообразно выделить в записи функции и объявить промежуточной переменной. Следовательно, в синтезируемой схеме появится фрагмент, выходом которого будет эта промежуточная переменная. Факторизация преследует следующие цели: 1) выполнение реальных ограничений на коэффициенты разветвления и нагружения логических элементов; 2) получение скобочной формы, уменьшающей сложность представления логической функции по сравнению с МДНФ (для этого необходимо найти факторы, встречающиеся в записи функции более одного раза, и вынести их за скобку); 3) минимизация сложности многовыходных комбинационных автоматов, заключающаяся в однократной реализации факторов, общих для различных функций автомата.
Наряду с методом Квайна — Мак-Класки находит применение метод Блека — Порецкого, использование которого может оказаться более предпочтительным, если исходная функция задана в виде, затрудняющем переход к ДСНФ.
Синтез многовыходных комбинационных автоматов возможен как синтез одновыходных автоматов, где — число выходов. Однако получаемые решения при этом оказываются неоптимальными. Поэтому важной процедурой синтеза многовыходных схем является факторизация.
Получение СДНФ заключается в выполнении операции склеивания
V = , (1)
где и — логические переменные. В качестве может фигурировать любая конъюнкция переменных. Следовательно, основу алгоритма получения СДНФ должен составлять поиск склеиваемых импликант с их преобразованием по (1).
Процедура поиска переборная. Для сокращения перебора все конституенты располагаются в порядке увеличения числа единиц в наборах переменных, отображаемых этими конституентами. Конституенты с одинаковым числом единиц считаются относящимися к одной группе. При поиске склеиваемых конституент рассматриваются не все возможные паросочетания конституент, а только сочетания конституент из разных соседних групп. Результаты склеивания образуют список импликант, над которым выполняются такие же операции упорядочения, поиска и склеивания импликант, как и над исходным списком конституент. Процедура продолжается, пока не останется склеиваемых импликант. Искомая СДНФ представляет собой совокупность таких импликант из исходного и всех образующихся списков, которые не участвовали в операциях склеивания.
Пример 1
Задана функция четырех аргументов ,...,. В табл. 1 указаны наборы значений аргументов, соответствующие конституентам единицы. Эти конституенты сгруппированы: 1; 2 и 3; 4 и 5; 6. Результаты .склеивания конституент даны в табл. 2.
Следующий шаг процедуры приводит к получению табл. 3 и оказывается последним. Искомая СДНФ имеет вид
= V (2)
Таблица 1    
Номер конституенты
11111
21101
31110
41100
50110
60010

Таблица 2    
Номера склеиваемых конституент
1,211-1
1,3111-
2,4110-
3,411-0
3,5-110
5,60-10

Таблица 3    
11--
11--
-110
0-10

Тупиковые ДНФ могут быть получены из таблицы покрытий, в которой для каждой конституенты из ДСНФ отводится одна строка, а для каждой простой «импликанты из СДНФ — один столбец. Элемент таблицы покрытий равен I. если -я импликанта покрывает (поглощает) -ю конституенту, иначе =0. Тупиковую ДНФ образуют импликанты тех столбцов, которые в совокупности имеют единицы во всех строках таблицы покрытий, причем исключение любой импликанты нарушает это условие. Функциям с большим числом аргументов соответствует большое число тупиковых ДНФ, такое, что полный их перебор с целью выделения МДНФ становится нереальным.
Поэтому используются приближенные алгоритмы получения МДНФ. К ним относится минимаксный алгоритм, в соответствии с которым включение импликант в МДНФ выполняется в следующей последовательности: выбирается строка таблицы покрытий с наименьшим числом единиц и среди столбцов, имеющих в этой строке единицы, выбирается столбец с наибольшим числом единиц. Импликанта этого столбца включается в МДНФ, а все конституенты, покрываемые этой импликантой, а, следовательно, и соответствующие им строки, вычеркиваются.
Процедура повторяется до тех пор, пока остаются невычеркнутые строки.
Пример 2
Таблица покрытий для функции (2) имеет вид табл. 4. В соответствии с минимаксным алгоритмом получаем МДНФ
=
Таблица 4    
Конституенты единицы
1 1 1 11  
1 1 0 11  
1 1 1 011 
1 1 0 01  
0 1 1 0-11
0 0 1 0- 1

Применение алгоритмов синтеза, связанных с построением ДСНФ реализуемых функций, затруднительно в практических задачах большой размерности. Невозможность применения точных алгоритмов оптимизации (такие алгоритмы имеют экспоненциальную сложность) и громоздкость промежуточных описаний обусловливают в ряде программ логического синтеза отказ от выполнения минимизации булевых функций по методу Квайна—Мак-Клаоки. В этих программах используют непосредственный синтез схем по первоначальным формам представления функций.
Первоначальными формами представления функций при синтезе комбинационных схем являются две таблицы, содержащие данные о ФВВ: 1) таблица интервалов с 2 столбцами, соответствующими входным переменным и их инверсным значениям; 2) таблица ФВВ (таблица функций) с столбцами, соответствующими реализуемым функциям. В этих таблицах выделяются строк, соответствующих элементарным конъюнкциям (интервалам), фигурирующим в ДНФ реализуемых функций. Если элемент таблицы интервалов равен 1, то -я переменная входит в -ю конъюнкцию, при =0 -я переменная в конъюнкцию не входит.
Алгоритм синтеза включает процедуры факторизации, синтеза в элементах И, ИЛИ и перехода к реальной элементной базе.
Факторизация используется для учета реальных ограничений на нагрузочные способности полюсов входных и внутренних переменных и на коэффициенты разветвления конъюнкторов. Эти ограничения эквивалентны ограничениям на число единиц в столбцах и строках матрицы интервалов соответственно. Если в -м столбце обнаружено нарушение заданного ограничения, то этот столбец расщепляется на два столбца с вынесением из старого столбца в новый единиц и с добавлением новой строки с единицей на пересечении со старым столбцом, где — максимально допустимое число единиц в столбце. Аналогично устраняются нарушения ограничений в строках таблицы интервалов, а также нарушения ограничений на коэффициенты нагружения конъюнкторов и коэффициенты разветвления дизъюнкторов, определяемые по числу единиц в строках и столбцах матрицы функций.
Синтез логической схемы из элементов И, ИЛИ осуществляется непосредственно по таблицам интервалов и ФВВ: каждая строка таблицы интервалов соответствует одному конъюнктору, а каждая строка таблицы функций — одному дизъюнктору.
Переход к реальной элементной базе проводится в условиях ограничений на состав возможных элементов. В большинстве систем логического проектирования допустимы элементы И—НЕ и (или) ИЛИ—НЕ с заданными нагрузочной способностью и числом входов. Алгоритм перехода основан на предварительном включении в каждое ребро графового представления исходной схемы, состоящей из элементов И, ИЛИ, пары вершин, соответствующих элементам НЕ (вершин типа НЕ). Далее осуществляется поочередная замена элементов И, ИЛИ на элементы выбранного типа И—НЕ, ИЛИ—НЕ. Для этого выбирается подграф, имеющий одну вершину типа И или ИЛИ с таким числом смежных вершин типа НЕ, которое делает справедливой замену подграфа на вершину типа И—НЕ или ИЛИ—НЕ. После замены всех вершин типа И, ИЛИ из графа исключаются сохранившиеся пары вершин типа НЕ. Итоговый граф дает искомую схему. В процессе перехода к реальной элементной базе проверяется соблюдение ограничений на число входов и нагрузочную способность элементов.