Эвристический алгоритм состоит из следующих шагов
УЛМ
Составить таблицу истинности (начальное значение выходов тригерров равно 0)
Гонки комбинационных схемах. Инерционность элементов и наличие различных факторов, приводящих к задержке распространения сигнала, приводят к задержке появления выходных сигналов КУ, т.е. сигналы на выходе КУ, соответствующие новому состоянию входных сигналов, появляются не сразу, а с некоторой задержкой.
Борьба с гонками.
Существует три наиболее часто встречающихся способа борьбы с гонками: - Синхронизация структурного автомата - Учет минимального времени задержки распространения сигнала - Построение противогоночных схем
- Направленное кодирование состояний абстрактного автомата
Кодирование внутренних состояний ЦА Кодирование заключается в сопоставлении каждому состоянию автомата набора (кода) состояний элементов памяти.
010 -> 100
T1: 0 -> 1 T2: 1 -> 0 T3: 3 -> 0 Гонки в автомате
- некритическими - критическими состязаниями
Соседнее кодирование
- в графе автомата не должно быть циклов с нечетным числом вершин; - два соседних состояния второго порядка не должны иметь более двух состояний, лежащих между ними.
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 состояний согласно списка пункта 2 кодируются кодами, содержащими только одну 1: 00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00. - Для оставшихся состояний опять в порядке списка п.2. используют коды с двумя единицами, затем с тремя и так далее пока не будут закодированы все состояния.
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 отличаются друг от друга
Эвристический алгоритм состоит из следующих шагов 1.Строим матрицу
2.Упорядочим строки матрицы
В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(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
3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда
R = log2M = log25 =3
Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001. Для удобства кодирования будем иллюстрировать этот процесс картой Карно:
4.Вычеркнем из матрицы
5.В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его g. (В нашем случае g = 1).
6.Строим матрицу
Пусть Bg = {g1,...,gF} – множество элементов из матрицы
Bg = B3 = {2,3} K2 = 000 K3 = 001.
7.Для каждого Kg f (f=1, ..., F) найдем K2 = 000 K3 = 001 Построим множество
Если оказывается, что
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.Из матрицы
К2 = 000 K3 = 001
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 K2 = 000 К3 = 001
К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- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
|