Тема 5. Схемотехника цифровых узлов, Цифровые автоматы и их разновидности

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

Как было указано в предыдущем разделе, большинство современных цифровых устройств являются последовательностными или цифровыми автоматами с памятью, состоящими из комбинационной схемы и элементов памяти – запоминающих элементов (ЗЭ) (рис.4.1). Там были рассмотрены

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

5.1 Цифровые автоматы и их разновидности

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

В состав цифровых автоматов обязательно входят запоминающие элементы (элементы памяти). Выходные сигналы в таких автоматах формируются в зависимости от входных сигналов и состояний, в которых находятся элементы памяти. Наличие элементов памяти придает ЦА свойство иметь некоторое внутреннее состояние А, определяемое совокупностью состояний всех элементов памяти. В зависимости от внутреннего состояния ЦА различно реагируют на один и тот же набор входных сигналов. Воспринимая входные сигналы Z при определенном состоянии, ЦА в соответствии с заложенной в него программой переходит в новое состояние и вырабатываетвыходные сигналы W. Переходы ЦА из одного состояния в другое начинаются с некоторого исходного состояния, задание которого также является частью задания автомата. В конечном счете, текущее состояние и выходы автомата зависят от начального состояния и всех наборов входных сигналов, поступивших на автомат в предшествующие моменты времени. Таким образом, вся последовательность входных сигналов определяет последовательность состояний автомата и его выходных сигналов. Это объясняет название «последовательностные схемы».

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

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

Цифровые автоматы в каноническом представлении разделяют на две части (рис. 5.1): память(ЭП) и комбинационную цепь (КЦ). На входы КЦ подаются входные сигналы Z_t и сигналы состояния A_t цифрового автомата. На ее выходе вырабатываются выходные сигналы W_t и сигналы перевода ЦА в новое состояние A_t+1.

Рис. 5.1. Структурная схема асинхронного (а) и синхронного (б) цифровых автоматов

В асинхронных автоматах (рис. 5.1.а) очень часто роль элементов памяти играют элементызадержки, через которые сигналы состояния A_tпередаются на входы КЦ, чтобы совместно с новым набором входных переменных Z_t определить следующую пару значений выходов W_t и состоянияA_t+1 на выходе. Элементы асинхронного ЦА переключаются под непосредственным воздействием изменений входных сигналов. Скорость распространения процесса переключений в цепях асинхронного автомата определяется собственными задержками элементов, поэтому моменты переходов из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени.

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

5.2 Абстрактный и структурный автоматы

Общая теория автоматов при сделанных выше допущениях разбивается на две большие части, которым присвоены названия абстрактной теории автоматов и структурной теории автоматов. Различие между ними заключается в том, что в абстрактной теории не учитываются структура как самого автомата, так и структуры его входных и выходных сигналов. Входные и выходные сигналы рассматриваются при этом просто как буквы двух фиксированных для данного автомата алфавитов: входного и выходного. Не интересуясь способом построения автомата, абстрактная теория изучает лишь те переходы, которые претерпевает автомат под воздействием входных сигналов, и те выходные сигналы, которые он при этом выдает.

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

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

Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстрактный автомат, определенный как 6-компонентный кортеж: S=(A, Z, W, d, l, а₁) у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний (внутренний алфавит),

2. Z={z₁, z₂, ... ,z_f} - множество входных сигналов (входной алфавит),

3. W={w₁, w₂, ..., w_g} - множество выходных сигналов (выходной алфавит),

4. d : A·Z®A - функция переходов, реализующая отображение D_d ÍА·Z в А. Иными словами функция d некоторым парам “состояние - входной сигнал” (а_m, z_f) ставит в соответствие состояния автомата а_s= d (a_m, z_f), a_sÎA,

5. l : A·Z®W - функция выходов, реализующая отображение D_l ÍА·Z на W. Функция l некоторым парам “состояние - входной сигнал” (а_m, z_f) ставит в соответствие выходные сигналы автомата W_g=l(а_m, z_f), W_gÎW,

