учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С.

В.Б. СИЛИН, Б.С. МЕЛЬНИКОВ по курСу КОНЕЧНЫЕ АВТОМАТЫ МОСКВА — 1978 УЧЕБНОЕ ПОСОБИЕ "ЭЛЕКТРОННЫ Е ВЫ Ч ИСЛИТЕЛЪНЫ Е УСТРОЙСТВА" МОСКВА-1Э78 МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕПИАЛЬНОГО ОБРАЗОВАНИЯ СССР МОСКОВСКИЙ ОРДЕНА ЛЕНИНА АВИА11ИОННЫЙ ИНСТИТУТ имени СЕРГО ОРДЖОНИКИДЗЕ В.Б. СИЛИН, Б.С, МЕЛЬНИКОВ УЧЕБНОЕ ПОСОБИЕ до курсу "ЭЛЕКТРОННЫЕ ВЫЧИСЛИТЕЛЬНЫЕ УСТРОЙСТВА Конечные автоматы (Для дневной и вечерней форм обучения) Утверждено на заседании редсовета 8 декабря 1977 г. УДК 681.51.013(075.8) ПРЕДИСЛОВИЕ (С) Московский авиационный институт, 1978 г. Зав. редакцией М.И. Кузнецова 681.14(075) С362 Настоящее учебное пособие по курсу 'Электронные вычислительные устройства" посвящается одному из узловых во- Ф просов теории и практики цифровых устройств - основам теории конечных автоматов.

Теория конечных автоматов является моподым и бурно развивающимся научно-техническим направлением, содержание которого выходит дапеко за рамки непосредственно цифровых устройств. По этой причине содержание многочисленных пубпикапий по конечным автоматам часто оказывается не слишком удобным материалом по систематическому изучению основ этого направления применительно к цифровой технике. Именно это и привепо к необходимости написания настоящего учебного пособия. Содержание пособия освещает основные этапы синтеза конечных автоматов. Материал изпожен таким образом, что он, с одной стороны, соответствует лекционному курсу и, с другой стороны, может непосредственно испопьзоваться при подготовке к лабораторным и практическим занятиям. Полнота изложения соответствует программе курса 'Эпектронные вычислительные устройства' дпи специальности "Конструирование и производство электронной вычислительной аппаратуры", подготавпиваемой на факультете "Радиоэлектроника летатепьных аппаратов .

Однако пособие в полном объеме может быть с успехом использовано студентами, обучающимися и по остальным специапьностям на дневном отделении факупьтета. При испопьзовании этого пособия студентами вечернего отдепения могут быть опущены разделы 1.1, 1.2, 1.3.7, 2.1, 2.5, 3, 4.

Разделы 1, 2 и 3 написаны канд. техн. наук В.Б. Силиным, раздеп 4 — канд. техн. наук Б.С. Мельниковым. 1. ВВЕДЕНИЕ 1.1. Задачи, не шаемые средствамн комбнвацновной логики Основная цель любой инженерной дисциплины — разработка совокупностя методов как теоретического, так и техннческого характера, обеспечивающих решение практических задач определенного круга.

Настоящий выпуск конспекта лекпнй посвящен одному нз важнейших разделов курса 'Электронные вычислительные устройства" — задачам синтеза цифровых электронных устройств, выполняющнм определенные функции обработки информация илн управления либо моделнруюшнм поведение некоторых реальных объектов. Вопросы синтеза цифровых устройств частично уже рассматривались во второй части конспекта лентий (1), содержащей логнческне основы цифровых вычнслительных устройств. Знание материала, наложенного в работе 11), позволяет на теоретическом уровне решать задачи сннтеза логических целей комбинационного типа. Принципиальной особенностью цепей такого типа является возможность обработхи только той янформацян, которая представлена на входах этих цепей в один и тот же момент времени.

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

Едва ли не самым элементарным примером задачи такого ро- 4 Рис. 1. Последовательный двоичный счетчик 1.2. Оцнсанне ст ойства с сох аненнем л едысто ин сигнала Рассмотрим некоторое устройство А (рнс. 2), обладаю- щее одним бинарным входом х я одним бинарным выходом у . 6 да является задача синтеза Очетчнка единичных сигналов.

