АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ЛЕКЦИЯ 4 Общая теория конечных цифровых автоматов с памятью

Читайте также:
  1. ERG – теория Альдерфера
  2. I. Теория естественного права
  3. I.1.5. Философия как теория и
  4. III.2. Преступление: общая характеристика
  5. V. Социологическая теория
  6. VI. Общая задача чистого разума
  7. А) Теория иерархии потребностей
  8. А. Понятие и общая характеристика рентных договоров
  9. Административная теория А. Файоля
  10. Аналитическая теория личности
  11. АТОМНАЯ ФИЗИКА. БОРОВСКАЯ ТЕОРИЯ АТОМА
  12. Бактериологическое оружие: общая характеристика, поражающее действие

 

Основные понятия и определения

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

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

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

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

Кодирование информации

Информацию, поступающую на вход автомата, а так же выходную информацию, принято кодировать конечной совокупностью символов. Эту совокупность называют алфавитом, отдельные символы, образующие алфавит – буквами, а любые упорядоченные последовательности букв – словами в этом алфавите. Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1, x2x2, x1x1x1 и т.д.

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

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

X(x1, …, xF) ---> A(a0,..., aM) ---> Y(y1, …, yG).

Рис. 4.1. Абстрактный автомат

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

Для задания любого КА S необходимо задавать совокупность из пяти объектов: S{A, X, Y, d, l},

где A = {a0, a1, a2,..., am,..., aM} – множество состояний автомата, X = {x1, x2, …, xf,…, xF} – множество входных сигналов или входной алфавит, Y = {y1, y2, …, yg,…, yG} – множество выходных сигналов или выходной алфавит, d – функция переходов, определяющая состояние автомата в момент времени (t + 1) в зависимости от состояния автомата и входного сигнала в момент времени t, т.е. a(t + 1) = d [a(t), x(t)],

1 – функция выходов, определяющая значение выходного сигнала в зависимости от состояния автомата и входного сигнала в тот же момент времени, т.е. y(t) = l[a(t), x(t)].

Если множества А, Х и У конечны, то автомат называется конечным.

Автомат работает следующим образом. В каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний, причем в начальный момент времени t = 0 он находится в состоянии a0. Автомат воспринимает входной сигнал x(t), выдает выходной сигнал y(t) = l[a(t), x(t)] и переходит в состояние a(t + 1) = d[a(t), x(t)]. Другими словами, абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t + 1) и y(t). Такие автоматы называют детерминированными.

 

Условия преобразования информации в детерминированных автоматах

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

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

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

Применяемые на практике автоматы принято разделять на два класса – это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Законы функционирования автоматов описываются следующими системами уравнений:

Автомат Мили:   Автомат Мура:
a(t + 1) = d [a(t), x(t)],   a(t + 1) = d [a(t), x(t)],
y(t) = l[a(t), x(t)]..   y(t) = l[a(t)].

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

Способы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l}, т.е. необходимо описать входной и выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a0, a1,... aM} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)