Xreferat.com » Остальные рефераты » ПТЦА - Прикладная теория цифровых автоматов

ПТЦА - Прикладная теория цифровых автоматов

13 приведена последовательность состояний, которые автомат проходит, воспринимая входное слово , и выходные сигналы, вырабатываемые на этих переходах.

Назовем выходное слово = (a1, ) реакцией автомата Мили в состоянии а1 на входное слово .

В нашем случае = w2 w1 w2 w2 w1 w2

Как видно, из приведенного примера, в ответ на входное слово длины k автомат Мили выдаст последовательность состояний длины k +1 и выходное слово длины k.

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


Аналогично можно описать поведение автомата Мура, находящегося в состоянии a1, при приходе входного слова

 = Zi1, Zi2, . . . , Zik ,учитывая, что W( t ) = (a( t )):


Входное слово

Zi1

Zi2

Zi3

Z
Последовательность cостояний

am

ai2 =  (am, Zi1 )

ai3 =  (ai2, Zi2 )

ai4 = (ai3, Zi3 )

Выходное слово

wi1 =  (am, Zi1)

wi2 =  (ai2, Zi2)

wi3 =  (ai3, Zi3)

wi4 =  (ai4)



Очевидно, что для автомата Мура выходной сигнал Wi1= (am) в момент времени i1 не зависит от входного сигнала Zi1 и определяется только состоянием am. Следовательно, сигнал Wi1 никак не связан с входным словом .

В связи с этим под реакцией автомата Мура, установленного в состояние am, на входное слово = Zi1, Zi2, . . . , Zik будем понимать выходное слово той же длины = (am, ) = Wi2 Wi3 ...Wik+1, сдвинутое по отношению к на один такт.

Рассмотрим пример. Пусть задан автомат Мура:

Подадим на вход этого автомата ту же последовательность, что и для автомата Мили: =z1 z2 z2 z1 z2 z2. Последовательность смены состояний и вырабатываемых выходных сигналов представлена в таблице:


w1

w2

w3

w4


a1

a2

a3

a4

z1

a2

a3

a4

a4

z1

a4

a1

a1

a1




Сравнивая реакции автомата Мили (табл. 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, b­2, 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-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на - классы эквивалентности.

Разбиение множества внутренних состояний автомата на - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.

Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они называются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автомата Мура определяются аналогично приведенному для автоматов Мили.

Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов :

Из таблицы выходов получаем разбиение на 1-классы эквивалентности 1, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами:

1 = {B1, B2}; B2 = {a1, a2, a5, a6}; B2 = {a3, a4}

Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.17), заменяя в таблице переходов состояния a1 соответствующими классами эквивалентности B1 или B2.


Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности Ci и разбиение 2 = {C1, C2, C3}, где С1 = {a1, a1}, C2 = {a5, a6}, C3 = {a3, a4}. Сравнивая 2 и 1, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 18), опять заменяя в таблице переходов состояния ai соответствующими классами эквивалентности Ci.



Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности Di и разбиение 3 ={ D1, D2, D3}, где D1 = {a1, a2}, D2 = {a5, a6}, D3 = {a3, a4}.

Сравнивая 3 и 2, замечаем, что D1 = C1, D2 = C2, D3 = C3, 3 = 3. Следовательно получили разбиение на - эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса Di по одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={a1, a4, a5}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 16) вычеркиваем столбцы, соответствующие "лишним состояниям" a2, a3, a6. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 19).

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

Структурный синтез ЦА.

Задачи синтеза ЦА.

Канонический метод структурного синтеза ЦА.

Элементарные цифровые автоматы с памятью

(триггерные устройства) и их свойства.

Вслед за этапом абстрактного синтеза автоматов следует этап структурного синтеза, целью которого является построение схемы, реализующей автомат из элементов заданного типа. Если абстрактный автомат был лишь математической моделью, проектируемого устройства, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутренне устройство на уровне логических схем. Основной задачей структурной теории автоматов является разработка общих методов построения структурных схем автоматов.

В отличие от абстрактного автомата, имеющего один вход и один выход, на которые поступают сигналы во входном и выходят в выходном W={W1,..,WG} алфавитах, структурный автомат имеет L входных каналов х1,х2,..,хL и N выходных y1,y2,…,yN на каждом из которых присутствует сигнал структурного алфавита.

Обычно в качестве структурного используется двоичный алфавит.


В этом случае каждому входному сигналу ZF абстрактного автомата соответствует некоторый двоичный вектор (lf1,lf2,..,lfL), где lfL{0,1}.

Очевидно, что для представления (кодирования) входных сигналов Z1,..,ZF абстрактного автомата различными двоичными векторами должно быть выполнено условие

L ] log2F [,

аналогично

N ] log2G [

Например , Z={Z1,Z2,Z3,Z4} W={W1,W2,W3}.

Тогда L log24=2 N log23=2

Закодировать входные и выходные сигналы можно ,например, так:


Z1 = 00 W1 = 00

Z2 = 01 W2 = 01

Z3 = 10 W3 = 11

Z4 = 11

Cледовательно, структурный автомат с двумя входами x1 и x2 и двумя выходами y1 и y2 может быть представлен в виде:



Задача синтеза структуры автомата.


На этапе структурного синтеза предварительно выбираются элементарные автоматы, путем композиции которых строят логические схемы полученных на этапе абстрактного синтеза автоматов Мили и Мура. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.

Рассмотрим канонический метод структурного синтеза при котором используются элементарные автоматы некоторого специального вида – автоматы с памятью, имеющие более одного состояния, и автоматы без памяти – с одним состоянием. Первые автоматы называются элементами памяти, вторые – комбинационные или логические элементы.

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


Для правильной работы схем сигналы на входе запоминающих элементов не должны непосредственно участвовать в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. Поэтому запоминающими элементами должны быть не автоматы Мили, а автоматы Мура. Таким образом, структурно полная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то же время, для синтеза автоматов с минимальным числом элементов памяти, необходимо в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов – полные автоматы.

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

Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний. Т.о. в таком автомате число выходных сигналов равно числу состояний автомата. В связи с этим, в автоматах памяти будем использовать одни и те же обозначения и для состояний, и для выходных сигналов.

Канонический метод структурного синтеза предполагает представление структурной схемы автомата в виде двух частей: памяти и комбинационной схемы.

Память состоит из элементарных автоматов Мура П1,....,ПZ,....,ПR. После выбора элементов памяти каждое состояние синтезируемого автомата А кодируется набором их состояний. Если все автоматы П1...,ПR одинаковы, что в общем случае необязательно, то их число

где M – число состояний синтезируемого автомата А, а b – число состояний элементарного автомата памяти. Обычно для элементарного автомата b=2, тогда .

Например, переход автомата А, имеющего 5 элементов памяти, алфавит состояний которых – двоичный, из одного состояния (Am)=01011 в другое (A3)= 11000, заключается в изменении состояний соответствующих автоматов памяти: первый элемент памяти переходит из 0 в 1, второй – из 1 в 1, третий из 0 в 0, четвёртый – из 1 в 0, пятый - из 1 в 0.

Переходы автоматов памяти, соответствующие переходам в автомате А, происходят под действием сигналов возбуждения памяти, поступающих с выхода комбинационной схемы на вход памяти автомата. Так на рисунке X=(X1,X2,..,XL) и Y=(Y1,Y2,...,YN) – векторные структурные входной и выходной сигналы автомата, U=(U1,U2,...,UT) – векторная функция возбуждения памяти и Q=(Q1,...,QT) – вектор выходного сигнала обратной связи от элементов памяти автомата.

Рассмотрим отдельно элемент памяти Пz, таблица переходов которого дана в таблице. Множество выходных сигналов элементов памяти совпадает с множеством внутренних состояний.


Полнота переходов очевидна из таблицы (в каждом столбце все состояния встречаются). При рассмотрении автомата на абстрактном уровне его можно представить в виде рис.22 а.


При переходе от абстрактного автомата к структурному, входные и выходные сигналы должны быть закодированы наборами сигналов структурного алфавита (входного или выходного соответственно). При двоичном структурном алфавите автомат Пz будет иметь два входных и два выходных канала.

Итак, сами компоненты Uz и Qz при Z = 1,...,R векторов сигналов возбуждения памяти U и сигналов обратной связи от памяти Q также могут быть представлены в виде векторов:

Uz = (UZ1,UZ2,...,UZK) и QZ = (QZ1,QZ2,...,QZR).

Если не оговорено особо, то используется двоичный структурный алфавит как для входных и выходных каналов синтезируемого автомата, так и для входных и выходных каналов автоматов памяти. Алфавит состояний автоматов памяти также обычно двоичный.

При построении функций возбуждения памяти автомата используют функцию входов элемента памяти (bi,bj), ставящую в соответствие каждой паре состояний (bi,bj) сигнал, который должен быть подан на вход этого автомата для перевода его из состояния bi в состояние bj. Функцию входов удобно задавать в виде таблицы. Для элемента памяти (функция переходов которого приведена ранее) функция входов имеет вид:



Если входные сигналы элемента памяти q1,...,qp закодированы наборами (UZ1,...,UZK) сигналов на его входных каналах, то элементами таблицы, задающей функцию входов вместо qi будут соответствующие наборы. Так, если q1 = 00, q2 = 01, q3 = 10, то соответствующая f входов будет иметь вид рис.23a.


Элементарные цифровые автоматы – элементы памяти.


В качестве элементов памяти структурного автомата обычно используются триггеры.

Триггер – это устройство, имеющее два устойчивых состояния, в которые он переходит под действием определённых входных сигналов.

Обычно в триггерах выделяют два вида входных сигналов (и соответственно входов): информационные и синхросигналы.

Информационные сигналы определяют новое состояние триггера и присутствуют в любых триггерах. По типу информационных сигналов осуществляется классификация триггеров: D, T, RS, JK, RST, DV и т.д.

Синхросигнал не является обязательным и вводится в триггерах с целью фиксации момента перехода триггера в новое состояние, задаваемое информационными входами. Обычно, при синтезе ЦА используются триггеры с синхровходом, поэтому в дальнейшем будем рассматривать только такие триггеры.

На синхровход триггера поступают тактирующие импульсы задающего генератора, синхронизирующего работу ЦА. Период следования импульсов соответствует одному такту автоматного времени ЦА.

Рассмотрим основные типы триггеров, используемые для синтеза ЦА: D, T, RS, JK.

D-триггер – элемент задержки – имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт.

Условное обозначение и таблица переходов D-триггера представлена на рис. .


D

Q t

Q t+1

0

0

0

0

1

0

1

0

1

1

1

1




Из приведенной таблицы переходов для данного триггера Qt+1 = f(Qt,Dt) можно получить таблицу функций его входов Dt = (Qt, Qt+1).


Q t

Q t+1

D t

0

0

0

0

1

1

1

Таблица функции входов D-триггера.

0

0

1

1

1


Как видно из таблицы, состояние, в которое переходит триггер (средний столбец), совпадает с поступившим на его вход сигналом D(t) (правый столбец). В связи с этим таблица функций возбуждения памяти синтезируемого автомата с использованием D-триггеров будет полностью совпадать с кодированной таблицей переходов этого автомата. Промышленность выпускает D-триггера в интегральном исполнении. Например,

K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход синхронизации, Q,Q – выходы, Q – прямой, – инверсный. R, S – входы установки в 0 и 1 соответственно. При подаче на вход R и S логического нуля триггер устанавливается в соответствующие состояния независимо от сигнала на входах D и C.


T-триггер – триггер со счетным входом – имеет один информационный вход Т и один выход Q и осуществляет суммирование по модулю два значений сигнала T и состояния Q в заданный момент времени.

Условное обозначение и таблица переходов T-триггера представлена на рис 26.


T

Q t

Q t+1

0

0

0

0

1

1

1

0

1

1

1

0


Таблица переходов T-триггера.



Таблица функций входов триггера Tt = f(Qt, Qt+1) представлена в таблице.


Q t

Q t+1

T t

0

0

0

0

1

1

1

Таблица функции входов T-триггера.

0

1

1

1

0


На основании этой таблицы можно получать функцию возбуждения элементов памяти при синтезе автомата на базе T-триггера. Например, если автомат перешел из состояния ai = 010 в состояние aj = 110, то для обеспечения этого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 T1 = 1,

для второго триггера при переходе из 1 в 1 T2 = 0,

для третьего триггера при переходе из 0 в 0 T3 =0 и т.д.

В чистом виде промышленность не выпускает T-триггера.

RS-триггер – триггер с раздельными входами.

Данный триггер имеет два входных канала R и S и один выходной Q. Вход S (set) называется входом установки в единицу, вход R (reset) – входом установки в нуль. Условное обозначение и таблица переходов RS-триггера представлена на рис. 27.

В таблице переходов при подаче комбинации S = R = 1 состояние перехода

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: