22112

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

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

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

Русский

2013-08-04

75.5 KB

3 чел.

Лекция 15

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

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

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

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

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

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

xj\ai

a0

a1

a2

x1

a1/y1

a1/y2

a1/y2

x2

a2y3

a2/y3

a0/y1

В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. Итак, имеем A={a0, a1, a2}; X={x1, x2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3.

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

R = ]log (n+1)[ = ] log 3[ = 2

L = ]log m[ = ] log 2[ = 1

R = ]log k[ = ] log 3[ = 2.

Таким образом, необходимо иметь два элементарных автомата Q1 и Q2 (т.к. R=2), один входной канал b1 и два выходных канала Z1 и Z2.

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

Сост.элем.авт.

Сост.задан.абстрактн.авт.

Q1

Q2

a0

0

0

a1

0

1

a2

1

0

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

Вх.сигн.структ.авт

Вх.сигн.задан.авт

1

X1

0

X2

1

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

Вх.сигн.структ.авт

Вх.сигн.задан.авт

Z1

Z2

Y1

0

0

Y2

0

1

Y3

1

0

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

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

Xj\ai

00

01

10

0

01/00

01/01

01/01

1

10/10

10/10

00/00

В таблицах кодирования выходные каналы Z1 и Z2 называются физическими выходами автомата.

  1.  Пользуясь таблицами кодирования можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов.

Кодированная таблица переходов определяет зависимость состояний Qi(t+1) элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. Т.е.

  Qi(t+1) = fi[(Q1(t), Q2(t), …, Qr(t),

В кодированной таблице выходов – выходные сигналы Zl(t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t.

1(t)

Q1(t)

Q2(t)

Q1(t+1)

Q2(t+1)

Z1(t)

Z2(t)

0

0

0

0

1

0

0

0

0

1

0

1

0

1

0

1

0

0

1

0

1

0

1

1

-

-

-

-

1

0

0

1

0

1

0

1

0

1

1

0

1

0

1

1

0

0

0

0

0

1

1

1

-

-

-

-

Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t.

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

J

K

Q(t)

Q(t+1)

0

b1

0

0

1

b2

0

1

b3

1

1

0

b4

0

1

1

1(t)

Q1(t)

Q2(t)

Q1(t+1)

Q2(t+1)

J1(t)

K1(t)

J2(t)

K2(t)

0

0

0

0

1

0

b

1

b

0

0

1

0

1

0

b

b

0

0

1

0

0

1

b

1

1

b

0

1

1

-

-

-

-

-

-

1

0

0

1

0

1

b

0

b

1

0

1

1

0

1

b

b

1

1

1

0

0

0

b

1

0

b

1

1

1

-

-

-

-

-

-

Например, переход Q1(t) из 0 в 0 обеспечивается подачей на вход J сигнала 0, а значение сигнала на входе K – безразлично.

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

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

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

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

J1

0

0

b

B

J2

1

B

B

1

1

1

b

b

0

b

b

0

Z1

0

0

B

0

1

1

b

0

K1

B

B

B

1

K2

B

0

B

B

B

B

b

1

b

1

b

B

Z2

0

1

B

1

0

0

b

0

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

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


 

А также другие работы, которые могут Вас заинтересовать

8231. Межпредметные связи в обучении, значение, виды, пути осуществления на уроках(на примере уроков географии) 15.65 KB
  Межпредметные связи в обучении, значение, виды, пути осуществления на уроках(на примере уроков географии) Межпредметные связи согласованное изучение разных учебных предметов. Они позволяют отразить в школьном обучении процесс интеграции раз...
8232. Самостоятельная учебно-познавательная деятельность учащихся: значение, виды самостоятельных работ, условия эффективности 18.64 KB
  Самостоятельная учебно-познавательная деятельность учащихся: значение, виды самостоятельных работ, условия эффективности. К самостоятельной учебно-познавательной деятельности относиться: кружки, практикумы, конференции, консультации, фак...
8233. Сущность понятия учебные достижения. Содержания, формы, виды, методы проверки знаний и умений учащихся 16.24 KB
  Сущность понятия учебные достижения. Содержания, формы, виды, методы проверки знаний и умений учащихся. Установлены следующие педагогические требования к организации контроля за учебной деятельностью учащихся: Индивидуальный характер контроля, осуще...
8234. Характеристика современного процесса воспитания. Его сущность, двусторонний характер, противоречия, закономерности 16.5 KB
  Характеристика современного процесса воспитания. Его сущность, двусторонний характер, противоречия, закономерности. Воспитание - функция общества, явление, возникшее в древние времена. Воспитание - целенаправленный процесс развития человек...
8235. Основные подходы к разработке содержания воспитания в современной педагогике 15.39 KB
  Основные подходы к разработке содержания воспитания в современной педагогике. Метод воспитания - это путь достижения заданной цели воспитания. Это система приёмов и средств, используемых для достижения поставленной цели. Приём воспитания...
8236. Характеристика методов воспитания учащихся. Критерии выбора эффективного использования методов воспитания в педагогическом процессе 19.55 KB
  Характеристика методов воспитания учащихся (по одной из классификаций). Критерии выбора эффективного использования методов воспитания в педагогическом процессе. Метод воспитания - это путь достижения заданной цели воспитания. Это система приёмо...
8237. Основные направления и формы воспитательной работы 18.84 KB
  Основные направления и формы воспитательной работы Основными направлениями, по которым проводится воспитательная работа являются: нравственное, правовое, трудовое, эстетическое и физическое воспитание. Воспитательная работа может проводиться и...
8238. Коллектив как объект и субъект воспитания. Признаки, стадии, средства формирования коллектива учащихся 16.51 KB
  Коллектив как объект и субъект воспитания. Признаки, стадии, средства формирования коллектива учащихся. Коллектив - некая социальная общность людей. По Макаренко признаки коллектива: 1) общность создания ради значимой цели. 2) цель отражается в...
8239. Технология коллективной творческой деятельности 16.39 KB
  Технология коллективной творческой деятельности. Методика КТД. В каждом КТД проявляется коллективное начало, творческое начало. Представляет собой поиск лучших идей. Педагогическая технология - это совокупность и порядок сформирован...