Синтез цифрового автомата
Покупка
Основная коллекция
Тематика:
Автоматика
Издательство:
Российский университет транспорта
Год издания: 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).
Рисунок 2.2 – Математическая модель абст- рактного автомата На этапе абстрактного синтеза производят задание алгоритма работы абстрактного автома- та. Алгоритм может быть задан с помощью таб- лиц переходов и выходов (табличный способ), графов, матриц соединений или аналитическим способом. Абстрактный автомат называется полным, если его функции переходов определены для всех пар (xi, aj), в противном случае – частич- ным. В качестве примера приведены таблицы переходов и выходов полного автомата Мили, где строки и столбцы обозначены буквами входные сигналы и состояния памяти. В клетках таблицы переходов на пересечении столбца Xi и строки aj записывается новое состояние – ре- зультат перехода al=δ(xi,aj), а в таблице выходов – выходной сигнал yk= λ(xi,aj). Для полного ав- томата Мили с произвольными множествами X = {x1, x2, x3}, Y = {y1, y2, y3} и A = {a1, a2, a3, a4} функция переходов представлена в таблице 2.1,
а функция выходов – в таблице 2.2. Часто при представлении автомата Мили используют одну совмещенную таблицу переходов и выходов (таблица 2.3), которую называют отмеченной. Таблица 2.1 – Таблица переходов Таблица 2.2 – Таблица выходов Xt At X1 t X2 t X3 t а1 a1 a2 a3 а2 a4 a4 a2 а3 a3 a1 a4 a4 a3 a1 a2 Xt At X1 t X2 t X3 t а1 Y1 Y2 Y2 а2 Y3 Y3 Y3 а3 Y2 Y1 Y3 a4 Y2 Y3 Y3