Эвристический алгоритм состоит из следующих шагов

УЛМ

x2	x1	x0	y

Составить таблицу истинности (начальное значение выходов тригерров равно 0)

x3	x2	x1	x0	Q⁰_JK	Q⁰_T	y0	y1

Гонки комбинационных схемах.

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

Борьба с гонками.

Существует три наиболее часто встречающихся способа борьбы с гонками:

- Синхронизация структурного автомата

- Учет минимального времени задержки распространения сигнала

- Построение противогоночных схем

- Направленное кодирование состояний абстрактного автомата

Кодирование внутренних состояний ЦА

Кодирование заключается в сопоставлении каждому состоянию автомата набора (кода) состояний элементов памяти.

010 -> 100

T1: 0 -> 1

T2: 1 -> 0

T3: 3 -> 0

Гонки в автомате

- некритическими

- критическими состязаниями

Соседнее кодирование

- в графе автомата не должно быть циклов с нечетным числом вершин;

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


a₁	a₂	a₃	a₇
a₆		a₄	a₅

a₁ ~ 000

a₂ ~ 010

a₃ ~ 110

a₄ ~ 111

a₅ ~ 101

a₆ ~ 001

a₇ ~ 100

Кодирование состояний

- алгоритм кодирования для D-триггеров;

- эвристический алгоритм кодирования.

Алгоритм кодирования для D-триггеров

- Каждому состоянию автомата а_m (m = 1,2,...,M) ставится в соответствие целое число N_m, равное числу переходов в состояние а_m (N_m равно числу появлений а_m в поле таблицы переходов или числу дуг, входящих в а_m при графическом способе задания автомата).

- Числа N₁, N₂, ..., N_m упорядочиваются по убыванию.

- Состояние а_s с наибольшим N_s кодируется кодом: , где R-количество элементов памяти.

- Следующие R состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00.

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

a₁

a₂

a₃

a₄

a₅

a₁

a₂

a₃

a₄

a₅

Z₁

a₁

a₅

a₃

a₁

Z₁

w₁

w₂

w₁

Z₂

a₂

a₃

a₂

a₃

Z₂

w₁

w₃

w₄

w₂

Z₃

a₃

a₄

a₂

a₄

a₂

Z₃

w₂

w₁

w₃

a₁~ N₁= 3 N₃ a₃= 000

a₂~ N₂= 4 N₂ a₂= 001

a₃~ N₃= 5 N₁ a₁= 010

a₄~ N₄= 5 N₄ a₄= 100

a₅~ N₅= 1 N₅ a₅= 011

w₁~ N₁= 6 N₁ w₁ = 00

w₂~ N₂= 5 N₂ w₂ = 01

w₃~ N₃= 2 N₃ w₃ = 10

w₄~ N₄= 2 N₄ w₄ = 11

Эвристический алгоритм кодирования

определения

- Вершины графа отождествляются с состояниями автомата

- Вершины i и j соединены ребром, если есть переход из а_i и а_j или наоборот

- q(i, j) - число всевозможных переходов автомата из а_i в а_j

- вес ребра р(i, j) = q(i, j) + q(j, i)

- w(i, j) = р(i, j)× d(i, j) , где d(i, j) – число компонентов, которыми коды состояний а_i в а_j отличаются друг от друга

	a₁	a₂	a₃	a₄	a₅
Z₁	a₁	a₁	a₅	a₃	a₁
Z₂	a₂	a₃	a₂	a₃	a₃
Z₃	a₃	a₄	a₂	a₄	a₂

Эвристический алгоритм состоит из следующих шагов

1.Строим матрицу , состоящую из всех пар номеров (i, j), для которых р(i, j) ¹ 0 и i<j. Для каждой пары в матрице указываем ее вес р(i, j), совпадающий с весом ребра соединяющего а_i и а_j.

		i	j	p(i,j)


T	=

2.Упорядочим строки матрицы , для чего построим матрицу следующим образом. В первую строку матрицы поместим пару (a,b) с наибольшим весом р(a,b). В нашем случае (a,b) = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с парой (a,b) выбирается пара (g,d) с наибольшим весом и заносится во вторую строку матрицы . Ясно, что {a,b}×{g,d}¹0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д..

В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(a) компонента a называется число появлений a в матрице ) и в матрицу заносится пара с наибольшей суммой весов.

(2,3) с p(2,3)=3;

(1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2, (3,5) с р(3,5) = 2;

р(1) = 3 р(2) = 3 р(1) + р(2) = 6

р(3) = 4 р(4) = 2 р(3) + р(4) = 6

р(3) = 4 р(5) = 2 р(3) + р(5) = 6

		i	j	p(i,j)


M	=

3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда

R = log₂M = log₂5 =3

Закодируем состояния из первой строки матрицы следующим образом: K₂ = K(а₂) = 000; K₃ = K(а₃) = 001.

Для удобства кодирования будем иллюстрировать этот процесс картой Карно:

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

		i	j	p(i,j)


M’	=

5.В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его g. (В нашем случае g = 1).

6.Строим матрицу , выбрав из строчки, содержащие g.

				i	j	p(i,j)

M_g	=	M’	=

Пусть B_g = {g₁,...,g_F} – множество элементов из матрицы , которые уже закодированы. Их коды К_g₁,..., K_g_F соответственно. В нашем случае:

B_g = B₃ = {2,3} K₂ = 000 K₃ = 001.

7.Для каждого K_g _f (f=1, ..., F) найдем – множество кодов, соседних с и еще не занятых для кодирования состояний автомата. (Для соседних кодов кодовое расстояние d=1).

K₂ = 000 = {100, 010}

K₃ = 001 = {011, 101}.

Построим множество

Если оказывается, что , то строим новое множество , где – множество кодов, у которых кодовое расстояние до кода равно 2 и т.д..

8.Для каждого кода из множества D_g находим кодовое расстояние до кода .

K₂ = 000 K₃ = 001

d(100, 000) = 1 d(100, 001) = 2

d(010, 000) = 1 d(010, 001) = 2

d(011, 000) = 2 d(011, 001) = 1

d(101, 000) = 2 d(100, 001) = 1

9.Находим значение функции w для каждого кода из множества D_g.

10.Из множества D_g выбираем код K_g, у которого получилось минимальное значение w в п.9. Выбираем код для состояния a₁ К₁=100.

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