22112

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

Лекция

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

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

Русский

2013-08-04

75.5 KB

4 чел.

Лекция 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». Другие изменения связаны с особенностью физического представления информации в ЦВМ, с особенностями логических элементов и с техническими особенностями логических элементов и с техническими особенностями конечных автоматов.


 

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

75704. Обязанности работников в обеспечении здоровых и безопасных условий труда 11.27 KB
  Обязанности работников в обеспечении здоровых и безопасных условий труда. Законодательство об охране труда предусматривает и обязанности работников. Они обязаны соблюдать нормы правила и инструкции по охране труда устанавливающие правила выполнения работ и поведения в производственных помещениях и на строительных площадках использовать и правильно применять коллективные и индивидуальные средства защиты специальную одежду и обувь маски очки респираторы и др. Если правила по охране труда предусматривают что обязательным условием допуска...
75705. Служба инженера по охране труда на лесохозяйственном предприятии 14.1 KB
  Служба инженера по охране труда на лесохозяйственном предприятии В соответствии со статьей 217 Трудового кодекса Российской Федерации в каждой организации осуществляющей производственную деятельность с численностью более 50 работников создаётся служба охраны труда или вводится должность специалиста по охране труда. В организациях с численностью 50 и менее работников решение о создании службы охраны труда принимает работодатель с учётом специфики деятельности данной организации. В случае отсутствия службы охраны труда специалиста...
75706. Управление риском 11.43 KB
  Методы защиты от опасности на производстве: 1 инженерный метод реализуется путём дистанционного управления опасными и вредными процессами. Приёмы защиты человека от опасности: 1 осуществление организации мер защиты 2 создание техники с максимальным уровнем безопасности 3 средства коллективной защиты 4 разработка средств индивидуальной защиты 5 обучение воспитание психологическое воздействие.
75707. Организация работы уполномоченного (доверенного) лица по охране труда профсоюзной организации предприятия или трудового коллектива 16.38 KB
  Организация работы уполномоченного доверенного лица по охране труда профсоюзной организации предприятия или трудового коллектива. Институт уполномоченных создается для организации общественного контроля за соблюдением законных прав и интересов работников в области охраны труда на предприятиях всех форм собственности независимо от сферы их хозяйственной деятельности ведомственной подчиненности и численности работников. Не рекомендуется избирать уполномоченными работников которые по занимаемой должности несут ответственность за состояние...
75708. Комитет (комиссия) по охране труда л/х предприяти 13.12 KB
  Комитет комиссия по охране труда л х предприятия КОМИТЕТ КОМИССИЯ ПО ОХРАНЕ ТРУДА рабочий орган управления охраной труда в организации обеспечивающий согласованные действия работодателя и работников направленные на создание здоровых и безопасных условий труда в организации Комитеты комиссии по ОТ далее К. В их состав на паритетной основе входят представители работодателей профессиональных союзов или иного уполномоченного работниками представительного органа Если в организации нет ни одной первичной профсоюзной организации то в...
75709. .ОБЩИЕ ПОЛОЖЕНИЯ. 15.12 KB
  Задачи функции и права комитета комиссии по охране труда л х предприятия. Комитет создается на паритетной основе из представителей работодателей и уполномоченных работниками по охране труда и осуществляют свою деятельность в целях организации сотрудничества и регулирования отношений работодателей и работников их представителей уполномоченных.Численность комитета равно удвоенной численности уполномоченных по охране труда от работников. Председателем комитета не может быть избран работник который по своим служебным обязанностям ...
75710. Виды надзора и контроля за обеспечением безопасных условий труда 16.92 KB
  Виды надзора и контроля за обеспечением безопасных условий труда. 41 в том числе право работника на здоровые и безопасные условия труда. В соответствии с Федеральным законом Об основах охраны труда в Российской Федерации Правительство Российской Федерации утвердило Положение о федеральной инспекции труда. Федеральная инспекция труда единая федеральная централизованная система государственных органов осуществляющих государственный надзор и контроль за соблюдением законодательства Российской Федерации о труде и охране труда всеми...
75711. Порядок проведения администр.-общественного контроля (трехступенчатого контроля) за соблюдением безопасности труда на лесохоз. предприятии 16.38 KB
  общественного контроля трехступенчатого контроля за соблюдением безопасности труда на лесохоз. Трехступенчатый контроль в системе управления охраной труда является основной формой контроля представителями работодателя и трудового коллектива учреждения образования за состоянием условий ибезопасности труда на рабочих местах производственных участках и цехах а также соблюдением всеми службами должностными лицами и работниками требований трудового законодательства. Он является важным фактором в системе мероприятий по оздоровлению условий...
75712. Медицинское освидетельствование работников. Предварительные и периодические медицинские осмотры 16.82 KB
  Медицинское освидетельствование работников. Работа по предупреждению производственного травматизма и профессиональной заболеваемости должна начинаться на уровне организаций с проведения предварительных при поступлении на работу а затем и периодических медицинских осмотров работников. В соответствии со статьями 213 266 и 212 Трудового кодекса РФ работодатель обязан проводить обязательные медицинские осмотры обследования отдельных категорий работников за счет средств работодателя. Медицинские осмотры обследования работников занятых на...