Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 53
Текст из файла (страница 53)
К сожалению, при кодировании состояний резльных'звтомзтов метод подствнавочных разбиений неприменим, твк квк он не аблздвет свойством подствновочных разбиений. Рассмотрим частотно-матричный метод кодирования состояний. Пусть в результзте вбстрвктнаго синтеза был построен могрзф, определяющий отображение ХЯ+ -+ Я У. После кодироввния получим могрвф, задающий отображение ХК+ -+ Я У, т. е. в первонзчзльнам могрзфе вершины, соответствующие идентификвторзм внутренних состояний Я<, будут заменены полными подграфвми, соответствующими кодам Я; внутренних состояний.
Данный метод кодиравзния можно резлизовзть с помощью следуюшего алгоритма синтеза кадируюшего дереве. 1. Строим двумерную мзтрицу Я = (д;.], каждой строке которой взаимно однозначно соответствует микроопервция или значение входного канала (элементы векторе У или Х), столбцу— внутреннее состояние. 1, если первичный терм, соответствующий т-й строке, входит в каждую пару векторов (Х, У)(Х -+ У), коПб ~ торые взвешивают дуги, исходящие из вершины 1, О в противном случае.
Каждому внутреннему состоянию (столбцу матрицы) взаимно однозначно сопоставляем произвольным образом мвксимзльную вершину синтезируемого кодируюшего дерева. Полагаем Я = ф. 2. По мзтрице Я нзхадим чзстотную мвтрицу отношений Р = фт. ф 3. Вычислим значения производной от модели, зздзннай мзгрицей 4. 4. Выбираем пару внутренних состояний, для которой вычисленное значение производной минимально.
5. Выбранную пару состояний вычеркиваем и ставим ей в соответствие в кодируюшем дереве вершину, являющуюся началом дуг, канцзми которых являются выбранные состояния. Постро'енной вершине взаимно одназнзчно сопастзвляем столбец строящейся матрицы (д„рзвный векторному произведению столбцов матрицы сд, соатветствуюших выбранным вершинам. 6. Проверяем, остзлись или нет нерассмотренные внутренние состояния, для которых вычислялись значения производной. Если дз, та переходим к и. 4, в противном случае — к и. 7.
7. Проверяем, абрвзавзнв ли матрица Я,. Если дв, то полагаем ьвс = Я и переходим к и. 2, в противном случае — к п. 8. 295 0) <010 Рис. 4.22 Я, юЯ! 1 0 1 0 0 0 0 1 0 0 Яз юба 0 0 0 1 О 0 0 0 0 1 Яз обз 0 1 0 0 0 0 1 О О 0 з! зз иг зз ° зз У! У! Уз Я! Яз 1 0 0 1 1 0 0 О 0 0 0 0 0 1 1 0 0 0 0 0 Яз Я! Яз Яе 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 О 0 1 0 1 0 1 0 0 1 0 1 з! и! зз зг зз зз У! р! Уз Уз Г,= 0 3 0 Часхотная метрика отношений щнй внл! Я! Яз 3 О 0 2 0 2 1 1 3 0 0 0 Я! Я! Яз. Я! Яз Яе 0 1 3 2 1 0 $2 1 2 4 1 1 1 5 1 2 0 294 Гл. 4. Теорил узормалъкых грамматик и автоматов 8. Каждым двум дугам, исходящим из вершины построенного дерева, начиная с дуг, исходящих из корня дерева, ставим в соотвехствие О и 1.
Путь, соединяющий корень дерева и максимальный элемент, взвешен кодом, который сопоставляется внутреннему состоянию, соответствующему этому максимальному элементу дерева. 9. Конец. Проиллюстрируем предлагаемый алгоритм на следующем примере. Пример 4.2. Пусхь в реаульхахе абстрактного синтеза был получен граф переходов 1) (рис. 4.22, а). Искользуя вредлагаемый алгоритм, аакодируем внутренние сосхояния авто- маха. Махрида С), соответствующая данному графу, имеет следующий вид.
соотвехсхвуюшая метрике !9, имеет следую- Я! Яз Яз $4.5. Кодирование внутренних состолкиб Вычисляем значения лроизводной для каидой пары состояний: дС~ У! — 2Ум+ У! 3 — 2. 1+4 — (Я! Я!)— дЯ ' УД! — — 5, 1 д~б 3 2 3+$ — (Яз, Яз) = = О,б7, ОЯ ' 3 дсг™ 2 — 2 2+ 5 — (Яз, Яз) = = 1,5, дЯ ' 2 дС~ 2 — 2 1+4 — (Яз, Я!)= =4, аЯ дам $ — 2 ° 2+ 4 — (Яз, Я!) = = 2,5, ЯЯ ' 2 ОО™ $2 1+$ — (Яз, Яз) = = 3, дЯ ' 1 дсз~ 5 — 2 ° 1+ 2 — (Яз, Яе) = аЯ дб~ 4 — 2 1+5 — (Я„Я,) ю ' =7, дЯ ' 1 д~м 4 2 2+2 — (Яз, Яз) = = 1.
аЯ Остальные значения кроивводной равны со. Производная(дг ' /дЯ)(Яс, Я,) м имеет минимальное значение на каре (Яг, Яз). Этой паре состояний схавим в соответствие "пересечение" соответствующих вершин строящегося дерева. Согласно алгоритму обьедиияем в нары сосхояния Яг, Яз и Я», Яз. В результате построим следующий ярус дерева. Махрнла 1„)„соответствующая вершинам достроенного яруса, имеет вид Частотная матрика отношений, соответствующая метрике Ц„имеет слелую- Значения нроиаводиой рваны оо. Искомое кодирующе дерево изобраиеио на рнс. 4.22, б. Вавешнваем исходящие из кендой вершины дуги 0 и 1. Согласно настроенному кодирующему дереву имеем следующие коды внутренних состояний авхомата: Я! — 010, Яз— 100, Яз — 101, Я! — 110, Яз — 011, Яв — 111.
296 Гл.4. Теорил формальнмх грамматик и автомотое Рассмотрим кодирование внутренних состояний автомата, исходя из удовлетворения требований надежности. Функционира. ванне автомата может нарушаться в резулыате неодинаковой задержки в реальной схеме, реализующей автомат из-за явления гонок, сущность которого можно проиллюстрировать на следующем примере (рис. 4.23). Пусть в рассматриваемый момент переключаются два триггера, А и В (событийное условие), причем функция возбуждения ~р одного из триггеров, например, В, содержит в качестве одной из переменных значение триггера А: сон = у(..., х+, ...) (функ- в циональнае условие); время задержки в 1 схемах возбуждения триггеров А н В 1 А определяется неравенством сьнА ) 24 1 (г.ьиА — время, в течение которого необходимо наличие "старого" значения триггера А в схеме возбуждения триггера В; ь, ге — время задержки сигнала возбуждения триггера А) (временное условие).
1 т 1 1 Прн выполнении этих трех условий значение т иггера будет вычислено нет правильно (так как для правильного вычисления значения триггера В необходимо, чтобы триггер А сохранял свое Рнс. 4.23 "староев значение по крайней мере в те- чение времени Ът (после начала перехода автомата), а триггер А аобновляетв свое значение через т). Это— так называемое воление гонок. Прн наличии гонок автомат переходит не в то состояние, которое указано при данном переходе, что приводит к нарушению автоматного соответствия. Гонки можно устранить, нарушив одно из трех условий гонок. Для тога чтобы нарушить временное условие, т.
е. чтобы выполнялась неравенство Ьид < Ьд, необходимо иметь схемы возбуждения триггеров А и В для определения Ьйд и Ьд. Эти схемы будут получены только на этапе структурного синтеза, для проведения которого необходимы резулыаты кодирования внутренних состояний. Следовательно, прн логическом устранении гонок нарушение этого условия неосуществимо. Технически третье условие можно нарушить, вводя второй каскад элементов обратной связи или с помощью синхронного выполнения схемы автомата.
Второе условие наличия гонок, т.е. условие ~рн = ~р(..., х~+,...), можно нарушить функциональным развязыванием элементов памяти, например применяя подстановочные разбиения. Первое условие (переключение двух и более элементов памяти прк одном переходе автомата) нарушается, если при любом переходе автомата переключается только один элемент памяти. Это означает: каждому внутреннему состоянию автомата сопоставляет- 2 4.5. Кодирование внутренних состолниб 297 ся такой код, чта если существует переход из состояния 51 в состояние 5 (Яг ~ 5.), то соответствующие им коды отличаются только в одном разряде.
Другими славами, при реализации автомата гонки отсутствуют, если соответствующий граф переходов можно расположить в к-мерном гиперкубе так, чтобы переходы из состояния 21 в состояние я (51 ~ь я ) осуществлялись только по ребрам гиперкуба и коды соответствующих вершин гиперкуба были сопоставлены вершинам графа переходов. Такое кодирование называется соседним.
Будем говорить, чта для графа переходов возможно соседнее кодирование кодами длины н, если ан вложим в и-мерный куб. Приведем условие вложимости графа переходов в гиперкуб. Из анализа гиперкуба следует, что если хроматическое число Ь(6) графа переходов С (без учета дуг, являющихся цетлями) больше 2, та для такого графа переходов не существует соседнега копирования. Таким образом, чтобы граф переходов С имел соседнее кодирование, требуется, чтобы он не содержал циклы нечетной длины.
Если же он их содержит, то необходимо устранить все циклы нечетной длины, вводя дополнительные внутренние состояния, в которых не реализуется отображение Х -ь У. Эти состояния называют неустабчивььни внутренними состояниями. Рассмотрим точный алгоритм соседнего кодирования, основанный на учете запрещенных фигур, характеризующих влажимость кодируемого графа в гиперкуб. Пример 4.3, Пусть заданграфпередадававтомата(рнс. 4 24), кеторыйнзображеп беа етебраженнй Х -ь У, петель, кратных дуг н арнентапнп (поскольку Рнс. 4.24 зте несушественна при решении аздачн соседнеге ваднровання). В сзетвегствнк с выведеннымн ранее уславнямн, чтебы соседнее каднраванне было ваамажна, необхзднмо н достатечна, чтебы граф яе содержал запрешенных падграфав. Прн праевтнревзннн автомата неебтаднмо так преебразевать зтн графы, чтебы все енн ставя влежнмымн.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
