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


 

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

36430. Государственные природные заказники России: статус, режим, функции, задачи, перспективы развития ФЗ и РЗ 26 KB
  Государственными природными заказниками являются территории акватории имеющие особое значение для сохранения или восстановления природных комплексов и их компонентов и поддержания экологического баланса. Режим особой охраны территорий государственных природных заказников 1. На территориях государственных природных заказников постоянно или временно запрещается или ограничивается любая деятельность если она противоречит целям создания государственных природных заказников или причиняет вред природным комплексам и их компонентам. На...
36431. История заповедного дела 26.5 KB
  Большое значение для расширения заповедного дела имел Декрет Совета Народных Комиссаров СССР от 16 сентября 1921 года Об охране памятников природы садов и парков заложивший основы классификации ОПТ. Улучшению работы по формированию ОПТ способствовало принятие федеральных законов Об охране окружающей природной среды 1991 и Об особо охраняемых природных территориях 1995 Сеть ОПТ области формировалась в течение почти 80 лет . Штильмарк выдвинули концепцию в соответствии с которой каждый регион должен обладать системой ОПТ. Впервые...
36432. Туристский спрос и предложение 30.5 KB
  Предложение туристского продукта зависит от многих факторов: количества туристских поставщиков предприятия размещения питания развлечений и т. Компоненты предложения определенного туристского региона могут быть разбиты на 4 основные категории: 1 природные ресурсы 2 инфраструктура 3 материальнотехническая база туризма которая включает: туроператоров и турагентов предприятия размещения предприятия питания и торговли автотранспортные предприятия и т. В состав материальнотехнической базы туризма входят: туроператоры и турагенты...
36433. Понятие туристского продукта, его жизненный цикл 34 KB
  Маркетинг в туризме как раз нацелен на изучение совокупного продукта различных сфер деятельности. Началом стадии внедрения продукта на рынок считается момент когда туристское предприятие впервые предложило его целевой аудитории. Основной характерной чертой этой стадии является медленный темп сбыта продукта и как следствие полное отсутствие или наличие незначительной прибыли.
36434. Категории производственных ресурсов туристского продукта. Ограниченность ресурсов 25.5 KB
  Ограниченность ресурсов Производство туристского продукта требует ресурсов. Существуют три основные категории производственных ресурсов или факторов производства: природные и культурноисторические людские капитальные. Большинство природных ресурсов истощаются в процессе туристской эксплуатации.
36435. Экологический туризм: предпосылки и особенности развития 29.5 KB
  Предпосылки зарождения экологического туризма Ведущая среди основных причин зарождения экологического туризма – это усиливающаяся изза массовости туризма нагрузка на природные и культурноисторические ресурсы. По мере роста глобализации мирового хозяйства росли и негативные изменения в геосфере Земли: – климатические изменения; – деградация почвы; – разрушение экосистем и уменьшение биологического разнообразия; – увеличение загрязнения воды почвы и воздуха; – природные бедствия вызванные деятельностью человека; – неконтролируемый прирост...
36436. Рекреациооные ресурсы 32.5 KB
  К рекреационным ресурсам относятся: природные комплексы и их компоненты рельеф климат водоемы растительность животный мир; культурноисторические достопримечательности; экономический потенциал территории включающий инфраструктуру трудовые ресурсы. Рекреационные ресурсы это совокупность элементов природных природнотехнических и социальноэкономических геосистем которые при соответствующем развитии производительных сил могут быть использованы для организации рекреационного хозяйства. Рекреационные ресурсы кроме природных...
36437. Эстетическая привлекательность ландшафтов 31 KB
  Современные подходы к оценке эстетической привлекательности ландшафтов. Объективистский подход предполагает выявление объективных критериев эстетической привлекательности кроющихся в физиономических характеристиках самого ландшафта субъективный же указывая на субъективную природу красоты исследует особенности ландшафтноэстетических предпочтений у разных групп людей.Объективистский подход к оценке эстетической привлекательности ландшафтов является в настоящее время наиболее признанным и распространенным. Также к его недостаткам...
36438. Виды воздействия рекреационной деятельности на ОС 25.5 KB
  Ранее исследованиям по анализу туристской деятельности уделялось мало внимания да и то рассматривали воздействие туризма только в определённых точках земного шара или воздействие отдельных его видов. Воздействие туризма на окружающую среду может быть прямым косвенным и побудительным а также положительным и отрицательным. Туризм не может развиваться без взаимодействия с окружающей средой однако с помощью управления развитием туризма и чёткого планирования возможно уменьшить негативное воздействие и увеличить положительное. Положительное...