Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

| |00 |01 |11 |10 |
|00 |00 |11 |01 |– |
|01 |– |10 |11 |– |
|11 |01 |– |10 |01 |

|0 |0 |X |0 |
|0 |1 |0 |1 |
|1 |0 |1 |0 |
|1 |1 |0 |X |

| |00 |01 |11 |10 |
|0 |0 |0 |X |
|0 |1 |1 |X |
|1 |0 |X |1 |
|1 |1 |X |0 |

| |00 |01 |11 |10 |
| | |1|2|2 |
| | |1|3|1 |
|T |=|1|5|1 |
| | |2|3|3 |
| | |2|4|1 |
| | |2|5|1 |
| | |3|4|2 |
| | |3|5|2 |

2. Упорядочим строки матрицы [pic], для чего построим матрицу [pic] следующим образом. В первую строку матрицы [pic] поместим пару ((,() с наибольшим весом р((,(). В нашем случае ((,() = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с парой ((,() выбирается пара ((,() с наибольшим весом и заносится во вторую строку матрицы [pic]. Ясно, что
{(,(}({(,(}(0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу [pic] пар выбирается пара с наибольшим весом и заносится в матрицу [pic] и т.д.. В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р(() компонента ( называется число появлений ( в матрице [pic]) и в матрицу [pic] заносится пара с наибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары: (1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2,
(3,5) с р(3,5) = 2.

Для определения того, какая пара займет второе место в матрице [pic] находим веса компонентов пар: р(1) = 3 р(2) = 3 р(1) + р(2) = 6 р(3) = 4 р(4) = 2 р(3) + р(4) = 6 р(3) = 4 р(5) = 2 р(3) + р(5) = 6

В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы [pic] может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всех пар, получим матрицу [pic] в виде:
| | |i|j|p(i|
| | | | |,j)|
| | |2|3|3 |
| | |1|2|2 |
|M |=|3|4|2 |
| | |3|5|2 |
| | |1|3|1 |
| | |1|5|1 |
| | |2|4|1 |
| | |2|5|1 |

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

R = ]log2M[ = ]log25[ =3.

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

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

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

| | |i|j|p(i|
| | | | |,j)|
| | |1|2|2 |
| | |3|4|2 |
|M’|=|3|5|2 |
| | |1|3|1 |
| | |1|5|1 |
| | |2|4|1 |
| | |2|5|1 |

5. В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его
(. (В нашем случае ( = 1).
6. Строим матрицу [pic], выбрав из [pic] строчки, содержащие (.

| | | | |i|j|p(i|
| | | | | | |,j)|
| | | | |1|2|2 |
|M(|=|M’|=|1|3|1 |
| | | | |1|5|1 |

Пусть B( = {(1,...,(F} – множество элементов из матрицы [pic], которые уже закодированы. Их коды К(1,..., K(F соответственно. В нашем случае:

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

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

K2 = 000 [pic] = {100, 010}

K3 = 001 [pic] = {011, 101}.

Построим множество [pic]
[pic]
Если оказывается, что [pic], то строим новое множество [pic], где [pic]– множество кодов, у которых кодовое расстояние до кода [pic]равно 2 и т.д..
8. Для каждого кода из множества D( находим кодовое расстояние до кода
[pic].

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 для каждого кода из множества D(.

[pic]

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

Рекомендуем скачать другие рефераты по теме: реферат на тему искусство, бесплатные тесты.





Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата