Наряду с традиционным понятием состояния ЛА $$\tilde A$$ размерности $$n$$, представляющего собой $$n$$ -мерный вектор, введем понятие обобщенного состояния. С этой целью зафиксируем некоторое целое положительное число $$\mu$$, такое, что $$1 \le \mu n$$, и вектор-столбец
$$\tidle s (t)=\lbrack s_1(t), \dots, s_\mu, \underbrace{x, \dots,x}_{n-\mu раз}}\rbrack' $$где $$x$$ - символ неопределенности, будем называть обобщенным состоянием (ОС) линейного автомата. Предполагается, что каждый символ неопределенности $$x$$ может принимать любое значение из поля $$GF(p)$$. Таким образом, каждому ОС линейного автомата соответствует некоторое подмножество $$S_n$$ всех состояний ЛА. Далее через $$\tilde {S_{\mu}}$$ будем обозначать пространство обобщенных состояний ЛА. Понятно, что число обобщенных состояний в $$\tilde {S_{\mu}}$$ равно $$p^{\mu}$$.
Вообще говоря, обобщенное состояние ЛА можно определить иначе, например, положив
$$\tilde s(t)=[s_1(t), \dots, s_{i_1-1}(t), \dots, x, s_{i_1+1}(t), \dots, s_{i_{n- \mu -1}}(t_, x, s_{i_{n- \mu +1}}(t), \dots, s_n(t)]' $$где $$n- \mu$$ штук значений координат $$s_{i_j}(t), j=1, \dots, \mu$$, номера которых выбраны произвольным образом, замещены символом неопределенности $$x$$. Легко показать, что путем подходящих перестановок строк и столбцов характеристических матриц линейный автомат $$\hat A$$ всегда может быть преобразован в такой изоморфный ему ЛА $$\tilde A$$, у которого ОС (12.2) отображается при этом в ОС (12.1). Поэтому для простоты записи, но не теряя при этом общности, примем первый вариант (12.1) определения ОС.
Далее условимся о следующих обозначениях: если $$H$$ есть матрица, то через $$[H]_a$$ обозначим матрицу с $$a$$ штук строками, совпадающими с первыми $$a$$ строками матрицы $$H$$. Аналогичное обозначение используем и для вектора: $$[\bar s]_a$$ - это вектор размерности $$a$$, у которого координаты совпадают с $$a$$ первыми координатами вектора $$\bar s$$.
ЛА с заданной величиной $$\mu$$, определяющей для ЛА пространство обобщенных состояний, условимся обозначать как $$\mu$$ -ЛА.
Введем для $$\mu$$ -ЛА понятие обобщенной диаграммы переходов (ОДП). ОДП для $$\mu$$ -ЛА над полем $$GF(p)$$ назовем ориентированный граф, содержащий $$p^{\mu}$$ вершин, взаимно однозначно соответствующих каждому ОС этого автомата. Две вершины $$\bar a$$ и $$\bar b$$ в ОДП соединяются дугой, ведущей из $$\bar a$$ в $$\bar b$$, помеченной входным символом $$\bat u$$ $$\mu$$ -ЛА, если существуют по крайней мере два таких "традиционных" состояния $$\bar s$$ и $$\tilde s$$ из $$S_n$$, что $$[s]_{\mu}=\bar a, [s]_{\mu}=\bar b, \tilde s=A\bar s+B\bar u$$.
Отметим различие между "традиционной" диаграммой переходов ЛА [19] и ОДП: в "традиционной" диаграмме каждой ее дуге, помеченной входным символом $$\bar u$$, соответствует единственный выходной символ (реакция ЛА на вход $$\bar u$$ в состоянии $$\bar s$$ ), а в ОДП некоторой дуге может соответствовать несколько выходных символов. Назовем ОДП сильно связной, если в ней для любой пары вершин $$\bar a$$ и $$\bar b$$ существует путь, ведущий из $$\bar a$$ в $$\bar b$$. Соответствующий этой ОДП $$\mu$$ -ЛА будем называть $$\mu$$ -сильно связным.
Понятно, что любому пути в ОДП из $$\bar a$$ в $$\bar b$$ соответствует некоторое входное слово $$\mu$$ -ЛА, возможно не одно, переводящее его из ОС $$\bar a$$ в ОС $$\bar b$$.
По аналогии с [19] $$\mu$$ -ЛА назовем $$k$$ -управляемым, если для любых двух его обобщенных состояний $$\bar a$$ и $$\bar b$$ существует входное слово длины $$k$$, переводящее его из $$\bar a$$ в $$\bar b$$. Очевидно, что $$k$$ -управляемый $$\mu$$ -ЛА является $$\mu$$ -сильно связным.
Теорема 12.1. $$\mu$$ -ЛА является $$\mu$$ -управляемым тогда и только тогда, когда ранг матрицы
$$[L_k]_{\mu}=[A^{k-1}B, A^{k-2}B, \dots, AB,B]_{\mu}$$равен $$\mu$$.
Доказательство. Пусть $$[\bar s]_{\mu}$$ и $$[\tilde s]_{\mu}$$ - различные произвольные ОС рассматриваемого $$\mu$$ -ЛА. По определению $$k$$ -управляемости существует такая входная последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ длины $$k$$, которая переводит $$\mu$$ -ЛА из $$[\bar s]_{\mu}$$ в $$[\tilde s]_{\mu}$$. Тогда на основании формулы (1.3) можно записать:
$$[\bar s]_{\mu}=[A^k \tilde s+A^{k-1}B\bar u(0)+\dots |AB\bar u(k-2)+B\bar u(k-1)]_{\mu}$$Отсюда следует, что
$$[\bar s-A^k\tilde s]_{\mu}=[A^{k-1}B\bar u(0)+ \dots +AB\bar u(k-2)+b\bar u(k-1)]_{\mu}=\\ =[L_k[\bar u(0), \bar u(1), \dots, \bar u(k-1)]']_{\mu}$$Поскольку $$\bar s-A^k\tilde s$$ может быть любым $$n$$ -мерным вектором, $$[\bar s-A^k\tilde s]_{\mu}$$ также может быть любым $$\mu$$ -мерным вектором. В силу этого последнее равенство можно записать в виде
$$[L_k \hat u]_{\mu}$$где $$\hat u=[\bar u(0), \bar u(1), \dots, \bar u(k-1)]'$$, и интерпретировать его как СЛАУ относительно неизвестных, являющихся координатами вектора $$\hat u$$.
Понятно, что существование входной последовательности, переводящей $$\mu$$ -ЛА из произвольного ОС $$[\tilde s]_{\mu}$$ в произвольное ОС $$[\bar s]_{\mu}$$, эквивалентно существованию решений выписанной выше системы при любых правых частях. Из алгебры известно [33], что необходимым и достаточным условием для этого является равенство ранга системы (12.3) величине $$\mu$$. Заметим, что при $$\mu =n$$, где $$n$$ - размерность ЛА, $$\mu$$ -
Путем вычислений можно убедиться, что
$$L_3=[A^2B,AB,B]= \left [ \begin {matrix} 010\\ 101\\ 111 \end {matrix} \right ]$$и $$\rank L_3=2$$. Тогда по теореме 12.1 этот ЛА не является сильно связным.
Положим $$\mu =2$$, тогда
$$[L_3]_2= \left [ \begin {matrix} 010\\ 101 \end {matrix} \right ]$$и $$rank [L_3]_2=2$$. По теореме 12.1 рассматриваемый $$\mu$$ -ЛА является 2-сильно связным. Таким образом, исходный ЛА не является сильно связным, однако в пространстве обобщенных состояний он становится 2-сильно связным.
Определим теперь понятие синхронизирующей последовательности для $$\mu$$ -ЛА в пространстве обобщенных состояний.
Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА назовем обобщенной СП (ОСП), если
$$\forall \bar s, \tilde s \in \tilde {S_{\mu}}\ \ [A^{k+1}\bar S+A^kB\bar u(0)+ \dots +B\bar u(k)]_{\mu}=[A^{k+1}\tilde s +A^kB \bar u(0)+ \dots +B \bar u(k)]_{\mu}$$Понятно, что при $$\mu =n$$, где $$n$$ - размерность ЛА, приведенное определение совпадает с определением обычной СП для этого же автомата. Перенося в (12.4) правую часть равенства влево и выполнив сокращения, получим
$$\forall \bar s, \tilde s \in S_{\mu}\ \ [A^{k+1}\bar s - A^k \tilde s)]_{\mu}=[0]_{\mu}$$где $$[0]=_{\mu}$$ - нулевой вектор размерности $$\mu$$. Поскольку в (12.5) $$\bar s$$ и $$\tilde s$$ могут быть любыми ОС из $$\tilde S_{\mu}$$, то (12.5) эквивалентно
$$\forall \bar s \in S_n\ \ [A^{k+1}\bar s]_{\mu}=[0]_{\mu}$$Из предиката (12.6) вытекает справедливость следующего утверждения.
Теорема 12.2. Для того чтобы $$\mu$$ -ЛА $$\tilde A$$ имела ОСП длины $$k+1$$, необходимо и достаточно, чтобы
$$[A^{k+1}]_{\mu}=[0]_{\mu}$$Как видим, эта теорема является аналогом теоремы 1.1 для обычного ЛА, т. е. ее естественным обобщением.
По аналогии с разделом 1.2 $$\mu$$ -ЛА условимся называть обобщенно синхронизируемым, если для него существует ОСП.
Рассмотрим ЛА над полем $$GF(2)$$, заданный следующими характеристическими матрицами:
$$A= \left [ \begin {matrix} 000\\ 010\\ 001 \end {matrix} \right ], B= \left [ \begin {matrix} 0\\ 0\\ 0 \end {matrix} \right ]$$Поскольку $$A \ne [0]$$, то для этого ЛА, как это следует из теоремы 1.1, СП длины 1 не существует. Положим $$\mu =1$$ и рассмотрим соответствующий 1-ЛА. Понятно, что состояние этого автомата в момент времени $$t+1$$ не зависит от состояния в момент $$t$$, так как $$B$$ есть нулевая матрица. Более того, для этого ЛА
$$s(t+1)=[0 s_2(t) s_2(t)]'$$Из последнего равенства следует, что
$$[s(t+1)]_1=[0]_1$$Последнее означает: любая входная последовательность длины 1 переводит 1-ЛА в одно и то же состояние $$[0]_1$$, т. е. любая такая последовательность является ОСП.
Таким образом, нами построен пример ЛА, не имеющего обычной СП некоторой фиксированной длины, но в то же время имеющего обобщенную СП такой длины.
Почти дословное повторение доказательства теоремы 1.2 позволяет установить справедливость ее аналога для $$\mu$$ -ЛА.
Теорема 12.3. Если для $$\mu$$ -ЛА существует хотя бы одна ОСП длины $$k$$, то обобщенными СП для него являются любые входные последовательности длины $$k$$ и более.
По аналогии с обобщенными СП введем понятия обобщенных УП и ДП для $$\mu$$ -ЛА $$\tilde A$$, полагая, что множеством его допустимых начальных состояний является множество, которое мы обозначим как $$\Init (\tilde A0$$.
Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА $$A$$ назовем обобщенной УП (ОУП), если
$$\forall \bar s(0), \tilde s(0) \in Init(\tilde A) \wedge_{d=0}^k[CA^d\bar s(0)+CA^{d-1}B\bar u(0)+ \dots +CB \bar u(d-1)+D\bar u(d)=\\ = CA^d \tilde s(0)+CA^{d-1}B\bar u(0)+ \dots +CB\bar u(d-1)+D\bar u(d)] \to\\ \to [A^{k+1}\bar s(0)+A^kB\bar u(0)+ \dots +AB\bar u(k-1)+B\bar u(k)]_{\mu}=\\ =[A^{k+1}\tilde s(0)+A^kB\bar u(0)+ \dots +AB\bar u(k-1)+B\bar u(k)]_{\mu}$$Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА $$\tilde A$$ назовем обобщенной ДП (ОДП), если
$$\forall \bar s(0), \tilde s(0) \in Init (\tilde A) \wedge_{d=0}^k[CA^d\bar s(0)+CA^{d-1}B\bar u(0)+ \dots +CB\bar u(d-1)+D\bar u(d)=\\ =CA^d \tilde s())+CA^{d-1}B\bar u(0)+ \dots + CB\bar u(d-1)+D\bar u(d)] \to [\bar s(0)]_{\mu}=[\tilde s(0)]_{\mu} $$Заметим, что содержательный смысл обобщенных УП и ДП тот же, что и обычных, но применительно к обобщенным состояниям. Ниже приводятся теоремы, которые содержат естественные обобщения результатов для обычных ЛА на ЛА, рассматриваемые в пространстве обобщенных состояний. Доказательства некоторых из этих утверждений опущены, поскольку могут быть получены за счет незначительного изменения уже приводившихся ранее доказательств.
Теорема 12.4. Для того чтобы $$\mu$$ -ЛА имел обобщенную УП длины $$k+1$$, необходимо и достаточно, чтобы
$$\forall \bar s \in \hat {Init}(\tilde A) (\exists k \ge 0 CA^k\bar s \ne [0]) \vee (\exists k \ge 0 [A^{k+1}\bar s]_{\mu}=[0]_{\mu})$$Здесь через $$\hat {\Init}(\tilde A)$$ обозначено множество состояний, представляющее собой всевозможные разности состояний из множества $$\Init (\tilde A)$$.
Теорема 12.5. Если у $$\mu$$ -ЛА $$\tilde A$$ размерности $$n$$ ранг характеристической матрицы $$C$$ равен $$n$$, то для него существует обобщенная УП длины 1.
Доказательство. Пусть $$\bar s$$ и $$\tilde s$$ - два различных начальных состояния $$\mu$$ -ЛА $$A$$ из множества допустимых. Через $$\bar y(0)$$ и $$\tilde y(0)$$ обозначим реакции этого автомата на входной символ $$\bar u(0)$$. Пусть $$[\bar {s_k}]_{\mu}$$ и $$[\tilde {s_k}]_{\mu}$$ - состояния $$\mu$$ -ЛА после подачи $$\bar u(0)$$. Если $$\bar u(0)$$ - обобщенная УП, то это означает, что
$$\forall \bar s, \tilde s \in \Init (\tilde A) \bar y(0)=\tilde y(0) \to [\bar {s_k}]_{\mu}=[\bar {s_k}]_{\mu}$$Предположим, что $$\bar u(0)$$ не является обобщенной УП, тогда
$$\exists \bar s, \tilde s \in \Init (\tilde A) \bar y(0)=\tilde y(0) \wedge [\bar {s_k}]_{\mu} \ne [\bar {s_k}]_{\mu}$$что эквивалентно
$$\exists \bar s, \tilde s \in \Init (\tilde A) C(\bar s - \tilde s)=[0] \wedge [\bar {s_k}]_{\mu} \ne [\bar {s_k}]_{\mu}$$Первый сомножитель в (12.7) можно интерпретировать как систему линейных
что противоречит условию теоремы. Отсюда следует ложность предиката (12.7) и, следовательно, справедливость теоремы.
Теорема 12.6. Если для $$\mu$$ -ЛА размерности $$n$$ существует хотя бы одна обобщенная УП длины $$k$$, то для этого автомата обобщенными УП являются любые входные последовательности длины $$k$$ и более.
Введем следующие обозначения: через $$K_t^{\mu}$$ и $$K_t^{(\mu)}$$ соответственно обозначим подматрицы матрицы
$$K_t=[C, CA, \dots, CA^{t-1}]'$$содержащие первые и соответственно последние $$\mu$$ ее столбцов.
Теорема 12.7. Для того чтобы $$\mu$$ -ЛА $$A$$ размерности $$n$$ имел обобщенную ДП длины $$t$$, необходимо и достаточно, чтобы ранг матрицы $$K_t^{\mu}$$ был равен $$\mu$$ и $$K_t^{(\mu)}=[0]$$.
Эта теорема является естественным обобщением теоремы 1.7. Два последующих утверждения являются аналогами теорем 1.8 и 1.9.
Теорема 12.8. Если для $$\mu$$ -ЛА существует хотя бы одна обобщенная ДП длины $$k$$, то для него обобщенными являются любые входные последовательности длины $$k$$ и более.
Теорема 12.9. Если для $$\mu$$ -ЛА размерности $$n$$ существуют обобщенные ДП, то длина таких минимальных последовательностей не превосходит $$n$$.
Заметим, что аналоги последней теоремы справедливы как для обобщенных СП, так и для обобщенных УП.
Выше были рассмотрены ЛА, в правых частях уравнений переходов и выходов которых фигурировали векторы и матрицы со значениями только в момент времени $$t$$. Вместе с тем многие реальные процессы и устройства требуют для своего описания использования уравнений с
Ниже будет использована классификация произвольных дискретных систем (ДС) с
Обыкновенная ДС - поведение ее описывается уравнением
$$\bar s(t+ \alpha )+A_1\bar s(t+ \alpha -1)+ \dots + A_{\alpha}\bar s(t)=B_0\bar u(t+ \beta)+ \dots +B_{\beta}\bar u(t), \beta < \alpha$$Для того чтобы движение обыкновенной ДС было однозначно определено при $$t \ge 0$$, для любого входа $$\bar u(t)$$ должны быть заданы начальные условия $$\bar s(0), \bar s(1), \dots, \bar s(\alpha -1)$$ и $$\bar u(0), \bar u(1), \dots, \bar u(\beta - 1)$$
ДС с запаздыванием по состоянию - поведение ее описывается уравнением
$$\bar s(t+1)=A\bar s(t)+A_1\bar s(t-h)+B\bar u(t)$$Для однозначного определения процесса $$\bar s(t)$$ при любом входе $$\bar u(t)$$ задаются начальные условия $$\bar s(0), \bar s(-1), \dots, \bar s(-h)$$, где $$h$$ - некоторое положительное целое число.
ДС с запаздыванием по управлению - поведение ее описывается уравнением
$$\bar s(t+1)=A\bar s(t)+B\bar u(t)+B_1\bar u(t-h)$$Для однозначности определения процесса $$\bar s(t)$$ при $$t \ge -$$ при любом входе $$\bar u(t)$$ должны быть заданы начальные условия $$\bar s(0)$$ и $$\bar u(0), \bar u(-1), \dots, \bar u(-h)$$, где $$h$$ - некоторое положительное целое число.
В этом разделе будут рассмотрены вопросы существования СП, УП и ДП и методы их построения для линейных
Для получения
Из приведенных выше описаний ДС можно заключить, что участвующие в них векторы $$\bar s(t)$$, вообще говоря, не всегда представляют собой состояние системы в общепринятом смысле, т. е. ту минимальную по объему информацию, которую необходимо знать в текущий момент времени $$t$$ для однозначного продолжения процесса $$\bar s(t)$$ при известном входе $$\bar u(t)$$ Учитывая сказанное, каждую из перечисленных выше ДС с
Рассмотрим вначале обыкновенную ДС, заданную уравнением (12.8). Состояние $$\bar z(t+\alpha)$$ этой ДС в произвольный момент времени $$t+\alpha$$ определим как вектор $$[\bar s(t), \bar s(t+1), \dots, \bar s(t + \alpha +1)]'$$ Тогда состояние, в которое она переходит при подаче входного сигнала $$\bar u(t+ \beta)$$, есть вектор $$\bar u(t+\alpha +1)=[\bar s(t+1), \dots, \bar s(t+ \alpha)]'$$. Таким образом, если эту ДС описывать в виде ЛА, то размерность такого ЛА есть величина $$n=m \alpha$$ а начальное состояние есть $$\bar z(0)=[\bar s(0), \bar s(1), \dots, \bar s(\alpha +1)]'$$ В качестве входного вектора $$\bar u(t+\beta)$$ этой ДС теперь будем использовать вектор $$\tilde u(t+\beta)=[\bar u(t), \bar u(t+1), \dots, \bar u(t+\beta)]'$$ С учетом изложенного, если описывать рассматриваемую ДС в виде ЛА, уравнение ее переходов состояний примет вид
$$\bar z(t+ \alpha +1)=A*\bar z(t+ \alpha)+B* \tilde u(t+\beta)$$Матрицы $$A*$$ и $$B*$$ имеют блочную структуру, которая описывается ниже. В роли блоков в матрице $$A*$$ выступают матрицы размерности $$m \times m$$, а число "блочных" строк и столбцов ее равно величине $$\alpha$$ Структура этой матрицы имеет следующий вид ( $$E_m$$ - единичная матрица размером $$m \times m$$ ):
$$A*= \left [ \begin {matrix} [0]E_m[0] \dots [0]\\ [0][0]E_m \dots [0]\\ \dots a \dots \dots \dots \dots \\ [0][0][0] \dots E_m\\ \A_{\alpha} -A_{\alpha -1} -A_{\alpha -2} \dots -A_1 \end {matrix} \right ] $$В роли блоков матрицы $$B*$$ выступают матрицы размерности $$m \times l$$. Число "блочных" строк в $$B*$$ равно $$\alpha$$, а число "блочных" столбцов - $$\beta +1$$. Структура этой матрицы такова:
$$B*= \left [ \begin {matrix} [0][0][0]\dots [0]\\ [0][0][0] \dots [0]\\ \dots \dots \dots \dots \dots\\ [0] [0][0] \dots [0]\\ B_{\beta}b_{\beta -1}B_{\beta -2} \dots B_0 \end {matrix} \right ]$$Непосредственной проверкой можно убедиться, что уравнение (12.11) с такими характеристическими матрицами задает линейный автомат, эквивалентный, с точки зрения функционирования, обыкновенной ДС, описанной разностным уравнением (1.1), откуда следует справедливость следующего утверждения:
Теорема 1.1 Для того чтобы ЛА с
Рассмотрим теперь ДС с
где матрицы $$A^{\cdot}$$ и $$B^{\cdot}$$ так же, как и в предыдущем случае, имеют блочную структуру. В роли блоков в матрице $$A^{\cdot}$$ выступают матрицы размерности $$m \times m$$, а число ее "блочных" строк и столбцов равно $$h+1$$:
$$A*= \left [ \begin {matrix} [0]E_m[0] \dots [0]\\ [0][0]E_m \dots [0]\\ \dots \dots \dots \dots \dots\\ [0][0][0] \dots E_m\\ A_1[0][0] \dots A \end {matrix} \right ]$$В роли блоков в матрице $$B*$$ выступают матрицы размерности $$m \times l$$, "блочных" строк в ней одна, а число столбцов - $$h+1$$:
$$B*=[[0] \dots [0]B]'$$Можно проверить, что уравнение (10.1) с приведенными характеристическими матрицами задают ЛА, эквивалентный, с точки зрения функционирования, ДС с
Рассмотрим, наконец, ДС с
Тогда очевидно, что основная характеристическая матрица соответствующего ЛА просто совпадает с матрицей $$A$$ из (1.1), а в роли матрицы $$B$$ в формуле (1.1) будет выступать "блочный" вектор
$$B*=[B[0] \dots [0] B_1]'$$Из изложенного следует, что условие существования СП для ДС с
Подводя итог, отметим, что каждой из перечисленных выше типов ДС можно поставить в соответствие такой ЛА без
Кроме того, для решения задачи о переводе ЛА с
где $$\bar s(t)=[s_1(t), s_2(t)]'$$ и $$\bar u(t)=[u_1(t)]'$$, т. е. $$m=2, l=1$$, а характеристические матрицы ДС имеют следующий вид:
$$A_1= \left [ \begin {matrix} 01\\ 00 \end {matrix} \right ], A_2= \left [ \begin {matrix} 00\\ 00 \end {matrix} \right ], B_0= \left [ \begin {matrix} 0\\ 1 \end {matrix} \right ], B_1= \left [ \begin {matrix} 1\\ 0 \end {matrix} \right ]$$Вычисления показывают, что эквивалентный рассматриваемой системе ЛА имеет следующие характеристические матрицы:
$$A*= \left [ \begin {matrix} 0010\\ 0001\\ 0001\\ 0000 \end {matrix} \right ], B*= \left [ \begin {matrix} 00\\ 00\\ 10\\ 01 \end {matrix} \right ]$$При этом состоянием ЛА и его входным вектором являются векторы:
$$\bar s(t)=[s_1(t), s_2(t), s_1(t+1), s_2(t+1]', \dots, \bar u(t)=[u_1(t), u_1(t+1)]'$$Пусть задано синхросостояние $$\tilde s=[0,1,0,1]'$$ и требуется найти такую входную последовательность, которая переводит ДС из произвольного начального состояния в синхросостояние $$\tilde s$$.
Легко проверить, что $$(A*)^3=[0]$$ откуда вытекает, что эквивалентный рассматриваемой системе ЛА синхронизируем и длина минимальной СП равна 3. Для нахождения искомой СП выпишем матричное уравнение вида (1.14) для нашего примера:
$$(A*)^2B* \tilde u(0)+A*B* \tilde u(1)+B*\tilde u(2)= \tilde s$$С учетом приведенных выше матриц $$A*$$ и $$B*$$ это уравнение принимает следующий вид:
$$\left [ \begin {matrix} 01\\ 00\\ 00\\ 00 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(0)\\ u_1(1) \end {matrix} \right ] + \left [ \begin {matrix} 10\\ 01\\ 10\\ 00 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(1)\\ u_2(1) \end {matrix} \right ] + \left [ \begin {matrix} 00\\ 00\\ 10\\ 01 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(2)\\ u_1(3) \end {matrix} \right ] = \left [ \begin {matrix} 0\\ 1\\ -\\ 1 \end {matrix} \right ] $$Перейдем от этого уравнения к равносильной системе, записанной в координатной форме:
$$u_1(1)+ u_1(1)=0, u_1(2)=1, u_1(1)+ u_1(2)=0, u_1(3)=1,$$где "+" - операция по модулю 2.
Легко проверить, что эта система совместна и ее решение таково:
$$u_1(0)=x, u_1(1)=1, u_1(2)=1, u_1(3)=0,$$где х означает безразличное значение (0 или 1). Следовательно, для рассматриваемой ДС в качестве СП, переводящей ее из произвольного начального состояния в заданное синхросостояние $$\tilde s$$, могут быть использованы две следующие входных последовательностей:
Коснемся теперь
Поскольку, как показано выше, каждый из рассматриваемых типов ДС соответствует эквивалентной ей ЛА без
Наряду с традиционным понятием состояния ЛА $$\tilde A$$ размерности $$n$$, представляющего собой $$n$$ -мерный вектор, введем понятие обобщенного состояния. С этой целью зафиксируем некоторое целое положительное число $$\mu$$, такое, что $$1 \le \mu n$$, и вектор-столбец
$$\tidle s (t)=\lbrack s_1(t), \dots, s_\mu, \underbrace{x, \dots,x}_{n-\mu раз}}\rbrack' $$где $$x$$ - символ неопределенности, будем называть обобщенным состоянием (ОС) линейного автомата. Предполагается, что каждый символ неопределенности $$x$$ может принимать любое значение из поля $$GF(p)$$. Таким образом, каждому ОС линейного автомата соответствует некоторое подмножество $$S_n$$ всех состояний ЛА. Далее через $$\tilde {S_{\mu}}$$ будем обозначать пространство обобщенных состояний ЛА. Понятно, что число обобщенных состояний в $$\tilde {S_{\mu}}$$ равно $$p^{\mu}$$.
Вообще говоря, обобщенное состояние ЛА можно определить иначе, например, положив
$$\tilde s(t)=[s_1(t), \dots, s_{i_1-1}(t), \dots, x, s_{i_1+1}(t), \dots, s_{i_{n- \mu -1}}(t_, x, s_{i_{n- \mu +1}}(t), \dots, s_n(t)]' $$где $$n- \mu$$ штук значений координат $$s_{i_j}(t), j=1, \dots, \mu$$, номера которых выбраны произвольным образом, замещены символом неопределенности $$x$$. Легко показать, что путем подходящих перестановок строк и столбцов характеристических матриц линейный автомат $$\hat A$$ всегда может быть преобразован в такой изоморфный ему ЛА $$\tilde A$$, у которого ОС (12.2) отображается при этом в ОС (12.1). Поэтому для простоты записи, но не теряя при этом общности, примем первый вариант (12.1) определения ОС.
Далее условимся о следующих обозначениях: если $$H$$ есть матрица, то через $$[H]_a$$ обозначим матрицу с $$a$$ штук строками, совпадающими с первыми $$a$$ строками матрицы $$H$$. Аналогичное обозначение используем и для вектора: $$[\bar s]_a$$ - это вектор размерности $$a$$, у которого координаты совпадают с $$a$$ первыми координатами вектора $$\bar s$$.
ЛА с заданной величиной $$\mu$$, определяющей для ЛА пространство обобщенных состояний, условимся обозначать как $$\mu$$ -ЛА.
Введем для $$\mu$$ -ЛА понятие обобщенной диаграммы переходов (ОДП). ОДП для $$\mu$$ -ЛА над полем $$GF(p)$$ назовем ориентированный граф, содержащий $$p^{\mu}$$ вершин, взаимно однозначно соответствующих каждому ОС этого автомата. Две вершины $$\bar a$$ и $$\bar b$$ в ОДП соединяются дугой, ведущей из $$\bar a$$ в $$\bar b$$, помеченной входным символом $$\bat u$$ $$\mu$$ -ЛА, если существуют по крайней мере два таких "традиционных" состояния $$\bar s$$ и $$\tilde s$$ из $$S_n$$, что $$[s]_{\mu}=\bar a, [s]_{\mu}=\bar b, \tilde s=A\bar s+B\bar u$$.
Отметим различие между "традиционной" диаграммой переходов ЛА [19] и ОДП: в "традиционной" диаграмме каждой ее дуге, помеченной входным символом $$\bar u$$, соответствует единственный выходной символ (реакция ЛА на вход $$\bar u$$ в состоянии $$\bar s$$ ), а в ОДП некоторой дуге может соответствовать несколько выходных символов. Назовем ОДП сильно связной, если в ней для любой пары вершин $$\bar a$$ и $$\bar b$$ существует путь, ведущий из $$\bar a$$ в $$\bar b$$. Соответствующий этой ОДП $$\mu$$ -ЛА будем называть $$\mu$$ -сильно связным.
Понятно, что любому пути в ОДП из $$\bar a$$ в $$\bar b$$ соответствует некоторое входное слово $$\mu$$ -ЛА, возможно не одно, переводящее его из ОС $$\bar a$$ в ОС $$\bar b$$.
По аналогии с [19] $$\mu$$ -ЛА назовем $$k$$ -управляемым, если для любых двух его обобщенных состояний $$\bar a$$ и $$\bar b$$ существует входное слово длины $$k$$, переводящее его из $$\bar a$$ в $$\bar b$$. Очевидно, что $$k$$ -управляемый $$\mu$$ -ЛА является $$\mu$$ -сильно связным.
Теорема 12.1. $$\mu$$ -ЛА является $$\mu$$ -управляемым тогда и только тогда, когда ранг матрицы
$$[L_k]_{\mu}=[A^{k-1}B, A^{k-2}B, \dots, AB,B]_{\mu}$$равен $$\mu$$.
Доказательство. Пусть $$[\bar s]_{\mu}$$ и $$[\tilde s]_{\mu}$$ - различные произвольные ОС рассматриваемого $$\mu$$ -ЛА. По определению $$k$$ -управляемости существует такая входная последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k-1)$$ длины $$k$$, которая переводит $$\mu$$ -ЛА из $$[\bar s]_{\mu}$$ в $$[\tilde s]_{\mu}$$. Тогда на основании формулы (1.3) можно записать:
$$[\bar s]_{\mu}=[A^k \tilde s+A^{k-1}B\bar u(0)+\dots |AB\bar u(k-2)+B\bar u(k-1)]_{\mu}$$Отсюда следует, что
$$[\bar s-A^k\tilde s]_{\mu}=[A^{k-1}B\bar u(0)+ \dots +AB\bar u(k-2)+b\bar u(k-1)]_{\mu}=\\ =[L_k[\bar u(0), \bar u(1), \dots, \bar u(k-1)]']_{\mu}$$Поскольку $$\bar s-A^k\tilde s$$ может быть любым $$n$$ -мерным вектором, $$[\bar s-A^k\tilde s]_{\mu}$$ также может быть любым $$\mu$$ -мерным вектором. В силу этого последнее равенство можно записать в виде
$$[L_k \hat u]_{\mu}$$где $$\hat u=[\bar u(0), \bar u(1), \dots, \bar u(k-1)]'$$, и интерпретировать его как СЛАУ относительно неизвестных, являющихся координатами вектора $$\hat u$$.
Понятно, что существование входной последовательности, переводящей $$\mu$$ -ЛА из произвольного ОС $$[\tilde s]_{\mu}$$ в произвольное ОС $$[\bar s]_{\mu}$$, эквивалентно существованию решений выписанной выше системы при любых правых частях. Из алгебры известно [33], что необходимым и достаточным условием для этого является равенство ранга системы (12.3) величине $$\mu$$. Заметим, что при $$\mu =n$$, где $$n$$ - размерность ЛА, $$\mu$$ -
Путем вычислений можно убедиться, что
$$L_3=[A^2B,AB,B]= \left [ \begin {matrix} 010\\ 101\\ 111 \end {matrix} \right ]$$и $$\rank L_3=2$$. Тогда по теореме 12.1 этот ЛА не является сильно связным.
Положим $$\mu =2$$, тогда
$$[L_3]_2= \left [ \begin {matrix} 010\\ 101 \end {matrix} \right ]$$и $$rank [L_3]_2=2$$. По теореме 12.1 рассматриваемый $$\mu$$ -ЛА является 2-сильно связным. Таким образом, исходный ЛА не является сильно связным, однако в пространстве обобщенных состояний он становится 2-сильно связным.
Определим теперь понятие синхронизирующей последовательности для $$\mu$$ -ЛА в пространстве обобщенных состояний.
Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА назовем обобщенной СП (ОСП), если
$$\forall \bar s, \tilde s \in \tilde {S_{\mu}}\ \ [A^{k+1}\bar S+A^kB\bar u(0)+ \dots +B\bar u(k)]_{\mu}=[A^{k+1}\tilde s +A^kB \bar u(0)+ \dots +B \bar u(k)]_{\mu}$$Понятно, что при $$\mu =n$$, где $$n$$ - размерность ЛА, приведенное определение совпадает с определением обычной СП для этого же автомата. Перенося в (12.4) правую часть равенства влево и выполнив сокращения, получим
$$\forall \bar s, \tilde s \in S_{\mu}\ \ [A^{k+1}\bar s - A^k \tilde s)]_{\mu}=[0]_{\mu}$$где $$[0]=_{\mu}$$ - нулевой вектор размерности $$\mu$$. Поскольку в (12.5) $$\bar s$$ и $$\tilde s$$ могут быть любыми ОС из $$\tilde S_{\mu}$$, то (12.5) эквивалентно
$$\forall \bar s \in S_n\ \ [A^{k+1}\bar s]_{\mu}=[0]_{\mu}$$Из предиката (12.6) вытекает справедливость следующего утверждения.
Теорема 12.2. Для того чтобы $$\mu$$ -ЛА $$\tilde A$$ имела ОСП длины $$k+1$$, необходимо и достаточно, чтобы
$$[A^{k+1}]_{\mu}=[0]_{\mu}$$Как видим, эта теорема является аналогом теоремы 1.1 для обычного ЛА, т. е. ее естественным обобщением.
По аналогии с разделом 1.2 $$\mu$$ -ЛА условимся называть обобщенно синхронизируемым, если для него существует ОСП.
Рассмотрим ЛА над полем $$GF(2)$$, заданный следующими характеристическими матрицами:
$$A= \left [ \begin {matrix} 000\\ 010\\ 001 \end {matrix} \right ], B= \left [ \begin {matrix} 0\\ 0\\ 0 \end {matrix} \right ]$$Поскольку $$A \ne [0]$$, то для этого ЛА, как это следует из теоремы 1.1, СП длины 1 не существует. Положим $$\mu =1$$ и рассмотрим соответствующий 1-ЛА. Понятно, что состояние этого автомата в момент времени $$t+1$$ не зависит от состояния в момент $$t$$, так как $$B$$ есть нулевая матрица. Более того, для этого ЛА
$$s(t+1)=[0 s_2(t) s_2(t)]'$$Из последнего равенства следует, что
$$[s(t+1)]_1=[0]_1$$Последнее означает: любая входная последовательность длины 1 переводит 1-ЛА в одно и то же состояние $$[0]_1$$, т. е. любая такая последовательность является ОСП.
Таким образом, нами построен пример ЛА, не имеющего обычной СП некоторой фиксированной длины, но в то же время имеющего обобщенную СП такой длины.
Почти дословное повторение доказательства теоремы 1.2 позволяет установить справедливость ее аналога для $$\mu$$ -ЛА.
Теорема 12.3. Если для $$\mu$$ -ЛА существует хотя бы одна ОСП длины $$k$$, то обобщенными СП для него являются любые входные последовательности длины $$k$$ и более.
По аналогии с обобщенными СП введем понятия обобщенных УП и ДП для $$\mu$$ -ЛА $$\tilde A$$, полагая, что множеством его допустимых начальных состояний является множество, которое мы обозначим как $$\Init (\tilde A0$$.
Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА $$A$$ назовем обобщенной УП (ОУП), если
$$\forall \bar s(0), \tilde s(0) \in Init(\tilde A) \wedge_{d=0}^k[CA^d\bar s(0)+CA^{d-1}B\bar u(0)+ \dots +CB \bar u(d-1)+D\bar u(d)=\\ = CA^d \tilde s(0)+CA^{d-1}B\bar u(0)+ \dots +CB\bar u(d-1)+D\bar u(d)] \to\\ \to [A^{k+1}\bar s(0)+A^kB\bar u(0)+ \dots +AB\bar u(k-1)+B\bar u(k)]_{\mu}=\\ =[A^{k+1}\tilde s(0)+A^kB\bar u(0)+ \dots +AB\bar u(k-1)+B\bar u(k)]_{\mu}$$Входную последовательность $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ $$\mu$$ -ЛА $$\tilde A$$ назовем обобщенной ДП (ОДП), если
$$\forall \bar s(0), \tilde s(0) \in Init (\tilde A) \wedge_{d=0}^k[CA^d\bar s(0)+CA^{d-1}B\bar u(0)+ \dots +CB\bar u(d-1)+D\bar u(d)=\\ =CA^d \tilde s())+CA^{d-1}B\bar u(0)+ \dots + CB\bar u(d-1)+D\bar u(d)] \to [\bar s(0)]_{\mu}=[\tilde s(0)]_{\mu} $$Заметим, что содержательный смысл обобщенных УП и ДП тот же, что и обычных, но применительно к обобщенным состояниям. Ниже приводятся теоремы, которые содержат естественные обобщения результатов для обычных ЛА на ЛА, рассматриваемые в пространстве обобщенных состояний. Доказательства некоторых из этих утверждений опущены, поскольку могут быть получены за счет незначительного изменения уже приводившихся ранее доказательств.
Теорема 12.4. Для того чтобы $$\mu$$ -ЛА имел обобщенную УП длины $$k+1$$, необходимо и достаточно, чтобы
$$\forall \bar s \in \hat {Init}(\tilde A) (\exists k \ge 0 CA^k\bar s \ne [0]) \vee (\exists k \ge 0 [A^{k+1}\bar s]_{\mu}=[0]_{\mu})$$Здесь через $$\hat {\Init}(\tilde A)$$ обозначено множество состояний, представляющее собой всевозможные разности состояний из множества $$\Init (\tilde A)$$.
Теорема 12.5. Если у $$\mu$$ -ЛА $$\tilde A$$ размерности $$n$$ ранг характеристической матрицы $$C$$ равен $$n$$, то для него существует обобщенная УП длины 1.
Доказательство. Пусть $$\bar s$$ и $$\tilde s$$ - два различных начальных состояния $$\mu$$ -ЛА $$A$$ из множества допустимых. Через $$\bar y(0)$$ и $$\tilde y(0)$$ обозначим реакции этого автомата на входной символ $$\bar u(0)$$. Пусть $$[\bar {s_k}]_{\mu}$$ и $$[\tilde {s_k}]_{\mu}$$ - состояния $$\mu$$ -ЛА после подачи $$\bar u(0)$$. Если $$\bar u(0)$$ - обобщенная УП, то это означает, что
$$\forall \bar s, \tilde s \in \Init (\tilde A) \bar y(0)=\tilde y(0) \to [\bar {s_k}]_{\mu}=[\bar {s_k}]_{\mu}$$Предположим, что $$\bar u(0)$$ не является обобщенной УП, тогда
$$\exists \bar s, \tilde s \in \Init (\tilde A) \bar y(0)=\tilde y(0) \wedge [\bar {s_k}]_{\mu} \ne [\bar {s_k}]_{\mu}$$что эквивалентно
$$\exists \bar s, \tilde s \in \Init (\tilde A) C(\bar s - \tilde s)=[0] \wedge [\bar {s_k}]_{\mu} \ne [\bar {s_k}]_{\mu}$$Первый сомножитель в (12.7) можно интерпретировать как систему линейных
что противоречит условию теоремы. Отсюда следует ложность предиката (12.7) и, следовательно, справедливость теоремы.
Теорема 12.6. Если для $$\mu$$ -ЛА размерности $$n$$ существует хотя бы одна обобщенная УП длины $$k$$, то для этого автомата обобщенными УП являются любые входные последовательности длины $$k$$ и более.
Введем следующие обозначения: через $$K_t^{\mu}$$ и $$K_t^{(\mu)}$$ соответственно обозначим подматрицы матрицы
$$K_t=[C, CA, \dots, CA^{t-1}]'$$содержащие первые и соответственно последние $$\mu$$ ее столбцов.
Теорема 12.7. Для того чтобы $$\mu$$ -ЛА $$A$$ размерности $$n$$ имел обобщенную ДП длины $$t$$, необходимо и достаточно, чтобы ранг матрицы $$K_t^{\mu}$$ был равен $$\mu$$ и $$K_t^{(\mu)}=[0]$$.
Эта теорема является естественным обобщением теоремы 1.7. Два последующих утверждения являются аналогами теорем 1.8 и 1.9.
Теорема 12.8. Если для $$\mu$$ -ЛА существует хотя бы одна обобщенная ДП длины $$k$$, то для него обобщенными являются любые входные последовательности длины $$k$$ и более.
Теорема 12.9. Если для $$\mu$$ -ЛА размерности $$n$$ существуют обобщенные ДП, то длина таких минимальных последовательностей не превосходит $$n$$.
Заметим, что аналоги последней теоремы справедливы как для обобщенных СП, так и для обобщенных УП.
Выше были рассмотрены ЛА, в правых частях уравнений переходов и выходов которых фигурировали векторы и матрицы со значениями только в момент времени $$t$$. Вместе с тем многие реальные процессы и устройства требуют для своего описания использования уравнений с
Ниже будет использована классификация произвольных дискретных систем (ДС) с
Обыкновенная ДС - поведение ее описывается уравнением
$$\bar s(t+ \alpha )+A_1\bar s(t+ \alpha -1)+ \dots + A_{\alpha}\bar s(t)=B_0\bar u(t+ \beta)+ \dots +B_{\beta}\bar u(t), \beta < \alpha$$Для того чтобы движение обыкновенной ДС было однозначно определено при $$t \ge 0$$, для любого входа $$\bar u(t)$$ должны быть заданы начальные условия $$\bar s(0), \bar s(1), \dots, \bar s(\alpha -1)$$ и $$\bar u(0), \bar u(1), \dots, \bar u(\beta - 1)$$
ДС с запаздыванием по состоянию - поведение ее описывается уравнением
$$\bar s(t+1)=A\bar s(t)+A_1\bar s(t-h)+B\bar u(t)$$Для однозначного определения процесса $$\bar s(t)$$ при любом входе $$\bar u(t)$$ задаются начальные условия $$\bar s(0), \bar s(-1), \dots, \bar s(-h)$$, где $$h$$ - некоторое положительное целое число.
ДС с запаздыванием по управлению - поведение ее описывается уравнением
$$\bar s(t+1)=A\bar s(t)+B\bar u(t)+B_1\bar u(t-h)$$Для однозначности определения процесса $$\bar s(t)$$ при $$t \ge -$$ при любом входе $$\bar u(t)$$ должны быть заданы начальные условия $$\bar s(0)$$ и $$\bar u(0), \bar u(-1), \dots, \bar u(-h)$$, где $$h$$ - некоторое положительное целое число.
В этом разделе будут рассмотрены вопросы существования СП, УП и ДП и методы их построения для линейных
Для получения
Из приведенных выше описаний ДС можно заключить, что участвующие в них векторы $$\bar s(t)$$, вообще говоря, не всегда представляют собой состояние системы в общепринятом смысле, т. е. ту минимальную по объему информацию, которую необходимо знать в текущий момент времени $$t$$ для однозначного продолжения процесса $$\bar s(t)$$ при известном входе $$\bar u(t)$$ Учитывая сказанное, каждую из перечисленных выше ДС с
Рассмотрим вначале обыкновенную ДС, заданную уравнением (12.8). Состояние $$\bar z(t+\alpha)$$ этой ДС в произвольный момент времени $$t+\alpha$$ определим как вектор $$[\bar s(t), \bar s(t+1), \dots, \bar s(t + \alpha +1)]'$$ Тогда состояние, в которое она переходит при подаче входного сигнала $$\bar u(t+ \beta)$$, есть вектор $$\bar u(t+\alpha +1)=[\bar s(t+1), \dots, \bar s(t+ \alpha)]'$$. Таким образом, если эту ДС описывать в виде ЛА, то размерность такого ЛА есть величина $$n=m \alpha$$ а начальное состояние есть $$\bar z(0)=[\bar s(0), \bar s(1), \dots, \bar s(\alpha +1)]'$$ В качестве входного вектора $$\bar u(t+\beta)$$ этой ДС теперь будем использовать вектор $$\tilde u(t+\beta)=[\bar u(t), \bar u(t+1), \dots, \bar u(t+\beta)]'$$ С учетом изложенного, если описывать рассматриваемую ДС в виде ЛА, уравнение ее переходов состояний примет вид
$$\bar z(t+ \alpha +1)=A*\bar z(t+ \alpha)+B* \tilde u(t+\beta)$$Матрицы $$A*$$ и $$B*$$ имеют блочную структуру, которая описывается ниже. В роли блоков в матрице $$A*$$ выступают матрицы размерности $$m \times m$$, а число "блочных" строк и столбцов ее равно величине $$\alpha$$ Структура этой матрицы имеет следующий вид ( $$E_m$$ - единичная матрица размером $$m \times m$$ ):
$$A*= \left [ \begin {matrix} [0]E_m[0] \dots [0]\\ [0][0]E_m \dots [0]\\ \dots a \dots \dots \dots \dots \\ [0][0][0] \dots E_m\\ \A_{\alpha} -A_{\alpha -1} -A_{\alpha -2} \dots -A_1 \end {matrix} \right ] $$В роли блоков матрицы $$B*$$ выступают матрицы размерности $$m \times l$$. Число "блочных" строк в $$B*$$ равно $$\alpha$$, а число "блочных" столбцов - $$\beta +1$$. Структура этой матрицы такова:
$$B*= \left [ \begin {matrix} [0][0][0]\dots [0]\\ [0][0][0] \dots [0]\\ \dots \dots \dots \dots \dots\\ [0] [0][0] \dots [0]\\ B_{\beta}b_{\beta -1}B_{\beta -2} \dots B_0 \end {matrix} \right ]$$Непосредственной проверкой можно убедиться, что уравнение (12.11) с такими характеристическими матрицами задает линейный автомат, эквивалентный, с точки зрения функционирования, обыкновенной ДС, описанной разностным уравнением (1.1), откуда следует справедливость следующего утверждения:
Теорема 1.1 Для того чтобы ЛА с
Рассмотрим теперь ДС с
где матрицы $$A^{\cdot}$$ и $$B^{\cdot}$$ так же, как и в предыдущем случае, имеют блочную структуру. В роли блоков в матрице $$A^{\cdot}$$ выступают матрицы размерности $$m \times m$$, а число ее "блочных" строк и столбцов равно $$h+1$$:
$$A*= \left [ \begin {matrix} [0]E_m[0] \dots [0]\\ [0][0]E_m \dots [0]\\ \dots \dots \dots \dots \dots\\ [0][0][0] \dots E_m\\ A_1[0][0] \dots A \end {matrix} \right ]$$В роли блоков в матрице $$B*$$ выступают матрицы размерности $$m \times l$$, "блочных" строк в ней одна, а число столбцов - $$h+1$$:
$$B*=[[0] \dots [0]B]'$$Можно проверить, что уравнение (10.1) с приведенными характеристическими матрицами задают ЛА, эквивалентный, с точки зрения функционирования, ДС с
Рассмотрим, наконец, ДС с
Тогда очевидно, что основная характеристическая матрица соответствующего ЛА просто совпадает с матрицей $$A$$ из (1.1), а в роли матрицы $$B$$ в формуле (1.1) будет выступать "блочный" вектор
$$B*=[B[0] \dots [0] B_1]'$$Из изложенного следует, что условие существования СП для ДС с
Подводя итог, отметим, что каждой из перечисленных выше типов ДС можно поставить в соответствие такой ЛА без
Кроме того, для решения задачи о переводе ЛА с
где $$\bar s(t)=[s_1(t), s_2(t)]'$$ и $$\bar u(t)=[u_1(t)]'$$, т. е. $$m=2, l=1$$, а характеристические матрицы ДС имеют следующий вид:
$$A_1= \left [ \begin {matrix} 01\\ 00 \end {matrix} \right ], A_2= \left [ \begin {matrix} 00\\ 00 \end {matrix} \right ], B_0= \left [ \begin {matrix} 0\\ 1 \end {matrix} \right ], B_1= \left [ \begin {matrix} 1\\ 0 \end {matrix} \right ]$$Вычисления показывают, что эквивалентный рассматриваемой системе ЛА имеет следующие характеристические матрицы:
$$A*= \left [ \begin {matrix} 0010\\ 0001\\ 0001\\ 0000 \end {matrix} \right ], B*= \left [ \begin {matrix} 00\\ 00\\ 10\\ 01 \end {matrix} \right ]$$При этом состоянием ЛА и его входным вектором являются векторы:
$$\bar s(t)=[s_1(t), s_2(t), s_1(t+1), s_2(t+1]', \dots, \bar u(t)=[u_1(t), u_1(t+1)]'$$Пусть задано синхросостояние $$\tilde s=[0,1,0,1]'$$ и требуется найти такую входную последовательность, которая переводит ДС из произвольного начального состояния в синхросостояние $$\tilde s$$.
Легко проверить, что $$(A*)^3=[0]$$ откуда вытекает, что эквивалентный рассматриваемой системе ЛА синхронизируем и длина минимальной СП равна 3. Для нахождения искомой СП выпишем матричное уравнение вида (1.14) для нашего примера:
$$(A*)^2B* \tilde u(0)+A*B* \tilde u(1)+B*\tilde u(2)= \tilde s$$С учетом приведенных выше матриц $$A*$$ и $$B*$$ это уравнение принимает следующий вид:
$$\left [ \begin {matrix} 01\\ 00\\ 00\\ 00 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(0)\\ u_1(1) \end {matrix} \right ] + \left [ \begin {matrix} 10\\ 01\\ 10\\ 00 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(1)\\ u_2(1) \end {matrix} \right ] + \left [ \begin {matrix} 00\\ 00\\ 10\\ 01 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(2)\\ u_1(3) \end {matrix} \right ] = \left [ \begin {matrix} 0\\ 1\\ -\\ 1 \end {matrix} \right ] $$Перейдем от этого уравнения к равносильной системе, записанной в координатной форме:
$$u_1(1)+ u_1(1)=0, u_1(2)=1, u_1(1)+ u_1(2)=0, u_1(3)=1,$$где "+" - операция по модулю 2.
Легко проверить, что эта система совместна и ее решение таково:
$$u_1(0)=x, u_1(1)=1, u_1(2)=1, u_1(3)=0,$$где х означает безразличное значение (0 или 1). Следовательно, для рассматриваемой ДС в качестве СП, переводящей ее из произвольного начального состояния в заданное синхросостояние $$\tilde s$$, могут быть использованы две следующие входных последовательностей:
Коснемся теперь
Поскольку, как показано выше, каждый из рассматриваемых типов ДС соответствует эквивалентной ей ЛА без
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.