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


 

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

32883. Общественное сознание и его структура. Ценности, нравственность, искусство 39.97 KB
  Общественное сознание и его структура. Общественное сознание воззрения людей в их совокупности на явления природы и социальную реальность выраженные в созданных обществом естественном или искусственном языке творениях духовной культуры социальных нормах и взглядах соц. Сознание людей может отставать от общественного бытия и не соответствовать ему. 3 Общественное сознание активно воздействует на всю жизнь общества.
32884. Революция и реформа. Смена лидеров в истории 45.35 KB
  Революция и реформа. Революция радикальное коренное глубокое качественное изменение скачок в развитии общества природы или познания сопряжённое с открытым разрывом с предыдущим состоянием. Социальная революция качественный скачок в развитии общества который сопровождается переходом государственной власти в руки революционного класса или классов и глубокими изменениями во всех сферах общественной жизни. В марксистской традиции введено разделение на буржуазные революции Приводят к замене феодализма капитализмом в экономике не до...
32885. Русская аксиология 49.6 KB
  Человека интересует не просто истина, а значение объекта для человека, для удовлетворения его потребностей. Человек оценивает факты своей жизни по их значимости, реализует ценностное отношение к миру. Ценностью является для человека все, что имеет для него определенную значимость
32886. Философия как мировоззрение. Предмет философии. Основной вопрос философии. Материализм и идеализм 41.21 KB
  Предмет философии. Основной вопрос философии. Предметы философии круг вопросов которые изучает философия. Структура предмета философии: Онтология Учение о бытие; Гносеология Учение о познании; Человек; Общество.
32887. Мифология как мировоззрение. Первобытная мифология. Религия как мировоззрение 38.38 KB
  Мифы пытаются дать ответ на следующие вопросы: Происхождение Вселенной Земли и человека; Объяснение природных явлений; Жизнь судьба смерть человека; Деятельность человека и его достижения; Вопросы чести долга этики и нравственности. Религия как мировоззрение: Религия форма мировоззрения основанная на вере в наличие фантастических сверхъестественных сил которые влияют на жизнь человека и окружающий мир. При религиозном мировоззрении для человека характерна чувственная образноэмоциональная а не рациональная форма...
32888. Античная философия. Пифагор, Сократ, Платон, Аристотель. Демокрит, Эпикур 48.3 KB
  Милет: Философия охватывала все науки и не ставила ключевого вопроса философии но был поставлен вопрос о первопричине мира. Один из основателей атомистики и материалистической философии. Сократ Платон Аристотель: Сократ Его учение знаменует переход философии к рассмотрению человека от рассмотрения природы и мира. Его деятельность поворотный момент античной философии.
32889. Средневековая философия. Отцы церкви (Василий Великий, Григорий Богослов, Иоанн Златоуст). Фома Аквинский, Григорий Палама. Реализм и номинализм 45.82 KB
  В результате в мире идет борьба между добром и злом но поскольку мир это творение Бога Добра то добро в итоге и одерживает победу. Основные черты: Теоцентризм Главная причина сущего Бог; Изучению самого по себе космоса природы явлений окружающего мира уделялось мало внимания так как они считались творением Бога; Господствовали догматы...
32890. Философия Нового времени в Европе. Дж. Бруно. Декарт. Ф. Бэкон. Гоббс. Д. Локк. Французский атеизм и материализм 49.04 KB
  Ее особенность ориентация главным образом на науку Поэтому на передний план выдвигаются теперь вопросы познания. Расхождения в оценке роли этих форм познания породили основные направления новоевропейской философии: 1 Эмпиризм направление в философии считающее основным источником познания чувственный опыт Особая форма сенсуализм выводящий все знания из ощущений Представители Ф.Лейбниц; Основные отличия: 1 Связан с реализмом 2 Признает врожденные идеи как основу истинного познания 3 Категория субстанции одна из основных;...
32891. Классическая немецкая философия. Кант, Фихте, Шеллинг, Гегель 40.14 KB
  Классическая немецкая философия. Немецкая философия конца XVIII первой половины XIX века есть завершение традиции классической европейской философии в целом. Философия состоит из 3х частей: 1. Философия природы Превращение абсолютной идеи в предметы и явления природы 3.