АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Табличный метод структурного синтеза конечных автоматов

Читайте также:
  1. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  2. I. Методические основы
  3. I. Предмет и метод теоретической экономики
  4. II. Метод упреждающего вписывания
  5. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
  6. II. Методы непрямого остеосинтеза.
  7. II. Проблема источника и метода познания.
  8. II. УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА ДИСЦИПЛИНЫ
  9. III. Методологические основы истории
  10. III. Предмет, метод и функции философии.
  11. III. Социологический метод
  12. III. УЧЕБНО – МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО КУРСУ «ИСТОРИЯ ЗАРУБЕЖНОЙ ЛИТЕРАТУРЫ К. XIX – НАЧ. XX В.»

Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении функции возбуждения каждого элементарного автомата и функций кодированных выходов заданного автомата. На этапе структурного синтеза выбираем способ кодирования состояний, входных и выходных сигналов автомата, в результате чего составляют кодированные таблицы переходов и выходов. Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов.

Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов.

Пример 6.1. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:

xj /ai a0 a1 a2
x1 a1/y1 a1/y2 a1/y2
x2 a2/y3 a2/y3 a0/y1

В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ.

A = {a0, a1, a2}; X = {x1, x2}; Y = {y1, y2, y3}. Здесь M + 1 = 3; F = 2, G = 3.

1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов:

= 2,

= 1,

=2.

Таким образом необходимо иметь два элементарных автомата Q1 и Q2, один входной канал a и два выходных канала z1 и z2 (каналы a и z называют еще физическими входами и выходами автомата соответственно).

2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.

Таблицa кодирования состояний автомата

aj Q1 Q2
a0    
a1    
a2    

Таблицa кодирования входных сигналов

xf O1
x1  
x2  

Таблицa кодирования выходных сигналов

yg z1 z2
y1    
y2    
y3    

Поскольку автомат имеет 3 состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата.

xj /ai      
  01/00 01/01 01/01
  10/10 10/10 00/00

3. Построим кодированные таблицы переходов и выходов. Эти таблицы определяют зависимости состояний элементарных автоматов и выходных сигналов в момент времени (t + 1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t, т.е.:

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

t t + 1
a O1 Q2 z1 z2 O1 Q2
             
             
             
      - - - -
             
             
             
      - - - -

4. Основная задача, решаемая в процессе структурного синтеза –, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построении этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK-триггера. С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения.

В строках этой таблицы записываются значения J и K, обеспечивающие нужный переход. Ниже представлена таблица функций возбуждения.

Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени.

t t + 1
a O1 Q2 J1 K1 J2 K2 O1 Q2
        b   b    
        b b      
      b     b    
      - - - - - -
        b   b    
        b b      
      b     b    
      - - - - - -

Поскольку функции возбуждения J(t) и K(t) определенны в тот же момент времени, что и их аргументы O1(t), Q2(t) и a(t), то эти функции являются переключательными.

В результате мы получим систему переключательных функций z1(t), z2(t), J1(t), K1(t), J2(t) и K2(t), заданных в виде таблиц их истинности.

5. Следующий этап – синтез комбинационной части конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, а переход к заданному базису осуществляют после.

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

, , , , , .

Обычно полученную систему ПФ минимизируют совместно. Однако совместная минимизация всех ПФ представляет собой достаточно трудоемкую и длительную операцию, применимую, в общем случае, при использовании машины. В результате минимизации мы получим следующую схему конечного автомата (рис. 6.2):

Рис. 6.2

Функциональные схемы, получаемые в результате структурного синтеза, в дальнейшем на этапе инженерной доработки подвергаются изменениям. Эти изменения связаны с тем, что добавляются специальные цепи, необходимые для работы разработанной схемы в составе ЭВМ. Например, в схеме регистра сдвига информации добавляется цепь «установка в 0». Другие изменения связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов.

Вопросы к лекции 6:

1. Нарисуйте структурную схему автомата Мили?

2. Чем управляется память в автомате?

3. Как определить количество элементов памяти?

4. Что такое «функции возбуждения»?

5. Что такое «элемент памяти»?

6. Какие состояния называют «запрещёнными»?

7. Как определяется количество входных и выходных каналов?

8. Какая задача решается в процессе структурного синтеза?

 

ЛЕКЦИЯ 7

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)