6 Основные понятия и определения теории абстрактных автоматов (лекция №9)
жүктеу/скачать 417.03 Kb.
|
- Бұл бет үшін навигация:
- 9.2 Пример структурного синтеза синхронного автомата
- В лабораторной работе необходимо выполнить кодирование состояний с помощью эвристического алгоритма.
3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда R = ]log2M[ = ]log25[ =3. Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001. Для удобства кодирования будем иллюстрировать этот процесс картой Карно: 
5. В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его . (В нашем случае = 1). 6. Строим матрицу  , выбрав из  строчки, содержащие .
Пусть B = {1,...,F} – множество элементов из матрицы B = B3 = {2,3} K2 = 000 K3 = 001. 7. Для каждого Kf (f=1, ..., F) найдем  – множество кодов, соседних с  и еще не занятых для кодирования состояний автомата. (Для соседних кодов кодовое расстояние d=1).
K2 = 000  = {100, 010}
K3 = 001  = {011, 101}.
Построим множество 
Если оказывается, что 8. Для каждого кода из множества D находим кодовое расстояние до кода .
K2 = 000 K3 = 001 d(100, 000) = 1 d(100, 001) = 2 d(010, 000) = 1 d(010, 001) = 2 d(011, 000) = 2 d(011, 001) = 1 d(101, 000) = 2 d(100, 001) = 1 9. Находим значение функции w для каждого кода из множества D. 
10. Из множества D выбираем код K, у которого получилось минимальное значение w в п.9. Выбираем код для состояния a1 К1 =100. 
11. Из матрицы вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу . Если в новой матрице не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем:
К2 = 000 = {010}
K3 = 001  = {011, 101}
K2 = 000 K3 = 001 d(010, 000) = 1 d(010, 001) = 2 d(011, 000) = 2 d(011, 001) = 1 d(101, 000) = 2 d(101, 001) = 1 
Выбираем К4 = 101.
К1 = 100  = {110}
K2 = 000  = {010}
К3 = 001 = {011}
К1 = 100 K2 = 000 K3 = 001 d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3 d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2 d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1 
Выбираем К5 = 011. 
Т.к. все состояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров: 
Минимально возможное количество переключений (если бы состояния были закодированы соседним кодированием) 
Коэффициент эффективности кодирования: 
Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм. Необходимо отметить в заключении, что использование алгоритма кодирования обеспечивает наиболее простую с точки зрения реализации схему, но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы – триггеры с двойной памятью: триггеры, управляемые фронтом и т.д..
Шаг 1 - Для упрощения примера кодирование выполняется не эвристическим алгоритмом, а наиболее простым последовательным способом. В лабораторной работе необходимо выполнить кодирование состояний с помощью эвристического алгоритма.
Шаг 2 – Переписывается таблица переходов в закодированном виде, вместо букв состояний подставляются двоичные коды состояний. Данная таблица показывает как должны переключатся триггеры под влиянием входных сигналов автомата.
Шаг 3 – Записывается подграф переходов для триггера (JK, RS, T, D), на котором будет построен автомат. В данном случае будем строить на Т-триггере.
Шаг 4 – Из закодированной таблицы переходов, полученной на шаге 2 и подрафа переходов для триггера (шаг 3) составляется таблица истинности для входных сигналов триггера, т.е. таблица истинности для функции переходов
Шаг 5 – По полученной на шаге 4 таблице строят карты Карно для всех входов триггеров. В данном случае три карты Карно для Т1, Т2, Т3
T1=(nQ2Q3X)U(Q1 nX)U(Q2 nX)
T2=(nQ1Q3)U(Q1 nX)U(Q2 nX)
T2=(Q3x)U(nQ1 X)U(Q1 Q3 nX) Шаг 6 – По таблице выходов строится таблица для получения функции выходов автомата.
y= Q1 nQ2 Q3 Шаг 7 – по уравнениям, полученным на шаге 5 и 6, строится схема автомата, приведенная на рисунке. 
жүктеу/скачать 417.03 Kb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
первую строку, соответствующую закодированным состояниям а2 и а3. Получим матрицу 
, то строим новое множество 
, где 
– множество кодов, у которых 
0
1
0
