Синтез цифровых автоматов. Захаров Н.Г - 70 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

69
первый элемент этой пары во второй. Иначе говоря, если δ(q, x) – функция переходов
автомата, то для полноты системы переходов в этом автомате необходимо и доста-
точно, чтобы для любой пары (q, b) его состояний уравнение b = δ(q, x) было бы раз-
решимым относительно входного сигнала х.
2.4. Полнота системы выходов в автомате Мура означает, что каждому состоя-
нию автомата соответствует свой собственный выходной сигнал, отличный от выход-
ного сигнала, соответствующего любому другому состоянию. Иначе говоря, для пол-
ноты системы выходов автомата Мура необходимо и достаточно, чтобы его сдвину-
тая функция выходов y = λ(q) осуществляла взаимно однозначное отображение мно-
жества состояний автомата на множество всех его выходных сигналов.
2.5. В автомате Мура с полной системой выходов можно отождествить внут-
ренние состояния с выходными сигналами автомата. Тогда один и тот же (структур-
ный) алфавит употребляется не только для обозначения (кодирования) входных и вы-
ходных сигналов, но и для кодирования внутренних состояний этого автомата.
Для автоматов с полной системой переходов целесообразно ввести следующее
определение.
2.6. Функцией входов автомата А с полной системой переходов и заданной
функцией переходов δ(q, x) называется функция х = µ(q, b) (обычно неоднозначная),
заданная на упорядоченных парах состояний автомата А. Для каждой такой пары (q,
b) в качестве значения функции входов µ(q, b) выбирается (непустое) множество
всех тех входных сигналов х, для которых δ(q, x) = b.
Функции входов конечных автоматов задаются таблицами входов. В таблице
входов на пересечении q-й строки b-го столбца помещается множество входных сиг-
налов, вызывающих переход автомата из состояния q в состояние b.
Таким образом, в реальных цифровых автоматах, как правило, употребляются
запоминающие элементы, представляющие собой автоматы Мура с полной системой
переходов и с полной системой выходов. При этом ограничения, вводимые канониче-
ским методом структурного синтеза, с практической точки зрения являются несуще-
ственными.
4.4.2. Теорема о структурной полноте
Рассмотрим справедливость следующего утверждения, которое назовем теоре-
мой о структурной полноте.
2.7. Всякая система элементарных автоматов считается структурно-полной
системой, если в этой системе имеется автомат Мура с нетривиальной памятью, об-
ладающий полной системой переходов и полной системой выходов и какой-нибудь
функционально полной системой логических элементов. Существует общий конст-
руктивный прием (канонический метод структурного синтеза), позволяющий в дан-
ном случае свести задачу структурного синтеза произвольных конечных автоматов к
задаче структурного синтеза комбинационных схем.
Для доказательства теоремы 2.7 синтезируем произвольный конечный автомат
А. Выберем запоминающие элементы А
1
, ..., А
р
, обладающие полными системами
переходов и выходов, причем такие, что произведение чисел их состояний не меньше,
чем число состояний автомата А. Каждому состоянию q автомата А поставим в соот-
ветствие конечную последовательность (q
1
, ..., q
р
) состояний автоматов А
1
, ..., А
р
так,

Страницы