Особенности дискретных автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе

Особенности дискретных автоматов

Контрольная работа

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией
в иллюстрирует рис. 1.3. Выходной сигнал уj элементарного автомата фиксирует новое устойчивое состояние в автомате и сохраняет неизменным это состояние на всем временном отрезке . Отрезок определяется в соответствии с такой формулою:

= – Δ0. (1.6)

Внешний такт Та автомата своею продолжительностью равный сумме внешних единичных тактов Т0:

(1.7)

Автоматное непрерывное время дает более полную возможность исследовать закон функционирования автоматов Мили и Мура, реализованных на триггерах, чем дискретное автоматное время tі. Однако, исследовать многофункциональные автоматы Мараховского, реализованные на схемах автоматной памяти, на протяжении внутреннего такта Δі, необходимо только в автоматном непрерывном времени [64].

В автоматах Мили, рассматриваемых в автоматном дискретном времени, выходной сигнал у1(t) определяется парой (х(t), а(t-1)), а сам автомат называется автоматом первого рода.

В автоматах Мура, рассматриваемых в автоматном дискретном времени, сдвинутый выходной сигнал у2(Т) определяется парой одинаковых состояний а(t) и а(Δ), где Т = t + Δ. Состояние а(t) устанавливается только после перехода автомата в это состояние под воздействием х(t) входного сигнала. Состояние а(Δ) сохраняется при сохраняющем е(Δ) входном сигнале. Сам автомат называется автоматом второго рода.

В многофункциональных автоматах, реализованных на схемах автоматной памяти и рассматриваемых в автоматном непрерывном времени, выходной сигнал исследуется как для многофункционального автомата 1-го и 2-го рода с использование входных сигналов х(t) и е(Δ). Автоматы Мараховского являются более общим типом цифровых автоматом, а автоматы Мили и Мура являются их частным случаем. Кроме этого, в автоматах Мараховского рассматривается и автомат 3-го рода, который дополняет теорию автоматов 1-го и 2-го рода.

Схемы автоматной памяти представляют собою матрицу запоминаемых состояний [64], состоящую из блоков πj, представляющих строки матрицы, в которых сохраняются подмножества определенных состояний автоматной схемы памяти под влиянием входного сигнала е(Δ), и блоков μі, представляющие столбцы матрицы с определенными подмножествами состояний автоматной схемы памяти, устанавливаемых входным сигналом х(t).

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

В детерминированных автоматах Мараховского дополнительно рассматривается функция δе сохранения состояний а(Δ), которая определяется парой (а(t), е(Δ)). Входной сигнал е(Δ) сохраняет состояние а(t) автоматов 1-го и 2-го рода после его установки на всем протяжении машинного такта Т в определенном подмножестве πj (рис. 1.3). Функции переходов из одного состояния а(Δ-1) в другое состояние а(t) определяется парой (а(Δ-1), х(t)), а сохранение состояния а(Δ) во время промежутка Δ определяется парой (а(t), е(Δ)).

В автоматах 3-го рода функция укрупненного перехода из состояния а(t) в состояние а(Δ) осуществляется под воздействием входного сигнала е(Δ) в определенном подмножестве μi и определяется парою (а(t), е(Δ)).

Типы выходных сигналов у определяют род автомата. Выходной сигнал у1 автомата первого рода определяется парой (а(Δ-1), х(t)), выходной сигнал у2 автомата второго рода определяется парой (а(t), а(Δ)), а выходной сигнал у3 автомата третьего рода определяется парой (а(t), е(Δ)). Общая теория автоматов при описанных допущениях разбита на абстрактную теорию автоматов и структурную теорию автоматов. В абстрактной теории автоматов отвлекаются от структуры самого автомата и его входных и выходных сигналов. Входные и выходные сигналы рассматриваются как буквы двух фиксированных алфавитов – входного и выходного. Абстрактная теория изучает лишь те переходы, которые осуществляет автомат под воздействием входных сигналов, и те выходные сигналы, которые выдаются.

