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


 

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

41828. Проведение исследования на основе готовой компьютерной модели 163.07 KB
  LINE х1 у1х2 у2 cоператор изображающий отрезок прямой х1 у1 начало отрезка х2 y2 конец отрезка c номер цвета. LINE х1 у1х2 у2 c B оператор изображающий прямоугольник со сторонами параллельными осями координат. LINE х1 у1х2 у2 c BF оператор изображающий закрашенный прямоугольник c номер цвета.146 6 Перемещение начала координат в центр экрана LINE 3.
41829. Работа с запросами в MS Access 117.5 KB
  Порядок выполнения задания Создание запросавыборки Создать запрос содержащий поля: Идент.Для этого необходимо выполнить следующую последовательность действий: При выбранной вкладке Запросы выполнить щелчок по кнопке . Открывается окно Новый запрос в котором выбрать режим создания запроса Конструктор затем ; Открывается окно Запрос1: запрос на выборку а затем активизируется окно Добавление таблицы в котором выбрать из списка таблиц таблицу Сотрудник щелчком мыши по имени таблицы а затем выполнить щелчок по кнопке после чего...
41830. Создание и форматирование таблиц. Использование логических и математических функций в табличных вычислениях 178.5 KB
  Использование логических функций необходимо, когда для выбора правильного решения нужно проверить выполнение одного или нескольких условий. Наиболее часто используемые функции этой категории
41831. Создание архива данных. Извлечение данных из архива. Атрибуты файла и его объем 27.83 KB
  Атрибуты файла и его объем Цель: изучение принципов архивации файлов функций и режимов работы наиболее распространенных архиваторов приобретение практических навыков работы по созданию архивных файлов и извлечению файлов из архивов. Теоретические сведения к лабораторной работе Архивация упаковка помещение загрузка исходных файлов в архивный файл в сжатом или несжатом виде. Архивация предназначена для создания резервных копий используемых файлов на случай потери или порчи по какимлибо причинам основной копии невнимательность...
41832. Художественные средства. Инструмент rtistic Mediа 217.5 KB
  Примеры рисования инструментом rtistic Medi Художественные средства Инструмент rtistic Medi Художественные средства входит в состав группы инструментов Curve Кривая рис. Инструмент rtistic Medi Художественные средства включает в себя пять отличных друг от друга режимов работы. Инструмент rtistic Medi Художественные средства может работать в следующих режимах: Preset Заготовка заготовка для живописи; Brush Кисть художественная кисть; Spryer Распылитель распылитель; Clligrphic Каллиграфический ...
41833. ИССЛЕДОВАНИЕ ТИПОВОЙ СХЕМЫ УПРАВЛЕНИЯ ЭЛЕКТРОПРИВОДОМ ПОСТОЯННОГО ТОКА ПОДЪЁМНО КРАНОВОГО МЕХАНИЗМА 247 KB
  Изучить принцип действия и исследовать работу одной из типовых схем управления электроприводом подъёмно кранового механизма с ДПТ независимого возбуждения. Ознакомиться с электрооборудованием типового шкафа управления. Исследовать работу схемы управления электроприводом подъёмно кранового механизма.
41834. Решение бухгалтерских задач с помощью пакета Excel 286.36 KB
  Решение бухгалтерских задач с помощью пакета Excel Цель работы Познакомиться с работой пакета Excel как инструмента для решения задач бухгалтерского учета. Научиться правильно задавать имена переменным определять ссылки на ячейки использовать функции при вводе формул работать с массивами данных в Excel. Должна быть установлена программа Microsoft Excel.
41835. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ И СХЕМЫ 238.57 KB
  Данная работа посвящена изучению простейших комбинационных логических устройств реализующих логические функции сложения умножения и отрицания. В результате функции отображающие информацию принимают в каждый момент времени только значения 0 или 1. Такие функции называют логическими а сигналы входные и выходные переменные двоичными бинарными. Рассматривая входные сигналы х1 х2 хп в качестве аргументов можно соответствующие выходные сигналы представлять в виде функции уi = fх0 х1 х2 хп с помощью...
41836. Изучение и анализ конструкций сцеплений транспортных автомобилей 78.68 KB
  Контрольные вопросы дайте классификацию сцеплений назначение устройство и принцип работы фрикционного однодискового гидравлического и электромагнитного сцеплений конструктивные особенности различных видов сцеплений их преимущества и недостатки применяемые материалы для изготовления элементов и узлов сцеплений какие приводы используются для управления сцеплением опишите их устройство и дайте им характеристику опишите устройство и работу центробежного сцепления какие существуют способы передачи крутящего момента от маховика двигателя к...