6. a_i ÎA - начальное состояние автомата.

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

Рис. 5.2. Абстрактный автомат

Абстрактный автомат (рис. 5.2) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном состоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t)ÎZ. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита W(t)=l(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=d[a(t), z(t)], a(t) ÎA, w(t) ÎW.

Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z во множество слов выходного алфавита W. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1),... - выходное слово. Таким образом, выходное слово = =j(входное слово), где j - отображение, осуществляемое абстрактным автоматом.

На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рис. 5.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.

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

На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).

Закон функционирования автомата Мили задается уравнениями:

a(t+1) = d(a(t), z(t)); w(t) = l(a(t), z(t)), где t = 0,1,2,...

Закон функционирования автомата Мура задается уравнениями:

a(t+1)=d(a(t), z(t)); w(t) = l(a(t)), где t = 0,1,2,...

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

Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так называемым С- автоматом.

Под абстрактным С- автоматом будем понимать математическую модель дискретного устройства, определяемую восьмикомпонентным вектором

S=( A, Z, W, U, d, l₁, l₂, а₁ ), у которого:

1. A={a₁, a₂, ... ,a_m} - множество состояний;

2. Z={z₁, z₂, ... ,z_f} - входной алфавит;

3. W={w₁, w₂, ..., w_g} - выходной алфавит типа 1;

4. U={u₁, u₂,...,u_h} - выходной алфавит типа 2;

5. d : A · Z ® A - функция переходов, реализующая отображение D_d ÍА·Z в А;

6. l₁ : A · Z ® W - функция выходов, реализующая отображение D_l1 ÍА·Z в W;

7. l₂ : A ® U - функция выходов, реализующая отображение D_l2 ÍА в U;

8. а₁ Î А - начальное состояние автомата.

Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов l₁ и l₂, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями: а( t + 1)=d(a( t), z( t)); w( t)=l₁(a( t), z( t)); u( t)=l₂(a( t)), где t = 0, 1, 2, ...

Выходной сигнал U_h=l₂(a_m) выдается все время, пока автомат находится в состоянии a_m. Выходной сигнал Wg=l₁(a_m, z_f) выдается во время действия входного сигнала Z_f при нахождении автомата в состоянии a_m.

Рассмотренные выше абстрактные автоматы можно разделить на:

1) полностью определенные и частичные;

2) детерминированные и вероятностные.

Полностью определенным называется абстрактный цифровой автомат , у которого функция переходов и функция выходов определены для всех пар (a_i, z_j).

Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функции определены не для всех пар (a_i, z_j).

К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии a_i, под действием любого входного сигнала z_j не может перейти более, чем в одно состояние.

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

Абстрактный автомат называется конечным, если конечны множества А = {a₁, a₂, ..., a_m}, Z = {z₁, z₂, ..., z_f}, W = {w₁, w₂, ..., w_g}. Автомат носит название инициального, если в нем выделено начальное состояние a₁.

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

В отличие от абстрактного автомата, имеющего один вход и один выход (рис. 5.3.а), на которые поступают сигналы во входном и выходят в выходном W={W₁,..,W_G} алфавитах, структурный автомат (рис. 5.3.б) имеет L входных каналов х₁,х₂,..,х_L и N выходных y₁,y₂,…,y_N на каждом из которых присутствует сигнал структурного алфавита.

Рис.5.3. Абстрактный (а) и структурный (б) автоматы

Обычно в качестве структурного используется двоичный алфавит. В этом случае каждому входному сигналу Z_F абстрактного автомата соответствует некоторый двоичный вектор(l_f1,l_f2,..,l_fL), где l_fLÎ{0,1}.

