Решение. Выявим совместимые внутренние состояния без предварительного выявления и объединения эквивалентных и псевдоэквивалентных состояний. Для этого построим треугольную табляцу (см. табл. 4.10).

По табл. 4.10 получаем следующие группы совместимых внутренних состояний: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 - 2,13 - 4,15 - 6,16 - 8,17 - 12,14-----

Таким образом, максимальным группами совместимых внутренних состояний являются: 1=1; 2=2, 13; 3=3; 4=4, 15; 5=5; 6=6, 16; 7=7; 8=8, 17; 9=9; 10=10; 11=11; 12=12, 14. Группы все непересекающиеся, а поэтому таблицу покрытий строить нет необходимости. Следовательно, получаем минимальный автомат с 12 внутренними состояниями (табл. 4.11).

Таблица 4.11

4.2. Формирование микрокоманд микропрограммного автомата

В разд. 3.4 было отмечено сходство матричной схемы алгоритма и матрицы переходов, причем сходство отмечалось при условии сопоставления с каждым оператором МСА отдельного внутреннего состояния автомата. Поэтому МСА можно рассматривать как язык задания автомата при условии, что оператор сопоставляется с выходом автомата, соответствующим не полному, а внутреннему состоянию автомата (т. е. автомату Мура [1, 3]). При такой автоматной интерпретации матричной схемы алгоритма задача минимизации числа внутренних состояний автомата состоит в объединении совместимых внутренних состояний автомата, имеющих непротиворечивые состояния выходов, т. е. непротиворечивые операторы.

Из сказанного вытекает, как следствие, то, что если условия работы микропрограммного автомата (МА) заданы не МСА, а ЛСА, то для минимизации числа внутренних состояний МА необходимо иметь метод, обеспечивающий непосредственно по ЛСА допустимое объединение операторов в группы, с каждой из которых могло бы сопоставиться внутреннее состояние МА. Такой метод получил название метода формирования микрокоманд [2, З]. При этом, когда говорят о МА, обычно члены ЛСА (операторы и ЛУ) называют микрооперациями (операторы - внешние, ЛУ - внутренние микрооперации), а внутренние состояния МА - макрокомандами [2, З]. Упорядоченная совокупность микрокоманд,. обеспечивающая реализацию автоматом заданных условии работы, называется микропрограммой [2, З]. Таким образом, минимизация числа внутренних состояний МА-это такое объединение микроопераций в группы (т. е. в микрокоманды), при котором образуется минимальное число микрокоманд.

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

Говорят, что логическое условие рг входит в распределение сдвигов оператора Л„ если последний может изменить значение pi, или оно может независимо измениться при выполнении данного оператора. Например, pi в ЛСА (3.9) проверяет значение номера входа (не превысило ли значение f числа имеющихся входов, т. е. iAn), а оператор Fi после прибавления к i единицы может изменить значение ЛУ р\. В частности, если перед выполнением оператора Fj значение 1=п, а поэтому pi=l, то после реализации оператора Fi значение pi изменится, т. е. pi=0, так как i>n. Поэтому ЛУ pi входит в распределение сдвигов оператора Fi.

Выявив, таким образом, все те ЛУ (например, pj1,pj2,рД) 1<п, где n- число всех ЛУ в ЛСА), значения которых могут измениться после выполнения оператора Aj, получим распределение сдвигов для оператора а], которое запишем в виде Aj={pi, pi2,...,pil}. Определив распределения сдвигов для каждого оператора ЛСА получим распределение сдвигов для всех

операторов ЛСА (полное распределение сдвигов). Из распределений сдвигов для операторов выделяют универсальное распределение, когда l=n, т. е. A,-{pi, pi, рп}, и пустое распределение сдвигов, когда оператор А, не изменяет значения ни одного из п ЛУ, т. е. aJ-{-}Более подробно о распределении сдвигов можно наити в [З].

Два члена ЛСА Xi и xj являются противоречивыми, если:

1)они не могут быть выполнены одновременно;

2)Xi - логическое условие, а xj - оператор, причем ЛУ xj входит в распределение сдвигов оператора

xj.

Член Xi, который может быть выполнен непосредственно перед членом х„ называется предшественником х,, а соответственно член Xj - последователем члена Xj. Очевидно, у любого члена ЛСА может быть несколько предшественников, у оператора может быть только один последователь, а у логического условия-два последователя, за счет чего при выполнении ЛСА образуются разветвления. Группа членов ЛСА образует ветвь, если каждый (И-1)-й член этой ветви является последователем 1-го члена.

Один и тот же член ЛСЛ может входить в несколько различных ветвей.

Группу членов ЛСА назовем совместимой, если в каждой ветви, образуемой членами этой группы, не содержится противоречивых членов. Совместимую группу членов ЛСА назовем максимальной, если добавление в нее любого другого члена ЛСА превращает ее в несовместимую. Каждая совместимая группа, в том числе и максимальная, может интерпретироваться как отдельная микрокоманда. Такая микрокоманда может состоять из набора как внутренних (логических условий), так и внешних (операторов) микроопераций, но при определенном наборе значений логических условий одновременно выполняются микрооперации, входящие лишь в одну ветвь микрокоманды. Для получения совместимой группы Mxi (микрокоманды), т.е. группы, первым членом которой является Xi выписывается член Xj ЛСА. Если у Xi имеется один последователь (т. е. Xj,-оператор), то этот последователь приписывается справа от Xj. При наличии двух последователей образуется разветвление и каждый из них выписывается справа от л-- ; на отдельной ветви. Этот процесс повторяется для всех вновь приписанных членов группы в каждой ветви. Ветвь группы Mxj, обрывается, если в нее вошел последний оператор ЛСА, либо если в нее должен быть включен член ЛСА, который является противоречивым с одним членом этой ветви, либо если после х, необходимо выписать Xi, который уже вошел в другую ветвь группы Мхх. В последнем случае необходимо указать стрелку от Xj к Xi. Формирование группы заканчивается после того, как обрываются все ее ветви. Если в первую группу вошли не все члены ЛСА, образуется вторая группа, начиная с наименьшего по порядку члена ЛСА, не вошедшего в предыдущую группу. Так процесс повторяется до тех пор, пока каждый член ЛСА не войдет хотя бы в одну группу.

