Кодирование состояний автоматов
Решая задачу кодирования состояний,
мы будем полагать, что кодирование
входного и выходного алфавитов зада-
но, хотя в принципе это не обязательно,
так как подобная ситуация чаще всего встречается на практике.
Разные варианты кодирования состоя- ний автомата позволяют получать схе- мы, разные по:
1) сложности КС, реализующих функции возбуждения и выхо-
дов;
2) возможности сохранения работо-способности схемы отдельных ее элементов (отказоустойчивости);
3) надежности работы в условиях
возможных рассогласований времен тактов ЭА.
Здесь обсуждается кодирование, упрощаю-
щее КС автомата.
Рассмотрим автомат вида:
(Функцию выходов не рассматриваем.)
Займемся структурным синтезом этого автомата.
Фиксируем коды алфавитов:
Примем, что ЭА - типа Д
и построим кодированную
таблицу переходов и возбуждения ЭА.
По таблице можно получить Д 0 и Д 1 в виде МДНФ
При малом числе переменных миними- зировать удобно по карте Карно.
Закодировав состояния, как
и построив новую кодирован-
ную таблицу переходов и воз-
буждения ЭА, мы получим но-
вые Д 0 и Д 1 :
Новый вариант кодирования дал функ- ции возбуждения, реализация которых заметно проще.
Наша цель - искать кодирования состояний, дающие простые схемы.
Наибольшая простота достигается, если
в результате кодирования получаются
функции, каждая (или значительная
часть) из которых не зависят от некото-
рых переменных, являющихся аргумен-
тами функций переходов и выходов.
В рассмотренном примере получено
Д 1 = Q0 ,
хотя в общем виде
Д 1 = f(x0,Q0,Q1).
Здесь кодирование привело к несущес- твенной зависимости Д 1 от Х0и Q1.
На практике обычно используют:
1) методы, основывающиеся на знании семантики функций переходов;
2) эвристические методы, учитывающие локальные характеристики связности отдельных состояний ;
3) Методы, учитывающие взаимосвязь функций переходов и выходов.
Мы будем рассматривать 2) и 3) .
Начнем с 2) .
Простейший алгоритм кодирования для
ЭА типа Д.
1. Определяется число ЭА как log 2 числа состояний автомата.
2. Состояния автомата упорядочи-ваются по убыванию числа пере-ходов в них.
3. Коды состояний ЭА упорядочи-ваются по возростанию числа еди-
ниц в кодах.
4. Состояниям с большим числом переходов в них ставятся в соот-ветствие коды с меньшим числом единиц.
В вышеприведенном примере получаем
Такое кодирование даст
Результат проще 1-го варианта, но сложнее 2-го.
Алгоритм, минимизирующий числоизменений состояний ЭА.
Обозначим W =å tmp , где tmp - число ЭА, изменяющих свое состояние при перехо-
де из Sm в Sp и из Sp в Sm . Суммирование
ведется по всем переходам (дугам) авто-
мата.
W может служить оценкой сложности КС автомата, раализующей функции возбуждения: чем меньше W тем проще КС.
Экспериментально-статистическая про- верка подтверждает эту гипотезу.
Алгоритм
1. Состояние, в которое идет наи-большее число переходов, коди-
руется 00...00.
2. Отыскивается состояние, наибо-
лее связанное по числу переходов
с ранее закодированными состоя-
ниями, и кодируется так, что бы
получить min текущего значения W.
3. Процедура заканчивается после кодирования всех состояний.
При малом числе состояний удобно пользоваться грфом автомата, при большом - таблицей переходов.
Пример.
1. S4 Û 000.
2. S3 Û 001.
t34 =2.
3.
|
4.
Взяв, например, код 100 получим t25 + t24 =4+1=5.
Завершая, получим:
5. S1 Û 111.
6. S0 Û 100.
Вариант не единственный и, возможно,не лучший, так как минимизация выполняется локально.
Учет взаимосвязи функций переходов ивыходов.
А. Автоматы Мура
Идея в построении схемы, реализующей
При S = S¢ | S¢¢ .
Схему можно рассматривать как модер-
низацию канонической реализации с от-сутствующей (тривиальной) КС функций выходов.
Выгода обуславливается:
¨ малой стоимостью ЭА, число которых обычно растет;
¨ использованием реализации функциональных зависимостей S¢(t+1)=Ф(X(t) , S(t) ) для реализации и Y, и функций возбуждения ЭА.
Алгоритм кодирования будем рассматривать на примере автомата :
Алгоритм.
1.По значениям функций выходов, отмечающим состояния, фиксируем коды S¢ для каждого состояния S.
Пример
S0¢= 00 ; S1¢= 01 ; S2¢= 01 ;
S3¢= 11 ; S4¢= 01 ; S5¢= 11 ;
2. Выделяем подмножества состояний, не-различимых по коду S¢, и определяем наибольшее число состояний, имеющих одинаковый код.
Пример
Подмножества: (S1 , S2 , S4);( S3 , S5)
Наибольшее число неразличимых по
коду S¢ состояний - 3.
Примечание
Если в автомате есть состояния с неопре- деленными значениями выходов, то они доопределяются и относятся к выделен- ным подмножествам так чтобы:
1) по возможности использовать коды S¢ , которые еще не были использованы;
2) не увеличивать наибольшее число состояний, имеющих одинаковый код.
3. Если все состояния различимы по коду S¢ , кодирование закончено, причем S = S¢ .
В рассматриваемом примере кодирование не закончено.
4. Определяем разрядность кода S¢¢ как log2 от наибольшего числа неразличимых по коду S¢ состояний.
В нашем примере имеем разрядность , равную log 2 3 = 2.
5. Кодируем состояния S= S¢ | S¢¢ (с учетом того, что значения S¢ уже зафик-сированы) по одному из алгоритмов кодирования состоя-ний, не учитывающих взаимо-связи функций выходов и пере-
ходов.
В примере будем использовать алгоритм, минимизирующий число изменений сос-
тояний ЭА, что даст:
1) S0 = 0000 4) S4 = 0110
2) S1 = 0100 5) S3 = 1101
3) S2 = 0101 6) S5 = 1100
Схема будет иметь вид:
Б. Автоматы Мили.
Здесь Y=F(X,S) , а не F(S) как у автома- тов Мура. Поэтому упрощение схем обы- чно не удается получить.
Замечания о применимости метода кодирования.
1. Использование для кодов состояний авто-матов Мура или Мили значений Y ведет к увеличению разрядности кода S (числа пе-ременных функций возбуждения и выходов).
В этом случае реализация КС автомата на
базе БИС ПЗУ может оказаться невыгод-
ной, так как сложность таких КС сильно
зависит от числа переменных.
В других случаях, и в том числе для КС
на БИС ПЛМ , рассматриваемый метод кодирования состояний автоматов Мура
(реже Мили) обычно дает хорошие резу-
льтаты.
2. Использование Y для представления
кодов состояний может оказаться неце-лесообразным при (log2k) << m, где k –
число состояний автомата, а m - число
выходов.
При этом не используют Y для предста-
вления кодов состояний, либо использу-
ют только m¢ из m выходов Y , как будто
других выходов нет. Обычно это выходы
при использовании которых разрядность
S¢¢ будет заметно меньше чем log2k, а разрядность S¢ близка к log2k.
В результате получается схема вида:
Выбор ЭА.
Сложность КС автомата зависит от того, какие типы ЭА используются в автомате, так как для разных ЭА требуются разные функции возбуждения.
Оптимальный выбор ЭА связан с пере-
бором большого числа вариантов схем.
Задача усложняется тем, что в общем
случае выбор ЭА следует совмещать с
выбором кодов состояний.
Приближенное решение задачи выбора
ЭА можно проводить на основе локаль-
ного независимого подбора типов отдель-
ных ЭА из числа перебираемых.
Просмотрев ЭАi для i = 0 ¸ k-1, выберем набор ЭА.
Рассматривая ЭАi нужно для каждого ти-
па ЭАi : D, T, JK, и т.д. получить функции возбуждения и выбрать тип ЭА, требую-
щий наиболее простую КС.
Оценка сложности КС может получаться
по разному в зависимости от используе-
мых ЛЭ.
Можно строить прототип КС, используя
простые приемы синтеза; можно оценивать
по числу конъюнкций в ДНФ; можно оце-
нивать по числу переменных и т.п.
Следует отметить, что на практике вы- бор из l типов ЭА часто связан с целе- сообразностью использования одного типа всех k ЭА. При этом перебор сок- ратится с k´l до l вариантов.
В некоторых случаях выбор типов ЭА
обуславливается соображениями, не свя-занными со сложностью КС автомата, на-пример, со сравнительными характерис-
тиками отдельных типов ЭА: надежность, потребляемая мощность и т.д.