Сравнительный анализ результатов кодирования

Кодирование близкое к соседнему

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

Для наглядного представления построим граф связей состояний автомата. На ребрах графа указано количество связей.

Рисунок 4.1.1 – Граф связей состояний автомата

Для данного варианта один из лучших способов кодирования близкого к соседнему выглядит следующим образом:

Таблица 4.1.2 – Таблица кодирования

S₀ S₁ S­­₂ S₄ S₅ S₃ X S₆

Рисунок 4.1.3 – Кодированная таблица переходов и выходов

Рисунок 4.1.4 – Выходные функции y₁, y₂

Рисунок 4.1.5 – Матрицы представления функций z₁, z₂, z₃

Z ₁ = входов

Z ₂ = входов

Z ₃ = входов

Y ₁ = входа

Y ₂ = входа

Суммарное число входов: 15 + 20 + 17 + 2 + 4 = 58.

Кодирование по критерию желательности соседства

Для осуществления данного кодирования строится т. наз. матрицы желательности соседства по 3 критериям:

1. По входным переменным: если в таблице переходов соседние по входным наборам элементы содержат состояния S_i и S_j, то элемент матрицы увеличивается на единицу.

2. По состоянию перехода: если в таблице переходов при одном входном наборе в состояниях S_i и S_j следующее состояние одно и то же, то элемент матрицы увеличивается на единицу.

3. По выходным переменным: если выходные наборы в состояниях S_i и S_j имеют r одинаковых компонент, то элемент увеличивается на r/k, где k - число внутренних переменных, k= , n- число состояний.

Кодирование состояний на основе матриц степени желательности соседства состоит в том, что состояния, имеющие наибольшее значение размещаются на соседних элементах булева пространства (кодируются соседними кодами). Затем к уже размещённым состояниям подбирается очередное новое, исходя из наибольшей суммарной степени желательности соседства.

Кодирование выполняется в два этапа:

1) Размещение на матричной форме n-переменных в соответствии с матрицей.

2) Вращение булева пространства с тем, чтобы наиболее часто встречающийся код был закодирован набором «000».

Построим матрицы желательности соседства для автомата:

А. По входным переменным:

Nbsp; | S0   |

Nbsp;   S1     | ||     S2       |     S3         || S4           | S5 B. По состоянию перехода: S1 S2 S3 S4 S5 S6   | |   || | | S0   |   | | || S1       | || | S2           | S3         | | S4           | S5 C. По выходным переменным: k = = 3, r = 2 S1 S2 S3 S4 S5 S6   2/3 2/3 1/3 1/3 1/3 1/3 S0   2/3 1/3 1/3 1/3 1/3 S1     1/3 1/3 1/3 1/3 S2             S3         2/3 2/3 S4           2/3 S5   D. Матрица критерия желательности соседства: S1 S2 S3 S4 S5 S6   1⅔ 1⅔ 2⅓ 5⅓ 1⅓ 2⅓ S0   2⅔ ⅓ 4⅓ 1⅓ 2⅓ S1     1⅓ 3⅓ 2⅓ 1⅓ S2         S3         4⅔ 3⅔ S4           2⅔ S5   Выбираем максимальный элемент в матрице D и в матрице кодирования состояний обеспечиваем соседство состояний, соответствующих данному элементу. Затем в ТПиВ автомата находим рассматриваемую пару состояний и также обеспечиваем соседство состояний. Найдя таковую пару, прибавляем единицу к соответствующему элементу суммарной матрицы требований. В соответствии с полученной матрицей кодируем состояния по матрице критерия желательности соседства: Таблица 4.2.1 – Таблица кодирования   y1 y2 y3 S0 S1 S2 S3 S4 S5 S6   S4 S0 S­­2 S6 S3 X S1 S5 Рисунок 4.2.2 – Кодированная таблица переходов и выходов     Рисунок 4.2.3 – Выходные функции y1, y2   Z3   Рисунок 4.2.4 – Матрицы представления функций z1, z2, z3     Z1 = входов Z2 = входов Z3 = входов Y1 = входа Y2 = входа Суммарное число входов: 18 + 16 + 15 + 2 + 4 = 55.  

Сравнительный анализ результатов кодирования

Схемы характеризуются сложностью и быстродействием. Сложность – это суммарное количество входов. Для того, чтобы построить более простую комбинационную схему, выберем кодирование с наименьшей сложностью. Сравним полученные значения кодирования близкого к соседнему и кодирования по критерию желательности соседства.

– Сложность кодирования близкого к соседнему: S=58

– Сложность кодирования по критерию желательности соседства: S=55

Выберем для синтеза схемы кодирование по критерию желательности соседства, как наиболее выгодное, относительно сложности схемы.