Глава4.

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

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

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

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

, (4.1)

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

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

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

, (4.2)

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

, (4.3)

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

1, если ;

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

, если .

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

, (4.4)

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

.

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

. (4.5)

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

, (4.6)

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

.

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

, (4.7)

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

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

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

.

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

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

.

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

.

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

,

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

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

. (4.8)

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

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

. (4.9)

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

. (4.10)

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

Достоверность КТ для произвольного периода.

Недостатком определения достоверности КТ в предыдущем разделе является невозможность определения достоверности при произвольном периоде при фиксированном значении [1]. Как оказывается на практике, снижение периода значительно снижает время на проведение теста (время уменьшается в раз), но при этом возникает вопрос о том, как изменяется достоверность КТ. То есть задача состоит в том, чтобы определить достоверность КТ как функцию периода :

.

Очевидным фактом является то, что с понижением периода достоверность КТ должна уменьшаться.

Для начала определим верхнюю границу достоверности для произвольного периода, а саму достоверность определим как функцию:

.

Чтобы определить значение верхней границы воспользуемся правой частью неравенства (6.13):

.

Значение правой части этого неравенства является частным случаем для максимального периода . Более того, эта формула не показывает зависимости достоверности от периода . Если установить зависимость достоверности от максимального периода , тогда это будет справедливо для произвольного периода. Найдем эту зависимость:

.

Тогда достоверность для произвольного периода определиться как:

. (4.11) Если период является простым числом, то можно преобразовать формулу (4.9) используя вышеприведённые рассуждения. Тогда получим:

=

=

.

При больших значениях периода отношение , тогда формула для определения достоверности произвольного (не обязательно максимального ) простого периода примет вид:

. (4.12)

Верхние и нижние оценки достоверности КТ для формулы 1.10, приведённые по формуле (4.10), выполняются для произвольного максимального периода . Обобщим их для произвольного периода.

Нижняя оценка примет вид:

Верхняя граница примет вид:

.

Итак, для произвольного не обязательно максимального периода получаем оценку достоверности КТ:

. (4.13)

Таким образом, формула (4.10) является частным случаем формулы (4.13), когда период T является максимальным для данного значения r, то есть равен .

61