Порядок выполнения работы
1. Подготовить схемы всех указанных выше триггеров.
2. По указанию преподавателя показать указанные схемы и их диаграммы работы.
Содержание отчета
Отчет должен содержать краткие теоретические сведения, необходимые для выполнения работы, таблицы, схемы и диаграммы, полученные при выполнении работы, а также выводы по работе.
Контрольные вопросы
1. Составьте таблицы переходов RS, RSR, RSS, RSE, D, T, DV и JK триггеров.
2. В чем различие между синхронными и асинхронными триггерами?
3. В чем различие между синхронными триггерами, управляемыми уровнем тактирующего сигнала и синхронными триггерами, управляемыми перепадом тактирующего сигнала?
4. Объяснить работу синхронных триггеров, выполненных по MS схеме и по схеме трех триггеров.
5. Охарактеризуйте этапы проектирования триггеров.
6. Как построить Т – триггер на основе D и JK триггеров?
ЛАБОРАТОРНАЯ РАБОТА № 5
ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ
СИНХРОННЫХ АВТОМАТОВ
Цель работы
Изучить методы проектирования и отладки цифровых синхронных автоматов Мура и Мили.
Основные положения
Для задания автомата необходимо описать все элементы множества S = {A, X, Y, , , a0}, т.е.
алфавит состояний А = {а0 ... аk}, где а0 - начальное состояние автомата,
входной алфавит Х = {х1 ... хn},
выходной алфавит Y = {y1 ... ym},
функцию переходов и выходов .
С этой целью наиболее часто используют табличный или графический способы задания. На этом и завершается первый этап синтеза автоматов.
Однако, автомат может содержать лишние внутренние состояния и
поэтому необходимо провести минимизацию числа состояний автомата.
Основная идея одного из методов минимизации состоит в разбиении
всех состояний исходного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Таким образом, получающийся в результате минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Два состояния аm и аs называются эквивалентными (аm аs), если (аm, ) = (аs, ) для всевозможных входных слов . Если аm и аs не эквивалентны, они различимы.
Введем понятие k эквивалентности. Два состояния аm и аs k – экви- валентны, если (аm, k) = (аs, k) для всевозможных входных слов длины k, если состояния не k - эквивалентны, они k - различимы. Приведенные ношения эквивалентности и k - эквивалентности используются для разбиения множества состояний автомата на попарно не пересекающиеся классы (классы эквивалентности). Соответствующие разбиения на классы эквивалентности и k-эквивалентности будем обозначать и k .Разбиение позволяет определить избыточные элементы в множестве состояний автомата.
Минимизация числа состояний автомата состоит из следующих шагов.
1. Находятся последовательные разбиения 1, 2 ... k, k+1 мно- жества состояний на классы до тех пор, пока на каком-то k+1 шаге не окажется k+1 = k .B этом случае k = , т.е. k-эквивалентные состояния являются в этом случае эквивалентными.
2. В каждом классе эквивалентности разбиения выбирается по одному элементу, которые образуют новое множество состояний мини- мального автомата.
3. Для определения функций переходов и выходов вычеркиваются строки не вошедшие в множество состояний минимального автомата. А в оставшихся строках таблицы переходов все состояния заменяются на эквивалентные из нового минимального множества состояний автомата.
Рассмотрим на примере минимизацию числа состояний автомата Мили, заданного таблицей переходов (таблица 5.1) и таблицей выходов (таблица 5.2).
Непосредственно по таблице выходов (таблица 5.2) получим разбиение 1 на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые строки 1 = {B1, B2}, B1 = {a1, a2, a5, a6},
B2 = {a3, a4}.
Таблица 5.1 – Таблица переходов Таблица 5.2 – Таблица выходов
А |
х 1 |
х 2 |
|
А |
х 1 |
х 2 |
а 1 |
а 3 |
а 5 |
|
а 1 |
y 1 |
y 1 |
а 2 |
а 4 |
а 6 |
|
а 2 |
y 1 |
y 1 |
а 3 |
а 3 |
а 5 |
|
а 3 |
y 1 |
y 2 |
а 4 |
а 4 |
а 6 |
|
а 4 |
y 1 |
y 2 |
а 5 |
а 5 |
а 1 |
|
а 5 |
y 1 |
y 1 |
а 6 |
а 6 |
а 2 |
|
а 6 |
y 1 |
y 1 |
Построим таблицу для 1 (таблица 5.3), заменяя состояния в таблице переходов соответствующими классами 1 – эквивалентных состояний.
По приведенной таблице получаем разбиение 2 на классы 2 – экви- валентных состояний (таблица 5.4), где 2 = {С1, C2, C3}, C1 = {a1, a2},
C2 = {a5, a6}, C3 = {a3, a4} .
Таблица 5.3 – 1–эквивалентности Таблица 5.4 – 2-эквивалентности
1 |
х 1 |
х 2 |
|
|
2 |
х 1 |
х 2 |
||
В 1 |
а 1 |
B 2 |
B 1 |
|
|
C 1 |
а 1 |
C 3 |
C 2 |
а 2 |
B 2 |
B 1 |
|
|
а 2 |
C 3 |
C 2 |
||
а 5 |
B 1 |
B 1 |
|
|
C 2 |
а 5 |
C 2 |
C 1 |
|
а 6 |
B 1 |
B 1 |
|
|
а 6 |
C 2 |
C 1 |
||
В 2
|
а 3 |
B 2 |
B 1 |
|
|
C 3 |
а 3 |
C 3 |
C 2 |
а 4 |
B 2 |
B 1 |
|
|
а 4 |
C 3 |
C 2 |
||
Производим разбиение 3, которое совпадает с 2. Поэтому про- извольно выберем из каждого класса С1, C2 и С3 по одному состоянию и получаем таблицу переходов (таблица 5.5) и таблицу выходов (таблица 5.6) минимального автомата Мили.
Таблица 5.5 – Таблица переходов Таблица 5.6 – Таблица выходов
А |
х 1 |
х 2 |
|
А |
х 1 |
х 2 |
а 1 |
а 4 |
а 5 |
|
а 1 |
y 1 |
y 1 |
а 4 |
а 4 |
а 5 |
|
а 4 |
y 1 |
y 2 |
а 5 |
а 5 |
а 1 |
|
а 5 |
y 1 |
y 2 |
Минимизация числа состояний автомата Мура проводится аналогично.
Канонический метод структурного синтеза позволяет свести зада- чу синтеза произвольного автомата к задаче синтеза комбинационных схем.
Канонический метод синтеза условно можно разделить на следующие этапы:
кодирование,
выбор элементов памяти,
построение булевых функций выходов автомата и возбуждения элементов памяти,
построение функциональной схемы автомата.
При переходе на структурный уровень представления, каждая буква x i входного алфавита X, каждая буква y i выходного алфавита Y, каждая буква аi алфавита состояний А представляется двоичным вектором.
Число сигналов, необходимых, например, для кодирования внутренних состояний автомата, определяется по формуле:
kc ] log 2 │A│ [ ,
где ] М [ - обозначает наименьшее целое число, большее или равное М,
│А│-мощность алфавита состояний автомата, например, если
А = {а1, а2, а3}, то │А│ = 3.
Если у автомата 3 состояния, то k 2. Иными словами, каждую букву аi c А можно закодировать двоичным вектором, состоящим не менее чем из двух компонент, например, А = {00, 01, 10}.
Пусть задан автомат Мили с помощью таблицы переходов (таблица 5.7) и таблицы выходов (таблица 5.8).
Мы видим, что минимальное число входных каналов k вх = 1, так как │X│= 2, а kвых = ]log2 2[ = 1. Иными словами, каждую букву x1, x2 можно закодировать двоичным вектором, состоящим из одной компоненты, т.е.
X = {0, 1}.
Таблица 5.7 – Таблица переходов Таблица 5.8 – Таблица выходов
Состояния автомата |
Входные сигналы |
|
Состояния автомата |
Входные сигналы |
||
х 1 |
х 2 |
|
х 1 |
х 2 |
||
а 1 |
а 2 |
а 1 |
|
а 1 |
y 1 |
y 3 |
а 2 |
а 1 |
а 2 |
|
а 2 |
y 2 |
y 4 |
а 3 |
а 3 |
а 2 |
|
а 3 |
y 1 |
y 2 |
Каждую букву y i выходного алфавита тоже представим как двоичный вектор, число компонент которого kвых = 2, т.е. равно числу физически реализуемых выходных каналов автомата. Y = {00,01,10,11}. Отметим, что в общем случае каждой кодируемой букве может быть приписан произвольный двоичный вектор, но обязательно две различные буквы одного и того же алфавита должны кодироваться различными двоичными векторами.
Закодированные таблицы переходов (таблица 5.9) и выходов (таблица 5.10) представлены ниже.
Таблица 5.9 – Таблица переходов Таблица 5.10 – Таблица выходов
Состояния
|
Входные сигналы |
|
Состояния
|
Входные сигналы |
||
Q 1 Q 2 |
х = 0 |
х = 1 |
|
Q 1 Q 2 |
х = 0 |
х = 1 |
0 0 |
0 1 |
0 0 |
|
0 0 |
0 0 |
1 0 |
0 1 |
0 0 |
0 1 |
|
0 1 |
0 1 |
1 1 |
1 0 |
1 0 |
0 1 |
|
1 0 |
0 0 |
0 1 |
Различны варианты кодирования состояний автомата приводят к различным выражениям функций выходов, в результате чего оказывается что сложность комбинационных схем автомата существенно зависит от выбранного метода кодирования.
Рассмотрим эвристический алгоритм кодирования состояний автомата, позволяющий минимизировать комбинационную схему автомата.
C этой целью возьмем автомат, граф которого имеет 5 состояний (рисунок 5.1).
Рисунок 5.1 – Автоматный граф
Алгоритм состоит из следующих шагов:
1.Построим матрицу, состоящую из всех различных пар номеров состояний, таких, что в автомате есть переходы для рассматриваемых пар.
Матрица строится таким образом, чтобы хотя бы один из элементов i-й строки содержался бы в какой-нибудь из предыдущих строк.
М =
|
1 |
2 |
2 |
4 |
|
2 |
5 |
|
3 |
2 |
|
4 |
3 |
|
4 |
5 |
|
5 |
4 |
|
5 |
1 |
Рисунок 5.2 – Матрица М
2.Закодируем состояния из первой строки матрицы следующим образом:
а1 = 000; а2 = 001. Кодирование будем иллюстрировать картой Карно.
Q 1 \ Q 2 Q 3 |
00 |
01 |
11 |
10 |
0 |
1 |
2 |
|
|
1 |
|
|
|
|
Рисунок 5.3 – Карта Карно после второго этапа
3.Вычеркнем из матрицы М первую строку, соответствующую закоди- рованным состояниям а1 и а2. Получим матрицу М '.
М ' =
|
2 |
4 |
2 |
5 |
|
3 |
2 |
|
4 |
3 |
|
4 |
5 |
|
5 |
4 |
|
5 |
1 |
Рисунок 5.4 – Матрица М '
4.В начальной строке матрицы М ' закодирован один элемент. Выбе- рем из первой строки М ' незакодированный элемент и обозначим его v. Т.е. v = 4.
5.Построим матрицу М 4, выбрав из матрицы М ' строки содержащие 4. В 4 - это множество элементов из матрицы М ', которые уже закодированы.В нашем случае закодирован только второй элемент.
М 4 =
|
2 |
4 |
4 |
3 |
|
4 |
5 |
|
5 |
4 |
Рисунок 5.5 – Матрица М 4
6.Для каждого состояния найдем множество кодов, соседних с кодом рассматриваемого состояния и еще незанятых для кодирования состояний автомата: C'2 = {101, 011}. Таким образом множество свободных кодов, которые могут использоваться для кодирования состояния 4: D'4 = C'2 = {101, 011} .
7.Для выбора кода вводим весовую функцию, характеризующую расстояние между кодами состояний, равное числу элементов памяти, изменяющих свое состояние при переходе:
W101 = │101-001│ =1 ;
W011 = │011-001│ =1 .
Выбираем а4 = 101 и отмечаем на карте Карно.
Q 1 \ Q 2 Q 3 |
00 |
01 |
11 |
10 |
0 |
1 |
2 |
|
|
1 |
|
4 |
|
|
Рисунок 5.6 – Карта Карно после седьмого этапа
8.Вычеркнем из матрицы М ' 1-ую строку, тогда она будет иметь вид
М ' = |
2 |
5 |
3 |
2 |
|
4 |
3 |
|
4 |
5 |
|
5 |
4 |
|
5 |
1 |
Рисунок 5.7 – Матрица М ' после восьмого этапа
9.Выберем из первой строки незакодированный элемент и обозначим его v = 5.
10.Построим матрицу М5, выбрав из М ' строчки, содержащие 5.
М 5 = |
2 |
5 |
4 |
5 |
|
5 |
4 |
|
5 |
1 |
Рисунок 5.7 – Матрица М 5
Множество элементов из матрицы, которое уже закодировано В5 = {2, 4, 1}.
11. Для каждого состояния из множества B5 найдем соседние коды, еще неиспользуемые для кодирования: C'2 = {011}, C'4 = {100, 111}, C'1 = {100, 010}. Таким образом множество свободных кодов, которое может использоваться для кодирования состоянии 5:
D'5 ={011,100,111,010} .
12.Определим весовую функцию для каждого кода
W011 =│011-001│+│011-101│+│011-101│+│011-000│= 1+2+2+2=7,
W100 =│100-001│+│100-101│+│100-101│+│100-000│= 2+1+1+1=5,
W111 =│111-001│+│111-101│+│111-101│+│111-000│= 2+1+1+3=7,
W010 =│010-001│+│010-101│+│010-101│+│010-000│= 2+3+3+1=9.
Таким образом W100 = min {W011, W100, W111, W010}.
Q 1 \ Q 2 Q 3 |
00 |
01 |
11 |
10 |
0 |
1 |
2 |
|
|
1 |
5 |
4 |
|
|
Рисунок 5.8 – Карта Карно после двенадцатого этапа
При расчете весовых функций учитывались только те состояния, с которыми связано состояние 5 (смотри граф переходов). Состояние 4 учи- тывалось дважды, так как они связаны двумя дугами .
13.Вычеркнем из матрицы М' первую строку и построим новую ма- трицу. В новую матрицу не входят также строки, где состояния уже за- кодированы.
М ' = |
3 |
2 |
4 |
3 |
Рисунок 5.9 – Матрица М ' после трнадцатого этапа
14.Выберем из первой строки незакодированный элемент v = 3.
15.Построим матрицу М3, выбрав из М ' строки, содержащие 3.
М 3 = |
3 |
2 |
4 |
3 |
Рисунок 5.10 – Матрица М 3
16.Множество элементов, которые уже закодированы В3 = {2,4}.
17.Найдем соседние коды для каждого состояния:
С'2 = { 011 }, C'4 = { 111 }.
Таким образом множество свободных кодов, которые могут использо- ваться для кодирования состояния 3: D'3 = {011, 111 }.
18.С помощью весовой функции выбираем код для рассматриваемого состояния:
W011 =│011-001│+│011-101│=1+2=3,
W111 =│111-001│+│111-101│=2+1=3.
Выбираем а3 = 011 и отмечаем на карте Карно.
Q 1 \ Q 2 Q 3 |
00 |
01 |
11 |
10 |
0 |
1 |
2 |
3 |
|
1 |
5 |
4 |
|
|
Рисунок 5.8 – Карта Карно после восемнадцатого этапа
Таким образом состояния автомата закодированы.
Отметим, что если D1j = 0, то строим новое множество D2j которое пред- ставляет множество кодов, у которых кодовое расстояние будет равно 2.
Если и D2j = 0, то строим D3j до тех пор пока Dnj = 0, где n = 1, 2, 3 ...
При каноническом методе структурного синтеза автоматов в качестве элементов памяти используются элементарные автоматы Мура с двумя устойчивыми состояниями. В качестве таких элементарных автоматов обычно используют D -, T -, RS -, JK - триггеры.
Очевидно, что число триггеров (элементов памяти) равно числу компонент вектора его состояний.
Удобно иметь специальную таблицу, в которой указано, какое зна- чение должен иметь сигнал возбуждения, чтобы соответствующий триггер перешел из состояния Qs в Qs+1 . Такие данные представлены в таблице 5.11.
Таблица 5.11 – Подграфы переходов триггеров
Qs Qs+1 |
D |
T |
R |
S |
J |
K |
0 0 |
0 |
0 |
|
0 |
0 |
|
0 1 |
1 |
1 |
0 |
1 |
1 |
|
1 0 |
0 |
1 |
1 |
0 |
|
1 |
1 1 |
1 |
0 |
0 |
|
|
0 |
Получим таблицу для определения функций возбуждения элементов памяти. Она получается на основе таблицы переходов, где вместо сос- тояний, в которые переходит автомат, записываем сигналы возбуждения триггеров, которые приведут триггер в нужное состояние.
В качестве элементов памяти автомата будем использовать Т -триггеры. Таблица возбуждений (таблица 5.12), соответствующая таблице переходов 5.9, приведена ниже.
Таблица 5.12 – Таблица возбуждений
Состояния
|
Входные сигналы |
|
Q 1 Q 2 |
х = 0 |
х = 1 |
0 0 |
0 1 |
0 0 |
0 1 |
0 0 |
0 1 |
1 0 |
1 0 |
0 1 |
|
Т 1 Т 2 |
Т 1 Т 2 |
Полученная таблица может быть интерпретирована как таблица
истинности. Поэтому, используя карты Карно, получим Т1 и Т2.
Таблица 5.13 – Карта Карно для Т 1
х \ Q 1Q 2 |
00 |
01 |
11 |
10 |
0 |
0 |
0 |
- |
1 |
1 |
0 |
0 |
- |
0 |
T
1
= Q
1
Таблица 5.14 – Карта Карно для Т 2
х \ Q 1Q 2 |
00 |
01 |
11 |
10 |
0 |
1 |
0 |
- |
0 |
1 |
0 |
1 |
- |
1 |
T 2 = Q 2 x Q 1 x 1 2
Получение булевых функций выходов проще и может быть сделано непосредственно по таблице выходов автомата. Уравнения булевых функций выходов автомата зависят от типа используемых элементов памяти, а зависят только от их количества.
Таблица 5.15 – Таблица выходов
Состояния
|
Входные сигналы |
|
Q 1 Q 2 |
х = 0 |
х = 1 |
0 0 |
0 0 |
1 0 |
0 1 |
0 1 |
1 1 |
1 0 |
0 0 |
0 1 |
Таблица 5.16 – Карта Карно для у 1
х \ Q 1Q 2 |
00 |
01 |
11 |
10 |
0 |
0 |
0 |
- |
0 |
1 |
1 |
1 |
- |
0 |
у 1 = 1 х
Таблица 5.17 – Карта Карно для у 2
х \ Q 1Q 2 |
00 |
01 |
11 |
10 |
0 |
0 |
1 |
- |
0 |
1 |
1 |
1 |
- |
1 |
у 2 = Q 2 Q 1 х
Если синтезируемый автомат является автоматом Мура, то постро- ение булевых функций осуществляется также.