22112

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

Лекция

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

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

Русский

2013-08-04

75.5 KB

2 чел.

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


 

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

19342. КЭШ-ПАМЯТЬ 159 KB
  АК ЛЕКЦИЯ № 19 КЭШПАМЯТЬ Кэшпамять Как уже отмечалось в качестве элементной базы основной памяти в большинстве ВМ служат микросхемы динамических ОЗУ на порядок уступающие по быстродействию центральному процессору. В результате процессор вынужден простаивать не
19343. АРХИТЕКТУРЫ С ПОЛНЫМ И СОКРАЩЁННЫМ НАБОРОМ КОМАНД 158.5 KB
  АК ЛЕКЦИЯ № 20 АРХИТЕКТУРЫ С ПОЛНЫМ И СОКРАЩЁННЫМ НАБОРОМ КОМАНД Современная технология программирования ориентирована на языки высокого уровня ЯВУ главная задача которых облегчить процесс написания программ. Более 90 всего процесса программирования осуществл...
19344. КОНВЕЙЕРНАЯ АРХИТЕКТУРА 146 KB
  АК ЛЕКЦИЯ № 21 КОНВЕЙЕРНАЯ АРХИТЕКТУРА Конвейерная обработка данных. Что необходимо для сложения двух вещественных чисел представленных в форме с плавающей запятой Целое множество мелких операций таких как сравнение порядков выравнивание порядков сложение ман
19345. СУПЕРСКАЛЯРНЫЕ ПРОЦЕССОРЫ 306.5 KB
  АК ЛЕКЦИЯ № 22 СУПЕРСКАЛЯРНЫЕ ПРОЦЕССОРЫ Суперскалярные процессоры Поскольку возможности по совершенствованию элементной базы уже практически исчерпаны дальнейшее повышение производительности ВМ лежит в плоскости архитектурных решений. Как уже отмечалось од
19346. VLIW – ПРОЦЕССОРЫ. НЕТРАДИЦИОННЫЕ АРХИТЕКТУРЫ 354 KB
  АК ЛЕКЦИЯ № 23 VLIW – ПРОЦЕССОРЫ. Нетрадиционные архитектуры Вычислительные системы с командными словами сверхбольшой длины VLIW Архитектура с командными словами сверхбольшой длины или со сверхдлинными командами VLIW Very Long Instruction Word известна с начала 80х из ряда универ...
19347. МНОГОЯДЕРНАЯ АРХИТЕКТУРА 277 KB
  АК ЛЕКЦИЯ № 24 МНОГОЯДЕРНАЯ АРХИТЕКТУРА Вычислительные системы класса MIMD Технология SIMD исторически стала осваиваться раньше что и предопределило широкое распространение SIMDсистем. В настоящее время тем не менее наметился устойчивый интерес к архитектурам класс...
19349. Проводниковые материалы 88 KB
  Лекция №2 Проводниковые материалы. Основные электрические параметры металлов Из общего курса физики известно что плотность электрического тока в веществе определяется зарядом q концентрацией n и дрейфовой средней направленной скоростью носителей заря
19350. Материалы используемые в электронных приборах 126 KB
  Лекция №1 Введение Для создания электронных приборов необходимо много различных материалов и уникальных технологических процессов. Современная радиотехника и особенно высокочастотная техника радиосвязь приборы и аппаратура радиоэлектроники требуют б...