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


 

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

68627. Текстовый процессор Microsoft Word: графика 264.05 KB
  Графическим объектом называют рисунок, который хранится на диске. Для создания простейших графических объектов выберите свободное место и нажмите кнопку вызова панели инструментов рисования (если ее нет в нижней части экрана). Графические объекты, создаваемые инструментами данной панели, имеют характер векторных объектов.
68628. Вычисления в электронных таблицах в MS Excel 91.02 KB
  Все функции несмотря на их разнообразие имеют одинаковый стандартный формат: имя функции и находящийся в круглых скобках перечень аргументов разделенных точками с запятой. Регистр при вводе функции не учитывается. Excel автоматически запишет имя функции прописными буквами.
68629. Построение диаграмм и графиков функций в MS Excel 65.58 KB
  Диаграммы графически представляют данные числового типа широко используются для анализа и сравнения данных представления их в наглядном виде позволяют показать соотношение различных значений или динамику изменения ряда данных. Числовым данным рабочего листа соответствуют элементы диаграммы...
68630. Системы счисления и кодирования; двоичная арифметика 481.18 KB
  Во всех этих числах встречается символ I единица. В этой последовательности десятичная точка запятая отделяет целую часть числа от дробной если число целое точка опускается. Крайний левый разряд числа называется старшим разрядом а крайний правый – младшим разрядом этого числа.
68631. Логические основы ЭВМ 28.37 KB
  Данное практическое занятие содержит информацию об основных понятиях математической логики: логических выражениях и операциях над ними правилах построении таблицы истинности для логического выражения о законах логики приводятся правила преобразования логических выражений.
68632. Текстовый процессор Microsoft Word: основы издательской работы 124.17 KB
  Цель и содержание работы: научиться создавать колонтитулы многоколонный текст и различные стили оформления. Теоретическое обоснование Microsoft Word2007 профессиональный текстовый редактор по своим возможностям приближающийся к настольным редакционно-издательским системам.
68633. MSWord. Автоматизация работы с текстом 898.47 KB
  Цель и содержание работы: Изучить основы интерфейса Microsoft Word2007, основные технологические операции и приёмы работы в среде текстового редактора Microsoft Word2007 для создания разнообразных текстовых документов.
68634. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ В СООБЩЕНИИ 40.59 KB
  Введение понятия количество информации В основе нашего мира лежат три составляющие вещество энергия и информация. А как много в мире вещества энергии и информации Можно измерить количество вещества например взвесив его.
68635. Оформление титульного листа 15.26 KB
  Оформление отчета Цель работы Научиться оформлять отчет о лабораторной работе в соответствии с правилами, принятыми в НГТУ. Изучить работу с автофигурами и основы построения блок-схем в Microsoft Word. Изучить работу со структурой документа в Microsoft Word.