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


 

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

22504. ЧТО ТАКОЕ СТРАТЕГИЧЕСКОЕ УПРАВЛЕНИЕ 343.32 KB
  Сущность стратегического управления Было бы наверно считать что еще 2030 лет назад фирмы совершенно не имели стратегического поведения. Разработка идей стратегического управления нашла отражение в работах таких авторов как Fannhofs и Granger 1971; Schendel и Hatten 1972; Irwin 1974; и др. В качестве ведущей идеи отражающей сущность перехода к стратегическому управлению от оперативного управления явилась идея необходимости переноса центра внимания высшего руководства на окружение для того чтобы соответствующим образом и своевременно...
22505. АНАЛИЗ СРЕДЫ 354.03 KB
  Внутренняя среда организации является источником ее жизненной силы. Она заключает в себе тот потенциал который дает возможность организации функционировать а следовательно существовать и выживать в определенном промежутке времени. Но внутренняя среда может также быть и источником проблем и даже гибели организации в том случае если она не обеспечивает необходимого функционирования организации. И на них претендуют многие другие организации находящиеся в этой же среде.
22506. ОПРЕДЕЛЕНИЕ МИССИИ И ЦЕЛЕЙ ОРГАНИЗАЦИИ 219.47 KB
  Но целевое начало в деятельности организации возникает отнюдь не только потому что ей нужно иметь ориентиры чтобы не погибнуть в изменяющемся окружении. В первую очередь целевое начало в деятельности организации возникает потому что организация это объединение людей преследующих определенные цели. Люди создают организации для того чтобы с их помощью решать свои проблемы.
22507. ЧТО ТАКОЕ СТРАТЕГИЯ ФИРМЫ И КАК ОНА ВЫРАБАТЫВАЕТСЯ 494.62 KB
  Сущность стратегии организации . Выбор стратегии и ее реализация составляют основную часть содержания стратегического управления. Существуют два противоположных взгляда на понимание стратегии. Первое понимание стратегии базируется на следующем процессе.
22508. КОНЦЕПЦИЯ ПРОДУКТА В СТРАТЕГИЧЕСКОМ УПРАВЛЕНИИ 466.76 KB
  Понятие продукта Понятие продукта очень сильно варьируется в зависимости от того кто вкладывает смысл в это понятие в контексте каких процессов оно рассматривается относительно к каким видам продукции применяется и т. Каждое данное понимание продукта отвечает на вопрос о том что делает фирма и принципиально отличается одно от другого в зависимости от того кто и в каком контексте дает ответ. Свой определенный смысл в понимание продукта вкладывает разработчик продукта посвоему смотрит на продукт плановик и наконец свой...
22509. ДИНАМИКА ПРОДУКТА 311.55 KB
  От того как фирма смотрит на производимый ею продукт как она подходит к выработке своей стратегии продукта во многом зависит сумеет ли фирма найти свое место на рынке сможет ли обеспечить себе устойчивые связи с окружением осуществить своевременные и адекватные запросам среды изменения. Но это было статическое рассмотрение продукта. Другим очень важным направлением рассмотрения продукта в стратегическом управлении является его динамическое рассмотрение в соответствии с которым продукт предстает как изменяющееся во времени...
22510. СТРАТЕГИЯ ПРОДУКТА 404.19 KB
  Ответ на эти вопросы относящиеся к стратегии продукта формируется под влиянием нескольких факторов. В первую очередь стратегия продукта зависит от стратегии фирмы. Однако хотя стратегия продукта и является подстратегией общей стратегии фирмы и соответственно определяется характером ее целей и ее стратегией тем не менее можно указать на отдельные факторы оказывающие непосредственное влияние на выработку стратегии продукта.
22511. КАК СТРОИТСЯ ВЗАИМОДЕЙСТВИЕ ЧЕЛОВЕКА И ОРГАНИЗАЦИИ 368.1 KB
  Для того чтобы понять как строится взаимодействие человека с организацией необходимо не только уяснить в чем суть проблемы этого взаимодействия а также то что в личности человека определяет его поведение в организации и какие характеристики организационного окружения влияют на то как происходит включение человека в деятельность организации. Подходы к построению взаимодействия человека и организационного окружения Взгляд на поведение человека в организации может быть осуществлен с двух позиций: с позиции человека взаимодействующего с...
22512. ВХОЖДЕНИЕ ЧЕЛОВЕКА В ОРГАНИЗАЦИЮ 134.02 KB
  Быть членом организации совсем не одно и то же что входить в организацию становиться ее членом. Втретьих это проблема изменений и модификаций в организации которые происходят даже тогда когда организация уже имеет свободное место для человека и сама принимает человека на это место в соответствии с ее потребностями и критериями отбора. От решения данных проблем зависит не только то сможет ли человек войти в организацию но и то как человек будет функционировать в организации как будет строиться его взаимодействие с организационным...