Лекция 4

ностей, состоящих из нулевых символов и символов

Лекция 4.

Методы повышения достоверности сигнатурного анализатора.

Наиболее полной характеристикой, описывающей свойства сигнатурного анализатора, является распределение вероятностей необнаружения ошибок в зависимости от их кратности. Поэтому одним из методов повышения достоверности может быть метод, основанный на увеличении старшей степени порождающего полинома m. Как показывают проведенные расчеты при m>8, вероятность необнаружения ошибки не зависит от кратности ошибки и близка к нулю, и дальнейшее возрастание m не приводит к сколь-нибудь заметному повышению достоверности сигнатурного анализатора. С другой стороны, увеличение значения m приводит к нежелательному расширению разрядности сигнатуры.

Имеются другие методы повышения достоверности сигнатурного анализатора, направленные количественное изменение Pn .Достаточно хорошие результаты можно полу-

чить при использовании m сигнатурных анализаторов, описываемых одним и тем же полиномом φ(х). При этом каждый анализатор обрабатывает только определенное множество символов анализируемой последовательности. за счет этого ошибка, возникшая в исходной последовательности, представляется в виде ошибок различной конфигурации для каждого из m анализаторов. Таким образом, реальная ошибочная последовательность имеет вид множества искусственно образованных последовательностей, каждая из которых может содержать некоторое отличное от других множество ошибочных бит. Причем. Если хотя бы для одной последовательности ошибочные биты представляют собой обнаруживаемую конфигурацию анализатором, описываемым полиномом φ(х), то возникшая ошибка будет обнаруживаемой на основании всех m сигнатур. Простейшим примером разбиения исходной последовательности является использование символов кодов, определяющих номера элементов анализируемой последовательности. Пример подобного разбиения (m=4) для последовательности длиной l=24 -1 приведен в таблице1.

Анализируемая последовательность представляется в виде четырех последователь-y(k) k 1,15. При этом для ка-

ждой из образованных последовательностей используется сигнатурный анализатор, описываемый полиномом φ(х), имеющим старшую степень, равную m=4. Каждый сигнатурный анализатор обнаруживает ошибки в зависимости от их кратности в соответствии с выражениями (10) и (11). Возникшая ошибка в исходной последовательности, предположим, состоящая из пяти неверных символов y(4), y(6), y(11), y(12) и y(13), отображается в виде искажения трех, четырех, двух и двух символов соответственно во вновь образованных четырех последовательностей. Следовательно, данная ошибка всегда будет обнаруживаемой, так как она представляется в виде двукратных ошибок для третьей и четвертой последовательностей, которые также обнаруживаемы. В общем случае любая ошибка, возникшая в исходной последовательности, отображается в виде некоторого множества ошибок меньшей кратности, мощность М1 которого оценивается соотношением

M1 int log 2 ,

где μ-кратность возникшей ошибки. Отсюда следует, что любая трехкратная ошибка будет обнаруживаемой, так как она представляется по меньшей мере двумя ошибками кратности 2 или 1.Аналогичным образом можно доказать возможность обнаружения всех ошибок кратности 4, 5 и т. д. Причем максимальная кратность μ обнаруживаемых ошибок в общем случае зависит от величины m.

Таблица 1.

№ элемента	Анализируе-			Искусственно образованная последовательность
последовательно-	мая последователь-			1	2	3	4
сти	ность
	y(k) k
		1,15
1	y1			0		0	y1
2	y2			0		y2	0
3	y3			0	0	y3	y3
4	y4			0		0	0
5	y5			0	y5	0	y5
6	y6			0	y6	y6	0
7	y7			0	y7	y7	y7
8	y8			y8	0	0	0
9	y9			y9	0	0	y9
10	y10			y10	0	y10	0
11	y11			y11	0	y11	y11
12	y12			y12	y12	0	0
13	y13			y1	y1	0	y1
14	y14			y14	y14	y14	0
15	y15			y15	y15	y15	y15
Кратность	μ =5			μ=2	μ =4	μ =2	μ =2
ошибки

Многоканальные сигнатурные анализаторы.

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

Методы построения многоканального сигнатурного анализатора. Для построения МСА используются следующие методы:

1). Синтез МСА, основанный на двойном сжатии данных в пространстве или во времени.

2). Синтез МСА, основанный на использовании матрицы состояний.

3). Синтез МСА, основанный на системе логических уравнений.

1. Синтез многоканального сигнатурного анализатора, основанный на двойном сжатии данных в пространстве или во времени.

Этот метод основан на преобразовании n выходных последовательностей

yi (k) {0,1} , i 1, n , k 1,l длиной l в одну последовательность {y0 (k)} по выражению:

n
y0 (k) yi (k) ;	(2.3.1)
i 1

Далее сформированная таким образом последовательность сжимается в m- разрядное ключевое слово.

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

Таким образом, первоначальные n последовательностей с тестируемой схемы

yi (k) {0,1} преобразуются в последовательность y0 (k) согласно (2.3.1). Далее сформированная таким образом последовательность сжимается в m – разрядную сигнатуру.

Рис.5: Двойное сжатие данных в пространстве.

Распределение вероятностей для данного метода оценивается как:

		/ 2		n 1		1
	Pn (2 j 1)(				) / 2		,
						l / 2
		j 1		n
	(2.3.2)
	где Pn	– это вероятность необнаружения ошибки кратности , причём для нечёт-
	ных значений		P =0.
			n

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

Рис.6: Четырехканальный сигнатурный анализатор.

Здесь в качестве примера использован полином (x) 1 x3 x4 . Он используется для анализа выходных реакций четырехвыходных цифровых схем. При этом конечное значение кода a1 (k)a2 (k)a3 (k)a4 (k) является результирующим значением сигнатуры S(y), представляющей собой компактную оценку сжатия четырех последовательностей

yi (k),i 1,4 .

Можно показать, что схема, приведённая на рисунке, эквивалентна относительно конечного результата схеме двухступенчатого сжатия информации. Оба подхода получе-

ния сигнатур отличаются неравномерностью закона распределения вероятностей Pn не-

обнаружения ошибки кратности , а, следовательно, невысокой эффективностью. Кроме того, сигнатура многоканального сигнатурного анализатора, а также размерность сигнатуры S(y) однозначно определяется количеством выходов n исследуемой схемы. Поэтому с увеличением n сложность устройства сжатия и количество бит, используемых для представления сигнатуры S(y), принимает практически недопустимые размеры. Попытка использовать идею каскадирования многоканальных сигнатурных анализаторов позволяет уменьшить размерность результирующей сигнатуры, однако в этом случае оказывается сложным оценить достоверность такого анализатора, которая будет зависеть от организации взаимосвязи МСА и их конкретной реализации. Также сложно оценить достоверность МСА.

2. Синтез многоканального сигнатурного анализатора, основанный на использовании матрицы состояния.

Работа такого многоканального сигнатурного анализатора будет описываться фор-

мулой:

A(k s) V s A(k )

(2.4.1)

где A(k+s) и A(k) – m-мерные векторы состояний сигнатурного анализатора,

A (a1 , a2 ,..., am ) .

Соответственно, (k+s) состояние сигнатурного анализатора будет описываться выражением (2.4.1) .Отсюда следует, что функциональные связи между регистрами сдвига МСА будут описываться матрицей вида:

		1		2 ...	m 1	m S
			1	0 ...	0	0
V	S		0	1 ...	0	0
		... ... ... ...				...
			0	0 ...	1	0

где S - число входов многоканального сигнатурного анализатора, а i 0,1 ко-

эффициенты порождающего полинома φ(x).

Сигнатурный анализатор, построенный по данной методике, выглядит следующим образом:

Рис.7: Восьмиканальный сигнатурный анализатор.

Недостатком этого метода является то, что количество входов n сигнатурного анализатора зависит от старшей степени порождающего полинома φ(x). Этот метод может быть использован лишь при условии: n m [1].

3. Синтез многоканального сигнатурного анализатора, основанный на системе логических уравнений.

Наиболее предпочтительным методом синтеза МСА является метод, позволяющий синтезировать МСА с произвольным числом входов и не зависящим от него множеством элементов памяти, определяемым только старшей степенью порождающего полинома φ(x).Также старшая степень полинома определяет разрядность сигнатур и достоверность тестирования.

Для произвольного φ(x) функционирование одноканального сигнатурного анализатора описывается системой уравнений:

ai (0) 0 , i 1, m ;

(2.5.1)

m

a1 (k) y(k)

i ai (k 1) ;

(2.5.2)

i 1

a j (k) a j 1 (k 1) ,

j 2, m , k 1,l ;

(2.5.3)

где y(k) {0,1} - k-й символ сжимаемой последовательности {y(k)},

k 1,l , где l-

длина сжимаемой последовательности, i {0,1} - коэффициенты порождающего полинома φ(x), ai (k 1) {0,1} - содержимое i-го элемента памяти регистра сдвига в k-1-й такт.

