<< Пред. стр. 5 (из 7) След. >>
Список литературы по разделу
v
v
v
v
v
v
v
3. Нахождение существенных импликант. Если в каком-либо из столбцов составленной таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантол. Существенная импликанта не может быть исключена из правой части (2.42), так как без нее не будет получено покрытие всего множества Т, данной функции. Поэтому из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы миннтермов, покрываемых этими существенными импликантами.
Пример 2.8 (продолжение). Для нашей функции существенной импликантой является
Она покрывает минитермы , , , . При переходе к следующему этапу эти минитермы могут быть вычеркнуты.
4. Вычеркивание лишних столбцов. Исследуется таблица, полученная после третьего этапа. Если в ней есть два столбца, в которых имеются метки в одинаковых строках, то один из них вычеркивается. Это можно сделать в силу того, что покрытие оставшегося столбца будет осуществлять покрытие выброшенного минитерма.
Пример 2.8 (продолжение). После вычеркиваний существенной импликанты и минитермов, которые она покрывает, таблица меток принимает вид:
v
v
v
v
v
v
v
v
В данном случае одинаковых столбцов нет.
5. Вычеркивание лишних первичных импликант. Если после выбрасывания некоторых столбцов на четвертом этапе в таблице появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейших рассмотрений, так как они не покрывают оставшиеся в рассмотрении минитермы.
6. Выбор минимального покрытия максимальными интервалами. Исследуется полученная таблица. Выбирается такая совокупность первичных импликат, которая включает метки во всех столбцах (по крайней мере, по одной метке в каждом столбце). При нескольких возможных вариантах такого выбора отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах, образующих покрытие.
Пример 2.8 (о к о н ч а н и e). Для рассматриваемой функции выбираем покрытие из импликант и , так как они совместно покрывают все оставшиеся после четвертого этапа минитермы. Минимальная ДНФ для этой функции имеет вид:
f (x1, х2, х3, х4) = v v .
Пример 2.9 Найти минимальную формулу для функции
f (x1, х2, х3, х4) = .
Составляем первичные импликаторы.
Минитермы 4-го ранга:
Минитсрмы 3-ro ранга:
Минитермы 2-го ранга:
.
Составляем таблицу меток
v v
v v
v
v v
v
Первичные импликанты являются существенными. Эти существенные импликанты покрывают все множество Т, для данной функции. Таким образом, МДНФ этой функции есть
f (x1, х2, х3, х4) = .
В методе Квайна есть одно существенное неудобство. Оно связано с необходимостью полного попарного сравнения на этапе нахождения простых импликант, С росиэм числа минитермов, определяющих СДНФ данной функции, растет число этих сравнений. Поэтому при достаточно болыпом числе минитермов применение метода Квайна становится затруднительным. В 1956 г. Мак — Класки предложил модернизацию первого этапа метода Квайна, дающего существенное уменьшение числа сравнений минитермов.
Идея Мак-Класки заключается в следующем. Если записать минитермы в виде их двоичных номеров, то все номера можно разбить по числу единиц в этих номерах на непересекающиеся группы. При этом в i-ю группу войдут все номера, имеющие в своей двоичной записи ровно i единиц. Попарное сравнение можно производить только между соседними по номеру группами, так как только эти группы отличаются для входящих в них минитермов в одном разряде. При образовании минитермов с рангом выше нулевого в разряды, соответствующие исключенным переменным, пишется знак "тире". Такая модификация, кроме того, на практике чрезвычайно удобна, так как позволяет избсжать выписывания громоздких минитермов и импликант, заменяя эту процедуру выписыванием их двоичных номеров.
Пример 2.10 Функция задана в СДНФ минитермамн с номерами 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15. Запишем эти минитермы по группам в двоичном коде.
Нулевая группа: 0000*.
Первая группа: 0001*, 0010*, 0100* 1000*.
Вторая группа: 0011*,0110*,1001*.
Третья группа: 0111*, 1011*.
Четвёртая группа: 1111*
Сравнивая соседние группы, получаем по группам минитермы 3-го ранга:
Нулевая группа: 000 —* , 00 — 0*, 0 — 00*, — 000*.
Первая группа: 00 — 1*, — 001*, 001 — *, 0 — 10*, 01 — 0*, 100 — *.
Вторая группа: 0 — 11*, — 011*,011 — *, 10 — 1*.
Третья группа: — 111*, 1 — 11*.
Теперь находим минитермы 2-го рога:
Нулевая группа: 00 — —, — 00 —, 0 — — О.
Первая группа: — 0 — 1, 0 — 1 —.
Вторая группа: — — 11.
Составляем таблицу меток
0000 0001 0010 0011 0100 0110 0111 1000 1001 1011 1111
00- -
-00-
0- -0
-0-1
0-1-
- -11 v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
v
Дальнейшая минимизация по методу Мак-Класки совпадает с минимизацией по методу Квайна. Для рассматриваемой функции минимальная ДНФ имеет следующий вид:
f (x1, х2, х3, х4) = .
С. Петрик предложил использовать таблицу покрытия для решения задачи нахождения всех тупиковых ДНФ заданной функции, из которых путем анализа их сложности можно выбрать минимальную ДНФ. Сущность метода Петрика состоит в следующем. По таблице покрытий Квайна — Мак-Класки строится конъюнкция дизъюнкций, каждая из которых есть совокупность тех импликант, которые в данном столбце имеют метки (число дизъюнкцнй в конъюнкции равно числу столбцов таблицы покрытий). После этого происходит раскрытие скобок с учетом свойства поглощения. Каждая конъюнкция в полученном после этого выражении соответствует некоторой тупиковой ДНФ рассматриваемой функции. Пусть, например, таблица покрытий некоторой f (x1, х2, х3, х4) имеет вид:
Обозначение Импликанты 0000 0011 0101 0110 0111 1011 1101 1110
A
B
C
D - - 11
- 1 – 1
- 11 –
000 -
v v
v
v
v
v
v
v
v
v
Отсюда (D)(A)(B)(C)(A v B v С)(А)(В)(С) ? ABCD и у функции f существует только одна тупиковая ДНФ (конечно, совпадающая с МДНФ)
f = А v В v С v D = .
Метод Блека-Порецкого
Недостатком рассмотренных методов минимизации является то, что для их применения необходимо, чтобы минимизируемся функция была представлена в СДНФ. Процесс такого представления для функций с большим числом аргументов зачастую является весьма громоздкой задачей. Например, если функция f задана в виде ДНФ
f (x1 , x2, хЗ, х4, х5 ) =
и требуется минимизировать эту функцию, то предварительно надо выписать СДНФ этой функции, состоящую из 18 минитермов.
Желательно найти возможность построения сокращенной ДНФ не по СДНФ, а по произвольной ДНФ заданной функции. Идея такого построения была рассмотрена в работах А. Блека и П. С. Порецкого. Построение СДНФ по произвольной ДНФ вытекает из следующей леммы.
Лемма. Если в ДНФ для данной функции f (x1 , x2… хn ) входят две конъюнкции вида и х,, то имеет место равенство
? (2.43)
где — ДНФ, эквивалентная функция f.
Доказано [5], что левая и правая части соотношения (2.43) принимают одинаковые значения на всех возможных наборах значений аргументов.
Рассмотрим произвольный набор значений аргументов, для которого
f (x1* , x2*… хn* ) = 0.
На основании (2.43) получаем:
0 ? 0 v AB.
Это равенство может выполняться лишь при условии, когда АВ = О. Таким образом, надо доказать, что на наборах значений аргументов, на которых функция / обращается в нуль, обязательно обращается в нуль А или В или одновременно А и В. ДНФ Р по предположению имеет вид:
? .
Так как на рассматриваемых наборах Р = 0, то одновременно выполняются следующие три равенства: S=0, =0 и =0. Из двух последних равенств вытекает, что либо А, либо В, либо А и В одновременно обращаются в нуль, так как и одновременно в нуль обратиться не могут.
Из доказанной леммы вытекает метод построения СДНФ. Для этого необходимо пополнение исходной ДНФ новыми членами согласно лемме. Затем надо провести элементарные поглощения и вновь повторить пополнение ДНФ. Процесс необходимо производить до тех пор, пока будут возникать новые конъюнкции. 11осле получения СДНФ можно использовать метод Квайна, начиная со второго этапа (то есть с построения таблицы меток).
Пример 2.11 Найти СДНФ для функции
f( ) =
Выпишем пары, удовлетворяющие лемме. Таких пар пять:
Построим пополненную ДНФ, не выписывая тех дополнительных членов, которые обращаются в нуль:
f( ) = .
После элементарных поглощений получим:
f( ) = .
В этой ДНФ есть только одна пара, удовлетворяющая условиям леммы . Однако пополнение за счет этой пары не вносит ничего нового в ДНФ. Полученное выражение есть СДНФ.
До этого проблема минимизации функций алгебры логики рассматривалась как задача о нахождении только аналитического представления функции, при котором число букв в представлении минимально, а само аналитическое представление относится к классу ДНФ. Отметим, что МДНФ зачастую не дает абсолютно минимального выражения. Иногда более практичной является минимизация МДНФ за счет вынесения за скобки.
Пример 2.12 Для функции
f( ) =
в примере 2.9 была найдена следующая МДНФ по методу Квайна:
f( ) = .
Если же произвести вынесение за скобки, то
f( ) = .
При этом полученное выражение содержит три буквы вместо четырех и, следовательно, является более простым, чем МДНФ этой же функции.
Метод импликантных таблиц
Проблема минимизации имеет большое значение для практических целей. Однако до настоящего времени не существует общего подхода к решению этой задачи в виду её сложности. Рассмотренные методы минимизации относятся к случаю, когда система базисных функций состоит из операций отрицания, конъюнкции и дизъюнкции. Проблема минимизации может быть сформулирована и для любого другого бриса, состоящего, например, из операции суммы по модулю два, конъюнкции и константы единицы, или для базиса, состоящего из функций Вебба или Шеффера. Так как выбор той или иной базисной системы функций предопределяет выбор стандартного набора типовых логических элементов, то решение проблемы минимизации связано с проблемой экономной реализации различных схем и устройств на базе выбранных типовых элементов.
Метод импликантных таблиц основан на полиномиальной форме представления функций. Как указывалось ранее, полиномиальным представлением функций алгебры логики называют сумму по модулю два любого конечного множества попарно различных элементарных конъюнкций и констант.
Метод импликантных таблиц представляет собой модификацию метода Квайна-Мак-Класки. Все минитермы записываются в виде их двоичных номеров. Кроме минитермов, на которых заданная функция принимает значение "1" (их называют А-минитермами), в таблицу импликант включаются и некоторые из минитермов, на которых функция принимает значение "0". Они определяются следующим образом: производится попарное сравнение всех А-минитермов. Если в сумме имеются две единицы, то берется любой из минитермов А1, А2 и пишутся четыре минитерма, которые получаются из А1 или А2 подстановкой на местах, соответствующих единицам, всех возможных комбинаций из "0" и "1". Если некоторые из полученных минитермов не А-минитермы, то они будут искомыми минитермами (их называют В-мннитермами).
Затем производится попарное склеивание всех А и В-минитермов. При этом из свойств (2.34) не отмечают минитермы, для которых произошло склеиванне.
В таблицу импликант включаются все А и В-минитермы, причем А- минитермы и В-минитермы разделяются, а в строках включаются все возможные полученные импликанты (включая А и В-минитермы). Исследуется таблица импликант. Выбирается такая совокупность импликант, которая покрывает все столбцы А-минитермов нечетное число раз и некоторые столбцы В- минитермов — четное число раз и которая содержит минимальное возможное число букв.
Недостатком приведенных выше методов является то, что при увеличении числа переменных перебор становится большим.
Пример 2.13
1 0 0 0 = A1
1 1 0 1 = A2
0 1 0 1
? ?
1 0 0 0 = A1
? ?
1 0 0 0
1 0 0 1 = B
1 1 0 0 = B
1 1 0 1
Пример 2.14 Для функции примера 2.13 таблица импликант имеет вид:
А В
000 100 010 111 110 101 011
000
100
010
111
110
101
011
-00
0-0
1-0
10-
-10
01-
11-
1-1
-11
--0
-1-
1-- v
v
v
v
v
v
v
<< Пред. стр. 5 (из 7) След. >>
Список литературы по разделу