Синдромное тестирование или метод счёта единиц.

Синдромом (контрольной суммой) некоторой булевой функции n переменных является соотношение

S=R/2ⁿ,

Где R вычисляется по выражению

R=

Для l=2ⁿ и равно числу единичных значений функции согласно таблице истинности. Определение понятия синдрома однозначно предполагает использование генератора счётчиковых последовательностей двоичных комбинаций из n входных переменных при тестировании схемы, реализующей заданную функцию.

2.5 Блок поиска неисправностей.

 

С помощью многоканальных сигнатурных анализаторов можно существенно ускорить процедуру контроля цифровых схем, которая увеличивается в n раз, где n-количество входов применяемого анализатора. В случае совпадения реально полученной сигнатуры с её эталонным значением считается, что с достаточно высокой вероятностью проверяемая схема находится в исправном состоянии. На этом процедура её исследования оканчивается. В противном случае, когда схема содержит неисправности, реальная сигнатура, как правило, отличается от эталонной, что служит основным аргументом для принятия гипотезы о неисправном состоянии схемы. В то же время вид полученной сигнатуры не несёт никакой дополнительной информации о характере возникшей неисправности. Более того остаётся открытым вопрос о том, какие из n анализируемых последовательностей, инициирующих реальную сигнатуру, содержат ошибки, т.е. возникает задача локализации неисправности с точностью до последовательности, несущей информацию о её присутствии.

Суммарная сигнатура S(x), полученная для последовательности {y_v(k)}, v=1, n, k=1, l, на n-канальном сигнатурном анализаторе, равна поразрядной сумме по модулю два сигнатур S_v(x), v=1, n. Причём каждая сигнатура S_j(x), jÎ {1, 2, 3, …n}, формируется для последовательности {y_j(k)} при условии, что {y_q(k)}=0000…00, q¹ jÎ {1, 2, …, n}.

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

1. В результате анализа n=2^d реальных последовательностей {y^*(k)}, v=1, nб на n-канальном анализаторе определяется значение сигнатуры S^*(x), которое соответствует соотношению:

 

.

2. По выражению  вычисляется эталонное значение сигнатуры S(x).

3. Реальное значение сигнатуры S^*(x) сравнивается с эталонной сигнатурой S(x). В случае выполнения равенства S^*(x)=S(x) переходят к выполнению п.11 и процедура контроля считается оконченной. В противном случае, когда S^*(x)¹ S(x), выполняется следующий этап алгоритма.

4. Все множество входных последовательностей разбивается на две группы, причём номера последовательностей {y₁(k)}, {y₂(k)}, {y₃(k)}, …., {y_n/2(k)} составляют множество А₂={1, 2, 3, …, n/2}, а последовательностей {y_n/2+1(k)}, {y_n/2+2(k)}, … {y_n(k)} – множество А₂={n/2+1, n/2+2, …, n}; величине i присваивается значение 1.

5. В результате анализа реальных последовательностей, номера которых задаются множеством А₁, на n-канальном анализаторе при условии, что последовательности, номера которых не определены множеством А₁, являются нулевыми, определяется значение реальной сигнатуры S^*(x).

6. На основании выражения  получаем S(x).

7. Проверяется справедливость равенства S(x)=S^*(x). В случае его выполнения элементы множества А₁ заменяются элементами множества А₂.

8. Значение переменной i увеличивается на единицу. Затем его величина сравнивается с величиной d. При i£ d переходят к следующему пункту алгоритма, в противном случае выполняется пункт 10.

9. По текущим значениям множества А₁ формируются новые множества А₁ и А₂. Новыми элементами множества А₁ будет первая половина его текущих элементов, вторая половина присваивается множеству А₂. После определения множеств А₁ и А₂ переходят к выполнению п. 5.

10. Единственный элемент множества А₁представляет собой номер ошибочной последовательности, формируемой на одном из полюсов исследуемой схемы.

11. Процедура контроля цифровой схемы считается оконченной.

2.6 Определение оценки эффективности методов сигнатурного анализатора и счёта единиц.

Достоверность сигнатурного анализа.

 

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

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

Величина Р_n рассчитывается для достаточно общего случая, приближённо соответствующего реальным примерам. Предполагается, что эталонная последовательность данных может равновероятно принимать разное значение, а любая конфигурация ошибочных бит может быть равновероятным событием. Далее, использую алгоритм деления полиномов как математический аппарат формирования сигнатуры, показываем, что для l-разрядного делимого вычисляются l-m-разрядное частное и m-разрядный остаток (сигнатура). При этом соответствие реальной последовательности, состоящей из l бит, эталонной оценивается только по равенству их m - разрядных сигнатур. Для 2^l-m различных частных будет формироваться одинаковая сигнатура. Это свидетельствует о том, что 2^l-m -1 ошибочных l -разрядных последовательностей будут считаться соответствующими одной - эталонной. Учитывая равно вероятность ошибочных последовательностей данных, можно заключить, что 2^l-m-1 ошибочных последовательностей, инициирующих эталонную сигнатуру, не обнаруживаемы. Таким образом, вероятность Р_n необнаружения ошибок в анализируемой последовательности данных будет вычисляться как отношение:

(2.6.1)

где 2^l-1 равняется общему числу ошибочных последовательностей.

Выражение (2.6.1) для условия l> > m преобразуется к более простому виду:

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

В качестве более точной меры оценки достоинств сигнатурного анализатора рассмотрим распределение вероятности необнаружения ошибки в зависимости от её кратности m, т.е. определим значение  где m=1, 2, 3,...2^m-1.

Можно показать, что не обнаруживаемых ошибок определяется следующим образом:

а количество возможных ошибок из m бит определяется как

И тогда выражение для вероятности не обнаружения ошибки принимает вид:

,

Анализ показывает, что для достаточно больших m , т.е. при m> 7 вероятность обнаружения ошибки практически равняется единице.

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: