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

Подождите немного. Документ загружается.

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

строкам соответствуют найденные простые импликанты булевых функций,

а cT0jr6uaM — наборы аргументов, соответствующие единичным значениям

минимизируемой функции:

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

О, в противном случае.

Простые импликанты, соответствующие строкам, которые входят в

минимальное 1Юкрытие, соединяются знаками дизъюнкции и образуют

МДИФ булевой функции.

Квайн г!редложил вычеркивать те столбцы из импликантных таблиц,

часть которых полностью эквивалентна по 1 какому-либо другому столбцу,

и для выбора строки в формулируемое покрытие начинать просмотр со

строк, имеющих максимальное количество единиц.

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

нахождении ее покрытий следующие:

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

IxjiH в матрице Q имеется такая пара строк Q' и Q', что Q' >Q'

то

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

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

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

столбец к' вычеркивается (проводится сжатие матрицы Q по столбцам).

11оследовагел_ьиым применением этих двух преобразований можно

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

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

матрицы Q.

Часто!по-мииимальпый метод минимизации основан на изложенных

выше положениях и содержит следующие этапы.

Из матрицы Q вычеркиваем те строки, которые полностью повторя-

ют всю или часть любой другой строки (поглощаемые строки).

Из Q вычеркиваем те столбцы, которые полностью повторяют весь

или часть любого другого столбца (гюглощаемые столбцы).

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

Q ос!апутся только не!юглощаемые строки и столбцы.

Из оставшихся столбцов матрицы Q отыскиваем столбец, в котором

паходигся минимальное количество единиц, находящихся в невычеркнутых

cipt)Kax.

Из всех невычеркнутых строк, имеющих единицу в выбранном соглас-

но П-3 столбце, находим ту строку, в которой имеется максимальное количе-

247

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

ство единиц. Если количество столбцов, удовлетворяющих п. 3, больше одно-

го,

то строку, соответствуЮ1цую условиям данного пункта, находим среди всех

столбцов, выделенных по п. 3. Эту строку выбираем в оптимальное покрьпие.

При равном количестве единиц в строках, удовлетворяющих п. 3 и п. 4,

первая из них выбирается для оптимального покрь1тия или же за счет не-

значительного усложнения алгоритма подсчитывается вес строк .?^, кото-

рые имеют единицы в столбцах, удовлетворяющих п. 3. Затем выбираем

строку, имеющую наибольший s^ в оптимальное покрытие. При одинако-

вых л^ в оптимальное покрытие выбирается первая из них.

Найденную строку и все столбцы, в которых эта строка имеет еди-

ницу, вычеркиваем из Q.

6. Оставшиеся строки проверяем на количество единиц в строке. Если

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

то эта строка вносится в оптимальное покрытие и процесс поиска опти-

мального покрытия на этом заканчивается; если каждая строка имеет толь-

ко по одной единице в каждом из оставшихся столбцов, то э^ги строки вно-

сятся в оптимальное покрытие и процесс поиска также на этом

закаичиваегся. Проверять специально после пяти пунктов алгоритма по-

следнее условие необязательно, так как оптимальное покрытие такой мат-

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

В противном случае весь алгоритм, начиная с п. 1, повторяется с ос-

тавшимися строками и столбцами.

10.8.

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

Для реализации вышешложенного алгоритма на ЭВМ используются час-

тшные матрицы отношений F двух типов F*^^ и

F*^^

. Матрица F" nojiynaeicfl

умножением Q на Q\ Эта частотная матрица отношений дает информацию о

юаимиом влиянии строк Q друг на друга. На диагонали F*"' находи^гся число

/ . которое определяет количество единиц в /-й строке (/, — собсгвениая час-

тота /-Й строки). Элементы /^ (/,^

~—

взаимная часгота /-й строки су-й строкой)

матрицы F*^^ определяют количество единиц, которые находя1ся в тех же са-

мых столбцах как в /-й, так и ву'-й строке. Матрица F*^^ получается умножением

Q' на Q (F'^^ = Q^Q) и дает информацию о юаимном шшянии столбцов. Здесь

/ покрывает количество единиц в /-м столбце, а /^ — количество единиц,

которые находятся

тех же самых строках как в

/-м,

так и ву-м столбцах..

248

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

В матрице F" находим номера строк матрицы Q, которые, соглас-

но п. 1 алгоритма, необходимо вычеркнуть. Это —у'-е строки, у кото-

рых /,

У„

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

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

/,)•

В матрице F^'*' находим номера столбцов матрицы Q, которые, соглас-

но li. 2 алюригма, необходимо вычеркнуть. Это — i-e столбцы, у которых

J„ ^ (ц

•

При эюм условии 7-й столбец матрицы Q будет noKpbiT теми же

строками, которые будут покрыватьу-й столбец.

Рассмотрим частотно-минимальный метод на примере. Частотная мат-

рица Q составляется следующим образом.

Мииималыгые

1срмы

XjX,

;;;;;;;>:./

"\^

^,х,х,х.

-x,i,x,x,

Термы

х,х^х,х,

XiS^XjX,

XfyX,X,

XfyXjX,

1*,сли

i-i'i lepM входит в составу-го выражения, чо элемент матрицы Q

'/„ " I

иначе 4,1=0.

000011

010100

000010

001011

101010

Составляется матрица F*^' = QQ'

•

20121

20001

111

матрица симметричная.

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

249

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

Если /, > f^j, то из матрицы Q вычеркиваетсяу-я строка.

Если /;, < JII, то вычеркиваетсяу-я строка.

В данном примере: /\4 ~ fw ^2;/,4 =3;/j4 >/|| г:>(3>2)из ма1рицы

вычеркивается 1-я строка:

Ля ~

y_14

~ /35 ~ '-

744

~ -'i /44

-^ ./55

~ -''

./44

^ /я'

/^, > /^,j :::> (3 > 1)

ИЗ матрицы Q вычеркивается 3-я сфока.

Количество строк, покрываемых /-м минимальным lepMOM, ука!ывае1

/,; количество строк, покрываемых /-м иу-м минимальными (ермами, вме-

сте указывает /^,.

Равенство /„

/^ или /^ = /^, показывает, что /-й терм и /-и и /-и тер-

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

бираем /(У) минтерм, так как /-и миитерм покрывает большее количество

строк, чему-й, и наоборот.

Составляем матрицу-столбец F*^^ =Q^Q:

101010

10100

2021

100 •

Если j„=

j\,

или /, ^/^,, то сравииваегся /, и /^^. Ехли /^ >./„. ю

вычеркиваем /-Й столбец из матрицы Q.

В данном примере /|, - fxi ~ f\s\ fw

j\y. </55 ("^ матрицы Q вычер-

киваем 3-Й и 5-Й столбцы); /jj

f^^-^

f^^

fu (из матрицы Q вычеркиваем

2-й столбец), если /г, - J\^\ f^^ > Аъ "^^^ вычеркиваем 5-й столбеп. а если

/^^^ -

у^^^;

у^^ =

у^^^^,

то вычеркиваем 5-й столбец.

/^, показывает, что /-я строка исходной матрицы покрывается |ермами

в количестве /^, штук.

f- показывает количество минимальных термов, покрывающих / и j

строки вместе.

Если /, -/, или /„ -/,,, то это показывает, сколько мингермов по-

крывают одновременно /-ю иу-ю строки вместе.

2.SO

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

Если /„ >

/j,

(или наоборот), то вычеркиваем /-Й столбец матрицы Q,

так как для покрытия 1-й строки исходной матрицы требуется большее ко-

личество термов, чем для покрытияу-й строки.

В результате этих операций

получим новую матрицу Q:

КГ

010

001

100

Поглощений нет.

Из матрицы Q следует, что

onTHMajrbiioe покрытие состав-

ляют миптермы 2, 4, 5, т. е.

Алгоритм,

реализующий

минимально-частотный метод,

представлен на рис. 10.8.

ВводЯ1СЯ исходные

дан-

ные.

В качесше исходных

дан-

ных выступают следующие па-

раметры:

/1 — количество

liaGopoB переменных /1=2'",

где т

•—

количество переменных;

N\ — количество переменных

(н;),

(V = (V +

; матрица 1А —

таблица исгинности.

Вьтзывается подпрограм-

ма sroiB.

В этой подпрограмме осу-

ществляется подсчет количества

наборов логических перемен-

ных, на которых функция F{x)

принимает значение «1» — «истина». Это число фиксируется с помощью

переменной М, которая определяется путем подсчета единиц в крайнем

правом столбце матрицы 1А.

Рис.

10.8.

Алгоритм минимизации

251

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

Сравниваются М и

2"'~'.

На этом шаге определяется, на каких набо-

рах задавать логическую функцию (I или 0). Если М <2"'\ то функция

задается на единичных наборах (признак RK - ]). Если М

2'""',

то функ-

ция задается на нулевых наборах (RK - О).

Вычисляются: МК = М(М - 1)/2 , определяющего максима1гьное ко-

личество промежуточных термов на одном шаге минимизации; определе-

ние IX, IY — матриц, в KoTopbix расположены минимальные термы.

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

В этой подпрограмме анализируется, на каких наборах задаеюя функ-

ция, и в соответствии с этим переписываются строки матрицы !А (строки

— термы, образующие ;югическую функцию) в матрицу IT (матрица ис-

ходных термов) и далее будем использовать только матрицу IT. Анализ

осуществляется через признак RK.

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

щихся в матрице ITERM.

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

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

ваттия термов.

Под склеиванием термов понимается операция вида

.YI^^

х^х^

- v,.

В машине это выглядит следующим образом;

НО

1 2

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

ется признак OR = \^ в противном случае OR^O. Если тюсле вьтттолттеттия

подпрограммы POISK OR = О, то это означает, что все минтермьт ттайдетты.

Можно ттереходить к поиску минимального покрытия.

Поиск минимальных термов ттроводится путем сравттеттия строк матриттьт

IT:

1-я строка сравнивается с 3, 4, 5, ..., Л/-Й, (Л/-1 )-я строка сравнивается с

Л/-Й. Количество несовттадений по элементам строки фиксируегся ттсреметт-

ной IR. Склеивание термов произойдет лишь в том случае, если IR - \ .

При /Я -

/-строку матрицы IT переттисьтваем в i-io строку матрттт^ьт

IX. В то место, где произошло склеивание, записывается ттифра «2». Помер

этой позиции фиксируется переменной IR.

Если при сравнении строк / и / строк /Л = 0, т.е. /-я

j-я строки оди-

наковые, то переходим к работе с (/

-f-1

)-й строкой. Если при сравнении /-и

строки с другими хотя бы один раз произошло склеиваттие (/Л = 1), то вы-

рабатывается признак RV ~ 1.

252

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

Если RV - О, то /-Ю строку переписываем в матрицу термов ITERM,

проверив предварительно, не склеивалась ли данная (-я строка с предыду-

щими строками с 1-й по (i~l )-ю. При сравнении /-Й иу-й строк в случае

склеивания номеру запомнится в одномерном массиве KR, на позиции под

номером 17. Проверка осуществляется путем поиска номера ; в массиве KR

по позициям от

до 17 текущего.

8. Если после работы подпрограммы POISK признак OR

1, то подпро-

грамма PO/SK выполняется еще раз, но здесь работаем в подпрограмме с

матрицей IX, а переписываем в матрицу 1Y. Если после этого шага OR = 1,

то еще раз вызывается подпрограмма POISK, но проводится перезапись из 1Y

в IX. Эш проводится до тех пор, пока признак OR = 1. Чтобы на этом этапе

выполнения npoi раммы избежать зацик/швания, вводится переменная NRAZ,

она фиксирует количество обращений к подпрограмме POISK. Как только

оно превысит заведомо большое число (100), то печатается сообщение

ОШИБКА В ITERM

выполнение программы заканчивается.

Ч. /12 = /И ) 1,

Л/1

Л/

Параметры /12 и Л/1 описывают матрицу покрытия IQ. Истинный раз-

мер матрицы IQ (П

ХМ), кроме этого необходимы дополнительные строка

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

10.

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

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

Мафнца образуется по следующему правилу,

q^^

— если г-й минтерм

входит в состав / неминимального терма; qjj =0 — в противном случае.

11.

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

С помощью этой подпрограммы формируется матрица F*^^, при этом

I-я строка IQ умтюжается на себя и попарные произведения суммируют-

ся,

получаем элемент /ц , затем 1-ю строку умножаем на 2-ю, 3-ю и т. д.,

I-IO на /! !, получаем элементы /,2, /п, ••-, //и

•

Затем 2-(р на 2-ю, 2-ю на

3-ю, 2-ю па 4-10, ...,

/11x711.

Это элемент /цц,,. Размер матрицы F"

равен /11

/11.

12.

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

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

рок

ма1

рицы IQ вплоть до /12 элемента.

Собсгветию обнуление проводит программа NR, которая вызывается

|юлпрограммой OBNUL. Подпрограмма OBNUL указывает номер строки,

которую ттеобходимо обнулить. Поиск такой строки осуществляется сле-

дующим образом:

253

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

последовательно выбираются диагональные элементы /„ матрицы

1FSTR;

/„ сравнивается с элементами строки столбца, на пересечении кото-

рых /„ находится;

если есть равенство f„=f„ или f„= f,,, то вырабатывается признак

ES -\ — признак наличия обнуления на данном этапе;

сравниваем /, и /^^; если /, > f ^, то выполняем:

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

сравнение каждого элемента этой строки с цифрой «2»;

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

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

число, то КСН = О.

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

минимальный терм;

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

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

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

Решение.

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

00000

00011

00101

00111

ОЮОО

01010

О11О0

01110

10000

10011

10101

10111

11000

11010

11100

11110

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

0001

0010

ООП

1001

1010

1011

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

254

lO.S-

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

Сравниваем 1-ю и 2-ю строки.

0001 два несовпадения

0010 W =

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

0001 ;Л = 1,

ООН ;л =

з.

Мерсиисыиаем

1-KI

фоку а

Mai

рицу IX и на 3-ю позицию заносим «2».

1Х=|0021|,

ет((Л') = 3,

Сравниваем 1-Н) и 4-к>С1роки:

0001 /Л = 1,

1001 т=\.

5;UR(2)

= 4.

Сравниваем [-юи 5-|ос|роки:

Сравниваем

-ю и 6-ю строки:

Сравниваем 2-к1 и 3-BteipoKH:

0001

1010

;л=з.

0001

=2.

1011

0010 т = \..т = *,кщъ) =

ъ.

0010

0021

2001

0012

Сравниваем 2-ii> и 4-ю сгроки:

С рав(П!Ваем

2-10

5-юс!роки:

0010 № =

1001

0010 Ж=1, №=1.

1010 17 =

Щ4) =

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

0010 т = г.

1011

0021

2001

0012

2010

CpaBiHHiacM 3-ю и 4-ю строки:

ООП ;« =

1001

255

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

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

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

Сравниваем

4-ю и 5-ю строки:

Срав(гиваем

4-io

и 6-ю строки:

ООП № =

1010

ООП т

\,т^\.

1011

0021

2001

0012

Щ5)=6.

1001 № =

1010

1001

W =

Ж = 3,

СТ(6)

1011

0021

2001

0012

2010

2011

1021

Сравниваем

5-io

и 6-ю строки:

1010

;Л =

№ =

1011 Щ7) = 6.

0021

2001

0012

2010 .

2011

1021

1012

Ни

один из термов не является

минимальным.

Из матрицы IX

формируем

IY.

Сравниваем

1-ю и 2-ю строки:

Сравниваем

1-ю и 3-ю строки:

Сравниваем

1-ю и 4-ю строки:

Сравниваем

1-ю и 5-ю строки:

0021

№=2.

2001

0021 № =

0012

0021 т = Ъ.

2010

256