Antik (1082243), страница 2
Текст из файла (страница 2)
Синхронный автомат (схема структурная)1.2. Абстрактный конечный автоматВ качестве основной математической модели СЦА используется абстрактный конечный автомат.Абстрактный конечный автомат это - математическая структура с тремя основными множествами А, B, S.А - называется множеством входных символов;B - называется множеством выходных символов;S - называется множеством (символов) состояний.Абстрактный конечный автомат функционирует в автоматномвремени t=0,1,2,..., определяемом как упорядоченное множествоцелых чисел.
Это означает, что автоматное время дискретно, исущественным является лишь номер момента времени; упорядоченность множества означает, что автоматное время имеет “направление”.Если обозначить через а(t), b(t), s(t) переменные со значениями в соответствующих множествах в момент t, то работа абстрактного конечного автомата описывается уравнениями, которые называются каноническимиs(t+1) = G(s(t),a(t))b(t)= f(s(t),a(t))7G - называется оператором перехода. Оператор перехода G,кроме вычисления значения, выполняет также сдвиг во времениэтого значения.f - называется функцией выхода;Принята также другая форма записи канонических уравнений:s := g(s,а)b = f(s,а)Знак двоеточие (:) означает операцию сдвига значения наединицу времени или иначе – операцию запоминания; g – функцию перехода.
Для фиксированного момента времени t аргументвремя в записи уравнений можно опустить, а так же идентифицировать конкретные значения переменных, например с помощьюиндексов:sj:= g(si, аp)bk= f(si,аp)Если по каким-либо соображениям преобразование, выполняемое комбинационной схемой, удобно записать в виде однойфункции, то возможны следующие формы записи каноническихуравнений:(s:,b) = h(s,а),Вычисления, выполняемые автоматом, можно рассматривать как процесс, т.е. строгую последовательность действий (шагов) преобразования символов, поступающих на а вход автоматав символы, появляющиеся на его b выходе.a(1),a(2),a(3),...,a(t),...b(1),b(2),b(3),...,b(t),...Каждый очередной выходной символ однозначно определяется последовательностью ранее поступивших входных символов, т.е. вычисление имеет свою “историю”.
Эта история сохраняется в автомате в виде переменной – состояние. Состояние автомата - это та минимальная информация, которая необходимадля предсказания дальнейшего поведения автомата. Поведениеавтомата трактуется как переходы из одного состояния в другоесостояние в определенные моменты автоматного времени с одновременным вычислением выходного значения.81.3. Соглашения …Для того чтобы абстрактный конечный автомат адекватномоделировал СЦА, необходимо выполнение некоторых соглашений.Входные и выходные сигналы СЦА, в общем случае, являются двоичными многоразрядными наборами, которые кодируютсимволы соответствующих множеств.Регистр в СЦА запоминает код состояния.
Состояния кодируются двоичными наборами. Количество разрядов памяти, азначит и кода состояния, называется мерностью автомата.КС в свою очередь реализуют функции переходов и выхода.Ход времени в СЦА инициируется изменением значенияединственного сигнала - сигнала синхронизации syn. На какомлибо из фронтов этого сигнала изменяется содержимое RG, азначит и состояние автомата (в схемах на рис.1 RG переключается по положительному (нарастающему) фронту сигнала syn). Переключающие фронты сигнала syn будем называть рабочимифронтами. Интервал времени между соседними рабочими фронтами называется тактовым интервалом или просто тактом (Т).TtРис.2. Структура тактаДля абстрактного автомата не имеет смысла понятие такта,как некоторого интервала “непрерывного” времени.
(Применительно к абстрактному автомату можно понимать термин такткак изменение дискретного времени на одну единицу). Для реального синхронного цифрового автомата величина этого интервала один из важнейших технических параметров, определяющихбыстродействие схемы. Величина этого интервала должна бытьдостаточной для того, чтобы закончились переходные процессы вКС, и установившиеся значения состояния могли быть записаныв RG. Переходные процессы начинаются из-за изменения либосостояния RG, либо изменения входных сигналов.
Изменениезначений на выходах RG происходит всегда на границе такта.9Для корректной работы синхронного автомата изменения входных сигналов должны происходить в интервале τ (рис.2) так, чтобы время t=T-τ , было бы достаточным для завершения переходных процессов.2.Основные структурные составляющие СЦА2.1. Комбинационная схемаВ соответствии с каноническими уравнениями можно детализировать схему СЦА на рис.1.1.-1 и представить СЦА в видесхемы на рис.2.1.-1, где одна КС представлена как декомпозициядвух КС – g и f.gРис.3.
Функции перехода, выхода и памяти в СЦАОдна из них - f реализует функцию выхода, другая - g вычисляет значение нового состояния, RG является памятью, онзапоминает значение состояния, выполняя тем самым операциюсдвига (переноса) во времени.КС, сама по себе, является частным случаем автомата - автомата без памяти или иначе автомата с одним состоянием.При реализации СЦА декомпозиция КС должна быть доведена до комбинационных схем, вычисляющих каждый отдельныйбит состояния и выходного значения.2.2. Память автоматаОдин двоичный разряд кода состояния запоминается триггером, обычно это – D-триггер, который может находиться в составе регистра.Напомним поведение во времени D-триггера с динамиче-10ской синхронизацией (рис.4).Рис.4. D–триггер (обозначение и временные диаграммы)Триггер выдает в течение такта значение, которое он “увидел” на D-входе во время появления рабочего фронта сигнала наC-входе.
Таким образом, D-триггер узнает об изменении сигналана входе D c задержкой, которая называется синхронизационнойзадержкой (τ – на рис.4).На изображении триггера (рис.4) не показаны входы асинхронной установки, обычно необходимые и присутствующие вреальных изделиях.Если в качестве элементов памяти используются JKтриггеры, то для любой i-координаты кода состояния функции,вычисляющие значения на входах триггера Ji и Ki , не зависят отзначения на выходе этого же триггера.
(При доказательстве использовать зависимость q := q ⋅ J ∨ q ⋅ K ).3. Основные типы синхронных автоматовСинхронные автоматы могут быть классифицированы различным образом. Для начала определим разбиения на следующиеклассы синхронных автоматов:1) полностью определенный и частично-определенный, 2) инициальный и неинициальный, а также выделим некоторый класс - 3)класс автоматов Мура.3.1. СЦА полностью и частично определенныеСинхронный автомат полностью определен, если функции fи g определены на всех возможных парах из элементов множества А входных символов и множества S состояний.
Количествоэлементов этих множеств в СЦА определяется разрядностью кодирующих двоичных наборов. Реализованный СЦА всегда полностью определен.11Если функции перехода и выхода определены не всюду, тосинхронный автомат - частично-определенный. При этом если вкаком-либо состоянии не определен переход для входного значения, то предполагается, что это значение не может появиться вовходной последовательности. Если не определено выходное значение, то в этом случае оно безразлично.3.2. Инициальные автоматыАвтомат называется инициальным, если в автомате выделеноодно состояние, называемое начальным (например, s0).
Начальноесостояние может быть параметром автомата; в этом случае говорят, что определено множество начальных состояний. Если нетвыделенного начального состояния, то автомат неинициальный.Для реализации инициального автомата схема СЦА должнабыть сконструирована так, чтобы начальное состояние фиксировалось (запоминалось) в RG до начала работы автомата.3.3.
Автомат МураАвтомат Мура - синхронный автомат, у которого значениявыхода определяются только состоянием автомата в тот же дискретный момент времени. При этом КС, вычисляющая выходноезначение, не связана непосредственно с входными сигналами.b = f(s),s:= g(s,a)Рис.5. Автомат МураПоэтому момент изменения выходных сигналов зависиттолько от момента изменения сигнала синхронизации (рабочегофронта). О такой зависимости между входом и выходом принятоговорить, что вход а и выход b “развязаны во времени”, или иначе - выход автомата “со сдвигом” зависит от входа.3.4. Автомат МилиАвтоматы, у которых вход и выход не развязаны во време-12ни, т.е.
хотя бы один выход зависит от текущего значения на входе, называют автоматами Мили.В автомате Мили могут одновременно существовать выходные переменные, которые зависят от входных переменных, как сосдвигом, так и без сдвига, как, например, в схеме автомата, приведенной на рис.6.c= fc(s),b= fb(s,a1),Рис.6. Автомат Милиs:= g(s,a1,a2)Переменная c зависит только от состояния автомата, т.е. сосдвигом от всех входных переменных. Переменная b зависит отпеременной a1 и состояния.4.Способы описания автоматовФункции f-выхода и g-переходов могут быть интерпретированы и заданы самым различным образом. Возможна следующаядостаточно условная классификация способов задания функциипереходов:1) функция переходов задана как вычисляемая функция, в этомслучае СЦА будем называть СЦА операционного типа, например q:=(q+1)modN, где q – код состояния;2) состояние автомата интерпретируется только как идентификатор шага некоторого вычисления (алгоритма) – в этом случаеСЦА будем называть СЦА управляющего типа.Такая классификация условна, хотя бы потому, что в зависимости от целесообразной интерпретации один и тот же автоматможет быть отнесен к любому из этих типов.4.1.Автоматная таблица.Функции f и g, также как и КС, могут быть заданы в виде13таблицы истинности в любой ее форме, но применительно к синхронным автоматам более других распространена форма двухвходовой таблицы, которая называется автоматной таблицей.Каждому состоянию автомата соответствует строка таблицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
