Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

Подобные соображения могут быть использованы н при кодирова­ нии выходных сигналов для минимизации функции выходов. Упоря­ дочим, например, выходные сигналы автомата S из таблицы выходов (табл. 2-5), которые в этой таблице встречаются:

ш3—3 раза; w.z—2 раза; агі— 1 раз; ад, — 1- раз; их—2 раза;

и*— 1 раз.

После кодирования выходных сигналов в соответствии с упорядо­ чиванием (табл. 3-12 и 3-13) таблица выходов автомата S примет вид табл. 3-14.

Непосредственно из этой таблицы получаем выражения функций выходов:

У і — т і т а у д ' з V TiTo.i'i.Vo = 1 V 6 ;

У2 = TiToA'iA'o V TjToAVa V ТіТоЛ'іЛ'з = 1 V 2 \/ 12;

'■= Т]Т2-

Напомним, что аналогичные выражения при первом варианте ко­ дирования выходных сигналов имели вид:

у1 = т1тгх1,Го V ТхЪХхХъ V ХхЪХіХг V XiXzXiX2 = 0 \/ 5 V 6 \/ 14;

у2 ^=х1 т2 х1 х2 V ТіТа.ѵу.Ѵо '■/ ТчТоДдл'., у т^плул'о — 0 \/ 1 \/ 5 \/ 14;

Г = ТіТо \/ TjT2.

Большое число работ [25, 26, 28], начало которых было положено Хартманисом и Стирном [27, 291, посвящено получению такого ко­

48

дирования, при котором уменьшается зависимость функций возбужде­ ния от переменных обратной связи т х, . . . , т; . Хартманне и Стирн показали, что этот подход тесно связан с существованием определен­ ныхразбиений множества состояний автомата. Как правило, нахож­ дение вариантов кодирования состояний, которые создают ослаблен­ ную функциональную зависимость для функций возбуждения, часто дает более экономичную схему, чем при других типах кодирования.

Упомянутый подход и развитые на его основе методы достаточно подробно изложены в литературе, в том числе и в монографиях [11, 18]. В то же время большинство авторов отмечают сложность этих методов кодирования при синтезе автоматов с большим числом состоя­ ний и переходов и при синтезе частичных автоматов, а также трудно­

методах, а рассмотрим эвристический алгоритм кодирования Состоя­ ний, предложенный в [19] и минимизирующий суммарное число из­ менений элементов памяти на всех переходах автомата. При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, т. е. также минимизируется комбинационная схема автомата.

Введем весовую функцию W = h t ms, где tms— \Km — Ks |2 — расстояние между кодами состояний ат и as, равное числу элементов памяти, изменяющих свое состояние на переходе (ат, а„); суммирова­ ние производится по всем переходам автомата. Введенная функция W может служить одной из оценок сложности комбинационной схемы

состоящую из всех различных пар номеров (ar, ßr), таких, что в авто­ мате S есть переход из ааг в а^г.

2. Переставим строки в матрице так, чтобы выполнялось условие

К> ßr} П (аі> ßi, - • , a,_i, ß,_i)=A0, /- = 2, . . . , R. (3-1)

Условие (3-1) означает, что хотя бы один из элементов r-й строки содержится в какой-нибудь из предыдущих строк. Имеются в виду только связные автоматы [19], для которых такая перестановка всегда возможна.

3. Закодируем состояния из первой строки матрицы М следующим образом:

Ка, = (00 . . . 00); /Ср, = (00 . . . 01).

4. Вычеркнем из матрицы М первую строчку, соответствующую закодированным состояниям аа и ар 4 Получим матрицу М ' .

5.В силу условия (3-1) в начальной строке матрицы М' закодиро­ ван один элемент. Выберем из первой строчки матрицы М' незакоди­ рованный элемент и обозначим его через у.

6.Построим матрицу М ѵ, выбрав из М ' строчки, содержащие у.

закодированы, в результате чего получим новую матрицу, которую

1Ниже вместо «элемент <хг, соответствующий закодированному состоянию

аа», будем говорить «закодированный элемент а Л». Кроме того, если вторая

строчка есть (ßj, а 4), то вычеркиваем и ее, таю как ее элементы уже закодиро­ ваны.

50

кодирование к соседнему, при котором к = 1. Эксперименты с про­ граммой на ЦВМ М220, проведенные для автоматов различной слож­ ности (число состояний М = 10-н 128), дали значения к в пределах

1,4 — 2,1 [19].

Без подробных пояснений приведем пример кодирования состояний авто­ мата, граф которого изображен на рис. 3-41:

12

24

25

I4

1Дугам графа ие приписаны входные и выходные сигналы, так как они не используются в алгоритме.

5 4

k = W/p = 10 : 8 = 1,25.

52