Синтез мікропрограмних автоматів

Побудувати операційний автомат, що обчислює кількість парних елементів у двох одномірних масивах (A [n], B [m]).

Мікропроцесорний автомат необхідно реалізувати за схемою Уілкса-Стрінжера у вигляді автомата Мілі.

Оптимальну функціональну схему керуючих частин автомата синтезувати на елементах системи І, АБО, НЕ, RS-, D - тригерах, доповнюючи її необхідними по алгоритму функціональними автоматами.

3.1.1 Змістовна схема алгоритму

До складу змістовної схеми алгоритму (Рис.1) входять операційні та умовні верхівки. Наш алгоритм виконує знаходження кількості парних елементів у двох одномірних масивах розмірністю [n] та [m], використовуючи при цьому чотири (4) умовні верхівки і десять (10) операційних верхівок. Позначення операційних верхівок показано на Рис.2. Позначення умовних верхівок на Рис.3. Перевірка елементів масивів виконується від стовпчика до стовпчика.

3.1.2 Змістовна таблиця кодування операційних та умовних верхівок

Кожна верхівка, чи то операційна чи умовна, кодується. При чому, якщо, мікро операції повторюються і умовні верхівки повторюються, вони кодуються однаково. У даному прикладі мікрооперації повторюються двічі, тому, однакові верхівки ми можемо кодувати одним кодом. Таблиця кодування верхівок зображена у Таблиці1.

Таблиця1

3.1.3 Закодована мікроопераційна схема алгоритму

Закодована мікроопераційна схема алгоритму будується на основі змістовної схеми алгоритму (Рис.1) і таблиці кодування операційних та умовних верхівок (Таблиця 1), шляхом заміни відповідних блоків. Схема алгоритму зображена на Рис.4.

3.1.4 Таблиця кодування мікрокоманд

Складаємо таблицю кодування мікрокоманд. Кожна мікрооперація кодується своєю мікрокомандою. Мікрооперації, які виконуються одна за одною послідовно на протязі одного такту часу, поєднуються до однієї мікрокоманди. У даному прикладі дві мікрооперації (mY₁, mY₂) виконуються одна за одною послідовно. Тому ми поєднуємо їх в одну мікрокоманду. Таблиця кодування зображена в Таблиці 2.

Таблиця 2

3.1.5 Закодована мікрокомандна схема алгоритма

Складаємо закодовану мікрокомандну схему алгоритму (Рис.5). Проставляємо мітки внутрішніх станів автомата Мілі таким чином:

мітки ставляться після кожної мікрокоманди (перед блоком після операційного);

початок та кінець мікрокомандної схеми алгоритму відмічається міткою а₀;

мітки проставляються згідно з порядковим номером;

3.1.6 Основна таблиця автомата (СІ - синхроімпульс)

Будуємо основну таблицю автомата (Таблиця 3). Ця таблиця складається на основі закодованої мікрокомандної схеми алгоритму (Рис.5) В першому стовпчику таблиці записуються усі стани, в яких може знаходитися наш автомат. В першому рядку таблиці записуються способи переходу автомата з одного стану в інший (вхідні сигнали), тобто, чи то буде СІ (той перехід, в процесі якого на шляху не зустрілась жодна верхівка), чи то при переході автомату буде поставлена умова. В клітинках таблиці фіксується, перехід до якого стану здійснюється, і що буде на виході. Наприклад, із стану а₀ автомат може здійснити перехід до стану а₁ і в результаті цього переходу на виході автомата буде Y₁, тобто, автомат виконає ті мікрооперації, які виконуються на протязі одного такту часу (mY₁ і mY₂ закодовані мікрокомандою Y₁), при чому, цей перехід станеться під синхроімпульсним сигналом.

Таблиця 3

3.1.7 Граф-схема переходів

Будуємо граф-схему переходів (Рис.7). Граф-схема будується на основі Рис.5. і Таблиці 3. Кружочками позначаються можливі стани автомата. Стрілки указують на перехід із стану i до стану j. Над стрілкою указується, під яким вхідним сигналом станеться перехід, і, що при цьому буде на виході автомата.

3.1.8 Система рівнянь переходів

Складаємо систему рівнянь переходів. Ця система складається на основі граф-схеми переходів (Рис.7) або основної таблиці абстрактного автомата (Таблиця 3). Сигнал СІ опущений.

3.1 9. Система рівнянь виходів

Складаємо систему рівнянь виходів. Ця система складається на основі закодованої мікрокомандної схеми алгоритму (Рис.5), де Х - вхід,

Y - вихід.

3.1.10 Кодування внутрішніх станів автомата

3.2 Синтез мікропрограмного автомата за схемою Уілкса-Стрінжера у вигляді автомата Мура

Для того, щоб закодувати внутрішні стани автомата, визначаємо кількість необхідних для цього тригерів (n). Кількість тригерів розраховується із співвідношення: log₂ A ? n, де

n - кількість необхідних тригерів;

А - кількість міток а_i (a₀ - a₆)

А = 7log₂ 7 ? nn = 3,Оскільки, нам необхідно 3 тригера, то внутрішні стани автомата будемо кодувати трьох розрядним війковим кодом. Процес кодування зображений в Таблиці 4.

Таблиця 4

3.2.10 Побудова схеми операційного автомата

Операційний автомат складається з трьох (3) частин (Рис.5).

У вхідній частині розташовані три (3) D-тригери, три (3) логічних елементи АБО, на які подається вхідний сигнал, декодер та дві шини, одна з яких необхідна для передачі сигналів, які надходять з декодера, а інша - для сигналів з виходів компаратора.

У перехідній частині автомата виконується перетворення сигнала на протязі одного такту часу. Пройшовши через логічні елементи І та (або) АБО, чи того не роблячи, сигнал змінюється і результат надходить на шину (a_t), відкіля продовжує передаватися до програмованої логічної матриці. Перехідна частина будується на основі системи рівнянь переходів.

Вихідна частина. Ця частина будується на основі системи рівнянь виходів. Тут виконується той самий процес, що й у перехідній частині, тільки сигнали подаються на вихідну шину Y_t, з якої сигнал надходить до вихідної матриці.

3.2.11 Схема операційного автомата