Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

входят все состояния класса Кі о одинаковыми значениями столбцов

•Кі = ' {S|, S2, 55), . K*' = {Sз, S,| ; iC2" = j 5 4j Sr).

Если по таблице переходов составить частотную матри­ цу отношений, определив при этом умножение как

Кг X Кі = 1;

Кі X Kj =■■ 0 ( і ф і ) ,

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

dGM

öS {St, Sß) — 0.

После получения классов К\, К2', К2" снова строим таб­ лицу переходов и т. д. до тех пор, пока каждый класс ус­ ловных эквивалентных состояний, выделенный на предыду­ щем піаге, останется неизменным.

В нашем случае таблица переходов, построенная с учетом сделанного разбиения класса К2, имеет вид

Анализ этой таблицы показывает, что все состояния каж­ дого из выделенных классов ведут себя «дружно» (перехо­ дят под воздействием X в один и тот жеклдсс), что обуслов­ ливает на выходе одно и то же значение Y для всех состоя­ ний класса при одном переходе. Следовательно,ч все состоя­ ния одного класса ведут себя как одно состояние, которым его и заменяют.

30'

Заменим классы К\, К 2 ', Къ" соответственно внутренними состояниями Sa, Sb, Sc. В результате получим минимизиро­ ванный граф переходов (рис. 2-3), задающий то же отобра­ жение X -> Y, что и первоначальный граф переходов (рис. 2-2). Для иллюстрации этого поставим три эксперимента.

Пусть на вход автомата подается временная последова­ тельность вида

X(0 = о і 1010.

Впервом и во втором случаях автомат задан первона­ чальным графом переходов (рис. 2-2) соответственно с на­ чальными состояниями 5 1 и 5г- В третьем случае автомат за­ дан минимизированным графом (рис. 2-3) с начальным со­

стоянием S a.

Определим временные выходные последовательности У (t) для каждого случая.

Все три эксперимента сведем в следующую таблицу:

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

нии.

фов, соответствующих таблицам выходов и переходов, равны нулю

на каждом шаге разбиения множества внутренних состояний на классы. Утверждение непосредственно следует из метода Хафмена.

§ 2-3. Введение счетчиков в обратную связь автомата

При введении счетчиков в обратную связь автомата упро­ щается схема возбуждения памяти автомата (рис. 2-4).

Рис. 2-4

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

Многие операции, выполняемые арифметическими уст­ ройствами современных ЦВМ, можно реализовать автома­ том, памятью которого является счетчик.

32

• f r

Ф <£ (6

а

^D-^HD—HD—HD—HD—HD

<■ л

6 ) 0 _ * 0 _ ? 0

Рис. 2-5

Например, операции «суммирование», «вычитание», «по­ разрядное сложение» в ЦВМ «Минск-ІІ» (рис. 2-5), опера­ ция «вычитание модулей» в ЦВМ «Днепр» (рис. 2-6) можно реализовать автоматом со счетчиком в цепи обратной связи. При этом необходимо помнить признаки, характеризующие ход вычислений для однозначного выполнения следующей микрокоманды, и ввести неустойчивые состояния для вырав­ нивания длин путей при наличии в графе переходов цикла, как, например, в рис. 2−6 состояния между и S25.

1

\

/

ким, что не позволяет его применять при кодировании внут­ ренних состояний управляющих автоматов ЦВМ. Поэтому в этом параграфе предложим частотно-матричный метод коди­ рования состояний.

В результате абстрактного синтеза был построен мограф, определяющий отображение X S + 5~У. После кодирования

идентификаторам внутренних состояний 5,-, будут изменены полными подграфами, соответствующими кодам Z,- внутрен­ них состояний .

Предлагаемый метод кодирования можно оформить в ви­ де следующего алгоритма синтеза кодирующего дерева:

1. Строим двухвходовую матрицу Q = каждой строке которой взаимно однозначно соответствует микрооперация, или значение входного канала (элементы вектора УилиХ), столбцу — внутреннее состояние, и

1, если первичный терм, соответствующий і-й стро- а . . = ке, входит в каждую пару векторов X Y (X -*■ У), гз взвешивающих дуги, исходящие из вершины /';

О— в противном случае.

Каждому внутреннему состоянию (столбцу матрицы) взаимно однозначно произвольным образом сопоставляем максимальную вершину синтезируемого кодирующего де­ рева.

Полагаем Q = Q.

2. По матрице Q находим частотную матрицу отноше­

ний F,

F - = Q • Q.

3. Вычисляем значения производной от модели, заданной

матрицей Q.

4.Выбираем пару внутренних состояний, на которых вы­ численное значение производной минимально.

5.Выбранную пару состояний вычеркиваем и ставим ей

всоответствие в кодирующем дереве вершину, являющуюся началом дуги, концом которых являются выбранные состоя­ ния (каждой паре выбранных состояний сопоставляем пере­

сечение этих состояний в смысле теории структур). По­

36

строенной вершине взаимно-однозначно сопоставляем стол­ бец в строящейся матрице Qc, равный векторному, произведе­

нию столбцов в матрице Q, соответствующих выбранным вершинам.

6. Проверяем, остались ли не рассмотренные внутренние состояния, для которых вычислялись значения производной. Если «остались», то переходим к пункту 4, в противном слу­ чае, — к пункту 7.

7. Проверяем, образована ли матрица Qc■ Если образова­

на, то полагаем Qc = Qи переходим к пункту 2, в противном случае, — к пункту 8.

8. Каждым двум дугам, исходящим из вершины в по­ строенном дереве, начиная с дуг, исходящих из корня дере­ ва, ставим в соответствие произвольно 0 или 1. *

Путь, соединяющий корень дерева и максимальный эле­ мент, взвешен кодом, который сопоставляется внутреннему состоянию, соответствующему этому максимальному эле­ менту дерева.

9. Конец.

Проиллюстрируем предлагаемый алгоритм на следующем примере. Пусть в результате абстрактного синтеза был полу­ чен граф переходов G (рис. 3-1). Используя предлагаемый алгоритм, закодируем внутренние состояния автомата.

Матрицу Q, соответствующую данному графу, предлагаем построить читателю самостоятельно.

Частотная' матрица отношений, соответствующая матри­ це Q, имеет следующий вид:

S, s 2 S3 s 4 S5 s 6

37