Пам'ять складається з елементарних автоматів Мура П1,....,ПZ,....,ПR. Після вибору елементів пам'яті кожен стан автомата, що синтезується, А кодується набором їх станів. Якщо всі автомати П1...,ПR однакові, що в загальному випадку необов'язкове, то їх число R?logbM, де M – число станів автомата, що синтезується, а b – число станів елементарного автомата пам'яті. Звичне для елементарного автомата b=2, тоді R?log2M.

Наприклад, перехід автомата А, що має 5 елементів пам'яті, алфавіт станів яких – двійковий, з одного стану (Am)=01011 у інше (A3)= 11000, полягає в зміні станів відповідних автоматів пам'яті: перший елемент пам'яті переходить з 0 в 1, другий – з 1 в 1, третій з 0 в 0, четвертий – з 1 в 0, п'ятий - з 1 в 0.

Переходи автоматів пам'яті, відповідні переходам в автоматі А, відбуваються під дією сигналів збудження пам'яті, поступаючих з виходу комбінаційної схеми на вхід пам'яті автомата. Так на рисунку X=(X1,X2,..,XL) і Y=(Y1,Y2,...,YN) – векторні структурні вхідний і вихідний сигнали автомата, U=(U1,U2,...,UT) – векторна функція збудження пам'яті і Q=(Q1,...,QT) – вектор вихідного сигналу зворотного зв'язку від елементів пам'яті автомата.

Якщо не обумовлено особливо, то використовується двійковий структурний алфавіт як для вхідних і вихідних каналів автомата, що синтезується, так і для вхідних і вихідних каналів автоматів пам'яті. Алфавіт станів автоматів пам'яті також звично двійковий.

При побудові функцій збудження пам'яті автомата використовують функцію входів елементу пам'яті (bi,bj), ставлячу у відповідність кожній парі станів (bi,bj) сигнал, який повинен бути поданий на вхід цього автомата для перекладу його із стану bi в стан bj. Функцію входів зручно задавати у вигляді таблиці. Для елементу пам'яті (функція переходів якого приведена раніше) функція входів має вигляд:

Рисунок 1.6 - Таблиця функції входів елемента пам’яті:

звичайна (а) і кодована (б)

1.3 Абстрактний і структурний синтез мікропрограмних автоматів

Граф-схема алгоритму є форма подання мікропрограми, яку повинен виконати операційний пристрій (ОП). При побудові операційного пристрою, що складається з операційного (ОА) і керуючого (КА) автоматів, необхідно вміти виділити функції ОА й КА із ГСА. Звичайно мікропрограма представляється у вигляді змістовної ГСА. У цьому випадку для завдання функцій ОА необхідно перелічити всі виконувані мікрооперації й всі логічні умови, що перевіряються даною мікропрограмою, а також описати розрядність слів, оброблюваних операційним пристроєм. На підставі цих даних можна побудувати ОА. Для ініціалізації виконання тієї або іншої мікрооперації на ОА повинні надходити в потрібний згідно ГСА момент часу керуючі сигнали Yi. Звичайно при проектуванні ОП приймають певний спосіб кодування мікрооперацій (найчастіше кодом, що містить стільки розрядів, скільки всього різних мікрооперацій) і для розробки ОА вважають, що КА видає код мікрооперацій, які повинні виконатися в цей момент часу.

Для КА важлива послідовність видачі відповідних кодів мікрооперацій залежно від логічних умов, вироблюваних ОА й аналізованих КА в потрібні моменти часу. Якщо прийнято спосіб кодування мікрооперацій, то функції КА задаються у кодованій ГСА. Тому для різних змістовних ГСА, що мають однакову кодовану ГСА, ОА будуть різні, але КА буде тим самим.

Надалі будемо розглядати синтез тільки КА й тільки кодованої ГСА.

Кінцевий автомат, що інтерпретує мікропрограму роботи дискретного пристрою, називається мікропрограмним автоматом. Ту саму ГСА можна інтерпретувати як автоматом Мілі, так й автоматом Мура.

Абстрактний синтез мікропрограмного автомата по ГСА здійснюється у два етапи:

1. Одержання відзначеної ГСА.

2. Побудова графа автомата або таблиць переходів і виходів.

Синтез автомата Мілі

На етапі одержання відзначеної ГСА входи вершин, що розміщені за операторними, відзначають символами a1, a2,.. за наступними правилами:

1) символом а1 відзначають вхід вершини, що розміщена за початковою, а також вхід кінцевої вершини;

2) входи всіх вершин наступних за операторними, повинні бути відзначені;

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

4) якщо вхід вершини відзначається, то тільки одним символом.

Ясно, що для проведення оцінок буде потрібно кінцеве число символів а1,...,am. Результатом першого етапу є відзначена ГСА, що є основою для другого етапу - переходу до графа або таблиць переходів-виходів.

На другому етапі, за відзначеною ГСА, будують граф автомата або таблиці переходів-виходів. В автоматі буде стільки станів скільки вершин ai в ГСА.

На площині рисунка відзначаємо всі стани автомата ai. Для кожного зі станів ai визначаємо за відзначеною ГСА всі шляхи, що ведуть в інші стани й проходять обов'язково тільки через одну операторну вершину.

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

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

На підставі відзначеної ГСА або графа автомата можна побудувати таблицю переходів-виходів. Для мікропрограмних автоматів таблиця переходів-виходів будується у вигляді списку й розрізняються пряма й зворотна таблиці.

Структурний синтез мікропрограмних автоматів після одержання графа або таблиці переходів-виходів у принципі аналогічний канонічному методу синтезу цифрових автоматів, розглянутому раніше. Однак існують і певні особливості в першу чергу пов'язані з тим, що для реальних автоматів кількість елементів пам'яті й вхідних сигналів може досягати десяти й більше. Функції збудження й вихідних сигналів важко піддаються мінімізації та й практично мінімізація не дає істотного спрощення цих функцій при великій кількості змінних. Тому мінімізація практично не використається при синтезі мікропрограмних автоматів.

При виконанні структурного синтезу будують так