Следует заметить, что если последователь Хг последнего члена ветви этой группы не был включен хотя бы в одну группу (например, из-за того, что Хг является противоречивым с одним из членов ветви), то обязательно должна быть группа mxi. Кроме того, отметим, что если имеется группа (микрокоманда) Mxi, то в остальных группах все ветви, в которые входит член xj, могут быть оборваны на предшественнике этого члена Xi.

Процесс формирования микрокоманд рассмотрим на следующих примерах.

Пример 47 Пусть задана ЛСА (3.9). Исходя из содержательного рассмотрения операторов этой ЛСА (см. пример 3.6), выявим операторы, которые можно выполнить одновременно. Информацию о возможности одновременного выполнения операторов (т. е. непротиворечивых операторов) представим в треугольной таблице (табл. 4.12), аналогичной той, которая использовалась ггря минимизации числа внутренних состояний автомата (см., например, табл. 4.11).

Несмотря на то, что в ЛСА (3.9) не указаны в явном виде операторы начала Ао и конца Ak, при формировании микрокоманд, они должны учитываться. При этом предполагается, что Ak переводит автомат в исходное состояние, а поэтому считается, что он всегда совместим с Ло. Вместе с тем операторы Ао и Ak не должны быть совместимы ни с одним другим оператором ЛСА.

Из табл. 4.12 видно, что кроме операторов Ау и Ak совместимыми являются также пары операторов f{и f]; А\ и Ач; А\ и Лз. Распределения сдвигов выявим также из содержательного рассмотрения операторов и ЛУ ЛСА (3.8). При этом для операторов Ац я Ak всегда берется универсальное распределение сдвигов:

А0 - (Pi, Р2, Рз, Pi, Рь) ; Ah - {plt р2, р3. Pi, р5] ;

/:г - iPi, Pi, Р3), Fj- {p2 Pi, p-j ; Ax- {ръ} ; A - { - >; A3 - {ps}.

Как видно, для оператора As получено пустое распределение сдвигов. Для примера рассмотрим составление распределения сдвигов для оператора A1, при этом выясним, чго он не может изменить значения следующих ЛУ:

1) pi, поскольку о. н не меняет значения i; 2) p2, так как возможность изменения определяется только типом измерительного прибора, подключенного к i-v. вертикали, а оператор А1 не меняет значения i; 3) p3, так как гоступленяе вызова от него не зависит, а номера i он не меняет; 4) pj, поскольку значение / изменяется только оператором F].

Таким образом, в распределение сдвигов для оператора А \ логические условия pi, ps, рз и /?4 не входят. Оно будет содержать только одкэ ЛУ ps, так как после реализации оператора Ai объект, подключенный к у-ц горизонтали, станет занятым л ps сменит свое значение с «I» на «О».

Образуем максимальные совместимые группы членов ЛСА (3.8). Для этого возьмем оператор Ац и

припишем справа его последователь Ау->[Рг]. Так как Fi не совместим с Ау (см. табл. 4.12), то ветвь обрывается на предыдущем члене (т. е. Ло), а оператор F, указывается в квадратных скобках. Поскольку у Ao имеется только один последователь, группа MAo состоит из одного оператора Ао, т. е. МАо={Ао-> [Fi]}.

Условимся, что члены, указанные в квадратных скобках, не входят з данную группу, а являются начальными членами других групп. Образуем остальные максимальные совместимые группы, при этом стрелка со знаком «+» после pi означает, что pi=1, а со знаком «-» pi=0;

Таблица 4.И

Таблица 4.13-

Как было ранее отмечено, операторы Ао и Aк объединяются в одну микрокоманду, т. е.

\MA0.Ah ={4>(Л)-Ч]>-

Таким образом, получено шесть микрокоманд, т. е. шесть внутренних состояний МА.

Пример 4.8. Пусть задана ЛСА (4.1), в которой различные вхождения одного и того же ЛУ пронумерованыразличными верхними индексами:

«=Т1 Рг Т3Р2Т2АРз Т2 А3ш Т3 !2 Аг IsPi Т1 At Р* f р\ Т4/р514 А, Л,ш Т111 А-0 и Т1 .

(4.1)

Исходя из анализа операторов ЛСА (4.1), рассмотренный в [2], выявлены операторы, которые можно реализовать одновременно. Информацию о возможности одновременного выполнения операторов представим в виде табл. 4.13.

Из рассмотрения функции, выполняемых операторами и ЛУ ЛСА (4.1), выявлены такие распределения сдвигов:

В группе ма, можно было бы продолжить составление группы после А5, так как p1 не входит в распределения сдвигов операторов А4 и A5. Однако здесь выписывание этой группы прерывается, так как уже имеется группа Мр1.

Таким образом, в данном примере получено восемь групп, а следовательно, восемь микрокоманд, причем для каждого последователя последних членов любой ветви этих микрокоманд имеется микрокоманда, в которой он будет первым членом. Поскольку все члены ЛСА (4.1) выписаны в этих восьми группах, полученная система микрокоманд является полной.