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

УЛМ

x2	x1	x0	y

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

 

x3	x2	x1	x0	Q0JK	Q0T	y0	y1

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

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

 

 

 

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

 

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

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

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

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

 

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

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

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

 

010 -> 100

 

T1: 0 -> 1

T2: 1 -> 0

T3: 3 -> 0

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

 

 

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

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

 

 

 

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

 

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

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

 

 

	a1	a2	a3	a7
	a6		a4	a5

 

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. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.

 

a1

a2

a3

a4

a5

a1

a2

a3

a4

a5

Z1

a1

a1

a5

a3

a1

Z1

w1

w2

w1

w1

w1

Z2

a2

a3

a2

a3

a3

Z2

w1

w3

w4

w2

w2

Z3

a3

a4

a2

a4

a2

Z3

w2

w2

w2

w1

w3

 

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 отличаются друг от друга

	a1	a2	a3	a4	a5
Z1	a1	a1	a5	a3	a1
Z2	a2	a3	a2	a3	a3
Z3	a3	a4	a2	a4	a2

 

 

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

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)
Mg	=	M’	=

 

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

 

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. В нашем случае имеем:

 

		i	j	p(i,j)
M’	=

 

К₂ = 000 = {010}

K₃ = 001 = {011, 101}

 

 

K₂ = 000 K₃ = 001

 

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

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

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

 

 

Выбираем К₄ = 101.

 

 

 

 

К₁ = 100 = {110}

K₂ = 000 = {010}

К₃ = 001 = {011}

 

 

К₁ = 100 K₂ = 000 K₃ = 001

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

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

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

 

 

Выбираем К₅ = 011.

 

 

 

 

 

---

Рекомендуемые страницы:

Воспользуйтесь поиском по сайту: