Лекция 7. Синтез микропрограммных автоматов

План: 1. Конечные автоматы.

2. Абстрактный автомат.

 

Конечные автоматы. Если входные и выходные переменные логических схем принимают значения из конечных алфавитов, они называются конечными автоматами.

Пусть Хс — алфавит входной переменной Xi, a Y_t — алфавит выходной переменной у с. Конечный автомат с п входами и т выхо­дами характеризуется входным алфавитом X = Х_г х Х₂ х... X хХ_п и выходным алфавитом Y = Y_x X Y2 х... X Y_m, причем символами входного алфавита служат слова х = (х_1у х₂, х_п) длины п, а символами выходного алфавита — слова у = (у_ъ у₂,...,у_т) длины m, где xi? Xi и y_i? Y_i. Особого внимания заслу­живают конечные автоматы с двузначным структурным алфави­том, зависимости между входными и выходными переменными которых выражаются булевыми функциями. Их значение обуслов­лено тем, что любая информация может быть представлена в двоич­ных кодах (двоично-десятичные коды чисел, телетайпный код в тех­нике связи и т. п.). В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окон­чания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвле­каются от существа этих процессов и считают, что переменные изме­няются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть раз­личными, но без потери общности их можно считать равными Δt. Предполагается, то тактовые моменты t_ν+1= t_ν + Δt определя­ются синхронизирующими сигналами. Таким.образом, вводится по­нятие дискретного автоматного времени t_v(v = 1, 2,...), причем переменные зависят не от физического времени, а от номера такта v, т. е. вместо непрерывных функций x(t) рассматриваются дискрет­ные значения x(v).

Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбина­ционных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход —выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую сово­купность промежуточных переменных s_l s₂,…, s_k, характеризую­щих состояние схемы. Набор всех возможных состояний, которые присущи данной схеме, называется множеством состояний. Если S₁, S₂,…, S_k — конечные алфавиты переменных состояния s_t, s₂, то множество состояний S = S₁ х S₂ x... x S_k также явля­ется конечным множеством.

. Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на v -м такте y(v) = = (y₁(v), y₂(v),…, y_m(v) однозначно определяется значениями входных переменных x(v) = (x₁(v), x₂(v),…, x_n(v)) и состоянием s(v) = s₁(v), s₂(v),…,s_k(v)) на том же такте, т. е. y(v) = λ(x(v),s(v)). Во-вторых, состояние s(v + 1) в следующем (v v + 1)-м такте одно­значно определяется входными переменными x(v) и состоянием s(v) в предыдущем такте, т. е. s(v + 1) = δ(x(v), s(v)).

Таким образом, состояние конечного автомата в любой тактовый момент характеризуется значениями такой совокупности перемен­ных, которая вместе с заданными значениями входных переменных позволяет определить выходные переменные в данный тактовый момент и состояние в следующий тактовый момент.

Ясно, что последовательностные схемы должны обладать способ­ностью сохранять предыдущее состояние до следующего такта в связи с чем их называют также автоматами с памятью или последовательностными машинами. В качестве памяти могут исполь­зоваться элементы задержки, на выходах которых повторяются входные воздействия со сдвигом во времени на интервал между тактами Δt. Широко применяются также различные запоминающие элементы, например, триггеры, способные сохранять состояния на выходах до тех пор, пока оно не изменяется в результате воздей­ствия на их входы.

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

Конечный автомат М определяется как система с конечным вход
ным алфавитом X ={ζ₁, ζ₁,…, ζ_p}, конечным выходным алфавитом Y = {v₁,v₂,…,v_q),конечным множеством состояний S={σ₁, σ_2,…, σ_r} и двумя характеристическими функциями:

 

s(v +l) = δ(x(v), s (v));

y(v)=λ(x(v), s(v)),

 

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

 

Блок-схема конечного автомата

 

 

В определении автомата участвует три конечных множества X, У, S и две функции δ и λ, задающие некоторые отношения между элементами этих множеств. Следовательно, конечный автомат можно обозначить упорядоченной пятеркой М={X,Y,S,δ,λ}. Мощности множеств X,Y,S равны соответственно:

где p_i, q_i,r_i - количество символов в алфавитах входной пере­менной х_i, выходной переменной у_i и переменной состояния s_i. При двоичном структурном алфавите р = 2ⁿ, q= 2^т и r = 2^k. Если необходимо подчеркнуть мощности множеств X, У и S, на которых определен конечный автомат, то его называют (p,q,r) - автоматом.

Характеристические функции б и λ, можно рассматривать как некоторые отображения множества X х S или его подмножества D X х S соответственно на множества S и Y. Если δ: X х S и λ: X х S → Y, автомат называется полным; если только δ: X х S →S, автомат называют полным по переходам. В случае, когда функции δ и λ определены не для всех наборов из множества X х S, автомат называют неполным или частично опре­деленным.

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

