Структурные автоматы (стр. 5 из 6)

С учетом доопределений входных переменных матрицы переходов некоторых стандартных триггеров имеют вид (таб. 28.)

Таблица 28.Матрицы переходов триггеров

Триггер-D			Триггер-Т			Триггер-RS				Триггеp-JK
Q(t)	Q(t+1)	D	Q(t)	Q(t+1)	Т	Q(t)	Q(t+1)	R	S	Q(t)	Q(t+1)	К	J
0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	1	1	0	1	1	0	1	0	1	0	1	0	1
1	0	0	1	0	1	1	0	1	0	1	0	1	0
1	1	1	1	1	0	1	1	0	0	1	1	0	0

5. Кодирование состояний и выходов автомата и сложность комбинационных схем

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

В рассмотренном ранее примере коды состояний автомата принимали значения: a₁=00, a₂=01, а₃=11. Если принять коды: a₁=01, а₂=01, а₃=00, то таблица переходов структурного автомата примет вид (табл. 29).

Если в качестве запоминающего элемента применить D-триггер, то таблица формирования функций возбуждения будет совпадать с данной таблицей. Тогда функции примут вид:

Таблица 29

ZlZ2
a1a2	00	01	10
01	10	00	10
10	-	01	00
00	01	-	00

;

;

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

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

Алгоритм весового метода кодирования:

1. Каждому выходному сигналу у, ставится в соответствие целое число P_i, равное числу появлений сигнала у_i в таблице выходов автомата.

2. Числа P_iсортируются по убыванию.

3. Выходной сигнал y_i с наибольшим весом (P_imax) кодируются кодом, содержащим все 0 (00...00).

4. Следующие L выходных сигналов (где L- число разрядов в двоичном векторе выходного сигнала) по списку убывания веса (см п. 2) кодируются кодами, содержащими одну 1 (00...01, 00...10,... ,10...00).

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

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

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

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

При таком критерии уменьшается сложность схем, реализующих дизъюнкции на входах элементов памяти, т.е. минимизируется комбинационная схема автомата. Для оценки кодирования вводится коэффициент эффективности кодирования:

K_эф= W/P;

где Р - общее количество переходов автомата,

W - весовая функция : W=t_ij

где t_ij- расстояние Хэмминга между кодами состояний а_i и а_j, равное числу элементов памяти, изменяющих свое состояние на данном переходе.

Отметим, что при определении весовой функции суммирование производится по всем переходам автомата. Коэффициент эффективности позволяет оценить сложность комбинационной схемы автомата: чем меньше его значение, тем меньше сложность комбинационной схемы, и оптимальный вариант - K_эф=1.

Алгоритм состоит из следующих шагов:

1. Построить матрицу М, составленную из всех пар номеров (a_r, b_r) переходов автомата.

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

3. Закодируем состояния из первой строки матрицы М следующим образом: Ka₁=00...00, Kb₁=00...01.

4. Вычеркнем из матрицы М первую строку с закодированными состояниями. Получим матрицу М'.

5. В начальной строке матрицы М' закодирован один элемент. Выберем из первой строки матрицы М' незакодированный элемент и обозначим его .

6. Построим матрицу M, выбрав из матрицы М' строки, содержащие у. Пусть В={₁,₂,...,_f,...,_F} - множество элементов из матрицы My, которые уже закодированы. Их коды обозначим через К₁,К₂,...

,К_f,...,К_F соответственно.

7. Для каждого Кg_f (f=1, 2,...,F) найдем C¹_gf- множество кодов, отстоящих от Кg_f на расстояние Хэмминга, равное 1 и еще не занятых для кодирования состояний автомата. Построим множество

.

Если D¹_ =0, то строим новое множество

, где - множество кодов, у которых кодовое расстояние с кодом K_f равно 2. Если и D²_ =0, строим D³_ и т.д., пока не найдем . Пусть .

8. Для каждого К_g находим w_gf=|K_g- K_f|² - расстояние Хэмминга между К_g и всеми используемыми кодами K_f(f=1, 2, ...,F).

9. Находим

10. Из

выбираем К_, у которого W_g=W_gmin. Элемент у кодируем кодом К_.

11. Из матрицы М' вычеркиваем строки, в которых оба элемента закодированы, в результате чего получаем новую матрицу, которую также обозначаем М’. Если в матрице М' не осталось ни одной строки, переходим к п. 12, иначе к п. 5.

12. Вычисляем функцию

где t_ij=|K_j-K_j|².

13. Конец.

Оценкой качества кодирования по рассмотренному алгоритму может служить число K=W/P, где P - число переходов в автомате. Очевидно, что K>=1, причем, чем меньше значение K, тем лучше результат кодирования.

Рассмотрим пример кодирования автомата, заданного таблицей переходов и выходов.

1. Строим матрицу М:

Кодируем первую строку: K₁=00;K₂=01;

2. Вычеркиваем из матрицы М 1-ю строку (1-3) и 6-ю строку (3-1). Получаем матрицу М', в первой строке которой незакодирован элемент 4. Обозначим =4 и запишем матрицу M_,. В матрице M_ закодированы 1 и З: В_={1,3}={00,01}

Находим W:

W₁₀=|00| |10|=3; W₁₁=|00| |11|=3;

|10|+|01| |11|+|01|

Выбираем K₄=10.

Вычеркнем из М' строку (1-4). Получим новую матрицу М', в первой строке которой не закодирован элемент 2. Обозначим g=2 и запишем матрицу М₂. В матрице М₂ закодированы элементы 3, 4:

Вg={3,4}={01,10}

Вычислим K=W/P=9/8=1,125.

6. Обеспечение устойчивости функционирования цифровых автоматов. Гонки в автоматах

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

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

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

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