Теория автоматов как научная дисциплина

Введение Теория автоматов как научная дисциплина возникла в пределах теории управляющих систем (теоретической кибернетики) в середине XX века, в период начавшегося бурного развития средств электронной вычислительной техники и соответствующих областей математического знания. Потребовалась разработка теоретической базы для решения проблем, возникавших при проектировании реальных цифровых ЭВМ, а также в процессе построения и исследования гипотетических систем, таких как нейронные сети. В качестве моделей последних рассматривались конечные автоматы. Цифровой автомат (ЦА) – это условная, формальная модель любого информационного устройства дискретного действия. Модель предназначена для представления устройства на логическом уровне, т.е. в ней не допускается использование каких-либо физических характеристик процессов, происходящих при работе реального устройства. В связи с таким упрощением число различимых состояний, в которых может оказаться ЦА, всегда ограничено. Переход из одного состояния в другое мыслится как мгновенный скачок, без всяких промежуточных состояний, тогда как в реальной физической системе соответствующий переход должен иметь бесчисленное множество переходных фаз с исчезающе малыми отличиями последующего состояния от предыдущего. Бесконечное число состояний для цифрового автомата означает его бесконечную сложность, так как иначе нельзя обеспечить явное отличие одного состояния от другого. В принципе можно представить себе бесконечный ЦА, как автомат с неограниченно наращиваемой памятью состояний, и такой автомат представляет определенный теоретический интерес, но в данном курсе мы будем касаться только конечных автоматов. Кстати, термины «конечный автомат» и «цифровой автомат» часто используются как синонимы и, по сути, выражают одно и то же понятие. Итак, подытоживая сказанное, мы определили ЦА как условную, упрощенную модель технического устройства, имеющую ограниченное дискретное множество состояний. В то же время можно дать и совершенно другое определение, вытекающее из назначения описываемого устройства. Можно считать ЦА моделью алгоритма, задающего некоторый процесс преобразования информации. В этом смысле понятие ЦА аналогично понятию машины Тьюринга, хотя прямой связи между этими понятиями нет. Машина Тьюринга это устройство, которое моделирует действия человека, решающего задачу, руководствуясь некоторым алгоритмом. То есть, машина Тьюринга представляет умозрительную конструкцию, позволяющую удобно описывать на интуитивном уровне специальные задачи математической теории вывода, а ЦА – это модель, позволяющая заниматься логическим синтезом реальных систем, отвлекаясь от протекающих в них физических процессов. Работа ЦА протекает во времени, но это особенное, автоматное время, представляющее смену последовательных дискретных моментов t = 0, 1, 2, 3,... ЦА всегда начинает свою работу с момента t = 0, а время окончания может быть не определенным или бесконечным. Теорию автоматов принято делить на две основные части: абстрактную и структурную. Абстрактная теория устанавливает свойства автомата, не раскрывая его внутреннего устройства (макроподход). В абстрактной теории преобладает алгоритмический аспект. Вычислительное устройство здесь рассматривается как абстрактный автомат – устройство, имеющее несколько входов, на которые одновременно подаются сигналы, и выход, сигналы на котором являются их функцией (рис. 1.1). Рис. 1.1. Схема абстрактного автомата Буква х изображает совокупность всех одновременно подаваемых на входы устройства сигналов. Фактически это должно означать некоторую комбинацию значений двоичных переменных, поступающих по разным линиям связи, но для абстрактной теории это не имеет значения. Теория ограничивается определением множества Х = {х1, х2, х3,… хр}, которое называется входным алфавитом. Под алфавитом здесь понимается счетное множество допустимых символов языка описания автомата. С течением автоматного времени буквы хi сменяют одна другую, образуя последовательность, например, х3, x3, x1, x3, x2, x1 . Такая последовательность называется входным словом автомата. Можно сказать, что входное слово состоит из l букв, или, что оно имеет длину l . Длина слова может быть различной, в том числе и бесконечной, порядок букв в слове может быть любым. Выход У автомата определяется аналогично. Все выходные буквы принадлежат выходному алфавиту Y = {y1, y2, ..., yr}. Число букв в алфавитах X и Y не обязательно одинаково, чаще оно оказывается различным. Последовательность выходных сигналов (букв), появляющихся в моменты t1, t2, ... , называется выходным словом, например y2, y2, y1, y4, y3, ... Роль абстрактного автомата сводится к тому, что он последовательно, букву за буквой, преобразует входные слова в выходные. При этом, естественно, совпадает длина входных и выходных слов. Каждая буква s означает одно определенное состояние ЦА. Все эти буквы в совокупности образуют внутренний алфавит или алфавит состояний. S = {s0, s1, s2, ..., sk-1}– совокупность символов, обозначающих состояния цифрового автомата, в котором непременно содержится начальное состояние s0. Так как в связи со сказанным, нумерация состояний начинается с нуля, при общем числе букв в алфавите, равном k, индекс последней буквы выражается как k–1. Структурная теория ЦА представляет автомат в виде логической сети с явно выраженными функциональными элементами, элементами памяти и линиями связи (микроподход). Представление об этом дает рис. 1.2. Рис. 1.2. Структурная схема цифрового автомата Предполагается, что структурные входы u1, u2, ... и выходы z1, z2, ... , а также внутренние линии связи несут только двоичные сигналы, принимающие значения: «логический нуль» и «логическая единица». Элементы памяти q1, q2, ... также могут хранить только нули или единицы. Совокупность всех одновременно действующих входных сигналов называется входным структурным вектором, а множество всех возможных значений этого вектора образует входной структурный алфавит U. Аналогично определяются выходной вектор и вектор внутренних состояний, число компонент которого равно числу элементов памяти в схеме ЦА. Ясно, что между буквами абстрактных алфавитов X, Y и S с одной стороны и буквами структурных алфавитов U, Z и Q – с другой должно существовать взаимно-однозначное отображение. И все же это – разные алфавиты. Переход от абстрактного алфавита к структурному называется кодированием автоматных алфавитов и представляет одну из важных задач структурной теории. Анализ автоматов считается прямой задачей, как в абстрактной, так и в структурной теории. Анализ устанавливает основные свойства автоматов и сравнивает автоматы между собой, создает методы описания и пути преобразования автоматов. Синтез автоматов считается обратной задачей, гораздо более сложной, решение которой позволяет построить функциональную схему цифрового автомата. В общем случае синтез состоит из двух этапов: абстрактного и структурного синтеза. На первом этапе создается формальная абстрактная модель автомата по заданному на произвольном входном языке алгоритму его работы, а на втором – выполняется кодирование автоматных алфавитов – переход от абстрактного алфавита к структурному алфавиту и составляется логическая, т.е. функциональная схема устройства. Рассмотрим некоторые вопросы классификации автоматов. Все ЦА можно разделить на два основных класса: автоматы без памяти, или примитивные автоматы, и автоматы с памятью. Автоматы без памяти – это обычные комбинационные логические сети, которые не содержат элементов памяти, линии связи в них идут только от входов к выходам и не образуют обратных связей. Внутреннее состояние у них одно и оно не может меняться. Поэтому выходные сигналы полностью определяются входными сигналами, действующими в данный момент автоматного времени. Типичными автоматами без памяти являются цифровые комбинационные элементы (КЭ): сумматоры, дешифраторы, схемы сравнения, мультиплексоры и т.п. При описании таких КЭ используется структурный по своему смыслу алфавит, но обозначения (например, входная переменная х) могут совпадать с принятыми в литературе буквами абстрактных алфавитов. Применительно к автоматам без памяти это допустимо, ввиду простоты их функций, и не приводит к неправильному пониманию. При описании автоматов с памятью придется более строго различать обозначения переменных на абстрактном и структурном уровнях. С точки зрения сигналов цифровой автомат полезно определить как систему, которая может принимать входные сигналы, и под их воздействием переходить из одного состояния в другое, сохранять его до прихода следующего входного сигнала, выдавать выходные сигналы (рис. 1.3).. Рис. 1.3. Общее изображение Рис. 1.4. Структурное изображение Цифровой автомат считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y, то есть это автомат с ограниченной памятью состояний. Конечный автомат, в каждом состоянии которого существует функция перехода для всех возможных входных символов, называется полностью определенным конечным автоматом. Для формального описания электронных схем, которые делятся на два типа в зависимости от того, каким образом выходной сигнал зависит от входного, используют аппарат математической логики и теории автоматов. Математический аппарат алгебры логики пригоден для анализа и синтеза схем без памяти, то есть таких схем, в которых совокупность выходных сигналов в любой момент времени представляет собой однозначную функцию входных сигналов в тот же момент времени. Реализуемый в этих схемах способ обработки информации называется комбинационным, так как результат на выходе зависит только от комбинации входных сигналов. Схемы с памятью, алгоритм работы которых зависит от времени, описываются с помощью математического аппарата теории конечных автоматов. Понятие цифрового автомата, как средства для представления и обработки любых видов информации, является одним из основных в информатике. Конечными автоматами являются как отдельные узлы ЭВМ, так и вся вычислительная машина. Модели конечных автоматов активно используются не только при проектировании устройств обработки дискретной информации, но в теории формальных языков и основанных на ней методов построения трансляторов, при реализации сетевых протоколов, в автоматном программировании, при разработке объектно-ориентированных и распределенных интеллектуальных систем. Теория автоматов нашла применение: • в проектировании систем логического управления; • при обработке текстов и построении компиляторов; • при оптимизации логических и объектно-ориентированных программ; • другое. 1 Основные понятия теории автоматов Предметом теории автоматов является изучение математических моделей преобразователей дискретной информации. В данной теории решаются следующие основные задачи: анализ и синтез автоматов, определение полноты, минимизация и эквивалентные преобразования автоматов. Дадим краткую формулировку каждой из перечисленных задач. Задача анализа. По заданному автомату описать его поведение. Вариант постановки: по неполному описанию автомата установить некоторые его свойства. Задача синтеза. Построить автомат с наперед заданным поведением (алгоритмом функционирования). Задачу синтеза принято рассматривать двояко: абстрактный синтез как построение математической модели автомата и структурный синтез как разработку функциональной логической схемы автомата. Задача полноты. Пусть M – некоторое множество автоматов. Определить, обладает ли совокупность автоматов, составляющих подмножество M'  M, свойством полноты. Иными словами, если ко всем автоматам подмножества M' конечное число раз применить операцию суперпозиции, совпадут ли M' и M? Задача минимизации. Построить автомат, минимальный заданному. Минимальный автомат обладает наименьшим числом компонентов модели (в частности, минимальной мощностью множества так называемых состоянии) и при этом функционально эквивалентен заданному автомату. Задача эквивалентных преобразований. Определить полную систему правил, позволяющую преобразовывать произвольный автомат в любой эквивалентный ему автомат. Частным случаем данной задачи является переход от одной модели автомата к другой. Два автомата функционально эквивалентны, если их поведение одинаково при воздействии одних и тех же последовательностей входных сигналов. В таком случае говорят о совпадении моделей поведения двух автоматов. В число основных понятий теории автоматов входят: • абстрактный автомат (АА); • композиция автоматов. Понятие АА позволяет рассматривать дискретные устройства с точки зрения алгоритмов их функционирования, то есть реализуемых последовательностей действий по преобразованию дискретной информации. Абстрактный автомат  это математическая модель, описывающее техническое устройство совокупностью входных, выходных сигналов и внутренних состояний, которая описывается пятью переменными (пятиместным кортежем): А = (X, Y, S, fy, fs), где первые три компонента - непустые множества: 1. X - множество входных сигналов АА, 2. Y - множество выходных сигналов АА, 3. S - множество состояний АА. Два последних компонента кортежа - характеристические функции: 4. fy - функция выходов; 5. fs - функция переходов АА из одного состояния в другое. Если множества X, Y, S - конечные, то такой АА называют конечным автоматом (КА). Если хотя бы одно из перечисленных множеств не является конечным, то такой АА называют бесконечным. Общую схему автомата можно представить в виде некоторого «черного ящика», осуществляющего преобразование вектора входных сигналов в вектор выходных сигналов (рис. 1.1): Рис. 1.4. Общая схема конечного автомата Введем обозначения мощностей множеств, входящих в указанный выше кортеж: X = {x1, x2, …, xp}, |X| = p; Y = {y1, y2, …, yq}, |Y| = q; S = {s1, s2, …, sn}, |S| = n. Конечный автомат, в описание которого входят, таким образом, определенные множества, называют (n, p, q)-автоматом, а самим множествам усваивают наименование векторов, например: вектор входных сигналов, вектор состояний. Все автоматы, и в том числе конечные, функционируют в дискретном исчислении времени. Моменты времени образуют ряд целых неотрицательных чисел: t = 0, 1, 2, 3, … В каждый дискретный момент времени КА находится в одном и только одном состоянии Sn, воспринимает одно значение вектора X и выдает на выходе одно значение вектора Y. Принято считать, что в момент времени t = 0 автомат находится в начальном состоянии S0, которое можно включить в кортеж отдельным, шестым компонентом: А = (X, Y, S, fy, fs, S0). Автомат с выделенным начальным состоянием называют инициальным. Таким образом, КА, изображенный на рис.1 можно записать: Y = fy(X, t). Фактор времени в приведенном уравнении учитывается введением вектора состояний S, как своего рода «памяти о прошлом». Действительно, на один и тот же набор входных сигналов (значений компонентов вектора X) автомат будет выдавать разные выходные сигналы (значения компонентов вектора Y) в зависимости от состояния, в котором он находится в данный момент времени. Текущее состояние, в свою очередь, определяется алгоритмом функционирования автомата. Абстрактный автомат реализует некоторое отображение множества слов входного алфавита X во множество слов выходного алфавита Y. При этом если входной алфавит X и множество S внутренних состояний автомата - конечные множества, то автомат называется конечным (finite automat). В детерминированных автоматах (deterministic automat) поведение и структура автомата в каждый момент времени однозначно определены текущей входной информацией и состоянием автомата. Состояние автомата в конкретный момент времени определяется состоянием его элементов памяти S. При аппаратной реализации конечного автомата в качестве элементов памяти используются триггеры - элементарные автоматы с двумя состояниями, которые обладают полными системами переходов и выходов. Под действием входных сигналов автомат переходит из одного состояния в другое. Входные сигналы подаются в дискретные интервалы времени. Промежуток между двумя последовательными моментами дискретного времени есть один такт работы автомата. Любая комбинация сигналов, передаваемых одновременно по реальным входным каналам (входное слово), рассматривается как один сигнал. Выходной сигнал является результатом работы автомата. Существует два способа введения автоматного времени, по которым цифровые автоматы делят на синхронные и асинхронные. В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены и зависят от некоторых событий. В таких автоматах интервал дискретности является переменным. В синхронных автоматах период следования входных сигналов является постоянной величиной и задаётся генератором синхросигналов. В детерминированных автоматах функция переходов fs однозначно определяет состояние Sn, в которое переходит автомат из исходного состояния Sm под действием входного сигнала Xp , то есть Sn = fs (Sm, Xp). Функция выходов fy определяет выходной сигнал, в зависимости от состояния автомата и входного сигнала, то есть Yg= fy ( Sm, Xp). Недетерминированный автомат (nondeterministic automat) может одновременно находиться в нескольких состояниях и значением его функции переходов является множество, состоящее из нуля, одного или нескольких состояний. Функционирование недетерминированных (вероятностных) автоматов может описываться статистически. В случае, когда множество S состоит из одного состояния, то есть S={s1}, получаем вырожденный абстрактный автомат, у которого выходной сигнал не зависит от предыстории этого автомата, а зависит только от входного сигнала. Дальнейшее изложение будем вести, исходя из практических соображений, применительно к полностью определенным, детерминированным и устойчивым конечным автоматам. Функция fs реализует бинарное отношение вида S  X  S, то есть каждой паре «состояние – входной сигнал» ставит в однозначное соответствие определенное состояние из множества S. Аналогично, бинарное отношение для функции fy имеет вид S  X  Y, то есть каждой паре «состояние – входной сигнал» ставится в соответствие конкретный выходной сигнал – элемент множества Y. Таким образом, характеристические функции определяют, в какое состояние s  S перейдет автомат в следующий, (t+1)-й момент времени и каково будет значение выходного сигнала y  Y в текущий момент времени t: s(t+1) = fs (x(t), s(t)) y(t) = fy (x(t), s(t)) Из приведенных уравнений видно, что аргументами характеристических функций являются текущее значение входного сигнала и текущее состояние. Конечный автомат, заданный парой уравнений (1), называется автоматом I рода или, по имени автора модели, автоматом Мили (Mealy). В автоматах Мили выходные сигналы являются функцией входных сигналов и состояния памяти. На практике часто встречаются автоматы, выходные сигналы которых в момент времени t однозначно определяются текущим состоянием автомата и не зависят от компонентов вектора входных сигналов: s' (t+1) = fs ' (x(t+1), s'(t)) y(t) = fy ' (s' (t)) Автомат, заданный парой уравнений (2), называют автоматом II рода или автоматом Мура (Moore). Штрих введен в обозначения для отличия записи функций и состояний автомата Мура от автомата Мили. Заметим, что автомат Мили по отношению к автомату Мура «запаздывает» на один дискретный момент времени по входному сигналу. В автоматах Мура выходные сигналы определяются только состоянием памяти. Автоматы I и II рода являются двумя базовыми моделями, изучаемыми теорией автоматов. Если для выходного сигнала некоторого КА имеет место уравнение: y(t) = fy(x(t)), то такой автомат называется тривиальным. Строго говоря, это уже не автомат, а комбинационная схема (КС), которая реализует совокупность булевых функций fy1, …, fyq для компонентов вектора выходных сигналов Y (рис. 1.3). 1.5 На практике конечный автомат представляет собой совокупность двух устройств – операционного и управляющего автоматов. Операционный автомат выполняет ряд действий над входными данными и выдает результат, а управляющий автомат задает последовательность этих действий, то есть алгоритм функционирования операционного автомата. Например, в случае кодового замка операционным автоматом является электромагнит, управляющий засовом, а управляющим автоматом – электронная схема, обеспечивающая считывание и анализ сигналов от клавиш, проверку кода, выдачу сигнала операционному автомату на открытие замка, сброс в начальное состояние. Другой пример – устройство умножения двоичных чисел с фиксированной запятой. Операционный автомат представляет собой ряд взаимосвязанных функциональных элементов – сумматора (например, дополнительного кода), регистров входных данных и результата, сдвигового регистра, цепи переноса двоичной единицы. Управляющий автомат задает порядок, в котором должны действовать составные узлы операционного автомата, чтобы обеспечить последовательность шагов реализуемого алгоритма умножения. 1.3 Способы задания автоматов Для задания автоматов используют начальные и автоматные языки описания. Начальные языки, такие как язык регулярных выражений алгебры событий, логическая схема алгоритма (ЛСА), графическая схема (граф-схема) алгоритма (ГСА), матричная схема алгоритма (МСА), функциональная микропрограмма (ФМП), система формул перехода (СФП), описывают автомат на поведенческом уровне. На этом уровне функции переходов и выходов обычно явно не заданы. Поведение автомата описывается в терминах входных и выходных последовательностей сигналов или сообщений, реализуемых автоматом отображений. Для высокоуровневого описания поведения программных автоматов (объектов, агентов) может использоваться язык диаграмм состояний и переходов в одной из объектно-ориентированных нотаций (например, унифицированный язык моделирования UML). Диаграммы состояний и переходов позволяют представить пространство состояний объектов, события, которые влекут переход из одного состояния в другое и действия, которые происходят при изменении состояния. Эти диаграммы используются в ходе анализа, чтобы показать динамику управляемого событиями поведения системы, а в ходе проектирования – для выражения поведения отдельных объектов или их взаимодействия. Любое изменение состояния предметной области связывается с некоторым событием, меняющим текущие значения атрибутов и связи объектов. Событие является основным понятием, которое используется для моделирования динамических процессов, происходящих в предметной области объектно-ориентированной системы. Каждое событие может приводить к смене состояния одного или нескольких объектов системы и возникновению новых событий. Наличие внутреннего состояния означает, что поведение объекта зависит не только от событий, но и от времени, поэтому конечный автомат является наилучшим способом его формального описания. Конечный автомат может использоваться как один из методов высокоуровневого управления логикой, с помощью которого передаются команды подсистеме нижележащего уровня. Для описания поведения объекта в ответ на переход в некоторое состояние или на возникновение некоторого события в диаграмму состояний включаются описания активностей и действий. Активностью называется операция, связанная с каким-либо состоянием объекта (она выполняется, когда объект попадает в указанное состояние); выполнение активности требует определенного времени, в отличие от действия – мгновенно выполняемой операции. Активности, запускаемой переходом на диаграмме состояний, может соответствовать еще одна (вложенная) диаграмма состояний. Каждый переход из состояния в состояние может быть связан либо с событием, либо с событием и условием. Условный переход может быть осуществлен только тогда, когда условие будет выполнено, иначе переход не состоится до тех пор, пока еще раз не произойдет событие и не будет проверено условие. Допускаются переходы и без свершения события, тогда переход осуществляется сразу после завершения действия, связанного с состоянием, при этом выполняется также действие, связанное с выходом из этого состояния. При использовании автоматных языков поведение автомата задается путем явного задания функций переходов и выходов. Наиболее часто используются табличный и графический способы задания работы автомата. При табличном способе задания автомата Мили, функции переходов и выходов задаются соответственно таблицей переходов и таблицей выходов. Строки обеих таблиц обозначаются входными сигналами автомата, а столбцы – его состояниями. На пересечении i-ой строки и j-го столбца таблицы переходов ставится соответствующее значение fs(aj,xi) функции переходов, а в таблице выходов соответствующее значение fy(aj,xi) функции выходов. Автомат Мура задается одной отмеченной таблицей переходов, в которой таблица выходов имеет лишь одну строку и совмещается с таблицей переходов (таблица 1.1). Таблица 1.1 fy fy(s1) fy(s2) fy(s3) xi\sj s1 s2 s3 x1 fs(s1 x1) fs(s2 x1) fs(s3 x1) x2 fs(s1 x2) fs(s2 x2) fs(s3 x2) x3 fs(s1 x3) fs(s2 x3) fs(s3 x3) При графическом способе задания автомата функции переходов и выходов задаются с помощью ориентированного связного графа, вершины которого соответствуют состояниям, а дуги – переходам между ними. Переходы из состояния sm в состояние sn под действием входного сигнала xi для автоматов Мили и Мура показаны на рисунке 1.6. Рисунок 1.6 Если переход автомата происходит под действием нескольких входных сигналов, то дуге (sm, sn) приписываются все эти входные и соответствующие выходные сигналы. Выходной сигнал yk = fy(sn) автомата Мура записывается рядом с соответствующей вершиной sj. Могут быть случаи, когда не все значения функций переходов и выходов определены. Автоматы с такими функциями называются частично определенными. При этом в тех местах таблицы переходов и таблицы выходов, где соответствующие функции неопределенны, проставляются прочерки (таблица1.2). Частично определенный автомат таблица1.2 fy fy(s1) fy(s2) fy(s3) xi\sj s1 s2 s3 x1 - fs(s2 x1) fs(s3 x1) x2 fs(s1 x2) - fs(s3 x2) x3 fs(s1 x3) fs(s2 x3) - Полнота системы переходов автомата в общем случае означает, что для любой пары состояний автомата (sm, sn) существует входной сигнал xi, так что определена функция sn = fy (sm, xi). Автомат обладает полной системой выходов, если каждому его состоянию соответствует выходной сигнал yk, отличный от выходных сигналов других состояний. Для решения задачи структурного синтеза микропрограммного автомата заданная система автоматов, на основе которой осуществляется синтез, должна быть структурно-полной. Всякая система элементарных автоматов, которая содержит автомат Мура, обладающий полными системами переходов и выходов, и какую либо функционально-полную систему логических элементов, является структурно-полной. Выделяют два этапа синтеза конечных автоматов: абстрактный и структурный. Целью структурного синтеза является построение схемы реализующей автомат из логических элементов и элементов памяти заданного типа или же его программная реализация. Целью абстрактного синтеза автомата, при котором отвлекаются от структуры, как самого автомата, так и его входных и выходных сигналов, является получение минимальных таблиц переходов и выходов на основе отмеченного графа алгоритма или диаграмм состояний и переходов. 1.3. Абстрактный синтез конечного автомата Задача абстрактного синтеза КА состоит в разработке математической модели на основании заданного алгоритма функционирования автомата. Так как модель представляет собой кортеж А = (X, Y, S, fy, fs), то в процессе синтеза необходимо конкретизировать все его компоненты. Множества X, Y, S могут быть заданы любым из способов, изучаемых в теории множеств. Поскольку множества конечны, вполне допустимо ограничиться простым перечислением их элементов. Это легко сделать, если мощности множеств невелики. В противном случае для задания того или иного множества можно, например, перечислить несколько первых его элементов и указать порождающую рекурсивную процедуру для получения остальных. Характеристические функции наиболее удобно представимы табличным и графическим способами. Табличный состоит в построении таблицы переходов и выходов КА, графический способ – в построении взвешенного орграфа переходов автомата. (ориентированный граф) Для изучения процесса абстрактного синтеза КА рассмотрим пример. «Автомат имеет два входа x1, x2 и один выход y. В начальный момент времени y = 0. На вход подаются сигналы: (x1, x2) = (0,0), (0,1), (1,0) и (1,1). В случае входной комбинации (1,0) на выходе формируется значение 1; если (x1, x2) = (0,1), то выдается y = 2. В остальных случаях y = 0». Как видно, описание работы автомата не обязательно связано с какой-либо конкретной системой счисления. Очевидно, в двоичной системе как вход, так и выход заданного автомата будут двухразрядными (x1, x2, y1, y2); в троичной системе вход останется двухразрядным, а выход будет одноразрядным (x1, x2, y); в 4-ричной системе вход и выход станут одноразрядными (x, y). Однако для построения математической модели определение системы счисления несущественно. Зададим множества, входящие в описание модели. 1. X = {(0,0), (0,1), (1,0), (1,1)}, где первый элемент каждой пары соответствует x1, второй элемент – x2. Для краткости запишем: X = {00, 01, 10, 11}. 2. Y = {0, 1, 2}. 3. Множество состояний S должно быть сформировано так, чтобы отрабатывалась каждая ветвь алгоритма функционирования автомата. Для этого алгоритм представим в виде схемы, иногда называемой граф-схемой алгоритма. Если каждый шаг алгоритма принять за микрокоманду, то схема алгоритма является наглядным изображением микропрограммы автомата как последовательности микрокоманд. Схема алгоритма заданного автомата представлена на рис. 1.7. Рис. 1.7. Схема алгоритма функционирования КА Состояния определим путем разметки схемы по следующим правилам, различным для моделей Мили и Мура. Модель Мили. 1). Вход блока, следующего за начальным, и вход конечного блока отвечают состоянию s0. 2). Вход блока, следующего за операторным, отвечает состоянию si, где i = 1, 2,… – номер операторного блока. Заметим, что разметка отражает цикличность работы автомата. На уровне модели цикл бесконечный: алгоритм и начинается, и завершается состоянием s0. В схемотехнической реализации функционирование продолжается, пока на электрическую схему автомата подается питание или действует разрешающий сигнал от автомата более высокого уровня иерархии. Разметка схемы алгоритма для модели Мили показана на рис. 1.8. Имеем множество состояний: S = {s0, s1}. Рис. 1.8. Разметка схемы алгоритма (модель Мили) Построим взвешенный ориентированный граф (орграф) переходов автомата Мили. Вершины графа соответствуют состояниям автомата. Дуга, направленная из вершины si в вершину sj, задает переход вида: Переход инициируется входным сигналом xk  X. На переходе формируется выходной сигнал ymY. Поэтому весом дуги является пара «вход/выход»: xk / ym. Проанализируем условия переходов. Переход КА из состояния s0 в состояние s1 является безусловным: булева функция, описывающая такой переход, тождественно равна единице, на графе соответствующая дуга будет помечена «1». Обратный переход из s1 в s0 возможен по трем ветвям алгоритма. На рис. 1.8 они обозначены как а), б), в) и указаны пунктирными стрелками. Условие прохода по каждой из ветвей представим в дизъюнктивной нормальной форме (ДНФ): ритма операторные блоки отсутствуют, на выходе автомата сохраняется прежний сигнал y = 0. Граф переходов показан на рис. 1.9, а. Веса дуг записаны в формате «вход/выход». Подчеркнем, что в автомате Мили выходной сигнал формируется именно на переходе КА из одного состояния в другое. Это становится понятным, если принять во внимание, что функция выходов автомата Мили зависит от двух аргументов: входного сигнала и текущего состояния. В процессе разметки схемы алгоритма каждый операторный блок оказывается между двумя состояниями, причем переход от одного к другому либо безусловный, когда операторные блоки расположены один за другим, либо условный, когда между операторными блоками присутствует не менее одного блока ветвления (см. рис. 1.8). На рис. 1.9, б приведена построенная по графу таблица переходов/выходов КА Мили. Строки таблицы соответствуют состояниям автомата, левая подтаблица отражает значения выходного сигнала в момент времени t для каждой пары «состояние – набор входных сигналов», правая подтаблица показывает, в какое состояние переходит автомат в следующий момент времени из данного состояния под воздействием каждого набора входных сигналов. В данном примере действие, заключенное в операторный блок, состоит именно в выработке выходного сигнала. Если схема алгоритма отражает микропрограмму функционирования некоторого операционного автомата, например, умножения чисел, то в операторных блоках будут присутствовать действия над данными, например, сдвиг множимого в регистре, сложение частичной суммы и множимого на сумматоре и тому подобное. Но каждому действию соответствует инициирующий сигнал, вырабатываемый управляющим автоматом, который и задает требуемую алгоритмом последовательность микрокоманд. Модель Мура. Разметка схемы алгоритма состоит в следующем. 1). Начальному и конечному блокам сопоставляют состояние s0. 2). Каждому операторному блоку ставится в соответствие состояние si, где i = 1, 2,… – номер блока. Таким образом, каждое состояние автомата Мура связано с действием, и обратно – каждое действие, то есть значение выходного сигнала, приписывается определенному состоянию. Напомним, что единственным аргументом функции выходов автомата Мура является его состояние в текущий момент времени. Разметка схемы алгоритма для случая КА Мура показана на рис. 1.10. Рис. 1.10. Разметка схемы алгоритма (модель Мура) Весом дуги является значение входного сигнала, инициировавшего переход. Так как выходной сигнал в момент времени t определяется исключительно текущим состоянием автомата, то обозначение выходного сигнала ym на графе приписывается вершине si, соответствующей состоянию, в котором этот выходной сигнал формируется. На рис. 1.11, а обозначения выходных сигналов выделены синим цветом. Таблица переходов/выходов (рис. 1.11, б) в отличие от модели Мили не разделяется на две подтаблицы – выходов и переходов, поскольку каждому состоянию соответствует определенное значение выходного сигнала независимо от сигналов на входах. Последние влияют только на переходы автомата: под воздействием каждого входного набора КА переходит из текущего состояния s'(t) в состояние s'(t+1) в соответствии с алгоритмом функционирования. 1.4 Связь между моделями автоматов Мили и Мура Для каждого автомата Мура может быть построен эквивалентный ему автомат Мили и наоборот. При этом два автомата являются эквивалентными, если после установки в начальное состояние их реакции на любое входное слово совпадают. Рассмотрим автомат Мура 1, совмещенная таблица переходов и выходов которого представлена в таблице 1.3. таблица 1.3 состояние/выход s1/ y1 s2/ y2 s3/ y3 s4/ y4 x1 s2 s3 s4 s4 x2 s4 s1 s1 s1 Пусть на вход данного автомата, установленного в начальное состояние s1, поступает входное слово X = x1 x2 x2 x1 x2 x2. Так как для автомата Мура выходной сигнал yg = fy (sm), то последовательность вырабатываемых им выходных сигналов (реакция Y= fy (s1,X) автомата) определяется только последовательностью состояний, которые автомат 1 проходит, воспринимая входное слово Y (таблица 1.4). Как видно из примера, в ответ на входное слово длины n автомат Мура выдаст последовательность состояний длины n + 1. таблица 1.4 Входное слово X x1 x2 x2 x1 x2 x2 Последовательность состояний S s1 s2 s1 s4 s4 s1 s4 Выходное слово Y y1 y2 y1 y2 y2 y1 y2 Аналогичную реакцию Y= fy (s1,X) на входное слово Y имеет автомат Мили (таблица 1.5), заданный таблицами переходов и выходов, представленными в таблице 1.6. таблица 1.5 Входное слово X x1 x2 x2 x1 x2 x2 Последовательность состояний S s1 s2 s1 s3 s3 s1 s3 Выходное слово Y y2 y1 y2 y2 y1 y2 таблица 1.6 fs (s,x) таблица переходов fs (s,x) таблица выходов s1 s2 s3 s1 s2 s3 x1 s2 s3 s3 x1 y2 y3 y2 x2 s3 s1 s1 x2 y2 y1 y1 Переход от автомата Мура 1 (рисунок 1.12) к эквивалентному ему автомату Мили 2 тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили (рисунок 1.13) необходимо выходной сигнал yp, записанный рядом с вершиной si исходного автомата Мура (рисунок 1.12), перенести на все дуги, входящие в эту вершину. Рисунок 1.12 Рисунок 1.13 Реакция на входное слово X автомата Мили, полученного в результате преобразования графа, будет совпадать с реакцией исходного автомата Мура. При этом необходимо отметить, что в эквивалентном автомате Мили количество состояний останется таким же, как в автомате Мура. Автомат Мили 2 реализует такое же преобразование слов входного алфавита, что и автомат Мили заданный на рисунке 1.11, но в отличие от последнего имеет не три, а четыре внутренних состояния. Для того чтобы убедиться в эквивалентности автомата Мили заданного на рисунке 1.11 автомату 2 , осуществим его преобразование к автомату Мура. Как и в предыдущем случае, переход наиболее удобно осуществлять при графическом способе задания автомата. Каждое состояние si исходного автомата Мили (рисунок 1.14) порождает столько состояний автомата Мура (рисунок 1.15), сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние si. Как следует из рисунка 1.14, при попадании автомата в состояние s1 вырабатываются выходные сигналы y1, при попадании автомата в s2 – сигналы y2, в s3 – сигналы y2 и y1. Каждой паре состояние si – выходной сигнал yj, который вырабатывается при попадании в это состояние, поставим в соответствие состояние sp эквивалентного автомата Мура с тем же выходным сигналом yj: s1 = (s1,y1), s2 = (s2,y2), s3 = (s3,y3), s4 = (s3,y2). Таким образом, состояние s3 исходного автомата Мили порождает два состояния (s3 и s4) эквивалентного автомата Мура. Так как в автомате Мили есть переход из s3 в s1 под действием x2 и переход из s3 в s3 под действием x1, то из состояний s3 и s4, порождаемых состоянием s3 автомата Мили в автомате Мура должны быть переходы в состояние s1 под действием сигнала x2, а также переходы s3  s4 и s4  s4 под действием сигнала x1. 1.2 Соединение автоматов Автоматной сетью называется соединение автоматов, осуществляемое таким образом, что они функционируют согласованно, и образуют новый автомат. Сетью из автоматов (автоматной сетью) называют соединения конечных автоматов таким образом, что выход одного автомата служит входом для другого и они функционируют согласованно, то есть изменяют свои состояния в одни и те же дискретные моменты времени. К основным способам соединения автоматов относятся: параллельное, последовательное и соединение с обратной связью. Параллельное соединение автоматов A1 = (S1, X, Y1, fs1, fy1, s11) и A2 = (S2, X, Y2, fs2, fy2, s12) представлено на рисунке 1.2. Рисунок 1.16 – Параллельное соединение автоматов Автоматы имеют общий входной алфавит X и схему φ, преобразующую выходные сигналы Y1 и Y2 в множество Y выходных сигналов результирующего автомата A = (S, X, Y, fs, fy, s1), у которого: • входной алфавит X; • выходной алфавит Y = φ (Y1,Y2); • внутренний алфавит S = S1  S2 образуется из всевозможных пар состояний автоматов A1 и A2; • функция переходов fs определяется правилом: fs (sm, xi) = (fs1 (sm1, xi), fs2 (sm2, xi)); • функция выходов fy определяется правилом: φ (am, xi) = φ (fy1(sm1, xi), fy2 (sm2, x[)). Последовательное соединение двух автоматов A1 = (S1, X, Y1, fs1, fy1, s11) и A2 = (S2, Y1, Y, fs2, fy2, s12) представлено на рисунке 1.3. Рисунок 1.17 – Последовательное соединение автоматов Выходные сигналы автомата A1 являются входными для автомата A2. Результирующий автомат A = (S, X, Y, fs1, fy1, a1) имеет: • внутренний алфавит S = S1  S2; • входной алфавит X; • выходной алфавит Y = Y2 (выходные сигналы автомата A2); • функцию переходов, определяемую правилом: fs (sm, xi) = (fs1(sm1, xi1), fs2(sm2, fy1 (sm1, xi1))); • функцию выходов: fy (sm, xi) = fy2 (sm2, fy1(sm1, xi)). Соединение с обратной связью двух автоматов представлено на рисунке 1.18, где A1 = (S1, X, Y1, fs1, fy1, s11) и A2 = (S2, X, Y2, fs2, fy2, s12). Рисунок 1.18 – Соединение с обратной связью При таком соединении один из автоматов обязательно должен быть автоматом Мура. Пусть A2 = (S2, X, Y2, fs2, fy2, s12) является автоматом Мура, у которого Y2 = fy2 (s2). Тогда результирующий автомат A = (S, X, Y, fs, fy, s1) имеет: • внутренний алфавит S = S1  S2; • входной алфавит x; • выходной алфавит Y = Y1 (выходные сигналы автомата S1); • функцию переходов fs (sm, xi) = (fs1(sm1, φ (xi, fy2 (sm 2))), fs2 (sm2, fy1 (sm1, φ (xi, fy2 (sm 2))))); • функцию выходов fy (sm, xi) = fy1 (sm1, φ (xi, fy2 (sm 2))). Логические функции Для формального описания работы цифровых схем применяется аппарат алгебры логики. В алгебре логики используются понятия «логическая переменная» и «логическая функция». Логическая переменная может принимать только два значения 0 или 1, т. е. х = {0,1}. Логическая функция f(х1 х2, ... хn) включает в себя несколько логических переменных, связанных между собой математическими знаками операций алгебры логики. Она может принимать значения 0 или 1 на каждом из наборов логических переменных х1 х2, ... хn . Количество переменных может быть любым. Логические функции одной и двух переменных называют элементарными. Существуют различные способы представления логических функций. Одним из распространенных является табличный способ, при котором каждому набору значений переменных в таблице соответствует значение самой функции. Такие таблицы называют таблицами истинности. В табл. 2.1 представлены логические функции одной переменной. Таких функций всего четыре: константа 0, тождественно х, инверсия х и константа 1. Инверсия (отрицание операция НЕ) обозначается чертой над функцией. Для двух переменных логических функций будет уже шестнадцать (табл. 2.2). Наиболее часто используются функции дизъюнкции f7(xb x2), конъюнкции f1(xbx2), отрицания дизъюнкции f8(xbx2), и отрицания конъюнкции f14(xbx2), называемые также функциями ИЛИ, И, ИЛИ-НЕ и И-НЕ. Отметим, что логика этих функций распространяется на любое число переменных. Используя элементарные функции можно получать выражения и для более сложных функции. Конъюнкцию (логическое умножение, операцию И) обозначают точкой, символами , & или не обозначают вовсе, а дизъюнкцию (логическое сложение, операцию ИЛИ)  символом . Элементарные логические функции обладают рядом свойств, используя которые можно упрощать логические функции и получать различные эквивалентные формы их представления. Пусть х  некоторая логическая переменная. Тогда справедливы следующие тождества: (под таблицей 2.2). Логическая функция может быть задана как в виде таблицы истинности, так и в виде формулы. Пусть логическая функция задана на некотором наборе логических переменных {х1,х2,х3,... хп}. Поскольку каждая переменная принимает значения 0 или 1, набор переменных можно рассматривать как целое двоичное число, разрядами которого являются логические переменные. Номера наборов удобно использовать для компактной записи логической функции. Введем вспомогательную логическую функцию Fi представляющую собой конъюнкцию всех переменных в прямом и инверсном виде и принимающую значение 1 на наборе переменных с номером i. Такую функцию называют термом. Так, F5 = принимает значение на наборе переменных {х1х2x3} = {101}, что соответствует номеру набора 5. Функция представляет собой конъюнкцию трех переменных. Любая заданная таблицей истинности логическая функция может быть представлена аналитически в виде совокупности термов связанных между собой знаками дизъюнкции, т.е. f(х1х2х3, ..., хп) = Fi ,где i-номера наборов, на которых функция принимает значение 1, символ  означает дизъюнкцию, объединяющую все термы Fi = 1. Таким образом, количество термов в аналитическом представлении функции соответствует количеству строк таблицы истинности, где функция принимает значение 1. Рассмотрим пример. Пусть функция задана следующей таблице истинности (табл. 2.3). На основании теоремы аналитическая запись функции имеет вид: Логическая функция, записанная в виде дизъюнкции термов всегда представлена в совершенной дизъюнктивной нормальной форме (СДНФ), т.е. каждый терм включает все переменные, что удобно для использования табличных способов упрощения функции. Существует еще представление функции в виде дизъюнкции неполных термов, в которых отсутствуют отдельные переменные. Так форма представления называется просто дизъюнктивной нормальной формой (ДНФ). Например, функция представлена в дизъюнктивной нормальной форме . Логическая функция может быть записана различным образом. Формы записи могут иметь различную сложность. Для количественной оценки сложности логических функций служит критерий Квайна. При этом если логическая функция записана в ДНФ, то ее сложность S равна сумме количества всех переменных и количества конъюнкций (S = 6 + 3 = 9). Так как сложность логической функции определяет сложность логической схемы, то желательно использовать наиболее простую, минимальную форму функции. Для нахождения минимальных форм логических функций применяют различные методы минимизации. Для логических схем, представляющих собой соединение нескольких логических элементов, в левой части таблицы перечисляются все возможные комбинации входных сигналов, а в правой части  соответствующие значения на выходе логической схемы. Очевидно, что левые части таблицы будут одинаковыми для всех функций двух переменных, для всех функций трёх переменных и т.д. Традиционно комбинации сигналов в них располагают в порядке возрастания соответствующих двоичных кодов. В правой части таблицы указывается значение функции. Она равна1 для значений переменных приведенных в аналитическом выражении и 0 в отсутствующих комбинациях. Пример таблицы истинности приведен в таблице 1. Эта таблица в дальнейшем будет использована в качестве примера иллюстрирующего выполнение практического задания. Х3 Х2 Х1 Х0 F 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Аналитическое выражение для данной таблицы: б) Составление логических схем Логические схемы составляются из элементов И, ИЛИ, НЕ и должны соответствовать заданному логическому выражению. Пример логической схемы, соответствующий первому и второму слагаемому аналитического выражения (1) приведен на рисунке 1. Рисунок 1. – Логическая схема дешифратора, соответствующая первым двум слагаемым Минимизация логических выражений Упрощение выражений булевых функций при проектировании информационных устройств делается с целью сократить объем оборудования, необходимого для реализации этих функций. Предпочтительной формой получаемого выражения является ДНФ. Для ДНФ имеется удобное графическое представление, а переход от ДНФ к техническому базису «И-НЕ» выполняется очень просто. ДНФ называется минимальной, если она содержит наименьшее число букв по сравнению с другими эквивалентными выражениями вида ДНФ. Под «буквой» понимается каждое вхождение аргумента в формулу. Например, выражение   состоит из восьми символов при всего трех аргументах. Задачу минимизации заданной логической формулы в принципе можно решить обычными средствами булевой алгебры путем постепенного упрощения этой формулы с использованием главным образом операций склеивания и поглощения. Минимизация логических выражений может осуществляться с помощью различных методов на основе правил булевой алгебры, в частности, диаграммы Вейча, диаграммы Венна и табличным методом, но наиболее простым и наглядным является графический способ минимизации с помощью карт Карно. Назначение карты Карно  найти логические суммы прямого и инверсного значения переменных. Для любой переменной, например, a , такая сумма равна   при любом значении : при  это будет , при  это . Поэтому при вынесении за скобки в выражении: Сумму  можно отбросить, при этом результат выражения не изменится. В этом и заключается минимизация логических выражений с помощью карт Карно. Для достижения поставленной цели минимизации нужно соблюдать правила разметки осей карты: 1. вертикальная ось размечается независимо от горизонтальной; 2. начинать разметку можно с любого сочетания переменных; 3. все сочетания переменных должны быть перечислены; 4. Для соседних клеток карты сочетание переменных должно отличаться не более чем одним знаком, причем соседними являются крайние клетки строки (столбца). Для функции двух переменных карта Карно  это квадрат 2x2 клетки. В этих клетках размещаются 4 значения функции из последнего столбца таблицы истинности. Рисунок 2.- Таблица истинности (а) и карта Карно (б) для функции двух переменных Для функции трех переменных карта Карно  это прямоугольник 2x4 или 4x2 клетки. В этих клетках размещаются 8 значений функции из последнего столбца таблицы истинности. При разметке большей из осей нужно четко придерживаться последнего, четвертого правила разметки и следить за тем, чтобы соседними не оказались сочетания 00 и 11, либо 01 и 10, в которых одновременно меняются обе переменные. Для функции четырех переменных карта Карно  это квадрат 4x4 клетки. В этих клетках размещаются 16 значений функции из последнего столбца таблицы истинности. При разметке обеих осей нужно также четко придерживаться последнего, четвертого правила разметки и следить за тем, чтобы по одной оси соседними не оказались сочетания, в которых одновременно меняются обе переменные. В клетки карты проставляются конкретные значения (логические 0 и 1) из соответствующих строк таблицы истинности. Затем рассматриваются только те клетки, которые заполнены единицами. Все эти единицы должны быть обведены контурами по следующим правилам составления контуров: 1. Контуры должны быть прямоугольными и содержать количество единиц, равное 2n , где n  целое число. Таким образом, в контуре может быть либо одна, либо две, либо четыре, либо восемь единиц. 2. Количество единиц в контуре должно быть максимальным, при этом контуры могут пересекаться между собой. Нужно учитывать, что крайние строки являются соседними и крайние столбцы также являются соседними, поэтому контуры могут быть "разорванными". 3. Количество контуров должно быть минимальным, но все единицы должны быть охвачены контурами. Нельзя забывать об отдельно стоящих единицах. Каждая такая единица  это контур, которому соответствует полное логическое произведение всех переменных. После обведения контуров нужно записать минимальное выражение как логическую сумму логических произведений. Каждому произведению соответствует один контур карты Карно. В произведение входят только те переменные, которые остаются в данном контуре неизменными. При этом переменная входит в произведение с инверсией, если ее значение в данном контуре равно 0, и без инверсии, если ее значение равно 1. На рисунке 3 приведена карта Карно рассматриваемого примера для таблицы 1. . 00 01 11 10 X3X2 1 1 1 1 1 1 1 1 Рисунок 3.- Карта Карно для таблицы 1 1. Первый контур охватывает четыре единицы, ему соответствует сумма термов:  2. Второй контур охватывает две единицы. Ему соответствует сумма термов  3. Третий контур охватывает две единицы. Ему соответствует сумма термов  4. Четвертый контур охватывает 2 единицы. Ему соответствует сумма термов  В результате получаем итоговое выражение: Как видно, из приведенных аналитических выражений 1 и 2, второе значительно меньше по размеру, что влечет уменьшение числа элементов логической схемы со всеми вытекающими из этого последствиями. 1.5 Минимизация таблиц переходов и выходов автомата Эквивалентные автоматы имеют одни и те же входной и выходной алфавиты и одинаковые алфавитные операторы, но могут иметь неодинаковое число состояний и даже отличаться моделью. Если считать модель заданной и одной и той же для сравниваемых автоматов, то остается практически важная задача выбрать из множества эквивалентных автоматов один, имеющий минимально возможное число состояний. Эта задача формулируется как задача минимизации числа состояний заданного автомата. Для полностью определенных автоматов эта задача решается относительно просто с использованием понятия эквивалентности состояний. Рассмотрим сначала минимизацию состояний автомата Мура. Два состояния si и sj этого автомата являются 0-эквивалентными, если при них выдается одна и та же выходная буква yk = fy (si) = fy (sj). Два состояния sm и sn  являются 1-эквивалентными, если у них не только совпадает выходная буква, но еще при любом х выполняется условие: si = fs (am, x); sj = fs (an, x) , где si и sj  – 0-эквивалентные состояния. При любом входном сигнале переход из 1-эквивалентных состояний заканчивается в 0-эквивалентных состояниях. Как следует из определения, 1-эквивалентные состояния обладают также свойствами 0-эквивалентности. Аналогично определяются 2-эквивалентные состояния и т.д., вплоть до бесконечно эквивалентных. Пробегая по любой из возможных цепочек эквивалентных состояний, автомат должен одинаковым образом преобразовывать входные слова в выходные. При этом, например, 3-эквивалентность обеспечит одинаковую обработку слов длиной до 3 букв, а бесконечная эквивалентность – слов любой длины. Самый простой из известных алгоритмов минимизации числа состояний полностью определенных автоматов – алгоритм Хона и Ауфенкампа состоит в последовательном разбиении внутреннего алфавита заданного автомата на классы эквивалентности, начиная с низшего вида эквивалентности. Таблица переходов автомата Мура x1 x2 x3 Класс 0-эквивалентности s0/y1 s0 s1 s3 А1 s1/y2 s4 s2 s1 А2 s2/y1 s2 s1 s3 А1 s3/y1 s6 s0 s1 А1 s4/y3 s3 s4 s5 А3 s5/y3 s3 s5 s4 А3 s6/y3 s3 s5 s4 А3 Разбиение на классы 0-эквивалентности происходит очевидным образом: А1 = { s 0, s 2, s 3}; A2 = {s 1}; A3 = { s 4, s 5, s 6}. Полученный результат оформим в виде таблицы 0-разбиения, которая аналогична исходной таблице переходов, но «старые» состояния сгруппированы в классы 0-эквивалентности, а вместо «новых» состояний в клетки таблицы вписаны обозначения соответствующих классов (табл. 4.5). Таблица 4.5 Таблица 0-разбиения заданного автомата Мура Класс 0-эквивалентности Состояние x1 x2 x3 Класс 1-эквивалентности A1 s0 s2 s3 A1 A1 A3 A2 A2 A1 A1 A1 A2 B1 B1 B2 A2 s1 B3 A3 s4 s5 s6 A1 A1 A1 A3 A3 A3 A3 A3 A3 B4 B4 B4 Состояния А1, А2, А3 в графах x1, x2, x3 ставятся на данных т. 4.4 , заменяя si  Ai (А1 = { s 0, s 2, s 3}; A2 = {s 1}; A3 = { s 4, s 5, s 6}.) Внутри каждого из классов 0-эквивалентности выделим классы 1-эквивалентности, которые обнаруживаются по совпадению строк таблицы. Всего получилось четыре класса: В1 = {s0, s2};  B2 = {s3};  B3 = {s1};  B4 = {s4, s5, s6}. В таблице 4.5 строка состояния A2 не заполнена, так как в этом нет необходимости: и без дальнейшего анализа ясно, что это состояние образует один самостоятельный класс бесконечной эквивалентности. Продолжение процесса разбиения на классы показано в таблице 1-разбиения (табл. 4.6). Таблица 4.6 Таблица 1-разбиения заданного автомата Мура Класс 1-эквивалентности Состояние x1 x2 x3 Класс 2-эквивалентности A1 s0 s2 s3 B1 B1 B4 B3 B3 B1 B2 B2 B3 C1 C1 C2 A2 s1 C3 A3 s4 s5 s6 B2 B2 B2 B4 B4 B4 B4 B4 B4 C4 C4 C4 В правом столбце размечены классы 2-эквивалентности, число которых оказалось равным числу классов 1-эквивалентности. Дальнейшее повторение описанных шагов разбиения не изменит числа классов, поэтому можно считать полученные четыре класса классами бесконечной эквивалентности. Каждый класс бесконечной эквивалентности заменим одним новым символом состояния и в результате получим новый автомат, эквивалентный заданному, но имеющий только четыре состояния (табл. 4.7): {s0, s2} b0; {s1} b1; {s3} b2; {s4, s5, s6} b3. Таблица 4.7 Таблица переходов минимизированного автомата Мура x1 x2 x3 b0/y1 b0 b1 b2 b1/y2 b3 b0 b1 b2/y1 b3 b0 b1 b3/y3 b2 b3 b3 Минимизация числа состояний автомата Мили по алгоритму Ауфенкампа и Хона выполняется аналогично, но понятие 0-эквивалентности здесь не имеет смысла. Поэтому разбиение начинается с уровня 1-эквивалентности. 1-эквивалентные состояния si и sj автомата Мили отвечают требованию  уk = fy (si, x) = fy (sj, x) при любых х. Выполним минимизацию автомата Мили, заданного таблицей 4.8. Таблица 4.8 Таблица переходов автомата Мили x1 x2 x3 Класс 1-эквивалентности s0 s0/y1 s1/y2 s4/y1 B1 s1 s0/y1 s2/y2 s4/y1 B1 s2 s1/y2 s5/y1 s4/y1 B2 s3 s3/y1 s4/y2 s4/y1 B1 s4 s0/y1 s5/y2 s4/y1 B1 s5 s4/y2 s2/y1 s4/y1 B2 Три класса 1-эквивалентности представим в виде таблицы 1-разбиения (табл. 4.9). Таблица 4.9 Таблица 1-разбиения заданного автомата Мили Класс 1-эквивалентности Состояние x1 x2 x3 Класс 2-эквивалентности B1 s0 s2 s3 s4 B1 B1 B1 B1 B1 B2 B1 B2 B1 B1 B1 B1 C1 C2 C1 C2 B2 s2 s5 B1 B1 B2 B2 B1 B1 C3 C3 2-разбиение показано в табл. 4.10, в правом столбце которой размечены классы 3-эквивалентности. Таблица 4.10 Таблица 2-разбиения заданного автомата Мили Класс 2-эквивалентности Состояние x1 x2 x3 Класс 3-эквивалентности C1 s0 s3 C1 C1 C2 C2 C2 C2 D1 D1 C2 s1 s4 C1 C1 C3 C3 C2 C2 D2 D2 C3 s2 s5 C2 C2 C3 C3 C2 C2 D3 D3 D1 = {a0, a3}; D2 = {a1, a4}; D3 = {a2, a5}. Заменив обозначения состояний составим таблицу переходов минимизированного автомата (табл. 4.11). Таблица 4.11 Таблица переходов минимизированного автомата Мили x1 x2 x3 b0 b0/y1 b1/y2 b1/y1 b1 b0/y1 b2/y2 b1/y1 b2 b0/y2 b2/y1 b1/y1 (далее аналогичный пример из Зайцева) Рассмотрим правила минимизации абстрактных таблиц переходов и выходов автомата. Задача минимизации автомата A состоит в нахождении эквивалентного автомата A' , содержащего минимально возможное число состояний. Минимизация основана на объединении в одно состояние множеств совместимых состояний. Состояния s1, s2,…,sk называются совместимыми, если при подаче на вход автомата любого входного слова xi = xi1 xi2… xin выходное слово yi, с точностью до неопределённых значений определяется только значением входного слова и не зависит от состояния si {si1, si2 ,…,sik}, в котором первоначально находился автомат. Если в вышеприведённом определении длину входного слова ограничить l символами, то состояния, удовлетворяющие этому определению, будут называться l - совместимыми. В частности, если состояния si1, si2 ,…,sik односовместимые, то при подаче на вход автомата одного любого входного сигнала x на выходе автомата будет сигнал, определяемый только значением входного сигнала, а не состоянием si {si1, si2 ,…,sik}, в котором находился первоначально автомат. Одно-совместимые состояния могут быть просто найдены по таблице выходов автомата Мили. Если некоторые столбцы таблицы выходов одинаковые, с точностью до неопределённых сигналов, то состояния, отмечающие эти столбцы, односовместимые. На рисунке 1.16 приведена таблица выходов автомата. s1 s2 s3 s4 x1 y1 y1 y2 - x2 - y1 - y2 x3 y2 y2 - y2 В приведённом автомате имеется два множества односовместимых состояний: 1) {s1,s2} 2) {s3,s4} . Всякое максимальное множество l - совместимых между собой состояний автомата, то есть такое множество, к которому нельзя добавить ни одного нового состояния без нарушения свойств l - совместимости, называется l - классом. Алгоритм минимизации числа состояний автомата S следующий: 1) Находятся последовательные разбиения π1, π 2,... π к, π к+1 множеств состояний автомата A={s0, s1, s2,..., sm} на классы одно-, двух-, k-, (k+1)-совместимых состояний до тех пор, пока на каком-то k+1 шаге не окажется, что π к+1= π к. Разбиение π к называется предельным. 2) В каждом предельном классе k - совместимых состояний выбирается по одному состоянию, которые образуют множество S' состояний минимального автомата A' , эквивалентного автомату A. 3) В таблицах переходов и выходов вычёркиваются столбцы, соответствующие не вошедшим в множество S' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества S'. 4) В качестве начального состояния s'0 выбирается одно из состояний, эквивалентное s0 . В частности, удобно за s'0 выбирать само состояние s0 . Для примера, найдем минимальные таблицы переходов и выходов автомата A, изображённого на рисунке 1.17. s0 s1 s2 s3 s4 s5 s6 s7 s0 s1 s2 s3 s4 s5 s6 s7 x0 s0 s1 s7 s1 s0 s4 s5 s3 x0 y0 - y0 y1 y1 y1 - y1 x1 s4 s3 s1 s5 s5 s2 s1 s0 x1 y1 y1 - y0 - y0 y0 y0 Рисунок 1.17 – Таблицы переходов и выходов 1) Находим разбиение π1 множества состояний s0, s1, s2, s3, s4, s5, s6, s7 на одно-совместимые классы. По таблице выходов находим, что таких класса два: В1={s0,s1.s2}, B2={s3, s4, s5, s6, s7}. Подставим в таблицу переходов (рисунок 1.17) вместо состояний s0 – s7 соответствующие значения В1, В2. После подстановки получим таблицу, изображённую на рисунке 1.18. s0 s1 s2 s3 s4 s5 s6 s7 x0 B1 B1 B2 B1 B1 B2 B2 B2 x1 B2 B2 B1 B2 B2 B1 B1 B1 Рисунок 1.18 б) Находим разбиение множества состояний s0, s1, s2, s3, s4, s5, s6, s7 на 2-совместимые классы. Двух - совместимые классы находятся внутри одно-совместимых классов. Выделяют их по следующему общему правилу. Если в таблице переходов автомата, в котором состояния обозначены наименованиями l-совместимых классов, несколько столбцов, относящихся к одному и тому же классу, одинаковые, то состояния автомата, обозначающие эти столбцы, образуют l+1 - совместные состояния. В соответствии с этим правилом, по таблице (рисунок 1.18) находим 2-совместимые классы. С1={s0,s1} , C2={s2} , С3={s3,s4} , C4={s5,s6,s7}. Подставим в таблицу переходов (рисунок 1.17) вместо состояний s0 – s7 соответствующие значения С1, С2, С3, С4 . После подстановки получим таблицу, изображённую на рисунке 1.19. s0 s1 s2 s3 s4 s5 s6 s7 x0 C1 C1 C4 C1 C1 C3 C4 C3 x1 C3 C3 C1 C4 C4 C2 C1 C1 Рисунок 1.19 в) Находим разбиение π3 множества состояний s0, s1, s2, s3, s4, s5, s6, s7 на 3-совместимые классы. Оно находится по таблице (рис.1.19) аналогично тому, как были найдены 2-совместимые классы. D1={s0,s1}, D2={s2}, D3={s3,s4}, D4={s5}, D5={d6}, D6={s7}. Подставим в таблицу переходов (рисунок 1.17) вместо состояний s0 – s7 соответствующие значения D1, D2, D3, D4, D5, D6. После подстановки получим таблицу, изображенную на рисунке 1.20. s0 s1 s2 s3 s4 s5 s6 s7 x0 D1 D1 D6 D1 D1 D3 D4 D3 x1 D3 D3 D1 D4 D4 D2 D1 D1 г) Находим разбиение π4 множества состояний s0, s1, s2, s3, s4, s5, s6, s7 на 4-совместимые классы: E1={s0,s1}, E2={s2}, E3={s3,s4}, E4={s5}, E5={s6}, E6={s7}. Разбиение π4 совпадает с разбиением π3 , следовательно, разбиение π3 предельное. 1 Находим множество S' состояний минимального автомата A' ={ s0,s2,s3,s5,s6,s7}. 3. Из таблицы (рисунок 1.17) вычеркиваем состояния, не вошедшие в множество S' , а в оставшихся столбцах таблицы переходов все состояния заменяем на эквивалентные из множества S' (s0  s1, s3  s4). В результате получим таблицы переходов и выходов, изображенные на рисунке 1.21. s0 s2 s3 s4 s5 s6 s7 s0 s2 s3 s4 s5 s6 s7 x0 s0 s7 y1 s0 s3 s5 s0 x0 y0 y0 y1 y1 y1 - y1 x1 s1 s0 y0 s5 s2 s1 s0 x1 y1 - y0 - y0 y0 y0 Рисунок 1.21 – Таблицы минимального автомата Причем, если в таблице выходов вычеркивается столбец, имеющий на пересечении с i-ой строкой определенный сигнал yj, а в оставшемся столбце, отмеченном состоянием, эквивалентным состоянию, отмечающем вычеркнутый столбец, на пересечении с i-ой строкой проставлен прочерк, то в оставшемся столбце вместо прочерка необходимо записать сигнал yj. 2 Проектирование операционного устройства 2.1 Структура операционного устройства В любой системе обработки цифровой информации можно выделить операционный и управляющий блоки. Такой подход упрощает проектирование, а также облегчает понимание процесса функционирования вычислительного устройства. Данный процесс состоит из того, что операционный блок производит определенные операции преобразования информации под управлением сигналов, вырабатываемых управляющим блоком. Эта распределенная во времени последовательность управляющих сигналов, порождающая в операционном блоке нужную последовательность элементарных преобразований информации, составляет микропрограмму операции. Представим центральную часть ЭВМ, называемую в дальнейшем операционным устройством, как совокупность управляющего и операционного автоматов (рисунок 2.1). Функциональная и структурная организация операционного устройства базируется на принципах микропрограммного управления. Управляющий автомат в операционном устройстве формирует набор управляющих сигналов Y={y1,y2,...yN} (под воздействием кода операции G и осведомительных сигналов X={x1,x2,...xL}), поступающих в операционный автомат и реализующих микропрограмму работы дискретного устройства. Рисунок 2.1 – Операционное устройство Функция операционного автомата состоит в непосредственном выполнении заданного набора операций над словами множества D с целью вычисления множества выходных слов R. В общем случае задача структурного синтеза операционного устройства сводится к нахождению общих приемов построения структурных схем цифровых автоматов. Порядок выполнения операций в дискретном устройстве определяется микропрограммой, представляющей совокупность микроопераций и логических условий. Под микрооперацией будем понимать элементарную операцию, выполняемую над содержимым одного операционного элемента за один машинный такт. Множество микроопераций Yt={yt1,yt2,...ytk}, выполняемых за один такт, назовем микрокомандой. Выполнение микропрограммы состоит в последовательном выполнении отдельных микрокоманд. Эта последовательность определяется логическими условиями X={x1,...xL}, формирующимися в операционном автомате и поступающими на вход управляющего автомата. В качестве исходного языка для записи микропрограммы обычно используется язык граф-схем алгоритмов - связный ориентированный граф в каждой условной вершине которого записывается один из элементов множества X={x1,...xL}, входных переменных, а в каждой операторной вершине - микрокоманда Yt={yt1,yt2,...ytk}. Далее мы рассмотрим способы получения абстрактных таблиц переходов и выходов автомата по графу алгоритма. Микрооперации функционально совместимы, если они могут быть выполнены в течение одного машинного такта. Структура операционного автомата может внести ограничения на количество одновременно выполняемых микроопераций, то есть функционально совместимые операции могут оказаться несовместимыми на структурном уровне. Таким образом, управляющие сигналы управляющего автомата инициируют микрооперации, реализуемые в операционном автомате, при этом возможность параллельного выполнения микроопераций определяется исходя из их труктурной совместимости, зависящей от типа операционного автомата. Функция операционного автомата сводится к вводу, выводу и хранению слов информации, выполнению микроопераций и вычислению логических условий. В состав операционного автомата входят: память S, предназначенная для фиксации входных, промежуточных и выходных значений, функциональные преобразователи Ф для вычисления содержимого памяти автомата и функциональные преобразователи ψ, для вычисления логических условий (рисунок 2.2). Рисунок 2.2 – Операционный автомат Разработка операционного автомата сводится к оценке различных структур в зависимости от требований к быстродействию и стоимости операционного устройства. Базовой для синтеза различных структур операционного автомата является каноническая структура, которая изображается с помощью элементов, представленных на структурном уровне, дающем общее представление о схемах. Синтез канонической структуры осуществляется на основе: - множества информационных слов S, которым ставятся в соответствие регистры той же разрядности (Sα,Sβ1,...Sβ2); - множества микроопераций Y={y1,y2...ym}; - множества логических условий X={x1,x2...xl}; Каждой из операций ставится в соответствие оператор вида Sα = ψ m(Sβ1, Sβ2 ...Sβk), реализованный на структурном уровне следующей схемой (рисунок 2.3). Каждому логическому условию ставится в соответствие комбинационная схема ψ l так, что xl= ψ l (Sβ1, Sβ2 ...Sβq) (рисунок 2.4). Обладая максимальной производительностью каноническая структура является избыточной по затратам оборудования, так как все микрооперации, связанные с вычислением одного и того же слова, являются функционально-несовместимыми и могут быть реализованы меньшим количеством схем. Например, если кодопреобразователи φm и φn реализуют эквивалентные функции (рис.2.5), то для вычисления слова Sα, используют один обобщенный оператор φ (рисунок 2.6). Если в микропрограмме встречаются микрооперации вида Sa = φm(Sa1, Sa2 ...Saq) и Sb = φm(Sb1, Sb2 ...Sbn), вычисляющие значения слов Sa и Sb с использованием одной функции φm, применяемой к различным наборам значений Sa1, Sa2 ...Saq) и Sb = φm(Sb1, Sb2 ...Sbn), то оптимальный подход к синтезу устройства может предполагать использование только одного функционального кодопреобразователя. Однако, использование одной комбинационной схемы для выполнения нескольких микроопераций исключает совместимость этих микроопераций, то есть их выполнение возможно только в различных тактах. При этом производительность операционного устройства может значительно упасть. 2.3 Классы операционных автоматов Операционный автомат, производительность которого не ниже производительности автомата с канонической структурой, а затраты оборудования минимальны выделяется в класс I-автоматов (рисунок 2.7). Требуемая производительность может быть обеспечена только в том случае, если синтезируемая структура не будет вносить ограничений на совместимость микроопераций, поэтому для I-автоматов характерно, что каждый из регистров обслуживается своей комбинационной схемой. Рисунок 2.7 – I-автомат Синтез I-автоматов состоит из следующих этапов: 1. Множество микроопераций Y={y1,y2...ym} разбивается на подмножества Y1,Y2,...Yn соответствующие словам S1, S2 . . .Sn. 2. На подмножестве Yi (i=1,…n) выделяются классы эквивалентных микроопераций kij. 3. Для каждого класса kij, содержащего не менее двух эквивалентных микроопераций строится обобщенный оператор. 4. На основе содержательного графа с использованием обобщенных операторов строится структура I-автоматов. При выполнении операций затраты оборудования в комбинационной части автомата можно минимизировать, если каждую комбинационную схему φm обобщить по отношению ко всем регистрам (словам S1,...Sn), то есть использовать каждую комбинационную схему φm для выполнения всех эквивалентных микроопераций. Такой операционный автомат, синтезированный по принципу обобщения всех комбинационных схем, выделяется в класс M-автоматов (рисунок 2.8). Рисунок 2.8 – M-автомат Любая микрооперация, выполняющая преобразования φm, реализуется с помощью общей комбинационной схемы Ф равнодоступной каждому регистру устройства. Информация на схему Ф поступает по информационным шинам А1, А2 под действием соответствующих управляющих сигналов аi{a1,a2,...an} и bj{b1,b2,...,bn}. Комбинационная схема Ф под действием управляющего сигнала φm реализует функцию Z= φm (A1,A2), результат выполнения которой выдается на шину Z и под действием сигнала dk{d1,d2,...dn} записывается в регистр Sk. Таким образом, для реализации микрооперации Sk := φm (Si,Sj) в M-автомат поступает специфичный набор управляющих сигналов: ai, bj, φm, dk, который в свою очередь порождает собственный набор микроопераций: {A1:=Si}, {A2:=Sj}, {Z:= φm (A1,A2)}, {Sk:=Z}. Организация комбинационной схемы ψ, формирующей логические условия, не отличается от канонической структуры, так как, в противном случае, при последовательном анализе условий схема значительно бы усложнилась. Дальнейшая минимизация схемы операционного автомата возможна за счет объединения шин, по которым информация передаётся в комбинационную схему Ф. В общем случае для подключения регистров необходимо наличие двух управляемых шин. Но далеко не всегда каждый регистр подключается к обеим обобщенным шинам A1, A2. В общем случае количество их может колебаться от m до 2m. Минимизация числа управляющих шин сводится к разделению множества числа слов S на два подмножества: A1 = {Sa1, Sa2 ...Sar} и A2 = {Sb1, Sb2 ...Sbp} которые должны удовлетворять следующим условиям: 1) Если слова Si и Sj участвуют в одной и той же микрооперации, они должны находится в разных подмножествах, то есть Si A1, Sj A2 или Si  A2 , Sj A1. 2) Каждое слово должно входить хотя бы в одно из подмножеств. 3) Распределение слов по подмножествам должно производиться таким образом, чтобы затраты оборудования в схемах передачи операндов с регистров на схему Ф были минимальными. Наряду с минимальными затратами оборудования производительность M-автоматов минимальна, так как в каждом такте может быть реализована только одна микрооперация. IM-автоматами называются операционные автоматы, структурная организация которых вносит ограничения на совместимость операций, но в то же время обеспечивает выполнение за такт более чем одной микрооперации. Выделяют IM-автоматы с параллельной комбинационной частью (рисунок 2.9) и IM-автоматы с последовательной комбинационной частью (рисунок 2.10). Рисунок 2.9 – IM-автомат с параллельной комбинационной частью Первые можно рассматривать, как комбинацию из нескольких M-автоматов, имеющих общую память. Они хорошо приспособлены для реализации микропрограмм, в которых присутствует большое число совместимых микроопераций, и линейные участки микропрограммы не содержат микроопераций, связанных с вычислением одного и того же слова. Комбинационная схема Фi равнодоступна всем регистрам операционного автомата. Автомат может выполнить за один такт L функционально-совместимых микроопераций (L  m). Синтез данного автомата производится путем разбиения исходного множества микроопераций на L подмножеств и синтеза M-автоматов для каждого из этих подмножеств. Разбиение проводится таким образом, чтобы функционально-совместимые микрооперации, которые в соответствии с микропрограммой могут выполняться одновременно, находились в различных подмножествах. Рисунок 2.10 – IM-автомат с последовательной комбинационной частью Структура IM-автоматов с последовательной комбинационной частью, как правило, реализуется в виде функционально-законченных устройств с фиксированной системой команд и фиксированной длиной разрядной сетки. Синтез автомата данного типа выполняется на основе выделения из функциональных микропрограмм линейных последовательностей, в каждой из которых выделяются микрооперации, результат выполнения которых присваивается одному и тому же слову. При возможности, такие микрооперации объединяются в составные. Рассмотрим набор микроопераций: S1:= S3, S1:=S1+S2, S1:= R1(S1). Их можно объединить в одну составную микрооперацию, записав её следующим образом: S1:= R1( S3+ S2). В общем виде: Sk:=φp(Si), Sk:= φq(Sk,Sj), Sk:= φr(Sk) или Sk:= φr(φq(Sj, φp(Si))). Для универсальности автомат, позволяющий выполнить составную функцию, должен иметь возможность выполнить и более простые микрооперации. Выполнение таких микроопераций будет обеспечено, если в автомате имеется возможность реализовать следующие действия: A3:=A2, A4:=A1, Z:= φr (A1), Z:= φr (A3) и т.д., то есть сквозное прохождение сигнала через комбинационные схемы без преобразования. Схемы Ф1,...Ф3 являются, как правило, достаточно специализированными: Ф1 – преобразует коды, передаваемые по шине А2 путем инвертирования, добавления знаковых разрядов и выполнения других аналогичных микроопераций, Ф2 – выполняет бинарные операции, Ф3 – для преобразования информации путем сдвига. Для микропроцессоров типичной является организация, при которой их внутренние регистры используются в различных целях. Система связей у этих регистров, как правило, магистральная, обеспечивающая возможность разнообразных межрегистровых пересылок. В связи с этим, внутренние регистры, используемые только для выполнения арифметических и логических операций, в операционном автомате могут отсутствовать. В этом случае можно рассматривать операционный автомат микропроцессора как комбинационную схему, настраиваемую сигналами микроопераций на различные преобразования операндов, находящихся в регистрах микропроцессора. Тогда, если произведено разбиение операционного автомата и соответствующего набора микроопераций на несколько операционных блоков для отдельных групп операций, то формальное описание процессов функционирования операционного устройства происходит на уровне машинных команд. В том случае, когда для выполнения программы необходимо использовать большое число внутренних слов, вместо набора регистров может использоваться оперативное запоминающее устройство. Принцип работы данного класса автоматов (S-автоматов) совпадает с принципом работы M-автоматов. Этот автомат (рисунок 2.11) является самым медленным из рассмотренных, так как запись информации в основную память требует значительно больше времени, чем занесение информации на регистр. Поэтому для повышения быстродействия S-автоматов результат выполнения команды заносится не в ОЗУ, а на один из регистров S1, S2 и в дальнейшем используется как аргумент в следующей операции. Рисунок 2.11 – S –автомат Занесение результата на регистры производится только в том случае, если в следующей операции этот результат используется в качестве аргумента. Это позволяет сократить число обращений к памяти и повысить быстродействие автомата. Рисунок 2.12 Увеличение количества регистров, в которых хранится информация (рисунок 2.12), дополнительно уменьшает количество обращений к основной памяти и характерно для процессоров с сокращенным набором команд. Так как количество связей между Si и Ф возрастает, то для управления работой автомата вводится дополнительный набор управляющих сигналов c1,c2,...cn. Альтернативой увеличению регистрового блока может служить ассоциативная кэш память, которая наряду с блоком регистров, обычно используется в большинстве современных микропроцессоров. 2.4 Управление выполнением операции Автоматическое управление вычислительным процессом осуществляет устройство управления. Устройство управления формирует управляющие сигналы, которые поступают в операционный автомат, а также на линии внешней магистрали, связывающей операционное устройство с остальными компонентами вычислительной машины. На протяжении машинного цикла устройство управления обеспечивает считывание очередной команды из оперативной памяти, её дешифрацию, формирование адресов операндов, пересылку операндов в операционное устройство, выработку необходимой для выполнения данной команды последовательности управляющих сигналов, сохранение результата операции, формирование адреса следующей команды. При централизованном способе управления выработку всех управляющих сигналов, необходимых для выборки и выполнения любой операции из системы команд машины, осуществляет единое устройство управления. Такие устройства управления часто используют асинхронный принцип тактирования и применяются преимущественно в одноадресных машинах со сравнительно небольшим числом микроопераций. Обычно используется смешанный способ управления, при котором управляющие сигналы, инициирующие прием команды и её дешифрацию, вырабатывает центральное устройство управления, а исполнение операции обеспечивает микропрограммный автомат местного устройства управления. По способу построения микропрограммные автоматы могут быть с программируемой или схемной (жесткой) логикой. Идея устройств управления с программируемой логикой, выдвинутая Морисом Уилксом (M.V. Wilkes, 1951), основана на том, что для инициирования любой микрооперации достаточно сформировать на соответствующей линии управляющий сигнал, для чего в регистр микрокоманд из управляющей памяти микропрограмм последовательно считываются микрокоманды, содержащие информацию о сигналах управления. По способу формирования сигналов управления выделяют микропрограммные автоматы с горизонтальной, вертикальной и смешанной кодировкой микрокоманд. При горизонтальном кодировании в операционной части под каждый инициирующий микрооперацию сигнал выделяется один разряд, что позволяет в рамках одной микрокоманды формировать любые сочетания микроопераций, обеспечивая максимальный параллелизм. Однако, данный способ кодирования приводит к большим затратам на хранение операционных частей микрокоманд и низкой эффективности использования памяти микропрограмм. Вертикальное кодирование, при котором операционная часть микрокоманды имеет минимальную длину, равную ближайшему к log2M большему целому, где M – число различных микроопераций, позволяет минимизировать затраты на хранение микрокоманд в памяти микропрограмм. При этом в каждой микрокоманде кодируется только одна микрооперация, что приводит не только к снижению производительности, но и увеличивает длину микропрограммы. При смешанном кодировании, которое делится на горизонтально-вертикальное и вертикально-горизонтальное, микрооперации разбиваются на группы. В горизонтально-вертикальном методе каждая группа представляется отдельным полем операционной части и включает несовместимые микрооперации, которые кодируются вертикальным способом. Как и в случаях горизонтального и вертикального кодирования, при горизонтально-вертикальном способе функции каждого поля микрокоманды фиксированы, то есть имеет место прямое кодирование. В вертикально-горизонтальном методе в группу включаются выполняемые в одном такте операции, при этом операционная часть делится на две части. Первая часть, длина которой соответствует максимальному количеству микроопераций в группе, кодируется горизонтально. Вторая часть, указывающая на принадлежность микроопераций к определенной группе, кодируется вертикально. Таким образом, поле второй части отводится для интерпретации других полей, то есть имеет место косвенное кодирование. Различают однофазные и многофазные микрокоманды. В первом случае все микрооперации, указанные в микрокоманде, выполняются одновременно за один такт. В другом случае такт разбивается на интервалы, называемые фазами или микротактами, и микрооперации выполняются в различных фазах. При двухуровневом кодировании микроопераций операционная часть микрокоманды определяет нанокоманду, которая хранится в памяти нанокоманд и используется для непосредственного формирования управляющих сигналов. Помимо операционной части в микрокоманде содержится также адресная часть, позволяющая сформировать адрес очередной микрокоманды. По способу формирования адреса следующей микрокоманды различают управляющие автоматы с принудительной адресацией, в которых адрес перехода явно указывается в микрокоманде, и автоматы с естественной адресацией, использующие микропрограммный счетчик. Если микропрограмма содержит незначительное количество переходов, то использование естественной адресации микрокоманд минимизирует объем памяти микропрограмм. Содержимое памяти микропрограмм определяет не только последовательность микроопераций, которые должны выполняться на каждом этапе цикла команды, но также последовательность самих этапов, представленных соответствующими микропрограммами. Запуск микропрограммы выполнения операции осуществляется путем преобразования поступающего из регистра команд кода операции в начальный адрес микропрограммы, который записывается в регистр адреса микрокоманд. Использование кода операции текущей команды для формирования адреса микропрограммы является примером неявного представления адреса. Каждая микропрограмма цикла завершается микрокомандой перехода, которая определяет дальнейшую последовательность реализуемых автоматом действий. Принцип управления с программируемой логикой обеспечивает достаточную гибкость: становится возможным изменять систему управления, не конструируя заново аппаратную часть, однако построенный на основе этого принципа управляющий автомат имеет невысокое быстродействие. Для повышения быстродействия управляющих автоматов с программируемой логикой могут использоваться: параллельная выборка микрокоманд из памяти микропрограмм; совмещение во времени работы операционного и управляющего устройства с конвейерной обработкой нескольких микрокоманд, находящихся на разных стадиях выполнения; однотактная реализация сложных разветвлений. В управляющих автоматах с жесткой логикой каждой микропрограмме соответствует свой набор логических схем с фиксированными связями между ними. Для начала выполнения микропрограммы код операции в регистре команд преобразуется в унитарный код, который активизирует схему, реализующую указанную операцию. Автомат с жесткой логикой обеспечивает наибольшее быстродействие при реализации простой системы команд, однако, при расширении набора команд происходит существенное усложнение аппаратной части. Введение в систему сложных команд приводит к тому, что наряду с жесткой логикой приходится прибегать к более медленным автоматам с программируемой логикой. Проектирование управляющих автоматов с жесткой логикой осуществляется на основе предложенного академиком В.М. Глушковым канонического метода, при котором структурный синтез автомата сводится к синтезу комбинационных схем. 3 Синтез микропрограммных автоматов 3.1 Способ получения абстрактных таблиц переходов и выходов автомата по графу алгоритма Микропрограммным автоматом принято называть конечный автомат, реализующий микропрограмму работы дискретного устройства. Функциональными операторами микропрограммы являются управляющие сигналы из множества Y={y1,....yn}, которые отождествляются с микрооперациями, то есть каждому управляющему сигналу ставится в соответствие микрооперация. Для синтеза микропрограммных автоматов удобно использовать язык графов алгоритмов, содержащий вершины четырех типов: начальную, конечную, операторную и условную. В каждой условной вершине записывается один из элементов множества X={x1,...xl} входных переменных. В каждой операторной вершине записывается микрокоманда Yt={yt1,....ytк} -подмножество множества всех микроопераций Y={y1,....yn}. При проектировании операционного устройства предварительно составляется содержательный граф алгоритма, в котором внутри условных и операторных вершин записываются не элементы множеств X и Y, а логические условия и микрооперации в содержательных терминах языка функционального микропрограммирования (Ф-языка). Этот язык позволяет описывать алгоритм, реализующий заданную микропрограмму работы операционного устройства в виде наборов микроопераций и условий. Основными элементами языка являются слова, поля и действия, обеспечивающие вычисление значений слов. Переход от содержательного графа к закодированному графу осуществляется путем установления соответствия между условиями и микрооперациями и элементами множеств X и Y. Описание работы дискретного устройства с помощью закодированного графа рассмотрим на примере (рисунок 3.1). Приведенный граф имеет четыре условных и пять операторных вершин. Для этого графа X={x1,x2,x3}, Y={y1,y2,y3,.y4}, поэтому у соответствующего дискретного устройства должно быть три входных и четыре выходных каналов. В устройстве реализуются пять различных микрокоманд: 1.Y0=0 ; 2.Y1={y1,y3}=Y5 ; 3.Y2={y1} ; 4.Y3={y2 ,y3,y4}; 5.Y4={y1,y3} Начальной вершине графа алгоритма соответствует некоторое начальное состояние дискретного устройства, при котором выполняется микрокоманда Y0, то есть выходные сигналы не выдаются. Если идти из начальной вершины по графу алгоритма в направлении ориентации дуг графа, выписывая при выходе из условной вершины по единице входную переменную, стоящую в одной вершине, а при выходе по нулю - отрицание этой переменной, то пройдя путь , прейдем к операторной вершине, в которой записана микрокоманда Y1={y1,y3}. Рисунок 3.1 Этому соответствует следующая работа дискретного устройства. Если в начальном состоянии на вход x2 придет сигнал, равный нулю (x2=0), то независимо от сигналов на остальных входных каналах, устройство перейдет в некоторое новое состояние, и на первом и третьем выходных каналах появятся сигналы равные единице (y1,y3=1), а на остальных выходных каналах - сигналы, равные нулю. То есть, будет выполнена микрокоманда Y1. Обозначим логическое условие перехода от есть, будет выполнена микрокоманда Y1. Обозначим логическое условие перехода от Y0 к Y1 как . Переход от Y2 к Y0 равен , то есть равняется логическому произведению условных вершин, лежащих на пути между вершинами Y2 и Y0. При этом, если выход из условной вершины по единице, то содержимое берется в прямом виде, если по нулю - в инверсном. Так как путь между Y5 и Y0 содержит пустое множество условных вершин, а логическое произведение пустого множества логических переменных равно единице, то переход a50=1. Таким образом: a03 = x2x1x3, , a14 = x1, , , a30 =1 и т.д. Абстрактный синтез автомата, производится в два этапа. На первом этапе выполняется отметка закодированного графа алгоритма символами а1,а2,...аM по следующим правилам. Для автомата Мили : - символом а1 отмечается вход вершины, следующей за начальной, а также вход конечной вершины; - входы всех вершин, следующих за операторными, кроме уже отмеченных символом а1, отмечаются а2,...аM, но не более, чем одним символом; - входы различных вершин, за исключением конечной, должны быть отмечены различными символами. Для автомата Мура : - символом а1 отмечаются начальная и конечная вершины; - различные операторные вершины отмечаются различными символами а2,...аM; - все операторные вершины должны быть отмечены, но не более, чем одним символом. После этого закодированный граф алгоритма становится отмеченным, что позволяет перейти ко второму этапу - получению абстрактных таблиц переходов и выходов. В качестве примера, рассмотрим отмеченный граф алгоритма для автомата Мили (рисунок 3.1). Если идти от одной отметки аm к другой отметке as в направлении ориентации дуг графа алгоритма, выписывая содержимое лежащих на этом пути вершин, то каждому такому пути можно поставить в соответствие слово , где Таким образом, путь вида - это путь по графу алгоритма из одной отметки am в другую отметку as (допустимо am = as), содержащий точно одну операторную вершину. Путь вида - это путь из некоторой отметки am в отметку ai, проходящий только через условные вершины. Переход от отмеченного графа алгоритма к таблицам переходов и выходов автомата Мили выполним следующим образом : 1) Будем считать, что a1,a2,...am - состояния автомата. 2) Находим все пути переходов на отмеченном графе алгоритма. При этом, если имеется несколько вхождений символа в путь перехода, то все эти символы, кроме одного удаляются. Если в путь перехода входят как xk, так и k , то такой путь перехода в дальнейшем не рассматривается. 3) Каждому пути перехода вида поставим в соответствие переход автомата S из состояния am в состояние as под действием входного сигнала X(am,as) = с выдачей выходного сигнала Y(am,as) = Ym . 4) Каждому пути перехода вида Ym поставим в соответствие переход автомата S из состояния am в состояние as под действием входного сигнала 1 с выдачей выходного сигнала Y(am,as). 5) Каждому пути перехода вида поставим в соответствие переход из am в ai. При этом выходной сигнал полагаем равным Y0 (пустая микрокоманда). В результате получаем автомат, имеющий столько же состояний, сколько символов потребовалось для отметки входов вершин графа алгоритма. Построим таблицу переходов и выходов автомата по отмеченному графу алгоритма, изображенному на рисунке 3.1. В этом случае имеем следующие пути переходов: Строим таблицы переходов и выходов, отмечая черточками неопределенные переходы (рисунок 3.2). Далее, по рассмотренным ранее правилам абстрактные таблицы минимизируются, и осуществляется переход к этапу структурного синтеза.