Между автоматами этих двух типов имеется взаимная связь и один из них может быть преобразован в другой. Положив в харак­теристических функциях автомата Мили s'(v) = (x(v), s(v)), получим y(v) = λ (s'(v)) и s'(v + 1)=(х(v + 1), s(v + 1))=(х(v + 1); δ(x(v), s(v))) = δ'(x(v + 1), s'(v)), т. е. приходим к автомату Мура. Обратный переход осуществляется подстановкой s(v) = = s'(v - 1), в результате чего получаем y(v) = λ'(s'(v))=λ'(x(v),s'(v -1))) = λ(x(v), s(v)), а также s(v + 1) = s'(v)= δ'(x(v), s'(v -1)) = δ(x(v), s(v)).

Для комбинационных схем функция перехода не имеет смысла, а функция выходов вырождается к виду у (v) = λ(x(v)). Их назы­вают автоматами без памяти или тривиальными автоматами.

Представления конечных автоматов. Автомат может быть задан различными способами, например, путем словесного описания его функционирования или перечислением "элементов множеств X, У, S, с указанием отношений между ними. При анализе и син­тезе конечных автоматов используются стандартные формы пред­ставления: таблицы, графы и матрицы. Элементы множеств X, Y, S удобно пронумеровать порядковыми числами, начиная с нуля, например: X = {0, 1, 2, 3}, Y = {О, 1} и S = {0, 1, 2, 3}. Тогда характеристические функции δ и λ, можно представить двумя таб­лицами, строки которых соответствуют состояниям, а столбцы - входам. Первая таблица, называемая таблицей переходов, соответ­ствует функции s(v + 1) = δ(x(v), s (v)), и ее клетки заполняются номерами состояний s(v + 1), в которые переходит автомат при воздействии x(v), и состоянии s(v) в данный тактовый момент. Вто­рая таблица, называемая таблицей выходов, соответствует функции y(v) = λ(х(v), s(v)), и ее клетки заполняются номерами выходов y(v) в данный тактовый момент, которые соответствуют воздействию x(v) и состоянию s(v) в тот же момент. Например, для заданных множеств X, Y, S такие таблицы могут иметь вид:

Обе таблицы можно объединить в общую таблицу переходов, если условиться записывать в клетках пары чисел (номер следую­щего состояния в числителе и номер выхода в знаменателе), т. е.

 

Граф автомата строится таким образом, что его вершины соот­ветствуют состояниям, а направленные дуги обозначаются как дизъюнкции входов, под воздействием которых совершается пере­ход из одного состояния в другое по направлению дуги. В знамена­телях записываются номера выходов, соответствующие этим пере­ходам. Граф, построенный в соответствии с при­веденной выше общей таблицей переходов будет иметь вид

 

Граф конечного автомата

Так как из состояния 0 автомат переходит в состояния 1, 2 и 3, то из вершины 0 графа исходят дуги в вершины 1, 2 и 3. При этом переход в состояние 1 со­вершается под воздействием 2 и ему соответствует выход 0, поэтому дуга из вершины 0 в 1 помечается как 2/0. Переход в состояние 2 совершается под воздействием 1 и ему соответствует выход 0, поэтому дуга из вершины 0 в 2 помечается как I/0. Переходы в со­стояние 3 совершаются под воздействиями 0 и 3 и им обоим соот­ветствует выход 0, поэтому дуга из вершины 0 в 3 помечается как дизъюнкция 0/0 V 3/0, Аналогично определяются и другие дуги графа. Петли соответствуют переходам, при которых состояния не изменяются. Так, рассматриваемый автомат переходит из состояния 2 в 2 под воздействиями 1 и 2, ко­торым соответствуют выходы 0 и 1. Следовательно, петля при вершине 2 помечается как дизъюнкция 1/0 V2/1.

Матрица соединения автомата М (или матрица переходов) представ­ляет собой квадратную таблицу в ко­торой номера строк и столбцов соот­ветствуют номерам состояний.

Клетка матрицы на пересечении i-й строки и j - го столбца заполняется дизъюнк­цией пар «вход - выход», которая приписана дуге графа исходящей из i -й вершины в j - ю вершину. При отсутствии та­кой ветви клетка заполняется нулем

Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, пре­образующей входные переменные x(v) и s(v) в выходные переменные y(v) и s(v + 1) в соответствии с заданными характеристическими функциями s(v + 1) = δ(х(v), s(v)) иy(v)= λ( х(v), s(v).). Для сохранения состояний s(v + 1) до следующего такта в цепь обрат­ной связи вводится необходимое количество элементов памяти.

При реализации автоматов в двоичном структурном алфавите можно использовать методы синтеза комбинацирнных схем. Для этого необходимо закодировать состояния схемы и представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осу­ществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если эле­менты множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, задан­ного таблицей, представленной выше, таблицу переходов можно преобразовать к виду:

Заменяя десятичные числа их двоичными эквивалентами, читае­мыми сверху вниз, получаем таблицу соответствия, в которой зна­чения функций s(v + 1) и y(v) представлены двоичными кодами:

 

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x_x(v), x₂(v) и переменным состояния s₁(v), s₂(v), а также три выхода, соответствующие перемен­ным состояния s₁(v + 1), s₂(v + 1) и выходной переменной y₁(v). Синтезиро­вав комбинационную схему, соответст­вующую полученной таблице и введя два элемента задержки З_г и 3₂, получим структурную схему автомата.

 

Структурная схема автомата

Литература:

1. Савельев А.Я. Прикладная теория цифровых автоматов. Учебник для вузов. М.: Высшая школа, 1987 г.

2. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1974 г.