Каноническая структура синхронного цифрового автомата

ЛЕКЦИЯ 3 1. ОСНОВНЫЕ ПОНЯТИЯ 1.1. Каноническая структура синхронного цифрового автомата Предметом изучения являются устройства, структура которых может быть представлена в виде конструкции из модулей двух типов комбинационной схемы (КС), на рисунках обозначена – CL (combinational logic), и регистра – RG (register) с динамической синхронизацией (рис.1). a syn s' CL C RG D Q s s b s' h Рис.1. Синхронный автомат (схема структурная) 1.2. Абстрактный конечный автомат В качестве основной математической модели СЦА используется абстрактный конечный автомат. Абстрактный конечный автомат - это математическая структура с тремя основными конечными множествами А, B, S А - называется множеством входных символов; B - называется множеством выходных символов; Q - называется множеством (символов) состояний. и двумя функциями: g: QA→Q, f: QA→B Абстрактный конечный автомат функционирует в автоматном времени t=0,1,2,..., определяемом как упорядоченное множество целых чисел. Это означает, что автоматное время дискретно, и существенным является лишь номер момента времени; упорядоченность множества означает, что автоматное время имеет “направление”. Если обозначить через а(t), b(t), q(t) переменные со значениями в соответствующих множествах в момент времени t, то работа абстрактного конечного автомата описывается уравнениями, которые называются каноническими q(t+1) = G(q(t),a(t)) b(t) = f(q(t),a(t)) G - называется оператором перехода. Оператор перехода G, кроме вычисления значения, выполняет также сдвиг во времени этого значения. f - называется функцией выхода; Принята также другая форма записи канонических уравнений: q := g(q,а) b = f(q,а) Знак двоеточие “:” означает операцию запоминания, а для дискретного времени − сдвиг значения на единицу времени. В этой записи g – функция перехода. Вычисления, выполняемые автоматом, можно рассматривать как процесс, т.е. строгую последовательность действий (шагов) преобразования символов, поступающих на вход автомата а в символы, появляющиеся на его выходе. a[1],a[2],a[3],...,a[t],... b[1],b[2],b[3],...,b[t],... При этом выполняется: g(q[0],a[1]a[2]) = g(g(q[0],a[1]),a[2]) f(q[0],a[1]a[2]) = f(g(q[0],a[1]),a[2]) Автомат отображает входные последовательности символов в выходные последовательности символов. Выходная последовательность порождается с той же скоростью, что и входная последовательность, ровно один выходной символ на каждый входной. Каждый очередной выходной символ однозначно определяется последовательностью ранее поступивших входных символов, т.е. вычисление имеет свою “историю”. Эта история сохраняется в автомате в виде переменной, которая называется – состояние автомата. Состояние автомата - это та минимальная информация, которая необходима для предсказания дальнейшего поведения автомата. Поведение автомата трактуется как его переходы из одного состояния в другое состояние в определенные моменты автоматного времени с одновременным вычислением выходного значения. 1.3. Соглашения … Для того чтобы абстрактный конечный автомат адекватно моделировал СЦА, необходимо выполнение некоторых соглашений. Входные и выходные сигналы СЦА, в общем случае, являются двоичными многоразрядными наборами, которые кодируют символы соответствующих множеств. Регистр в СЦА запоминает код состояния. Состояния кодируются двоичными наборами. Ход времени в СЦА инициируется изменением значения единственного сигнала - сигнала синхронизации sync. На каком-либо из фронтов этого сигнала изменяется содержимое RG, а значит и состояние автомата, так в схемах на рис.1 RG переключается по положительному (нарастающему) фронту сигнала sync. Переключающие фронты сигнала sync будем называть рабочими фронтами. Интервал времени между соседними рабочими фронтами называется тактовым интервалом или просто тактом (Т), рис.2. T t Рис.2. Структура такта Для абстрактного автомата не имеет смысла понятие такта, как некоторого интервала “непрерывного” времени. Применительно к абстрактному автомату можно понимать термин такт как изменение дискретного времени на одну единицу. Для реального синхронного цифрового автомата величина этого интервала − один из важнейших технических параметров, определяющих быстродействие схемы. Величина этого интервала должна быть достаточной для того, чтобы закончились переходные процессы в КС и установившиеся значения состояния могли быть записаны в RG. Переходные процессы могут начинаться из-за изменения либо состояния RG, либо изменения входных сигналов. Изменение значений на выходах RG происходит всегда на границе такта. Для корректной работы синхронного автомата изменения входных сигналов должны происходить в интервале  (рис.2) так, что бы время t=T- было бы достаточным для завершения переходных процессов. 2. ОСНОВНЫЕ СТРУКТУРНЫЕ СОСТАВЛЯЮЩИЕ СЦА 2.1. Комбинационная схема В соответствии с каноническими уравнениями можно детализировать схему СЦА на рис.1 и представить СЦА в виде схемы изображённой на рис.3, где одна КС представлена как декомпозиция двух КС – g и f. CL a g RG s' syn CL s b f C s Рис.3. Функции перехода, выхода и памяти в СЦА Одна из них «f» реализует функцию выхода, другая «g» вычисляет значение нового состояния. Памятью автомата является регистр RG, он запоминает значение состояния автомата, выполняя. тем самым, операцию сдвига (переноса) во времени. КС, сама по себе, является частным случаем автомата. Она представляет собой автомат без памяти или иначе автомат с одним состоянием. При реализации СЦА декомпозиция КС должна быть доведена до элементарных комбинационных схем, вычисляющих каждый отдельный бит состояния и выходного значения. 2.2. Память автомата Один двоичный разряд кода состояния запоминается триггером. Обычно это D-триггер, который может находиться в составе регистра. Напомним работу во времени синхронного D-триггера (рис.4). S a D syn C R T q syn a -q q Рис.4. D–триггер (обозначение и временные диаграммы) Триггер выдает в течение такта значение, которое он “увидел” на Dвходе во время появления рабочего фронта сигнала на C-входе. Таким образом, D-триггер “узнает” об изменении сигнала на входе D c запаздыванием, которое называется синхронизационным запаздыванием ( – на рис.4). 3. ОСНОВНЫЕ ТИПЫ СИНХРОННЫХ АВТОМАТОВ Синхронные автоматы могут быть классифицированы различным образом. Для начала определим разбиения на следующие классы синхронных автоматов: 1) полностью определенный и частично-определенный, 2) инициальный и неинициальный, а также выделим некоторый класс - 3) класс автоматов Мура. 3.1. СЦА полностью и частично определенные Синхронный автомат полностью определен, если функции f и g определены на всех возможных парах из элементов множества А входных символов и множества S состояний. Количество элементов этих множеств в СЦА определяется разрядностью кодирующих двоичных наборов. Реализованный СЦА всегда полностью определен. Если функции перехода и/или выхода определены не всюду, то синхронный автомат - частично-определенный. При этом если в каком-либо состоянии не определен переход для входного значения, то предполагается, что это значение не может появиться во входной последовательности. Если не определено выходное значение, то в этом случае оно безразлично. Реализованный автомат всегда определён полностью. 3.2. Инициальные автоматы Автомат называется инициальным, если в автомате выделено одно состояние, называемое начальным (например, q0). Начальное состояние может быть параметром автомата; в этом случае говорят, что определено множество начальных состояний. Если нет выделенного начального состояния, то автомат неинициальный. Для реализации инициального автомата схема СЦА должна быть сконструирована так, чтобы начальное состояние (запоминалось) в RG до начала работы автомата. фиксировалось 3.3. Автомат Мура Автомат Мура - синхронный автомат, у которого значения выхода определяются только состоянием автомата в тот же дискретный момент времени. При этом КС, вычисляющая выходное значение, не связана непосредственно с входными сигналами. CL a g RG s' syn s CL b f C s b = f(s), s:= g(s,a) Рис.5. Автомат Мура Поэтому момент изменения выходных сигналов зависит только от момента изменения сигнала синхронизации (рабочего фронта). О такой зависимости между входом и выходом принято говорить, что вход а и выход b “развязаны во времени”, или иначе - выход автомата “со сдвигом” зависит от входа. 3.4. Автомат Мили Автоматы, у которых вход и выход не развязаны во времени, т.е. хотя бы один выход зависит от текущего значения на входе, называют автоматами Мили. В автомате Мили могут одновременно существовать выходные переменные, которые зависят от входных переменных, как со сдвигом, так и без сдвига, как, например, в схеме автомата, приведенной на рис.6. c= fc(s), b= fb(s,a1), Рис.6. Автомат Мили s:= g(s,a1,a2) Переменная c определена только состоянием автомата, т.е. зависит «со сдвигом» от всех входных переменных. Переменная b зависит от переменной a1 и состояния автомата. 4. СПОСОБЫ ОПИСАНИЯ АВТОМАТОВ Функции f выхода и g переходов могут быть интерпретированы и заданы самым различным образом в зависимости от цели, для которой проектируется автомат. Например: 1) Функция переходов задаётся как вычисляемая функция. В этом случае СЦА называют СЦА операционного типа, например, канонический счётчик Q:=(Q+1)mod2n, где Q – код состояния; накапливающий сумматор S:=S+A+c, где с – входной перенос. 2) Состояние автомата интерпретируется только как идентификатор шага некоторого вычисления (алгоритма) – в этом случае СЦА будем называть СЦА управляющего типа. 3) Автомат – распознаватель отвечает на вопрос, принадлежит ли поданное на вход слово определённому множеству. 4) Автомат – преобразователь преобразует входные слова в выходные, например, в целях кодирования или декодирования информации. 4.1. Автоматная таблица. Если автомат не операционного типа, то функции f и g могут быть заданы в виде таблицы истинности в любой ее форме, но применительно к синхронным автоматам более других распространена форма двухвходовой таблицы, которая называется автоматной таблицей. Каждому состоянию автомата соответствует строка таблицы. Заголовками строк служат либо идентификаторы состояний, либо коды состояний. Каждому входному символу соответствует столбец с заголовком в виде символа или его кода. (Разумеется, можно использовать транспонированную таблицу со строками входными символами и столбцами - состояниями.) Каждая клетка таблицы с координатами [i,j] содержит, в общем случае, два значения: (sq/bp), где sq:=g(si, аj) – новое (следующее) состояние автомата, bp =f(si, аj) - выходное значение. Таблица автомата Мура, при такой структуре таблицы, будет содержать во всех клетках одной строки одно и тоже выходное значение. Поэтому изображение таблицы автомата Мура будет проще, если клетка содержит только одно значение - новое состояние, но есть столбец с выходными значениями для каждого состояния. Первая строка таблицы для инициальных автоматов, чаще всего, соответствует начальному состоянию автомата. Пример 4.1.-1. Инкрементор. Автомат - инкрементор с одноразрядным входом (a) и одноразрядным выходом (b). На вход поступает последовательно многоразрядное число в дополнительном коде, начиная с младших разрядов. На выходе синхронно появляется результат - число на единицу большее, чем исходное. Решение: Пусть автомат имеет два состояния p 1 и p0. p1 - соответствует значению переноса 1, это состояние является начальным; p0 - соответствует значению переноса 0. Тогда согласно правилам сложения одноразрядных двоичных кодов, получим таблицу 1. Таблица 2 получена из таблицы 1 присваиванием двоичных кодов состояниям. По таблице 2 могут быть получены таблицы истинности (например, в виде карты Карно) функций f и g - табл.3, табл.4. Таблица-1 вход состояние p1 p0 1 p0/1 p0/0 p1/1 p0/1 Таблица -3 f 1 1 b=s+a Таблца-2 1 1 1 1 0/1 0/0 1/0 0/1 Таблица-4 g 1 1 1 s’ = s  a Схема СЦА - инкрементора может быть такой, как на рис.7а. a) б) Рис.7. Инкрементор в дополнительном коде Для правильной интерпретации работы схемы необходимо условиться о правилах (протоколе) взаимодействия схемы с внешней средой. Например: 1) начальное входное значение и начальное состояние устанавливается при start=1; 2) выходные значения читаются при значениях start=0 и syn=0. Если считать, что функция суммирования одноразрядных двоичных чисел задана (р,s)=HS(x,y), то аналогичную схему можно получить, синтезируя СЦА как автомат операционного типа. В этом случае каноническое уравнение автомата конкретизируется как (b,s:)=HS(s,a) при s(0)=1. Соответствующая схема приведена на рис.7б. 4.2. Автоматный граф (граф переходов). При описании автоматов удобно отобразить математическую структуру абстрактного автомата на другую математическую структуру ориентированного графа. G = (S,D), где S - множество вершин графа, D - множество дуг графа - упорядоченных пар вершин. Структура графа помогает выделить два объекта математической структуры автомата: состояния − вершины графа и функцию переходов − дуги графа, остальные объекты автомата вводятся как пометки дуг или вершин. Дуги помечаются символами входного алфавита, а символами выходного алфавита помечаются дуги или вершины в зависимости от типа автомата G = ({si},{dj[ak/bh]}) для автомата Мили, G = ({si[bh]},{dj[ak]})для автомата Мура. Диаграммой будем называть какое-либо геометрическое изображение графа. Диаграмма автомата - инкрементора может иметь вид рис.8. Дуги смежные одной и той же паре вершин и одинаково направленные (параллельные дуги) могут быть объединены в одну дугу, помеченную соответствующим образом - рис.8б (а - имя входной переменной). a) б) Рис.8. Диаграмма автомата - инкрементора Рис.9. Автоматная диаграмма D-триггера Автоматный граф полностью определённого автомата должен удовлетворять условию однозначности, т.е. не должно существовать двух дуг, выходящих из одной и той же вершины, с одинаковыми входными пометками. Автоматный граф полностью определенного автомата удовлетворяет условию полноты, т.е. для всякой вершины s и для всякого входного символа q имеется дуга, помеченная символом q и выходящая из s. Примером диаграммы автомата Мура может служить автоматная диаграмма D-триггера (рис.9). Отличие этой диаграммы от предыдущей в том, что выходным значением помечены не дуги, а состояния. Блок-схема должна удовлетворять условию однозначности: если любой путь, соединяющий две операторные вершины, не содержит входных переменных, которые участвует в вычислении условия более одного раза. Блок-схема автомата D-триггера приведена на рис.10. 4.4. Блок-текст Блок-текст − это описание блок-схемы в виде последовательного текста. В блок-тексте используются блоки двух типов операторные и блоки переходов. Операторные блоки − в скобках вида {...}, блоки перехода − в скобках вида <<...>>. И те, и другие блоки могут снабжаться метками, стоящими перед блоком. Операторный блок соответствует операторной вершине блок-схемы. В блоках перехода используется оператор GO в одной из двух форм: GO m - безусловный переход, GO (P; m0,m1,m2,...) - условный переход, где, m0,m1,... - метки блоков, P - значение, интерпретируемое оператором GO как неотрицательное целое число, являющееся порядковым номером метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных переходов соответствуют условным вершинам блок-схемы. Например, см. рис.11. Рис.11. Блок-текст 5. АВТОНОМНЫЕ АВТОМАТЫ СЦА, у которого единственным изменяющимся входным сигналом является сигнал синхронизации, называется автономным автоматом. Рис.12. Диаграмма инициального автономного автомата Автомат, имеющий n-разрядную память, имеет 2n состояний. Соответственно полный граф переходов автомата имеет 2 n вершин. У автономного автомата из каждой вершины выходит ровно по одной дуге. Граф автомата может иметь более одного компонента связности. В каждом компоненте связности графа автономного автомата может быть только один цикл, к этому циклу могут быть подвешены деревья, ориентированные в его сторону. Граф инициального автомата имеет только один компонент связности с числом вершин N2n (рис.12). Число состояний (вершин) в цикле инициального автономного автомата называют модулем счета. Любой неавтономный автомат можно сделать автономным, если зафиксировать входной символ. При этом все переходы в новое состояние осуществляются при одном и том же значении входного символа. В инженерной практике автономные автоматы используются как счетчики и в качестве генераторов периодических последовательностей. 5.1. Параллельная композиция Параллельная или синхронная композиция автономных автоматов приведена на рис.13. Интересны счетные возможности такой композиции, т.е. число состояний в цикле (модуль счета). Этот модуль равен наименьшему общему кратному всех модулей автоматов, входящих в синхронную композицию. Модуль будет наибольшим, если модули автоматов взаимно простые числа – тогда он будет равен их произведению. T AA1 CL CL AA2 Рис.13. Параллельное включение АА T AA1 t AA2 Рис.14. Последовательное включение АА 5.2. Последовательная композиция Последовательная или асинхронная композиция синхронных автономных автоматов приведена на рис.14. Для переключения автомата АА2 используется изменение значения какого-либо одноразрядного выходного сигнала автомата АА1. Счетные возможности такой композиции максимальны, если сигнал t выбран так, что он изменяет свое значение за цикл автомата AA1 не более двух раз, т.е. переключающий фронт ровно один за цикл. Тогда модуль композиции равен произведению модулей автономных автоматов. 6.3. Эквивалентность автоматов Мура автоматам Мили 6.3.1. На практике бывает удобно перейти к эквивалентному автомату, имеющему, быть может, большее число состояний, чем исходный автомат, но зато обладающему некоторыми другими “полезными” качествами. Так обстоит дело при переходе от произвольно заданного автомата Мили к эквивалентному ему автомату Мура, который обладает “полезным” свойством “развязывать” вход и выход. В таких случаях вместо склеивания состояний применяется, в некотором смысле, обратная операция “расщепления состояний”. Автомат Мура, полученный как эквивалентный автомату Мили, выдает такие же выходные последовательности, но со сдвигом на такт. Преобразование автомата Мили в эквивалентный ему автомат Мура покажем на следующем примере. Пример 6.3.-1.   0,A 1,B 1,A 0,C 0,B 1,C A B C A0 A1 B0 B1 C0 C1 1 1 1  A0 A0 A1 A1 B0 B0  B1 B1 C0 C0 C1 C1 1 1 1 A A B B C C  A B A C B C  A B A C B C 6.3.2. При замене автомата Мура равносильным ему автоматом Мили, сопоставляем каждой дуге di[ak], направленной к вершине sz[bh] в автомате Мура, дугу di[ak/bh], направленную к вершине sz в автомате Мили. Затем минимизируем состояния автомата. 7. «ПРЯМОЕ» ПРОЕКТИРОВАНИЕ Эффективным методом решения любых задач является метод декомпозиции. Рассмотрим некоторые примеры проектирования автоматов, используя, по возможности, декомпозицию. Пример 1.-1. Синтезировать автомат с одноразрядным входом и одноразрядным выходом, на выходе которого фиксируется по модулю 2 количество единичных блоков с нечетным числом единиц. Рис.20. Временные диаграммы автомата На временной диаграмме (рис.20) приведены два возможных варианта выхода: out_v1 - c “привязкой” изменения к входному сигналу и out_v2 - с “привязкой” изменения к сигналу синхронизации. Решение 1. В этой задаче нужно считать по модулю 2 как количество блоков, так и количество единиц в блоке. Поэтому возможна следующая композиции автоматов - рис.21. in syn A1 A2 q in out_v1 A1 syn A2 q out_v2 Рис.21. Декомпозиция автомата Автомат A1 считает по модулю 2 количество единиц в блоке и сбрасывается в ноль, если нет единиц на входе. Автомат A2 − счетчик по модулю 2 с параметром. В первом варианте А2 синхронизируется отрицательным фронтом входного сигнала in, переключается при единице на q; во втором варианте А2 - синхронизируется отрицательным фронтом сигнала q, переключается при нулевом входном сигнале in. Временные диаграммы (рис.22), автоматные таблицы и схема (рис.23) иллюстрируют решение. В схеме использованы JK-триггеры для минимизации комбинационной схемы автомата. Рис.22. Временные диаграммы автоматов Автоматные таблицы и таблицы возбуждения триггеров A1 in 1 1 1 s in J 1 1 1 X X 1 X X 1 1 1 in s K q 1 1 1 1 s s A2_V1 q J=in 1 1 1 X X 1 X X 1 1 q s K=1 in 1 1 1 1 s s A2_V2 in 1 1 1 X X 1 X X 1 1 s J=q in s K=q J=in K=in Рис.23. Схемы автоматов Решение 2 - без использования декомпозиции. Пусть искомый автомат имеет две группы состояний: xP - состояния, в которых автомат находится, если в текущей входной последовательности есть нечетное количество блоков с нечетным числом единиц; xR - все тоже самое, но с четным количеством блоков. В каждую из групп входят состояния: Kx - закончился или не начался блок единиц; Lx - текущее количество единиц в блоке нечетно; Mx - текущее количество единиц в блоке четно; Чтобы получить временную диаграмму по варианту 1 (out_v1), надо синтезировать автомат Мили, а, если – по варианту 2 (out_v2), то надо синтезировать автомат Мура. ВАРИАНТ-1 ВАРИАНТ-2 Рис.24. Диаграммы переходов автоматов без декомпозиции Состояния (KP,MP) и (KR,MR) явно эквивалентны, поэтому в графах останется по четыре состояния. Если коды состояний для автомата Мура (вариант-2) выбрать так, чтобы начальное состояние (KR) имело код [00], а выходное значение совпадало со значением одного из разрядов кода, то способов кодирования состояний, приводящих к различным схемам, всего 2. код1 код2 KR 00 00 LR 10 10 KP 01 11 LP 11 01 После минимизации комбинационной части автомата получаем: при реализации памяти на D-триггерах − переменные di, а для JK-триггеров – переменные (Ji, Ki). s2,s1 00 01 11 10 00 01 00 01 1 10 11 01 00 s2,s1 00 01 11 10 a a код1 (d1=a  s2 s1 v 2  s1 v a  s1) (J1=K1=a  s2) (d2=a  s2) (J2= a, K2=1) код2 (d1=as2 v as1) (d2= a + s2) (J1=a  s2, K1=a s2) (J2=K2= a) 00 00 11 11 1 10 11 01 00 s2,s1 00 01 11 10 автомат Мили (ВАРИАНТ-1) код2 out_v1=d1=a  s2 v a  s1 a 1 1 1 1 1 Пример 1.-2. Синтезировать устройство, которое вычисляет максимальное из нескольких чисел. Каждое из чисел поступает по одноразрядной шине, начиная со старших разрядов. Одноименные разряды всех чисел поступают синхронно. На одноразрядном выходе синхронно появляется результат - значения разрядов максимального из чисел. Для каждого отдельного числа спроектируем локальный автомат со следующими состояниями: M - число максимальное - значение на выходе равно входному; N - число немаксимальное - на выходе автомата 0, т.е. наименьшее возможное значение. Теперь можно сравнить значения на выходе всех автоматов и выдать максимальное, т.е. выполнить дизъюнкцию, см. рис.25. Рис.25. Структура автомата поиска максимального Локальный автомат (Ai) переходит из состояния M в состояние N тогда, когда число перестает быть максимальным, т.е. когда значение входного разряда числа меньше значения на выходе дизъюнкции. Выход m, а значит и выход qi, должен зависеть без сдвига от переменной di. В то же время выход автомата qi должен зависеть со сдвигом от переменной m, поскольку это переменная обратной связи. Поэтому структура локального автомата должна быть такой, как на рис.26. Рис.26. Схема локального автомата Работа автомата определяется следующими таблицами: Автоматная таблица: Таблица f: Таблица g: d,m 00 01 11 10 M 0,M 0,N 1,M X,X N 0,N 0,N 0,N 0,N s d.. 1 0, 1, 1 0, 0, s d,m 00 01 11 10 ,0 ,1 ,0 ,X 1 ,1 ,1 ,1 ,1 s