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 однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.


 

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

26396. Гортань larynx 25 KB
  Остов гортани образован 5 хрящами на которых прикрепляются мышца гортани и глотки: кольцевидный хрящ cartilagо cricoidea гиалиновый состоит из пластинки и дужки. На переднем крае пластинки заметны фасетки для сочленения с черпаловидными хрящами. Черпаловидные хрящи соединяются суставами с пластинкой кольцевидного хряща. Основание хряща соединено связкой с телом щитовидного хряща вершина отогнута вперед.
26397. Грудная клетка и полость 23.5 KB
  Мышечный аппарат грудной клетки представлен дыхательными мышцами которые образуют 2 функциональные группы: вдыхатели инспираторы и выдыхатели экспираторы. Грудная клетка замыкает грудную полость cavum thoracis при этом форма грудной клетки определяет объём грудной полости и как следствие функциональные возможности органов грудной полости прежде всего лёгких и сердца При этом важное значение имеет форма диафрагмы которая отделяет грудную и брюшную полости друг от друга и образует купол вершина которого расположена в плоскости 67...
26398. Дыхательный аппарат apparatus respiratorius 20 KB
  Состав у млекопитающих: носоглотка – гортань – трахея – лёгкие. У птиц: носовая полость – носоглотка – верхняя гортань состоит из 3 хрящей отсутствуют щитовидный и надгортанник – трахея длинная тесно связана с пищеводом – у бифуркации трахеи – нижняя певчая гортань макроскорически прозрачна несколько расширена пузыревидно является резонатором звуков – лёгкие очень компактные и врастают в грудной отдел позвоночника.
26399. Закономерности строения и ветвления сосудов. Круги кровообращения 21.5 KB
  Отработанная венозная кровь собирается в посткапилляры – венулы – вены. Вены снабжены клапанами – складками эндотелия. Все вены объединяются в 2 крупные – краниальную и каудальную полые у которых отсутствуют клапаны впадают в правое предсердие.
26400. Законы биологического развития. Онтогенез и филогенез 21 KB
  Закон взаимосвязи организма и внешней среды закон целостности и неделимости организма: целостность биологических систем поддерживается в процессе развития за счёт интеграции систем закон экономии биоматериала и места основной биогенетический закон Геккель – филогенез определяет онтогенез. Филогенез phylon – род племя – исторический путь развития вида. дифференциации: в процессе развития организма органа ткани или клетки однородные структуры разделяются на обособленные отличающиеся друг от друга части благодаря чему меняются формы...
26401. Застенные железы тонкой кишки 24 KB
  Выводной проток ductus pancreaticus открывается в 12перстную кку: лошадь: объединяется вместе с печёночным протоком в фатеров дивертикул; свинья КРС: расстояние между печёночным и панкреатическим протоками – 35 см; собака: может быть несколько добавочных протоков. и вегетативное печёночное нервное сплетение и выходит общий печёночный проток и лимфатические сосуды в воротах лимфоузел. Пузырный проток соединяется с печёночным образуя желчный проток который идёт в 12перстную кишку. Отток лимфы в поясничную истерну грудной лимфатический...
26402. Зев (fauces) 20.5 KB
  Образован мягким нёбом сверху корнем языка снизу и по бокам небноязычными дужками arcus palatoglossus в виде складок слизистой оболочки соединяющих мягкое нёбо с боковыми поверхностями корня языка. В составе кольца – язычная миндалина tonsilla lingualis в виде углублений слизистой с лимфатическими фолликулами в корне языка непарная нёбная миндалина tonsilla veli palatini на основании мягкого нёба у лошадей и свиней парные нёбные tonsilla palatina по бокам от нёбноязычных дужек и миндалины евстахиевых труб у их оснований.
26403. Зейгоподий грудной конечности и локтевой сустав 22.5 KB
  Последняя находится в редуцированном состоянии Зейгоподий и стилоподий формируют локтевой сустав art. Иннервация: из плечевого сплетения plexus brachialis которое образовано вентральными ветвями смешанных спинномозговых 5 6 7 8 шейных нервов и первых двух грудных: лучевой поверхностныйкожу и глубокий иннервирует только разгибатели локтевой срединный межкостный.
26404. Зейгоподий тазовой конечности и коленный сустав 22.5 KB
  Они формируют с бедренной костью самый сложный сустав в организме коленный art. Сустав характеризуется большим количеством внутрисуставных связок крестовидные менискоберцовые менискобедренная межменисковая. К этому суставу относится коленная чашка patella которая представляет из себя сесамовидную кость которая развилась в сухожилии четырехглавого мускула бедра.