В процессе эксплуатации в цифровых устройствах могут возникнуть различные неисправности. Для обеспечения правильного функционирования этих устройств необходимо проводить их проверку с целью обнаружения возможных неисправностей. Один из способов обнаружения неисправностей заключается в прерывании режима штатной работы устройства и подачи на него специально построенной входной последовательности, называемой тестом. Тест должен обладать следующим свойством: реакция проверяемых устройств на него должна быть различной в зависимости от того, является ли это устройство исправным или содержит неисправность. Следовательно, процесс обнаружения неисправностей представляет собой эксперимент, проводимый над устройством.
Эта лекция посвящена проблеме обнаружения неисправностей в цифровых системах, описываемых моделями линейных автоматов. Ранее известные методы построения тестов для ЛА, описанные в работах [2], [27], содержали жесткие требования, касающиеся как наличия информации о начальном состоянии, так и схемной реализации. Заметим, что эти требования почти никогда не выполняются.
Предлагаемые ниже методы не требуют выполнения упомянутых жестких ограничений и являются менее трудоемкими. Далее предполагается, что в ЛА могут возникать неисправности, приводящие к изменению его характеристических матриц, но не увеличивающие числа его состояний и не выводящие исходное устройство из класса ЛА.
Предполагается также, что неисправность, возникнув в ЛА в некоторый момент, сохраняется в нем и во все последующие моменты времени. Последнее означает, что из рассмотрения исключаются только сбои и перемежающиеся неисправности, которые представляют собой кратковременные самоустраняющиеся неисправности одного и того же типа, появляющиеся в устройстве через некоторые не обязательно равные промежутки времени. Что же касается "неисчезающих" неисправностей, то рассматриваемое разнообразие их видов предельно широко. В самом деле, любые из встречающихся на практике неисправностей, например, типа константных, перепутывания связей, коротких замыканий, изменения реализуемой
Ниже рассматривается следующая задача. Пусть задан ЛА и некоторая его неисправная модификация из множества допустимых неисправных модификаций. Требуется построить такую входную последовательность (тест), которая эту неисправность обнаруживает.
Входную последовательность назовем тестом, обнаруживающим заданную неисправность, если независимо от начальных состояний исправного ЛА и его неисправной модификации их входные реакции на эту последовательность различны.
Построенные предложенными ниже методами тесты используются для проведения экспериментов по распознаванию (обнаружению) неисправностей. Тесты подаются на вход ЛА, фиксируется реакция проверяемого устройства на этот тест и по этой реакции делается заключение об исправности или неисправности устройства.
Напомним вначале некоторые понятия, которые понадобятся в дальнейшем.
Говорят, что ЛА $$\tilde A$$ имеет конечную память глубины $$\mu$$, если в любой момент времени $$t$$ выход $$y(t)$$ однозначно определяется входом в этот же момент и предыдущими $$\mu$$ входами и $$\mu$$ выходами, т. е. для всех $$t$$ справедливо соотношение
$$\bar y(t)=f(\bar u(t), \bar (t-1), \dots, \bar u(t- \mu), \bar y(t-1), \dots, \bar y(t-\mu))$$Содержательно это означает, что реакция такого ЛА в произвольный момент времени может быть предсказана только на основе знания входной последовательности и соответствующей реакции ЛА в предшествующие $$\mu$$ моментов времени.
Из теории ЛА известно [19], что каждый ЛА имеет конечную память глубины $$\mu$$, где $$\mu \le n$$ ( $$n$$ - размерность ЛА).
Говорят, что ЛА $$\tilde A$$ является $$\mu$$ - определенным, если его выход $$\bar y(t)$$ в любой момент времени $$t$$ зависит лишь от предыдущих $$\mu$$ входов, т. е. справедливо соотношение
$$\bar y(t)=f(\bar u(t), \bar u(t-1), \dots, \bar u(t - \mu))$$Перейдем теперь к описанию методов построения тестов. Пусть $$A_1, B_1, C_1, D_1$$ - характеристические матрицы ЛА $$\tilde {A_1}$$, являющегося неисправной модификацией исходного ЛА $$\tilde A$$.
Рассмотрим случай, когда как исходный ЛА $$\tilde A$$, так и неисправный ЛА $$\tilde {A_1}$$ являются $$\mu$$ -определенными, однако значения параметра $$\mu$$ для них необязательно совпадают. Пусть $$\mu = \max$$ ( $$\mu_1$$, $$\mu_2$$ ), где $$\mu_1$$ и $$\mu_2$$ - значения параметра $$\mu$$ для ЛА $$\tilde A$$ и $$\tilde {A_1}$$ соответственно. В [19] доказано, что необходимым и достаточным условием $$\mu$$ -определенности ЛА является выполнение соотношения $$CA^{\mu}=[0]$$. Отсюда следует, что $$CA^k=[0]$$ и $$C_1A_1^k=[0]$$ для всех $$k \ge \mu$$.
Если на исправный и неисправный ЛА подана одна и та же входная последовательность $$\bar u(0), \bar u(1), \dots, \bar u(\mu)$$, то с учетом только что приведенных равенств и формулы (1.4) полной реакции ЛА независимо от начальных состояний автоматов $$\tilde A$$ и $$\tilde {A_1}$$ соответствующие реакции имеют вид
$$\bar y(\mu)=CA^{\mu -1}B \bar u(0)+CA^{\mu-2} B\bar u(1)+ \dots +CB \bar u(\mu-1)+D\bar u(\mu),\\ \bar {y_1}=C_1A_1^{\mu -1}B_1 \bar u(0)+C_1A_1^{\mu -2}B_1 \bar u(1)+ \dots + C_1B_1 \bar u(\mu -1)+D_1 \bar u(\mu)$$Произведя вычитание, получим
$$\bar y(\mu)- \bar {y_1}(\mu)=[CA^{\mu -1}B-C_1A_1^{\mu -1}B_1]\bar u(0)+ \dots +[D-D_1]\bar u(\mu)$$Понятно, что заданная неисправность будет обнаружена входной последовательностью (тестом) $$\bar u(0), \bar u(1), \dots, \bar u(\mu)$$, если и только если реакции $$\bar u(\mu)$$ и $$\bar {y_1}(\mu)$$ различаются, т. е. $$\bar y(\mu)-\bar {y_1}(\mu) \ne [0]$$.
Соотношение (14.1) будем рассматривать как СЛАУ относительно неизвестных, являющихся координатами вектора
$$u =[u_1(0),\dots, u_l(0),\dots, u_1(\mu),\dots, u_l(\mu)] $$и на ее основе организуем процедуру построения теста. Обозначим через $$Q $$ матрицу системы (14.1); тогда (14.1) перепишется в виде
$$Qu=y$$где $$y$$ - некоторый $$m$$ -мерный ненулевой вектор.
Обозначим через $$T$$ множество всех тестов, обнаруживающих заданную неисправность. Для поиска множества $$T$$ необходимо варьировать правую часть системы (14.3) и при каждой конкретной правой части находить решение системы, если оно существует.
Легко сообразить, что число всевозможных правых частей системы (14.3) равно величине $$p^{(\mu +1)m}$$, которая даже при сравнительно небольших значениях параметров $$p$$, $$\mu$$ и $$m$$ достаточно велика. По этой причине предлагаемый метод довольно трудоемок и мы рассмотрим другой, более эффективный метод.
Суть его состоит в том, что вместо неоднородной системы (14.3) будет рассматриваться соответствующая ей однородная система
$$Qu=[0]$$множество решений которой обозначим через $$U_0$$. Если $$U$$ - множество всевозможных векторов вида (14.2), то очевидно, что множество $$U/U_0$$ является искомым множеством $$T$$ тестов. Таким образом, при такой организации построения тестов все свелось к решению единственной однородной системы уравнений.
Пусть ранг матрицы $$Q$$ равен $$r$$. Если $$r = (\mu +1)l$$, то из алгебры известно, что нулевое решение будет единственным решением однородной системы (2.4), а при $$r < (\mu +1)l$$ система имеет ненулевые решения, метод поиска которых известен.
Проиллюстрируем предложенный метод на примере. Пусть ЛА над полем $$GF(2)$$ задан следующими характеристическими матрицами ( $$n = 4, l = 2, m = 2$$ ):
$$A= \left [ \begin {matrix} 0000\\ 1000\\ 1100\\ 1110 \end {matrix} \right ],\\ B= \left [ \begin {matrix} 11\\ 11\\ 11\\ 11 \end {matrix} \right ],\\ C= \left [ \begin {matrix} 1100\\ 1000 \end {matrix} \right ],\\ D= \left [ \begin {matrix} 11\\ 11 \end {matrix} \right ] $$Пусть неисправный автомат задан матрицами
$$A_1= \left [ \begin {matrix} 1111\\ 1111\\ 1000\\ 1000\\ \end {matrix} \right ],\\ B_1=B,\\ C_1= \left [ \begin {matrix} 1100\\ 0011 \end {matrix} \right ],\\ D_1=D $$Легко проверить, что $$CA^2 = [0] $$ и $$CA_1^2 = [0] $$, т. е. оба ЛА являются $$\mu$$ -определенными ( $$\mu = 2$$ ).
По формуле полной реакции имеем следующие результаты:
$$\bar u(2)=CAB \bar u(0) \oplus CB\bar u(1) \oplus D\bar u(2),\\ \bar {y_1}(2)=C_1A_1B \bar u(0) \oplus C_1B \bar u(1) \oplus D \bar u(2)$$Отсюда получаем однородную линейную систему вида (14.4):
$$[CAB \oplus C_1A_1B]\bar u(0) \oplus [CB \oplus C_1B]\bar u(1)=[0]$$Выполнив соответствующие вычисления, придем к следующей однородной системе уравнений в координатной форме:
$$u_1(0) \oplus u_2(0)=0;\\ u_1(0) \oplus u_2(1)=0$$Легко проверить, что ранг матрицы последней системы $$r = 2$$, т. е. он меньше числа неизвестных ( $$\mu +1)l = 3\times 2 = 6$$. Отсюда следует, что система имеет ненулевое решение. Считая, например, переменные $$u_2(0) $$ и $$u_2(1) $$ свободными, выразим через них оставшиеся переменные
$$u_1(0)=u_2(0); u_1(1)=u_2(1)$$Отметим, что в рассматриваемой системе переменные $$u_1(2) $$ и $$u_2(2) $$ отсутствуют в силу специфики самой системы, т. е. выступают здесь в роли фиктивных переменных. Из сказанного вытекает, что решениями этой однородной системы являются всевозможные значения $$u_1(0), u_2(0), u_1(1), u_2(1) $$, удовлетворяющие соотношениям (14.5), а также произвольные значения переменных $$u_1(2), u_2(2) $$.
Зная множество $$U_0$$ решений рассмотренной однородной системы, построим множество $$Т$$ всех тестов, обнаруживающих заданную неисправность, как
Обратимся теперь к методу построения тестов для синхронизируемых автоматов. В соответствии с приведенным ранее критерием синхронизируемости для любого синхронизируемого ЛА существует такое целое число $$k$$, что $$A^k = [0] $$, но тогда справедливо и равенство $$CA^k = [0] $$ при любой матрице $$С$$. Отсюда вытекает справедливость следующего утверждения.
Теорема 14.1. Каждый синхронизируемый ЛА является одновременно и $$\mu$$ -определенным.
Понятно, что эта теорема обосновывает возможности применения описанного выше метода построения тестов к синхронизируемым ЛА.
Предложенный метод построения тестов предполагает, что неисправные ЛА должны сохранять свойства $$\mu$$ -определенности или синхронизируемости. Заметим, что это требование не является слишком ограничительным. Так, оно заведомо выполняется, если возникающие в автомате неисправности сказываются только на характеристических матрицах $$B, C$$ и $$D$$. Однако не всякое изменение матрицы $$А$$ указанные свойства будет сохранять.
Перейдем теперь к описанию метода построения тестов для произвольного ЛА, а не обязательно $$\mu$$ -определенного либо синхронизируемого. Этот метод базируется на том факте, что любой ЛА является автоматом с конечной памятью.
Предположим, что исправный (неисправный) ЛА имеет глубину памяти $$\mu_1(\mu_2)$$ и пусть $$\mu = \max (\mi_1, \mu_2)$$ ). Из теории ЛА известно [19], что функции выходов ЛА $$\tilde A$$ и $$\tilde {A_1}$$ соответственно можно представить в виде:
$$\bar y(t)V_0^1\bar u(t)+ V_1\bar u(t-1)+ \dots +V_{\mu}\bar u(t-\mu)+W_0\bar y(t-1)+ \dots +W_{\mu}\bar y(t- \mu ),\\ \bar {y_1}(t)=V_0^1\bar u(t)+V_1^1\bar u(t-1)+ \dots + V_{\mu}^1 \bar u(t- \mu)+W_0^1 \bar y(t-1)+ \dots + W_{\mu}^1 \bar y(t- \mu),$$где $$V_i(V_i^1), W_i(W_i^1)$$ - матрицы соответствующей размерности. Способ приведения
Очевидно, что входная последовательность $$\bar u(t-\mu), u(t-\mu+1), \dots, u(t)$$ является минимальным по
Приравняв выражение (14.7) некоторому ненулевому вектору $$y$$, мы получим СЛАУ относительно неизвестных, являющихся координатами вектора
$$u=[u_1(t- \mu), \dots, u_1(t- \mu), \dots, u_1(t), \dots, u_1(t)]'$$Если через $$Q$$ обозначим матрицу полученной СЛАУ, то в этом обозначении она примет вид
$$Qu=y$$Заметим, что все сказанное выше относительно поиска решений системы (14.3) остается справедливым и для последней системы. Таким образом, построение множества всех тестов для произвольных ЛА, так же как для $$\mu$$ -определенных и синхронизируемых ЛА, сводится к
Проиллюстрируем предложенный метод на примере ЛА над полем $$GF(2) $$ с характеристическими матрицами
$$A= \left [ \begin {matrix} 0100\\ 1100\\ 0001\\ 0101 \end {matrix} \right ],\\ B= \left [ \begin {matrix} 1\\ 1\\ 1\\ 0 \end {matrix} \right ],\\ C= \left [ \begin {matrix} 0101 \end {matrix} \right ], D=[1]$$Найдем представление
Тогда, используя формулы полной реакции ЛА и только что полученное равенство, вычислим
$$y(2)=CA^2 \bar s (0)+CABu(0)+CBu(1)+Du(0)=\\ =C\bar s(0)+CA\bar s(0)+CABu(0)+CBu(1)+Du(1)=\\ =[y(0)+Du(0)]+[y(1)+CBu(0)+Du(1)]+CABu(0)+CBu(1)+Du(1).$$После преобразований получаем
$$y(2)=u(2)+u(0)+u(0)+y(1)+y(0),$$откуда для любого $$t$$
$$y(t)=u(t)+u(t-2)+y(t-1)+y(t-2).$$Пусть неисправный ЛА задан следующими характеристическими матрицами:
$$A_1=A, B_1=B, C_1=[1 0 1 0], D_1=D.$$Проведя аналогичные вычисления для неисправного ЛА, получим
$$y_1(t)=u(t)+u(t-1)+y_1(t-1)+y_1(t-2).$$Упоминавшаяся выше СЛАУ для нашего примера примет вид
$$y(t)-y_1(t)=u(t-1) \oplus u(t-2)$$Понятно, что для получения множества всех тестов, обнаруживающих заданную неисправность, необходимо найти все решения СЛАУ
$$u(t-1) \oplus u(t-2)=1$$Отсюда получаем, что
$$u(t-1)=1 \oplus u(t-2)=\overline {u(t-2)}$$Таким образом, множество всех искомых тестов составляют такие тройки двоичных наборов $$(u(t), u(t-1), u(t-2)) $$, у которых $$u(t) $$ может иметь произвольное значение, а величины $$u(t-1) $$ и $$u(t-2) $$ должны быть инверсными.
Отметим следующий важный факт: предложенный метод строит тест длины $$\mu +1$$, где $$\mu $$ - глубина памяти ЛА. Поскольку, как известно, $$\mu \le n$$, где $$n$$ - размерность ЛА, такой метод дает возможность строить достаточно короткие по
Для нестационарных ЛА рассмотрим ту же задачу, которая исследовалась в предыдущем разделе для стационарных ЛА. При этом будем предполагать, что класс неисправностей, возникающих в НЛА, полностью идентичен соответствующему классу в случае стационарных ЛА.
По аналогии со стационарными ЛА вначале рассмотрим метод синтеза тестов для синхронизируемых НЛА. Идея этого метода ничем не отличается от случая стационарного ЛА, и поэтому мы обозначим только некоторые его ключевые моменты.
Как и ранее, предполагается, что исправный и неисправный НЛА являются синхронизируемыми, однако длины минимальных СП для них не обязательно совпадают. Пусть $$k = max(k_1, k_2) $$, где $$k_1$$ и $$k_2$$ - длины минимальных СП для исправного НЛА $$\tilde A$$ и неисправного НЛА $$\tilde {A_1}$$ соответственно. Используя формулу (1.8) полной реакции НЛА и необходимое и достаточное условие (2.11) существования СП длины $$k+1$$, как и в случае стационарного ЛА приходим к выводу, что поиск искомой тестовой последовательности $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ для обнаружения заданной неисправности сводится к решению
Здесь y - некоторый ненулевой вектор, а матрица, снабженная индексом "1", относится к неисправному НЛА.
Множество всех искомых тестов может быть получено путем решения СЛАУ (14.8) для всевозможных ненулевых правых ее частей. Поскольку этот способ требует рассмотрения множества СЛАУ, более эффективным является другой способ, основанный на поиске решения одной однородной СЛАУ, соответствующей неоднородной системе (14.8), с последующим построением с помощью "однородного" решения искомых "неоднородных".
Вообще говоря, может оказаться, что при рассматриваемом значении $$k$$ система (14.8) не является совместной ни при каких правых частях. В этом случае увеличим $$k$$ на единицу и будем строить новую систему вида (14.8). Этот процесс продолжается далее аналогичным образом до тех пор, пока либо не будет найдено множество всех тестов, либо величина $$k$$ не достигнет верхней границы длины минимального теста. Такой границей, в частности, может служить верхняя
Проиллюстрируем предложенный метод на примере. Пусть $$n = l = m = 2$$ и НЛА над полем GF(2) задана следующими характеристическими матрицами:
$$A(0)= \left [ \begin {matrix} 10\\ 10 \end {matrix} \right ],\\ A(1)= \left [ \begin {matrix} 00\\ 11 \end {matrix} \right ], \\ A(2)= \left [ \begin {matrix} 11\\ 11 \end {matrix} \right ],\\ A(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i= 3,4, \dots ;\\ B(0)= \left [ \begin {matrix} 00\\ 00 \end {matrix} \right ],\\ B(1)= \left [ \begin {matrix} 11\\ 00 \end {matrix} \right ], \\ B(2)= \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ], \\ B(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4, \dots ;\\ C(i)=D(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4, \dots.$$Предположим, что неисправный НЛА задается следующими характеристическими матрицами:
$$A_1(0)= \left [ \begin {matrix} 10\\ 10 \end {matrix} \right ],\\ A_1(1)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], A_1(2)= \left [ \begin {matrix} 00\\ 11 \end {matrix} \right ],\\ A_1(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i= 3, 4, \dots ;\\ B_1(0)= \left [ \begin {matrix} 0\\ 00 \end {matrix} \right ],\\ B_1(1)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ],\\ B_1(2)= \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ],\\ B_1(i)= \left [ \begin {matrix} 10\\ 00 \end {matrix} \right ], i=3,4, \dots ;\\ C_1(i)=D_1(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4,\dots.$$Вычисления показывают, что $$A(1)A(0)=[0]$$ и $$A_1(2)A_1(1)A_1(0)=[0]$$.
Следовательно, как исправный, так и неисправный НЛА синхронизируемы и длины СП для них равны 2 и 3 соответственно. Исходя из этого, начнем построение тестов длины $$k = 4$$. Итак, вначале в качестве кандидата в тесты рассмотрим входную последовательность $$\bar u(0), \bar u(1), \bar u(2), \bar u(3)$$. Выпишем реакции на эту последовательность исправного и неисправного НЛА:
$$\bar y(3)=C(3)A(2)A(1)A(0)\bar s(0)+C(3)A(2)A(1)B(0)\bar u(0)+C(3)A(2)B(1)\bar u(1)+C(3)B(2)\bar u(2)+D(3)\bar u(3),\\ \bar {y_1}=C_1(3)A_1(2)A_1(1)A_1(0)s(0)+C_1(3)A_1(2)A_1(1)B_1(0)\bar u(0)+\\ +C_1(3)A_1(2)B_1(1)\bar u(1)+C_1(3)B_1(2) \bar u(2)+D_1(3)\bar u(3)$$Выполнив соответствующие вычисления в координатной форме с учетом того, что все операции выполняются по модулю 2, получим следующие результаты:
$$\bar y(3)= \left [ \begin {matrix} u_1(1)+u_2(1)+u_1(3)+u_2(2)\\ u_1(1)+u_2(1)+u_1(2)+u_2(3) \end {matrix} \right ],\\ y_1(3)= \left [ \begin {matrix} u_2(2)+u_1(3)\\ u_1(1)+u_2(1)+u_1(2)+u_2(3) \end {matrix} \right ]$$Используя эти векторы, построим однородную систему, соответствующую системе (14.8):
$$\bar y(3)+\bar {y_1}= \left [ \begin {matrix} u_1(1)+u_2(1)\\ 0 \end {matrix} \right ]= \left [ \begin {matrix} 0\\ 0 \end {matrix} \right]$$Ее решениями являются все четверки векторов $$\bar u(0), \bar u(1), \bar u(2), \bar u(3)$$, у которых $$u_1(1)=u_2(1)$$ Отсюда следует, что искомое множество тестов составляет такие же четверки векторов, но для которых справедливо условие $$u_1(1) \ne u_2(1)$$ Легко подсчитать, что всего таких векторов 128 штук.
Предложенный метод предполагает сохранение свойства синхронизируемости у неисправного НЛА, если исправный НЛА был синхронизируем. Понятно, что это не всегда выполняется. В связи с этим рассмотрим метод синтеза тестов, ориентированный на произвольные минимальные НЛА. Этот метод есть прямой аналог метода распознавания автоматов, принадлежащих исключительному классу, описанному в [18].
Опишем кратко его суть применительно к рассматриваемой нами задаче, когда исключительный класс состоит только из двух автоматов, исправного и неисправного. При этом условимся считать, что множества их допустимых состояний совпадают с соответствующими множествами всех состояний автоматов.
Для исправного НЛА $$A$$ построим минимальную УП $$\bar {u_1}$$, которая существует в силу минимальности НЛА, и подадим ее на предъявленный для эксперимента экземпляр автомата. Естественно, что экспериментатору неизвестно, является ли этот автомат исправным или неисправным. По наблюдаемой реакции найдем конечное состояние $$\bar {s_f}(\tilde A)$$, в котором должен оказаться испытываемый автомат, если бы он был исправным.
Далее построим УП $$\bar {u_2}$$ для неисправного НЛА $$\tilde {A_1}$$ и подадим ее на предъявленный для эксперимента экземпляр автомата. По наблюдаемой реакции найдем конечное состояние $$\bar {s_1}(\tilde {A_1})$$, в котором должен оказаться испытываемый автомат, если бы он был неисправным. Предполагается, что НЛА $$\tilde {A_1}$$ представлен своей минимальной формой и потому УП для него существует.
Напомним, что в силу теоремы 2.2 если НЛА имеет хотя бы одну УП длины $$k$$, то все другие входные последовательности длины $$k$$ и более также являются для этого НЛА установочными. Это свойство позволяет "наложить" друг на друга УП $$\bar {u_1}$$ и $$\bar {u_1}$$ и тем самым сократить длину последовательности, осуществляющей установку НЛА $$\tilde A$$ и $$\tilde {A_1}$$. В самом деле, если выбрать произвольную входную последовательность $$\bar u$$ длины $$k = \max(k_1, k_2) $$, где $$k_1 (k_2) $$ есть длина минимальной УП для автомата $$\tilde A(\tilde {A_1})$$, то эта последовательность будет устанавливать в известное экспериментатору состояние как автомат $$\tilde A$$ так и автомат $$\tilde {A_1}$$.
Для обнаружения неисправности теперь осталось ответить на вопрос, является ли испытываемый автомат автоматом $$\tilde A$$ в состоянии $$\bar {s_1}(\tilde A)$$ либо автоматом $$\tilde {A_1}$$ в состоянии $$\bar {s_f}(\tilde {A_1})$$. Для ответа на этот вопрос подадим на вход испытываемого автомата входную последовательность, построенную на основе метода различающей функции. Синтез этой последовательности осуществим в виде пошагового процесса, делая попытки найти сначала последовательности длины 1, затем длины 2 и т. д. С этой целью сначала выпишем реакции автоматов $$\tilde A$$ и $$\tilde {A_1}$$ с начальными состояниями $$\bar {s_f}(\tilde A)$$ и $$\bar {s_f}(\tilde {A_1})$$ на входную последовательность $$\bar u(0)$$ длины 1:
$$\bar y(0)=C(0) \bar {s_f}(\tilde A)+D(0) \bar u(0),\\ y_1(0)C_1(0) \bar {s_f}(\tilde {A_1})+D_1(0) \bar u(0)$$Теперь сформируем выражение (различающую функцию):
$$\bar y(0)-\bar {y_1}(0)= \bar b$$где $$\bar b$$ - некоторый произвольный ненулевой вектор. Это выражение будем интерпретировать как СЛАУ относительно координат $$\bar u(0)$$. Решая эту систему при всевозможных ненулевых правых частях, найдем все различающие последовательности длины 1. Если эта система окажется несовместной, сформируем очередную систему
$$\bar y(1)-\bar {y_1}(1)=\bar b$$и ищем ее решение. Указанный процесс продолжается далее аналогичным образом до тех пор, пока не будет найдена различающая последовательность. Этот процесс заведомо конечен, поскольку неисправности в НЛА предполагаются существенными, т. е. проявляющими себя в процессе функционирования. Кстати, вывод о конечности процесса построения различающей последовательности следует также и из того факта, что упомянутая последовательность есть не что иное, как ДП минимального автомата для двух допустимых начальных состояний. Такая диагностическая задача, как известно [18], всегда разрешима.
Таким образом, искомый тест будет состоять из двух последовательностей, первая из которых представляет собой совмещенную УП, а вторая - различающую последовательность.
Остановимся теперь на верхней оценке длины теста, полученного описанным методом.
В разделе 2.3 лекции 2 было показано, что в общем случае длина минимальной УП для НЛА не ограничена сверху. Поэтому рассмотрим периодические НЛА, у которых длина УП, а следовательно, и теста, заведомо конечна.
В том же разделе 2.3 было установлено, что для периодического НЛА длина УП не превосходит $$\lambda n$$ где $$\lambda$$ - период главной характеристической матрицы $$A$$ НЛА $$\tilde A$$, $$n$$ - ее размерность. Что касается второй части теста, то ее можно рассматривать как ДП и поэтому длина ее не превосходит $$n$$. Таким образом, общая длина теста, построенного таким методом, не превышает величины $$\lambda n+n = (\lambda +1)n$$.
Сравним эту оценку с соответствующей верхней оценкой длины теста для произвольного автомата, не являющегося НЛА. Как показано в [18] , верхняя
Здесь $$q$$ - число состояний автомата. Поскольку для НЛА $$q = p^n$$, в терминах параметра $$q$$
В процессе эксплуатации в цифровых устройствах могут возникнуть различные неисправности. Для обеспечения правильного функционирования этих устройств необходимо проводить их проверку с целью обнаружения возможных неисправностей. Один из способов обнаружения неисправностей заключается в прерывании режима штатной работы устройства и подачи на него специально построенной входной последовательности, называемой тестом. Тест должен обладать следующим свойством: реакция проверяемых устройств на него должна быть различной в зависимости от того, является ли это устройство исправным или содержит неисправность. Следовательно, процесс обнаружения неисправностей представляет собой эксперимент, проводимый над устройством.
Эта лекция посвящена проблеме обнаружения неисправностей в цифровых системах, описываемых моделями линейных автоматов. Ранее известные методы построения тестов для ЛА, описанные в работах [2], [27], содержали жесткие требования, касающиеся как наличия информации о начальном состоянии, так и схемной реализации. Заметим, что эти требования почти никогда не выполняются.
Предлагаемые ниже методы не требуют выполнения упомянутых жестких ограничений и являются менее трудоемкими. Далее предполагается, что в ЛА могут возникать неисправности, приводящие к изменению его характеристических матриц, но не увеличивающие числа его состояний и не выводящие исходное устройство из класса ЛА.
Предполагается также, что неисправность, возникнув в ЛА в некоторый момент, сохраняется в нем и во все последующие моменты времени. Последнее означает, что из рассмотрения исключаются только сбои и перемежающиеся неисправности, которые представляют собой кратковременные самоустраняющиеся неисправности одного и того же типа, появляющиеся в устройстве через некоторые не обязательно равные промежутки времени. Что же касается "неисчезающих" неисправностей, то рассматриваемое разнообразие их видов предельно широко. В самом деле, любые из встречающихся на практике неисправностей, например, типа константных, перепутывания связей, коротких замыканий, изменения реализуемой
Ниже рассматривается следующая задача. Пусть задан ЛА и некоторая его неисправная модификация из множества допустимых неисправных модификаций. Требуется построить такую входную последовательность (тест), которая эту неисправность обнаруживает.
Входную последовательность назовем тестом, обнаруживающим заданную неисправность, если независимо от начальных состояний исправного ЛА и его неисправной модификации их входные реакции на эту последовательность различны.
Построенные предложенными ниже методами тесты используются для проведения экспериментов по распознаванию (обнаружению) неисправностей. Тесты подаются на вход ЛА, фиксируется реакция проверяемого устройства на этот тест и по этой реакции делается заключение об исправности или неисправности устройства.
Напомним вначале некоторые понятия, которые понадобятся в дальнейшем.
Говорят, что ЛА $$\tilde A$$ имеет конечную память глубины $$\mu$$, если в любой момент времени $$t$$ выход $$y(t)$$ однозначно определяется входом в этот же момент и предыдущими $$\mu$$ входами и $$\mu$$ выходами, т. е. для всех $$t$$ справедливо соотношение
$$\bar y(t)=f(\bar u(t), \bar (t-1), \dots, \bar u(t- \mu), \bar y(t-1), \dots, \bar y(t-\mu))$$Содержательно это означает, что реакция такого ЛА в произвольный момент времени может быть предсказана только на основе знания входной последовательности и соответствующей реакции ЛА в предшествующие $$\mu$$ моментов времени.
Из теории ЛА известно [19], что каждый ЛА имеет конечную память глубины $$\mu$$, где $$\mu \le n$$ ( $$n$$ - размерность ЛА).
Говорят, что ЛА $$\tilde A$$ является $$\mu$$ - определенным, если его выход $$\bar y(t)$$ в любой момент времени $$t$$ зависит лишь от предыдущих $$\mu$$ входов, т. е. справедливо соотношение
$$\bar y(t)=f(\bar u(t), \bar u(t-1), \dots, \bar u(t - \mu))$$Перейдем теперь к описанию методов построения тестов. Пусть $$A_1, B_1, C_1, D_1$$ - характеристические матрицы ЛА $$\tilde {A_1}$$, являющегося неисправной модификацией исходного ЛА $$\tilde A$$.
Рассмотрим случай, когда как исходный ЛА $$\tilde A$$, так и неисправный ЛА $$\tilde {A_1}$$ являются $$\mu$$ -определенными, однако значения параметра $$\mu$$ для них необязательно совпадают. Пусть $$\mu = \max$$ ( $$\mu_1$$, $$\mu_2$$ ), где $$\mu_1$$ и $$\mu_2$$ - значения параметра $$\mu$$ для ЛА $$\tilde A$$ и $$\tilde {A_1}$$ соответственно. В [19] доказано, что необходимым и достаточным условием $$\mu$$ -определенности ЛА является выполнение соотношения $$CA^{\mu}=[0]$$. Отсюда следует, что $$CA^k=[0]$$ и $$C_1A_1^k=[0]$$ для всех $$k \ge \mu$$.
Если на исправный и неисправный ЛА подана одна и та же входная последовательность $$\bar u(0), \bar u(1), \dots, \bar u(\mu)$$, то с учетом только что приведенных равенств и формулы (1.4) полной реакции ЛА независимо от начальных состояний автоматов $$\tilde A$$ и $$\tilde {A_1}$$ соответствующие реакции имеют вид
$$\bar y(\mu)=CA^{\mu -1}B \bar u(0)+CA^{\mu-2} B\bar u(1)+ \dots +CB \bar u(\mu-1)+D\bar u(\mu),\\ \bar {y_1}=C_1A_1^{\mu -1}B_1 \bar u(0)+C_1A_1^{\mu -2}B_1 \bar u(1)+ \dots + C_1B_1 \bar u(\mu -1)+D_1 \bar u(\mu)$$Произведя вычитание, получим
$$\bar y(\mu)- \bar {y_1}(\mu)=[CA^{\mu -1}B-C_1A_1^{\mu -1}B_1]\bar u(0)+ \dots +[D-D_1]\bar u(\mu)$$Понятно, что заданная неисправность будет обнаружена входной последовательностью (тестом) $$\bar u(0), \bar u(1), \dots, \bar u(\mu)$$, если и только если реакции $$\bar u(\mu)$$ и $$\bar {y_1}(\mu)$$ различаются, т. е. $$\bar y(\mu)-\bar {y_1}(\mu) \ne [0]$$.
Соотношение (14.1) будем рассматривать как СЛАУ относительно неизвестных, являющихся координатами вектора
$$u =[u_1(0),\dots, u_l(0),\dots, u_1(\mu),\dots, u_l(\mu)] $$и на ее основе организуем процедуру построения теста. Обозначим через $$Q $$ матрицу системы (14.1); тогда (14.1) перепишется в виде
$$Qu=y$$где $$y$$ - некоторый $$m$$ -мерный ненулевой вектор.
Обозначим через $$T$$ множество всех тестов, обнаруживающих заданную неисправность. Для поиска множества $$T$$ необходимо варьировать правую часть системы (14.3) и при каждой конкретной правой части находить решение системы, если оно существует.
Легко сообразить, что число всевозможных правых частей системы (14.3) равно величине $$p^{(\mu +1)m}$$, которая даже при сравнительно небольших значениях параметров $$p$$, $$\mu$$ и $$m$$ достаточно велика. По этой причине предлагаемый метод довольно трудоемок и мы рассмотрим другой, более эффективный метод.
Суть его состоит в том, что вместо неоднородной системы (14.3) будет рассматриваться соответствующая ей однородная система
$$Qu=[0]$$множество решений которой обозначим через $$U_0$$. Если $$U$$ - множество всевозможных векторов вида (14.2), то очевидно, что множество $$U/U_0$$ является искомым множеством $$T$$ тестов. Таким образом, при такой организации построения тестов все свелось к решению единственной однородной системы уравнений.
Пусть ранг матрицы $$Q$$ равен $$r$$. Если $$r = (\mu +1)l$$, то из алгебры известно, что нулевое решение будет единственным решением однородной системы (2.4), а при $$r < (\mu +1)l$$ система имеет ненулевые решения, метод поиска которых известен.
Проиллюстрируем предложенный метод на примере. Пусть ЛА над полем $$GF(2)$$ задан следующими характеристическими матрицами ( $$n = 4, l = 2, m = 2$$ ):
$$A= \left [ \begin {matrix} 0000\\ 1000\\ 1100\\ 1110 \end {matrix} \right ],\\ B= \left [ \begin {matrix} 11\\ 11\\ 11\\ 11 \end {matrix} \right ],\\ C= \left [ \begin {matrix} 1100\\ 1000 \end {matrix} \right ],\\ D= \left [ \begin {matrix} 11\\ 11 \end {matrix} \right ] $$Пусть неисправный автомат задан матрицами
$$A_1= \left [ \begin {matrix} 1111\\ 1111\\ 1000\\ 1000\\ \end {matrix} \right ],\\ B_1=B,\\ C_1= \left [ \begin {matrix} 1100\\ 0011 \end {matrix} \right ],\\ D_1=D $$Легко проверить, что $$CA^2 = [0] $$ и $$CA_1^2 = [0] $$, т. е. оба ЛА являются $$\mu$$ -определенными ( $$\mu = 2$$ ).
По формуле полной реакции имеем следующие результаты:
$$\bar u(2)=CAB \bar u(0) \oplus CB\bar u(1) \oplus D\bar u(2),\\ \bar {y_1}(2)=C_1A_1B \bar u(0) \oplus C_1B \bar u(1) \oplus D \bar u(2)$$Отсюда получаем однородную линейную систему вида (14.4):
$$[CAB \oplus C_1A_1B]\bar u(0) \oplus [CB \oplus C_1B]\bar u(1)=[0]$$Выполнив соответствующие вычисления, придем к следующей однородной системе уравнений в координатной форме:
$$u_1(0) \oplus u_2(0)=0;\\ u_1(0) \oplus u_2(1)=0$$Легко проверить, что ранг матрицы последней системы $$r = 2$$, т. е. он меньше числа неизвестных ( $$\mu +1)l = 3\times 2 = 6$$. Отсюда следует, что система имеет ненулевое решение. Считая, например, переменные $$u_2(0) $$ и $$u_2(1) $$ свободными, выразим через них оставшиеся переменные
$$u_1(0)=u_2(0); u_1(1)=u_2(1)$$Отметим, что в рассматриваемой системе переменные $$u_1(2) $$ и $$u_2(2) $$ отсутствуют в силу специфики самой системы, т. е. выступают здесь в роли фиктивных переменных. Из сказанного вытекает, что решениями этой однородной системы являются всевозможные значения $$u_1(0), u_2(0), u_1(1), u_2(1) $$, удовлетворяющие соотношениям (14.5), а также произвольные значения переменных $$u_1(2), u_2(2) $$.
Зная множество $$U_0$$ решений рассмотренной однородной системы, построим множество $$Т$$ всех тестов, обнаруживающих заданную неисправность, как
Обратимся теперь к методу построения тестов для синхронизируемых автоматов. В соответствии с приведенным ранее критерием синхронизируемости для любого синхронизируемого ЛА существует такое целое число $$k$$, что $$A^k = [0] $$, но тогда справедливо и равенство $$CA^k = [0] $$ при любой матрице $$С$$. Отсюда вытекает справедливость следующего утверждения.
Теорема 14.1. Каждый синхронизируемый ЛА является одновременно и $$\mu$$ -определенным.
Понятно, что эта теорема обосновывает возможности применения описанного выше метода построения тестов к синхронизируемым ЛА.
Предложенный метод построения тестов предполагает, что неисправные ЛА должны сохранять свойства $$\mu$$ -определенности или синхронизируемости. Заметим, что это требование не является слишком ограничительным. Так, оно заведомо выполняется, если возникающие в автомате неисправности сказываются только на характеристических матрицах $$B, C$$ и $$D$$. Однако не всякое изменение матрицы $$А$$ указанные свойства будет сохранять.
Перейдем теперь к описанию метода построения тестов для произвольного ЛА, а не обязательно $$\mu$$ -определенного либо синхронизируемого. Этот метод базируется на том факте, что любой ЛА является автоматом с конечной памятью.
Предположим, что исправный (неисправный) ЛА имеет глубину памяти $$\mu_1(\mu_2)$$ и пусть $$\mu = \max (\mi_1, \mu_2)$$ ). Из теории ЛА известно [19], что функции выходов ЛА $$\tilde A$$ и $$\tilde {A_1}$$ соответственно можно представить в виде:
$$\bar y(t)V_0^1\bar u(t)+ V_1\bar u(t-1)+ \dots +V_{\mu}\bar u(t-\mu)+W_0\bar y(t-1)+ \dots +W_{\mu}\bar y(t- \mu ),\\ \bar {y_1}(t)=V_0^1\bar u(t)+V_1^1\bar u(t-1)+ \dots + V_{\mu}^1 \bar u(t- \mu)+W_0^1 \bar y(t-1)+ \dots + W_{\mu}^1 \bar y(t- \mu),$$где $$V_i(V_i^1), W_i(W_i^1)$$ - матрицы соответствующей размерности. Способ приведения
Очевидно, что входная последовательность $$\bar u(t-\mu), u(t-\mu+1), \dots, u(t)$$ является минимальным по
Приравняв выражение (14.7) некоторому ненулевому вектору $$y$$, мы получим СЛАУ относительно неизвестных, являющихся координатами вектора
$$u=[u_1(t- \mu), \dots, u_1(t- \mu), \dots, u_1(t), \dots, u_1(t)]'$$Если через $$Q$$ обозначим матрицу полученной СЛАУ, то в этом обозначении она примет вид
$$Qu=y$$Заметим, что все сказанное выше относительно поиска решений системы (14.3) остается справедливым и для последней системы. Таким образом, построение множества всех тестов для произвольных ЛА, так же как для $$\mu$$ -определенных и синхронизируемых ЛА, сводится к
Проиллюстрируем предложенный метод на примере ЛА над полем $$GF(2) $$ с характеристическими матрицами
$$A= \left [ \begin {matrix} 0100\\ 1100\\ 0001\\ 0101 \end {matrix} \right ],\\ B= \left [ \begin {matrix} 1\\ 1\\ 1\\ 0 \end {matrix} \right ],\\ C= \left [ \begin {matrix} 0101 \end {matrix} \right ], D=[1]$$Найдем представление
Тогда, используя формулы полной реакции ЛА и только что полученное равенство, вычислим
$$y(2)=CA^2 \bar s (0)+CABu(0)+CBu(1)+Du(0)=\\ =C\bar s(0)+CA\bar s(0)+CABu(0)+CBu(1)+Du(1)=\\ =[y(0)+Du(0)]+[y(1)+CBu(0)+Du(1)]+CABu(0)+CBu(1)+Du(1).$$После преобразований получаем
$$y(2)=u(2)+u(0)+u(0)+y(1)+y(0),$$откуда для любого $$t$$
$$y(t)=u(t)+u(t-2)+y(t-1)+y(t-2).$$Пусть неисправный ЛА задан следующими характеристическими матрицами:
$$A_1=A, B_1=B, C_1=[1 0 1 0], D_1=D.$$Проведя аналогичные вычисления для неисправного ЛА, получим
$$y_1(t)=u(t)+u(t-1)+y_1(t-1)+y_1(t-2).$$Упоминавшаяся выше СЛАУ для нашего примера примет вид
$$y(t)-y_1(t)=u(t-1) \oplus u(t-2)$$Понятно, что для получения множества всех тестов, обнаруживающих заданную неисправность, необходимо найти все решения СЛАУ
$$u(t-1) \oplus u(t-2)=1$$Отсюда получаем, что
$$u(t-1)=1 \oplus u(t-2)=\overline {u(t-2)}$$Таким образом, множество всех искомых тестов составляют такие тройки двоичных наборов $$(u(t), u(t-1), u(t-2)) $$, у которых $$u(t) $$ может иметь произвольное значение, а величины $$u(t-1) $$ и $$u(t-2) $$ должны быть инверсными.
Отметим следующий важный факт: предложенный метод строит тест длины $$\mu +1$$, где $$\mu $$ - глубина памяти ЛА. Поскольку, как известно, $$\mu \le n$$, где $$n$$ - размерность ЛА, такой метод дает возможность строить достаточно короткие по
Для нестационарных ЛА рассмотрим ту же задачу, которая исследовалась в предыдущем разделе для стационарных ЛА. При этом будем предполагать, что класс неисправностей, возникающих в НЛА, полностью идентичен соответствующему классу в случае стационарных ЛА.
По аналогии со стационарными ЛА вначале рассмотрим метод синтеза тестов для синхронизируемых НЛА. Идея этого метода ничем не отличается от случая стационарного ЛА, и поэтому мы обозначим только некоторые его ключевые моменты.
Как и ранее, предполагается, что исправный и неисправный НЛА являются синхронизируемыми, однако длины минимальных СП для них не обязательно совпадают. Пусть $$k = max(k_1, k_2) $$, где $$k_1$$ и $$k_2$$ - длины минимальных СП для исправного НЛА $$\tilde A$$ и неисправного НЛА $$\tilde {A_1}$$ соответственно. Используя формулу (1.8) полной реакции НЛА и необходимое и достаточное условие (2.11) существования СП длины $$k+1$$, как и в случае стационарного ЛА приходим к выводу, что поиск искомой тестовой последовательности $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ для обнаружения заданной неисправности сводится к решению
Здесь y - некоторый ненулевой вектор, а матрица, снабженная индексом "1", относится к неисправному НЛА.
Множество всех искомых тестов может быть получено путем решения СЛАУ (14.8) для всевозможных ненулевых правых ее частей. Поскольку этот способ требует рассмотрения множества СЛАУ, более эффективным является другой способ, основанный на поиске решения одной однородной СЛАУ, соответствующей неоднородной системе (14.8), с последующим построением с помощью "однородного" решения искомых "неоднородных".
Вообще говоря, может оказаться, что при рассматриваемом значении $$k$$ система (14.8) не является совместной ни при каких правых частях. В этом случае увеличим $$k$$ на единицу и будем строить новую систему вида (14.8). Этот процесс продолжается далее аналогичным образом до тех пор, пока либо не будет найдено множество всех тестов, либо величина $$k$$ не достигнет верхней границы длины минимального теста. Такой границей, в частности, может служить верхняя
Проиллюстрируем предложенный метод на примере. Пусть $$n = l = m = 2$$ и НЛА над полем GF(2) задана следующими характеристическими матрицами:
$$A(0)= \left [ \begin {matrix} 10\\ 10 \end {matrix} \right ],\\ A(1)= \left [ \begin {matrix} 00\\ 11 \end {matrix} \right ], \\ A(2)= \left [ \begin {matrix} 11\\ 11 \end {matrix} \right ],\\ A(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i= 3,4, \dots ;\\ B(0)= \left [ \begin {matrix} 00\\ 00 \end {matrix} \right ],\\ B(1)= \left [ \begin {matrix} 11\\ 00 \end {matrix} \right ], \\ B(2)= \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ], \\ B(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4, \dots ;\\ C(i)=D(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4, \dots.$$Предположим, что неисправный НЛА задается следующими характеристическими матрицами:
$$A_1(0)= \left [ \begin {matrix} 10\\ 10 \end {matrix} \right ],\\ A_1(1)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], A_1(2)= \left [ \begin {matrix} 00\\ 11 \end {matrix} \right ],\\ A_1(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i= 3, 4, \dots ;\\ B_1(0)= \left [ \begin {matrix} 0\\ 00 \end {matrix} \right ],\\ B_1(1)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ],\\ B_1(2)= \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ],\\ B_1(i)= \left [ \begin {matrix} 10\\ 00 \end {matrix} \right ], i=3,4, \dots ;\\ C_1(i)=D_1(i)= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], i=3,4,\dots.$$Вычисления показывают, что $$A(1)A(0)=[0]$$ и $$A_1(2)A_1(1)A_1(0)=[0]$$.
Следовательно, как исправный, так и неисправный НЛА синхронизируемы и длины СП для них равны 2 и 3 соответственно. Исходя из этого, начнем построение тестов длины $$k = 4$$. Итак, вначале в качестве кандидата в тесты рассмотрим входную последовательность $$\bar u(0), \bar u(1), \bar u(2), \bar u(3)$$. Выпишем реакции на эту последовательность исправного и неисправного НЛА:
$$\bar y(3)=C(3)A(2)A(1)A(0)\bar s(0)+C(3)A(2)A(1)B(0)\bar u(0)+C(3)A(2)B(1)\bar u(1)+C(3)B(2)\bar u(2)+D(3)\bar u(3),\\ \bar {y_1}=C_1(3)A_1(2)A_1(1)A_1(0)s(0)+C_1(3)A_1(2)A_1(1)B_1(0)\bar u(0)+\\ +C_1(3)A_1(2)B_1(1)\bar u(1)+C_1(3)B_1(2) \bar u(2)+D_1(3)\bar u(3)$$Выполнив соответствующие вычисления в координатной форме с учетом того, что все операции выполняются по модулю 2, получим следующие результаты:
$$\bar y(3)= \left [ \begin {matrix} u_1(1)+u_2(1)+u_1(3)+u_2(2)\\ u_1(1)+u_2(1)+u_1(2)+u_2(3) \end {matrix} \right ],\\ y_1(3)= \left [ \begin {matrix} u_2(2)+u_1(3)\\ u_1(1)+u_2(1)+u_1(2)+u_2(3) \end {matrix} \right ]$$Используя эти векторы, построим однородную систему, соответствующую системе (14.8):
$$\bar y(3)+\bar {y_1}= \left [ \begin {matrix} u_1(1)+u_2(1)\\ 0 \end {matrix} \right ]= \left [ \begin {matrix} 0\\ 0 \end {matrix} \right]$$Ее решениями являются все четверки векторов $$\bar u(0), \bar u(1), \bar u(2), \bar u(3)$$, у которых $$u_1(1)=u_2(1)$$ Отсюда следует, что искомое множество тестов составляет такие же четверки векторов, но для которых справедливо условие $$u_1(1) \ne u_2(1)$$ Легко подсчитать, что всего таких векторов 128 штук.
Предложенный метод предполагает сохранение свойства синхронизируемости у неисправного НЛА, если исправный НЛА был синхронизируем. Понятно, что это не всегда выполняется. В связи с этим рассмотрим метод синтеза тестов, ориентированный на произвольные минимальные НЛА. Этот метод есть прямой аналог метода распознавания автоматов, принадлежащих исключительному классу, описанному в [18].
Опишем кратко его суть применительно к рассматриваемой нами задаче, когда исключительный класс состоит только из двух автоматов, исправного и неисправного. При этом условимся считать, что множества их допустимых состояний совпадают с соответствующими множествами всех состояний автоматов.
Для исправного НЛА $$A$$ построим минимальную УП $$\bar {u_1}$$, которая существует в силу минимальности НЛА, и подадим ее на предъявленный для эксперимента экземпляр автомата. Естественно, что экспериментатору неизвестно, является ли этот автомат исправным или неисправным. По наблюдаемой реакции найдем конечное состояние $$\bar {s_f}(\tilde A)$$, в котором должен оказаться испытываемый автомат, если бы он был исправным.
Далее построим УП $$\bar {u_2}$$ для неисправного НЛА $$\tilde {A_1}$$ и подадим ее на предъявленный для эксперимента экземпляр автомата. По наблюдаемой реакции найдем конечное состояние $$\bar {s_1}(\tilde {A_1})$$, в котором должен оказаться испытываемый автомат, если бы он был неисправным. Предполагается, что НЛА $$\tilde {A_1}$$ представлен своей минимальной формой и потому УП для него существует.
Напомним, что в силу теоремы 2.2 если НЛА имеет хотя бы одну УП длины $$k$$, то все другие входные последовательности длины $$k$$ и более также являются для этого НЛА установочными. Это свойство позволяет "наложить" друг на друга УП $$\bar {u_1}$$ и $$\bar {u_1}$$ и тем самым сократить длину последовательности, осуществляющей установку НЛА $$\tilde A$$ и $$\tilde {A_1}$$. В самом деле, если выбрать произвольную входную последовательность $$\bar u$$ длины $$k = \max(k_1, k_2) $$, где $$k_1 (k_2) $$ есть длина минимальной УП для автомата $$\tilde A(\tilde {A_1})$$, то эта последовательность будет устанавливать в известное экспериментатору состояние как автомат $$\tilde A$$ так и автомат $$\tilde {A_1}$$.
Для обнаружения неисправности теперь осталось ответить на вопрос, является ли испытываемый автомат автоматом $$\tilde A$$ в состоянии $$\bar {s_1}(\tilde A)$$ либо автоматом $$\tilde {A_1}$$ в состоянии $$\bar {s_f}(\tilde {A_1})$$. Для ответа на этот вопрос подадим на вход испытываемого автомата входную последовательность, построенную на основе метода различающей функции. Синтез этой последовательности осуществим в виде пошагового процесса, делая попытки найти сначала последовательности длины 1, затем длины 2 и т. д. С этой целью сначала выпишем реакции автоматов $$\tilde A$$ и $$\tilde {A_1}$$ с начальными состояниями $$\bar {s_f}(\tilde A)$$ и $$\bar {s_f}(\tilde {A_1})$$ на входную последовательность $$\bar u(0)$$ длины 1:
$$\bar y(0)=C(0) \bar {s_f}(\tilde A)+D(0) \bar u(0),\\ y_1(0)C_1(0) \bar {s_f}(\tilde {A_1})+D_1(0) \bar u(0)$$Теперь сформируем выражение (различающую функцию):
$$\bar y(0)-\bar {y_1}(0)= \bar b$$где $$\bar b$$ - некоторый произвольный ненулевой вектор. Это выражение будем интерпретировать как СЛАУ относительно координат $$\bar u(0)$$. Решая эту систему при всевозможных ненулевых правых частях, найдем все различающие последовательности длины 1. Если эта система окажется несовместной, сформируем очередную систему
$$\bar y(1)-\bar {y_1}(1)=\bar b$$и ищем ее решение. Указанный процесс продолжается далее аналогичным образом до тех пор, пока не будет найдена различающая последовательность. Этот процесс заведомо конечен, поскольку неисправности в НЛА предполагаются существенными, т. е. проявляющими себя в процессе функционирования. Кстати, вывод о конечности процесса построения различающей последовательности следует также и из того факта, что упомянутая последовательность есть не что иное, как ДП минимального автомата для двух допустимых начальных состояний. Такая диагностическая задача, как известно [18], всегда разрешима.
Таким образом, искомый тест будет состоять из двух последовательностей, первая из которых представляет собой совмещенную УП, а вторая - различающую последовательность.
Остановимся теперь на верхней оценке длины теста, полученного описанным методом.
В разделе 2.3 лекции 2 было показано, что в общем случае длина минимальной УП для НЛА не ограничена сверху. Поэтому рассмотрим периодические НЛА, у которых длина УП, а следовательно, и теста, заведомо конечна.
В том же разделе 2.3 было установлено, что для периодического НЛА длина УП не превосходит $$\lambda n$$ где $$\lambda$$ - период главной характеристической матрицы $$A$$ НЛА $$\tilde A$$, $$n$$ - ее размерность. Что касается второй части теста, то ее можно рассматривать как ДП и поэтому длина ее не превосходит $$n$$. Таким образом, общая длина теста, построенного таким методом, не превышает величины $$\lambda n+n = (\lambda +1)n$$.
Сравним эту оценку с соответствующей верхней оценкой длины теста для произвольного автомата, не являющегося НЛА. Как показано в [18] , верхняя
Здесь $$q$$ - число состояний автомата. Поскольку для НЛА $$q = p^n$$, в терминах параметра $$q$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.