Очевидно, что для представления (кодирования) входных сигналов Z₁,..,Z_F абстрактного автомата различными двоичными векторами должно быть выполнено условие L ] log₂F [, аналогично N ] log₂G [. Например, Z={Z₁,Z₂,Z₃,Z₄} и W={W₁,W₂,W₃}, тогда L log₂4=2 и N log₂3=2

Закодировать входные и выходные сигналы можно, например, так: Z₁ = 00, Z₂ = 01, Z₃ = 10, Z₄= 11, W₁ = 00, W₂ = 01 и W₃ = 11.

Следовательно, структурный автомат с двумя входами x₁ и x₂ и двумя выходами y₁ и y₂ может быть представлен в виде, представленном на рис.5.4:

Рис.5.4 Структурный автомат с двумя входами x₁ и x₂ и двумя выходами y₁ и y₂

5.3. Способы описания и задания автоматов

Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, Z, W, d, l, а₁). Множества А, Z, W описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций d и l (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графический.

При табличном способе задания автомат Мили описывается с помощью двух таблиц. Одна из них (таблица переходов) задает функцию d, т.е. a(t +1)=d(a(t), z(t)) (табл. 5.1), вторая (таблица выходов) - функцию l, т.е. W(t)=l(a(t), z(t)) ( табл. 5.2).

Каждому столбцу из приведенных таблиц поставлено в соответствие одно состояние из множества А, каждой строке – один входной сигнал из множества Z. На пересечении столбца a_m и строки z_f в табл. 5.1 записывается состояние a_s, в которое должен перейти автомат из состояния a_m под действием входного сигнала Z_f, т.е. a_s=d(a_m, z_f). На пересечении столбца a_m и строки z_f в табл. 5.2 записывается выходной сигнал W_g, выдаваемый автоматом в состоянии a_m при поступлении на вход сигнала z_f, т.е. W_g = l(a_m, z_f).

Для приведенных таблиц множества, образующие автомат A={a₁, a₂, a₃,a₄}, Z={z₁, z₂}, W={w₁, w₂, w₃, w₄, w₅}. Автомат Мили может быть задан одной совмещенной таблицей переходов и выходов (табл. 5.3), в которой каждый элемент a_s / w_g записанный на пересечении столбца a_m и строки z_f, определяется следующим образом: a_s=d(a_m, z_f); w_f=l(a_m, z_f).

Автомат Мура задается одной отмеченной таблицей переходов (табл. 5.4), в которой каждому столбцу приписаны не только состояние a_m, но еще и выходной сигнал W_g, соответствующий этому состоянию, где W_g=l(a_m).

Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк. Об этом говорит сайт https://intellect.icu . В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода. Кроме того, выходной сигнал может быть неопределенным и для некоторых существующих переходов.

Для задания С - автоматов также используется табличный метод. В этом случае таблица переходов (табл.5.5) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим выходным сигналом u_i выходного алфавита типа 2 (табл.5.6).

При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины a_m, задает переход в автомате из состояния a_m в состояние a_s. В начале этой дуги записывается входной сигнал Z_fÎZ, вызывающий данный переход a_s=d(a_m,z_f). Для графа автомата Мили выходной сигнал w_gÎW, формируемый на переходе, записывается в конце дуги, а для автомата Мура – рядом с вершиной a_m, отмеченной состоянием a_m, в котором он формируется. Если переход в автомате из состояния a_m в состояние a_s производится под действием нескольких входных сигналов, то дуге графа, направленной из a_m в a_s, приписываются все эти входные и соответствующие выходные сигналы. Граф С-автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Графы автоматов, заданных своими таблицами переходов и выходов (табл. 5.1¸5.6) представлены на рисунках 5.5¸5.7.

5.4. Связь между моделями Мура и Мили

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

Для каждого автомата Мили может быть построен эквивалентный ему автомат Мура и наоборот.( аналогично это относится и к С-автоматам)

Переход от автомата Мура к эквивалентному ему автомату Мили тривиален и легко осуществляется при графическом способе задания автомата. Для получения графа автомата Мили необходимо выходной сигнал W_g, записанный рядом с вершиной a_s исходного автомата Мура, перенести на все дуги, входящие в эту вершину.

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

Переход от автомата Мили к эквивалентному ему автомату Мура более сложен. Это связано с тем, что в автомате Мура в каждом состоянии вырабатывается только один выходной сигнал. Переход наиболее наглядно делать при графическом способе задания автомата. В этом случае каждое состояние a_i исходного автомата Мили порождает столько состояний автомата Мура, сколько различных выходных сигналов вырабатывается в исходном автомате при попадании в состояние a_i. Рассмотрим переход от автомата Мили S_a к автомату Мура S_b на примере автомата (рис. 5.6).

Как следует из рис. 5.6, для автомата S_a при попадании в состояние а₁ вырабатываются выходные сигналы W₂, W₄, W₅, при попадании в а₂ – W₁, W₂, a₃ – W₂, a₄ – W₃. Каждой паре „состояние a_i- выходной сигнал W_j”, который вырабатывается при попадании в это состояние, поставим в соответствие состояние b_k эквивалентного автомата Мура S_b с тем же выходным сигналом W_j : b₁=(a₁, W₂), b₂ =(a₁, W₄), b₃ =(a₁, W₅), b₄ =(a₂, W₁), b₅ =(a₂, W₂), b₆ =(a₃, W₂), b₇ =(a₄, W₃), т.е. каждое состояние a_i автомата Мили порождает некоторое множество A_i состояний эквивалентного автомата Мура: A₁={b₁, b₂, b₃}, A₂={b₄, b₅}, A₃={b₆}, A₄={b₇}. Как видно, в эквивалентном автомате Мура количество состояний 7. Для построения графа S_b поступаем следующим образом. Т.к. в автомате S_a есть переход из состояния а₁ в состояние а₂ под действием сигнала z₁ с выдачей W₁, то из множества состояний A₁ = {b₁, b₂, b₃}, порождаемых состоянием а₁ автомата S_a в автомате S_b должен быть переход в состояние (a₃, W₂) = b₆ под действием сигнала Z₂ и т.д. Граф эквивалентного автомата Мура представлен на рис. 5.8.

Рис. 5.8. Автомат Мура S_b, эквивалентный автомату Мили S_a

Если от автомата Мура S_b, эквивалентного автомату Мили S_a (рис. 5.8) вновь перейти к автомату Мили, то получим автомат Мили S₁ (рис. 5.9).

Рис. 5.9. Автомат Мили S₁, эквивалентный автомату Мура S_b

Вследствие транзитивности отношения эквивалентности два автомата Мили S₁ и S_a также будут эквивалентными, но у последнего будут на 3 состояния больше. Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем возникает задача нахождения минимального (т.е. с минимальным числом состояний) автомата в классе эквивалентных между собой автоматов.

5.5. Минимизация числа внутренних состояний полностью определенных автоматов

Рассмотрим метод минимизации полностью определенных автоматов, предложенный Ауфенкампом и Хоном.

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

Для пользования методом введем несколько определений.

Два состояния абстрактного автомата называются 1-эквивалентными в том случае, если реакции автомата в этих состояниях на всевозможные входные слова совпадают.

Объединение всех 1-эквивалентных состояний абстрактного автомата образует 1-класс эквивалентности.

1-эквивалентные состояния автомата называются 2-эквивалентными, если они переводятся любым входным сигналом также в 1-эквивалентные состояния.

Объединение всех 2-эквивалентных состояний образует 2-класс эквивалентности.

По индукции можно распространить определение до i-эквивалентных состояний и i-классов эквивалентности.

Если для некоторого i разбиения состояний автомата на ( i +1) - классы совпадает с разбиением на i-классы, то оно является разбиением и на ¥ - классы эквивалентности.

Разбиение множества внутренних состояний автомата на ¥ - классы и является требуемым разбиением на классы эквивалентности, при этом такое разбиение может быть получено за конечное число шагов.

Все вышеизложенное непосредственно применимо к минимизации автомата Мили. При минимизации полностью определенных автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-эквивалентные классы: к такому классу относятся одинаково отмеченные состояния автомата Мура.

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

Рассмотрим пример минимизации автомата Мили, заданного таблицами переходов и выходов – таблицы 5.7.

Из таблицы выходов получаем разбиение на 1-классы эквивалентности p₁, объединяя в эквивалентные классы Bi состояния с одинаковыми столбцами: p₁ = {B₁, B₂}; B₂ = {a₁, a₂, a₅, a₆}; B₂ = {a₃, a₄}. Для получения 2-эквивалентных состояний строим таблицу 1-разбиения (табл.5.8), заменяя в таблице переходов состояния a₁ соответствующими классами эквивалентности B1 или B2.

Из полученной таблицы 1-разбиения получаем 2-классы эквивалентности C_i и разбиение p₂ = {C₁, C₂, C₃}, где С₁ = {a₁, a₂}, C₂ = {a₅, a₆}, C₃ = {a₃, a₄}. Сравнивая p₂ и p₁, отмечаем, что эти разбиения отличаются друг от друга. Поэтому аналогично строим таблицу 2-разбиения (табл. 5.9), опять заменяя в таблице переходов состояния a_i соответствующими классами эквивалентности C_i.

Из полученной таблицы 2-разбиения получаем 3-классы эквивалентности D_i и разбиение p₃ ={ D₁, D₂, D₃}, где D₁ = {a₁, a₂}, D₂ = {a₅, a₆}, D₃ = {a₃, a₄}.

Сравнивая p₃ и p₂, замечаем, что D₁ = C₁, D₂ = C₂, D₃ = C₃, p₃ = p₃. Следовательно получили разбиение на ¥- эквивалентные классы. Т.к. всего три таких класса, то минимальный автомат будет содержать всего три состояния. Выбираем из каждого класса D_i по одному состоянию и получаем множество состояний A' минимального автомата. Пусть, например, A'={à₁, à₄, à₅}. Для получения минимального автомата из первоначальных таблиц переходов и выходов (табл. 5.7) вычеркиваем столбцы, соответствующие "лишним состояниям" a₂, a₃, a₆. В результате получается минимальный автомат Мили, эквивалентный исходному автомату (табл. 5.10).

Табл.5.10. Таблицы переходов и выходов минимального автомата

Минимизацией числа внутренних состояний автомата заканчивается этап абстрактного синтеза.

5.6. Принцип микропрограммного управления. Понятия об операционном и управляющем автоматах

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для выполнения операций над информацией используются операционные устройства – процессоры, каналы ввода-вывода, устройства управления внешними устройствами и т.д. Функцией операционного устройства является выполнение заданного множества операций F={f₁,...,f_G} над входными словами D={d₁,...,d_H} c целью вычисления слов R={r₁,...,r_Q}, которые представляют результаты операцийR=f_g(D), где g=1,2,...,G.

Функциональная и структурная организация операционных устройств базируется на принципе микропрограммного управления, который состоит в следующем:

1. Любая операция f_g (g=1,...,G), реализуемая устройством, рассматривается как сложное действие, которое разделяется на последовательность элементарных действий над словами информации. Эти элементарные действия называются микрооперациями.

2. Для управления порядком следования микроопераций используются логические условия, которые в зависимости от значений слов, преобразуемых микрооперациями, принимают значения "ложь" или "истина" (1 или 0).

3. Процесс выполнения операций в устройстве описывается в форме алгоритма, который представляется в терминах микроопераций и логических условий и

продолжение следует...

Продолжение:

Часть 1 Тема 5. Схемотехника цифровых узлов, Цифровые автоматы и их разновидности
Часть 2 Операционные элементы - Тема 5. Схемотехника цифровых узлов, Цифровые автоматы
Часть 3 Вау!! 😲 Ты еще не читал? Это зря! - Тема 5. Схемотехника цифровых узлов, Цифровые автоматы

См.также

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