Главная | Обратная связь
МегаЛекции

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




УЛМ

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

 

a1 ~ 000

a2 ~ 010

a3 ~ 110

a4 ~ 111

a5 ~ 101

a6 ~ 001

a7 ~ 100


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

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

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

 


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

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

- Числа N1, N2, ..., Nm упорядочиваются по убыванию.

- Состояние аs с наибольшим Ns кодируется кодом: , где 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

 

a1 ~ N1 = 3 N3 a3 = 000

a2 ~ N2 = 4 N2 a2 = 001

a3 ~ N3 = 5 N1 a1 = 010

a4 ~ N4 = 5 N4 a4 = 100

a5 ~ N5 = 1 N5 a5 = 011

 

 

w1 ~ N1 = 6 N1 w1 = 00

w2 ~ N2 = 5 N2 w2 = 01

w3 ~ N3 = 2 N3 w3 = 10

w4 ~ N4 = 2 N4 w4 = 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 = log2M = log25 =3

 

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

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

 

 


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

 

    i j p(i,j)
   
   
M’ =
   
   
   
   

 

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

 


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

 

        i j p(i,j)
       
Mg = M’ =
       

 

Пусть Bg = {g1,...,gF} – множество элементов из матрицы , которые уже закодированы. Их коды Кg1,..., KgF соответственно. В нашем случае:

 

Bg = B3 = {2,3} K2 = 000 K3 = 001.

 

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

K2 = 000 = {100, 010}

K3 = 001 = {011, 101}.


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

 

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

 

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

 

K2 = 000 K3 = 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 для каждого кода из множества Dg.

 

 

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

 


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

 

    i j p(i,j)
   
   
M’ =
   
   

 

К2 = 000 = {010}

K3 = 001 = {011, 101}

 

 


K2 = 000 K3 = 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

 

 

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

 

 


 

 

К1 = 100 = {110}

K2 = 000 = {010}

К3 = 001 = {011}

 

 

К1 = 100 K2 = 000 K3 = 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

 

 

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

 

 

 

 

 





©2015- 2017 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов.