Перейдем теперь к описанию используемой нами модели БА. Условимся, что для входных и выходных символов БА, а также для состояний БА будут сохранены те же обозначения, что и для ЛА.
Предполагается, что БА $$\tilde A$$ задан над полем $$GF(p)=\{0,1, \dots , p-1\}$$.
Далее рассматриваются БА, функционирование которых описывается следующими системами уравнений состояний и выходов соответственно:
$$\bar s(t+1)=A\bar s(t)+(\sum_{i=1}^lF_iu_i(t))\bar s(t)+B\bar u(t)$$ $$\bar y(t)=C\bar s(t)+(\sum_{i=1}^lC_iu_i(t))\bar s(t)+D\bar u(t)$$где $$A, F_i$$ - матрицы размерности $$n \times n, B$$ - размерности $$n \times l; C, G_i$$ - размерности $$m \times n; D$$ - размерности $$m \times l$$.
Упомянутые матрицы будем называть далее характеристическими матрицами БА. Элементами всех этих матриц являются элементы поля $$GF(p) $$.
Введем следующие обозначения:
$$I(\bar u(t))=\sum_{i=1}^lF_iu_i(t),\\ J(\bar u(t))=\su,_{i=1}^lG_iu_i(t)$$Пусть задана входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ и пусть $$\bar s(0)$$ есть начальное состояние БА. Методом
Применительно к БА $$\tilde A$$ определение 1.1 СП $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ (в лекции 1) принимает следующий вид:
$$\forall \bar s_1, \bar s_2 \in S_n \left \{ \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s_1+\prod_{i=0}^t[A+I(\bar u(t-i))]B\bar u(0)+ \dots$$ $$+[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right \}=\left \{\prod_{i=0}^t[A+I(\bar u(t-i))] \bar s_2+$$ $$+[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right \}=\left { \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s_2+$$ $$+\prod_{i=0}^{t-1}[A+I(\bar u(t-i))]B\bar u(0)_+\dots +[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(k) \right \}$$Перенося в левую часть равенства (21.5) все выражения, стоящие в правой его части, получим
$$\forall \bar s \ne [0], |pi_{i=0}^t[A+I(\bar u(t-i))]\bar s=[0]$$где $$[0]$$ - нулевая матрица (в частности, вектор) соответствующей размерности.
Теорема 21.1. Для того чтобы входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была СП для БА $$\tilde A$$, необходимо и достаточно, чтобы выполнялось равенство
$$\prod_{i=0}^t[A+I(\bar u(t-i))]=[0]$$Доказательство. Докажем необходимость условия (21.7), поскольку его достаточность очевидна. Обозначим через $$H=[h_{ij}]$$ матрицу, представляющую собой левую часть (21.7). Пусть $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ есть СП, но тогда выполняется равенство (21.6). Поскольку $$\bar s$$ - произвольное состояние, то положим $$\bar s=[1,0,\dots ,0]'$$, при котором (21.6) становится равенством $$[h_{11} h_{21} \dots h_{n1}]'=[0]$$. Из этого равенства следует, что $$h_{i1}=0, i=\overline {1,n}$$. Полагая далее $$\bar s$$ равным векторам $$[0,1,0,\dots , 0]', \dots, [0, 0, \dots, 1]'$$, аналогичными рассуждениями придем к заключению, что и все остальные столбцы матрицы $$H$$, как и ее первый столбец, нулевые. Таким образом, из (21.6) следует (21.7), что и требовалось доказать.
Из (21.7) следует справедливость следующего утверждения.
Теорема 21.2. Для того чтобы входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была СП для БС $$\tilde A$$, достаточно, чтобы по крайней мере для одного из значений $$i=0,1, \dots, t$$ выполнялось равенство
$$[A+I(\bar u(t-i))]=[0]$$Приведем еще одно достаточное условие существования СП. Предварительно напомним, что квадратная матрица называется верхней (нижней) треугольной, если все ее элементы, лежащие на главной диагонали и ниже (выше) ее, нулевые.
Теорема 21.3. Если характеристические матрицы $$A$$ и $$F_i= \overline {1,l}$$, БС $$\tilde A$$ являются верхними (нижними) треугольными, то для этой БС существуют СП длины, не большей $$n$$, где $$n$$ - число строк и столбцов упомянутых матриц.
Доказательство. Пусть $$A$$ и $$F_i, i=\overline {1, l}$$, являются верхними треугольными матрицами. Тогда каждый сомножитель в произведении (21.7) также представляет собой матрицу того же типа. Условимся нумеровать диагонали этих матриц, лежащие выше главной диагонали и параллельные ей, числами $$1,2, \dots, n-1$$. Непосредственными вычислениями легко убедиться, что все элементы первой диагонали матрицы-произведения двух верхних треугольных матриц равны нулю. Если эту матрицу вновь умножить на верхнюю треугольную матрицу, т. е. взять произведение трех сомножителей из (21.7), то в результате получится матрица, у которой нулевыми будут элементы первой и второй диагонали. Отсюда методом индукции можно доказать, что произведение $$n$$ штук верхних треугольных матриц даст нулевую матрицу. Тогда на основании теоремы 21.1 рассматриваемая БА имеет СП, длина которой не превосходит $$n$$.
Для
Поскольку БА представляет собой
Опишем метод построения СП. Обратимся к равенству (21.7) и на его основе организуем пошаговый процесс поиска СП, начиная с СП длины 1 (при $$t=0$$ ), затем СП длины 2 (при $$t=1$$ ) и т. д. При варьировании величины $$t$$ равенство (21.7) будет принимать последовательно следующий вид:
$$A+I(\bar u(0))=[0],\\ [A+I(\bar u(1))][A+I(\bar u(0))]=[0],\\ ………………………………………,\\ [A+I(\bar u(t-1))][A+I(\bar u(t-2))] \dots [A+I(\bar u(0))]=[0]$$Поиск СП начнем с попытки решения первой из выписанных систем в (21.9), рассматривая в качестве неизвестных координаты вектора $$\bar u(0)$$. Эта неоднородная
Здесь элементы $$f_{ij}(\nu)$$ есть элементы матрицы $$F_{\nu}$$. Как известно [19], эта система будет совместной, если $$rank L = rank\ \tilde L$$, где $$\tilde L$$ - расширенная (добавлением столбца, состоящего из соответствующих элементов матрицы $$A$$ ) матрица той же системы. В случае совместности этой системы возможны два случая: 1) $$rank\ L = l$$ ; 2) $$rank\ L < l$$. В первом случае система имеет единственное решение, которое дает искомую СП. Во втором случае система имеет множество решений, каждому из которых соответствует своя СП. Поскольку решение системы отыскивается среди элементов конечного поля $$GF(p) $$, множество решений будет конечным.
Если упомянутая
Проиллюстрируем метод на примере БА над полем $$GF(2) $$, у которой $$n=3, l=2$$, а характеристические матрицы имеют следующий вид:
$$A= \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ] , F_i= \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ], F_2= \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] $$Первое равенство в (21.9) дает следующую систему уравнений:
$$\left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ] + \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] u_2(0)= \left [ \begin {matrix} 000\\ 000\\ 000 \end {matrix} \right ] $$Легко убедиться, что она несовместна, и потому выписываем вторую систему из (21.9):
$$\left ( \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]+ \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 100 \end {matrix} \right ]u_2(0) \right) \cdot\\ \cdot \left ( \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]+ \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ]u_1(1)+ \left [ \begin {matrix} 001\\ 000\\ 100 \end {matrix} \right ]u_2(1) \right )= \left [ \begin {matrix} 000\\ 000\\ 000 \end {matrix} \right ] $$После выполнения преобразований система примет вид
$$\left [ \begin {matrix} 1+(u_1(0)+u_2(0))u_2(1) 0 u_1(1)+u_2(1)+u_2(1)(u_1(0)+u_2(0))\\ 0u_1(0)u_1(1)0\\ u_2(0)+u_2(0)u_2(1)0u_2(0)(u_1(1)+u_2(1))+u_2(0)u_2(1) \end {matrix} \right ] =[0]$$В конечном счете, приравнивая каждый элемент последней матрицы нулю, получим систему уравнений
$$(u_1(0)u_2(0))u_2(1)+1=0,\\ u_1(1)+u_2(1)+u_2(1)(u_1(0)+u_2(0))=0,\\ u_2(0)+u_2(0)u_2(1)=0,\\ u_2(0)(u_1(1)+u_2(1))+u_2(0)u_2(1)=0$$Напомним, что решение мы ищем в поле $$GF(2) $$ и потому операция "+" - это сложение по модулю 2. Легко убедиться, что эта система имеет два решения:
Таким образом, рассматриваемый БА имеет две СП: $$\bar u(0)=[1,0]', \bar u(1)=[0,1]'$$ и $$\bar u(0)=[0,1]', \bar u(1)=[0,1]'$$.
Поиск требуемой входной последовательности осуществим следующим образом. В (21.1) положим $$t=0$$ и вместо $$\bar s(0)$$ подставим состояние $$\bar s_1$$, а вместо $$\bar s(1)$$ - состояние $$\bar s_2$$. Полученное выражение будем рассматривать как систему линейных алгебраических уравнений относительно неизвестных $$u_1(0), \dots, u_l(0)$$. Очевидно, что если эта система совместна, то ее решению соответствует искомая входная последовательность. Если таких решений будет несколько, то это говорит о существовании нескольких путей перехода из $$\bar s_1>$$ в $$\bar s_2$$, а отсутствие решений - о невозможности требуемого перехода с помощью входной последовательности длины 1. В последнем случае сделаем попытку найти соответствующую последовательность длины 2, положив в (21.3) $$t=1$$ и заменив $$\bar s(t)$$ и $$\bar s(t+1)$$ соответственно на $$\bar s_1$$ и $$\bar s_2$$. Если полученная система вновь окажется несовместной, то продолжим описанный процесс далее аналогичным образом. Если до значения $$t=w-2$$ включительно, где $$w$$ - число состояний БА, все последовательно получаемые
Проиллюстрируем описанный метод на примере БА над полем $$GF(2) $$, уже рассмотренном выше, где характеристическая матрица $$B$$ имеет вид
$$B= \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ] $$Пусть требуется найти входную последовательность, переводящую заданную БС из состояния $$\bar s_1=[1,1,1]'$$ в состояние $$\bar s_2=[0,0,1]'$$.
Выпишем систему уравнений, используя выражение (6.1):
$$\left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]\times \left [ \begin {matrix} 1\\ 1\\ 1 \end {matrix} \right ] + \left ( \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] u_2(0) \right ) + \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(0)\\ u_2(0) \end {matrix} \right ] = \left [ \begin {matrix} 0\\ 0\\ 1 \end {matrix} \right ] $$Выполнив соответствующие преобразования, в итоге получим систему
$$\left [ \begin {matrix} u_2(0)+1\\ u_1(0)+u_2(0)\\ u_1(0) \end {matrix} \right ]= \left [ \begin {matrix} 0\\ 0\\ 1 \end {matrix} \right ] $$Эта система имеет единственное решение $$u_1(0)=1, u_2(0)=1$$, следовательно, искомая входная последовательность есть $$[1,1]'$$.
Условия существования такой последовательности даются следующей теоремой.
Теорема 21.4. Для того чтобы последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была УП для БА $$\tilde A$$, необходимо и достаточно, чтобы для каждого ненулевого состояния $$\bar s \in S_n$$ выполнялось по крайней мере одно из двух условий:
Здесь знак $$\wedge_{d=0}^t(\vee_{d=0}^t)$$ означает дизъюнкцию (конъюнкцию) выражений, стоящих за этим знаком и получаемых при изменении индекса $$d$$ от 0 до $$t$$. Условимся о следующем: если при вычислении $$I(\bar u(\nu))$$ и $$J(\bar u(\nu))$$ окажется, что $$\nu \lt; 0$$ при некоторых $$i$$ и $$d$$, то в соответствующем выражении сомножители $$[A+I(\bar u(\nu))]$$ и $$[C+J(\bar u(\nu))]$$ полагаются равными
Доказательство. Применительно к БА $$\tilde A$$ определение 1.2 УП принимает следующий вид: последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ называется УП, если
$$\forall \bar s_1, \bar s_2, \in S_n, \wedge_{d=0}^t\{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]s_1+\dots\\ \dots +[C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d)=[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(d-i-1)]\bar s_2+ \dots\\ \dots =[C+j(\bar u(d))]B\bar u(0)+ \dots + [A+I(u(t))]B\bar u(t-1)+B\bar u(t)=\\ =\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]B\bar u(0)+\dots +[A+I(u(t))]B\bar u(t-1)+B\bar u(t)=\\ =\prod_{i=0}^{t-1}[A+I(\bar u(t-i))]\bar s_2+\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]B\bar u(0)+\dots +[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right ]$$Преобразуем каждое в отдельности равенство, стоящее до и после знака импликации, перенеся все в левые их части и осуществив соответствующие сокращения, в результате чего получим
$$\forall \bar s_1, \bar s_2 \in S_n, [\wedge_{d=0}^t[C+J(\bar u(d))]\prod_{i=0}^t[A+I(d-i-1)](\bar s_1-\bar s_2)=[0]] \to\\ \to \prod_{i=0}^t[A+I(\bar u(t-i))](\bar s_1- \bar s_2)=[0]$$Поскольку $$\bar s_1$$ и $$\bar s_2$$ - произвольные не совпадающие между собой состояния из $$S_n$$, то и состояние $$\bar s=\bar s_1 - \bar s_2$$ также может быть любым ненулевым состоянием из $$S_n$$. Отсюда следует, что последний предикат эквивалентен предикату
$$\forall \bar s \ne [0] [\wedge_{d=0}^t[C+J(\bar u(d))] \prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s=[0] \to \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s=[0]$$Поскольку $$X \to Y$$ эквивалентно $$\bar X \vee Y$$, то последний предикат эквивалентен следующему предикату
$$\forall \bar s \ne [0] [\vee_{d=0}^t[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar \ne [0]] \vee \vee \prod_{i=0}t[A+I(\bar u(t-i))]\bar s=[0]$$Из этого предиката и следует справедливость теоремы.
Проиллюстрируем предложенный метод на примере БА над полем $$GF(2) $$, у которого $$n=3, l=2, m=2$$, а характеристические матрицы таковы:
$$A= \left [ \begin {matrix} 100\\ 010\\ 001 \end {matrix} \right ] , B= \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ], F_1= \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ], F_2= \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] ,\\ C= \left [ \begin {matrix} 001\\ 011 \end {matrix} \right ], D= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ] , G_1= \left [ \begin {matrix} 101\\ 011 \end {matrix} \right ], G_2= \left [ \begin {matrix} 011\\ 101 \end {matrix} \right ] $$Первое условие теоремы 21.4 при $$d=0$$ порождает систему уравнений
$$[C+J(\bar u(0))]\bar s= \left [ \begin {matrix} u_1(0) u_2(0) u_1(0)+u_2(0)+1\\ u_2(0) u_1(0)+1 u_1(0)+u_2(0)+1 \end {matrix} \right ] * \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0] $$Рассмотрим теперь все возможные векторы $$\bar u(0):[0,0]' [1,0]', [1,0]', [1,1]'$$. Их подстановка в выписанную нелинейную систему порождает четыре следующих системы:
$$begin {cases} s_3=0,\\ s_2+s_3=0 \end {cases}, begin {cases} s_2=0,\\ s_1+s_2=0 \end {cases}, begin {cases} s_1,,\ 0=0, \end {cases}, begin {cases} s_1+s_2+s-3=0,\\ s_1+s_3=0 \end {cases}$$Каждая из этих систем относительно неизвестных $$s_1, s_2, s_3$$ имеет не единственное решение, и поэтому условие 1 теоремы 21.4 для всех входных последовательностей длины 1 не выполняется. Перейдем теперь к проверке условия 2 той же теоремы, которое при $$d=0$$ порождает систему
$$[A+I(\bar u(0))]\bar s= \left [ \begin {matrix} 10u_i(0)+u_2(0)\\ 0u_1(0)+10\\ u_2(0)0u_2(0)+1 \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0]$$Легко проверить, что эта система имеет единственное (нулевое) решение при любом $$\bar u(0)$$, т. е. условие 2 также не выполняется. Поэтому перейдем к поиску УП длины 2, полагая $$d=1$$.
Условие 1 теоремы 21.4 порождает следующую систему уравнений:
$$begin {cases} [C+J(\bar u(0))]\bar s=[0],\\ {C+J(\bar u(1))][A+I(\bar u(0))]\bar s=[0] \end {cases}$$В координатной записи эта же система имеет следующий вид:
$$\left [ \begin {matrix} u_1(0)u_2(0)u_1(0)+u_2(0)+1\\ u_2(0)u_1(0)+1u_1(0)+u_2(0)+1 \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0],\\ \left [ \begin {matrix} [u_1(1)+u_2(1)+1]*u_2(1)[u_1(0)+1]u_1(1)[u_1(0)+u_2(0)]+\\ *u_2(0)+u_1(1)+u_1(1)+u_2(1)+1][u_2(0)+1]\\ [u_1(1)+u_2(1)+1]*[u_1(1)+1]*u_2(1)[u_1(0)+u_2(0)]+\\ *u_2(0)+u_2(01)*[u_1(0)+1]+[u_1(1)+u_2(1)+1][u_2(0)+1] \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0]$$Теперь необходимо рассмотреть все возможные пары векторов $$\bar u(0), \bar u(1)$$ и, подставляя их в выписанную выше систему, получить множество систем линейных уравнений относительно неизвестных $$s_1, s_2, s_3$$. Вычисления показывают, что, например, для пар входных векторов $$\bar u(0)=[1,1]', \bar u(1)=[0,0}'$$ и $$\bar u(0)=[0,0]', \bar u(1)=[1,0]'$$ первая подсистема $$[C+J(\bar u(0))]\bar s=[0]$$ имеет ненулевое решение ( $$\bar s=[1,0,1]'$$ и $$\bar s=[1,0,0]'$$ соответственно), а вторая подсистема для этих же пар входных векторов имеет единственное (нулевое) решение. Последний факт означает, что условие 1 теоремы выполняется, следовательно, обе приведенные входные последовательности являются для рассматриваемого БА установочными. Заметим, что этот БА имеет и другие УП длины 2, которые находятся аналогично.
Для подтверждения сказанного, в приведенной таблице показаны реакции рассматриваемого БА на две найденные входные последовательности и соответствующие конечные состояния. Состояния БА в таблице закодированы в виде десятичного эквивалента двоичного представления вектора-состояния. Так, например, состояние $$\bar s=[1,0,0]'$$ закодировано числом 4, состояние $$\bar s=[1,0,1]'$$ - числом 5 и т. д.
| Входное слово 3, 0 | Входное слово 0, 2 | |||
|---|---|---|---|---|
| Начальное состояние | Реакция БА | Конечное состояние | Реакция БА | Конечное состояние |
| 0 | 3, 2 | 7 | 0, 2 | 5 |
| 1 | 0, 2 | 7 | 3, 2 | 0 |
| 2 | 1, 2 | 7 | 1, 2 | 5 |
| 3 | 2, 2 | 7 | 2, 2 | 0 |
| 4 | 0, 1 | 2 | 0, 0 | 1 |
| 5 | 3, 1 | 2 | 3, 0 | 5 |
| 6 | 2, 1 | 2 | 1, 0 | 1 |
| 7 | 1, 1 | 2 | 2, 0 | 4 |
Аналогичная кодировка в таблице принята для входных и выходных векторов. Так, УП $$[0,0]', [1,0]'$$ закодирована как последовательность 0, 2; а УП $$[1,1]', [0,0]'$$ - как последовательность 3, 0.
Условия существования такой последовательности даются следующей теоремой.
Теорема 21.5. Для того чтобы последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ была ДП для БА $$\tilde A$$, необходимо и достаточно, чтобы
$$rank \left [ \begin {matrix} C+J(\bar u(0)\\ [C+J(\bar u(1))][A+I(\bar u(0))]\\ ………………………………….\\ [C+J(\bar u(t))]\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))] \end {matrix} \right ]=n, \ \mbox {где} \ {n} \ \mbox {размерность БА}$$Доказательство. Применительно к БА определение 1.3 ДП принимает следующий вид: последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ называется ДП, если
$$\forall \bar s_1, \bar s_2 \in S_n \wedge_{d=0}^{t} \left \{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s_1+$$ $$\dots, [C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d)=[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s_2+$$ $$\dots +[C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d) \right \} \to \bar s_1=\bar s_2$$Выполнив преобразование так же, как это делалось в предыдущем доказательстве, получим предикат
$$\forall \bar s_1, s_2 \in S_n \wedge_{d=0}^{t} \left \{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I (\bar u(d-i-1))](\bar s_1-\bar s_2)=0] \right \} \to \bar s_1=\bar s_2$$Если последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ является для БА диагностической, то это означает, что знание реакции БА на нее позволяет однозначно найти ее начальное состояние. Выходы БА на ДП, используя (21.4), можно представить как функции от начального состояния $$\bar s(0)$$:
$$\bar y(0)=[C+J(\bar u(0))]\bar s(0)+D\bar u(0),\\ \bar y(1)=[C+J(\bar u(1))][A+I(\bar u (1))]\bar s(0)+[C+J(\bar u(1))]B\bar u(0)+D\bar u(1),\\ ………………………………….\\ \bar y(t)=[C+J(\bar u(t))]\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]\bar s(0)+ \dots +D\bar u(t)$$Поскольку ДП $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ и реакция БА на нее известны, выписанные соотношения можно представить в виде
$$[C+J(\bar u(0))]\bar s(0)= Ф_0(\bar u(0)),\\ [C+J(\bar u(1))][A+I(\bar u(0))]\bar s(0)= Ф_1(\bar u(0), \bar u(1)),\\ ………………………………………………………\\ [C+J(\bar u(t))] \prod_{i=0}^{i-1}[A+I(\bar u(t-i-1))]\bar s(0)= Ф_t(\bar u(0), \dots, \bar u(t)))$$где $$Ф_i(\bat u(0), \dots, \bar u(i)), (i=\overline {0,t}) $$ - некоторые значения из поля $$GF(p) $$.
Выписанную совокупность соотношений можно интерпретировать как систему линейных уравнений относительно неизвестных $$s_1(0), \dots, s_n(0)$$, являющихся координатами вектора-состояния $$\bar s(0)$$. Однозначность восстановления начального состояния $$\bar s(0)$$ по наблюдаемой реакции $$\bar y(0), \bar y(1), \dots, \bar y(t)$$ при известной входной последовательности $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ означает, что представленная
Опишем теперь метод нахождения ДП для заданного БА, основанный на теореме 21.5. Метод состоит в переборе всевозможных входных слов $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ последовательно для $$t=1,2,3,\dots$$ и вычислении для очередного проверяемого слова ранга матрицы, фигурирующей в теореме 21.5. Если этот ранг окажется равным n, то проверяемое входное слово является искомой ДП. В противном случае указанный процесс продолжается далее до тех пор, пока значение параметра $$t$$ не достигнет своего предельного значения, равного верхней границе длины минимальной ДП для рассматриваемого БА. Если и при этом значении $$t$$ ДП не будет найдена, то для рассматриваемого БА ее не существует. Проиллюстрируем этот метод на примере БА, для которого выше осуществлялся поиск УП. Для этого БА приведем некоторые "составляющие" матрицы в условиях теоремы 21.5:
$$[C+J(\bar u(0))]= \left [ \begin {matrix} u_1(0)u_2(0)u_1(0)+u_2(0)+1\\ u_2(0)U_1(0)+1 u_1(0)+u_2(0)+1 \end {matrix} \right ],\\ [C+J(\bar u(0))][A+I(\bar u(0))]= \left [ \begin {matrix} [u_1(1)+u_2(1)]*u_2(0)+u_1(1) u_2(1)[u_1(0)+1]u_1(1)[u_1(0)+u_2(0)]+[u_1(1)+u_2(1)+1][u_2(0)+1]\\ [u_1(1)+u_2(1)]*u_2(0)+u_1(1)[u_1(1)+1][u_1(0)+1]u_2(1)[u_1(0)+u_2(0)]+[u_1(1)+u_2(1)+1][u_2(0)+1] \end {matrix} \right ] $$Размерность матрицы $$[C+J(\bar u(0))]$$ равна $$2 \times 3$$, следовательно, ее ранг не может превышать 2. Но тогда, поскольку для рассматриваемой БС $$n=3$$, условие теоремы 21.5 при $$t=0$$ не может быть выполнено. В связи с этим перейдем к перебору всевозможных входных слов длины 2 (полагая $$t=1$$ ). Рассмотрим, например, входное слово $$\bar u(0), \bar (1)=3,0$$. Для него матрица из условия теоремы 21.5 имеет вид
$$\left [ \begin {matrix} C+J(\bat u(0))\\ [C+J(\bar u(0))][A+I(\bar u(0))] \end {matrix} \right ]= \left [ \begin {matrix} 100\\ 100\\ 111\\ 101 \end {matrix} \right ] $$Поскольку ранг этой матрицы равен 3, проверяемое слово 3, 0 есть ДП. В этом можно убедиться по данным, приведенным в таблице. Для другого входного слова $$\bar u(0), \bar u(1)=0,2$$ та же матрица из условий теоремы равна
$$\left [ \begin {matrix} 001\\ 011\\ 100\\ 000 \end {matrix} \right ] $$Ранг ее также равен 3, следовательно, входное слово 0, 2 также является ДП для рассматриваемого БА. Таким образом, оба входных слова 3, 0 и 0, 2 являются для рассматриваемого БА одновременно УП и ДП.
Перейдем теперь к описанию используемой нами модели БА. Условимся, что для входных и выходных символов БА, а также для состояний БА будут сохранены те же обозначения, что и для ЛА.
Предполагается, что БА $$\tilde A$$ задан над полем $$GF(p)=\{0,1, \dots , p-1\}$$.
Далее рассматриваются БА, функционирование которых описывается следующими системами уравнений состояний и выходов соответственно:
$$\bar s(t+1)=A\bar s(t)+(\sum_{i=1}^lF_iu_i(t))\bar s(t)+B\bar u(t)$$ $$\bar y(t)=C\bar s(t)+(\sum_{i=1}^lC_iu_i(t))\bar s(t)+D\bar u(t)$$где $$A, F_i$$ - матрицы размерности $$n \times n, B$$ - размерности $$n \times l; C, G_i$$ - размерности $$m \times n; D$$ - размерности $$m \times l$$.
Упомянутые матрицы будем называть далее характеристическими матрицами БА. Элементами всех этих матриц являются элементы поля $$GF(p) $$.
Введем следующие обозначения:
$$I(\bar u(t))=\sum_{i=1}^lF_iu_i(t),\\ J(\bar u(t))=\su,_{i=1}^lG_iu_i(t)$$Пусть задана входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ и пусть $$\bar s(0)$$ есть начальное состояние БА. Методом
Применительно к БА $$\tilde A$$ определение 1.1 СП $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ (в лекции 1) принимает следующий вид:
$$\forall \bar s_1, \bar s_2 \in S_n \left \{ \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s_1+\prod_{i=0}^t[A+I(\bar u(t-i))]B\bar u(0)+ \dots$$ $$+[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right \}=\left \{\prod_{i=0}^t[A+I(\bar u(t-i))] \bar s_2+$$ $$+[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right \}=\left { \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s_2+$$ $$+\prod_{i=0}^{t-1}[A+I(\bar u(t-i))]B\bar u(0)_+\dots +[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(k) \right \}$$Перенося в левую часть равенства (21.5) все выражения, стоящие в правой его части, получим
$$\forall \bar s \ne [0], |pi_{i=0}^t[A+I(\bar u(t-i))]\bar s=[0]$$где $$[0]$$ - нулевая матрица (в частности, вектор) соответствующей размерности.
Теорема 21.1. Для того чтобы входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была СП для БА $$\tilde A$$, необходимо и достаточно, чтобы выполнялось равенство
$$\prod_{i=0}^t[A+I(\bar u(t-i))]=[0]$$Доказательство. Докажем необходимость условия (21.7), поскольку его достаточность очевидна. Обозначим через $$H=[h_{ij}]$$ матрицу, представляющую собой левую часть (21.7). Пусть $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ есть СП, но тогда выполняется равенство (21.6). Поскольку $$\bar s$$ - произвольное состояние, то положим $$\bar s=[1,0,\dots ,0]'$$, при котором (21.6) становится равенством $$[h_{11} h_{21} \dots h_{n1}]'=[0]$$. Из этого равенства следует, что $$h_{i1}=0, i=\overline {1,n}$$. Полагая далее $$\bar s$$ равным векторам $$[0,1,0,\dots , 0]', \dots, [0, 0, \dots, 1]'$$, аналогичными рассуждениями придем к заключению, что и все остальные столбцы матрицы $$H$$, как и ее первый столбец, нулевые. Таким образом, из (21.6) следует (21.7), что и требовалось доказать.
Из (21.7) следует справедливость следующего утверждения.
Теорема 21.2. Для того чтобы входная последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была СП для БС $$\tilde A$$, достаточно, чтобы по крайней мере для одного из значений $$i=0,1, \dots, t$$ выполнялось равенство
$$[A+I(\bar u(t-i))]=[0]$$Приведем еще одно достаточное условие существования СП. Предварительно напомним, что квадратная матрица называется верхней (нижней) треугольной, если все ее элементы, лежащие на главной диагонали и ниже (выше) ее, нулевые.
Теорема 21.3. Если характеристические матрицы $$A$$ и $$F_i= \overline {1,l}$$, БС $$\tilde A$$ являются верхними (нижними) треугольными, то для этой БС существуют СП длины, не большей $$n$$, где $$n$$ - число строк и столбцов упомянутых матриц.
Доказательство. Пусть $$A$$ и $$F_i, i=\overline {1, l}$$, являются верхними треугольными матрицами. Тогда каждый сомножитель в произведении (21.7) также представляет собой матрицу того же типа. Условимся нумеровать диагонали этих матриц, лежащие выше главной диагонали и параллельные ей, числами $$1,2, \dots, n-1$$. Непосредственными вычислениями легко убедиться, что все элементы первой диагонали матрицы-произведения двух верхних треугольных матриц равны нулю. Если эту матрицу вновь умножить на верхнюю треугольную матрицу, т. е. взять произведение трех сомножителей из (21.7), то в результате получится матрица, у которой нулевыми будут элементы первой и второй диагонали. Отсюда методом индукции можно доказать, что произведение $$n$$ штук верхних треугольных матриц даст нулевую матрицу. Тогда на основании теоремы 21.1 рассматриваемая БА имеет СП, длина которой не превосходит $$n$$.
Для
Поскольку БА представляет собой
Опишем метод построения СП. Обратимся к равенству (21.7) и на его основе организуем пошаговый процесс поиска СП, начиная с СП длины 1 (при $$t=0$$ ), затем СП длины 2 (при $$t=1$$ ) и т. д. При варьировании величины $$t$$ равенство (21.7) будет принимать последовательно следующий вид:
$$A+I(\bar u(0))=[0],\\ [A+I(\bar u(1))][A+I(\bar u(0))]=[0],\\ ………………………………………,\\ [A+I(\bar u(t-1))][A+I(\bar u(t-2))] \dots [A+I(\bar u(0))]=[0]$$Поиск СП начнем с попытки решения первой из выписанных систем в (21.9), рассматривая в качестве неизвестных координаты вектора $$\bar u(0)$$. Эта неоднородная
Здесь элементы $$f_{ij}(\nu)$$ есть элементы матрицы $$F_{\nu}$$. Как известно [19], эта система будет совместной, если $$rank L = rank\ \tilde L$$, где $$\tilde L$$ - расширенная (добавлением столбца, состоящего из соответствующих элементов матрицы $$A$$ ) матрица той же системы. В случае совместности этой системы возможны два случая: 1) $$rank\ L = l$$ ; 2) $$rank\ L < l$$. В первом случае система имеет единственное решение, которое дает искомую СП. Во втором случае система имеет множество решений, каждому из которых соответствует своя СП. Поскольку решение системы отыскивается среди элементов конечного поля $$GF(p) $$, множество решений будет конечным.
Если упомянутая
Проиллюстрируем метод на примере БА над полем $$GF(2) $$, у которой $$n=3, l=2$$, а характеристические матрицы имеют следующий вид:
$$A= \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ] , F_i= \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ], F_2= \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] $$Первое равенство в (21.9) дает следующую систему уравнений:
$$\left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ] + \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] u_2(0)= \left [ \begin {matrix} 000\\ 000\\ 000 \end {matrix} \right ] $$Легко убедиться, что она несовместна, и потому выписываем вторую систему из (21.9):
$$\left ( \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]+ \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 100 \end {matrix} \right ]u_2(0) \right) \cdot\\ \cdot \left ( \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]+ \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ]u_1(1)+ \left [ \begin {matrix} 001\\ 000\\ 100 \end {matrix} \right ]u_2(1) \right )= \left [ \begin {matrix} 000\\ 000\\ 000 \end {matrix} \right ] $$После выполнения преобразований система примет вид
$$\left [ \begin {matrix} 1+(u_1(0)+u_2(0))u_2(1) 0 u_1(1)+u_2(1)+u_2(1)(u_1(0)+u_2(0))\\ 0u_1(0)u_1(1)0\\ u_2(0)+u_2(0)u_2(1)0u_2(0)(u_1(1)+u_2(1))+u_2(0)u_2(1) \end {matrix} \right ] =[0]$$В конечном счете, приравнивая каждый элемент последней матрицы нулю, получим систему уравнений
$$(u_1(0)u_2(0))u_2(1)+1=0,\\ u_1(1)+u_2(1)+u_2(1)(u_1(0)+u_2(0))=0,\\ u_2(0)+u_2(0)u_2(1)=0,\\ u_2(0)(u_1(1)+u_2(1))+u_2(0)u_2(1)=0$$Напомним, что решение мы ищем в поле $$GF(2) $$ и потому операция "+" - это сложение по модулю 2. Легко убедиться, что эта система имеет два решения:
Таким образом, рассматриваемый БА имеет две СП: $$\bar u(0)=[1,0]', \bar u(1)=[0,1]'$$ и $$\bar u(0)=[0,1]', \bar u(1)=[0,1]'$$.
Поиск требуемой входной последовательности осуществим следующим образом. В (21.1) положим $$t=0$$ и вместо $$\bar s(0)$$ подставим состояние $$\bar s_1$$, а вместо $$\bar s(1)$$ - состояние $$\bar s_2$$. Полученное выражение будем рассматривать как систему линейных алгебраических уравнений относительно неизвестных $$u_1(0), \dots, u_l(0)$$. Очевидно, что если эта система совместна, то ее решению соответствует искомая входная последовательность. Если таких решений будет несколько, то это говорит о существовании нескольких путей перехода из $$\bar s_1>$$ в $$\bar s_2$$, а отсутствие решений - о невозможности требуемого перехода с помощью входной последовательности длины 1. В последнем случае сделаем попытку найти соответствующую последовательность длины 2, положив в (21.3) $$t=1$$ и заменив $$\bar s(t)$$ и $$\bar s(t+1)$$ соответственно на $$\bar s_1$$ и $$\bar s_2$$. Если полученная система вновь окажется несовместной, то продолжим описанный процесс далее аналогичным образом. Если до значения $$t=w-2$$ включительно, где $$w$$ - число состояний БА, все последовательно получаемые
Проиллюстрируем описанный метод на примере БА над полем $$GF(2) $$, уже рассмотренном выше, где характеристическая матрица $$B$$ имеет вид
$$B= \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ] $$Пусть требуется найти входную последовательность, переводящую заданную БС из состояния $$\bar s_1=[1,1,1]'$$ в состояние $$\bar s_2=[0,0,1]'$$.
Выпишем систему уравнений, используя выражение (6.1):
$$\left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ]\times \left [ \begin {matrix} 1\\ 1\\ 1 \end {matrix} \right ] + \left ( \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ] u_1(0)+ \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] u_2(0) \right ) + \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ] \times \left [ \begin {matrix} u_1(0)\\ u_2(0) \end {matrix} \right ] = \left [ \begin {matrix} 0\\ 0\\ 1 \end {matrix} \right ] $$Выполнив соответствующие преобразования, в итоге получим систему
$$\left [ \begin {matrix} u_2(0)+1\\ u_1(0)+u_2(0)\\ u_1(0) \end {matrix} \right ]= \left [ \begin {matrix} 0\\ 0\\ 1 \end {matrix} \right ] $$Эта система имеет единственное решение $$u_1(0)=1, u_2(0)=1$$, следовательно, искомая входная последовательность есть $$[1,1]'$$.
Условия существования такой последовательности даются следующей теоремой.
Теорема 21.4. Для того чтобы последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ была УП для БА $$\tilde A$$, необходимо и достаточно, чтобы для каждого ненулевого состояния $$\bar s \in S_n$$ выполнялось по крайней мере одно из двух условий:
Здесь знак $$\wedge_{d=0}^t(\vee_{d=0}^t)$$ означает дизъюнкцию (конъюнкцию) выражений, стоящих за этим знаком и получаемых при изменении индекса $$d$$ от 0 до $$t$$. Условимся о следующем: если при вычислении $$I(\bar u(\nu))$$ и $$J(\bar u(\nu))$$ окажется, что $$\nu \lt; 0$$ при некоторых $$i$$ и $$d$$, то в соответствующем выражении сомножители $$[A+I(\bar u(\nu))]$$ и $$[C+J(\bar u(\nu))]$$ полагаются равными
Доказательство. Применительно к БА $$\tilde A$$ определение 1.2 УП принимает следующий вид: последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ называется УП, если
$$\forall \bar s_1, \bar s_2, \in S_n, \wedge_{d=0}^t\{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]s_1+\dots\\ \dots +[C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d)=[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(d-i-1)]\bar s_2+ \dots\\ \dots =[C+j(\bar u(d))]B\bar u(0)+ \dots + [A+I(u(t))]B\bar u(t-1)+B\bar u(t)=\\ =\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]B\bar u(0)+\dots +[A+I(u(t))]B\bar u(t-1)+B\bar u(t)=\\ =\prod_{i=0}^{t-1}[A+I(\bar u(t-i))]\bar s_2+\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]B\bar u(0)+\dots +[A+I(\bar u(t))]B\bar u(t-1)+B\bar u(t) \right ]$$Преобразуем каждое в отдельности равенство, стоящее до и после знака импликации, перенеся все в левые их части и осуществив соответствующие сокращения, в результате чего получим
$$\forall \bar s_1, \bar s_2 \in S_n, [\wedge_{d=0}^t[C+J(\bar u(d))]\prod_{i=0}^t[A+I(d-i-1)](\bar s_1-\bar s_2)=[0]] \to\\ \to \prod_{i=0}^t[A+I(\bar u(t-i))](\bar s_1- \bar s_2)=[0]$$Поскольку $$\bar s_1$$ и $$\bar s_2$$ - произвольные не совпадающие между собой состояния из $$S_n$$, то и состояние $$\bar s=\bar s_1 - \bar s_2$$ также может быть любым ненулевым состоянием из $$S_n$$. Отсюда следует, что последний предикат эквивалентен предикату
$$\forall \bar s \ne [0] [\wedge_{d=0}^t[C+J(\bar u(d))] \prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s=[0] \to \prod_{i=0}^t[A+I(\bar u(t-i))]\bar s=[0]$$Поскольку $$X \to Y$$ эквивалентно $$\bar X \vee Y$$, то последний предикат эквивалентен следующему предикату
$$\forall \bar s \ne [0] [\vee_{d=0}^t[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar \ne [0]] \vee \vee \prod_{i=0}t[A+I(\bar u(t-i))]\bar s=[0]$$Из этого предиката и следует справедливость теоремы.
Проиллюстрируем предложенный метод на примере БА над полем $$GF(2) $$, у которого $$n=3, l=2, m=2$$, а характеристические матрицы таковы:
$$A= \left [ \begin {matrix} 100\\ 010\\ 001 \end {matrix} \right ] , B= \left [ \begin {matrix} 10\\ 01\\ 10 \end {matrix} \right ], F_1= \left [ \begin {matrix} 001\\ 010\\ 000 \end {matrix} \right ], F_2= \left [ \begin {matrix} 001\\ 000\\ 101 \end {matrix} \right ] ,\\ C= \left [ \begin {matrix} 001\\ 011 \end {matrix} \right ], D= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ] , G_1= \left [ \begin {matrix} 101\\ 011 \end {matrix} \right ], G_2= \left [ \begin {matrix} 011\\ 101 \end {matrix} \right ] $$Первое условие теоремы 21.4 при $$d=0$$ порождает систему уравнений
$$[C+J(\bar u(0))]\bar s= \left [ \begin {matrix} u_1(0) u_2(0) u_1(0)+u_2(0)+1\\ u_2(0) u_1(0)+1 u_1(0)+u_2(0)+1 \end {matrix} \right ] * \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0] $$Рассмотрим теперь все возможные векторы $$\bar u(0):[0,0]' [1,0]', [1,0]', [1,1]'$$. Их подстановка в выписанную нелинейную систему порождает четыре следующих системы:
$$begin {cases} s_3=0,\\ s_2+s_3=0 \end {cases}, begin {cases} s_2=0,\\ s_1+s_2=0 \end {cases}, begin {cases} s_1,,\ 0=0, \end {cases}, begin {cases} s_1+s_2+s-3=0,\\ s_1+s_3=0 \end {cases}$$Каждая из этих систем относительно неизвестных $$s_1, s_2, s_3$$ имеет не единственное решение, и поэтому условие 1 теоремы 21.4 для всех входных последовательностей длины 1 не выполняется. Перейдем теперь к проверке условия 2 той же теоремы, которое при $$d=0$$ порождает систему
$$[A+I(\bar u(0))]\bar s= \left [ \begin {matrix} 10u_i(0)+u_2(0)\\ 0u_1(0)+10\\ u_2(0)0u_2(0)+1 \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0]$$Легко проверить, что эта система имеет единственное (нулевое) решение при любом $$\bar u(0)$$, т. е. условие 2 также не выполняется. Поэтому перейдем к поиску УП длины 2, полагая $$d=1$$.
Условие 1 теоремы 21.4 порождает следующую систему уравнений:
$$begin {cases} [C+J(\bar u(0))]\bar s=[0],\\ {C+J(\bar u(1))][A+I(\bar u(0))]\bar s=[0] \end {cases}$$В координатной записи эта же система имеет следующий вид:
$$\left [ \begin {matrix} u_1(0)u_2(0)u_1(0)+u_2(0)+1\\ u_2(0)u_1(0)+1u_1(0)+u_2(0)+1 \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0],\\ \left [ \begin {matrix} [u_1(1)+u_2(1)+1]*u_2(1)[u_1(0)+1]u_1(1)[u_1(0)+u_2(0)]+\\ *u_2(0)+u_1(1)+u_1(1)+u_2(1)+1][u_2(0)+1]\\ [u_1(1)+u_2(1)+1]*[u_1(1)+1]*u_2(1)[u_1(0)+u_2(0)]+\\ *u_2(0)+u_2(01)*[u_1(0)+1]+[u_1(1)+u_2(1)+1][u_2(0)+1] \end {matrix} \right ]* \left [ \begin {matrix} s_1\\ s_2\\ s_3 \end {matrix} \right ]=[0]$$Теперь необходимо рассмотреть все возможные пары векторов $$\bar u(0), \bar u(1)$$ и, подставляя их в выписанную выше систему, получить множество систем линейных уравнений относительно неизвестных $$s_1, s_2, s_3$$. Вычисления показывают, что, например, для пар входных векторов $$\bar u(0)=[1,1]', \bar u(1)=[0,0}'$$ и $$\bar u(0)=[0,0]', \bar u(1)=[1,0]'$$ первая подсистема $$[C+J(\bar u(0))]\bar s=[0]$$ имеет ненулевое решение ( $$\bar s=[1,0,1]'$$ и $$\bar s=[1,0,0]'$$ соответственно), а вторая подсистема для этих же пар входных векторов имеет единственное (нулевое) решение. Последний факт означает, что условие 1 теоремы выполняется, следовательно, обе приведенные входные последовательности являются для рассматриваемого БА установочными. Заметим, что этот БА имеет и другие УП длины 2, которые находятся аналогично.
Для подтверждения сказанного, в приведенной таблице показаны реакции рассматриваемого БА на две найденные входные последовательности и соответствующие конечные состояния. Состояния БА в таблице закодированы в виде десятичного эквивалента двоичного представления вектора-состояния. Так, например, состояние $$\bar s=[1,0,0]'$$ закодировано числом 4, состояние $$\bar s=[1,0,1]'$$ - числом 5 и т. д.
| Входное слово 3, 0 | Входное слово 0, 2 | |||
|---|---|---|---|---|
| Начальное состояние | Реакция БА | Конечное состояние | Реакция БА | Конечное состояние |
| 0 | 3, 2 | 7 | 0, 2 | 5 |
| 1 | 0, 2 | 7 | 3, 2 | 0 |
| 2 | 1, 2 | 7 | 1, 2 | 5 |
| 3 | 2, 2 | 7 | 2, 2 | 0 |
| 4 | 0, 1 | 2 | 0, 0 | 1 |
| 5 | 3, 1 | 2 | 3, 0 | 5 |
| 6 | 2, 1 | 2 | 1, 0 | 1 |
| 7 | 1, 1 | 2 | 2, 0 | 4 |
Аналогичная кодировка в таблице принята для входных и выходных векторов. Так, УП $$[0,0]', [1,0]'$$ закодирована как последовательность 0, 2; а УП $$[1,1]', [0,0]'$$ - как последовательность 3, 0.
Условия существования такой последовательности даются следующей теоремой.
Теорема 21.5. Для того чтобы последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ была ДП для БА $$\tilde A$$, необходимо и достаточно, чтобы
$$rank \left [ \begin {matrix} C+J(\bar u(0)\\ [C+J(\bar u(1))][A+I(\bar u(0))]\\ ………………………………….\\ [C+J(\bar u(t))]\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))] \end {matrix} \right ]=n, \ \mbox {где} \ {n} \ \mbox {размерность БА}$$Доказательство. Применительно к БА определение 1.3 ДП принимает следующий вид: последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ называется ДП, если
$$\forall \bar s_1, \bar s_2 \in S_n \wedge_{d=0}^{t} \left \{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s_1+$$ $$\dots, [C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d)=[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I(\bar u(d-i-1))]\bar s_2+$$ $$\dots +[C+J(\bar u(d))]B\bar u(d-1)+D\bar u(d) \right \} \to \bar s_1=\bar s_2$$Выполнив преобразование так же, как это делалось в предыдущем доказательстве, получим предикат
$$\forall \bar s_1, s_2 \in S_n \wedge_{d=0}^{t} \left \{[C+J(\bar u(d))]\prod_{i=0}^{d-1}[A+I (\bar u(d-i-1))](\bar s_1-\bar s_2)=0] \right \} \to \bar s_1=\bar s_2$$Если последовательность $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ является для БА диагностической, то это означает, что знание реакции БА на нее позволяет однозначно найти ее начальное состояние. Выходы БА на ДП, используя (21.4), можно представить как функции от начального состояния $$\bar s(0)$$:
$$\bar y(0)=[C+J(\bar u(0))]\bar s(0)+D\bar u(0),\\ \bar y(1)=[C+J(\bar u(1))][A+I(\bar u (1))]\bar s(0)+[C+J(\bar u(1))]B\bar u(0)+D\bar u(1),\\ ………………………………….\\ \bar y(t)=[C+J(\bar u(t))]\prod_{i=0}^{t-1}[A+I(\bar u(t-i-1))]\bar s(0)+ \dots +D\bar u(t)$$Поскольку ДП $$\bat u(0), \bar u(1), \dots, \bar u(t) $$ и реакция БА на нее известны, выписанные соотношения можно представить в виде
$$[C+J(\bar u(0))]\bar s(0)= Ф_0(\bar u(0)),\\ [C+J(\bar u(1))][A+I(\bar u(0))]\bar s(0)= Ф_1(\bar u(0), \bar u(1)),\\ ………………………………………………………\\ [C+J(\bar u(t))] \prod_{i=0}^{i-1}[A+I(\bar u(t-i-1))]\bar s(0)= Ф_t(\bar u(0), \dots, \bar u(t)))$$где $$Ф_i(\bat u(0), \dots, \bar u(i)), (i=\overline {0,t}) $$ - некоторые значения из поля $$GF(p) $$.
Выписанную совокупность соотношений можно интерпретировать как систему линейных уравнений относительно неизвестных $$s_1(0), \dots, s_n(0)$$, являющихся координатами вектора-состояния $$\bar s(0)$$. Однозначность восстановления начального состояния $$\bar s(0)$$ по наблюдаемой реакции $$\bar y(0), \bar y(1), \dots, \bar y(t)$$ при известной входной последовательности $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ означает, что представленная
Опишем теперь метод нахождения ДП для заданного БА, основанный на теореме 21.5. Метод состоит в переборе всевозможных входных слов $$\bat u(0), \bar u(1), \dots, \bar u(t)$$ последовательно для $$t=1,2,3,\dots$$ и вычислении для очередного проверяемого слова ранга матрицы, фигурирующей в теореме 21.5. Если этот ранг окажется равным n, то проверяемое входное слово является искомой ДП. В противном случае указанный процесс продолжается далее до тех пор, пока значение параметра $$t$$ не достигнет своего предельного значения, равного верхней границе длины минимальной ДП для рассматриваемого БА. Если и при этом значении $$t$$ ДП не будет найдена, то для рассматриваемого БА ее не существует. Проиллюстрируем этот метод на примере БА, для которого выше осуществлялся поиск УП. Для этого БА приведем некоторые "составляющие" матрицы в условиях теоремы 21.5:
$$[C+J(\bar u(0))]= \left [ \begin {matrix} u_1(0)u_2(0)u_1(0)+u_2(0)+1\\ u_2(0)U_1(0)+1 u_1(0)+u_2(0)+1 \end {matrix} \right ],\\ [C+J(\bar u(0))][A+I(\bar u(0))]= \left [ \begin {matrix} [u_1(1)+u_2(1)]*u_2(0)+u_1(1) u_2(1)[u_1(0)+1]u_1(1)[u_1(0)+u_2(0)]+[u_1(1)+u_2(1)+1][u_2(0)+1]\\ [u_1(1)+u_2(1)]*u_2(0)+u_1(1)[u_1(1)+1][u_1(0)+1]u_2(1)[u_1(0)+u_2(0)]+[u_1(1)+u_2(1)+1][u_2(0)+1] \end {matrix} \right ] $$Размерность матрицы $$[C+J(\bar u(0))]$$ равна $$2 \times 3$$, следовательно, ее ранг не может превышать 2. Но тогда, поскольку для рассматриваемой БС $$n=3$$, условие теоремы 21.5 при $$t=0$$ не может быть выполнено. В связи с этим перейдем к перебору всевозможных входных слов длины 2 (полагая $$t=1$$ ). Рассмотрим, например, входное слово $$\bar u(0), \bar (1)=3,0$$. Для него матрица из условия теоремы 21.5 имеет вид
$$\left [ \begin {matrix} C+J(\bat u(0))\\ [C+J(\bar u(0))][A+I(\bar u(0))] \end {matrix} \right ]= \left [ \begin {matrix} 100\\ 100\\ 111\\ 101 \end {matrix} \right ] $$Поскольку ранг этой матрицы равен 3, проверяемое слово 3, 0 есть ДП. В этом можно убедиться по данным, приведенным в таблице. Для другого входного слова $$\bar u(0), \bar u(1)=0,2$$ та же матрица из условий теоремы равна
$$\left [ \begin {matrix} 001\\ 011\\ 100\\ 000 \end {matrix} \right ] $$Ранг ее также равен 3, следовательно, входное слово 0, 2 также является ДП для рассматриваемого БА. Таким образом, оба входных слова 3, 0 и 0, 2 являются для рассматриваемого БА одновременно УП и ДП.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.