22115

Синтез конечных автоматов

Лекция

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

В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени но и от состояния схемы которое в свою очередь определяется значениями входных сигналов поступивших в предшествующие моменты времени. Понятие состояния введено в связи с тем что часто возникает необходимость в описании поведения систем выходные сигналы которых зависят не только от состояния входов в данный момент времени но и от некоторых предысторий т. Состояния как раз и соответствуют некоторой памяти о прошлом...

Русский

2013-08-04

31.5 KB

17 чел.

Лекция 1

Синтез конечных автоматов

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

Введем основные понятия и определения.

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

состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

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

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

Например. В алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1, и т.д.

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

Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

 

 X    y(y1,y2,…,yk)

Автомат функционирует в дискретные моменты времени, интервал между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия  (T = const) и асинхронного действия (T const). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить  целыми не отрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.

 Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, , ), где

A = {a0,a1,a2,...,an} – множество внутренних состояний автомата,

X = {x1, x2,…, xm} – множество входных сигналов (входной алфавит), Xi буква входного алфавита, Y = {y1, y2,…, yk} – множество выходных сигналов (выходной алфавит), - функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находиться в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t)  в момент времени t, т.е. a(t+1) = [a(t),x(t)], - функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t)  в момент времени t, т.е. y(t) = [a(t), x(t)]. Автомат работает следующим образом: в каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0, он всегда находится в состоянии a(t = 0) = a0. В момент времени t автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = [a(t), x(t)] и переходит в следующее состояние a(t+1) = [a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t+1) и y(t). Такие автоматы называют детерминированными. Преобразование информации в детерминированных автоматах подчиняется следующим условиям:

  1.  Любое входное слово длинною l букв, преобразуется в выходное слово той же длины.

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

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

Мы  будем изучать детерминированные автоматы.

Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.

Закон функционирования автоматов Мили описывается следующей системой уравнений:

a(t + 1) = [a(t),x(t)]

y(t) = [a(t),x(t)]   .

t = 0,1,2,3…  

Работа автоматов Мура задается следующими уравнениями:

 

a(t + 1) = [a(t),x(t)]  

   .

y(t) = [a(t)]  

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.


 

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

15209. Сегіз сері (Мұхамедқанапия) Баһрамұлы Шақшақов поэзиясы (1818 - 1854) 83 KB
  Сегіз сері Мұхамедқанапия Баһрамұлы Шақшақов поэзиясы. 1818 1854 Сабақтың мақсаты : 1. Білімділік : Серілер поэзиясы туралы ойларын тереңдету серілерге тән ортақ қасиетті танып білу Сегіз серінің өзіне ғана тән қасиеттерін ерекшелеу ажырату. Өңдерімен жән...
15210. ТАРЛАН ТАЛАНТ ТАҒДЫРЫ 75 KB
  ТАРЛАН ТАЛАНТ ТАҒДЫРЫ Мұқанов Сәбит Мұқанұлы 1900-1973 қазақтың әйгілі жазушысы қоғам қайраткері Қазақ КСР Ғылым академиясының академигі. Туған жері қазіргі Солтүстік Қазақстан облысының Жамбыл ауданындағы Жаманшұбар деген жер. Әке шешеден жастай жетім қа
15211. Сәкен Иманасовтың өлеңдерiн оқудан өрбiген ой 47.5 KB
  Екi тумас ер ақын Сәкен Иманасовтың өлеңдерiн оқудан өрбiген ой Әлемдi билейтiн сөз сөздi билейтiн ақын. Талантпен талғаммен қоса табандылықты азаматтықты қажет ететiн ақын болу қиынның қиыны. Азаматтық жоқ жерде ақындық та жоқ. Төлеген Айбергенов: Ақын болу оң
15212. Сүйінбай Аронұлы 170 KB
  Сүйінбай Аронұлы 1815-1898 Сүйінбай ақын Алматы облысының Жамбыл ауданы Қарақыстақ ауылында дүниеге келген сонда қайтыс болды. Қазақ халқының ақыны айтыс өнерінің шебері. Аронұлы Сүйінбай 1815 1898 қазақтың әйгілі ақыны айтыс өнерінің майталман жүйрігі. Туып өске...
15213. Торайғыров Сұлтанмахмұт 59 KB
  Торайғыров Сұлтанмахмұт 1893-1920 Торайғыров Сұлтанмахмұт қазақ ақыны ағартушы қоғам қайраткері ойшыл. Солтүстік Қазақстан облысының Уәлиханов ауданында туған. Торайғыровтың 3 жасында шешесі қайтыс болып 6 жасына дейін әжесінің тәрбиесінде болды. Кейін әкес
15214. Төлеген Айбергенов 62 KB
  Төлеген Айбергенов Сағындым жаным мен сені Көркіңді жүрген қуаныш қылып мендей ме екен бар ағаң Шын інім болсаң бас бұрма жаным өсек ғайбатқа бораған. Қажет жерінде қатыгездік пен қаталдық керек десек те Адамның заңғар ұлылығын сен сағынышымен есепте. ...
15215. Ұлтымыздың Ұстазы - Ахмет Байтұрсынов 314.5 KB
  Ұлттың ұлы ұстазы: А.Байтұрсынұлының 130 жылдығына арналған әдістемелік құрал / ҚМРБК Құраст. А.Байжұманова. Алматы 2003. 46 б. Биылғы жыл халқымыздың көрнекті қоғам қайраткері кешегі Абай Ыбырай Шоқан салған ағартушылық демократтық бағытты ілгері жалғастырушы ір...
15216. Халел Досмұхамедұлы - Мұрат ақын шығармаларын жинаушы һәм зерттеуші 42 KB
  Алаш қайраткерлері ұлтымыздың рухани мұрасын жинауда, жариялауда және зерттеуде маңызды істер атқарғаны белгілі. Олардың бұл саладағы аса нәтижелі жұмыстары – осы халық үшін маңызды мәселенің бастауында тұрғандығымен де бағалы. Айталық, Әлихан Бөкейхан, Ахмет Байтұрсынұлы халық ауыз әдебиеті үлгілерін, Мағжан Жұмабаев Базар
15217. ҚАЛАМ ҚҰДІРЕТІ 69.5 KB
  ҚАЛАМ ҚҰДІРЕТІ Алла тағала берген ақылымен теңіздей терең білімімен уақыттың өзінен озған ғұлама фәниден бақиға аттанарда өсиет айтыпты: Дауыл ма жауын ба сең бе сел ме өрт пе дерт пе... қандай қысылтаяң қиын шақ болса да ең алдымен халықтың қазынасын құтқарыңд