close

Вход

Забыли?

вход по аккаунту

?

Mishyra1

код для вставкиСкачать
Министерство образования и науки российской федерации
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
ЦИФРОВЫЕ АВТОМАТЫ.
СТРУКТУРНЫЙ СИНТЕЗ
КОНЕЧНЫХ АВТОМАТОВ
Учебно-методическое пособие
Санкт-Петербург
2014
Составитель – кандидат технических наук, доцент О. В. Мишура
Рецензент – кандидат технических наук, доцент В. П. Попов
Издание предназначено для студентов I курса, обучающихся по
направлению 230400 (квалификация – бакалавр).
Подготовлено кафедрой информационно-сетевых технологий и рекомендовано к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического
приборостроения.
Корректор Т. В. Звертановская
Компьютерная верстка Н. Н. Караваевой
Сдано в набор 23.10.14. Подписано к печати 23.12.14. Формат 60×84 1/16.
Бумага офсетная. Усл. печ. л. 1,2. Тираж 100 экз. Заказ № 681.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2014
1. АБСТРАКТНЫЕ АВТОМАТЫ
1.1. Основные понятия
Автомат – это дискретное устройство, преобразующее входной
сигнал zf в один из выходных сигналов wg в зависимости от того,
в каком состоянии am находился автомат к моменту поступления
входного сигнала: f = 1, 2, ¼, F; g = 1, 2, ¼, G; m = 1, 2, ¼, M. Значения
F, G, M – конечны, поэтому автомат называется конечным. Таким
образом, выходной сигнал автомата в каждый момент времени зависит от значений входного сигнала не только в данный, но и в предыдущие моменты времени. Эта зависимость проявляется в изменении у автомата его внутренних состояний таким образом, что
в каждый момент времени определяется как входным сигналом в тот
же момент времени, так и состоянием, в котором оказался автомат к
данному моменту времени в результате воздействия на его вход сигналов, поступивших в предыдущие моменты времени. В составе таких устройств обязательно присутствуют элементы памяти, внутреннее состояние которых отражает предысторию поступления последовательности входных сигналов. Такие цифровые устройства
называются последовательностными, или конечными автоматами.
1.2. Понятие абстрактного автомата
Математической моделью дискретного устройства, обладающего памятью, является абстрактный автомат, который задается совокупностью пяти объектов:
S = { A, Z, W, δ, λ},
(1)
где À = {a0 , a1, ¼, am , ¼, aM } – множество состояний автомата, причем a0 – начальное состояние; Z = {z1, z2 , ¼, zf ,¼, zF } – множество
входных сигналов; W = {w1, w2 , ¼, wg , ¼, wG } – множество выходных
3
Z = {z1 , z2 , ¼, zf , ¼, zF }
À = {a0 , a1 , ¼, am , ¼, aM }
W = {w1 , w2 , ¼, wg , ¼, wG }
Рис. 1. Абстрактный автомат
сигналов; δ – функция переходов, обеспечивающая выработку последующего состояния аsавтомата в зависимости от текущего состояния am и входного сигнала zf, т. е. às = δ(am , zf ); λ – функция выходов, обеспечивающая выработку выходного сигнала автомата
в зависимости от его состояния am и входного сигнала zf, т. е.
wg = λ(am , zf ).
Абстрактный автомат – автомат, рассматриваемый безотносительно к его внутренней структуре.
Абстрактный автомат имеет один входной и один выходной каналы. Условно его можно изобразить в виде устройства с одним входом и одним выходом (рис. 1).
Абстрактный автомат работает в дискретном автоматном времени, последовательные моменты которого отождествляются с натуральными числами: t = 1, 2, ¼ . В каждый момент времени t абстрактный автомат находится в определенном состоянии из множества А возможных состояний, причем в начальный момент времени
t = 0 – всегда в начальном состоянии а0.
В момент t автомат находится в состоянии а(t). На его вход поступает сигнал z(t), и автомат вырабатывает на выходном канале сигнал w(t) = λ(à(t), z(t)). После чего переходит в состояние, которое
в следующий момент (t + 1) автоматного времени определяется как
à(t + 1) = δ (à(t), z(t)).
Таким образом, абстрактный автомат каждой букве (слову) входной последовательности сигналов Z ставит в однозначное соответствие букву (слово) выходной последовательности сигналов W.
1.3. Абстрактные автоматы Мили и Мура
Абстрактный автомат Мили задается следующими функциями
переходов и выходов (2). Выражение (2) – закон функционирования
автомата Мили:
4
ìïà(t + 1) = δ (à(t), z(t)) ï
í
ïï w(t) = λ ( à(t), z(t)).
ïî
(2)
Абстрактный автомат Мура задается следующими функциями
переходов и выходов (3):
ìïà(t + 1) = δ (à(t), z(t))
ï
í
ïï w(t) = λ ( à(t)).
ïî
(3)
Выражение (3) – закон функционирования автомата Мура.
Различие между автоматами Мили и Мура состоит в том, что выходной сигнал в автомате Мили зависит как от состояния автомата, так и от входного сигнала в рассматриваемый момент времени,
а в автомате Мура – только от состояния автомата.
Автомат Мура всегда можно свести к автомату Мили с тем же самым числом состояний и теми же самыми последовательностями
входных и выходных сигналов.
Для конечного автомата функции δ и λ определены на конечном
множестве значений аргументов и принимают значения из конечных множеств.
1.4. Способы задания автоматов
1.4.1. Табличный способ задания автоматов
На основании закона функционирования автомата Мили (2) автомат Мили может быть задан двумя таблицами: таблицей переходов, задающей функцию à(t + 1) = δ(à(t), z(t)), и таблицей выходов,
задающей функцию w(t) = λ(à(t), z(t)).
В левом столбце таблицы проставляются все возможные входные
сигналы zf, а в верхней строчке – все возможные внутренние состояния автомата аm.
В таблице переходов (табл. 1, а) на пересечении столбца аm и строки zf проставляется состояние aS = δ(am , zf ), в которое к моменту
времени (t + 1) автомат переходит из состояния am под воздействием
входного сигнала zf.
В таблице выходов (табл. 1, б) в аналогичной клетке проставляется выходной сигнал wg = λ(am , zf ), вырабатываемый в момент времени t.
Пусть для автомата Мили множество входных сигналов z = {z1, z2 },
множество выходных сигналов w = {w1, w2 , w3 }, множество внутренних состояний À = {a0 , a1, a2 }.
5
Тогда таблицы переходов (см. табл. 1, а) и выходов (см. табл. 1, б)
имеют вид:
Таблица 1, а
Таблица 1, б
Таблица переходов автомата
Мили
zf
am
а0
а1
а2
z1
а2
а0
а1
z2
а1
а2
а2
Таблица выходов автомата
Мили
zf
am
а0
а1
а2
z1
w2
w1
w2
z2
w1
w3
w3
Для автомата Мура выходной сигнал определяется только внутренним состоянием автомата и не зависит от поступающего входного сигнала, поэтому каждому внутреннему состоянию автомата Мура соответствует определенный выходной сигнал. Вследствие этого
автомат Мура задается только одной таблицей переходов (табл. 2),
которая называется отмеченной, так как каждое состояние отмечается соответствующим выходным сигналом.
Отмеченная таблица переходов автомата Мура (см. табл. 2) отличается от таблицы переходов автомата Мили (см. табл. 1, а) наличием верхней строчки, где проставлены выходные сигналы, соответствующие внутренним состояниям автомата Мура.
Если множество входных сигналов автомата Мура Z = {z1, z2 },
множество выходных сигналов W = {w1, w2 , w3 }, а множество внутренних состояний A = {a0 , a1, a2 , a3 }, то отмеченная таблица переходов автомата Мура может иметь вид:
Таблица 2
Отмеченная таблица переходов автомата Мура
wg
zf
6
w1
w1
w2
w3
a0
a1
a2
a3
z1
a3
a2
a0
a1
z2
a1
a3
a2
a2
am
1.4.2. Графический способ задания автоматов
Графический способ задания автоматов основан на построении
направленных графов. Составляющие направленных графов – это
вершины и дуги. Вершины графов изображаются в виде кружков, в
которых для автоматов Мили проставляются внутренние состояния автоматов, а для автоматов Мура – внутренние состояния и соответствующие им выходные сигналы. Дуги соединяют вершины
графа. Причем, если существует переход aS = δ(am , zf ), то вершина
as соединяется дугой с вершиной аm, направление дуги – от am к aS.
Для автомата Мили дуга отмечается входным сигналом в начале дуги и выходным сигналом в ее конце. Для автомата Мура дуга в середине отмечается только входным сигналом.
Представим граф автомата Мили, заданный таблицами (см.
табл. 1, а, б; рис. 2).
Представим граф автомата Мура, заданный табл. 2 (рис. 3).
Заданием таблиц для автоматов Мили и Мура или построением
графов этих автоматов заканчивается этап абстрактного синтеза
автоматов, где автоматы являются только математическими моделями проектируемых устройств и их внутреннее устройство не рассматривается.
z1
w2
w3
a2
w1
a0
z2
w1
w2
z2
z1
w3
z2
z1
a1
Рис. 2. Граф автомата Мили
a0/w1
z1
a3/w3
z2
z1
z2
z2
a1/w1
z1
a2/w2
z1
z2
Рис. 3. Граф автомата Мура
7
2. СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТОВ
2.1. Структурный автомат
Структурный синтез автоматов осуществляется на базе структурной теории автоматов и сводится к построению схемы, реализующей автомат, состоящий из элементов памяти и логических элементов. Абстрактный автомат представляет собой математическую
модель проектируемого устройства. В структурном автомате учитываются структура входных и выходных сигналов, а также внутренняя структура автомата.
Схема структурного автомата состоит из двух частей: памяти автомата, объединяющей отдельные элементы памяти, и комбинационной схемы, объединяющей логические элементы (рис. 4).
Память структурного автомата, состоящая из элементов памяти
ÝÏ1, …, ÝÏr , …, ÝÏ R , представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная схема представляет собой схему, построенную из логических элементов, составляющих функционально полный базис.
Рассмотрим этапы структурного синтеза автомата.
2.2. Кодирование состояний абстрактного автомата
В процессе структурного синтеза различным состояниям заданного абстрактного автомата ставятся в соответствие различные упорядоченные последовательности состояний элементарных автоматов –
элементов памяти. Таким образом, каждое состояние абстрактного
автомата àm (m = 0, 1, 2, ¼, m, ¼, M) кодируется в структурном автомате набором состояний элементарных автоматов – двоичных элементов памяти ÝÏr (r = 1, 2, ¼, r , ¼, R).
X1
XL
.
.
.
Комбинационная схема
U1...
ЭП1
UR
Память
V1... VR
.
.
.
Y1
YN
ЭПR
Рис. 4. Структурная схема конечного автомата
8
Общее число элементов памяти определяется из выражения:
R ³]log2 (M + 1)[,
(4)
где ]a[ – ближайшее целое число, больше или равно а; а – целое
число.
2.3. Кодирование абстрактных входных и выходных сигналов
У абстрактного автомата один входной и один выходной каналы.
В структурной теории как входные, так и выходные каналы состоят
из нескольких элементарных входных и элементарных выходных
каналов. По этим каналам передаются элементарные сигналы. Набор всех возможных элементарных сигналов для данного автомата
называется структурным алфавитом данного автомата. Структурный автомат (см. рис. 4) имеет входные x1, x2 , ¼, xl , ¼, xL и выходные ó1, ó2 , ..., ón , ¼, yN каналы, на которых появляются сигналы в
структурном алфавите автоматов, являющихся двоичными.
zf (f = 1, ¼, f, ¼, F)
и
выходной
Каждый
входной
wg (g = 1, ¼, g, ¼, G) сигналы абстрактного автомата могут быть закодированы набором состояний входных и выходных каналов
структурного автомата. Разрядность соответствующих двоичных
наборов определяется следующим образом:
L ³]log2F[; (5)
N ³ log2G[. (6)
Переходу абстрактного автомата Мили из состояния аm в состояние аS под воздействием входного сигнала zf с выдачей выходного сигнала wg соответствует переход структурного автомата из одного состояния в другое, закодированное соответствующими R-разрядными
словами, под воздействием L-разрядного входного сигнала с выдачей
N-разрядного сигнала на выходе. Изменение состояний элементов памяти на таком переходе происходит под воздействием сигналов на
входах элементов памяти автомата U = {u1, u2 ,..., ur , ¼, uR }, являющихся выходными сигналами комбинационной схемы и называемых сигналами возбуждения памяти. Выходными сигналами элементов памяти являются сигналы V = {v1, v2 , ¼, vr , ¼, vR }, которые
называются функцией обратной связи от памяти автомата к комбинационной схеме.
Таким образом, после определения количества элементов памяти R по формуле (4), определяющих функционирование памяти
9
автомата, кодирования внутренних состояний абстрактного автомата R-разрядными наборами для структурного автомата, кодирования входных и выходных сигналов абстрактного автомата соответствующими L- и N-разрядными словами структурного автомата
производится синтез комбинационных схем, реализующих функции выходов ó1, ¼, ón , ¼, yN и возбуждения u1, ¼, ur , ¼, uR . Построением схемы в виде (см. рис. 4), реализующей проектируемый
структурный автомат, заканчивается структурный синтез.
2.4. Элементарные автоматы
Из теории о структурной полноте следует, что для структурной
полноты системы элементарных автоматов необходимо включение
в нее элементарных автоматов Мура с полной системой переходов и
полной системой выходов. Такие автоматы, представляющие собой
элементы памяти, могут обладать любым числом внутренних состояний, однако, исходя из реальных возможностей современной технологии, оптимальным числом состояний элементарного автомата
является два, а структурным алфавитом состояний автомата является двоичный алфавит. Всем перечисленным условиям отвечают
триггеры с раздельными входами типа RS и счетным входом T, которые используются в качестве элементарных автоматов – элементов памяти в цифровых устройствах, в качестве устройств с двумя
устойчивыми состояниями «1» и «0».
2.4.1. RS-триггер
Условное обозначение RS-триггера приведено на рис. 5: S – единичный вход (set); R – нулевой вход (reset); Q и Q – прямой и инверсный выходы триггера.
При подаче единичного сигнала на вход S триггер устанавливается в единичное состояние. На его прямом выходе Q – единичный
сигнал (Q = 1), а на инверсном выходе Q – нулевой (Q = 0). При по-
S
R
T
Q
Q
Рис. 5. Условное обозначение RS-триггера
10
A
TA
S
A
R
Рис. 6. Условное обозначение триггера ТА типа RS
даче единичного сигнала на вход R триггер устанавливается в нулевое состояние. На его прямом выходе Q – нулевой сигнал (Q = 0),
а на инверсном Q – единичный сигнал (Q = 1). Если обозначить такой триггер буквой А, то имеем следующее условное обозначение
(рис. 6).
Представим таблицу переходов RS-триггера, где Q(t) – текущее
состояние триггера, Q(t + 1) – следующее состояние триггера,
в которое он переходит при подаче на входы пары сигналов R и S
(табл. 3).
Таблица 3
Таблица переходов RS-триггера
Q(t)
Q(t + 1)
S
R
0
0
0
–
0
1
1
0
1
0
0
1
1
1
–
0
Прочерки в таблице обозначают безразличное значение сигналов.
На основе табл. 3 можно построить граф RS-триггера (рис. 7).
SR
S
R
1
0
SR
Рис. 7. Граф RS-триггера
11
По таблице переходов:
1. переход 0 ® 0 может происходить по двум вариантам входных
сигналов: S R Ú SR = S – не зависит от R;
2. переход 1 ® 1 : S R Ú S R = R – не зависит от S;
3. переход 0 ® 1 : S R;
4. переход 1 ® 0 : SR.
Чтобы оставить триггер в прежнем состоянии, входные сигналы
S и R могут вообще не подаваться.
2.4.2. Т-триггер
Условное обозначение Т-триггера, если он обозначен А, представлено на рис. 8: А, À – прямой и инверсный выходы триггера.
Чтобы перевести триггер в новое состояние, на вход Т нужно подать единичный сигнал. Чтобы сохранить прежнее состояние, на
вход Т нужно подать нулевой сигнал.
Таблица переходов Т-триггера имеет следующий вид (табл. 4).
Таблица 4
Таблица переходов Т-триггера
Q(t)
Q(t + 1)
Т
0
0
0
0
1
1
1
0
1
1
1
0
На основании таблицы можно построить граф Т-триггера (рис. 9).
T
TA
A
T
A
T
T
1
0
T
Рис. 8. Условное обозначение
триггера ТА типа Т
12
Рис. 9. Граф Т-триггера
3. ПРИМЕРЫ СТРУКТУРНОГО СИНТЕЗА
АВТОМАТОВ МИЛИ И МУРА
3.1. Структурный синтез автомата Мили
В качестве примера рассмотрим структурный синтез автомата
Мили, который задан таблично, табл. 1, а – таблица переходов автомата Мили, табл. 1, б – таблица выходов автомата Мили.
Будем считать, что в качестве элементов памяти используются
триггеры типа Т – со счетным входом, а при реализации комбинационной части логической схемы автомата (см. рис. 4) при помощи
логических элементов используется базис Шеффера.
Структурная схема проектируемого автомата Мили в общем виде
представлена на рис. 4.
По формуле (4) определим количество элементов памяти –
Т-триггеров, учитывая, что проектируемый автомат Мили имеет
три внутренних состояния: à0 , à1, à2 .
R = ]log2 (M + 1)[ = ]log2 (2 + 1)[ = 2.
Таким образом, память проектируемого автомата Мили состоит
из двух элементов памяти – двух Т-триггеров: ТА и ТВ.
Закодируем внутренние состояния автомата Мили, учитывая,
что код будет двухразрядный, состоящий из букв А и В, где прямые
значения А и В соответствуют единичным значениям в кодовой
комбинации, а инверсные значения À è Â – нулевым значениям.
Таким образом:
à0 ® 00 => À Â;
à1 ® 01 => ÀÂ
;
à2 ® 10 => À Â.
Определим количество структурных входных и выходных сигналов, т. е. разрядность для их кодирования по формулам (5) и (6).
Разрядность кода для входных сигналов:
L = ]log2F[=]log2 2[= 1.
Разрядность кода для выходных сигналов:
N = ]log2G[=]log2 3[= 2.
13
Закодируем входные сигналы следующим образом:
z1 = 0 => x;
z2 = 1 => x.
Закодируем выходные сигналы следующим образом:
w1 = 01 => y1y2 ;
w2 = 10 => y1 y2 ;
w3 = 11 => y1y2 .
При операциях кодирования использовалось совпадение индекса у параметра абстрактного автомата с предлагаемым двоичным
кодом соответствующего параметра структурного автомата, например, w3 = 11 => y1y2 .
Учитывая предложенные варианты кодирования внутренних состояний, входных и выходных сигналов абстрактного проектируемого автомата Мили, представим табл. 1, а и 1, б в закодированном
виде, т. е. для структурного автомата Мили.
Табл. 1, а будет иметь вид, показанный в табл. 5.
Табл. 1, б будет иметь вид, показанный в табл. 6.
Таблица 6
Таблица 5
Таблица переходов структурного
автомата Мили
х
АВ
x
х
À Â
ÀÂ
ÀÂ
À Â
ÀÂ
ÀÂ
ÀÂ
ÀÂ
ÀÂ
Таблица выходов структурного
автомата Мили
x
AB
AB
AB
AB
x
ó1 ó2
ó1 ó2
ó1 ó2
x
ó1 ó2
ó1 ó2
ó1 ó2
Теперь необходимо определить сигналы возбуждения, которые
подаются из комбинационной части схемы (см. рис. 4) на элементы
памяти u1, ¼, uR . Для нашего конкретного случая R = 2, поэтому
сигналы u1 и u2. Поскольку в качестве элементов памяти выбраны
Т-триггеры, то сигналы возбуждения памяти – это входные сигналы триггеров, т. е. ТА и ТВ.
Рассматривая табл. 1, а, 5 и таблицу переходов Т-триггеров 4,
можно сделать вывод, чтобы осуществить переход автомата из со14
стояния а0 в а1, нужно изменить состояние триггера ТВ из нулевого
в единичное, а состояние триггера ТА оставить без изменения. Для
осуществления перехода из а0 в а2 необходимо изменить состояние
триггера ТА с нулевого на единичное, а состояние триггера ТВ оставить без изменения и т. д. Подобным образом нужно рассмотреть все
возможные переходы в табл. 5. На основании такого анализа составляем таблицу возбуждения, в которой в соответствующих клетках
представлены сигналы изменения состояния триггеров ТА и ТВ, являющихся сигналами возбуждения памяти (табл. 7).
Таблица 7
Таблица возбуждения автомата Мили
АВ
x
ТА,ТВ
ТА
ТА
x
x
AB
A B
ÒÀ
ТВ
ÒÂ
ÀB
ТА
ТВ
ТА
ТВ
ÒÀ
ТВ
ТА
ТВ
ТА
ТВ
ТВ
ÒÀ
ÒÂ
Из табл. 7 можно найти логические функции, описывающие сигналы возбуждения памяти, путем нахождения конъюнкций внутренних состояний и входных сигналов, которые потом объединяются знаками дизъюнкций, т. е. в ДНФ:
Ò À = ÀÂõ Ú ÀÂõ Ú ÀÂõ. (7)
Для минимизации этого выражения воспользуемся диаграммой
Вейча:
В
1
А
1
1
х
TA = Bx Ú ABx. (7a)
Аналогичным образом найдем ТВ:
ÒÂ = ÀÂõ Ú ÀÂõ Ú ÀÂõ Ú ÀÂõ; (8)
15
В
1
1
А
1
1
х
ÒÂ = ÀÂ Ú Àõ Ú ÀÂõ. (9)
Логические функции, описывающие выходные сигналы у1 и у2,
можно найти из табл. 6.
ó1 = ÀÂõ Ú ÀÂx Ú ÀÂõ Ú ÀÂõ; В
1
(10)
А
1
1
1
х
ó1 = ÀÂ Ú Âõ Ú ÀÂõ; (11)
ó2 = ÀÂõ Ú ÀBõ Ú ÀBx Ú ÀÂõ; (12)
ó2 = ÀÂ Ú Âõ. (13)
Таким образом, найдены параметры структурного автомата Мили: функции возбуждения памяти ТА (7a) и ТВ(9) и выходные сигналы у1 (11) и у2 (13). Для построения схемы автомата Мили переведем
выражения (7a), (9), (11), (13) в базис Шеффера, используя законы де
Моргана:
16
Ò À = Bx Ú ABx = ( Âõ)*(ÀÂõ) = S (S(B, x ), S( A, B, x)); (14)
TB = ÀÂ Ú Àõ Ú ÀÂõ = ÀÂ*Àõ*ÀÂõ = (15)
y1 = ÀÂ Ú Âõ Ú ÀÂõ = ÀÂ*Âõ*ÀÂõ = (16)
= S (S( À, Â), S( À, õ), S( À, Â, õ ));
= S(S( À, Â), S(Â, õ ), S( À, Â, õ));
y2 = ÀÂ Ú Âõ = ( ÀÂ)( Âõ) = S(S(À, Â), S(Â, õ)) . (17)
По выражениям (14)–(17) построим логическую схему проектируемого автомата Мили (рис. 10).
x x
B
AA
B
&
&
&
TA
T TA
A
A
&
&
&
TB T TB
&
y1
&
y2
B
B
&
&
&
&
&
&
Рис. 10. Логическая схема структурного автомата Мили
17
3.2. Структурный синтез автомата Мура
В качестве примера рассмотрим структурный синтез автомата Мура, заданного графически. Граф абстрактного автомата Мура
приведен на рис. 3.
В качестве элементов памяти будем использовать RS-триггеры.
При реализации комбинационной части логической схемы автомата (см. рис. 4) при помощи логических элементов будем использовать базис Пирса.
Структурная схема проектируемого автомата Мура в общем виде
представлена на рис. 4.
По формуле (4) определим количество элементов памяти – RSтриггеров, учитывая, что проектируемый автомат Мура имеет четыре внутренних состояния: à0 , à1, à2 , à3
R = ]log2 (M + 1)[ = ]log2 (3 + 1)[ = 2.
Таким образом, память проектируемого автомата Мура будет состоять из двух элементов памяти – двух RS-триггеров: ТА и ТВ.
Закодируем внутренние состояния автомата Мура, учитывая,
что код будет двухразрядным, состоящим из двух букв А и В, где
прямые значения А и В соответствуют единичным значениям в кодовой комбинации, а инверсные значения À è Â – нулевым значениям.
Таким образом,
à0 = 00 => ÀÂ;
à1 = 01 => ÀÂ;
à2 = 10 => ÀÂ;
à3 = 11 => ÀÂ.
Определим количество структурных входных и выходных сигналов, т. е. разрядность для их кодирования по формулам (5) и (6).
Разрядность кода для входных сигналов:
L = ]log2F[ = ]log2 2[ = 1.
Разрядность кода для выходных сигналов:
N = ]log2G[ = ]log2 3[ = 2.
18
Закодируем входные сигналы следующим образом:
z1 = 0 => x;
z2 = 1 => x.
Закодируем выходные сигналы следующим образом:
w1 = 01 => y1y2 ;
w2 = 10 => y1 y2 ;
w3 = 11 => y1y2 .
При операциях кодирования использовалось совпадение индекса у параметра абстрактного автомата с предлагаемым двоичным
кодом соответствующего параметра структурного автомата, например, w3 = 11 => y1y2 .
Учитывая предложенные варианты кодирования внутренних
состояний, входных и выходных сигналов абстрактного проектируемого автомата Мура, представим граф автомата Мура (см. рис. 3)
в закодированном виде, т. е. для структурного автомата Мура (рис. 11).
Теперь необходимо определить сигналы возбуждения, которые
подаются из комбинационной части схемы (см. рис. 4) на элементы
памяти U1, ¼, UR . Для нашего конкретного случая R = 2, поэтому
сигналы возбуждения U1 и U2. Поскольку в качестве элементов памяти выбраны RS-триггеры, то сигналы возбуждения памяти – это
пары входных сигналов триггеров: для Ò À ® R A , S A и для
Ò B ® R B , SB .
Рассматривая графы автомата Мура на рис. 3 и 11 и таблицу переходов триггера RS (см. табл. 3), можно сделать следующий вывод.
AB/
y1y2
x
x
x
AB/
y1y2
AB/
y1y2
x
x
x
AB/
y1y2
x
x
Рис. 11. Закодированный граф автомата Мура
19
SA, RA; SB, RB
AB/
y1y2
x
SA, RA; –, RB
–, RA; SB, RB
SA, –; SB, RB
S A , R A ; S B, –
x
AB/
y1y2
x
AB/
y1y2
x
x
x
AB/
y1y2
SA, RA; –, RB
x
SA, RA; SB, RB
Рис. 12. Закодированный граф автомата Мура
с отмеченными дугами
Чтобы осуществить переход автомата из состояния а0 в состояние
а1, нужно изменить состояние триггера ТВ из нулевого в единичное, а состояние триггера ТА оставить без изменения, чтобы осуществить переход автомата из состояния а2 в состояние а0, нужно изменить состояние триггера ТА из единичного в нулевое, а состояние
триггера ТВ оставить без изменения. Подобным образом нужно рассмотреть все возможные переходы по графу на рис. 3. На основании
такого анализа и учитывая таблицу переходов триггера RS (табл. 3),
представим граф на рис. 11 следующим образом (рис. 12): дуги этого
графа пометим соответствующими парами входных сигналов триггера RS, которые обеспечивают данный переход.
По графу на рис. 12 находим логические функции, описывающие
сигналы возбуждения памяти, т. е. пары входных сигналов триггеров R и S, путем определения конъюнкций внутренних состояний
и входных сигналов автомата, которые потом объединяются знаками дизъюнкций, т. е. в ДНФ. В данном случае неопределенные входные сигналы S и R, которые обозначены прочерками, будем считать
единичными и также включим в ДНФ.
S A = ABx Ú ABx Ú ABx Ú ABx Ú ABx .
----
В
х
20
А
----
Подчеркнутые конъюнкции – это прочерки, т. е. неопределенные
значения входного сигнала SA:
S A = AB Ú Ax; (18)
R A = ABx Ú ABx Ú ABx;
----
В
А
х
R A = Ax; (19)
SB = ABx Ú ABx Ú ABx Ú ABx;
----
В
----
А
х
SB = AB; (20)
RB = ABx Ú ABx Ú ABx Ú ABx;
----
----
В
А
–
1
–
х
RB = Ax Ú ABx. (21)
Логические функции, описывающие выходные сигналы у1 и у2,
определяются дизъюнкциями внутренних состояний и не зависят
от входных сигналов:
ó1 = AB Ú AB = À; (22)
ó1 = AB Ú AB Ú AB = A Ú B. (23)
21
Таким образом, найдены параметры структурного автомата Мура: функции возбуждения памяти, т. е. входные сигналы триггеров
ТА и ТВ, а именно, SA(18) и RA(19), SB (20) и RB(21), и выходные сигналы у1(22) и у2(23).
Для построения схемы автомата Мура переведем выражения
(18)–(23) в базис Пирса, используя законы де Моргана:
S A = AB Ú Ax = ( À Ú Â) Ú ( À Ú õ) = ÐÐ(Ð( À, Â), Ð ( À, õ));
(24)
R A = Ax = À Ú õ = Ð( À, õ); (25)
SB = A B = À Ú Â = Ð( À, Â); (26)
RB = A x Ú A B x = ( À Ú õ ) Ú (À Ú Â Ú õ) = ÐÐ(Ð( À, õ ), Ð ( À, Â, õ)); (27)
x x
AA
B
B
1
1
SA
1
S TA
1
R
1
RA
1
SB
A
A
S TB B
1
R
1
1
1
B
RB
y1
1
1
y2
Рис. 13. Логическая схема структурного автомата Мура
22
ó1 = À; (28)
ó2 = À Ú Â = ÐÐ ( À, Â).
(29)
По выражениям (24)–(29) построим логическую схему проектируемого автомата Мура (рис. 13).
Рекомендуемая литература
1. Мишура О. В. Цифровые автоматы. Основы алгебры логики.
Минимизация логических функций при помощи диаграмм Вейча:
учеб.-метод. пособие для студ. 2-го курса заочной формы обучения.
СПб.: ГУАП, 2013.
2. Пятибратов А. П., Кирпиченко А. А., Гудьно Л. П. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 2002.
3. Фрикс К. Вводный курс цифровой электроники. М.: Техносфера, 2004.
Содержание
1. Абстрактные автоматы....................................................... 1.1. Основные понятия...................................................... 1.2. Понятие абстрактного автомата.................................... 1.3. Абстрактные автоматы Мили и Мура............................. 1.4. Способы задания автоматов.......................................... 3
3
3
4
5
2. Структурный синтез автоматов............................................ 2.1. Структурный автомат.................................................. 2.2. Кодирование состояний абстрактного автомата............... 2.3. Кодирование абстрактных входных и выходных сигналов
2.4. Элементарные автоматы.............................................. 8
8
8
9
10
3. Примеры структурного синтеза автоматов мили и мура......... 3.1. Структурный синтез автомата Мили.............................. 3.2. Структурный синтез автомата Мура.............................. Рекомендуемая литература................................................ 13
13
18
23
23
Документ
Категория
Без категории
Просмотров
0
Размер файла
979 Кб
Теги
mishyra1
1/--страниц
Пожаловаться на содержимое документа