Задачи и последовательность анализа дискретных устройств с памятью

Дискретных устройств с памятью

Описание и анализ условий функционирования

Напомним, что отличительной особенностью, выделяющей дискретные устройства с памятью, является наличие в них запоминающих элементов, элементов памяти (ЭП), состояние которых и определяет внутреннее состояние ДУ.

В ДУ с памятью набор значений выходных сигналов определяется не только набором значений входных сигналов в тот же момент времени, но и предыдущими наборами, а также последовательностью поступления наборов входных сигналов, т.е. ДУ с памятью «запоминает» предыдущую информацию (состояние входных сигналов) и учитывает ее в последующих тактах работы.

В теории дискретных автоматов (дискретных устройств) с памятью принимают следующие основные допущения:

- переход ДА из одного внутреннего состояния в другое осуществляется скачкообразно;

- после перехода ДА в произвольное внутреннее состояние переход в следующее состояние оказывается возможным не ранее чем через некоторый фиксированный для данного автомата промежуток времени τ > 0, называемый интервалом дискретности автомата.

Скачкообразность перехода означает, что переход автомата из одного состояния в другое происходит мгновенно, непосредственно, минуя какие-либо промежуточные состояния. В любом реальном дискретном устройстве имеет место конечная длительность переходных процессов, так что требование скачкообразности перехода в полной мере никогда не удовлетворяется. Однако указанное допущение позволяет достаточно хорошо описывать основные свойства реальных ДУ и поэтому принимается для построения теории ДА.

Допущение, что после перехода ДА в произвольное состояние переход в следующее состояние оказывается возможным только через некоторый фиксированный для данного автомата промежуток времени, дает возможность рассматривать функционирование автомата в так называемом дискретном времени. Это допущение хорошо согласуется с действительностью и отражает тот факт, что пока в дискретном автомате не закончится переходный процесс, связанный с предыдущим изменением состояния, ни один из входных сигналов не может изменить своего значения. Допущение соответствует ограничению по быстродействию, которое всегда имеет место в реальных ДА.

Напомним, что при рассмотрении функционирования ДА во времени непрерывная шкала времени делится на интервалы, называемые тактами. Тактом работы ДА называется отрезок времени произвольной длины, в течение которого не происходит изменения состояний автомата (входов и внутренних состояний). Каждому такту присваивается порядковый номер, и номера тактов образуют дискретное (автоматное) время.

Таким образом, такт является единицей измерения введенного автоматного времени. Шкала времени функционирования ДА разделена на интервалы (такты), занумерованные целыми положительными числами 0, 1, 2, … и т.д. Реальная длительность тактов может быть произвольной.

Такты работы ДУ с памятью делятся на устойчивые и неустойчивые.

Такт называется устойчивым, если без изменения входных сигналов состояние ДУ не изменяется, т.е. устойчивый такт предшествует моменту изменения состояния входов.

Такт называется неустойчивым, если изменение внутреннего состояния ДУ происходит без изменения входных сигналов, т.е. неустойчивый такт предшествует моменту изменения внутреннего состояния дискретного устройства, т.е. состояния элементов памяти.

Дискретное устройство с памятью, как известно, может быть представлено в виде двух взаимосвязанных устройств (автоматов): совокупности элементов памяти (автомата памяти) и логического преобразователя (дискретного автомата без памяти).

Последовательность изменения состояния входов называется входной последовательностью автомата и обозначается P (X) = w ₁ → w ₂ → … → w_j → …, где w_j = w (x ₁, x ₂, …, x_n)= x _i. Например, P (x ₁, x ₂, …, x_n) = 0000 → 0001 → … 0100 → … В этой записи набор 0000 означает, что в начальный момент времени на все входы автомата поступают нулевые входные сигналы, а знак «→» означает, что входной набор, записанный слева от него, сменяется набором, стоящим справа.

Последовательность изменений состояния выходов ДА называется выходной последовательностью и обозначается:

P (Z) = γ ₁ → γ ₂ → … → γ_j → …, γ_j = γ (z ₁, z ₂, …, z_m)=Z_j.

Аналогично для записи изменений состояний памяти вводится последовательность изменений состояний памяти

P (Y) = s ₀ → s ₁ → s ₂ → … → s_j → …, s_j = s (y ₁, y ₂, …, y_k)=Y_j.

Условия работы ДА с памятью определяются функциональными соответствиями между перечисленными выше последовательностями.

Логический преобразователь асинхронного ДА с памятью удобно условно представлять в виде двух отдельных блоков: блока формирования выходных сигналов и блока управления памятью. В этом случае структурная схема ДУ с памятью будет иметь вид, показанный на рисунке 5.1.

	Рисунок 5.1

Для математического описания автомата с памятью задается множество входных сигналов X, множество выходных сигналов Z, множество состояний памяти Y (или множество состояний автомата A), начальное состояние памяти автомата S ₀ (начальное состояние автомата А ₀), функция переходов автомата (или ) и функция выходов автомата или (или , ).

Множества X, Y, Z и начальное состояние S ₀ задаются перечислением:

Функции переходов и выходов могут быть заданы несколькими формализованными моделями. Для изучения моделей автоматов с памятью необходимы формализованные языки, в которые в качестве одной из переменных входит время, и есть правила, определяющие операции над ним и другими переменными.

В настоящее время модели автоматов с памятью получают на различных формализованных языках:

= на языке таблиц переходов-выходов;

= на языке графов переходов-выходов;

= на языке граф-схем алгоритмов;

= на языке логических схем алгоритмов;

= на языке матричных схем алгоритмов;

= на языке таблиц включений;

= на языке алгебры событий и состояний

и других.

Наибольшее внимание мы будем уделять языку таблиц переходов-выходов и языку графов переходов-выходов, в которых функции переходов и выходов автомата задаются соответственно таблицами и графами.

Напомним, что задачей анализа ДУ с памятью является определение условий их работы. Результатом анализа должно явиться построение таблиц переходов-выходов, которые полностью характеризуют условия работы ДУ.

При анализе ДУ с памятью необходимо установить соответствие между состоянием входных сигналов и элементов памяти и состоянием сигналов обратной связи (элементов памяти) и выходных сигналов, а также последовательность чередования этих состояний во времени.