Основы информатики_Савельев А.Я_Учебник_2001

10 7 Минимизация функций в базисах Шеффера и Пирса

строкам соответствуют найденные простые импликанты булевых функций, а cT0jr6uaM — наборы аргументов, соответствующие единичным значениям минимизируемой функции:

1. если ья простая импликанта содержит j-ю конституенгу 1, О, в противном случае.

Простые импликанты, соответствующие строкам, которые входят в минимальное 1Юкрытие, соединяются знаками дизъюнкции и образуют МДИФ булевой функции.

Квайн г!редложил вычеркивать те столбцы из импликантных таблиц, часть которых полностью эквивалентна по 1 какому-либо другому столбцу, и для выбора строки в формулируемое покрытие начинать просмотр со строк, имеющих максимальное количество единиц.

Основные правила для упрощения заданной булевой матрицы Q при нахождении ее покрытий следующие:

1) правило ггоглощения строк.

IxjiH в матрице Q имеется такая пара строк Q' и Q', что Q' >Q' ^ то строка (J' вычеркивается (проводится сжатие матрицы Q по строкам);

2) правило поглощения столбцов.

Если в матрице Q имеется такая пара столбцов к' ч к', что к' <к', то

столбец к' вычеркивается (проводится сжатие матрицы Q по столбцам). 11оследовагел_ьиым применением этих двух преобразований можно

сжа1ь исходную матрицу до «циклической» матрицы, которая содержит среди своих покрытий хотя бы одно из минимальных покрытий исходной матрицы Q.

Часто!по-мииимальпый метод минимизации основан на изложенных выше положениях и содержит следующие этапы.

1.Из матрицы Q вычеркиваем те строки, которые полностью повторя­ ют всю или часть любой другой строки (поглощаемые строки).

2.Из Q вычеркиваем те столбцы, которые полностью повторяют весь или часть любого другого столбца (гюглощаемые столбцы).

11унк1ы 1 и 2 выполняются гюследовательно до тех пор, пока в матрице Q ос!апутся только не!юглощаемые строки и столбцы.

3. Из оставшихся столбцов матрицы Q отыскиваем столбец, в котором паходигся минимальное количество единиц, находящихся в невычеркнутых cipt)Kax.

4. Из всех невычеркнутых строк, имеющих единицу в выбранном соглас­ но П-3 столбце, находим ту строку, в которой имеется максимальное количе-

247

10 Методы логического проектирования

ство единиц. Если количество столбцов, удовлетворяющих п. 3, больше одно­ го, то строку, соответствуЮ1цую условиям данного пункта, находим среди всех столбцов, выделенных по п. 3. Эту строку выбираем в оптимальное покрьпие.

При равном количестве единиц в строках, удовлетворяющих п. 3 и п. 4, первая из них выбирается для оптимального покрь1тия или же за счет не­ значительного усложнения алгоритма подсчитывается вес строк .?^, кото­ рые имеют единицы в столбцах, удовлетворяющих п. 3. Затем выбираем строку, имеющую наибольший s^ в оптимальное покрытие. При одинако­ вых л^ в оптимальное покрытие выбирается первая из них.

5.Найденную строку и все столбцы, в которых эта строка имеет еди­ ницу, вычеркиваем из Q.

6.Оставшиеся строки проверяем на количество единиц в строке. Если находится строка с числом единиц, равным числу невычеркнутых столбцов, то эта строка вносится в оптимальное покрытие и процесс поиска опти­ мального покрытия на этом заканчивается; если каждая строка имеет толь­ ко по одной единице в каждом из оставшихся столбцов, то э^ги строки вно­ сятся в оптимальное покрытие и процесс поиска также на этом закаичиваегся. Проверять специально после пяти пунктов алгоритма по­ следнее условие необязательно, так как оптимальное покрытие такой мат­ рицы найдется последовательным выполнением пунктов алгоритма.

В противном случае весь алгоритм, начиная с п. 1, повторяется с ос­ тавшимися строками и столбцами.

10.8. Реализация частотно - минимальною метода

Для реализации вышешложенного алгоритма на ЭВМ используются частшные матрицы отношений F двух типов F*^^ и F*^^ . Матрица F " nojiynaeicfl умножением Q на Q \ Эта частотная матрица отношений дает информацию о

тота /-Й строки). Элементы /^ (/,^ ~— взаимная часгота /-й строки су-й строкой) матрицы F*^^ определяют количество единиц, которые находя1ся в тех же са­ мых столбцах как в /-й, так и ву'-й строке. Матрица F*^^ получается умножением

