Терема о структурном синтезе КА.


Вопрос 45. Терема о структурном синтезе КА.
Пусть задан некоторый КА в общем виде K=<A,Q,B,???>. Теорема 4.2.: Любой К. автомат K может быть реализован сетью из ??? и элемента задержки D с не более , чем |Q| состояниями.
b(t)=?(q(t), a(t))
q? (t) = ? (q(t), a(t))
автоматы ? и ? являются комбинационными на множестве входящих знаков A=A*Q. ДОК-ВО : Осуществим методом мат. индукции по длине строки для исходного автомата и сети автоматов К : предполагается, что результирующий автомат описывается соединением дискретных функций. {b(t)=?(q(?), a(t)) , q? (t) = ? (q(t), a(t))
состояние в следующий момент времени = вычисленному состоянию в текущий момент времени (время дискретно). K(q, ?)= K’(q’, ?) , где q ’(Qd |Qd|=|Q|. Синхронизация асинхронного автомата производится в момент времени , когда меняется знак x.

Вопрос 46. Синхронный автомат. Синхронный элемент задержки.
Определение : Потенциальный сигнал- это дискретный сигнал интервалы времени между соседними изменениями которого значительно больше времени реакции схемы на которую он воздействует. Импульсный сигнал — это дискретный сигнал длительность которого соизмеримо с временем реакции схемы на которую он воздействует ( заканчивается сразу после оказания воздействия). Абстрактный импульсный сигнал — это импульсный сигнал длительность которого бесконечно мала но достаточна для оказания воздействия на абстрактную схему. Оператор переходов — это преобразователь потенциального сигнала в импульсный. Позволяет абстрагироваться от физических характеристик конкретной схемы.
dx=lim x(t)&x(t-?t) , где x(t)- потенциальный сигнал ; dx — абстрактный импульсный сигнал. dx= x(t) & x(t — ?t) , где ?t — время реакции схемы.
реализуя оператор переходов : x*=x( t — ?t)
Структура синхронного автомата: система уравнений описывающая работу синхронного автомата : {b(t) = ? (q(t), a(t)) ; {q+(t) = ? (q(t), a(t)) ; {q(t) = q(t)•dH ? q+(t) dH
Синхронный элемент задержки : Синхронный элемент задержки (памяти) — это элемент на выходе которого появляется входной знак в момент импульсного воздействия тактового сигнала и удерживается до прихода следующего тактового сигнала. DL- триггер нельзя использовать в качестве синхронного элемента задержки.

Вопрос 47: Асинхронный автомат. Синтез Асинхронных потенциальных автоматов.
Рассмотрим последовательные схемы. В отличии от комбинационных схем, эти имеют элементы памяти. Определение: асинхронный потенциальный автомат — это конечный автомат ( последовательная схема в виде реализации логических элементов) изменение входного знака которого может привести к изменению состояний, т.е. все состояния автомата устойчивы по всем входным знакам. ?qi ?Q , ?aj ? A состояние ?(qi, aj)=?(qi, aj, aj). Структура Асинхронного потенциального автомата: в качестве элементов памяти используется элемент задержки на время ?
b(t)=?(q(t), a(t))
q+(t)=?(q(t), a(t))
q(t+?)=q+(t) , ??R
? может быть уменьшена до величины соизмеримой с временем задержки комбинационной части автомата. tзд — среднее время задержки распространения сигнала. Для реальных автоматов мы можем отказаться от элемента задержки , т.к. они сами является задержкой.
Вопрос 49. Структурный синтез комбинационных автоматов (КА).
a) Пусть f заданна на Ф над системой определ. ?
b) В произвольной формуле Ф подставим в соответствии схему Г из элементарных комбинационных автоматов каждый из которых реализует операцию из ?
c) Состояния схемы Г определим индукцией по длине формулы Ф. Базис: если Ф=?(xi1…xik), где ? операция над которым построена формула, а xi1…xik исходные переменные, то Г состоит из одного элемента ?.
Предположение индукции: пусть построена некая схема Гi реализующая выражения Ф1…Фк, где Фi – или переменная или же выражение реализованное схемой Гi. Вывод индукции: тогда если Ф=?(Ф1…Фк) (формула Ф может быть представлена в виде операции ? над подформулами Фi)
Замечание: для произвольного выражения заданного в базисе ? м.б. построена схема Г из элементов каждый из которых реализует операцию из ? в виде ориентированного дерева. Входы схемы соотв. Концевым вершинам, а выходы – корню дерева. Число знаков операций в формуле равно числу логических элементов схемы.
Теорема 5.3: Для того чтобы произвольная функция f могла быть реализована Г над базисов ? необходимо и достаточно, чтобы множество операций реализуемых автоматным базисом ? было функционально полным.
Вопрос 50. Кодирование алфавитов конечного автомата. Синтез конечных автоматов в заданном автоматном базисе.
В связи с тем, что ?(q,a)=b и ?(q,a)=q определены на множество содержащим возможно разное число элементов, и не совпадающими со злачностью операции автоматного базиса на ?, то прибегают к кодированию A,B,Q в виде последовательности знаков в виде алгор. Автоматного базиса.

Загрузка...