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

UptoLike

ВУЗ: 

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

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

Рубрика: 

68
Канонический метод структурного синтеза оперирует с элементарными авто-
матами, которые делят на два больших класса. Первый класс составляют элементар-
ные автоматы с памятью (т. е. автоматы, имеющие более одного внутреннего со-
стояния); такие автоматы называются элементами памяти или запоминающими эле-
ментами. Второй класс составляют автоматы без памяти (т. е. автоматы с одним
внутренним состоянием), которые принято называть комбинационными, или логиче-
скими элементами.
При принятых допущениях в результате композиции логических элементов
всегда получают автоматы без памяти или, как их иначе называют, комбинационные
схемы. Каждая комбинационная схема (автомат без памяти) характеризуется вектор-
ной функцией выходов, устанавливающей зависимость структурного выходного сиг-
нала x(t) от структурного входного сигнала y(t) в один и тот же момент автоматного
времени:
y(t) = λ x(t),
где λ – векторная функция выходов.
Задание такой функции эквивалентно заданию системы обычных (скалярных)
функций, устанавливающих зависимость каждой компоненты вектора y(t) от компо-
нент (в общем случае всех) вектора x(t).
По аналогии с основной задачей структурного синтеза автоматов может быть
сформулирована задача структурного синтеза комбинационных схем.
2.2. Пусть задано некоторое конечное множество логических элементов (эле-
ментов без памяти) в одном и том же структурном алфавите Z′; предположим, что та-
ких логических элементов имеется неограниченное число экземпляров. Требуется
найти общий конструктивный прием (алгоритм), позволяющий по любому конечному
автомату А без памяти в структурном алфавите Z′ осуществить некоторую компози-
цию заданных логических элементов так, чтобы полученная в результате композиции
комбинационная схема имела ту же самую векторную функцию выходов, что и за-
данный автомат А.
В некоторых случаях при определенном выборе системы логических элемен-
тов сформулированная задача не имеет решение. В другом случае, когда решение
имеется (для произвольного конечного автомата без памяти), считают, что заданная
система логических элементов функционально полна.
Обычно на практике векторная функция выходов λ исходного для комбинаци-
онного синтеза автомата без памяти А задается не во всех точках, так как в некоторых
точках значения функции не определены (безразличны). В таком случае комбинаци-
онная схема, получаемая при решении задачи комбинационного синтеза, должна
иметь векторную функцию выходов, совпадающую с функцией λ во всех точках, в
которых значения функции λ определены.
Сущность канонического метода структурного синтеза автоматов заключается
в том, чтобы свести задачу структурного синтеза произвольных автоматов к задаче
структурного синтеза комбинационных схем (автоматов без памяти). При этом специ-
альным образом производится выбор запоминающих элементов. В качестве запоми-
нающих элементов выбираются автоматы Мура, обладающие полной системой пе-
реходов и полной системой выходов.
2.3. Полнота системы переходов в автомате Мура означает, что для любой упо-
рядоченной пары состояний этого автомата найдется входной сигнал, переводящий

Страницы