Лекция 10 Конечные автоматы. Понятие о конечных автоматах. Способы задания. Автоматы Мили и Мура. Абстрактный и структурный автоматы. Понятие элементарного автомата. Общая структурная схема конечного автомата. Схемные реализации Термин «автомат», как правило, используется в двух аспектах. С одной стороны, автомат - это устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q1(t), q2(t), ..., qn(t)}, в которые он под действием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время - Термин «автомат», как правило, используется в двух аспектах. С одной стороны, автомат - это устройство, выполняющее некоторые функции без непосредственного участия человека. В этом смысле мы говорим, что ЭВМ – автомат, так как после загрузки программы и исходных данных ЭВМ решает заданную задачу без участия человека. С другой стороны, термин «автомат» как математическое понятие обозначает математическую модель реальных технических автоматов. В этом смысле автомат представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний Q = {q1(t), q2(t), ..., qn(t)}, в которые он под действием входных сигналов переходит скачкообразно, т. е. практически мгновенно, минуя промежуточное состояние. Конечно, это условие не выполняется в реальности, так как любой переходный процесс длится конечное время
- Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов – конечные множества. На практике часто используется понятие цифрового автомата, под которым понимают устройство, предназначенное для преобразования информации. С общей точки зрения, процесс получения информации есть ни что иное, как процесс снятия неопределенности в результате того, что из некоторой совокупности возможных в данной конкретной ситуации явлений выделяется явление, фактически имевшее место. Таким образом, в понятии информации существенно не само происшедшее явление, а лишь его отношение к совокупности явлений, которые могли произойти. Устройства, служащие для преобразования дискретной информации, называются дискретными автоматами.
- В современных дискретных автоматах принято обычно отождествлять буквы используемого стандартного алфавита с цифрами той или иной системы счисления. В состав цифровых автоматов обязательно входят запоминающие элементы (элементы памяти). Выходные сигналы в таких автоматах формируются в зависимости от входных сигналов и состояний, в которых находятся элементы памяти. Поэтому дискретные автоматы принято называть также цифровыми автоматами.
10.1 Понятие о конечных автоматах и способы их задания - Термин «конечный автомат» используется для обозначения одного класса цифровых устройств, находящих применение в автоматике, телемеханике, вычислительной технике. В отличие от комбинационных схем эти устройства содержат память.
- Выходные сигналы конечного автомата (КА) зависят от значений на входах не только в данный момент времени, но и от предыдущих значений входных сигналов.
- Необходимая информация о сигналах, поступивших на входы раньше, может быть учтена посредством введения промежуточных сигналов, которые связаны с внутренней структурой автомата и называются состояниями автомата.
- Используют два типа моделей КА – абстрактная и структурная.
- Изменения состояний цифрового автомата вызываются входными сигналами, которые возникают вне автомата и передаются в автомат по конечному числу входных каналов.
- В отношении входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных входных сигналов обязательно конечно, а, во-вторых, входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами.
- Отметим, что при таком допущении входной сигнал рассматривается как мгновенный, хотя в действительности он имеет конечную длительность. Особо следует подчеркнуть, что реальный физический входной сигнал, вызывающий изменение состояния автомата в момент времени t, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к текущему моменту времени t, а не к предыдущему (t –1). Результатом работы цифрового автомата является выдача выходных сигналов, передаваемых из автомата во внешние цепи по конечному числу выходных каналов.
- В отношении выходных сигналов вводятся допущения, аналогичные допущениям для входных сигналов. Во-первых, число различных выходных сигналов для любого цифрового автомата всегда конечно. Во-вторых, каждому отличному от нуля моменту автоматного времени относится соответствующий ему входной сигнал. Реальный физический выходной сигнал y(t), отнесенный к моменту времени t, появляется всегда после соответствующего этому же моменту времени входного сигнала x(t). Что же касается момента времени t перехода автомата из состояния q(t–1) в состояние q(t), то сигнал y(t) может фактически появится либо раньше, либо позже этого момента. В первом случае принимается, что выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t–1) автомата в предыдущий момент времени, во втором случае сигнал y(t) однозначно определяется парой (x(t), q(t)). Будем считать, что для любого момента времени всегда имеет место лишь одна из этих возможностей (одновременно для всех переходов).
Абстрактный автомат - Абстрактный автомат – это математическая модель, в которой абстрагируются от реальной физической природы сигналов и рассматривают их как буквы некоторого алфавита.
- Абстрактный автомат (АА) имеет один вход и один выход и работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... Эти моменты времени называются тактами. В момент t АА, находясь в состоянии q(t), способен воспринять на выходе в этот же момент букву выходного алфавита y(t) и перейти в следующее состояние q(t+1).
- Если на вход АА подавать буква за буквой некоторую последовательность букв входного алфавита х1, х2, х3... – входное слово, то на выходе АА будут последовательно появляться буквы выходного алфавита у1, у2, у3…– выходное слово.
- АА может быть задан: 1) аналитическим, 2)табличным или матричным и 3)графическим способами.
Аналитический способ задания АА - Задается множеством из пяти элементов:
- A = {X, Y, Q, Гq, q1},
- где Х = {х1, х2,..., хn} – множество входных сигналов (входной алфавит);
- Y={y1, y2,...,ym} – множество выходных сигналов (выходной алфавит);
- Q={q1, q2,…,qr} – множество возможных внутренних состояний (алфавит состояний);
- Гq = { Гq1, Гq2,..., Гqr} – отображение множества Q в себя, которое любому q∈Qи каждой входной букве x∈X сопоставляет состояние qk∈Q, определяющее функцию переходов ϕ(q,x) и выходную букву y∈Y, определяющую функцию выходов ψ(q,x); q1∈Q– начальное состояние автомата.
Задание АА - Пусть Х = {х1,х2,х3}, Y={y1,у2,y3,y4,y5,у6},
- Q = {q1,q2,q3,q4,q5};
- Гq1 = {q2(x1/y1), q4(x2/y3), q5(x3/y4)},
- Гq2 = {q3(x1/y6), q1(x2/y1)},
- Гq3 = {q1(x2/y5), q4(x3/y3)},
- Гq4 = {q4(x1/y4), q5(x2/y2)},
- Гq5 = {q1(x1/y5), q2(x3/y1)}.
- Запись для отображения Гq1 = {q2(x1/y1), q4(x2/y3), q5(x3/y4)} читается следующим образом:
- q2(x1/y1): АА переходит из состояния q1 в состояние q2, если на входе х1, при этом на выходе появляется y1;
- q4(x2/y3): АА переходит из состояния q1 в q4, если на входе x2, при этом на выходе появляется у3;
- q5(x3/y4): АА переходит из состояния q1 в q5, если на входе х3, при этом на выходе появляется у4.
- Аналогичный смысл имеют отображения Гq2, Гq3, Гq4 и Гq5.
Законы функционирования автомата Мили и Мура - Автомат называется конечным, если конечны множества X, Y, Q.
- Функция переходов ϕ(q,x) и функция выходов ψ(q,x) определяют закон функционирования конечного автомата в дискретные моменты времени. На практике наибольшее распространение получили автоматы Мили и Мура.
- Закон функционирования автомата Мили задается уравнениями
- которые показывают, что внутреннее состояние q(t+l) и выходной сигнал y(t) однозначно определяются состоянием q(t) и входным сигналом x(t).
- В автомате Мура выходные сигналы зависят только от состояний автомата в рассматриваемый момент времени и не зависят от значений входных сигналов. Закон функционирования автомата Мура описывается следующими уравнениями:
- Два автомата называются эквивалентными, если любую одну и ту же входную последовательность они перерабатывают в одну и ту же выходную последовательность, но могут иметь различные состояния.
- Для каждого автомата Мили существует эквивалентный ему автомат Мура, т. е. модели Мили и Мура обладают равными функциональными возможностями.
- Наиболее общей является модель Мили, ее и будем рассматривать.
- Если функции ϕ и ψ определены на всех значениях q(t) и x(t), то такие автоматы называются полными или полностью определенными.
- Если ϕ и ψ определены не на всех значениях q(t) и x(t), то такие автоматы называются частичными.
Табличный способ задания АА - Задание с помощью обобщенной таблицы переходов и выходов. Строки таблицы соответствуют возможным значениям входного сигнала, а столбцы – внутренним состояниям автомата. На пересечении строки и столбца указывается очередное состояние автомата и через косую черту соответствующее значение выходного сигнала.
Пример табличного задания АА Матрица соединений автомата - Иногда используют две отдельные таблицы: таблицу переходов и таблицу выходов. АА можно задать также матрицей соединений автомата. Строки и столбцы этой матрицы соответствуют различным состояниям автомата. На пересечении qk–строки и qℓ –столбца записывается буква входного алфавита xi∈X, вызывающая переход автомата из состояния qk в qℓ, а через косую черту – буква выходного алфавита yj∈Y, которая появляется на выходе автомата. Если ни одна из букв входного алфавита не переводит автомат из состояния qk в qℓ, то на соответствующем пересечении ставится нуль.
Графический способ задания АА - АА изображается в виде ориентированного графа. Вершины графа отождествляются с внутренними состояниями автомата. Каждая дуга отличается входным сигналом, вызвавшем в автомате соответствующий переход, и выходным сигналом, который возникает при этом переходе.
Структурный автомат - В отличие от АА, имеющего один вход и один выход, структурный автомат (СА) имеет р входов (u1, u2, ..., uР) и ℓ выходов (v1,v2,...,vℓ), на каждом из которых сигнал может принимать два значения – 0 или 1.
- Букве хi входного алфавита АА соответствует вектор, компонентами которого являются нули и единицы – сигналы на входах СА. Для кодирования входных сигналов АА различными векторами должно быть выполнено условие p≥log2n , т. е. число входов р выбирается равным ближайшему целому числу, не меньшему, чем log2n(n-количество входных сигналов). Точно так же букве уi выходного алфавита АА соответствует вектор из 0 и 1, число компонентов е которого определяется выражением , е ≥ log2m (m-количество выходных сигналов).
10.2. Синтез конечных автоматов - Используемый на практике метод синтеза КА предполагает, что общая структура автомата имеет вид, представленный на рис.:
- Первое комбинационное устройство (КУ1) вырабатывает входные сигналы (сигналы возбуждения) для элементов памяти (ЭП).
- Второе комбинационное устройство (КУ2) вырабатывает выходные сигналы автомата. Синтез КА сводится к определению количества элементов памяти и выбору их типов, а также к построению схем КУ1 и КУ2 в выбранном базисе.
10.2.1. Элементарные автоматы - В качестве ЭП (элементов памяти), обеспечивающих временную задержку сигналов на один такт, используются серийно выпускаемые триггеры.
- Триггер – это двоичный запоминающий элемент, имеющий один или несколько входов и два выхода. Под действием входных сигналов триггер может переключаться в любое из двух устойчивых состояний (0 или 1) и сохранять это состояние в течение заданного времени.
- Так как триггеры имеют только два устойчивых состояния, их называют элементарными автоматами. Выходные сигналы триггера совпадают с его состоянием.
- Описать работу триггера можно таблицей переходов, в которой указываются значения 0 или 1 входных сигналов, вызывающих один из четырех возможных типов переходов:
- 0→0; 0→1; 1→0; 1→1.
Типы триггеров. D-триггер - Название D-триггера произошло от английского слова Delay (задержка), так как его следующее состояние равно сигналу на входе D, задержанному на один такт.
- Как уже отмечалось, выходные сигналы триггеров совпадают с состоянием, в которое они переходят, поэтому для описания элементарных автоматов достаточно задать таблицу переходов.
Пример D-триггера - Триггер имеет один вход D и два выхода, обозначенных w и
Таблица определяет переходы D-триггера w(t) →w(t+1):
|
Граф D-триггера приведен на рис. Вершины графа соответствуют состояниям 0 и 1, а дуги отмечены сигналами, вызывающими соответствующие переходы.
| | | |
Функцию переходов D-триггера можно также представить в аналитической форме
| | Т-триггер или триггер со счетным входом
Функциональная схема Т-триггера
|
Таблица переходов:
| | | |
При Т=0 триггер находится в состоянии хранения информации, сигнал Т=1 вызывает переключение триггера в противоположное состояние.
| |
Граф Т-триггера
|
Функция переходов Т-триггера
| | | | RS-триггер
Функциональная схема RS-триггера
|
Таблица переходов:
| | | |
Схема имеет два входа S и R и два выхода, обозначенных w и . Сигнал S (от англ. set – установка) переключает триггер в единичное состояние, а сигнал R (англ. reset – переустановка) вызывает переключение триггера в нулевое состояние. Вход S называется единичным установочным, а вход R – нулевым установочным. Символ * в табл. означает, что подача сигналов ноль или единица на соответствующие входы S и R не влияет на данный переход триггера.
| |
Граф RS-триггера
|
Функция переходов RS-триггера
| | | | J-K триггер
Функциональная схема J-K-триггера
|
Таблица переходов (10.5):
| | | |
Вход J называется единичным установочным входом, а вход К – нулевым установочным. В J-K триггере допускается одновременная подача входных сигналов J = l и К = 1. Таблица переходов J-K триггера задана табл. 10.5. Cимвол * означает, что значение сигнала 0 или 1 на отмеченном входе не влияет на данный переход триггера.
| |
Граф J-K-триггера
|
Функция переходов J-K-триггера
| | | | 10.2.2. Переход от абстрактного автомата к структурной схеме. - Структурный синтез автоматов заключается в составлении системы логических функций, на основании которой строятся комбинационные устройства, формирующие выходные сигналы и сигналы возбуждения элементов памяти (триггеров).
- Выделяют пять основных этапов структурного синтеза.
- 1. Кодирование входного и выходного алфавитов АА, кодирование состояний АА. Чтобы закодировать входные сигналы АА, нужно каждой букве входного алфавита xi, i=1,…, n поставить в соответствие совокупность значений двоичных сигналов u1,u2,…, uP на входах СА. При этом количество р физических входов СА определяют из условия выбирая ближайшее целое число p≥ log2n.
- При кодировании выходных сигналов АА каждой букве yj, j=1,…,m выходного алфавита ставится в соответствие совокупность значений двоичных сигналов v1,v2,...,ve на выходах СА. Количество е физических выходов СА определяют из условия e≥ log2m, выбирая ближайшее целое число.
- Аналогично кодированию входных и выходных сигналов каждой букве qk (k=1,…, r) алфавита состояний абстрактного автомата ставится в соответствие совокупность значений двоичных сигналов w1,w2,...,wZ состояний (выходов) элементов памяти. Количество элементов памяти определяют из условия z≥ log2r, выбирая ближайшее целое число
- 2. Выбор типа элементарных автоматов (ЭА) (элементов памяти). При выборе элементов памяти ориентируются на имеющуюся элементную базу. Для выбранного типа триггеров составляют таблицу переходов, в которой для каждого возможного типа переходов указана комбинация сигналов на входах (сигналов возбуждения триггеров).
- 3. Составление обобщенной таблицы переходов и выходов для закодированных переменных.
- 4. Определение функций возбуждения элементарных автоматов и выходных функций СА. Минимизация этих функций.
- 5. Составление структурной схемы синтезируемого автомата, т. е. составление комбинационной схемы, реализующей функции возбуждения ЭА и выходные функции СА.
Пример синтеза структурной схемы - В качестве элементов памяти использовать D-триггеры, в качестве элементной базы использовать логические элементы И, ИЛИ, НЕ.
- Таблица 10.6
- В соответствии с табл. 10.6 количество букв входного алфавита АА п=3, количество букв выходного алфавита m = 6, количество состояний r = 5.
- Определим количество входов СА: p ≥log23, принимаем р = 2. Количество выходов СА: e ≥log26, принимаем е = 3. Количество элементов памяти, т. е. необходимое количество D-триггеров: z ≥log25, принимаем z =3.
Принцип кодирования переменных - Принцип кодирования переменных будет определять сложность схем комбинационных устройств, формирующих сигналы возбуждения Di (i = 1,2,3) триггеров и выходные сигналы Vj (j = 1, 2, 3).
- Минимальное число слагаемых в ДСНФ для Di и Vj получается при следующем алгоритме кодирования:
- 1) упорядочить кодируемые переменные в порядке уменьшения числа их появлений в таблице переходов-выходов;
- 2) первая из них, т. е. наиболее часто встречающаяся, кодируется нулевым кодом, затем используются коды, содержащие по одной единице, затем по две и т. д., до тех пор, пока все состояния не будут закодированы.
- Закодируем переменные xj, vj, qk.
Кодировка переменных xj - Переменные x1, х2, x3 встречаются в табл. 10.6 по одному разу, результаты кодирования занесены в табл. 10.7.
- Таблица 10.7
Кодировка переменных yj - В табл.10.6. переменная y1 встречается чаще всего (три раза), кодируем ее нулевым кодом; переменные у3, y4, y5 встречаются по два раза, используем для них коды содержащие по одной единице; переменные у2, y6 встречаются в табл. 10.6 по 1 разу, используем для них коды содержащие по две единицы.
- Результаты кодирования занесены в табл. 10.8.
- Таблица 10.8
Кодировка переменных qk (k=1,…,5) - Учтено, что q1 и q4 встречаются в табл. 10.6 по три раза, q2 и q5 по 2 раза, q3 встречается один раз. Результаты кодирования занесены в табл. 10.9.
Обобщенная таблица переходов и выходов СА - На основании результатов кодирования строим обобщенную таблицу переходов и выходов СА (табл. 10.10), заменяя состояния, входные и выходные переменные их кодами. В клетках таблицы записаны состояния
- w1(t + 1)w2(t + 1)w3(t + 1) и
- через черту выходы v1v2v3 структурного автомата, которые возникнут при появлении на входах комбинаций u1u2 и исходном состоянии триггеров w1(t)w2(t)w3(t).
Таблица 10.10 - Таблица 10.10
- Используя таблицу переходов D-триггера (табл. 10.2) и данные табл. 10.10, составим обобщенную таблицу функционирования СА (табл. 10.11). Функции возбуждения трех триггеров обозначены через D1, D2 и D3 соответственно.
- Dk=1, если k-й триггер на данном переходе wk(t) → wk(t+1) переключается из состояния 0 в 1 или наоборот.
- Dk = 0, если k-й триггер на рассматриваемом переходе wk(t) → wk(t+1) не переключается.
Таблица 10.11 СДНФ выходных функций V1, V2 и V3 и функций возбуждения триггеров D1, D2 и D3, зависящих от набора переменных u1, u2, w1(t), w2(t), w3(t). - В результате получим систему логических функций для построения комбинационной части автомата:
- В записанной системе некоторые конъюнкции встречаются несколько раз. Каждую конъюнкцию обозначим определенным числом, в результате система логических функций примет вид:
- Осуществить минимизацию функций Vi Dj.
Карта Карно для Vi - При кодировании букв входного алфавита была не задействована комбинация 11, поэтому вторая строка карты заполнена звездочками.
- При кодировании состояний автоматов не задействованы кодовые комбинации 110, 101, 111, которые по обозначениям в карте Карно соответствуют первым трем столбцам. Эти столбцы также заполнены звездочками, что означает независимость возникновения таких сигналов при работе автомата. В карте Карно для всех описываемых функций эти звездочки будут присутствовать.
- Остальные клетки карт заполняются в соответствии с табл. 10.11. Звездочки, соответствующие строкам этой таблице, имеют увеличенный размер, чтобы отличать их от предыдущих. Единицы и нули рассматриваются обычным способом.
Карта Карно для V1 - При минимизации V1 сформированы две группы.
- Первая из 8 клеток описывается конъюнкцией двух переменных (произведение букв, которые являются общими для всех клеток карт, объединенных в группу).
- Вторая из 4 клеток описывается конъюнкцией трех переменных , тогда
Карта Карно для функции V2 Карта Карно для функции V3 Карта Карно для функции D1 - В результате минимизации получено следующее выражение
Карта Карно для функции D2 - В результате минимизации получено следующее выражение:
Карта Карно для функции D3 - В результате минимизации получено следующее выражение:
Таблицы функционирования шифратора и дешифратора - Шифратор и дешифратор являются комбинационными схемами и реализуются в том же базисе, который задан для автомата.
- Шифратор должен обеспечить переход от букв входного алфавита к соответствующим кодам.
- Таблица 10.12 –результаты кодирования
- Таблица 10.12 позволяет записать U1 и U2 как логические функции трех переменных:
- Дешифратор должен обеспечить переход от кодов выходного алфавита к самим буквам.
- Табл. 10.13 является истинности дешифратора с тремя входами и шестью выходами.
- Каждому предусмотренному набору входных сигналов соответствует сигнал на одном из выходов. Входные сигналы представлены как функции переменных V1, V2 и V3.
Общая функциональная схема автомата |
Скачать 1.47 Mb.