Конечные автоматы

В большинстве случаев работа устройства в момент t_i определяется не только входным словом, подаваемым в момент времениt_i, но зависит также и от входных слов, поступивших в предыдущие моменты времени. В этом случае имеют дело с автоматом с памятью, который часто называют простоконечным автоматом. Конечные автоматы изучаются в теории автоматов разделе кибернетики.

Устройства, которые служат для преобразования дискретной информации, называются дискретными автоматами. Дискретную информацию задают алфавитом,буквы которого отождествляют с цифрами. Поэтому дискретные автоматы принято также называтьцифровыми. Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного (для реальных автоматов всегда конечного) множества внутренних состояний и свойства скачкообразного перехода автомата из одного состояния в другое. Скачкообразность перехода позволяет трактовать этот переход как мгновенный без промежуточных состояний. При этом переходные процессы не принимаются во внимание.

Считается также, что переход из одного состояния в другое оказывается возможным не ранее, чем через промежуток времени >0. Это допущение позволяет рассматривать функционирование автомата в дискретном времени.

В синхронных автоматах моменты времени, в которые оказывается возможным изменение состояния автомата, определяются специальным устройством - генератором синхроимпульсов. В асинхронных автоматах моменты переходов из одного состояния в другое заранее не определены и совершаются через неравные промежутки времени. Теория асинхронных автоматов из-за этого отличается от теории синхронных автоматов.

Но можно свести ее в ряде случаев к теории синхронных автоматов, вводя понятие абстрактного автоматного времени: t=0, 1, 2,...n.

Общая теория автоматов делится на абстрактную и структурную теорию автоматов. В автомате имеются алфавиты: входной - X, выходной - У и состояний - А. Число входных сигналов конечно, и они рассматриваются как причина перехода из одного состояния в другое :a(t-1)a(t), гдеаА. Число выходных сигналов конечно и каждому отличному от О моменту автоматного времени соответствует выходной сигналy(t), который может появиться в моментt, но обязательно после входного сигналаx(t), соответствующего этому же моменту времени(уУ ихХ). У(t) может появиться в момент перехода из состояния a(t-1) в a(t) или после перехода. В первом случаеy(t) однозначно определяется паройx(t) и a(t-1), во втором случае - паройx(t) иa(t). Поэтому различаютавтоматы I рода (автоматы Мили) и II рода (автоматы Мура).

Абстрактный автомат и способы его задания. Абстрактный автомат задается как совокупность шестерки объектов: конечного множества X входных сигналов (входной алфавит); конечного множества У выходных сигналов (выходной алфавит); множества А, называемогомножеством состояний автомата; из множества А, называемого

начальным состоянием автомата и функций(а, х) и (а,х), задающих однозначное отображение множества пар а,х (аА иxX) в множества А и У. Функция(а, х) называетсяфункцией переходов автомата, а функция(а,х) - функцией выходов, либосдвинутой функцией выходов. Если автомат задан функцией выходов, то это автомат I рода (Мили), сдвинутой функцией выходов - II рода (Мура).

Для автомата Мили: a(t)=(a(t-1)),х(t); У(1)=(а(t-1)),х(t); (t= ).

Для автомата Мура: a(t)=(a(t-1)),х(t); У(1)=(а(t)),х(t)= (а(t)); (t= ).

Существует несколько способов задания автоматов. Наиболее распространенными являются табличный и графический. При табличном способе задания автоматов описание работы автомата задается таблицей переходов и выходов. Таблицей3.4задана функция переходова=(а, х), а таблицей3.5задана функция выходовy=(а,х) автомата Мили.

Частичным автоматом называется автомат, у которого функциии определены не для всех пар (а,, xj). На месте неопределенных состояний и выходных сигналов в таблицах переходов и выходов ставятся прочерки. Для задания автоматов Мура удобно пользоваться отмеченной таблицей переходов, в которой каждому столбцу помимо состояния приписывается еще и выходной сигнал, соответствующий этому состоянию (таблица3.6) .

Таблица 3.6

xi/ai	a1	a2	a3	a4
x1	y1	y2	y3	y1
x2	y2	y3	y1	y2
x3	y1	y2	y3	y2

При графическом способе задания автоматов описание работы автомата задается в виде ориентированного связ­ного графа, вершины которого соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины а_iи а_sграфа автоматасвязаны между собой дугой, направленной отa_i кa_s, если в автомате имеется переход отa_i к а_s, т.е.а_s=(а_i, x_j) при некоторомx_jX. Дуге(a_i, а_s) графа автомата Мили приписывается входной сигналx_j и выходнойy_g=(a_i, x_j), если он определен, в противном случае ставится прочерк (рис. 2.6). Граф автомата Мура отличается от графа автомата Мили тем, что выходной сигнал приписан вершине графа (Рис.3.2).

2.3.2. Структурный автомат и его синтез. В структурном автомате учитывается структура входных и выходных сигналов, а также самого устройства, т.е. в структурномавтомате осуществляется дальнейшая детализация абстрактного автомата. В структурном автомате вводится понятие множества входных и множества выходных узлов.

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

Рис. 3.2. Графическое изображение автомата

Наиболее распространенным структурным алфавитом является в настоящее время двоичный алфавит. Для абстрактного автомата задается входной алфавит Х={х₁, х₂, ...х_F}, выходнойУ={у₁, у₂,...y_G} и алфавит состоянийA={a₁, а₂, ...а_M}. Для перехода от абстрактного автомата к структурному необходимо выполнить переход от абстрактного алфавита к структурному. Каждый входной сигналх_f кодируется вектором(е_f1,е_fl,...е_fL), гдее_fl{0,1}, L]log₂F[. Каждый выходной сигналy_g кодируется вектором(e_g1...e_gm...e_gM), где e_gm{0,1}, N]log₂G[. Каждое состояниеa_m, кодируется вектором(e_m1...e_m2...e_mr...e_mR), где е_mr{0,1}, R]lоg₂М[.

Рис. 3.3. Структурный автомат Рис. 3.4. Структурный синтез автомата

Структурный автомат представлен на рис. 3.3, гдеZ_l - обозначение 1-го входного узла, аW_n - обозначениеп-го выходного узла структурного автомата.

Наиболее удобно изображать автомат на этапе структурного синтеза в виде двух частей:памяти и комбинационной схемы(рис.3.4). ЗдесьТ₁...Т_R - элементарные автоматы памяти, которые, как правило, находятся в состоянии "0" или "1", v - векторный сигнал обратной связи:U_r - функциявозбуждения памяти автомата:

Ur=Ur(v₁, v₂...v_R, z₁, z₂,... z_l) для автомата Мили(Мура);

Таблица 3.7

W_n=W_n(v₁, v₂...v_R, z₁,... z_l) для автомата Мили;

W_n=W_n(v₁, v₂...v_R) для автомата Мура.

ai	a1	a2	a3
q1/b1	b1	b2	b3
q1	b1	b1	b3
q2	b1	b1	b3
q3	b3	b3	b1

Канонический метод структурного синтеза автоматов. Автомат Мура обладает полнотой, если он обладает полнотой переходов и выходов. Примером такого автоматаявляется автомат, заданный таблицей 2.12.

Полнота переходов автомата Мура означает, что для любой пары состояний(b_i-b_j) найдется входной сигнал, который переведет автомат изb_i иb_j, т.е. в каждом столбце должны встречаться все состояния. Полнота выходов автоматов Мура означает, что каждое состояние отмечено своим, отличным от других, выходным сигналом.

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

Пример 3.3. Задан абстрактный автомат Мили (таблицы3.8и3.9).

Необходимо синтезировать структурный автомат.

Решение. Для этого задаются :

- функционально-полной системой элементов (например И, ИЛИ, НЕ, реализующихфункции соответственно конъюнкцию, дизъюнкцию, отрицание).

- абстрактным автоматом Мура, обладающим полнотой (табл. 3.10), где алфавит выходных сигналовтождественен алфавиту состояний. Осуществляют переход от абстрактного автомата Мура к структурному, выполняя кодирование (табл.3.11-3.12). Тогда в табл.3.13представлен структурный автомат Мура.

Формируют функцию автомата Мура. Функция входа определяет, какой входной сигнал должен быть подан на автомат, чтобы перевести его из состояния b₁в состояние b_j(таблица3.15,3.16).

Выполняется кодирование входных (x_j), выходных (y_g) сигналов и состояний (a_m) заданного абстрактного автомата Мили (табл.3.16-3.18).

Для синтеза комбинационной схемы автомата необходимо составить систему уравнений:

W₁=W₁(v₁, v₂, z₁, z₂);

W₂=W₃(v₁, v₂, z₁, z₂);

W₃=W₃(v₁, v₂, z₁, z₂);

U₁=U₁(v₁, v₂, z₁, z₂);

U₁=U₁(v₁, v₂, z₁, z₂);

Таблицы переходов и выходов автомата Мили (таблицы3.8-3.9) в закодированном виде представленны в табл.3.19и3.20.

По таблице 3.20можно составить булевские выражения для

W₁-W₃:W₁=v₁v₂ z₁ z₂v₁z₁; W₂=v₁v₂ z₁ z₂;

W3= z₁ z₂ v₁z₁ v₁v₂ z₁ z₂ v₂ z₂;

Таблица 3.21

z1z2/v1v2	00	10	11
00	10	-	00
10	11	00	-
11	10	11	11

Эти три уравнения определяют ту часть комбинационной схемы, которая вырабатывает выходные сигналы. А для реализации функций возбужденияU₁ иU₂ необходимо построить таблицу входов, которая строится по таблице переходов автомата Мили (табл.3.19) и по таблице входов автомата Мура, обладающего полнотой (табл.3.15). Таблица входов синтезируемого автомата Мили представлена таблицей3.21.

По таблице входов (табл. 3.21) составляются выражения для функций возбуждения:

U1= v₁z₁ z₂v₁v₂ z₁z₂; U₂=z₂v₁ z₁z₂v₁v₂ z₁z₂;

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

Реализация комбинационной схемы производится в заданном базисе (в данном случае - И, ИЛИ, НЕ) после выполнения минимизации системы булевых выражений. Синтезированный структурный автомат Мили имеет 2 физических входа (z₁ иz₂), 3 физических выхода(V₁, W₂, W₃), 2 элемента памяти (автоматы Мура, обладающие полнотой).

Основная литература: 2 [82-123],3 [51-82]

Дополнительная литература:5 [236-283], 7 [305-361]

Контрольные вопросы:

1. Назовите отличе автомата Мура от автомата Миля?

2. Приведите пример синтеза автомата?

3. Назовите основные формы представления автомата?

4. Назовите основные способы задания ФАЛ?

5. Чем отличается ДСНФ от КСНФ?

6. Назовите основные методы минимизации ФАЛ?

Тема лекции 4. Основы схемотехники операционных блоков ЦУ и МПС. Комбинационные схемы. Шифраторы и дешифраторы. Схемы сравнения.

Основные блоки ЦУ делятся на два основных класса:

- комбинационные схемы или схемы без памяти ;

- последовательностные схемы (конечные автомаы или схемы с памятью).

К комбинационным схемам относятся шифраторы и дешифраторы, мультиплексоры и демультиплексоры, компараторы, одноразрядные сумматоры.

Дешифраторы и шифраторы

Дешифратор- это комбинационная схема, преобразующая код, подаваемый на входы, в сигнал на одном из выходов. Если на входы дешифраторов подаются двоичные переменные, то на одном из выходов дешифратора вырабатывается сигнал - 1, а на остальных - 0.

Шифраторвыполняют функцию, обратную функции дешифраторов, т.е. при возбуждении одного из входов шифратора на его выходах образуется двоичный код, отображающий номер возбужденного входа. В общем случае двоичный код шифраторов имеет 2п входов и n выходов.

Рис. 4.1. Дешифратор на 3 входа

Система уравнений, описывающая работу дешифратора, имеет следующий вид:

где x₁(i=0, n-1) - двоичные переменные на входах дешифратора; Р_m(m=0,2ⁿ-1) выходы дешифратора. Для x=3 получим:

P₀=₂₁₀; P₁=₂₁x₀; P₂=₂x₁₀; P₃=₂x₁x₀;

P₄=x₂₁₀; P₅=x₂₁x₀; P₆=x₂x₁₀; P₇=x₂x₁x₀.

Отсюда видно, что для реализации одноступенчатого дешифратора на три входа достаточно иметь восемь схем И. На рис. 4.1представлен дешифратор на три входа на схемах И, а на рис 4.2. – на схемах И-НЕ.

В дешифраторах часто предусматривается операция стробирования, которая позволяет выработать выходные сигналы только в определенные интервалы времени. Количество входов и соответственно выходов в дешифраторах, реализованных в виде СИСа, ограничены. Дешифратор с требуемыми входами и выходами может быть получен из одноступенчатых дешифраторов путем их наращивания.

Рис. 4. 2. Структурная и логическая схемы дешифратора

Рис. 4.3. Структурная схема дешифратора на 64 выхода

На рис. 4.3показана схема дешифратора на 64 выхода посредством трехвходовых стробируемых дешифраторов. На этой схеме старшие разряды x₅, х₄, х₃дешифрируются на первом дешифраторе при C=1. Единичные уровни с выхода этого дешифратора включают один из дешифраторов второй ступени по его стробирующему входу и дешифрируют три младших разряда входного слова. Например, при подаче на вход слова 111001₂=57₁₀по коду 111 DC1 вырабатывается единичный сигнал на выходе 7, который отпирает DC9. На входах DC2-DC9 действует код 001, который возбуждает 1 выход DC9, что соответствует 57 выходу дешифратора.

Шифраторывыполняют функцию, обратную функции дешифраторов, т.е. при возбуждении одного из входов шифратора на его выходах образуется двоичный код, отображающий номер возбужденного входа. В общем случае двоичный код шифраторов имеет 2п входов и n выходов. Правило функционирования шифратора приведено в табл. 4.3.

Из таблицы имеем:

У₀ = P₁ + P₃ + P₅ + P₇ + P₉;

У₁ = P₂ + P₃ + P₆ + P₇;

У₂ = P₄ + P₅ + P₆ + P₇;

У ₃ = P₈ + P₉;

На рис. 4.3 приведена схема шифратора, реализующая функцииприведенной в

табл. 4.1.

Таблица 4.1.

x9	x8	x7	x6	x5	x4	x3	x2	x1	x0	y3	Y2	Y1	y0
0 0 0 0 0 0 0 0 0 1	0 0 0 0 0 0 0 0 1 0	0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 1 0 0 0	0 0 0 0 0 1 0 0 0 0	0 0 0 0 1 0 0 0 0 0	0 0 0 1 0 0 0 0 0 0	0 0 1 0 0 0 0 0 0 0	0 1 0 0 0 0 0 0 0 0	1 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 1 1	0 0 0 0 1 1 1 1 0 0	0 0 1 1 0 0 1 1 0 0	0 1 0 1 0 1 0 1 0 1

Рис. 4.4. Структурная и логическая схемы шифратора

Схемы сравнения

Рассмотрим два целых двоичных числа A=a₁a₂и B=b₁b₂, и пусть у(А=В), у(А>В) и у(А<В) - некоторые полностью определенные булевы функции, которые заданы табл. 4.4. ДНФ этих функций представляется в виде:

В результате минимизаций получим:

Реализация этих функций на программируемых логических матрицах (ПЛМ)

(4, 3, 10) показана на рис. 4.4а.

Для реализации на ПЛМ функции у(А>B), у(A<B), у(А=В) представим в следующем виде:

(4.7)

(4.8)

(4.9)

Реализация этих функций на ПЛМД (4, 3, 5) показана на рис. 4.4 б.

Рис 4.4. Схема реализации на ПЛМ

Основная литература: 2 [82-123],3 [51-82]

Дополнительная литература:5 [236-283], 7 [305-361]

Контрольные вопросы:

1. Назовите основную функцию выполняемую дешифратоомт?

2. Назовите основную функцию выполняемую шифратором?

3. Дайте определние понятию комбинационная схема?

4. В чем разница шифратора и дешифратора?

5. В каких случаях шифратор называют неполным?

6. Назовите основную функцию выполняемую схемой сравнения?

Тема лекции 5. Типовые операционные блоки ЦУ и МПС. Мультиплексоры и демультиплексоры. Компаратор.

Мультиплексоры и демультиплексоры

Мультиплексоромназывается комбинационная схема, осуществляющая передачу данных от n входных каналов в один выходной канал. Подключение входных каналов к выходному производится под управлением кода адреса. На рис.5.1изображена схема

мультиплексора на 4 входа и на один выход (4.1). На входной канал поступают данные х₁, х₂, х_з, х₄, а на управляющие - код адреса а₁и а₂. Код адреса дешифрируется дешифратором и единица с выхода дешифратора, поступая на вход соответствующей схемы И, разрешает прохождение x_iна выход F.

В мультиплексорах, выпускаемых в виде отдельных микросхем, число информационных входов ограничено. Требуемое число входов обеспечивается путем наращивания. Одним из способов наращивания является объединение нескольких мультиплексоров в пирамидную схему. На рис. 5.2приведен вариант мультиплексора 16-1 на основе мультиплексора 4-1.

Рис. 5.1. Схема мультиплексора на 4 входа и его условное обозначение

Рис. 5.2. Схема мультиплексора на 16 входов

Демультиплексоримеет один ин-формационный вход и n информационных выходов. Демультиплексоры выполняют функцию, обратную функции мультиплексора.

Рис. 5.3. Схема демультиплексора и его условное обозначение

На рис. 5.3показаны схемы демультиплексора на 4 выхода. Соответствующая схема И выдает на выход информационный сигнал х в зависимости от кода, поступающего с выхода дешифратора.