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


 

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

34768. Здоровье как ценность, философия здоровья человека 28.5 KB
  В большинстве стран был принят целый ряд юридических документов государственных масштабов по экологическому контролю за деятельностью промышленных и других предприятий по охране окружающей среды и здоровья человека. сформировался культ здоровья и здорового образа жизни как поощряемого и престижного способа существования. Культ здоровья и здорового образа жизни является жизненно важным делом лишь для очень небольшого количества людей в основном энтузиастов.
34769. Проблема жизни и смерти в духовном опыте человека. Философия о смысле жизни, смерти и бессмертии. Право на смерть 67.5 KB
  Философия о смысле жизни смерти и бессмертии. В чем смысл жизни Постановка проблемы В жизни каждого нормального человека рано или поздно наступит момент когда он задается вопросом о конечности своего индивидуального существования. Наличием такого знания в духовном опыте человека в значительной степени и объясняется острота с которой перед ним встает вопрос о смысле и цели жизни.
34770. Понятие истины. Объективность истины. Принципы: корреспонденции, когеренции и прагматизма. Гносеологическая, логическая и онтологическая формы истины 42.5 KB
  Объективность истины. Гносеологическая логическая и онтологическая формы истины. Абсолютные истины складываются на основе относительных.
34771. Истина как процесс. Диалектика абсолютной и относительной истины 39.5 KB
  Диалектика абсолютной и относительной истины. Конвенциональная концепция истины считает истинное знание или его логические основания результатом конвенции соглашения. Разброс мнений достаточно велик однако наибольшим авторитетом и самым широким распространением пользовалась и пользуется классическая концепция истины берущая свое начало от Аристотеля и сводящаяся к корреспонденции соответствию знания объекту. Классическая концепция истины хорошо согласуется с исходным гносеологическим тезисом диалектикоматериалистической философии о том...
34772. Истина, ложь, заблуждение. Конкретность истины. Ложь «во спасение». Проблема врачебных ошибок 41.5 KB
  Конкретность истины.В философии понятие истины совпадает с комплексом базовых концепций позволяющих различить достоверное и недостоверное знание по степени его принципиальной возможности согласовываться с действительностью по его самостоятельной противоречивости непротиворечивости а также в рамках разведения полезности и бесполезности эффективности и неэффективности. категория истины обладает двойственной характеристикой. уклонение от истины принимаемое нами за истинное суждение; основывается всегда на неверности по существу самих...
34773. Практика как критерий истины. Абсолютность и относительность практики как критерия истины 43 KB
  Абсолютность и относительность практики как критерия истины К сожалению фактически все попытки решить проблему критерия истины не увенчались успехом. следует выделить две особенности практики как критерия истины: 1. Это достигается в процессе материального воплощения мышления в человеческой практики. С его помощью невозможно доказать немедленно непосредственно истинность или ложность тех или иных научных теорий которые выходят за пределы возможностей самой практики обусловленной историческим отрезком времени.
34774. Практика как специфический способ отношения человека к миру. Формы практической деятельности. Специфика медицинской практики 34 KB
  Формы практической деятельности. Интегративные функции практики по отношению к другим формам жизнедеятельности В сфере реального отношения людей к миру к природе к обществу к другим людям формируются исходные стимулы развитии всех форм человеческой культуры. Создаваемые в культуре и в материальном производстве и в регуляции отношений между людьми в обществе и наконец в сфере науки искусства философии способы деятельности возникают но сути своей как ответ па определенные проблемы и задачи связанные с воспроизводством...
34775. Глобальные проблемы современности. Философский анализ и решение. Альтернативы будущего 42.5 KB
  Остановим внимание на названных и в первую очередь на экологической проблеме в силу тех причин что все происходящее на планете Земля с участием человека или без него протекает и в природе. Геосфера поверхность Земли как необитаемая так и пригодная для жизни человека. Ноосфера ноо разум область разумной деятельности человека онрделяемая в конечном счете уровнем человеческого интеллекта и объемом перерабатываемой его мозгом информации. С целью их разгадки все сферы взаимоотношений природы и человека были условно разделены на...
34776. Философия медицины. Антропоцентризм. Духовность и медицина. Проблема человека 42.5 KB
  Это касается и права индивида на свободный личный выбор жизни или смерти. Антропоцентризм предписывает противопоставлять феномен человека всем прочим феноменам жизни и Вселенной вообще. Лежит в основе потребительского отношения к природе оправдания уничтожения и эксплуатации других форм жизни. Понимание основ духовной жизни пациента часто включает в себя и знание его духовного развития.