Абстрактная теория автоматов, таким образом, близка к теории алгоритмов, являясь по существу ее дальнейшей детализацией.

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

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

Частным случаем дискретных автоматов являются автоматы, обладающие одним внутренним состоянием, которые называют комбинационными схемами или автоматами без памяти. Работа таких автоматов состоит в том, что они сопоставляют каждому входному сигналу х(t) соответствующий выходной сигнал у(t).

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

Один тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(Δ-1) подмножества πi в состояние а(Δ) подмножества πki ≠ πk) с определенной вероятностью Р1 под влиянием пары (хр(t). ek(Δ)), в которой входной сигнал хр(t) устанавливает в схеме памяти не запоминаемое состояние ар(t) ни при одном входном сигнале e(Δ). Другой тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(Δ-1) подмножества πi в состояние а(Δ) подмножества πki ≠ πk) под влиянием пары (х(t). ев(Δ)), в которой входной сигнал ев(Δ) с определенной вероятностью Р2 определяет подмножество сохраняемых состояний πk. Вероятностный переход второго типа возможен при рассмотрении трех уровней автоматной схемы памяти в цифровом автомате.

Нечеткие переходы в нечеткие подмножества Qн, состоящие из определенного числа четких подмножеств πi, определяют переходы из вполне определенного состояния автомата а(Δ-1) подмножества πi в состояние а(Δ) подмножества πki ≠ πk) с определенной вероятностью Рн под влиянием пары (хр(t). ев(Δ)).

Вероятностные и нечеткие переходы являются расплывчатыми и в большой степени зависят от физических свойств реальных автоматов.

Заключение

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

Литература

Пухальский Г.И., Новоселова Т.Я. Цифровые устройства. Учебное пособие для вузов. - Санкт-Петербург: Политехника издательство, 2006. – 880с.

Захаров Н.Г., Рогов В.Н. Синтез цифровых автоматов: Учебное пособие – Ульяновск: УлГТУ, 2013. – 136с.

В.А.Горбатов, А.В.Горбатов, М.В.Горбатова Теория автоматов: Учебник для студентов втузов. – М.: АСТ: Астрель. – 559с.

Ю.Г.Карпов Теория автоматов: Учебник для вузов. - 1-е издание. – СПб: Издат. дом ПИТЕР, 2013 год. - 208с.

Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов - М.: Высшая школа, 1987, - 272с.

Брауэр В. Введение в теорию конечных автоматов. Перевод с английского под редакцией Ю.И. Журавлева-М. Радио и связь, 1987, - 392с.

Глушков В.М. Синтез цифровых автоматов, Государственное издательство физико-математической литературы. Москва 1962.

Каган Б.М. Электронные вычислительные машины и системы.- М. Энергоавтомиздат, 1988, - 551с.

Киносита К., Асада К., Карашу О. Логическое проектирование СБИС – М. Мир, 1988, - 309с.

Савельев Н.В., Коняхин В.В. Функционально-логическое проектирование БИС.-М. Высшая школа, 2000. - 156с.

А.Фридман, П.Менон. Теория и проектирование переключательных схем. Москва. Мир. 1978

С.З.Кузьмин. Основы теории цифровой обработки радиолокационной информации. Москва. Советское радио. 1974

Д.А.Поспелов. Логические методы анализа и синтеза схем. Москва. Энергия. Издание третье, переработанное и дополненное. 1974.

Киносита К., Асада К., Карашу О. Логическое проектирование СБИС – М. Мир, 1988, - 309с.

Шило В.Л. Популярные цифровые микросхемы. Справочник. - Челябинск: Металлургия, 1988.

Браммер Ю.А., Пащук И.Н. Импульсные и цифровые устройства. – М.: Высшая школа, 2013.

Похожие работы

<< < 1 2 3 4 5