Теория автоматов авторы. Теория автоматов. Общие положения

Все рассмотренные выше устройства относятся к классу комбинационных схем, то есть дискретных устройств без памяти. Наряду с ними в цифровой технике широкое распространение получили последовательностные автоматы, или, иначе, комбинационные схемы, объединенные с элементами памяти.

Под термином автомат можно понимать некоторое реально существующее устройство, функционирующее на основании как сигналов о состоянии внешней среды, так и внутренних сигналов о состоянии самого автомата. В этом плане ЭВМ может быть рассмотрена как цифровой автомат. Под цифровым автоматом понимается устройство, предназначенное для преобразования цифровой информации. С другой стороны, под термином автомат можно понимать математическую модель некоторого устройства. Общая теория автоматов подразделяется на две части: абстрактную и структурную теорию автоматов. Различие между ними состоит в том, что абстрактная теория абстрагируется от структуры как самого автомата, так и входных и выходных сигналов. В абстрактной теории анализируются переходы автомата под воздействием абстрактных входных слов и формируемые на этих переходах абстрактные выходные слова.

В структурной теории рассматривается структура как самого автомата, так и его входных и выходных сигналов, способы построения автоматов из элементарных автоматов, способы кодирования входных и выходных сигналов, состояний автомата.

В соответствии с этим принято различать две модели автоматов: структурную и абстрактную. Абстрактная модель применяется при теоретическом рассмотрении автоматов. Структурная модель служит для построения схемы автомата из логических элементов и триггеров и предназначена для выполнения функции управления.

Абстрактный автомат – это математическая модель цифрового автомата, задаваемая шестикомпонентным вектором S=(A,Z,W,d,l,a 1), где А={a a ,…,a m } – множество внутренних состояний абстрактного автомата; Z=, в которые автомат перейдет из состояния a i под воздействием сигнала x j; а в таблице выходов - соответствующий этому переходу выходной сигнал y g = [ a i,x j]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.

Совмещенная таблица переходов и выходов автомата Мили:

Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура.

Отмеченная таблица переходов автомата Мура:

В этой таблице каждому столбцу приписан, кроме состояния a i, еще и выходной сигнал y (t ) = (a (t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s, если в автомате имеется переход из a i в a s, то есть a s = (a i, x j). В автомате Мили дуга отмечается входным сигналом x j, вызвавшим переход, и выходным сигналом y g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

Граф для автомата Мили:

Граф для автомата Мура

2.3 Частичные автоматы

В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат - частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai, xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще.

Пример таблицы переходов и выходов частичного автомата Мили

Из таблицы переходов видно, что Т-триггер обладает полной системой переходов и выходов, поскольку для каждой пары состояний (0-0, 0-1, 1-0,

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

Матрица переходов:

Матрица переходов определяет значения сигналов на входах элементарного автомата, обеспечивающие каждый их четырех возможных переходов. Здесь Q(t) и Q(t+1) - состояния автомата в моменты времени t и t+1 соответственно. Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки.

Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча по матрице перехода:

Из диаграммы имеем:

Поскольку эта формула совпадает с аналитической записью переключательной функции сложение по модулю два, то Т-триггер часто называют триггером со счетным входом Т, а входной сигнал, поступающий на вход Т, счетным сигналом. На практике кроме асинхронного Т-триггера, работу которого мы рассмотрели, используют так же и синхронный Т-триггер, который в отличие от асинхронного меняет свои состояния только при Т = 1 и С = 1. Если хотя бы один из этих сигналов равен нулю, то триггер сохраняет свое состояние. Вход С называют входом синхронизации.

Поясняющая работу комбинационная схема и обозначение синхронного

Т-триггера представлены на рисунке:

2.5 D-триггер

D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что Q(t+1) = D(t). Название D-триггера происходит от английского слова "delay" - задержка. Из определения следует, что состояние триггера в момент времени t+1 повторяет значение входного сигнала D(t) в момент времени t (отсюда и название триггера задержки).

Матрица переходов для D-триггера:

Обозначения асинхронного и синхронного D-триггеров:

В синхронном D-триггере при С=0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть

Асинхронный D-триггер практического значения не имеет.

Граф D-триггера

2.6 RS-триггер

RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S такие, что при S=1 и R=0 триггер принимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым.

Матрица переходов RS-триггера:

Комбинация сигналов R=1 и S=1 является запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая может принимать два значения 0 v 1. Аналогично, переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R=0, S=0 и R=0, S=1. Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записана переменная b2. По матрице переходов можно построить граф RS-триггера.

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

Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча:

2.7 JK-триггер

JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K, который при условии J * K = 1 осуществляет инверсию предыдущего состояния (т.е. при J*K=1, Q(t+1) = Q(t)), а в остальных случаях функционируют в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Этот триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то есть зависимость Q(t+1) = f имеет вид:

Таблица истинности JK-триггера:

По этой таблице можно построить диаграмму Вейча для Q(t+1), которую можно использовать для минимизации, и матрицу переходов:

Матрица переходов JK-триггера:

В интегральной схемотехнике применяются только тактируемые (синхронные) JK триггера, которые при C=0 сохраняют свое состояние, а при C=1 работают как асинхронные JK триггера.

2.8 Универсальный триггер

Триггер JK относится к разряду универсальных триггеров, поскольку на его основе путем несложной внешней коммутации можно построить RS-, D- и T- триггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как эта комбинация является запрещенной для RS триггера.

Счетный триггер на основе JK триггера получается путем объединения входов J и K.

Триггер задержки (D-триггер) строится путем подключения к входу K инвертора, на который подается тот же сигнал, что и на вход J. В этом случае вход J выполняет функцию входа D, а все устройство в целом реализует таблицу переходов D-триггера .

Заключение

В данной работе были описаны основные принципы работы автоматов. При этом автоматы были разделены на абстрактные и автоматы, применяемые в микросхемотехнике. Так же теория автоматов тесно связана с теорией алгоритмов.

Исследование абстрактных автоматов в результате привели к активному развитию вычислительной техники и микросхемотехники соответственно.

Список использованных источников

1. Дискретная математика. Учебное пособие. Саяпин А.В., Сливина Т.А. Редакционно-издательский отдел СибГАУ. Красноярск 2010 163с.

2. Лекции по теории цифровых автоматов [Электронный ресурс]. Лекции [Сайт]. URL: http://www.twirpx.com/file/455856/

Размещено на Allbest.ru

Подобные документы

Теория приближений как раздел математики, изучающий вопрос о возможности приближенного представления математических объектов. Построение интерполяционного многочлена. Приближение кусочно-полиномиальными функциями. Алгоритм программы и ее реализация.

курсовая работа , добавлен 18.10.2015


Описание абстрактных, структурных и частичных конечных автоматов. Работа синхронных конечных автоматов, содержащих различные типы триггеров, определение сигналов их возбуждения. Пример канонического метода структурного синтеза. Схема дверного замка.

учебное пособие , добавлен 07.06.2009


Теория вероятностей - раздел математики, изучающий закономерности случайных явлений: случайные события, случайные величины, их свойства и операции над ними. Методы решения задач по теории вероятности, определение математического ожидания и дисперсии.

контрольная работа , добавлен 04.02.2012


Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

дипломная работа , добавлен 08.08.2007


Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.

реферат , добавлен 13.06.2011


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

презентация , добавлен 22.10.2013


Свойства дискретного преобразования Фурье, представленные в виде математических формул, которые наиболее адекватно соответствуют цифровой технике обработки информации. Алгоритм быстрого преобразования Фурье (БПФ), его значение для программирования.

учебное пособие , добавлен 11.02.2014


реферат , добавлен 13.01.2011


Изучение конкретного раздела дискретной математики. Решение 5-ти задач по изученной теме с методическим описанием. Методика составления и реализация в виде программы алгоритма по изученной теме. Порядок разработки программного интерфейса и руководства.

курсовая работа , добавлен 27.04.2011


Геометрия как раздел математики, изучающий пространственные отношения и формы, а также другие отношений и формы, сходные с пространственными по своей структуре. Основные этапы становления и развития данной науки, ее современные достижения и перспективы.