которые находятся в тех же самых строках как в /-м, так и ву-м столбцах..

248

10 8 Реализация частотно-минимального метода

Вматрице F " находим номера строк матрицы Q, которые, соглас­ но п. 1 алгоритма, необходимо вычеркнуть. Это —у'-е строки, у кото­ рых / , = У„

Вэтом случае /-я иу-я строки или полностью эквивалентны ( / - / , ) ,

или/-Я строка является частью /-и строки (/, > /,)•

В матрице F^'*' находим номера столбцов матрицы Q, которые, соглас­ но li. 2 алюригма, необходимо вычеркнуть. Это — i-e столбцы, у которых J„ ^ (ц • При эюм условии 7-й столбец матрицы Q будет noKpbiT теми же строками, которые будут покрыватьу-й столбец.

Рассмотрим частотно-минимальный метод на примере. Частотная мат­ рица Q составляется следующим образом.

licjiH /„ = Д или /„ = Д,, то сравниваются диагональные члены /„ и / „ ,

249

10 К4етоды логического проектирования

мы вместе покрывают одинаковое количество строк. Если /„ > /,,. то вы­

2.SO

10.8 Реализация частотно-минимального метода

Если / „ > / j , (или наоборот), то вычеркиваем /-Й столбец матрицы Q, так как для покрытия 1-й строки исходной матрицы требуется большее ко­ личество термов, чем для покрытияу-й строки.

В результате этих операций получим новую матрицу Q:

010

001

100

принимает значение «1» — «истина». Это число фиксируется с помощью переменной М, которая определяется путем подсчета единиц в крайнем правом столбце матрицы 1А.

251

W.Методы логического проектирования

3.Сравниваются М и 2"'~'. На этом шаге определяется, на каких набо­

рах задавать логическую функцию (I или 0). Если М <2"'\ то функция задается на единичных наборах (признак RK - ]). Если М > 2'""', то функция задается на нулевых наборах (RK - О).

4.Вычисляются: МК = М(М - 1)/2 , определяющего максима1гьное ко­ личество промежуточных термов на одном шаге минимизации; определе­ ние IX, IY — матриц, в KoTopbix расположены минимальные термы.

5.Вызывается подпрограмма TABL

Вэтой подпрограмме анализируется, на каких наборах задаеюя функ­ ция, и в соответствии с этим переписываются строки матрицы !А (строки

—термы, образующие ;югическую функцию) в матрицу IT (матрица ис­ ходных термов) и далее будем использовать только матрицу IT. Анализ осуществляется через признак RK.

6. /! I - 0. Переменная /11 определяет количество минтермов, находя­ щихся в матрице ITERM.

7. Вызов подпрограммы POISK.

Вэтой подпрограмме осуществлгяется поиск минтермов путем сютеиваттия термов.

Под склеиванием термов понимается операция вида .YI^^ + х^х^ - v,. В машине это выглядит следующим образом;

НО

Ш

1 2 Если хотя бьт один раз произошло склеиватше термов, то вьтрабатьтва-

ется признак OR = \^ в противном случае OR^O. Если тюсле вьтттолттеттия подпрограммы POISK OR = О, то это означает, что все минтермьт ттайдетты. Можно ттереходить к поиску минимального покрытия.

Поиск минимальных термов ттроводится путем сравттеттия строк матриттьт IT: 1-я строка сравнивается с 3, 4, 5, ..., Л/-Й, ( Л / - 1 )-я строка сравнивается с Л/-Й. Количество несовттадений по элементам строки фиксируегся ттсреметтной IR. Склеивание термов произойдет лишь в том случае, если IR - \ .

При /Я - 1 /-строку матрицы IT переттисьтваем в i-io строку матрттт^ьт IX. В то место, где произошло склеивание, записывается ттифра «2». Помер этой позиции фиксируется переменной IR.

Если при сравнении строк / и / строк /Л = 0, т.е. /-я и j-я строки оди­ наковые, то переходим к работе с (/ -f-1 )-й строкой. Если при сравнении /-и строки с другими хотя бы один раз произошло склеиваттие (/Л = 1), то вы­ рабатывается признак RV ~ 1.

252

10.8 Реалиэщия частотно-минимального метода

Если RV - О, то /-Ю строку переписываем в матрицу термов ITERM, проверив предварительно, не склеивалась ли данная (-я строка с предыду­ щими строками с 1-й по ( i ~ l )-ю. При сравнении /-Й иу-й строк в случае склеивания номеру запомнится в одномерном массиве KR, на позиции под номером 17. Проверка осуществляется путем поиска номера ; в массиве KR по позициям от 1 до 17 текущего.

8. Если после работы подпрограммы POISK признак OR == 1, то подпро­ грамма PO/SK выполняется еще раз, но здесь работаем в подпрограмме с матрицей IX, а переписываем в матрицу 1Y. Если после этого шага OR = 1, то еще раз вызывается подпрограмма POISK, но проводится перезапись из 1Y в IX. Эш проводится до тех пор, пока признак OR = 1. Чтобы на этом этапе выполнения npoi раммы избежать зацик/швания, вводится переменная NRAZ, она фиксирует количество обращений к подпрограмме POISK. Как только оно превысит заведомо большое число (100), то печатается сообщение ОШИБКА В ITERM и выполнение программы заканчивается.

Ч. /12 = /И ) 1, Л/1 = Л/ + 1.

Параметры /12 и Л/1 описывают матрицу покрытия IQ. Истинный раз­ мер матрицы IQ (П I ХМ), кроме этого необходимы дополнительные строка

ис (олбец для обозначения номеров строк и столбцов матрицы 1Q.

10.Вызов подпрограммы QPOKR.

Спомощью этой подпрограммы формируем матрицу покрытия IQ.

Мафнца образуется по следующему правилу, q^^ = 1 — если г-й минтерм входит в состав / неминимального терма; qjj =0 — в противном случае.

11.Вызов подпрограммы MULTR.

Спомощью этой подпрограммы формируется матрица F*^^, при этом I-я строка IQ умтюжается на себя и попарные произведения суммируют­

12.Вызов подпрограммы OBNUL.

Спомощью этой подпрограммы проводится вычеркивание (обнуление) CI рок ма1 рицы IQ вплоть до /12 элемента.

Собсгветию обнуление проводит программа NR, которая вызывается |юлпрограммой OBNUL. Подпрограмма OBNUL указывает номер строки, которую ттеобходимо обнулить. Поиск такой строки осуществляется сле­ дующим образом:

253

выбор (-Й строки из матрицы ITERM;

сравнение каждого элемента этой строки с цифрой «2»; подсчет количества «2» в этой строке — число их обозначим А'; если К

— чегное число, то вырабатывается признак KCU = 1; если К — нечетное число, то КСН = О.

Признак КСН указывает, с отрицанием или без шрицания записывать минимальный терм;

печать строки матрицы ITERM по элемен-1ам.

Пример 10.7. Пусть задана функция f{x^, jr^, j:?, ^^4) = v(^ - 2. 3 . 9,10,1!)

1

Найти минимальную форму функции в базисе Шеффера (Вебба).

Ре ш е н и е .

1.Составляем матрицу 1А:

00000

00011

00101

00111

ОЮОО

01010

О11О0

01110

10000

10011

10101

10111

11000

11010

11100

11110

2. М =в (результатработы п/п- STOLB).

0001

0010

ООП (резульгат работы 1Годнрограммы TABL). 1001

1010

1011

254

lO.S- Реализация частотно-минимального метода

Мерсиисыиаем 1-KI С фоку а Mai рицу IX и на 3-ю позицию заносим «2». 1Х=|0021|, ет((Л') = 3,

255

10. Методы логического проектирования

Сравниваем 3-ю и 5-ю строки:

ООП № = 2. 1010

Сравниваем 3-ю и 6-ю строки:

ООП т = \,т^\.

1011

0021

IX = 00122001 Щ5)=6.

Сравниваем 4-ю и5-ю строки:

1001 № = 2.

1010

Срав(гиваем4-io и6-ю строки:

1001 W = l, Ж = 3,СТ(6)= 6.

1011

0021

2001

0012

2010

2011

1021

Сравниваем 5-io и6-ю строки:

1010 ;Л = 1, № = 4.

1011 Щ 7 ) = 6.

0021

2001

0012

2010 .

2011

1021

1012

Ни один из термовне являетсяминимальным.

Из матрицы IXформируем IY. Сравниваем 1-ю и2-ю строки:

0021 № = 2 .

2001

Сравниваем 1-ю и3-ю строки:

0021 № = 2.

0012

Сравниваем 1-ю и4-ю строки:

0021 т = Ъ.

2010

Сравниваем 1-ю и5-юстроки:

256