РАЗДЕЛ 2
РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ КМУУ
БЕЗ РАЗДЕЛЕНИЯ КОДОВ
2.1. Кодирование логических условий
Пусть автомат адресации КМУУ U1 задан ПСТ (табл. 2.1), из которой следует, что X = {x1, ..., x5}, L=5, R1=3, R2=4.
Таблица 2.1
Прямая структурная таблица автомата S1 КМУУ U1
amK(am)asK(as)Xh?hФhha10 0 0a20 0 1D7D1 D41a30 1 0D6D22a40 1 1D6 D7D2 D33a20 0 1a30 1 0D6D1 D34a40 1 1D6 D7D25a30 1 0a51 0 01D5D1 D46a40 1 1a20 0 11D7D57a51 0 0a30 1 0D6D1 D48a20 0 1D7D29a61 0 1D5 D7D1 D310a61 0 1a20 0 1D7D211a10 0 0-D112
Пусть X(am) - множество переменных, определяющих переходы из состояния am?A. В нашем случае X(a1)={x1, x2}, X(a3)=X(a4)=?, X(a5)={x3, x4}, X(a6)={x5}. Для синтеза MU1 используем методику замены логических условий из работы [5].
1. Определим число G кодирующих переменных pg?P по формуле
G = max (G1, ..., GM), (2.1)
где Gm=|X(am)|, . В нашем случае G=2, следовательно P={p1, p2}.
2. Построим таблицу замены входных переменных со столбцами am, p1, ..., pG, в которой на пересечении строки am и столбца pg записывается переменная xl?X, заменяемая в состоянии am?A переменной pg?P. Таблица замены строится так, чтобы выполнялось условие
, (2.2)
где pi, pj ? P, X(pi), X(pj) - множество логических условий в столбцах pi и pj соответственно.
Для нашего примера таблица замены (табл. 2.2) удовлетворяет условию (2.2).
Таблица 2.2
Таблица замены входных переменных автомата S1
amp1p2K(am)amp1p2K(am)a1x1x20 0 0a4--0 1 1a2x3-0 0 1a5x3x41 0 0a3--0 1 0a6-x51 0 1
3. Сформируем систему функций (1.15) в виде
, (2.3)
где Cgm - булева переменная, равная единице если и только если переменная xl?X заменяется в состоянии am?A переменной pg?P. В нашем случае имеем:
;
.
Очевидно, что каждая функция системы (2.3) тривиально реализуется на мультиплексоре, имеющем R1 управляющих входов. В нашем случае M-подсхема реализуется на двух мультиплексорах (рис. 2.1).
Как видно из рис. 2.1, информационные возможности мультиплексоров используются на 3/8, то есть 5 информационных входов из 8 остаются незадействованными. Назовем показателем использования мультиплексоров коэффициент
(2.4)
где Lg=|X(pg)|, при этом показатель
(2.5)
характеризует эффективность использования ресурсов M-подсхемы.
В нашем случае K1=K2=0.375=KM.
Для увеличения коэффициента KM в работе [18] предлагается два метода:
1. Уточненное кодирование состояний, при котором в первую очередь кодируются состояния с условными переходами.
2. Преобразование кодов состояний в коды логических условий, при котором в схему автомата вводится специальный преобразователь кода.
В первом случае множество состояний A разбивается на два класса: A1 - состояния с условными переходами и a1?A1, A2 - состояния с безусловными переходами. Для автомата S1 имеем A1={a1, a2, a5, a6}, A2={a3, a4}. Если состояния am?A закодировать следующим образом: K(a1)=000, K(a2)=001, K(a5)=010, K(a6)=011, K(a3)=100, K(a4)=101, то для всех состояний am?A1 T1=0. В этом случае M-подсхема имеет вид (рис. 2.2).
Теперь согласно (2.4)-(2.5) имеем K1=K2=KM=0.75. Кроме того, при выполнении условия
(2.6)
параметры - и, следовательно, стоимость - мультиплексоров при уточненном кодировании уменьшается.
На рис. 2.3 приведена схема MU1 с преобразователем ПК кодов состояний в коды логических условий .
В этой схеме ПК формирует переменные Zr?Z, кодирующие логические условия, |Z|=R6. Вопросы синтеза подобных схем достаточно полно рассмотрены в [41, 45].
Условимся далее КМУУ с уточненным кодированием состояний обозначать как MCUi, а КМУУ с преобразователем <состояние - логическое условие> - как MLUi ().
Рассмотрим особенности замены логических условий в КМУУ U2. На рис. 2.4 приведена структурная схема КМУУ MU2.
Пусть автомат адресации S1 КМУУ U2 задан таблицей переходов (табл. 2.3), в которой A(), A(Og) - соответственно определяет адрес i-го входа ОЛЦ ?g?C и адрес ее выхода в УП.
Как видно из табл. 2.3, состояния am?A здесь в явном виде отсутствуют. В этой связи методика синтеза [18] должна быть модифицирована. Рассмотрим предлагаемую модификацию.
1. Построим множества X(Og) логических условий, определяющих переходы из ОЛЦ ?g?C. Определим мощность множества кодирующих переменных P:
GO = max (G1, ..., GG), (2.7)
где Gg=|X(Og)|, .
Таблица 2.3
Таблица переходов автомата S1 КМУУ U2
OgA(Og)A()XhФhhO10 0 0 00 0 0 1D410 1 0 0D220 1 1 0D2 D33O20 1 0 10 1 0 0D240 0 1 0D1 D35O31 0 0 11 0 1 01D1 D36O41 1 0 01 1 0 11D1 D2 D47O51 1 0 10 0 0 1D481 1 1 0D1 D2 D39O61 1 1 00 1 0 0D2100 1 1 0D2 D3110 0 0 1D412
2. Построим таблицу замены логических условий со столбцами Og, p1, ..., pG и строками O1, ..., OG. На пересечении строки Oi и столбца pg запишем переменную xl?X, заменяемую для ОЛЦ ?g?C переменной pg?P. Распределение переменных xl?X производится так, чтобы выполнялось условие (2.2).
3. Сформулируем систему функций (1.15) в виде
, (2.8)
где Cig - булева переменная, равная единице, если и только если переменная pi?P заменяет условие xl?X для ОЛЦ ?g?C, Bg - конъюнкция переменных Tr?T, соответствующая адресу A(Og).
4. Построим M-подсхему по системе (2.8), подавая на управляющие входы переменные Tr?T.
5. Построим преобразованную ПСТ автомата S1, заменив столбец Xh столбцом Ph по известной методике [5].
Для автомата S1 имеем X(O1)={x1, x2}, X(O2)={x3}, X(O3)=X(O4)=?, X(O5)={x4}, X(O6)={x3, x5}, G=2, то есть P={p1, p2}. Таблица замены логических условий (табл. 2.4) включает столбец A(Og), содержащий переменные, поступающие на управляющие входы мультиплексоров.
Таблица 2.4.
Замена логических условий автомата S1 КМУУ U2
Ogp1p2A(Og)Ogp1p2A(Og)O1