Реферат - Прикладная теория цифровых автоматов. - Темы рефератов - Бесплатные рефераты - Рефераты


    Сочинения | Краткие содержания | Рефераты | Школьные сочинения по литературе |



Рефераты > Темы рефератов > Цифровые устройства > Реферат "Прикладная теория цифровых автоматов."

Рефераты по Цифровые устройства - "Прикладная теория цифровых автоматов."

Страница реферата: 1 2 3 4 5 6 7 8 9


ункции имеем:
.
,
. Следовательно, окончательно имеем:


Для реализации функции по последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента 2ИЛИ ( рис.8 ).
= 4 или 5). Однако ранг схемы увеличился до 7, что приводит к увеличению задержки срабатывания схемы. 1.6. Анализ комбинационных схем.
Задачи анализа КС возникают при необходимости проверить правильность синтеза (на этапе проектирования) или определить БФ, реализуемую КС (при анализе или ремонте схем). Все существующие методы анализа делятся на прямые и косвенные.
В результате анализа КС прямым методом получается множество наборов входных переменных, обеспечивающих заданное значение на выходе, что позволяет записать в алгебраическом виде БФ, реализуемую схемой. К прямым методам относится метод (- алгоритма.
Применение косвенных методов дает возможность определить реакцию схемы на заданный набор входных переменных в статике или проанализировать переходный процесс смены одного входного набора на другой. Примерами косвенных методов анализа, являются методы синхронного и асинхронного моделирования.
Все упомянутые методы анализа являются машинoориентированными, что позволяет выполнить анализ схемы на ЭВМ.
Для всех методов анализа необходимо описать схему в виде схемного списка, в который включается в общем случае следующие данные: номер ЛЭ в схеме; логическая функция, реализуемая ЛЭ; входные переменные для данного ЛЭ. Например, схема представленная на рис.9, может быть описана следующим списком:


1.7. Анализ комбинационных схем методом (-алгоритма.
для простейшего логического элемента 2И, выполняющего функцию Y=X1X2. Таблица истинности для этой функции:

Табл.3 Таблица истинности функции Y=X1X2


={1 1}. На выходе ЛЭ будет 0 при трех наборах, образующих нулевое покрытие:

Это покрытие можно упростить, заметив, что первый набор склеивается со вторым и третьим, т.е.

для основных ЛЭ, представленных ниже в табл. 4.
Таблица 4.

ЛЭ Y Y Y Y Y Y Y

НЕ 2И 2И – НЕ 2ИЛИ 2ИЛИ–НЕ ИСК. ИЛИ 3И – НЕ
X X1 X2 X1 X2 X1 X2 X1 X2 X1 X2 X1 X2 X3
1 0 X 1 1 0 0 1 X 0 0 1 1 1
X 0 X 1 1 1
0 1 1 0 X 1 X 0 0 0 1 0 X X
X 0 X 1 1 0 X 0 X
X X 0
При анализе схемы методом ( - алгоритма, задавшись определенным значением на выходе, заменяют его соответствующим покрытием элемента, формирующего выходной сигнал. В результате этого определяется, какие должны быть сигналы на выходах элементов, подключенных к выходному ЛЭ. В свою очередь, сигналы на выходах этих элементов можно заменить соответствующими покрытиями, т.е. определить значения выходных сигналов для других ЛЭ и т.д. Этот процесс продолжается до тех пор, пока не получатся покрытия, состоящие только из входных переменных, называемых опорными. Совокупность таких покрытий и дает соответствующее покрытие схемы.
Пример анализа КС (рис 9. ) методом ( - алгоритма представлен в табл. 5. В последней колонке этой таблицы приведен оператор подстановки, в результате работы которого сигнал на выходе ЛЭ заменяется соответствующим покрытием. Необходимо обратить внимание, что все значения переменных, записанные в одной строке, должны одновременно быть в наличии для обеспечения заданного значения выходного сигнала. По-
этому, при замене одного из значений в строке соответствующим покрытием, все остальные значения для других переменных в этой строке должны присутствовать совместно с этим покрытием.
На основании полученного единичного покрытия можно записать БФ, реализуемую схемой:

Таблица 5 Анализ схемы методом ( – алгоритма.




В дальнейшем можно сравнить полученную БФ с той, по которой строилась схема и проверить правильность ее построения. При анализе схемы может оказаться, что некоторая переменная, получившая на одном из предыдущих шагов некоторые значения на данном шаге должна принять противоположное значение. Возникшее противоречие говорит о том, что данный путь является тупиковым и его необходимо исключить из дальнейшего рассмотрения. Если ни при одной комбинации входных переменных не обеспечивается значение 1(0) на выходе, то это означает, что схема реализует константу 0(1) соответственно.
1. 8 Анализ КС методом синхронного моделирования.
При данном методе считается, что все ЛЭ переключаются одновременно, без задержки. В результате применения метода определяется установившееся значение сигнала на выходе схемы.
Рассмотрим метод синхронного моделирования на примере схемы ( рис.9 ).
На первом этапе схему разбиваем на уровни и записываем в порядке возрастания уровня уравнения, описывающие функционирование ЛЭ:
Проанализируем схему при подаче на вход набора X1=0, Х2=0, Х3=0, Х4=1, Х5=1. Для этого решаем записанные уравнения в порядке возрастания уравнения. Имеем:
;
;
;
.
Следовательно, при подаче на вход набора {00011}, на выходе будет Y=1. Аналогично можно промоделировать работу схемы при подаче на вход любого другого набора.
1.9 Анализ КС методом асинхронного моделирования.
Реальный ЛЭ переключается за какое-то конечное время, зависящее от технологии изготовления, условий эксплуатации, емкостей нагрузки и т.д. Прохождение сигнала последовательно через несколько ЛЭ будет приводить к накоплению времени задержки и возникновению сдвига во времени выходного сигнала по отношению ко входному. Наличие задержки и порождаемого ею временного сдвига сигналов может приводить к появлению на выходе отдельных ЛЭ и всей схемы в целом кратковременных сигналов, не предусмотренных БФ, реализуемой схемой. Как иллюстрацию, рассмотрим схему рис.11, а .


Рис. 11 а)

Рис. 11 . Статический риск сбоя.
а)- схема, б)- временные диаграммы.
t1-время задержки инвертора
t2-время задержки элемента 2И
, т.е. константу 0 независимо от входного сигнала X. Однако в переходном процессе в результате задержки срабатывания ЛЭ возможна ситуация, когда на обоих входах элемента 2И будут логические единицы, что может привести к появлению на выходе схемы логической 1 (см. рис.11 б). Рассмотренный случай возможен при задержке срабатывания второго элемента больше, чем первого. Такое явление называется риском сбоя. Различают статистический и динамический риски сбоя.
При статическом риске сбоя до и после переходного процесса состояние выходного сигнала одно и то же, а во время переходного процесса возможно кратковременное появление противоположного сигнала.
При динамическом риске сбоя до и после переходного процесса состояния выходного сигнала противоположные, но в переходном процессе выходной сигнал несколько раз меняет свое значение. Динамический риск сбоя возможен в схеме (рис.12 а) при смене набора (Х1=0, Х2=1, Х3=1) на набор (Х1=1, Х2=0, Х3=0) и иллюстрируется диаграммами (рис.12 б).
В данном примере динамический риск сбоя на выходе КС сопровождается статическим на выходе элемента 1. Как видно из временных диаграмм риск сбоя имеет место при наличии определенного временного сдвига между сигналами, поступающими на вход ЛЭ. Нежелательные сигналы на выходе могут и отсутствовать при другом соотношении временных сигналов, однако принципиальная возможность их появления является фактором снижающим надежность работы схемы. Поэтому очень важно уметь обнаруживать и устранять такие явления.

Для анализа процесса переключения КС при смене входных наборов и обнаружения рисков сбоя используется метод асинхронного моделирования. При этом методе считается, что каждый элемент переключается с одинаковой задержкой. Анализ включает такие этапы:
1.Каждому элементу схемы присваивается уровень, причем уровень 1 имеют элементы, все входы которых являются независимыми входами схемы.
2.Записываются уравнения, описывающие каждый ЛЭ в порядке убывания уровня.
3.Для исходного входного набора А(X1, X2, … , Xn ) определяется значение сигналов на выходах всех ЛЭ схемы. Пусть данный набор А заменяется набором В(X1, X2, … , Xn ).
4.Помечаются те уравнения, в правой части которых хотя бы одна из переменных изменила свое значение.
5.Решаются помеченные уравнения в порядке их записи в схеме . После решения уравнение считается непомеченным.
6.Если после решения всех уравнений системы переменные, входящие в левые части уравнений, изменили свои значения, то вновь помечаются те уравнения, в правые части которых входят эти переменные. Затем осуществляется переход к п.5. В противном случае моделирование данного входного набора считается законченным. Выполнение п.5 называется тактом моделирования.
Анализ схемы (рис.13) методом асинхронного моделирования приведен ниже. Для данной схемы входной набор А(1011110) заменяется набором В(1101011).



Рис. 13. Комбинационная схема для метода асинхронного моделирования.
Уравнения, описывающие ЛЭ:

Табл. 6 Таблица моделирования схемы

Выходы Такты моделирования Прим.

0 1 2 3
e6 1 0 1 0 дин.
e5 0 1 0 0 стат.
e4 0 0 0 0
e3 1 0 0 0
e2 1 0 0 0
e1 0 1 0 1
Как следует из результатов моделирования, при смене набора А набором В на выходе элемента 4 имеет место статический риск сбоя, а на выходе схемы - динамический риск сбоя.
Радикальным способом устранения рисков сбоя является введение стробирования для снятия выходного сигнала КС. Стробирующий импульс подается после окончания переходного процесса в КС (т.е. когда на выходе КС уже установилось необходимое значение выходного сигнала), что исключает влияние возможных сбоев на вырабатываемый схемой сигнал.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ АБСТРАKТНЫХ АВТОМАТОВ.
Ознакомившись в курсах "Программирование" и "Машинная арифметика" с принципами работы ЭЦВМ, можно указать на две основные особенности таких вычислительных машин: оперирование данными, представленными в цифровой форме и автоматическая работа по заранее составленной программе. Эти особенности показывают, что любая ЭЦВМ является цифровым автоматом (ЦА). Понятие ЦА служит обобщением для всех видов устройств обработки цифровой информации, имеющих программное управление.
Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воздействием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.
Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстрактный автомат, определенный как 6-компонентный кортеж: S=(A,Z,W,(,(,а1) у которого:
1. A={a1, a2, ... ,am} - множество состояний (внутренний алфавит)
2. Z={z1, z2, ... ,zf} - множество входных сигналов (входной алфавит)
3. W={w1, w2, ..., wg} - множество выходных сигналов (выходной алфавит)
4. ( : A(Z(A - функция переходов, реализующая отображение D( (А(Z в А. Иными словами функция ( некоторым парам состояние - входной сигнал (аm, zf) ставит в соответствие состояния автомата аs= ( (am, zf), as(A.
5. ( : A(Z(W - функция выходов, реализующая отображение D( (А(Z на W. Функция ( некоторым парам состояние - входной сигнал (аm, zf) ставит в соответствие выходные сигналы автомата Wg=((аm, zf) , Wg(W.
6. ai (A - начальное состояние автомата.
Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.

Абстрактный автомат (рис.14) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t) ( Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита W(t)=((a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=([a(t), z(t)], a(t) (A, w(t) (W.
Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Т.о. выходное слово = ((входное слово), где ( - отображение, осуществляемое абстрактным автоматом.
На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рис. 14 ), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.
Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию состояния и входа в данный момент времени.
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).
Закон функционирования автомата Мили задается уравнениями:
a(t+1) = ((a(t), z(t)); w(t) = ((a(t), z(t)), t = 0,1,2,...
Закон функционирования автомата Мура задается уравнениями:
a(t+1)=((a(t), z(t)); w(t) = ((a(t)), t = 0,1,2,...
Из сравнения законов функционирования видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или Мура дополнительно к законам функционирования, необходимо указать начальное состояние и определить внутренний, входной и выходной алфавиты.
Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так называемым С- автоматом.
Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьмикомпонентным вектором S=( A, Z, W, U, (, (1, (2, а1 ), у которого:
1. A={a1, a2, ... ,am} - множество состояний;
2. Z={z1, z2, ... ,zf} - входной алфавит;
3. W={w1, w2, ..., wg} - выходной алфавит типа 1;
4. U={u1, u2,...,uh} - выходной алфавит типа 2;
5. ( : A ( Z ( A - функция переходов, реализующая отображение D( (А(Z в А;
6. (1 : A ( Z ( W - функция выходов, реализующая отображение D(1 (А(Z в W;
7. (2 : A ( U - функция выходов, реализующая отображение D(2 ( А в U;
8. а1 ( А - начальное состояние автомата.
Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов (1 и (2, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а( t + 1) = (( a( t ), z( t )); w( t ) = (1( a ( t ), z( t )); u( t ) = (2( a( t )); t = 0, 1, 2, ...
Выходной сигнал Uh=(2( am ) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=(1( am, zf ) выдается во время действия входного сигнала Zf при нахождении автомата в состоянии am.
Рассмотренные выше абстрактные автоматы можно разделить на:
полностью определенные и частичные;
детерминированные и вероятностные;
синхронные и асинхронные;
Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( ai, zj ).
Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар ( ai, zj ).
К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов : автомат, находящийся в некотором состоянии ai, под действием любого входного сигнала zj не может перейти более, чем в одно состояние.
В противном случае это будет вероятностный автомат, в котором при заданном состоянии ai и заданном входном сигнале zj возможен переход с заданной вероятностью в различные состояния.
Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния. Состояние as автомата называется устойчивым, если для любого состояния ai и входного сигнала zj таких, что (( ai, zj ) = as имеет место (( as, zj ) = as, т.е. состояние устойчиво, если попав в это состояние под действием некоторого сигнала zj, автомат выйдет из него только под действием другого сигнала zk, отличного от zj.
Автомат, у которого все состояния устойчивы - асинхронный.
Автомат называется синхронным, если он не является асинхронным.
Абстрактный автомат называется конечным, если конечны множества А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат носит название инициального, если в нем выделено начальное состояние a1.
СПОСОБЫ ОПИСАНИЯ И ЗАДАНИЯ АВТОМАТОВ.
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, (, (, а1 ). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций ( и ( ( следовательно и всего автомата в целом ) наибольшее распространение получили табличный и графический.
При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов ) задает функцию (, т.е. a( t +1) = (( a( t ), z( t )) ( табл.7), вторая (таблица выходов ) - функцию (, т.е. W( t )=(( a( t ), z( t )) ( табл. 8 ).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке - один входной сигнал из множества Z. На пересечении столбца am и строки zf в табл.7 записывается состояние as, в которое должен перейти автомат из состояния am под действием входного сигнала Zf, т.е. as = ((am, zf). На пересечении столбца am и строки zf в табл.8 записывается выходной сигнал Wg, выдаваемый автоматом в состоянии am при поступлении на вход сигнала zf, т.е. Wg = (( am, zf ).
Для приведенных таблиц множества, образующие автомат A={a1, a2, a3,a4}, Z={z1, z2}, W={w1, w2, w3, w4, w5}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл.9), в которой каждый элемент as / wg записанный на пересечении столбца am и строки zf, определяется следующим образом:

as=((am, zf); wf=((am, zf).
Автомат Мура задается одной отмеченной таблицей переходов (табл.10), в которой каждому столбцу приписаны не только состояние am , но еще и выходной сигнал Wg, соответствующий этому состоянию, где Wg=((am).

Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.
Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.11) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом ui выходного алфавита типа 2 (табл.12)

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал Zf(Z, вызывающий данный переход as=((am,zf). Для графа автомата Мили выходной сигнал wg(W, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Граф С- автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов
(табл. 7(12) представлены на рисунках 15,16,17.


СВЯЗЬ МЕЖДУ МОДЕЛЯМИ МИЛИ И МУРА.
Рассмотрим некоторый автомат Мили, заданный таблицами переходов и выходов. Таблица переходов а) и выходов б) автомата Мили

Подадим на вход автомата, установленного в состояние а1, входное слово (=z1 z2 z2 z1 z2 z2. Так как ((а1, z1) = a2, ((a1, z1) = W2, то под воздействием входного сигнала z1 автомат перейдет в состояние а2 и выдаст на переходе выходной сигнал W2. Затем, находясь в состоянии а2 под воздействием сигнала Z2 перейдет в состояние а1=((а2, z2) и выдаст сигнал W1=((a2, z2) и т.д. В табл. 13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово (, и выходные сигналы, вырабатываемые на этих переходах.

Назовем выходное слово ( = ( (a1, () реакцией автомата Мили в состоянии а1 на входное слово (.
В нашем случае ( = w2 w1 w2 w2 w1 w2
Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.

В общем виде поведение автомата Мили, установленного в состояние am, можно описать следующим образом (табл. 14).

Аналогично можно описать поведение автомата Мура, находящегося в состоянии a1, при приходе входного слова
( = Zi1, Zi2, . . . , Zik ,учитывая, что W( t ) = ((a( t )):
Очевидно, что для автомата Мура выходной сигнал Wi1= ((am) в момент времени i1 не зависит от входного сигнала Zi1 и определяется только состоянием am. Следовательно, сигнал Wi1 никак не связан с входным словом (.
В связи с этим под реакцией автомата Мура, установленного в состояние am, на входное слово ( = Zi1, Zi2, . . . , Zik будем понимать выходное слово той же длины ( = ((am, () = Wi2 Wi3 ...Wik+1, сдвинутое по отношению к ( на один такт.
Рассмотрим пример. Пусть задан автомат Мура:
Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: (=z1 z2 z2 z1 z2 z2. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:

Сравнивая реакции автомата Мили (табл. 13) и автомата Мура (табл.15), отмечаем, что эти реакции на одно и то же слово ( совпадают. Следовательно автоматы Мили и Мура реализуют одно и то же преобразование слов входного алфавита. Такие автоматы называются эквивалентными. Строгое определение эквивалентности следующее:
два автомата с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установки их в начальное состояние их реакции на любое входное слово совпадают.
Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.
Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал Wg, записанный рядом с вершиной as исходного автомата Мура, перенести на все дуги, входящие в эту вершину. На рис. 18 приведен граф автомата Мили, эквивалентного автомату Мура (рис. 16)

Легко убедиться, что полученный автомат Мили действительно эквивалентный исходному автомату Мура. Для этого достаточно рассмотреть реакцию обеих автоматов на произвольную входную последовательность, что предлагается выполнить самостоятельно. Необходимо также отметить, что в эквивалентном автомате Мили количество состояний такое же, как и в исходном автомате Мура.
Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Как и в предыдущем случае, переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние ai исходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние ai. Рассмотрим переход от автомата Мили Sa к автомату Мура Sb на примере автомата (рис. 15).
Как следует из рис. 15 для автомата Sa при попадании в состояние а1 вырабатываются выходные сигналы W2, W4, W5, при попадании в а2 – W1, W2, a3 – W2, a4 – W3. Каждой паре состояние ai - выходной сигнал Wj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние bk эквивалентного автомата Мура Sb с тем же выходным сигналом Wj : b1 = (a1, W2), b2 = (a1, W4), b3 = (a1, W5), b4 = (a2, W1), b5 = (a2, W2), b6 = (a3, W2), b7 = (a4, W3), т.е. каждое состояние ai автомата Мили порождает некоторое множество Ai состояний эквивалентного автомата Мура: A1 = { b1, b2, b3 }, A2 = { b4, b5 }, A3 = { b6 }, A4 = { b7 }. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа Sb поступаем следующим образом. Т.к. в автомате Sa есть переход из состояния а1 в состояние а2 под действием сигнала z1 с выдачей W1, то из множества состояний A1 = {b1, b2, b3}, порождаемых состоянием а1 автомата Sa в автомате Sb должен быть переход в состояние (a3, W2) = b6 под действием сигнала Z2 и т.д. Граф эквивалентного автомата Мура представлен на рис.19.

Если от автомата Мура Sb, эквивалентного автомату Мили Sa (рис. 19) вновь перейти к автомату Мили, то получим автомат Мили S1 (рис. 20)

Вследствие транзитивности отношения эквивалентности два автомата Мили S1 и Sa также будут эквивалентными, но у последнего будут на 3 состояния больше. Т.о., эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.
МИНИМИЗАЦИЯ ЧИСЛА ВНУТРЕННИХ СОСТОЯНИЙ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ АВТОМАТОВ.
Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.
Основная идея этого метода заключается в разбиении всех состояний исходного абстрактного автомата на попарно непересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Т.о. получающийся в результате минимальный автомат имеет столько состояний, на сколько классов эквивалентности ра


Страница реферата: 1 2 3 4 5 6 7 8 9



Рефераты > Темы рефератов > Цифровые устройства > Реферат "Прикладная теория цифровых автоматов."

Рефераты по Цифровые устройства - "Прикладная теория цифровых автоматов."