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

Пусть перед некоторым 17-м шагом имеем строчку операторов

YoYiY, Y;'<7—1‘

Если на наборе Д„1? некоторая функция <*iq_ ltq равна единице

ния ГСА прекращается.

Строчка Y qY ^ Y ^ . . . Yiq_ xYiq называется значением ГСА на последовательности наборов Дш1, Дт2, . . . . Д,п 7_,, Amq.

Если каждому оператору Y t (t = 0, 1, . . . , Т 1) граф-схемы поставлено в соответствие некоторое подмножество В ( логических ус­ ловий, элементы которого могут изменяться во время выполнения опе­ ратора Yt, то говорят, что задано распределение сдвигов. Распределе­ ние сдвигов является дополнительной к ГСА информацией о логике работы устройств, и эта дополнительная информация может быть ис­ пользована для упрощения ГСА.1

Пусть процесс выполнения ГСА рассматривается для некоторой последовательности наборов значений логических условий

^ml» ^ш2і • • • I ^mqy ^m- <7+1

и пусть набор Amq предшествует моменту выполнения оператора Ylqj

Д,„ „,, либо совпадает с набором А__ либо отличается от него только значениями переменных из множества Biq.

ГСА Г х и Гп равносильны при данном распределении сдвигов

57

Описание работы дискретного устройства с помощью граф-схемы алгоритмов поясним на примере рис. 4-3. Приведенная ГСАГимеет одну начальную, одну конечную, 16 условных и 11 операторных вер­ шин. Так как для этой граф-схемы X = (х'ъ . . . , ,v8), Y — [ух...........

г/0}, то у соответствующего дискретного устройства должно быть 8 входных и 9 выходных каналов, т. е. предполагается, что для каждой

торный выходной сигнал (ylt . . . , уп, . . . , yN), компоненты которого определяются следующим образом:

если yn ^ Y t\

если уп (£ У,, п = 1, . . . , N.

В частности, оператору У0 соответствует выходной сигнал, у ко­

числять лишь те компоненты, которые в соответствующем структур­ ном выходном сигнале принимают значение единицы. Используя такое допущение, можно сказать, что при выполнении оператора У0 выход­ ные сигналы не выдаются.

Начальной вершине ГСА соответствует некоторое начальное со­ стояние дискретного устройства, при котором выполняется оператор У0. Если теперь идти из начальной вершины по граф-схеме в направ­ лении ориентации дуг графа, выписывая при выходе из условной вер­ шины по «1» логическое условие, стоящее в этой вершине, а при вы­

—Ys = (Уі , г/зЬ x^gXgXi — У8 = \Уъ Ув)1- -

Этому соответствует следующая работа дискретного устройства.

Если в начальном состоянии на вход х х придет сигнал, равный еди­ нице (хх = 1), то независимо от сигналов на остальных входных ка­ налах устройство перейдет в некоторое новое состояние и на первом и втором выходных каналах появятся сигналы, равные единице (г/х= = у 2 = 1), а на остальных выходных каналах — сигналы, равные нулю. Согласно принятому выше допущению можно сказать, что уст­ ройство выдаст выходные сигналы у г, у 2, т. е. будет выполнен опера­ тор Y 2 . Таким образом, а 0 1 = x lt т. е. равняется конъюнкции содер­ жимого условных вершин, лежащих на пути между вершинами У0 и

58

Уг (с учетом выходов по «1» и «О»), Аналогично а 0, = х ^ Х о , а оі =

пустое множество условных вершин, а конъюнкция пустого множества

из выходов которой соединен с ее входом. Будем называть такие ус­

а 10И фактически определяется только первым путем, поэтому в даль­

нейшем будем учитывать лишь те пути через возвратную вершину, которые проходят через выход, не соединенный с ее входом, и будем считать, что на рис. 4-3 имеется один путь вида (4-1) из вершины У10 в вершину 7 ц .

в работе дискретных устройств. В связи с этим будем иногда называть возвратную вершину ждущей вершиной.

4-3. Содержательные граф-схемы алгоритмов

Обычно при проектировании различных устройств предварительно составляется так называемая содержательная граф-схема алгоритма, в которой внутри условных и операторных вершин записаны не эле­ менты множеств X и У, а логические условия и микрооперации в со­ держательных терминах.

В качестве примера рассмотрим алгоритм выполнения операции

чается частное. Проследим выполнение операции деления по содержа­ тельной граф-схеме, изображенной на рис. 4-4.

В начале операции определяется знак -Частного. Если знаки дели­ мого и делителя не совпадают (sign Z Ф sign 2), в знаковый разряд результата (sign У) записывается единица — частное отрицательно. Если знаки совпадают, то это действие пропускается. Далее сбрасы­

всегда равен нулю, так как в предыдущей микрокоманде его сбро­ сили),из делимого вычитается делитель, для чего на сумматор подается обратный код регистра Z (Б : = Е + Zo6p). Если на первом такте

59

(CT = 0) после вычитания на сумматоре оказывается положительное число (sign 2 = 0), то делимое больше делителя, т. е. имеет место пе­ реполнение, и после записи единицы в триггер переполнения (ТП : — != 1) операция прекращается. Если же sign 2 = 1, то наращивается счетчик тактов (СТ: = СТ-|- 1), сумматор и регистр Y сдвигаются

такт. Если после вычитания на некотором такте на сумматоре оказы­ вается отрицательное число, то на следующем такте вместо вычитания содержимого регистра Z из содержимого сумматора производится их сложение (2: = 2 + Z), т. е. реализуется .операция деления без вос­ становления остатка. Если на некотором такте, кроме первого, после вычитания на сумматоре получается положительное число (sign 2 = = 0), то в младший п-й разряд результата записывается единица (Y [п] := 1). По прошествии п тактов (СТ = п) операция заканчи­ вается. Результат деления записан в регистре Y.

60

После построения содержательной ГСА логические условия и мик­ рооперации кодируются символами Х; xL и Уі >

у ■■■■> Ум соответственно:

При таком кодировании вершин содержательной ГСА, приведен­ ной на рис. 4-4, получим ГСА, изображенную на рис. 4-5.

4-4. Логические схемы алгоритмов

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

щей из символов операторов, логических условий и верхних и ниж-

і І

них стрелок, которым приписаны натуральные числа ( ] , I ; і = 1, 2, . . .) [12]. Такая запись алгоритма носит название логической схемы алгоритма (ЛСА). Рассматриваемые ниже ЛСА удовлетворяют следующим условиям:

