Достоверность для максимального периода

Под линейной последовательной системой (ЛПОС) понимается конечный автомат, заданный уравнениями:

где есть входной, выходной векторы, вектор состояния, векторы над полем . Матрица называется матрицей внутренней сети ЛПОС, а многочлен называется характеристическим многочленом ЛПОС [2].

При кольцевом тестировании (КТ) результат проверки получается при наблюдении поведения автономного генератора, в который преобразуется проверяемый элемент. В тестовом режиме генератор устанавливается в начальное состояние, затем подаются тактовых сигналов, где - период генератора. Если конечное состояние генератора совпадает с начальным, то проверяемое устройство считается исправным, в противном случае — неисправным.

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

Множество неисправных модификаций ЛПОС разбивается на классы эквивалентности , которые представляются многочленами над . Тем самым рассматриваются неисправности, преобразующие систему в линейные неисправные модификации. Предполагается, что исправная ЛПОС описывается неприводимым нормированным многочленом той степени, а появление любого из "неисправных" многочленов происходит с вероятностью . Здесь для комбинационного ДУ, для не зависящего от входа ДУ, для не зависящего от выхода ДУ, или для зависящего от входа и выхода ДУ, для произвольного ДУ в системе КД. Определим достоверность тестирования в множестве представителей классов . Для этого достоверность будем находить по формуле:

, (6.6)

где вероятность необнаружения неисправностей, вычисляемая при предположении о равновероятностном появлении дефектов.

Имеется несколько методов определения достоверности, но все они сводятся к определению достоверности по формуле (6.6) Таким образом, разница в определении достоверности различными способами заключается в разнице определения вероятности необнаружения неисправностей . Рассмотрим эти методы.

1. Произведём подсчёт для случая примитивного , для которого формула (6.6) допускает нижнюю оценку. В этом случае система тестирования имеет максимальный период . Поскольку исправность ДУ устанавливается по факту выполнения равенства:

, (6.7)

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

, (6.8)

где суммирование проводится по всем делителям числа ; функция Мёбиуса:

1, если ;

0, если делится на квадрат простого числа;

, если .

Формула (1.3) может быть переписана в виде:

, (6.9)

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

.

2. Второй способ отличается от первого иным определением . А сама достоверность рассчитывается по формуле:

. (6.10)

Если решение об исправности ДУ принимается по результату выполнения равенства (6.7) в такте и невыполнения 1.2 в тактах 1,2,…,1, то неисправные модификации системы с примитивным многочленом не будут обнаружены. Число примитивных многочленов равно:

, (6.11)

где ; функция Эйлера, которая может быть выражена через функцию Мёбиуса следующим образом:

.

В этом случае для выражения (6.11) имеет вид:

, (6.12)

где простые делители числа . Оценка 6.11 обычно для выражения (6.12) оказывается выше, чем для выражения (6.10).

Оба способа определения достоверности кольцевого тестирования дают примерно одинаковые результаты.

Если - простое число, то неравенство 1.5 для обоих случаев анализа результатов превращается в равенство:

.

Это выражение является нижней границей определения достоверности кольцевого тестирования.

Верхней границей определения достоверности КТ является выражение:

.

Таким образом, достоверность КТ лежит в пределах:

. (6.13)

3. Определим далее достоверность тестирования во множестве неисправных модификаций ЛПОС. Пусть проверяемая ЛПОС преобразована в автономную ЛПОС (АЛПОС) введением обратной связи, так что уравнение переходов состояний АЛПОС имеет вид:

,

где вектор-столбец состояний АЛПОС; характеристическая матрица над , имеющая размер . Дополнительное оборудование, необходимое в тестовом режиме, состоит из дополнительных входов и выходов ЛПОС, используемых только в тестовом режиме, а также дополнительной ЛПОС, включаемой в контур обратной связи проверяемой ЛПОС. Под неисправностью проверяемой ЛПОС будем понимать физический дефект, приводящий к искажению матрицы АЛПОС. Зададим неисправности в виде множества искажённых матриц , где матрица размера . Так как достоверность определяется по формуле 1.1, где вероятность необнаружения искажения матрицы при условии равновероятности всех искажений.

Таким образом, мощность множества оказывается равной числу различных матриц . Рассмотрим систему простого максимального периода . В этом случае каждый примитивный многочлен представляет один из классов , имеющих одинаковые мощности:

. (6.14)

Имеет место теорема.

Теорема. Пусть характеристический многочлен АЛПОС является неприводимым многочленом степени простого периода . Тогда достоверность кольцевого тестирования:

. (6.15)

Формула (6.15) для достоверности допускает нижнюю и верхнюю оценки. Так как , а , тогда получаем:

. (6.15а)

Причём это выполняется даже если максимальный период не является простым числом.

Недостатком данного способа определения достоверности КТ по формуле (6.15) является то, что он даёт точное значение достоверности лишь для простого максимального периода, хотя формула (6.15а) верна для произвольного максимального для данного периода . Этого недостатка лишён следующий способ определения достоверности для максимального периода.

4. Повторяя аналогичные третьему способу рассуждения до получения формулы 1.9, определим число "неисправных" многочленов, приводящих к выполнению 1.2, равно , следовательно, для достоверности в полном множестве неисправностей получаем:

. (6.16)

Часто на практике не требуется высокой точности вычислений. Поэтому, исходя из выражения 1.8, достоверность может быть грубо определена по формуле:

.

Но при этом необходимо учесть, что реальная достоверность не может превышать значения .

Таким образом, метод КТ является эффективным способом проверки логической сети из ЛПОС, так как достоверность проверки высока и большинстве случаев требуется небольшое количество дополнительного оборудования. Значения достоверности, определяемые в полном множестве неисправностей и в множестве представителей классов эквивалентностей, оказываются близкими. Этот факт согласуется с практическим опытом тестирования не только в кольцевых системах.

Дата добавления: 2014-01-07