3.3.4. Вопросы оптимизации автоматов на матрицах

Методы оптимизации автоматов на матрицах направлены, в основном, на сокращение суммарной площади матриц. Как было указано в п. 3.3.1, матрицы М_& и М₁ при тривиальной реализации автомата сильно разрежены: большая часть площади этих матриц не используется, так как в узлах нет диодов. Это касается части матрицы М_&, вычисляющей функции переходов (в области переменных Х), и матрицы М₁ (в области переменных У).

Кодирование логических условий х. Площадь матрицы м& в автоматах Мили и Мура зависит:

1. от количества элементов памяти (количество выходов Q и Q элементов памяти обозначим К_Q; К_Q входит в общее число горизонтальных шин матрицы М_&; К_Q >= 2 • ] log₂ | A | [ );

2. от количества переменных Х (количество горизонталь­ных шин от этих переменных К_Х = 2•|Х| также входит в общее число горизонтальных шин матрицы М_&);

1. от числа переходов Т(a_m a_s) автомата К_Т.

Уменьшить К_Q невозможно, так как в автоматах на матрицах используется всегда минимальное кодирование состояний. Количество переходов можно иногда уменьшить за счет использования разметки ГСА с узлами. В то же время в каждой конкретной функции переходов Тa_ma_s обычно используются не все переменные из множества Х, а только некоторые из них. Например, по структурной таблице из п. 3.3.2 и 3.3.3 видно, что в каждой функции Тa_ma_s используется максимум одна переменная Х (при общем их количестве 3), поэтому есть возможность уменьшить площадь SМ_& за счет замены трех переменных Х одним логическим условием Р, принимающим значение определенной переменной Х в зависимости от состояния автомата a_m.

Алгоритм такой замены описан ниже.

1. Разобьем множество входных сигналов автомата (логических ус­ловий) Х на пересекающиеся подмножества Ха_м; элемен­тами Ха_м являются логические условия Х_j, определяющие все переходы автомата из состояния а_м.

2. Найдем максимум =maxХа_м и введем новое множество, содержащее  логических условий Р={Р₁, Р₂...Р_}.

3. Каждую переменную хХа_м заменим на переменную из множе­ства Р; составим таблицу этой подстановки. Желательно, чтобы одноименные логические условия Х_j оказались в одном и том же столбце таблицы.

4. Запишем функции Р_i= F(а_м,x_i), используя таблицу подста­новки.

5. Закодируем состояния автомата таким образом, чтобы можно было реализовать эти функции на матрицах М_& и М₁ с мини­мальными затратами. Полученные коды состояний будем использовать далее при составлении структурной таблицы автомата.

6. Используем сформированные функции Р_i вместо переменных Х в матрице М_& для вычисления функций переходов автомата Тa_ma_s.

Например, пусть по размеченному графу автомата с шестью состояниями a₀…a₅ и семью логическими условиями х₀…х₆ получили следующие подмножества Ха_м:

Ха₀={х₀,х₁}; Ха₃={х₅};

Ха₁={х₂,х₃}; Ха₄={х₁,х₃};

Ха₂={х₃,х₄}; Ха₅={х₆}.

Нетрудно заметить, что Max Ха_i= 2.

Введем два новых логических условия: Р={Р₁, Р₂} и составим таблицу замены переменных Х на переменные Р.

ам	Р1	Р2
а0	х0	х1
а1	х3	х2
а2	х3	х4
а3	х5	-
а4	х3	х1
а5	х6	-

Запишем выражение для Р₁ и Р₂ :

Р₁ = а₀х₀  ( а₁ а₂ а₄) х₃  а₃х₅  а₅х₆

Р₂ = а₁х₂  ( а₀ а₄) х₁ а₂х_4.

В этих выражениях, например, Р₁ принимает значение ло­гического условия х₀, если автомат находится в состоянии а₀ (так как при этом а₀=1); значение х₃, если автомат нахо­дится в одном из состояний: а₁ или а₂ или а₄ и т.п.

Закодируем состояния автомата таким образом, чтобы выражения в скобках можно было записать в виде одного терма, используя переменные Q₃, Q₂, Q₁ – сигналы с выходов элементов памяти состояний автомата. Используем карту Карно. В ячейках карты расставим состояния а_I таким образом, чтобы была возможность осуществить их минимальное покрытие согласно скобочным частям выражений Р₁ и Р₂. Получим следующие коды состояний:

Ка₀ = 000; Ка₃ = 000;

Ка₁ = 111; Ка₄ = 100;

Ка₂ = 101; Ка₅ = 011.

Учитывая то, что в карте Карно есть свободные клетки, используем их для минимизации выражений Р₁ и Р₂ :

Р₁ = а₀х₀  ( а₁ а₂ а₄) х₃  а₃х₅  а₅х₆=

= Q₂Q₁ х₀  Q₂ х₃  Q₁Q₀ х₅  Q₂ Q₀ х₆ = Z₁  Z₂  Z₃  Z₄ ,

где Z₁= Q₂Q₁ х₀ ; Z₂ = Q₂ х₃; Z₃ = Q₁Q₀ х₅; Z₄ = Q₂ Q₀ х₆;

Р₂ = а₁х₂  ( а₀ а₄) х₁ а₂х₄ =

= Q₂ Q₁ х₂  Q₁Q₀ х₁Q₁ Q₀ х₄ = Z₅  Z₆  Z₇ ,

где Z₅ = Q₂ • Q₁ • х_{2 ;} Z₆ = Q₁•Q₀• х₁; Z₇ = Q₁• Q₀•х₄.

Рис. 3.37

Функциональная схема, реализующая преобразование логических условий Х в логические условия Р, приведена на рис. 3.37. Матрица М_& вычисляет термы Z₁ … Z₇ , матрица М₁ – функции Р₁ и Р₂.

Площадь матрицы М_& равна

SМ_& = (К_Х + К_Q) • К_Z ,

где К_Х – количество логических ус­ловий Х, в нашем примере – К_Х=7; К_{Q –} количество прямых и ин­версных выходов элементов па­мяти, в нашем примере К_Q = 6; К_Z – количество термов в функциях Р₁и Р₂ , в нашем при­мере К_Z=7.

Таким образом, в нашем при­мере SМ_& = 91.

Площадь матрицы М₁ равна SМ₁ = К_Z • К_Р , где К_{Р –} количество логических ус­ловий Р.

В нашем примере SМ₁ = 14. Общая площадь матриц М_& и М₁, используемых для минимиза­ции количества логических усло­вий, равна

S_Мр = (К_Х + К_Q) • К_Z + К_Z • К_Р = (К_Х + К_Q + К_Р)* К_Z .

Если не использовать кодирование логических условий Х, то площадь части матрицы М_&, вычисляющей функции переходов Тa_ma_s (в нашем примере этой матрицы нет) и использующей в качестве переменных Х, равна

S_МТх = 2 • К_Х • К_Т,

где К_{Т –} количество переходов (строк) в структурной таблице ав­томата.

При замене логических условий Х на Р эта площадь составит

S_МТр = 2 • К_Р • К_Т.

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

S_Хр = S_Мр + S_МТр = (К_Х + К_Q + К_Р)* К_Z + 2 • К_Р • К_Т,

а без кодирования

S_Хх = S_МТх = 2 • К_Х • К_Т.

Использование описанного преобразования имеет смысл, если S_Хр заметно меньше, чем S_Хх. Разница в площадях матриц без кодиро­вания и с кодированием логических условий

 S_Х = S_Хх – S_Хр = 2 • К_Х • К_{Т –} (К_Х + К_Q + К_Р)•К_{Z –} 2•К_Р•К_Т =

= 2 • К_Т • ( К_{Х –} К_Р) – (К_Х + К_Q + К_Р)•К_Z .

Чтобы эта разница была положительной ( S_Х > 0), необхо­димо выполнение условия

2 • К_Т • ( К_{Х –} К_Р) > (К_Х + К_Q + К_Р)•К_Z ,

иначе преобразование логических условий имеет смысл, если выполняется соотношение

К_Т > ((К_Х + К_Q + К_Р)•К_Z) / (2 • ( К_{Х –} К_Р)).

Если условие выполняется и при этом S_Х имеет значительную величину (относительно S_Хх), то можно проделать описанную процедуру и по­лучить при этом более эффективное использование матриц.

В нашем примере

 S_Х =2 • К_Т • ( К_{Х –} К_Р) – (К_Х + К_Q + К_Р)•К_Z .=

= 2 • К_Т • ( 7 _– 2) – (7 + 6 + 2) • 7 = 10 • К_Т – 105.

Из полученных выражений видно, что  S_Х > 0, если в авто­мате К_Т>11 (количество переходов больше 11); при выполнении этого условия имеет смысл выполнить преобразование логических условий Х в логические условия Р.