1.Содержат один начальный (Ун) и один конечный оператор (Ук);

2.Перед оператором Y tt и после оператора Ук стрелок быть не должно.

3.Вслед за каждым логическим условием всегда стоит верхняя

стрелка.

4. Не существует двух одинаковых (с одинаковыми цифрами) ниж­ них стрелок.

І

5.Для каждой нижней стрелки .|. должна быть по крайней мере одна верхняя стрелка.

6.Для каждой верхней стрелки должна быть точно одна нижняя

стрелка.

Вопросы равносильных преобразований ЛСА были исследованы Ю. И. Яновым [24]. Использование ЛСА для описания работы дис­ кретных устройств получило широкое развитие в работах В. Г. Лаза­

61

соответствует некоторое начальное состояние дискретного устройства, при котором никакие выходные сигналы не выдаются. Если в началь­ ном состоянии на вход х4 устройства придет сигнал, равный единице (х4 = 1), то устройство перейдет в некоторое новое состояние, в кото­

ром выполняется оператор 1 У4 — первый справа после логического

1

условия х 1. Если х4 = 0, то выходим по верхней стрелке f и ищем

1

нижнюю стрелку с той же цифрой ( I ). После нее стоит логическое ус-

2

ловие д'., со стрелкой f , за ней—операторы У4, Y 3, а вслед за нижней

Так как со = 0, после оператора У2 всегда выполняется оператор

/

Yt, а переход к У3 возможен только по стрелке f .

ные функции перехода равны нулю. Понятия значения ЛСА на допу­ стимой последовательности наборов, распределения сдвигов и равно­ сильности логических схем алгоритмов будем понимать точно так же, как и подобные понятия для ГСА, введенные в § 4-2.

Изложим алгоритм перехода от ГСА к ЛСА на примере граф-схемы, изобра­ женной на рис. 4-7.

1.Входы всех вершин ГСА (условных и операторных), к которым подхо

более одной стрелки, а также вход конечной вершины, даже если к ней подхо­

1 При описании работы устройства на языке ЛСА под оператором, как и в случае ГСА, понимается множество микроопераций, выполняемых в устройстве одновременно.

62