Из теории автоматов известно, что реакция автомата с памятью непредсказуема, если неизвестно его начальное состояние. Вместе с тем эта реакция может быть предсказана, если имеется информация о том, из какого состояния данный автомат стартовал. Отсюда вполне очевидна важность задачи анализа автоматов, состоящей в распознавании его начального состояния. Другой важной задачей анализа является распознавание конечного (финального) состояния автомата, поскольку знание его позволяет ввести автомат в различные режимы работы, желательные для достижения заданной цели. Напомним, что эксперименты, служащие для определения начального и конечного состояний, принято называть диагностическими и установочными соответственно. Один частный случай установочного эксперимента называется синхронизирующим.
Эта лекция посвящена исследованию некоторых из перечисленных выше экспериментов для линейных автоматов (ЛА). Предварительно мы опишем объект исследования и приведем основные определения, которые потребуются в дальнейшем.
Начнем с краткого описания модели ЛА, а для более детального знакомства с ней отошлем читателя к монографиям [19], [66]. ЛА является системой с конечным числом входных полюсов, к которым подводятся внешние сигналы, и с конечным числом выходных полюсов, на которых наблюдаются сигналы реакции. Воздействия, поступающие на ЛА, прикладываются одновременно ко всем входам в дискретные моменты времени, которые для удобства представляются целыми числами. Интервалы времени между двумя такими последовательными моментами называются тактами.
Структурная схема ЛА состоит из соединения конечного числа элементарных составляющих, каждая из которых мгновенно выполняет одну из трех функций:
Все операции совершаются одновременно, в результате чего на выходных полюсах ЛА появляются сигналы, принимающие значения из конечного поля, над которым задан ЛА. Таким образом, ЛА может рассматриваться как "черный" ящик с некоторым числом входов и выходов.
Определим три типа компонент, называемых элементарными составляющими ЛА над конечным полем $$GF(p)=\{0,1, \dots, p-1\}$$.
При построении ЛА допускается любое соединение конечного числа элементарных составляющих с одним исключением: не должно быть ни одной замкнутой петли, не содержащей по крайней мере одну задержку. Нарушение этого правила приводит к построению соединения, в котором действует неопределенный сигнал.
Отметим, что усилитель с константой 0 или 1 обозначают соответственно разрыв и прямое соединение. Таким образом, ЛА над полем $$GF(2) $$ (двоичный ЛА) состоит только из сумматоров по модулю 2 и задержек. Поэтому практическая привлекательность двоичных ЛА вполне очевидна.
Усилитель с константой $$p-1= -1$$ называется
Двоичные ЛА являются очень удобными математическими моделями реальных электронных устройств.
Условимся считать, что число входных полюсов ЛА равно $$l$$, число выходных полюсов равно $$m$$. Предполагается, что входные сигналы принимают значение из поля $$GF(p)=\{0,1,\dots , p-1\}$$, где $$p$$ - простое число. Под состоянием ЛА понимается упорядоченная совокупность состояний элементов задержек (обозначим их число через $$n$$ ), входящих в состав ЛА. Число $$n$$ обычно называют размерностью ЛА, и множество состояний обозначают через $$S_n$$.
Введем следующие обозначения:
$$\bar u(t)= [u_1(t),\dots , u_l(t)]', \bar y(t)= [y_1(t),\dots, y_m(t)]', \bar s(t)= [s_1(t),\dots, s_n(t)]'.$$Здесь $$\bar u(t), \bar y(t) \bar s(t)$$ - входной, выходной векторы и вектор-состояние соответственно, а через $$t$$ обозначен момент дискретного времени.
Функционирование ЛА $$\tilde A$$ задается системами уравнений состояний и выходов соответственно:
$$\bar s(t+1)=A \bar s(t)+B\bar (t)$$ $$\bar y(t)=C \bar s(t)+D\bar u(t)$$где $$A=[a_{i,j}]_{nxn}, B=[b_{i,j}]_{nxl}, C=[c_{i,j}]_{mxn}, D=[d_{i,j}]_{mxl}$$, называются характеристическими матрицами ЛА. Матрица $$A$$ обычно называется главной (основной) характеристической матрицей. Все перечисленные матрицы состоят из элементов поля $$GF(p) $$.
Методом
Последняя из этих формул носит название формулы полной реакции ЛА.
Описанную выше модель принято называть стационарным ЛА. Наряду с ней рассмотрим и так называемые нестационарные ЛА (НЛА), функционирование которых задается следующими уравнениями состояний и выходов соответственно:
$$\bar s(t+1)=A(t)\bar s(t)+B(t)\bar u(t),$$ $$\bar y (t)=C(t)\bar s(t)+D(t)\bar u (t)$$Размерность матриц в этих формулах та же, что и в формулах (10.1) и (10.2).
По аналогии со стационарными ЛА можно доказать, что если $$\bar u(0), \bar u(1), \dots, \bar u(t)$$ - входная последовательность НЛА и $$s(0)$$ - начальное состояние НЛА, то его конечное состояние и выходная реакция вычисляются по следующим формулам:
$$\bar s(t+1)=A(t)A(t-1) \dots A(0)\bar s(0)+ \sum_{i=1}^{t-1}A(t)A(t-1) \dots A(i+1)B(i)\bar u(i)+B(t)\bar u(t)$$ $$\bar y(t)=C(t)A(t-1) \dots A(0)\bar s (0)+ \sum_{i=0}^{t-1}C(t)A(t-1) \dots A(i+1)B(i) \bar u(i)+D(t) \bar u (t)$$Определим теперь различные типы экспериментов, которые будут исследоваться нами. Для их проведения необходимо иметь соответствующие последовательности, подаваемые на вход автомата и позволяющие по наблюдаемой реакции находить ответ на интересующий исследователя вопрос. Для разных типов экспериментов необходимо располагать различными типами последовательностей.
Напомним теперь определения соответствующих последовательностей и сделаем это для компактности записей применительно к самой общей модели конечного детерминированного
Как и ранее, под
где $$S, X, Y$$ - конечные множества состояний, входной и выходной алфавиты соответственно, а $$\delta: S \times X \to S$$ и $$\lambda: S \times X \to Y$$ - отображения, называемые функциями переходов и выходов.
Пусть $$S=\{s_1, \dots , s_n\}, X=\{x_1,\dots, x_l\}$$.
Определение 10.1. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется синхронизирующее й (СП), если
$$\forall s_{j_1}, s_{j_2} \in S \delta (s_{j_1}, p) = \delta (s_{j_2},p)$$Содержательно это определение означает, что СП $$р$$ переводит автомат $$А$$ в одно и то же конечное состояние независимо от того, из какого состояния он стартовал.
В этом и приведенных ниже определениях
Определение 10.2. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется установочной (УП), если
$$\forall s_{j_1}, s_{j_2} \in S \lambda (s_{j_1}, p)= \lambda (s_{j_2},p) \to \delta (s_{j_1},p)=\delta (s_{j_2},p)$$Поясним содержательный смысл этого определения: по наблюдаемой реакции на установочную последовательность однозначно идентифицируется конечное состояние автомата.
Очевидно, что СП можно рассматривать как частный, а точнее, как вырожденный случай УП, поскольку подача СП вызывает перевод автомата в известное конечное состояние, хотя и не требует при этом наблюдения его реакции.
Определение 10.3. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется диагностической (ДП), если
$$\forall s_{j_1}, s_{j_2} \in S \lambda (s_{j_1}, p)= \lambda (s_{j_2},p) \to s_{j_1},=s_{j_2}$$Обращаясь к содержательному смыслу этого определения, отметим, что знание реакции автомата на ДП позволяет однозначно идентифицировать его начальное состояние.
Понятно, что каждая ДП одновременно является и УП, поскольку, определив по реакции на ДП начальное состояние автомата, легко определить состояние, в котором он окажется после подачи ДП. Обратное, однако, неверно, т. е. не каждая УП является одновременно и ДП.
Разрешимость установочной и
Отметим, что для автоматов Мили, в общем случае нелинейных, в монографии А. Гилла [18] условия существования перечисленных выше последовательностей сформулированы в терминах весьма громоздкой конструкции
Приведенное выше определение СП применительно к ЛА формулируется следующим образом: входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ ЛА $$А$$ назовем СП, если
$$\forall \bar {s_i}(0), \bar {s_j}(0) \in S_n\\ A^k \bar {s_i}(0)+A^{k-1}B\bar u(0)+ \dots +B \bar u(k-1)=A^k \bar {s_j}(0)+A^{k-1}B\bar u(0)+ \dots +B \bar u(k-1)$$Перенося в (10.9) правую часть равенства влево, получим
$$\forall \bar {s_j}(0), \bar {s_j}(0) \in S_n A^k(\bar {s_i}(0)-\bar {s_j}(0))=[0]$$Символом [0] здесь и далее обозначается нулевая матрица или нулевой вектор подходящей размерности.
Поскольку в (10.10) $$\bar {s_i}(0)$$ и $$\bar {s_j}(0)$$ есть произвольные состояния, то (10.10) эквивалентно предикату
$$\forall \bar s \in S_n A^k \bar s=[0]$$Теорема 10.1. Для того чтобы ЛА $$А$$ имел СП длины $$k$$, необходимо и достаточно, чтобы $$А^k=[0] $$.
Доказательство. Соотношение
$$A^k\bar s=[0]$$можно интерпретировать как систему линейных алгебраических уравнений (СЛАУ) относительно переменных $$s_1, s_2,\dots , s_n$$, являющихся координатами вектор-столбца $$\bar s$$. Пусть ранг матрицы $$А^k$$ равен $$r$$, где $$r \le n$$. Из алгебры известно, что в этом случае число свободных неизвестных $$s_{r+1}, s_{r+2},\dots, s_n$$ в системе (10.12) равно $$n-r$$. Тогда переменные $$s_1 , s_2,\dots, s_r$$ будут выражаться через свободные переменные и, следовательно, число решений системы равно $$р^{n-r}$$. Поскольку СП для ЛА существует тогда и только тогда, когда решением системы (10.12) является любой вектор $$\bar s \in S_n$$, где $$|S_n|=p^n$$, то из сравнения $$p^n$$ и $$p^{n-r}$$ вытекает, что $$r$$ должно равняться нулю, т. е. ранг матрицы $$А^k$$ равен 0. Из последнего равенства следует, что $$А^k =[0] $$.
Определение 10.4. Линейный автомат $$А$$ будем называть синхронизируемым, если у него существует СП.
Из теоремы 10.1 вытекает следующее следствие.
Следствие. Для того чтобы ЛА $$А$$ был синхронизируем, необходимо, чтобы его главная характеристическая матрица А была вырожденной.
Доказательство. Пусть ЛА синхронизируем, тогда существует такое целое $$k$$, что $$А^k = [0] $$. Это означает, что матрица $$А^k$$ является вырожденной. Из алгебры известно, что определитель произведения матриц равен произведению определителей. Отсюда следует, что $$|A^k| = |A|^k$$, где $$|A^k|$$ и $$|A|$$ -
Теорема 10.2. Если для ЛА $$А$$ существует хотя бы одна СП длины $$k$$, то для этого автомата синхронизирующими являются любые входные последовательности длины $$k$$ и более.
Доказательство. Из теоремы 10.1 следует, что для ЛА, имеющего СП $$\bar u(0), bar u(1), \dots, \bar u(k-1)$$ длины $$k$$, конечное состояние ЛА после подачи СП выражается по формуле (10.3) следующим образом:
$$\bar s(k)=A^{k-1}B\bar u(0)+A^{k-2}B\bar u(1)+ \dots +AB \bar u(k-2)+B \bar u (k-1)$$Поскольку правая часть последнего равенства не зависит от начального состояния $$\bar s(0)$$ ЛА, это означает, что при любом начальном состоянии некоторая фиксированная входная последовательность $$\bar u(0), bar u(1), \dots, \bar u(k-1)$$ переводит ЛА в одно и то же конечное состояние. Этот факт остается справедливым и для любой другой фиксированной входной последовательности. Иными словами, любая входная последовательность длины $$k$$ является для этого ЛА синхронизирующей. Ясно, что и любая входная последовательность большей длины также будет синхронизирующей.
Заметим, что последняя теорема свидетельствует о принципиальном различии между общими
Обратимся теперь к вопросу о том, как практически установить существование у заданного ЛА СП и если таковая существует, то как найти длину минимальной СП. Из теории автоматов известно, что установочная задача для автомата с $$\nu$$ состояниями и с $$\nu$$ допустимыми начальными состояниями всегда может быть решена с помощью простого безусловного эксперимента длины $$l$$, где $$l \le (\nu -1)^2$$.
Упомянутая выше верхняя граница длины минимальной СП, равная величине $$(2^n-1)^2$$, достаточно велика. Укажем один частный вид ЛА, для которого эта верхняя граница существенно ниже.
Назовем квадратную матрицу верхней (нижней) треугольной, если все ее элементы, лежащие на главной диагонали и ниже (выше) нее, равны нулю.
Теорема 10.3. Если главная характеристическая матрица ЛА размерности n является верхней (нижней) треугольной, то длина минимальной СП для этого ЛА не превосходит $$n$$.
Доказательство. Проведем его для верхней треугольной матрицы, которую обозначим через А:
$$\left [ \begin {matrix} 0a_{12}a_{13}\dots a_{1, n-1}a_{1,n}\\ 00a_{23} \dots a_{2,n-1} a_{2,n}\\ \dots \dots \dots \dots \dots \dots\\ 0 0 0 \dots a_{n-2, n-1} a_{n-2,n}\\ 0 0 0 \dots 0 a_{n-1, n}\\ 0 0 0 \dots 0 0 \end {matrix} \right ] $$Условимся нумеровать диагонали матрицы, параллельные ее главной диагонали и расположенные выше нее, в порядке убывания числа элементов в них. Тогда диагональ, содержащая элементы $$a_{12}, a_{23}, \dots, a_{n-2,n-1}, a_{n-1,n}$$, получит номер 1, а диагональ, содержащая единственный элемент $$a_{1n}$$, - номер $$n-1$$. Непосредственными вычислениями можно убедиться, что в матрице $$А^2$$ все элементы первой диагонали равны 0, в матрице $$А^3$$ все элементы первой и второй диагонали также равны 0. Методом индукции можно доказать, что в матрице $$А^k$$ наряду с ее нулевой
Для
Ниже будет показано, что в действительности длина минимальной СП не превосходит $$n$$ для произвольного синхронизируемого ЛА размерности $$n$$, а не только для частного вида ЛА, фигурирующего в теореме 10.3.
Состояние ЛА А, в котором он оказывается после подачи некоторой его СП, назовем синхросостоянием.
Обозначим через $$\Synh (A) $$ множество всех возможных синхросостояний ЛА. Ясно, что в общем случае попарно различные СП могут переводить ЛА как в различные, так и в совпадающие синхросостояния, т. е. $$|\Synh(A)| \le p^n$$.
Рассмотрим следующую задачу. Пусть задан синхронизируемый ЛА $$А$$, синхросостояние $$\bar s \in \Synh(A) $$ и пусть $$k $$ - длина минимальной СП этого автомата. Требуется найти такую входную последовательность длины $$k$$, которая переводит ЛА $$А$$ в синхросостояние $$\bar s$$.
Для рассматриваемого ЛА выражение (10.13) можно переписать в виде
$$A^{k-1}B\bar u(0) +A^{k-1} B \bar u(1)+\dots + AB\bar u(k-2)+ B \bar u(k-1)= \bar s$$Далее (10.14) будем рассматривать как СЛАУ (неоднородных) относительно неизвестных $$u_1(0), \dots, u_l(0), \dots, u_1(k-1), \dots, u_l(k-1) $$, общее число которых равно $$l \times k$$.
Пусть $$Q = [q_{ij}]_{n x lk}$$ есть матрица системы (10.14), а $$\bar Q$$ есть расширенная (добавлением к матрице $$Q$$ столбца $$\bar s$$ ) матрица той же системы и $$\rank Q = r$$. Необходимым и достаточным условием совместности системы (10.14) является, как известно из алгебры, условие
Напомним, как могут быть найдены решения системы (10.14) в случае ее совместности. С этой целью выберем в матрице $$Q r$$ линейно независимых строк и в (10.14) оставим лишь те уравнения, коэффициенты которых вошли в выбранные строки. В левых частях этих уравнений оставляем такие $$r$$ неизвестных, что определитель из коэффициентов при них отличен от нуля. Остальные неизвестные в этих уравнениях объявляем свободными и переносим в правые части уравнений. Варьируя значения свободных переменных (все они являются элементами поля $$GF(p) $$ ) и вычисляя значения остальных неизвестных (например, по правилу Крамера), получим все решения системы (10.14).
Проиллюстрируем сказанное на примере. Пусть ЛА над полем $$GF(2) $$ задан характеристическими матрицами:
$$A= \left [ \begin {matrix} 0 0 0 0\\ 1 0 0 0\\ 1 1 0 0\\ 1 1 1 0 \end {matrix} \right ],\\ b= \left [ \begin {matrix} 1 1\\ 1 1\\ 1 1\\ 11 \end {matrix} \right ] $$где $$n = 4, l = 2$$, тогда $$\bar u=[u_1, u_2]' $$.
По теореме 10.3 этот ЛА синхронизируем и длина его минимальной СП равна 4. Система (10.14) в нашем случае в
Вычислим матрицы $$A^3 B, A^2 B, AB$$:
$$A^3B= \left [ \begin {matrix} 00\\ 00\\ 00\\ 11 \end {matrix} \right ],\\ A^2B= \left [ \begin {matrix} 00\\ 00\\ 11\\ 11 \end {matrix} \right ],\\ AB= \left [ \begin {matrix} 00\\ 11\\ 00\\ 11 \end {matrix} \right ]$$Используя эти матрицы, перепишем систему уравнений (10.15) в координатной форме, где неизвестными являются $$u_1(0), u_2(0), u_1(1), u_2(1), u_1(2), u_2(2), u_1(3), u_2(3) $$ - координаты векторов $$\bar u(0), bar u(1), \bar u(2), \bar u(3)$$:
$$u_1(3) + u_2(3) = s_1,\\ u_1(2) + u_2(2) + u_1(3) + u_2(3) = s_2, \\ u_1(1) + u_2(1) + u_1(3) + u_2(3) = s_3,\\ u_1(0) + u_2(0) + u_1(1) + u_2(1) + u_1(2) + u_2(2) + u_1(3) + u_2(3) = s_4.$$Здесь $$s_1, s_2, s_3, s_4$$ есть координаты вектора $$\bar s$$.
Матрица этой системы имеет вид
$$Q= \left \{ \begin {matrix} 00000011\\ 00001111\\ 00110011\\ 11111111 \end {matrix} \right \} $$Вычисления показывают, что $$\rank Q = 4$$. Перенумеруем столбцы матрицы $$Q$$ слева направо начиная с 1. Выберем в $$Q$$ четыре линейно независимых столбца, например, с номерами 1, 3, 5, 7, которым соответствуют неизвестные $$u_1(0), u_1(1), u_1(2), u_1(3) $$. Легко проверить, что определитель, составленный из названных столбцов, отличен от нуля. Оставим эти перечисленные неизвестные в левых частях уравнений системы (10.16), а остальные переменные объявим свободными и перенесем в правые части уравнений:
$$u_1(3 ) = u_2(3) + s_1,\\ u _1(2) + u_1(3) = u_2(2) + u_2(3) + s_2,\\ u _1(1) + u_1(3) = u_2(1) + u_2(3) + s_3,\\ u_1(0) + u_1(1) + u_1(2) + u_1(3) = u_2(0) + u_2(1) + u_2(2) + u_2(3) +s_4.$$После простых и очевидных преобразований последняя система примет вид
$$u_1(3 ) = u_2(3) + s_1,\\ u_1(2) = u_2(2) + s_1 + s_2,\\ u_1(1) = u_2(1) + s_1 + s_3,\\ u_1(0) = u_2(0) + s_1 + s_2 + s_3 + s_4.$$Выберем, например, состояние $$\bar s = (1,1,1,1)' $$ и проверим, является ли оно синхросостоянием. Если да, то найдем минимальную по длине СП, переводящую заданный ЛА в это синхросостояние. Условимся также среди всех минимальных по длине СП найти такую, которая имеет минимальный вес. Весом СП назовем число, которое равно сумме координат входных символов, составляющих эту СП.
Поскольку в нашем примере $$s_1 = s_2 = s_3 = s_4 = 1$$, то система (10.17) примет вид:
$$u_1(3) = u_2(3) +1; u_1(2) = u_2(2) ; u_1(1) = u_2(1) ; u_1(0) = u_2(0).$$Для получения искомой СП минимального веса положим $$u_2(3), u_2(2), u_2(1), u_2(0) $$ равными нулю. Тогда искомая СП, переводящая заданный ЛА из любого состояния в состояние $$(1,1,1,1)' $$, такова: $$(0,0)', (0,0)', (0,0)', (1,0)'$$.
ЛА над полем $$GF(2) $$ задан следующими характеристическими матрицами:
$$A= \begin {pmatrix} 0 0 1\\ 0 1 1\\ 1 1 1 \end {pmatrix},\\ b= \begin {pmatrix} 0 1\\ 1 0\\ 1 1 \end {pmatrix},\\ C= \begin {pmatrix} 0 10\\ 001 \end {pmatrix}, D= \begin {pmatrix} 10\\ 01 \end {pmatrix}$$Требуется проверить, существует ли для этого ЛА синхронизирующая (установочная, диагностическая) последовательность.
ЛА над полем $$GF(2) $$ имеет следующие характеристические матрицы:
$$A= \begin {pmatrix} 000\\ 100\\ 110 \end {pmatrix}, B= \begin {pmatrix} 10\\ 01\\ 11 \end {pmatrix}$$Покажите, что этот ЛА является синхронизируемым и найдите длину минимальной СП.
Проверьте, является ли состояние $$s=[1,1,1]' $$ этого ЛА синхросостоянием, и если да, то найдите минимальную СП, переводящую ЛА в это состояние.
Из теории автоматов известно, что реакция автомата с памятью непредсказуема, если неизвестно его начальное состояние. Вместе с тем эта реакция может быть предсказана, если имеется информация о том, из какого состояния данный автомат стартовал. Отсюда вполне очевидна важность задачи анализа автоматов, состоящей в распознавании его начального состояния. Другой важной задачей анализа является распознавание конечного (финального) состояния автомата, поскольку знание его позволяет ввести автомат в различные режимы работы, желательные для достижения заданной цели. Напомним, что эксперименты, служащие для определения начального и конечного состояний, принято называть диагностическими и установочными соответственно. Один частный случай установочного эксперимента называется синхронизирующим.
Эта лекция посвящена исследованию некоторых из перечисленных выше экспериментов для линейных автоматов (ЛА). Предварительно мы опишем объект исследования и приведем основные определения, которые потребуются в дальнейшем.
Начнем с краткого описания модели ЛА, а для более детального знакомства с ней отошлем читателя к монографиям [19], [66]. ЛА является системой с конечным числом входных полюсов, к которым подводятся внешние сигналы, и с конечным числом выходных полюсов, на которых наблюдаются сигналы реакции. Воздействия, поступающие на ЛА, прикладываются одновременно ко всем входам в дискретные моменты времени, которые для удобства представляются целыми числами. Интервалы времени между двумя такими последовательными моментами называются тактами.
Структурная схема ЛА состоит из соединения конечного числа элементарных составляющих, каждая из которых мгновенно выполняет одну из трех функций:
Все операции совершаются одновременно, в результате чего на выходных полюсах ЛА появляются сигналы, принимающие значения из конечного поля, над которым задан ЛА. Таким образом, ЛА может рассматриваться как "черный" ящик с некоторым числом входов и выходов.
Определим три типа компонент, называемых элементарными составляющими ЛА над конечным полем $$GF(p)=\{0,1, \dots, p-1\}$$.
При построении ЛА допускается любое соединение конечного числа элементарных составляющих с одним исключением: не должно быть ни одной замкнутой петли, не содержащей по крайней мере одну задержку. Нарушение этого правила приводит к построению соединения, в котором действует неопределенный сигнал.
Отметим, что усилитель с константой 0 или 1 обозначают соответственно разрыв и прямое соединение. Таким образом, ЛА над полем $$GF(2) $$ (двоичный ЛА) состоит только из сумматоров по модулю 2 и задержек. Поэтому практическая привлекательность двоичных ЛА вполне очевидна.
Усилитель с константой $$p-1= -1$$ называется
Двоичные ЛА являются очень удобными математическими моделями реальных электронных устройств.
Условимся считать, что число входных полюсов ЛА равно $$l$$, число выходных полюсов равно $$m$$. Предполагается, что входные сигналы принимают значение из поля $$GF(p)=\{0,1,\dots , p-1\}$$, где $$p$$ - простое число. Под состоянием ЛА понимается упорядоченная совокупность состояний элементов задержек (обозначим их число через $$n$$ ), входящих в состав ЛА. Число $$n$$ обычно называют размерностью ЛА, и множество состояний обозначают через $$S_n$$.
Введем следующие обозначения:
$$\bar u(t)= [u_1(t),\dots , u_l(t)]', \bar y(t)= [y_1(t),\dots, y_m(t)]', \bar s(t)= [s_1(t),\dots, s_n(t)]'.$$Здесь $$\bar u(t), \bar y(t) \bar s(t)$$ - входной, выходной векторы и вектор-состояние соответственно, а через $$t$$ обозначен момент дискретного времени.
Функционирование ЛА $$\tilde A$$ задается системами уравнений состояний и выходов соответственно:
$$\bar s(t+1)=A \bar s(t)+B\bar (t)$$ $$\bar y(t)=C \bar s(t)+D\bar u(t)$$где $$A=[a_{i,j}]_{nxn}, B=[b_{i,j}]_{nxl}, C=[c_{i,j}]_{mxn}, D=[d_{i,j}]_{mxl}$$, называются характеристическими матрицами ЛА. Матрица $$A$$ обычно называется главной (основной) характеристической матрицей. Все перечисленные матрицы состоят из элементов поля $$GF(p) $$.
Методом
Последняя из этих формул носит название формулы полной реакции ЛА.
Описанную выше модель принято называть стационарным ЛА. Наряду с ней рассмотрим и так называемые нестационарные ЛА (НЛА), функционирование которых задается следующими уравнениями состояний и выходов соответственно:
$$\bar s(t+1)=A(t)\bar s(t)+B(t)\bar u(t),$$ $$\bar y (t)=C(t)\bar s(t)+D(t)\bar u (t)$$Размерность матриц в этих формулах та же, что и в формулах (10.1) и (10.2).
По аналогии со стационарными ЛА можно доказать, что если $$\bar u(0), \bar u(1), \dots, \bar u(t)$$ - входная последовательность НЛА и $$s(0)$$ - начальное состояние НЛА, то его конечное состояние и выходная реакция вычисляются по следующим формулам:
$$\bar s(t+1)=A(t)A(t-1) \dots A(0)\bar s(0)+ \sum_{i=1}^{t-1}A(t)A(t-1) \dots A(i+1)B(i)\bar u(i)+B(t)\bar u(t)$$ $$\bar y(t)=C(t)A(t-1) \dots A(0)\bar s (0)+ \sum_{i=0}^{t-1}C(t)A(t-1) \dots A(i+1)B(i) \bar u(i)+D(t) \bar u (t)$$Определим теперь различные типы экспериментов, которые будут исследоваться нами. Для их проведения необходимо иметь соответствующие последовательности, подаваемые на вход автомата и позволяющие по наблюдаемой реакции находить ответ на интересующий исследователя вопрос. Для разных типов экспериментов необходимо располагать различными типами последовательностей.
Напомним теперь определения соответствующих последовательностей и сделаем это для компактности записей применительно к самой общей модели конечного детерминированного
Как и ранее, под
где $$S, X, Y$$ - конечные множества состояний, входной и выходной алфавиты соответственно, а $$\delta: S \times X \to S$$ и $$\lambda: S \times X \to Y$$ - отображения, называемые функциями переходов и выходов.
Пусть $$S=\{s_1, \dots , s_n\}, X=\{x_1,\dots, x_l\}$$.
Определение 10.1. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется синхронизирующее й (СП), если
$$\forall s_{j_1}, s_{j_2} \in S \delta (s_{j_1}, p) = \delta (s_{j_2},p)$$Содержательно это определение означает, что СП $$р$$ переводит автомат $$А$$ в одно и то же конечное состояние независимо от того, из какого состояния он стартовал.
В этом и приведенных ниже определениях
Определение 10.2. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется установочной (УП), если
$$\forall s_{j_1}, s_{j_2} \in S \lambda (s_{j_1}, p)= \lambda (s_{j_2},p) \to \delta (s_{j_1},p)=\delta (s_{j_2},p)$$Поясним содержательный смысл этого определения: по наблюдаемой реакции на установочную последовательность однозначно идентифицируется конечное состояние автомата.
Очевидно, что СП можно рассматривать как частный, а точнее, как вырожденный случай УП, поскольку подача СП вызывает перевод автомата в известное конечное состояние, хотя и не требует при этом наблюдения его реакции.
Определение 10.3. Входная последовательность $$p=x_{i_1}, x_{i_2}, \dots, x_{i_a}$$ называется диагностической (ДП), если
$$\forall s_{j_1}, s_{j_2} \in S \lambda (s_{j_1}, p)= \lambda (s_{j_2},p) \to s_{j_1},=s_{j_2}$$Обращаясь к содержательному смыслу этого определения, отметим, что знание реакции автомата на ДП позволяет однозначно идентифицировать его начальное состояние.
Понятно, что каждая ДП одновременно является и УП, поскольку, определив по реакции на ДП начальное состояние автомата, легко определить состояние, в котором он окажется после подачи ДП. Обратное, однако, неверно, т. е. не каждая УП является одновременно и ДП.
Разрешимость установочной и
Отметим, что для автоматов Мили, в общем случае нелинейных, в монографии А. Гилла [18] условия существования перечисленных выше последовательностей сформулированы в терминах весьма громоздкой конструкции
Приведенное выше определение СП применительно к ЛА формулируется следующим образом: входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ ЛА $$А$$ назовем СП, если
$$\forall \bar {s_i}(0), \bar {s_j}(0) \in S_n\\ A^k \bar {s_i}(0)+A^{k-1}B\bar u(0)+ \dots +B \bar u(k-1)=A^k \bar {s_j}(0)+A^{k-1}B\bar u(0)+ \dots +B \bar u(k-1)$$Перенося в (10.9) правую часть равенства влево, получим
$$\forall \bar {s_j}(0), \bar {s_j}(0) \in S_n A^k(\bar {s_i}(0)-\bar {s_j}(0))=[0]$$Символом [0] здесь и далее обозначается нулевая матрица или нулевой вектор подходящей размерности.
Поскольку в (10.10) $$\bar {s_i}(0)$$ и $$\bar {s_j}(0)$$ есть произвольные состояния, то (10.10) эквивалентно предикату
$$\forall \bar s \in S_n A^k \bar s=[0]$$Теорема 10.1. Для того чтобы ЛА $$А$$ имел СП длины $$k$$, необходимо и достаточно, чтобы $$А^k=[0] $$.
Доказательство. Соотношение
$$A^k\bar s=[0]$$можно интерпретировать как систему линейных алгебраических уравнений (СЛАУ) относительно переменных $$s_1, s_2,\dots , s_n$$, являющихся координатами вектор-столбца $$\bar s$$. Пусть ранг матрицы $$А^k$$ равен $$r$$, где $$r \le n$$. Из алгебры известно, что в этом случае число свободных неизвестных $$s_{r+1}, s_{r+2},\dots, s_n$$ в системе (10.12) равно $$n-r$$. Тогда переменные $$s_1 , s_2,\dots, s_r$$ будут выражаться через свободные переменные и, следовательно, число решений системы равно $$р^{n-r}$$. Поскольку СП для ЛА существует тогда и только тогда, когда решением системы (10.12) является любой вектор $$\bar s \in S_n$$, где $$|S_n|=p^n$$, то из сравнения $$p^n$$ и $$p^{n-r}$$ вытекает, что $$r$$ должно равняться нулю, т. е. ранг матрицы $$А^k$$ равен 0. Из последнего равенства следует, что $$А^k =[0] $$.
Определение 10.4. Линейный автомат $$А$$ будем называть синхронизируемым, если у него существует СП.
Из теоремы 10.1 вытекает следующее следствие.
Следствие. Для того чтобы ЛА $$А$$ был синхронизируем, необходимо, чтобы его главная характеристическая матрица А была вырожденной.
Доказательство. Пусть ЛА синхронизируем, тогда существует такое целое $$k$$, что $$А^k = [0] $$. Это означает, что матрица $$А^k$$ является вырожденной. Из алгебры известно, что определитель произведения матриц равен произведению определителей. Отсюда следует, что $$|A^k| = |A|^k$$, где $$|A^k|$$ и $$|A|$$ -
Теорема 10.2. Если для ЛА $$А$$ существует хотя бы одна СП длины $$k$$, то для этого автомата синхронизирующими являются любые входные последовательности длины $$k$$ и более.
Доказательство. Из теоремы 10.1 следует, что для ЛА, имеющего СП $$\bar u(0), bar u(1), \dots, \bar u(k-1)$$ длины $$k$$, конечное состояние ЛА после подачи СП выражается по формуле (10.3) следующим образом:
$$\bar s(k)=A^{k-1}B\bar u(0)+A^{k-2}B\bar u(1)+ \dots +AB \bar u(k-2)+B \bar u (k-1)$$Поскольку правая часть последнего равенства не зависит от начального состояния $$\bar s(0)$$ ЛА, это означает, что при любом начальном состоянии некоторая фиксированная входная последовательность $$\bar u(0), bar u(1), \dots, \bar u(k-1)$$ переводит ЛА в одно и то же конечное состояние. Этот факт остается справедливым и для любой другой фиксированной входной последовательности. Иными словами, любая входная последовательность длины $$k$$ является для этого ЛА синхронизирующей. Ясно, что и любая входная последовательность большей длины также будет синхронизирующей.
Заметим, что последняя теорема свидетельствует о принципиальном различии между общими
Обратимся теперь к вопросу о том, как практически установить существование у заданного ЛА СП и если таковая существует, то как найти длину минимальной СП. Из теории автоматов известно, что установочная задача для автомата с $$\nu$$ состояниями и с $$\nu$$ допустимыми начальными состояниями всегда может быть решена с помощью простого безусловного эксперимента длины $$l$$, где $$l \le (\nu -1)^2$$.
Упомянутая выше верхняя граница длины минимальной СП, равная величине $$(2^n-1)^2$$, достаточно велика. Укажем один частный вид ЛА, для которого эта верхняя граница существенно ниже.
Назовем квадратную матрицу верхней (нижней) треугольной, если все ее элементы, лежащие на главной диагонали и ниже (выше) нее, равны нулю.
Теорема 10.3. Если главная характеристическая матрица ЛА размерности n является верхней (нижней) треугольной, то длина минимальной СП для этого ЛА не превосходит $$n$$.
Доказательство. Проведем его для верхней треугольной матрицы, которую обозначим через А:
$$\left [ \begin {matrix} 0a_{12}a_{13}\dots a_{1, n-1}a_{1,n}\\ 00a_{23} \dots a_{2,n-1} a_{2,n}\\ \dots \dots \dots \dots \dots \dots\\ 0 0 0 \dots a_{n-2, n-1} a_{n-2,n}\\ 0 0 0 \dots 0 a_{n-1, n}\\ 0 0 0 \dots 0 0 \end {matrix} \right ] $$Условимся нумеровать диагонали матрицы, параллельные ее главной диагонали и расположенные выше нее, в порядке убывания числа элементов в них. Тогда диагональ, содержащая элементы $$a_{12}, a_{23}, \dots, a_{n-2,n-1}, a_{n-1,n}$$, получит номер 1, а диагональ, содержащая единственный элемент $$a_{1n}$$, - номер $$n-1$$. Непосредственными вычислениями можно убедиться, что в матрице $$А^2$$ все элементы первой диагонали равны 0, в матрице $$А^3$$ все элементы первой и второй диагонали также равны 0. Методом индукции можно доказать, что в матрице $$А^k$$ наряду с ее нулевой
Для
Ниже будет показано, что в действительности длина минимальной СП не превосходит $$n$$ для произвольного синхронизируемого ЛА размерности $$n$$, а не только для частного вида ЛА, фигурирующего в теореме 10.3.
Состояние ЛА А, в котором он оказывается после подачи некоторой его СП, назовем синхросостоянием.
Обозначим через $$\Synh (A) $$ множество всех возможных синхросостояний ЛА. Ясно, что в общем случае попарно различные СП могут переводить ЛА как в различные, так и в совпадающие синхросостояния, т. е. $$|\Synh(A)| \le p^n$$.
Рассмотрим следующую задачу. Пусть задан синхронизируемый ЛА $$А$$, синхросостояние $$\bar s \in \Synh(A) $$ и пусть $$k $$ - длина минимальной СП этого автомата. Требуется найти такую входную последовательность длины $$k$$, которая переводит ЛА $$А$$ в синхросостояние $$\bar s$$.
Для рассматриваемого ЛА выражение (10.13) можно переписать в виде
$$A^{k-1}B\bar u(0) +A^{k-1} B \bar u(1)+\dots + AB\bar u(k-2)+ B \bar u(k-1)= \bar s$$Далее (10.14) будем рассматривать как СЛАУ (неоднородных) относительно неизвестных $$u_1(0), \dots, u_l(0), \dots, u_1(k-1), \dots, u_l(k-1) $$, общее число которых равно $$l \times k$$.
Пусть $$Q = [q_{ij}]_{n x lk}$$ есть матрица системы (10.14), а $$\bar Q$$ есть расширенная (добавлением к матрице $$Q$$ столбца $$\bar s$$ ) матрица той же системы и $$\rank Q = r$$. Необходимым и достаточным условием совместности системы (10.14) является, как известно из алгебры, условие
Напомним, как могут быть найдены решения системы (10.14) в случае ее совместности. С этой целью выберем в матрице $$Q r$$ линейно независимых строк и в (10.14) оставим лишь те уравнения, коэффициенты которых вошли в выбранные строки. В левых частях этих уравнений оставляем такие $$r$$ неизвестных, что определитель из коэффициентов при них отличен от нуля. Остальные неизвестные в этих уравнениях объявляем свободными и переносим в правые части уравнений. Варьируя значения свободных переменных (все они являются элементами поля $$GF(p) $$ ) и вычисляя значения остальных неизвестных (например, по правилу Крамера), получим все решения системы (10.14).
Проиллюстрируем сказанное на примере. Пусть ЛА над полем $$GF(2) $$ задан характеристическими матрицами:
$$A= \left [ \begin {matrix} 0 0 0 0\\ 1 0 0 0\\ 1 1 0 0\\ 1 1 1 0 \end {matrix} \right ],\\ b= \left [ \begin {matrix} 1 1\\ 1 1\\ 1 1\\ 11 \end {matrix} \right ] $$где $$n = 4, l = 2$$, тогда $$\bar u=[u_1, u_2]' $$.
По теореме 10.3 этот ЛА синхронизируем и длина его минимальной СП равна 4. Система (10.14) в нашем случае в
Вычислим матрицы $$A^3 B, A^2 B, AB$$:
$$A^3B= \left [ \begin {matrix} 00\\ 00\\ 00\\ 11 \end {matrix} \right ],\\ A^2B= \left [ \begin {matrix} 00\\ 00\\ 11\\ 11 \end {matrix} \right ],\\ AB= \left [ \begin {matrix} 00\\ 11\\ 00\\ 11 \end {matrix} \right ]$$Используя эти матрицы, перепишем систему уравнений (10.15) в координатной форме, где неизвестными являются $$u_1(0), u_2(0), u_1(1), u_2(1), u_1(2), u_2(2), u_1(3), u_2(3) $$ - координаты векторов $$\bar u(0), bar u(1), \bar u(2), \bar u(3)$$:
$$u_1(3) + u_2(3) = s_1,\\ u_1(2) + u_2(2) + u_1(3) + u_2(3) = s_2, \\ u_1(1) + u_2(1) + u_1(3) + u_2(3) = s_3,\\ u_1(0) + u_2(0) + u_1(1) + u_2(1) + u_1(2) + u_2(2) + u_1(3) + u_2(3) = s_4.$$Здесь $$s_1, s_2, s_3, s_4$$ есть координаты вектора $$\bar s$$.
Матрица этой системы имеет вид
$$Q= \left \{ \begin {matrix} 00000011\\ 00001111\\ 00110011\\ 11111111 \end {matrix} \right \} $$Вычисления показывают, что $$\rank Q = 4$$. Перенумеруем столбцы матрицы $$Q$$ слева направо начиная с 1. Выберем в $$Q$$ четыре линейно независимых столбца, например, с номерами 1, 3, 5, 7, которым соответствуют неизвестные $$u_1(0), u_1(1), u_1(2), u_1(3) $$. Легко проверить, что определитель, составленный из названных столбцов, отличен от нуля. Оставим эти перечисленные неизвестные в левых частях уравнений системы (10.16), а остальные переменные объявим свободными и перенесем в правые части уравнений:
$$u_1(3 ) = u_2(3) + s_1,\\ u _1(2) + u_1(3) = u_2(2) + u_2(3) + s_2,\\ u _1(1) + u_1(3) = u_2(1) + u_2(3) + s_3,\\ u_1(0) + u_1(1) + u_1(2) + u_1(3) = u_2(0) + u_2(1) + u_2(2) + u_2(3) +s_4.$$После простых и очевидных преобразований последняя система примет вид
$$u_1(3 ) = u_2(3) + s_1,\\ u_1(2) = u_2(2) + s_1 + s_2,\\ u_1(1) = u_2(1) + s_1 + s_3,\\ u_1(0) = u_2(0) + s_1 + s_2 + s_3 + s_4.$$Выберем, например, состояние $$\bar s = (1,1,1,1)' $$ и проверим, является ли оно синхросостоянием. Если да, то найдем минимальную по длине СП, переводящую заданный ЛА в это синхросостояние. Условимся также среди всех минимальных по длине СП найти такую, которая имеет минимальный вес. Весом СП назовем число, которое равно сумме координат входных символов, составляющих эту СП.
Поскольку в нашем примере $$s_1 = s_2 = s_3 = s_4 = 1$$, то система (10.17) примет вид:
$$u_1(3) = u_2(3) +1; u_1(2) = u_2(2) ; u_1(1) = u_2(1) ; u_1(0) = u_2(0).$$Для получения искомой СП минимального веса положим $$u_2(3), u_2(2), u_2(1), u_2(0) $$ равными нулю. Тогда искомая СП, переводящая заданный ЛА из любого состояния в состояние $$(1,1,1,1)' $$, такова: $$(0,0)', (0,0)', (0,0)', (1,0)'$$.
ЛА над полем $$GF(2) $$ задан следующими характеристическими матрицами:
$$A= \begin {pmatrix} 0 0 1\\ 0 1 1\\ 1 1 1 \end {pmatrix},\\ b= \begin {pmatrix} 0 1\\ 1 0\\ 1 1 \end {pmatrix},\\ C= \begin {pmatrix} 0 10\\ 001 \end {pmatrix}, D= \begin {pmatrix} 10\\ 01 \end {pmatrix}$$Требуется проверить, существует ли для этого ЛА синхронизирующая (установочная, диагностическая) последовательность.
ЛА над полем $$GF(2) $$ имеет следующие характеристические матрицы:
$$A= \begin {pmatrix} 000\\ 100\\ 110 \end {pmatrix}, B= \begin {pmatrix} 10\\ 01\\ 11 \end {pmatrix}$$Покажите, что этот ЛА является синхронизируемым и найдите длину минимальной СП.
Проверьте, является ли состояние $$s=[1,1,1]' $$ этого ЛА синхросостоянием, и если да, то найдите минимальную СП, переводящую ЛА в это состояние.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.