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

ПТЦА - Прикладная теория цифровых автоматов
113094
знака
120
таблиц
81
изображение

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

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

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

В частности, для автомата, заданного своими таблицами переходов и выходов (см. ниже) при кодировании на базе D-триггеров.

a1

a2

a3

a4

a5

a1

a2

a3

a4

a5

Z1

a1

a1

a5

a3

a1

Z1

w1

w2

w1

w1

w1

Z2

a2

a3

a2

a3

a3

Z2

w1

w3

w4

w2

w2

Z3

a3

a4

a2

a4

a2

Z3

w2

w2

w2

w1

w3


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

Аналогично кодированию внутренних состояний для D-триггеров можно кодировать выходные сигналы для любого типа триггеров, т.е. чем чаще вырабатывается данный выходной сигнал wi, тем меньше единиц в его коде. Так для автомата (рис.41.) имеем:

w1 ~ N1 = 6 N1 w1 = 00

w2 ~ N2 = 5 N2 w2 = 01

w3 ~ N3 = 2 N3 w3 = 10

w4 ~ N4 = 2 N4 w4 = 11

Предполагается самостоятельно окончить синтез автомата при данном кодировании и при любом другом. Результаты сравнить.

 

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

Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.

Введем некоторые определения.

Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из аi и аj или наоборот.

Обозначим q(i, j) число всевозможных переходов автомата из аi в аj. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).

Введем функцию w(i, j) = р(i, j)× d(i, j), где d(i, j) – число компонентов, которыми коды состояний аi в аj отличаются друг от друга (т.е. кодовое расстояние между кодами аi в аj).

Функция w(i ,j) имеет простой физический смысл. Перход автомата из аi в аj (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям аi и аj (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)×d(i ,j) =w(i ,j).

Но тогда функция показывает, сколько всего переключается триггеров при прохождении автомата по всем возможным переходам. Функция w показывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. W можно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным , т.е. суммарному числу переходов для автомата.

Из выражения для w следует, что переход из аi в аi, для которого d(i,i)=0, не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).

Рассмотрим применение эвристического алгоритма на конкретном примере автомата, заданного таблицами переходов и выходов (рис.41. ). Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рис.42. На каждом ребре указан его вес.

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

1. Строим матрицу , состоящую из всех пар номеров (i, j), для которых р(i, j) ¹ 0 (т.е. в автомате есть переход из аi в аj или наоборот) и i<j. Для каждой пары в матрице  указываем ее вес р(i, j), совпадающий с весом ребра соединяющего аi и аj.

i

j

p(i,j)

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. Упорядочим строки матрицы , для чего построим матрицу  следующим образом. В первую строку матрицы  поместим пару (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) претендуют пары: (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

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

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

Информация о работе «ПТЦА - Прикладная теория цифровых автоматов»
Раздел: Разное
Количество знаков с пробелами: 113094
Количество таблиц: 120
Количество изображений: 81

Похожие работы

Скачать
66716
0
0

... (пе- редний фронт) сигнала, то используется элемент ИЛИ. (Первый перепад сигнала синхронизации в новом такте не должен быть рабочим.)  _ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА При проектировании вычислительного устройства основными являются ограничения на:  1)- время вычисления;  2)- объем аппаратуры, реализующей вычисления;  3)- тип применяемых базовых функций.  ОПТИМИЗАЦИЯ ...

Скачать
31451
6
0

... если Да то на E07(Л2), иначе на C04(Л2). E07(Л2) Выводим частное, т.е. Z:=Рг.В. F07(Л2) Конец. 1.6 Описание моделирующей программы (Приложение В) Программа операции деления без восстановления остатка со сдвигом остатка с фиксированной точкой в коде 8421, 8421+6 выполнена на языке программирования ассемблера. В моделирующей программе регистрами Рг.А, Рг.В, Рг.К, а так же ...

0 комментариев


Наверх