Кодирование выходных сигналов автомата (микрокоманд y_j ). В автоматах Мили при простейшей реализации (п. 3.2) в матрице М₁ есть сильно разреженная часть, где вычисляются y_i. Это происходит потому, что общее число микрокоманд в автомате может быть большим, но на каждом переходе вырабатывается небольшое число микрокоманд. В таком случае можно повысить эффективность использования матрицы М₁, используя кодирование микрокоманд. Для этого необходимо:

1. выписать из ГСА или обратной структурной таблицы одинаковые группы микрокоманд, которые обозначить как В_i;

2. записать выражения для y_i как В_j – дизъюнкция групп В_i, в которых функция y_i =1;

3. составить граф отношений между группами В_i. Вершины графа соответствуют группам микрокоманд В_i, ребрами соединяются вершины (В_i.), содержащие одинаковые микрокоманды;

4. закодировать вершины (В_i) двоичным кодом (b₁ b₂ b₃ …) таким образом, чтобы связанные вершины на графе можно было выразить через конъюнкцию переменных b_i. Количество переменных b_i должно быть минимальным и равно ] log₂ B  [;

5. записать выражения для b_j как Т_j: где Т_j – дизъюнкция функций переходов автомата Мили, на которых b_j =1;

6. записать выражения y_i=В_j через конъюнкцию переменных b_i: у_i=b_j;

7. реализовать функции b_j = Т_j с помощью матрицы М₁;

8. реализовать функции у_i=b_j с помощью матрицы М_&.

Рассмотрим пример.

Таблица 3.15

№	Y(amas)	Т(amas)	Вi	b1b2b3b4
1	y1, y2	T1	B1	0 0 1 1
2	y1, y3	T2	B2	0 1 1 0
3	y7, y8	T3	B3	1 0 0 1
4	y1, y10	T4	B4	0 1 1 1
5	y5, y6	T5	B5	1 0 1 1
6	y3	T6	B6	1 1 1 0
7	y4, y8	T7	B7	1 1 0 0
8	y4, y8, y9	T8	B8	1 1 0 1
9	y1, y10	T9	B4	0 1 1 1
10	y4, y8	T10	B7	1 1 0 0
11	y4, y8, y9	T11	B8	1 1 0 1
12	y1, y10	T12	B4	0 1 1 1
13	y5, y6	T13	B5	1 0 1 1
14	y5, y6	T14	B5	1 0 1 1
15	y4, y8, y9	T15	B8	1 1 0 1
16	y1, y10	T16	B4	0 1 1 1
17	y7, y8	T17	B3	1 0 0 1
18	y9	T18	B9	0 1 0 1
19	y5, y11	T19	B10	1 0 1 0

Допустим имеется обратная структурная таблица (табл. 3.15) автомата Мили для реализации на ПЛМ, из которой мы выпишем только столбец Ya_ma_s, а в столбце Тa_ma_s оставим только обозначение функций переходов Т_i. Остальные столбцы таблицы нас не интересуют. Из этой таблицы видно, что площадь матрицы М₁ при простейшей реализации автомата, использующаяся для формирования микрокоманд y_i, равна

S_МУ = К_У • К_Т = 11• 19 = 209.

В этом примере коли­че­ство микроко­манд, ко­торые может формиро­вать автомат, равно 11 (y₁…y₁₁), но на каж­дом из 19 возможных перехо­дов T₁ … T₁₉ формиру­ется мак­симум 3 микроко­манды.

Добавим в эту таблицу еще два столбца. Первый – для обозначе­ния групп микроко­манд (В_i); в нашем примере – 10 различных групп микрокоманд (обозначим их B₁...B₁₀). Во вто­ром столбце будем записывать коды групп В_i. Минимальное количество разрядов для коди­рования В_i равно четырем. Обо­значим код В_i: b₁ b₂ b₃ b₄.

Выра­зим y_i через дизъ­юнкцию В_j, в которые входит y_i:

y₁ = B₁  B₂  B₄ ;

y₂ = B₁ ;

y₃ = B₂  B₆ ;

y₄ = B₇  B₈;

y₅ = B₅  B₁₀;

y₆ = B₅;

y₇ = B₃;

y₈ = B₃  B₇  B₈;

y₉ = B₈  B₉;

y₁₀ = B₄;

y₁₁ = B_10.

Используя выражения y_i=В_j построим граф отношений между группами В_i, в котором ребрами соединяются вершины (В_i.), содержащие одинаковые микрокоманды (рис. 3.38). Используя карту Карно, закодируем группы В_i так, чтобы можно было совместно покрыть связанные вершины (смотри карту Карно).

Рис. 3.38

По карте Карно запишем коды B_i (КB_i), выраженные через значения пере­менных b₁ b₂ b₃ b₄:

КВ₁=0011; КВ₂=0110; КВ₃=1001;

КВ₄=0111; КВ₅=1011; КВ₆=1110;

КВ₇=1100; КВ₈=1101; КВ₉=0101;

КВ₁₀=1010.

Запишем полученные коды групп микрокоманд в столбец (b₁b₂b₃b₄) структурной таблицы автомата и выразим функции b_i как дизъюнкцию соответствующих переменных T_i той же таблицы:

b₁ = T₃ T₅ T₆ T₇ T₈ T₁₀ T₁₁ T₁₃ T₁₄ T₁₅ T₁₇ T₁₉ ;

b₂ = T₂ T₄ T₆ T₇T₈T₉ T₁₀ T₁₁ T₁₂ T₁₅ T₁₆ T₁₈ ;

b₃ = T₁ T₂ T₄ T₅ T₆ T₉ T₁₂ T₁₃ T₁₄ T₁₆ T₁₉ ;

b₄ = T₁ T₃  T₄ T₅ T₈ T₉ T₁₁ T₁₂ T₁₃ T₁₄ T₁₅ T₁₆ T₁₇  T₁₈.

Выразим y_i , записанные через дизъюнкцию В_j, в виде конъюнкции у_i=b_j (согласно покрытиям в карте Карно):

y1 = B1  B2  B4 = b1 b3;	y2 = B1 = b1 b2 ;
y3 = B2  B6 = b2 b3 b4 ;	y4 = B7  B8= b1 b2 b3 ;
y5 = B5  B10 = b1 b2 b3 ; y7 = B3 = b1 b2 b3 ; y9 = B8  B9 = b2 b3 b4 ; y11 = B10 = b1 b2 b3 b4 ;	y6 = B5 = b1 b2 b3 b4 ; y8 = B3  B7  B8 = b1 b3 ; y10 = B4 = b1 b2 b3 b4 .

Реализуем функции b_{1 …} b₄ с помощью матрицы М₁, а функции y_{1 …} y₁₁ – с помощью матрицы М_& (рис. 3.39).

Оценим суммарную площадь матриц М₁ и М_& , реализующих функции выходов автомата Мили с кодированием микрокоманд:

S_Мb = К_b • К_Т = 4 • 19 = 76, где К_Т – количество переменных, используемых для кодирования групп микрокоманд; S_МУb = 2 • К_b • К_У = 2 • 4 • 11 = 88; S_МУк = S_Мb + S_МУb = 76 + 88 = 164.

Рис. 3.39

Разница в площадях матриц без кодирования и с кодированием составляет

 S_У = S_МУ – S_МУк= 209 – 164 = 45.

Экономия площади матриц позволяет реализовать более сложный автомат на меньшей площади кристалла матрицы.

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

К_Т • (К_У – К_b ) > 2 • К_b • К_У .

Решение о кодировании можно принять после определения количества групп микрокоманд В_j и возможности их минимального кодирования переменными b_j.

На рисунках приведены обобщенные структурные схемы автомата Мили с кодиро­ванием логических условий и мик­рокоманд (рис. 3.40) и автомата Мура с кодирова­нием логических условий и мик­рокоманд (рис. 3.41).

Рис. 3.40

В схеме автомата Мили используются следующие элементы:

– память состояний – ПС;

– матрица М_&(1), вычисляющая термы z_i для последующего вычисле­ния логических условий Р матрицей М₁₍₁₎;

– матрица М_&(2), вычисляющая функции переходов Т_i;

– матрица М₁₍₂₎, вычисляющая функции управления элементами памяти состояний Fa_ma_s и коды групп микрокоманд КВ_i (b₁b₂...);

– матрица М_&(3), вычисляющая значения функций y_i.

В схеме автомата Мура используются следующие элементы:

– память состояний – ПС;

– матрица М_&(1), вычисляющая термы z_i для последующего вычисле­ния логических условий Р матрицей М₁₍₁₎;

– матрица М_&(2), вычисляющая функции переходов Т_i;

– матрица М₁₍₂₎, вычисляющая функции управления элементами памяти состояний Fa_ma_s;

– матрица М_&(3), выполняющая функции дешифратора состояний автомата и вычисляющая значения функций а_i;

– матрица М₁₍₃₎, вычисляющая значения функций y_i.

Рис. 3.41

Лекция 16.