Из выражения (2.5.2) следует, что содержимое первого элемента памяти анализатора в (k+2)-й такт работы равно:

m		m
a1 (k 2) y(k 1) 1 y(k) 1		i ai (k)		i ai 1	(k) ;
i 1		i 2
а в (k+3)-й такт:

							m
a1 (k 3) y(k 2) 1 y(k 1) 1 1 y(k) 1 1										i ai	(k)
							i 1
m				m		m
1		i ai 1 (k)	2 y(k)	2		i ai (k)		i ai 2 (k)
i 2				i 1		i 3

В общем случае для некоторого (k + l)-го такта можно записать:

l		m
a1 (k l)		i (l)y(k 1 i)		i	(l)ai (k) ;
i 1		i 1

(2.5.4)

где i (l) {0,1},i 1, m , коэффициенты, позволяющие формировать сдвинутую на l

тактов копию М-последовательности, описываемой полиномом φ(x). Значения δi(l) определяются из системы уравнений:

l 1

i (l) i l 1

n i

(l n),

i 1, m l 1,

l 1, m ;

n 1

(2.5.5)

l 1

(l n),

i m l 2, m,

l 1, m ;

i (l)

n i

n 1

m

i (l)

(l n),

i 1, m,

l 1, m ;

n i

n 1

Коэффициенты i (l) {0,1} определяются как:

i (l) 0,

i l

i (l) 1,

i l

l i

i

(l

n),

l i,

l i m

i (l)

n

n 1

m

i (l)

i

(l

n),

l i m

n

n 1

(2.5.6)

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

y1 (k) y2 (k) ... yl (k) y1 (k 1) ... yl (k 1) y1 (k 2) ... yl (k 2) ;

(2.5.7)

где yv (k) {0,1} — значение двоичного символа на υ-м выходе ЦУ в k-й такт рабо-

ты ЦС. Таким образом, в каждый такт работы анализатора на его вход последовательно, начиная с первого выхода ЦУ, поступают значения yυ(k). При этом в соответствии с (2.5.1) и (2.5.2) функционирование одноканального анализатора в l-канальном режиме описывается системой:

l					m
a1 (k l)		i	(l) yi	(k)			i	(l)ai	(k)
i 1					i 2
a j (k l) a1 (k l 1 j),					j l 1

a j (k l) a j l (k),	j l 1,	k 0, 1, 2, , j 2, m

(2.5.8)

Основываясь на (2.5.8), оказывается возможным построение многоканального анализатора, выполняющего за один такт те же преобразования с последовательностью (2.5.7), что и одноканальный за l тактов [3].

Алгоритм построения многоканального сигнатурного анализатора состоит из следующих этапов.

1. Для заданной вероятности Рd обнаружения ошибки определяется количество m элементов памяти сигнатурного анализатора с учетом неравенства

P 1

1

(2.5.9)

d 2m

2.Выбирается порождающий полипом φ(х) и находятся численные значения коэффициентов i {0,1},i 1, m , причем deg φ(x) = m.

3.Задается количество l входов анализатора.

4.С использованием (2.5.5) вычисляются постоянные коэффициенты δi(l+1-j), i=(1,

2, 3, … ,m), j=(1, 2, … c) где с = min(l, m).

5. Определяются коэффициенты βi, (l+1-j) Є {0, 1}, i=(1, 2, … l), j=(1, 2, … с), из системы

l (l) 1

	c 1
l 1 j i			(l),	j 1,			l 1,
		n l j n
	n 1
l 1 j i	(l 1 j) l j (l),			i 0,			l j,			j 1, c

(2.5.10)

получаемой на основе (2.5.6).

6. Строится функциональная схема многоканального сигнатурного анализатора с помощью системы логических уравнений

l 1 j					l 1 j
a j (k 1)		i	(l 1 j) yi (k)				(l 1 j) a(k),	j 1, c
						i
i 1					i 1
a j (k 1) a j l (k),			j c 1, m.

Применение многоканальных анализаторов для диагностики неисправно-

стей.

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

щей информацию о её присутствии. Рассмотрим возможные варианты решения данной задачи для случая применения n–канальных анализаторов.

Предварительно докажем следующую теорему.

Теорема: Суммарная сигнатура S(x), полученная для последовательностей

yv (k) , v 1, n, k 1,l на n-канальном сигнатурном анализаторе, равна поразрядной сумме по модулю два сигнатур Sv (x) , v 1, n , причём каждая из сигнатур S j (x), j 1,2...n ,