Устройство, реализующее функция такого счетчика (рис. 1), нмеет однв вход, на который поступают бинарные сигналы якай йэа а '1 (единячный счетный сигнац) Сч -- ц нли 0" (отсутствие счетного сигнала). Выход устройства позволяет представлять общее число поступивших сигналов за определенный интервал времени в виде некоторого п -разрядного двоичного кода. Естественно, что максимальное число подсчитанных сигналов не должно а превосходить 2 — 1. В ходе работы счетчнха поступление каждого. очередного счетного сигнала должно будет приводить к изменению выходного кода счетчика. Однако новое выходное значение может быть определено только с учетом уже накопленного ранее чнсла счетных сигналов, т.е.

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

Рассматриваемые устройства должны обладать способностью в том илн ином виде фнкснровать 'предысторию сигнала, т.е. должны обладать 'памятью". Это одновременно означает, что аппарат комбннацнонной логнки должен быть дополнен какями-то вовымн средствамн,с помощью которых могла бы быть получена возможность адекватно описывать пропесс преобразования ннформации во времени. Зафиксируем дпя етого устройства некоторый, начапьный момент времени, своего реда момент его вкпючевмя, в кеторый обеспечивак»тся опредепанаые всегда идемтичпые успения качана его функынояпровааив. Обозначим моменты времени подачи входных сигналов пнфрами натуральноге рипа, мспопьзуемыми в качестве кндексов у обозначений входных сигналов.

хй,) «л «»» Ркс. 2. Устройство, сохраняющее преды- сторию сигнала При этом попожим, что момент вкпючеяия устройства будет нупевым. Будем далее попагать, что выходные сигыапы с пренебрежимо мздой задержкой будут изменяться вслед за поступпеыием очередных входных.

Таким образом, на вход устройства А будет подаваться некоторая последовательность развернутых в поспедоватепьные моменты времена сигаапов х (1»)» х ( 4д), ° °,Х(8 )..., в то времи кзк иа выходе' будет формироваться соответствующая последоватепьность дй»)» ~( 8~)», » Д (» )»» Возможны разпнчные варианты попе деним такого устройства.

В простейшем случае каждый из выходных сигвалюв м»эжет зависеть только от очередного входного свгнапа: и(~„)=Уха~ )), (1 1) при этом вад функпая 1 (.,) остается неизменным в течение всего времена функпиопкрованая. Очевидно, чтр в этом простейшем случае рассматриваемое устройство может быть эквивалентно представпено комбныапионной пагичесхой пенью, реализующей одну вз четырех возможных погнческах фувицкй от одной переменной. Какая-вибо зависимость выходных значений ~ от ранее поступивших будет отсутствовать. В случае самого сложыого варианта поведения этого устройства будет наблюдаться зависимость выходного сигнала у от очередного и всех ранее поступивших входных сигна- Ф пов, начиная с самого первого Х~, независимо от реально достигнутого номера Ю. Такой вариант поведения соответствует устройству практически неограниченыой сложности,что, повидимому, исключено дпя устройств технического происхо- 6 жданки» поэтому данный вариант поведения может не рассматриватьсы.

В практических ситуапккх ыаибопь»пий мнтерес должны представпить устройства с конечной предысторией, т.е. устройства, в которых. выходные сигналы зависят от очередного и некоторого конечного чкспа 4 ранее поступивших входных смгнапов: у~и„) =Г/х/~ ( ) х/е,(, ),. х~е»),х~2 )),(1.2) В тех спучаях, когда пи Н, вепичины Х (~,) дням«1 доопределяютси таким образом, чтобы из (1.2) всегда следовапи неебходюаые 9п .

Очевидно, что в этих устройствах последние 4 пз поступивших ранее входных сигвапов н представляют собой саму конечную предысторию устройства, опредепяющую реакпию устройства на очередной входной сигнал. Обозыачим эту предысторию дпы очередного 1„момента времеви как /' й. Она, таким образом, вкпы»чает в себя поспедовательность' входных снгпапов, начиная с х ( ~„~ ) к кончан Х И„~ ) . Заметим, что влияние этой предыстории йе ограничивается ее участием в формировании очередного и -го выходного сигнала, но и проявляется в постепенно ослабеваюшей степени на протяжении еше Й -1 шага работы устройства (рис.