Структурный этап синтеза автоматов.

Исходными данными для структурного этапа являются:

1. Абстрактный автомат, заданный виде графа или табличных переходов и выходов.

2. Система логических элементов, на которых необходимо реализовать автомат.

3. Тип элемента памяти, на котором реализуется автомат.

4. Требования, предъявляющиеся к схеме автомата по сложности и (или) быстродействию и так далее.

Результатом этапа является функциональная схема на заданных логических элементах.

На данном этапе автомат рассматривается виде следующей схемы:

КУ – комбинационный узел

БП – блок памяти

ЭП – элемент памяти

X₁…X_m– коды (в совокупности код одной буквы входного алфавита)

Z₁…Z_m– код выходной буквы

Y₁…Y_k– код состояния автомата

Y₁¹…Y_k¹

1. X₁…X_m– входные переменные структурного автомата, которые обозначают коды символов входного алфавита.

2. Z₁…Z_m– выходные переменные структурного автомата, которые обозначают разряды кодов символов выходного алфавита.

3. Y₁…Y_k– внутренние переменные структурного автомата, которые обозначают разряд кода символов состояний.

4. Y₁¹…Y_k¹– функции возбуждения элементов памяти структурного автомата.

Между переменными абстрактного и структурированного автоматов существует взаимнооднозначное и структурное соответствие.

Входные алфавиты.

Абстрактная	Структурная
P = {P1…Pn}	X= {δ1,δ2,…,δn} – множество кодовых комбинаций на входе
P1≡ δ1 – букве соответствует код Pn≡ δn
W = {W1,…,Wl}	Z= {β1,β2…,βl} – множество кодовых комбинаций выходных переменных
W1 ≡ β1 We ≡ βe
S = {S1,…Sm}	Y= {γ1,…,γm} – множество кодовых комбинаций внутри переменной соответствующей состоянию
S1 ≡ γ1 Sm ≡ γm
Sj = φ(Si,Pk)	y1 = φ11(γ1, δ1) … yk = φk1(γi, δi)
Функция перехода Автомат Мура: Wj = ψ(Sj)	Z1 = ψ (γj) … Zm = ψ1m (γj)
Автомат Миля Wj=ψ(Sj , Pk)	Z1=ψ11(γj , γi) … Zm=ψ1m(γj , γi)

γ_j,β₁,δ₁– конкретные значения кодовых комбинаций.

Основные этапы структурного синтеза.

1. Кодирование входного и выходного алфавитов (если требуется).

2. Кодирование информации может быть опущены, так как в исходных дпнных входы и выходы могут быть закодированы.

3. Кодирование состояний абстрактного автомата.

Существует много способов кодирования состояний.

По тому, как будет закодировано состояние, зависит окончательная схемная сложность автомата.

Если автомат имеет mсостояний, то длина кода может быть отlog₂mдоm.

4. Закодированные значения входных и выходных состояний подставляют в таблицу переходов и выходов и получают кодированную таблицу переходов и выходов, которые описывает уже структурный автомат.

5. На основе кодированной таблицы строится система Булевой функции для возбуждения элементов памяти и выходов автомата.

6. Совместно минимизируется полученная система булевых функций (пример Карты Карно).

7. Построение блока памяти на логических элементах.

8. Построение функциональной схемы всего автомата на заданных логических элементах.