Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Синтез цифрового автомата

Покупка
Основная коллекция
Артикул: 788101.01.99
В учебно-методическом пособии приведены этапы структурного синтеза конечных автоматов с памятью, содержатся теоретические материалы по общей теории цифровых автоматов, приведены варианты для выполнения курсового проекта, а также задачи для самостоятельного решения обучающимися.
Архипов, Е. В. Синтез цифрового автомата : учебно-методическое пособие / Е. В. Архипов, А. А. Антонов, Т. С. Туктамышева. - Москва : РУТ (МИИТ), 2019. - 75 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/1896908 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
МИНИСТЕРСТВО ТРАНСПОРТА 
РОССИЙСКОЙ ФЕДЕРАЦИИ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ 
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ 
УЧРЕЖДЕНИЕ ВЫСШЕГО 
ОБРАЗОВАНИЯ 
«РОССИЙСКИЙ УНИВЕРСИТЕТ 
ТРАНСПОРТА (МИИТ)» 
 
Кафедра «Автоматика, телемеханика и связь 
на железнодорожном транспорте» 
 
 
Е.В. АРХИПОВ, А.А. АНТОНОВ, 
Т.С. ТУКТАМЫШЕВА 
 
 
СИНТЕЗ ЦИФРОВОГО АВТОМАТА 
 
 
Учебно-методическое пособие к курсовому 
проектированию 
по дисциплине 
«ТЕОРИЯ ДИСКРЕТНЫХ УСТРОЙСТВ» 
 
 
 
МОСКВА - 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