 |
Структурный этап синтеза автоматов.
|
|
|
|
Исходными данными для структурного этапа являются:
- Абстрактный автомат, заданный виде графа или табличных переходов и выходов.
- Система логических элементов, на которых необходимо реализовать автомат.
- Тип элемента памяти, на котором реализуется автомат.
- Требования, предъявляющиеся к схеме автомата по сложности и (или) быстродействию и так далее.
Результатом этапа является функциональная схема на заданных логических элементах.
На данном этапе автомат рассматривается виде следующей схемы:
КУ – комбинационный узел
БП – блок памяти
ЭП – элемент памяти
X1…Xm – коды (в совокупности код одной буквы входного алфавита)
Z1…Zm – код выходной буквы
Y1…Yk – код состояния автомата
Y11…Yk1
1) X1…Xm – входные переменные структурного автомата, которые обозначают коды символов входного алфавита.
2) Z1…Zm – выходные переменные структурного автомата, которые обозначают разряды кодов символов выходного алфавита.
3) Y1…Yk – внутренние переменные структурного автомата, которые обозначают разряд кода символов состояний.
4) Y11…Yk1 – функции возбуждения элементов памяти структурного автомата.
Между переменными абстрактного и структурированного автоматов существует взаимнооднозначное и структурное соответствие.
Входные алфавиты.
| Абстрактная | Структурная | ||
| 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, δ1 – конкретные значения кодовых комбинаций.
Основные этапы структурного синтеза.
- Кодирование входного и выходного алфавитов (если требуется).
- Кодирование информации может быть опущены, так как в исходных дпнных входы и выходы могут быть закодированы.
- Кодирование состояний абстрактного автомата.
Существует много способов кодирования состояний.
По тому, как будет закодировано состояние, зависит окончательная схемная сложность автомата.
Если автомат имеет m состояний, то длина кода может быть от log2m до m.
- Закодированные значения входных и выходных состояний подставляют в таблицу переходов и выходов и получают кодированную таблицу переходов и выходов, которые описывает уже структурный автомат.
- На основе кодированной таблицы строится система Булевой функции для возбуждения элементов памяти и выходов автомата.
- Совместно минимизируется полученная система булевых функций (пример Карты Карно).
- Построение блока памяти на логических элементах.
- Построение функциональной схемы всего автомата на заданных логических элементах.
Типы памяти.
Триггер – это двоичный элемент памяти. В качестве элементов памяти используется двоичные элементы – триггеры, которые имеют два устойчивых состояния.
Элемент памяти как правило имеет два выхода: прямой и инверсный.
Значение на прямом выходе соответствует коду состояния триггера и как правило выходному сигналу триггера.
Элементом памяти в автомате будем называть автомат Мура, обладающий полной системой переходов и выходов.
Автомат обладает полной системой переходов, если любых пар Si и Sj можно указать сигнал вызвавший переход из Si в Sj.
|
|
|
Автомат обладает полной системой выходов, если каждому состоянию автомата можно приписать выходной сигнал, отличный от выходных сигналов других состояний.
Основные типы триггеров.
Существует 4 основных логических типа триггера:
два одновходовых: «D», «T»
два двухвходовых: «RS», «JK»
- «D» триггер или триггер задержки (delay)
Графическое обозначение:
это автомат Мура (дуги – значения D)
Выходные значения во всех значениях будут совпадать с кодом состояния и будут обозначаться буквой q.
| W(q) | P(D) | 0 | 1 |
| S(q) | |||
| 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 |
Для триггеров удобно использовать иную форму таблицы переходов.
| qt à qt+1 | D |
| 0 à 0 | 0 |
| 0 à 1 | 1 |
| 1 à 0 | 0 |
| 1 à 1 | 1 |
Эта таблица упрощается и приводится к виду:
0
0 à 0 т.е. значение D пишется над стрелкой.
1
0 à 1
0
1 à 0
1
1 à 1
- «T» триггер (Toggle - кувыркаться)
Триггер меняет свое состояние (Т = 1)
| q / T | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| qt à qt+1 | T |
| 0 à 0 | 0 |
| 0 à 1 | 1 |
| 1 à 0 | 1 |
| 1 à 1 | 0 |
0
0 à 0
1
0 à 1
1
1 à 0
0
1 à 1
- «RS» триггер
R – reset – сбрасывает в 0 (00 – хранение предыдущего состояния)
S – set – установка в 1 (11 - запрещена)
R = 1 – сброс
S = 1 – установка
R = S = 0 – хранение
R = S = 1 – запрещена.
* - безразлично чему равен сигнал
| q / RS | 00 | 01 | 10 | 11 |
| 0 | 0 | 1 | 0 | -- |
| 1 | 1 | 1 | 0 | -- |
«--» - запрещенные комбинации
| qt à qt+1 | RS |
| 0 à 0 | *0 |
| 0 à 1 | 01 |
| 1 à 0 | 10 |
| 1 à 1 | 0* |
*0
0 à 0
01
0 à 1
10
1 à 0
0*
1 à 1
- «JK» триггер (jump – установка 1, kill - сброс)
J = 1 K = 0 – установка
J = 0 K = 1 – сброс
J = K = 0 - хранение
J = K = 1 – инверсия
1)
|
00 – хранение
01 - сброс
2) 0 à 1
|
10 – установка
11 - инверсия
3) 1 à 1
*0
4) 1 à 0
*1
| q / JK | 00 | 01 | 10 | 11 |
| 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| qt à qt+1 | JK |
| 0 à 0 | 0* |
| 0 à 1 | 1* |
| 1 à 0 | *1 |
| 1 à 1 | *0 |
0*
0 à 0
1*
0 à 1
*1
1 à 0
*0
1 à 1
|
|
|