формируется для последовательности yv (k) при условии, чтоyq (k) 00...0, q j 1,2...n .

Используя результаты теоремы, можно формализовать процедуру контроля цифро-

вой схемы. При этом входными последовательностями yv (k) , v 1, n, k 1, l этого анализатора в общем случае могут быть последовательности, формируемые на входных, промежуточных и выходных полюсах схемы, для которых в результате предварительных ис-

следований определены значения эталонных сигнатур Sv (x), v 1, n . Не нарушая общности, предположим, что n=2d, и представим процедуру контроля цифровой схемы с локализацией неисправности до первой последовательности, содержащей вызванные ею ошибки

ввиде следующего алгоритма:

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

n	l	n	n
yv* (k)x(k 1)n v 1 gv (x) 1 (x) Sv				(x)
v 1	k 1	v 1	v 1	(3.2.1)
По выражению
	n
S(x) Sv		(x)		(3.2.2)
	v 1

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

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

Все множество входных последовательностей разбивается на две группы, причём

номера последовательностей {y1 (k)},{y2 (k)},...{yn / 2 (k)} составляют множество

А1={1,2,3…n/2}, а номера последовательностей {yn / 2 1 (k)},{yn / 2 2 (k)},...{yn (k)} составляют множество А2={n/2+1,n/2+2,…n}. Значению i присваивается значение 1.

В результате анализа реальных последовательностей, номера которых задаются множеством А1 на n–канальном сигнатурном анализаторе при условии, что последовательности, номера которых определяет множество А2, являются нулевыми, определяется значение реальной сигнатуры.

На основании выражения

n
S(x) S j (x)
j A1	(3.2.3)

определяем S(x).

Проверяется справедливость равенства S*(x)=S(x), в случае выполнения множество А1 заменяется элементами множества А2.

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

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

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

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

Развитием рассмотренного алгоритма может быть построение процедуры определения всех последовательностей, содержащих ошибки. Это позволит более точно провести диагностирование неисправностей. Для реализации такого алгоритма могут быть использованы методики, применяемые в случае одноканального сигнатурного анализа.

3.3 Расчет достоверности многоканального сигнатурного анализатора.

На практике были рассчитаны достоверности многоканального сигнатурного анализатора при старших степенях порождающего полинома соответственно равных 4, 8, 12 и 16. Их вероятности необнаружения ошибки представлены в виде диаграммы:

m	m	m	m
=4	=8	=12	=16
0	0	0	0
0	0	0	0
0,	0	0	0,
076923	,00395	,00024	000015
0,	0	0	0,
076923	,00395	,00024	000015
0,	0	0	0,
055944	,00391	,00024	000015
0,	0	0	0,
055944	,00391	,00024	000015
0,	0	0	0,
067599	,00391	,00024	000015
0,	0	0	0,
067599	,00391	,00024	000015

	вероятность необнаружения ошибки при разных m
	0,09
	0,08
	0,07
Pn	0,06
,
вероятность	0,05
	0,04
	0,03
	0,02
	0,01
	0
	1	2	3	4	5	6	7	8
				критерий ошибки				Рис. 3.1

Теорема: Множество ошибок последовательности y1 (k) k 1,2m 1, не обнаруживаемых одноканальным СА, реализованном на основании примитивного полинома

(x) , m deg (x) которого равна m, соответствует множеству необнаруживаемых

ошибок n=2d – канальным анализатором, описываемым полиномом (x) (d – целое положительное число),[6] при условии отсутствия ошибок в последовательностях

{yg (k)}, g 2, n , любом целом положительном d.

Если рассчитать вероятность необнаружения ошибки при m=8 двумя способами, то есть если мы оценим достоверность анализатора интегральной величиной либо распреде-

лением вероятностей Pn необнаружения ошибки, то при сравнении их значений, мы сможем определить, что результаты идентичны. Это можно более определенно увидеть на графике. При критерии ошибки, начиная с 5, достоверность одна и та же. Значит мы имеем право для расчета достоверности не учитывать значение кратности ошибки, а рассчи-

	P	1
тывать ее, используя интегральную величину	n	2m . Значит можем сказать, что досто-

верность многоканального сигнатурного анализатора не зависит от кратности ошибки

		Ин-
	Рас-	тегр.распр-
µ пред.вер-ти		ние.
1	0	0
2	0	0
	0,0039	0,0039
3	5	1
	0,0039	0,0039
4	5	1
	0,0039	0,0039
5	1	1
	0,0039	0,0039
6	1	1
7	0,0039	0,0039