Визначення закону функціонування Автомату Мілі

Нехай мікропрограма задана у виді закодованого графа (рис. 7.1, а) і для її інтерпретації використовується автомат Мілі з законом функціонування

A (t+1)=[А (t), X (t)];

Y (t)=[A (t), X (t)]

Де А={а₁, а₂..., а_n} — множина станів автомату, t=0, 1, 2,... і А (0)=a₁ — початковий стан автомату. Мікропрограма оперує з чотирма логічними умовами X={x₁,..., x₄} і п'ятьма мікроопераціями Y= {y₁,..., y₅} Тому автомат, що реалізує цю мікропрограму, повинен мати чотири входу x₁,..., x₄ і п'ять виходів y₁,..., y₅. Необхідний набір станів автомату визначається шляхом позначки графа мікропрограми, що виробляється в наступному порядку:

1) символом a₁ відмічається вхід першої верхівки, наступної за початком, а також вхід кінцевої верхівки;

Рис. 7.1. Граф мікропрограми і відповідний їй граф автомату Мілі

2) входи верхівок, наступних за операторними верхівками, відмічаються символами a₂, a_3,...

3) входи двох різних верхівок, за винятком кінцевої, не можуть бути відмічені однаковими символами;

4) вхід верхівки може визначатися тільки одним символом. Приклад позначки графа мікропрограми станами a₁, a₂,..., a₆ автомату наведений на рис. 7.1, а. Припускається, що в початковому стані a₁ автомат формує нульові значення на всіх виході y₁,..., y₅ По закінченню роботи автомат вертається в цей же стан a₁.

Перехід по графу мікропрограми з позначки а_i, в позначку a_j в напрямку дуг графа визначає шлях

(1)

Де якщо шлях проходить через вихід умовної верхівки х, відмічений значенням 1, і , якщо шлях 'проходить через вихід, відмічений значенням 0; y_a y_b,..., y_— множина мікрооперацій, означена в єдиній операторній верхівці, через яку проходить даний шлях. Наприклад, на графі рис. 7.1, а з позначки а₁ в позначку а₂ можна перейти двома шляхами: а_{1 1}у₁у₂а₂ і а₁х₁у₂а₂ А з позначки а₂ в а₄-по єдиному шляху a₂x₂x₃y₁y₄a₄. Шлях, що не проходить через умовні верхівки, містить порожню множину логічних умов a_iy_ay_b ... y_a_j. Деякі шляхи, ведучі до позначки а₁ — кінцевої верхівки графа, можуть містити порожню множину мікрооперацій:

(2)

Очевидно, що увся множина шляхів виду (1) або (2) визначає множину переходів між станами a_i і a_j, автомату Мілі.

Якщо станам а₁, а₂,..., a_n поставити в відповідність верхівки графа, а шляхам (1) і (2)-дуги, спрямовані з верхівки а_i в верхівку a_j і відмічені наборами значень вхідних і вихідних сигналів, те отриманий граф буде визначати закон функціонування автомату Мілі. Так, граф мікропрограми рис. 7.1, a породжує автомат Мілі з законом функціонування рис. 7.1, б. Помітимо, що дуги на графі автомату відмічаються тільки тими вхідними сигналами X, що визначають можливість переходу з стану a_i в стан a_j і тими вихідними сигналами У, що в даній ситуації приймають значення 1. При Цьому припускається, що всі інші вихідні сигнали мають нульове значення.

Коли автомат не працює (мікропрограма не виконується), він знаходиться в початковому стані a1 При запуску (ініціюванні мікропрограми) автомат зберігає стан а₁ на пртязі одного такту, за час якого виконуються мікрооперації, відповідні поточним значенням вхідних сигналів X. По закінченню першого такту автомат перемикається в черговий стан a_j, що передбачаеться законом функціонування, і в ОА починає виконуватися наступний набір мікрооперацій. Момент закінчення мікропрограми відмічається поверненням автомату в початковий стан a₁.

Для запуску автомату використовується спеціальний сигнал B, що відноситься до групи вхідних сигналів і має тривалість, рівну такту. Щоб виключити можливість появи вихідних сигналів y в моменти, коли автомат знаходиться в стані a₁ і не працює, дугам, вихідним з верхівки a₁ додатково приписується пускаючий сигнал В (рис. 7.1, б), тільки при одиничному значенні якого вихідним сигналам У присвоюється значення 1 і стає можливим перехід автомату в наступний стан. При В=0 автомат зберігає початковий стан і всі вихідні сигнали мають нульові значення. Введення сигналу В в закон функціонування автомату відповідає включенню верхівки ,що чекає В в граф мікро-

Рис. 7.2. Засіб введення додаткових станів

програми (рис. 7.1, в), з допомогою якої відзначається той факт, що виконання мікропрограми починається тільки при В=1.

Автомат Мілі може інтерпретувати мікропрограму коректно тільки в тому випадку, якщо для всіх переходів виду (1) виконується умова незалежності логічних умов x_, x_,..., x_ від результатів виконання мікрооперацій y_, y_,..., y_.

Умова незалежності порушується, якщо на деякому переході a_ix_x_ ... x_y_ay_b ... y_a_j спостерігається функціональна залежність x_=f (y_r). В такому випадку виконання мікрооперації у_r може призвести до модифікації значення умови x_, і автомат, реагуючи на новий набір вхідних сигналів, сформує набір вихідних сигналів, не відповідний мікропрограмі. Для запобігання цьому негативному ефекту необхідно проаналізувати всі переходи, що мають місце в автоматі, виявити-вхідні сигнали x_, x_,..., x_ що залежать від мікрооперації. Що породжуються ними, і структурними засобами виключити вплив цих сигналів на процес виконання мікрооперацій. Для цієї мети можна використати наступні засоби: 1) запам'ятовування значень сигналів x_, x_,..., x_ на проміжок часу, рівний тривалості такту; 2) введення в автомат додаткових станів; 3) реалізація автомата по схемі Мура.

Запам'ятовування сигналів x_, x_,..., x_ виробляється на тригерах, що перемикаються в стані x_, x_,..., x_ в кінці такту, водночас з переключенням автомату в новий стан. Порядок введення додаткових станів ілюструється рис. 7.2, а. Припускається, що x_=(y_a, y_b) т. т. умова незалежності для даного фрагменту мікропрограми порушується. Як видно з рис. 7.2, б, додаткові стану а_r і a_l виключають можливість переключення сигналів y_a і у_b при модифікації значення x_. Введення додаткових станів наводить до додаткових затрат обладнання і збільшує час виконання мікропрограмми. Реалізація останнього засобу розглядається нижче.