КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Понятие о дискретном (цифровом) автомате
Дискретнымиавтоматами называются устройства, служащие для преобразования дискретной информации. Т.к. буквы используемого стандартного алфавита обычно заменяются цифрами какой-либо системы счисления, то дискретные автоматы называют также цифровыми автоматами (ЦА). Основным качеством, выделяющим ЦА из числа других преобразователей информации, является наличие дискретного (в реальных автоматах всегда конечного) множества внутренних состояний ЦА и свойства скачкообразногоперехода автомата из одного состояния в другое. Скачкообразность перехода может рассматриваться как мгновенность срабатывания. Второе допущение: после перехода ЦА в произвольное состояние переход в следующее состояние оказывается возможным не ранее некоторого времени , которое называется интерваломдискретности автомата. Т.о. работу ЦА рассматривают в дискретномвремени. При этом различают два основных случая. 1) В синхронных ЦА, моменты времени, в которые возможно изменение состояния ЦА, определяются специальным устройством – генератором синхронизирующих импульсов. 2) В асинхронных ЦА моменты переходов из одного состояния в другое заранее неопределенны и могут совершаться через неравные между собой промежутки времени. Теория асинхронных ЦА при некоторых допущениях может быть сведена к синхронному случаю. Поэтому дальше будем рассматривать абстрактное автоматное время, принимающее целые неотрицательные значения и строить теорию синхронных автоматов. Изменения состояний ЦА вызываются входными сигналами, возникающими вне автомата и передающимися в ЦА по конечному числу входных каналов. Для любого ЦА число входных сигналов всегда конечно, входные сигналы рассматриваются как причина перехода ЦА из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами. Результат работы ЦА – выдача выходных сигналов по конечному числу выходныхканалов. При этом число различных выходных сигналов для любого ЦА всегда конечно и каждому отличному от 0 моменту автоматного времени относится соответствующий ему выходной сигнал. Реальный физический выходной сигнал , отнесенный к моменту времени , появляется всегда после соответствующего этому же времени входного сигнала . Что же касается момента времени перехода ЦА из состояния в состояние , то сигнал может фактически появиться либо раньше, либо позже этого момента. В первом случае выходной сигнал однозначно определяется входным сигналом и состоянием автомата в предыдущий момент времени, во втором случае сигнал однозначно определяется парой . ЦА, в которых называются автоматамипервогорода, а автоматы, в которых - автоматамивторогорода. ЦА называется правильным, если выходной сигнал определяется лишь одним его состоянием (или ) и не зависит от . Т.к. состояние в любом ЦА однозначно определяется парой (,), то всякий автомат 2-го рода можно рассматривать как частный случай автоматов 1-го рода. Автоматы 1-го рода называются автоматамиМили. Правильные автоматы 2-го рода называются автоматамиМура. Общая теория автоматов разбивается на две большие части: абстрактную теорию автоматов, структурную теорию автоматов. Не интересуясь способом построения автомата. Абстрактная теория изучает лишь те переходы, которые претерпевает автомат под воздействием входных сигналов, и те выходные сигналы, которые он при этом выдает. Абстрактная теория автоматов близка, т.о. теории алгоритмов. Структурная теория автоматов интересуется прежде всего структурой как самого автомата. Так и его входных и выходных сигналов. Частным случаем дискретных автоматов являются автоматы, обладающие лишь одним внутренним состоянием. Такие автоматы называются комбинационнымисхемами или автоматамибезпамяти. Работа таких автоматов состоит в то, что еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза автомата к задаче синтеза комбинационных схем. Глава 7
Дата добавления: 2014-01-06; Просмотров: 986; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |