Лекция 15.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Р₂ = а₁х₂ Ú ( а₀Ú а₄) х₁Ú а₂х_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_Хх. Разница в площадях матриц без кодиро­вания и с кодированием логических условий

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

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

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

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

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

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

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

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

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

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

Из полученных выражений видно, что D 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

Допустим имеется обратная структурная таблица (табл. 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 (согласно покрытиям в карте Карно):

Реализуем функции 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

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

D 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