Читайте также:
|
1. Находим количество элементов памяти 
, (
- число состояний абстрактного автомата) и кодируем состояния абстрактного автомата (табл.5.1).
| Таблица 5.1. | |
am\ 
|
|
| a1 | |
| a2 | |
| … | |
| aM |
2. Кодируем входные и выходные сигналы, то есть
o находим количество входов структурного автомата 
, (
- число входных сигналов абстрактного автомата);
o количество выходов 1 типа 
; (
- число выходных сигналов 1 типа);
o количество выходов 2 типа 
, (
- число выходных сигналов 2 типа) и кодируем входные (табл.5.2) и выходные сигналы (табл.5.3) и (табл.5.4) абстрактного автомата.
| Таблица 5.2. | |||
| z f / x 1 | xL x1x2…x1 | ||
| z | |||
| z | |||
| … | |||
| z | |||
| Таблица 5.3. | |||
| wf/y 1y2…yN | y 1y2…yN | ||
| w1 | |||
| w2 | |||
| … | |||
| wG | |||
o
| Таблица 5.4. | |
| uh/r 1 r2…rD | r 1 r2…rD |
| u1 | |
| u2 | |
| … | |
| uH |
3. Структурный автомат представляем обобщенной схемой (рис.5.6).
Рис. 5.6.
4. Составляем закодированную таблицу выходов автомата и по ней записываем уравнения выходов.
o 
;
o 
;
o...
o 
;
o 
;
o 
;
o...
o 
;
o...
5. Составляем закодированную таблицу переходов автомата и по ней записываем уравнения для функций возбуждения, используя таблицы переходов соответсвующих элементов памяти.
o 
;
o 
;
o...
o 
;
6. Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ}).
3.3. Кодирование состояний и сложность комбинационных схем 
3.3.1. Кодирование состояний и КС
Вспомним синтез автомата на линиях задержки, таблица переходов которого Т. 4.
В таблице Т. 15 состояние автомата кодируется так: к(а1) = 00, к(а2) = 01, к(а3) = 11.
В результате синтеза, функция возбуждения имеет такой вид:
Будем кодировать состояния автомата так: к(а1) = 01, к(а2) = 10, к(а3) = 00. Таблица переходов Т. 3-11 будет такой:
Так как таблица функции возбуждения при синтезе на линиях задержки совпадает с таблицей переходов, непосредственно с таблицей Т. 3-11, имеют такие функции возбуждения.
Рассмотрим алгоритм, который используется при кодировании состояний и позволяет упростить функции возбуждения:
1) каждому состоянию 
ставим в соответствие число Nm равное числу переходов в это состояние, или равное числу ветвей, входящих в это состояние на графе;
2) числа N1, N2,…,NM сортируются по убыванию;
3) состояние аt c наибольшим Nt кодируется кодом 0000…0;
4) следующие I-состояний (I - число элементов памяти) кодируется кодами с одной "1": (00..01), (00..10),…,(10...00);
5) следующие I-состояний из оставшихся кодируются кодами содержащие две "1".
В результате получаем такое кодирование, при котором чем больше переходов в некоторое состояние, тем меньше единиц содержит код этого состояния.
3.3.2. Кодирование выходных сигналов и КС
Аналогичные соображения могут быть использованы и при кодировании выходных сигналов для минимизации функции выходов. Вспомним таблицу выходов абстрактного С-автомата Т.5.
Упорядочим выходные сигналы автомата по частоте их появления в таблице графа.
w3 - 3 раза
w2 - 2 раза
w1 - 1 раз
w4 - 1 раз
U1 - 2 раза
U2 - 1 раз
Закодируем выходной сигнал первого и второго рода Т. 3-12, Т. 3-13.
Таблица выходов теперь будет такой:
Непосредственно из таблицы Т. 3-14 получаем выражение для функции выходов:
3.3.3. Оценка сложности КС
Введем весовую функцию
- расстояние между кодами состояний аm и as, равное числу элементов, которые изменяют свое значение при переходе из состояния аm в as.
Функция W, сумма произведений по всем возможным переходам, и служит оценкой сложности КС. Чем меньше значение функции, тем проще КС.
Рассмотрим один из самых распространенных алгоритмов:
1) строится матрица-столбец
состоящая из всех различных пар номеров, так что в автомате есть переход из 
r в 
r;
2) упорядочить строки в матрице так, чтобы выполнялось условие
.
Это означает, что хотя бы один из элементов r-строки содержится в какой-нибудь из предыдущих строк. Для связных графов это всегда возможно;
3) закодируем состояние из 1 строки матрицы М таким образом, что
4) вычеркиваем из М одну строку, соответствующую закодированным состояниям a1, b1
5) в силу условия пункта 2 в 1 строке новой матрицы М1 оказывается закодированным 1 элемент. Другой незакодированный элемент обозначим через 
;
6) выбрав из матрицы М1 все строки, содержащие , построим матрицу М . В этой матрице выберем множество элементов В = ( f), 
f = 1,.., F, которые уже закодированы. Их обозначим k 1, k 2, …, k f;
7) для каждого k f (f = 1, …, F) находится множество кодов соседних с k f и еще не занятых для кодирования состояния автомата. Это множество
.
Может оказаться, что
где c f это множество кодов, у которых кодовое расстояние с кодом k f равно 2. Если и это
делаем дальше
пока не найдется
.
Обозначим
.
8) для каждого кода k 
g находим кодовое расстояние между этим кодом и всеми используемыми кодами k f
.
9) находим
Если в автомате имеются переходы из 1 состояния в другое и обратно, вес перехода входит в Wgдважды.
10) из множества Dn выбираем код k , у которого вес Wg = min Wg. Состояние a кодируется кодом k .
11) из матрицы М1 вычеркиваем строки, где закодированы оба элемента. Получаем М2. Если в ней не осталось ни одной строчки, то переходим к пункту 12, иначе - к 5.
12) вычисляем функцию
.
Оценкой качества кодирования служит число
,
где Р - число переходов. Значение kк лежит в пределах [1 - I], чем ближе к 1, тем лучше автомат.
3.3.4. Пример кодирования состояний автомата
Рассмотрим автомат представленный графом
Дугам графа входные и выходные сигналы не приписываются, т.к. они в работе алгоритма кодирования состояния не участвуют.
Строим матрицу М.
Кодируем первую строчку: k1 = 000, k2 = 001. Расположим эти коды в карте Карно.
Из матрицы вычеркиваем первую строчку и получаем матрицу М1.
В первой строке М1 не закодирован элемент = 4. Собираем матрицу из этих элементов.
В М4 уже закодирован элемент "2", ==> множество В4 = (2). Для элемента "2" с кодом 001 строим множество С12, которое получаем инвертируя элементы этого множества.
С12 = (101, 011).
С12 объединяем (если их несколько) и получаем объединение D14 = (101, 011). Находим весовые функции элементов с исходными кодами
Для элемента а4 можно взять любой из этих кодов, так как оба они равны единице. Возьмем код k4 = 101. Заносим его в карту Карно
В М1 удаляем 1 строку и получаем М2
В первой строке М2 не закодированным оказывается элемент = 5. Собираем матрицу М5
Множество В5 = (2, 4, 1). Коды этих элементов: "2" - 001, "4" - 101, "1" - 000.
Неиспользуемые смежные коды будут:
Находим весовые функции:
Надо взять число, которое дает минимальное расстояние: W100 = min (W011, W100, W111, W010).
Этим кодом и будет закодирован элемент а5 - k5 = 100.
В М2 удаляем 1 строчку и все строки, в которых элементы уже закодированы
= 3 - незакодирован. Матрица, состоящая из строчек с незакодированными элементами совпадает с матрицей М3.
Весовые функции:
k3 = 100
Все состояния оказываются закодированными.
Весовая функция всего автомата:
Число переходов самого автомата равно 8 (Р = 8).
Коэффициент качества кодирования:
Дата добавления: 2015-12-08; просмотров: 30 | Нарушение авторских прав