Синтез цифрового автомата
Покупка
Основная коллекция
Тематика:
Автоматика
Издательство:
Российский университет транспорта
Год издания: 2019
Кол-во страниц: 75
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Специалитет
Артикул: 788101.01.99
В учебно-методическом пособии приведены этапы структурного синтеза конечных автоматов с памятью, содержатся теоретические материалы по общей теории цифровых автоматов, приведены варианты для выполнения курсового проекта, а также задачи для самостоятельного решения обучающимися.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)» Кафедра «Автоматика, телемеханика и связь на железнодорожном транспорте» Е.В. АРХИПОВ, А.А. АНТОНОВ, Т.С. ТУКТАМЫШЕВА СИНТЕЗ ЦИФРОВОГО АВТОМАТА Учебно-методическое пособие к курсовому проектированию по дисциплине «ТЕОРИЯ ДИСКРЕТНЫХ УСТРОЙСТВ» МОСКВА - 2019
МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)» Кафедра «Автоматика, телемеханика и связь на железнодорожном транспорте» Е.В. АРХИПОВ, А.А. АНТОНОВ, Т.С. ТУКТАМЫШЕВА СИНТЕЗ ЦИФРОВОГО АВТОМАТА Учебно-методическое пособие для студентов специальности «СИСТЕМЫ ОБЕСПЕЧЕНИЯ ДВИЖЕНИЯ ПОЕЗДОВ» МОСКВА - 2019
УДК 681.51 А 87 Архипов Е.В., Антонов А.А., Туктамышева Т.С. Синтез цифрового автомата: Учебнометодическое пособие. – М.: РУТ (МИИТ), 2019. – 75 с. В учебно-методическом пособии приведены этапы структурного синтеза конечных автоматов с памятью, содержатся теоретические материалы по общей теории цифровых автоматов, приведены варианты для выполнения курсового проекта, а также задачи для самостоятельного решения обучающимися. Рецензент – доцент кафедры «Электропоезда и локомотивы» РУТ (МИИТ), к.т.н., доцент А.А. Чучин © РУТ (МИИТ), 2019
1.ЦЕЛЬ И ЗАДАЧИ КУРСОВОГО ПРОЕКТА Студенты должны научиться применять теоретические знания, полученные при изучении курса «Теория дискретных устройств», решая конкретные задачи по созданию цифровых автоматов. По мере выполнения курсового проекта (работы), студенты должны дополнительно освоить заданные разделы учебников с новым теоретическим материалом: разделов по дискретной математике; особенности реализации схем внутренней памяти конечных автоматов в сочетании с комбинационными схемами возбуждения триггеров и комбинационных схем для построения выходов конечного автомата. 2.КРАТКИЕ СВЕДЕНИЯ ИЗ ОБЩЕЙ ТЕОРИИ ЦИФРОВЫХ АВТОМАТОВ Общая теория автоматов подразделяется на абстрактную и структурную. Абстрактная теория изучает поведение автомата относительно внешней среды и не рассматривает способы его построения. Структурная теория автомата изучает способы построения логических схем
автоматов на основе алгоритма, заданного на
абстрактном уровне.
На этапе абстрактного синтеза решаются
две задачи: от словесного описания алгоритма
работы автомата переходят к стандартному способу задания алгоритма его работы (обычно
табличному); вторая задача – получение минимальной отмеченной таблицы переходов конечного автомата.
Следующий этап разработки теории автоматов – структурный синтез автомата, который
позволяет по минимальной отмеченной таблице
переходов построить цифровую схему автомата.
2.1. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНЫХ
АВТОМАТОВ
Абстрактный автомат, как систему, задают упорядоченной совокупностью шести объектов {X,Y,A,δ, λ, а1} (рис. 2.1), где
Рисунок 2.1 – Структурная схема абстрактного
автомата
X = {x1, x2,…, xn} – множество входных
сигналов (входной алфавит);
Y= {y1, y2,…,yk} - множество выходных
сигналов (выходной алфавит);
A= {a1, a2,…,al} – множество состояний
(внутренний алфавит), определяемый памятью
автомата;
δ - функция переходов, задающая отображение множества δ: A×X → A
λ- функция выходов, задающая отображение множества λ: A×X → Y или A→Y;
a1 - начальное состояние автомата.
Функция переходов δ показывает все возможные переходы из одного состояние памяти
ai в другое aj под действием входных сигналов.
Функция выходов λ задает все возможные выходные сигналы, вырабатываемые автоматом в
дискретные моменты времени в зависимости от
xi и aj.
Если функции переходов и выходов автомата однозначно определены для каждой пары
(а, x) ∈ А × Х, то автомат называют детерминированным или частично определенным.
Ограничение числа состояний абстрактного автомата определяет такое понятие как конечный автомат. Функционирование автомата
состоит в порождении двух последовательностей: последовательности очередных состояний
автомата а1[1], a2[2], a3[3],… и последовательности выходных состояний у1[1], у2[2], у3[3],…, которые для последовательности символов x1[1], x2[2], x3[3],… разворачиваются в моменты дискретного времени t = 1,2,3,.... Моменты дискретного времени получили название тактов. Функционирование автомата в дискретные моменты времени t может быть описано системой рекуррентных соотношений at+1=δ(at,хt). Понятие «память» (внутренние устойчивые состояния) автомата введено для описания систем, сигналы на выходах которых зависят как от входных сигналов в данный момент времени, так и от предыдущей истории развития процесса. В общем, множество устойчивых состояний автомата – это совокупность текущих значений физических параметров элементов памяти (например, напряжение на выходах триггеров), которая сохраняется до поступления соответствующего входного сигнала. Внутреннее состояние автомата соответствует некоторой памяти о прошлом и позволяет устранить время как явную переменную и выражать выходные сигналы в виде функции входов и памяти. Автомат работает в дискретном времени и переход из одного состояния в другое состояние
происходит мгновенно. По способу ввода дискретного времени автоматы подразделяются на синхронные и асинхронные. В синхронных автоматах дискретное время задают генератором синхронных сигналов: t = 0,1,2,…, где t– номер такта. Наиболее полно описаны и на практике широко применяются синхронные автоматы. Автомат, имеющий начальное состояние, называется инициальным. В начальный момент времени t = 0 инициальный автомат всегда находится в начальном состоянии a1∈A. По способу формирования выходных сигналов различают автоматы Мили, Мура и C– автоматы. Функция переходов всех автоматов одинакова и записываются в виде: At= δ [Xt, At+1]. Функции выходов задают выражения: Yt = λ [Xt, At+1] - для автоматов Мили, выходные сигналы являются функцией входных сигналов и состояния памяти; Yt = λ [At] - для автоматов Мура, выходные сигналы определяется только состоянием памяти; C–автомат - объединяет свойства автоматов Мили и Мура. Абстрактные автоматы Мили и Мура характеризуются одноканальными входами и выходами (рис.2.2).