Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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

УЛМ

x2 x1 x0 y
       
       
       
       
       
       
       
       

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

 

x3 x2 x1 x0 Q0JK Q0T y0 y1
               
               
               

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

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

 


 

 



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

 

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

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

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

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

 

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

   

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

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

 

010 -> 100

 

T1: 0 -> 1

T2: 1 -> 0

T3: 3 -> 0


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

 

 

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

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

 

 

 


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

 

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

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

 


 

         
  a 1 a 2 a 3 a 7
  a 6   a 4 a 5

 

a 1 ~ 000

a 2 ~ 010

a 3 ~ 110

a 4 ~ 111

a 5 ~ 101

a 6 ~ 001

a 7 ~ 100


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

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

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

 


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

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

- Числа N 1, N 2,..., N m упорядочиваются по убыванию.

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

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

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


 

  a 1 a 2 a 3 a 4 a 5     a 1 a 2 a 3 a 4 a 5
Z 1 a 1 a 1 a 5 a 3 a 1   Z 1 w 1 w 2 w 1 w 1 w 1
Z 2 a 2 a 3 a 2 a 3 a 3   Z 2 w 1 w 3 w 4 w 2 w 2
Z 3 a 3 a 4 a 2 a 4 a 2   Z 3 w 2 w 2 w 2 w 1 w 3

 

a 1 ~ N 1 = 3 N 3 a 3 = 000

a 2 ~ N 2 = 4 N 2 a 2 = 001

a 3 ~ N 3 = 5 N 1 a 1 = 010

a 4 ~ N 4 = 5 N 4 a 4 = 100

a 5 ~ N 5 = 1 N 5 a 5 = 011

 

 

w 1 ~ N 1 = 6 N 1 w 1 = 00

w 2 ~ N 2 = 5 N 2 w 2 = 01

w 3 ~ N 3 = 2 N 3 w 3 = 10

w 4 ~ N 4 = 2 N 4 w 4 = 11


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

определения

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

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

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

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

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


  a 1 a 2 a 3 a 4 a 5  
Z 1 a 1 a 1 a 5 a 3 a 1  
Z 2 a 2 a 3 a 2 a 3 a 3  
Z 3 a 3 a 4 a 2 a 4 a 2  

 

 


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

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

 

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

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

 

 


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

 

    i j p(i,j)
         
         
M’ =      
         
         
         
         

 

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

 


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

 

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

 

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

 

Bg = B 3 = {2,3} K 2 = 000 K 3 = 001.

 

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

K 2 = 000 = {100, 010}

K 3 = 001 = {011, 101}.


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

 

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

 

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

 

K 2 = 000 K 3 = 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. Выбираем код для состояния a 1 К 1 =100.

 


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

 

    i j p(i,j)
         
         
M’ =      
         
         

 

К 2 = 000 = {010}

K 3 = 001 = {011, 101}

 

 


K 2 = 000 K 3 = 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}

K 2 = 000 = {010}

К 3 = 001 = {011}

 

 

К 1 = 100 K 2 = 000 K 3 = 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 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...