ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 106
Скачиваний: 0
находится функция / у , равная дизъюнкции функций перехода, стоя щих в этом столбце:
|
|
f у |
= |
V |
|
«/<■ |
|
|
|
t |
|
і=о |
|
|
|
В MCA М (табл. 7-11): |
|
|
|
|
|
||
fyl = XlX2’ |
1’ ’ |
= ^ V Х\Х2 ~ |
^ ’ |
fy, = Х\Х2V Х\Х2V Х\ х і’ |
|||
f у. = |
V Х2V |
М '^2 V Х\ “ М V -*2 |
V Л:2 = ^’ f У„ = Х1Х2Х3' |
||||
fyK= X2V xix2V *2 V M'S V X,X2X3 V xi = M V *2 V %
|
Рис. 7-12. ГСА Г до учета распределения сдвигов |
|
|
|
|
Среди |
fy |
(t = 1, . . . , Т + 1) отыскиваются сокращенные |
осо |
||
бенные функции относительно переменных хп , . . . , xiR £ |
X, |
т. |
е. |
||
функции, |
которые можно представить в виде fY = х.'1. . . x.‘R |
f' |
= |
||
= фу f , |
где f |
не зависит от ,ѵп, . . . , x.R; x ^ = хіг при |
е.г = |
1 |
и |
X. — хІГ при е.г = 0 (г = 1...........R). Исключая из фу логические ус
ловия, входящие в распределение сдвигов оператора Yt, цолучим функции фу . В рассматриваемом примере
Ф у х= Х 1Х2’ |
Ф у , = ЛТ ’ |
ФѴа == •*•!» |
ФУ., ” Х1’ |
157
ф у ( — A'j; |
Ф у , — х 1> |
Ф Y = X l W |
Ф ’у„ = Х 1 'Ѵ |
^
Из рассуждений, аналогичных приведенным при построении MCA
очевидно, что если Ф*у< = х £е . . . х £ . . . х ^ ( [ х к1, . . . . xkQ) С
|
Ul^ |
{х'ц, |
. . . , xiR)), то в |
строке |
Yt в выражениях а1р(р = |
1, . . . , |
|
+ 1) |
переменную xkq можно |
заменить на единицу, если |
ekq = 1, |
|
или на нуль, если ekq = |
0 (<7 == |
1, . . . , Q). |
|
||
|
Рассмотрим еще один пример минимизации MCA с учетом распре |
||||
деления сдвигов1. В табл. 7-13 приведена матричная схема алгоритма, для которой задано:
Рис. 7-13. ГСА Г' после учета распределения
|
сдвигов |
|
У 1------- |
Ві = |
[*2. *3. *4); |
У2------ |
В2= 0 ; |
|
у з -------- |
В з = |
(*з); |
У4-------- |
В4 = |
{*1, Х2, Х3}\ |
Уь------- |
Въ= [ х г, ж4}; |
|
у к----- |
вК=0. |
|
Непосредственно из табл. 7-12 с учетом распределения сдвигов |
||
имеем фу = x y\ фу3= * р |
Фу, = Л:4’' |
Фу5 = х2Заменяя в строке Y y |
переменную х х на нуль, в строке Y 3 — х г на единицу, в строке У„—х4 на единицу и в строке Y 5 —x 2 на единицу, получим MCA М' в табл. 7-14.
1 Пример взят из |8, стр. 46].
158
^0
Уі
Yt
у 3
У4
У*
Л
Y о
Уз
У4
^5
Таблица 7-13
MCA М до минимизации с учетом распределения сдвигов
У1 |
Y„ |
Уз |
Уз |
У3 |
Ук |
■Ѵі |
|
*1*2 |
|
*1*2 |
|
.Ѵ'іА'2.Ѵз |
|
*1*2 |
|
*1*2*3 |
*2 |
|
|
|
XoX'i. |
Х2ХІ |
*i |
*1*4 |
|
|
*1*4 |
|
*i |
|
|
|
. |
*2*4 |
*2V *4 |
|
1 |
|
|
|
|
|
MCA М' |
после минимизации MCA М |
Таблица 7-14 |
||
|
|
||||
Уі |
F 3 |
У3 |
У4 |
Уз |
|
*1 |
|
*1*2 |
|
*1*2 |
|
*2*3 |
|
|
|
|
Х2 |
|
|
|
*2*4 |
*2*4 |
Х'4 |
|
|
|
|
|
1 |
|
|
|
|
Л'о |
А*2 |
|
1 |
|
|
|
|
В MCA М' fy — 1 не является сокращенной особенной функцией,
в связи с чем ее нельзя непосредственно использовать для минимиза ции MCA. Однако из табл. 7-14 видно, что Y 2 выполняется после Yb независимо от значений логических условий. В то же время <Pys = х 2,
т. е. до и сразу после выполнения оператора |
Yü переменная х 2 равна |
единице. Подставляя тогда в строку Yb аЬ 2 = |
л:3 вместо а 63 = 1, имеем |
159
фу = х2, после чего, заменив в строке Y 2х0 на единицу и вернувшись к а 62 = 1, получим окончательно MCA М " в табл. 7-15.
|
|
|
|
|
Таблица 7-15 |
MCA М" после дополнительной минимизации MCA М' |
|||||
|
у 1 |
Y п |
у» |
Уъ |
У* |
^ 0 |
Л 'і |
|
Х ± Х о |
х у л у |
|
Уі |
ЛуЛ'З |
|
|
дулу ■ |
Л'о |
|
|
|
67 |
'Ѵ4 |
Л'4 |
У3 |
|
|
|
|
1 |
У5 |
|
1 |
|
|
|
В MCA М " удалены строка и столбец К,, так как все ссу., (/ = О, 1, . . . , 5) оказались равными нулю.
При минимизации ГСА (или MCA) с помощью методов, изложенных в § 7-1, рассмотренную методику учета распределения сдвигов можно интерпретировать в терминах отмеченных кубических покрытий. Для MCA М (табл. 7-13) исходным покрытием будет:
ПОххх 1 10ха' 3 11 XX 5
Yj ОЮх' 1 1 1 Л'Х' 3 011л: 5
хОхх к
Y 2 XОх'1 4
ХІХІ 5 х'хх'0 к
К3 0хх0 1
Охх 1 4
1XXX к
к4 ХІХІ 5 хОхх к
XXX0 к
Кб хххх 2
160
Покрытия формул перехода для различных исходящих операторов отделены друг от друга горизонтальной чертой. В левом столбце ука зан исходящий оператор, в среднем — логический куб, а в правом — индекс оператора, отмечающего этот куб (индекс входящего оператора). Так, для первой строчки (К„) MCA М (табл. 7-13), записанной в виде формулы перехода
|
|
Y о |
XxY1 \ / а'і-ѵ2У з \/ |
Л']Л:аѴ 5, |
|
|
|||
отмеченное покрытие |
имеет вид |
|
|
|
|
|
|
||
|
|
|
Уо |
ОXXX |
1 |
|
|
|
|
|
|
|
|
10XX |
3 |
|
|
|
|
|
|
|
|
11 XX |
5. |
|
|
|
|
Для определения |
функций / у |
(t = |
l', . . . , 5, к) |
из исходного от |
|||||
меченного покрытия |
(7-7) |
выбираются кубы, отмеченные символом /: |
|||||||
|
|
QXXX |
|
|
|
11 XX |
|
|
|
|
|
|
|
|
0 1 1 А |
|
|
||
|
|
010а |
|
|
|
|
|
||
|
|
|
|
|
А1А 1 |
|
|
||
|
|
Оа.ѵО |
|
|
|
|
|
||
|
|
|
|
|
АІА 1 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
=\хххх\; |
|
|
|
хОхх |
|
|
||
|
*1 |
1 |
|
|
|
|
|
|
|
|
|
10 XX |
|
|
|
XXXО |
|
|
|
|
|
1 Іхх |
|
fy |
= |
1XXX |
|
|
|
|
|
xOxl |
|
|
|
хОхх |
|
|
|
|
?Y = |
|
|
|
|
XXX О |
|
|
|
Покрытия фу содержат по одному кубу |
и получаются из / , |
сле |
|||||||
дующим образом. Если во всех кубах покрытия / ѵ |
і-я связанная |
ко- |
|||||||
ордината |
одинакова |
(і |
1, . . . , |
|
|
|
1/ |
|
то |
п, где п — размерность куба), |
|||||||||
в кубе ф |
t-я координата будет связана и примет то же значение, что |
||||||||
и в fy . Различным связанным координатам или свободным координа
там в кубах fy соответствуют свободные координаты в №.. . Если у
11 ‘ t
Ф у все построенные таким образом координаты оказались свобод
ными, то полагаем фу = 0 . Например, фу = Оххх, так как в покры
тии fY первые координаты всех кубов равны нулю. Точно так же фуз= 0 , Фуз= 1лхг, у у = х х х \ , фу5= ХІХХ, фу = 0 .
Покрытие ф*у получается из фу заменой r'-й связанной координаты
на свободную, если лу f Bt (соответствующее этой координате логи ческое условие входит в распределение сдвигов оператора Yt, і —
161