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


 

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

28201. Вклад В.Вундта в оформление психологии как самостоятельной науки. Создание психофизики (Г.Фехнер) 33 KB
  Кризис психологии выявился в наибольшей своей остроте когда сформировалась поведенческая психология рефлексология в России и бихевиоризм в Америке потому что поведенческая психология выдвинув поведение как предмет психологии с особенной остротой выявила кризис центрального понятия всей современной психологии понятия сознания. Согласно Вундту предметом изучения психологии является сознание а именно состояния сознания связи и отношения между ними законы которым они подчиняются. Используя метроном Вундт выделил ряд основных...
28202. Влияние идей И.М.Сеченова и И.П.Павлова на становление отечественной психологии 40.5 KB
  Иван Петрович Павлов 18491936 создатель материалистического учения о высшей нервной деятельности животных и человека. Учение Павлова о высшей нервной деятельности сложилось под влиянием материалистических традиций русской философии и развивало идеи И. В начале своей научной деятельности Павлов занимался преимущественно изучением сердца и кровеносных сосудов. Так было заложено начало павловского учения о трофической нервной системе особых нервных волокнах регулирующих процессы питания в тканях обмен веществ в них и тем самым...
28203. Вклад В.М. Бехтерева в развитие российской психологии 35.5 KB
  Бехтерева в развитие российской психологии. Бехтерев Владимир Михайлович 18571927 русский невропатолог психиатр физиолог психолог. Психологическое творчество Бехтерева можно условно разделить на два этапа. Бехтерев говорил о равноправном существовании двух психологий: субъективной основным методом которой должна быть интроспекция и объективной.
28204. Психофизическая проблема (законы Вебера-Фехнера и Стивенса). Виды порогов и чувствительность 40 KB
  Виды порогов и чувствительность. Для того чтобы измерить уровень абсолютной и дифференциальной чувствительности вводится понятие порогов ощущений или сенсорных порогов. Основной вопрос психофизики это вопрос о порогах. Виды порогов: абсолютный порог верхний и нижний дифференциальный порог оперативный порог.
28205. Особая роль осязания в структуре сенсорной организации человека и его значение в процессах познания и труда (Ананьев, Веккер, Ломов, Ярмоленко) 37.5 KB
  Особая роль осязания в структуре сенсорной организации человека и его значение в процессах познания и труда Ананьев Веккер Ломов Ярмоленко. Базовая роль осязания в процессе чувственной репрезентации Веккер. Восприятие предметов внешней среды с помощью осязания позволяет оценивать их форму размеры свойства поверхности консистенцию температуру сухость или влажность положение и перемещение в пространстве. Связь осязания с основными жизненными функциями и трудом придает ему важное жизненное значение.
28206. Сфера вторичных образов: эмпирические характеристики образа представления 58 KB
  Сфера вторичных образов: эмпирические характеристики образа представления. оно отражает то что когдато отражалось и следы этого образа остались в сознании человека. В отличие от перцептивного образа существенной особенностью которого является выделение фигуры из фона не допускающее однако их взаимного отделения в представлении фигура может не соотноситься с определенной координатой пространственного фона а фон может быть отделен от фигуры пустое пространство . Оно выражается в схематизации образа.
28207. Константность восприятия и ее приспособительное значение 32.5 KB
  Константность восприятия и ее приспособительное значение. Константность это свойство перцептивного образа оставаться относительно неизменным при изменении условий восприятия. Константность относительное постоянство адекватного отражения свойств и качеств объектов в изменяющихся условиях среды; константность всегда предметна. Впервые константность восприятия была поставлена в центр экспериментального исследования в 1889 г.
28208. Целостность восприятия и законы Гештальта: влияние целого на элементы и факторы объединения отдельного в целое 42.5 KB
  Целостность восприятия и законы Гештальта: влияние целого на элементы и факторы объединения отдельного в целое. ЦЕЛОСТНОСТЬ ВОСПРИЯТИЯ свойство восприятия состоящее в том что всякий объект воспринимается как целое даже если некоторые части этого целого в данный момент не могут быть наблюдаемы например тыльная часть вещи. Каждая часть входящая в образ восприятия приобретает значение лишь при соотнесении ее с целым и определяется им. Сам образ восприятия также зависит от особенностей составляющих его частей.
28209. Культурно-историческая психология (Л.С.Выготский, А.Н.Леонтьев) 50 KB
  Важнейшее отличие деятельности человека от поведения животных заключается в использовании человеком орудий труда для преобразования мира и сохранении этих орудий. Центральный момент возникновение символической деятельности овладение словесным знаком. Процесс формирования высшей психической функции отнюдь не мгновенен он растянут на десятилетие зарождаясь в речевом общении и завершаясь в полноценной символической деятельности. Общение со взрослым овладение способами интеллектуальной деятельности под его руководством как бы задают...