Методы компактного тестирования

Для современных ЦУ тестовые последовательности имеют, как правило, большую длину. Многие алгоритмы диагностирования предполагают проведение анализа полной реакции проверяемого ЦУ именно на эти "длинные" тесты. Если используемые тесты представляют собой исчерпывающие двоичные последовательности, либо они генерируются с применением заранее выбранных случайных или псевдослучайных алгоритмов, то проблемы воспроизведения и хранения самих тестов не возникает. Однако для выходных реакций ЦУ на тест проблема их хранения имеет место и является достаточно сложной.

Одним из возможных решений сокращения объема сохраняемых выходных реакций является подсчет и использования определенных интегральных оценок, имеющих значительно меньший объем. Упомянутые оценки, получаемые с прменением различных алгоритмов сжатия информации, обычно именуются синдромами, сигнатурами, контрольными суммами и т.п. Методы, основанные на описанном подходе, получили наименование методов компактного тестирования [1-9].

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

Рассмотрим двоичную последовательность проверяемого ЦУ, состоящую из $$|\tau|$$ последовательно формируемых этим устройством двоичных реакций $$R^*= R^*_1R_2^*\ldots R^*_{|\tau|}$$. Пусть $$R$$ - эталонная реакция устройства на тот же тест.

Перечислим наиболее часто реализуемые функции счета:

Функция счета числа единичных значений сигналов в выходной последовательности [5] $$S_0^{(1)}(R^*)=\sum\limits_{j=1}^{|\tau|}{R^*_j}$$

Функция счета числа переходов изменений значений сигналов из 0 в 1 и из 1 в 0 [6] $$S_1^{(\ne)}(R^*)=\sum\limits_{j=2}^{|\tau|}{(R^*_j \oplus R^*_{j-1})}$$

Функция счета числа повторений значений сигналов [3] $$S_1^{(\equiv)}(R^*)=\sum\limits_{j=2}^{|\tau|}{(R^*_j \oplus R^*_{j-1})}$$

Функция счета числа передних фронтов (изменений значений сигналов из 0 в 1) [10] $$S_1^{(01)}(R^*)=\sum\limits_{j=2}^{|\tau|}{(R^*_j\cdot \overline{R^*_{j-1}})}$$

Функция счета числа задних фронтов (изменений значений сигналов из 1 в 0) [10] $$S_1^{(10)}(R^*)=\sum\limits_{j=2}^{|\tau|}{(\overline {R^*_j}\cdot {R^*_{j-1}})}$$

В табл. 26.1 приведены максимальные значения, которые могут принимать функции счета и объем информации, необходимый для хранения этих значений, где целая часть числа $$|\tau |$$обозначена как $$\lceil |\tau |\rceil$$.

Функция	Максимальное значение	Объем информации
$$S_0^{(1)}$$	$$|\tau |$$	$$\log_2{\lceil |\tau |+1\rceil}$$
$$S_1^{(\ne)}$$	$$|\tau |-1$$	$$\log_2{\lceil |\tau |\rceil}$$
$$S_1^{(\equiv)}$$	$$|\tau |-1$$	$$\log_2{\lceil |\tau |\rceil}$$
$$S_1^{(01)}$$	$$|\tau |/2$$	$$\log_2{\lceil |\tau |/2+1\rceil}$$
$$S_1^{(10)}$$	$$|\tau |/2$$	$$\log_2{\lceil |\tau |/2+1\rceil}$$

Из приведенной таблицы видно, что применение функций счета дает значительное сокращение объема хранимой информации. Несомненно, что в этом главное достоинство перечисленных методов сжатия информации. Однако следует иметь в виду, что при сжатии различных последовательностей вполне возможно получение совпадающих интегральных оценок, т.е. снижение разрешающей способности тестирования.

Для компенсации этого недостатка в работах [5,6] для комбинационных одновыходных устройств предложены методы построения диагностических последовательностей, позволяющих при тестировании с использованием функций счета $$S_0^{(1)}$$ или функции счета изменений значений сигналов $$S_1^{(\ne)}$$ отличить свертку эталонной реакции от свертки реакции любой неисправной модификации.

Что касается достоверности результатов вероятностного компактного тестирования комбинационного одновыходного устройства с использованием тех же функций счета $$S_0^{(1)}$$ и $$S_1^{(\ne)}$$ при условии равновероятности возникновения неисправностей, то для нее известна следующая асимптотическая оценка вероятности принятия неисправного устройства за исправное :

$$P\approx\cfrac{1}{\sqrt{\pi|\tau|}}$$

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

В [3] рассмотрены варианты функций счета для $$m$$-выходных устройств, а также предлагается вариант построения теста для проверки исправности устройства с помощью компактного тестирования, использующего в качестве сверток выходных реакций устройства значения сразу трех функций счета.

Еще одна разновидность методов компактного тестирования - это синдромное тестирование, когда в качестве компактной свертки используется так называемый синдром.

Рассмотрим одновыходное комбинационное устройство с $$n$$ входами, реализующее логическую функцию $$f$$. Тогда синдромом этого устройства называется величина, введенная в [7,8], значение которой есть

$$S(f)=\cfrac{s_0^{(1)}(R^*)}{2^n}$$

где $$R^*$$ - выходная последовательность устройства при подаче на вход последовательности, состоящей из $$2^n$$ всевозможных тестовых воздействий. Очевидно, что справедливо неравенство

$$0\le S(f)\le 1$$

Также ясно, что значение синдрома не зависит от конкретной реализации функции $$f$$.

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

По выражению (26.1) легко можно вычислить значения синдрома для простейших логических элементов. Эти значения приведены в табл. 26.2.

	И	И-НЕ	ИЛИ	ИЛИ-НЕ	М2	М2-НЕ
$$S$$	$$1/2^n$$	$$1-1/2^n$$	$$1-1/2^n$$	$$1/2^n$$	$$1/2$$	$$1/2^n$$

Элемент М-2 в этой таблице означает сумму по модулю 2.

Рассмотрим устройство, конфигурация которого показана на рис. 26.1. Предположим, что $$C_1$$ и $$C_2$$ не имеют общих входов и реализуют функции $$f_1$$ и $$f_2$$ соответственно. Тогда схема вычисления значения синдрома для всего устройства, в зависимости от типа элемента $$C$$, приведена в табл. 26.3.

(рис 26.1) Вычисление синдрома сложной функции

Тип элемента $$C$$	Синдром $$S(f)$$
ИЛИ	$$S(f_1)+ S(f_2)- S(f_1) S(f_2)$$
И	$$S(f_1) S(f_2)$$
М2	$$S(f_1)+ S(f_2)-2 S(f_1) S(f_2)$$

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

Если же предположить, что у $$C_1$$ и $$C_2$$ есть некоторое количество общих входов, то для всего устройства согласно [2] синдром вычисляется по выражениям, представленным в табл. 26.4.

Тип элемента $$C$$	Синдром $$S(f)$$
ИЛИ	$$S(f_1)+ S(f_2)- S(f_1f_2)$$
И	$$S(f_1)- S(f_1\overline{f}_2)$$
М2	$$S(f_1)+ S(f_2)- 2S(f_1f_2)$$

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

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

Мы не будем здесь останавливаться на синтезе устройств, поддающихся синдромному тестированию, однако детально ознакомиться с этим можно по работам [7,11,12].

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

$$S_0^{(\oplus)}(R^*)= \bigoplus\limits_{i=1}^{|\tau|}{R_i^*}$$

Понятно, что такая компактная свертка для одновыходного устройства занимает всего лишь один бит, но с ее помощью можно обнаружить любую неисправность, приводящую к нечетному числу инверсий в выходной последовательности. Четное количество инверсий выходных значений данный метод не обнаруживает. Однако такой метод оказывается полезным в процессе проектирования так называемых контролепригодных ЦУ .

Еще один метод компактного тестирования, который кратко описывается ниже, базируется на свертывании выходных последовательностей при помощи сдвигового регистра с обратными связями и сумматором по модулю два на его входе, который называется сигнатурным анализатором .Типовая схема такой системы диагностирования приведена на рис. 26.2.

(рис 26.2) Схема системы диагностирования с применением СА

На этом рисунке $$t_j$$- тестовые воздействия, ОД-объект диагностирования, $$S$$- сдвиговый регистр, $$R^*$$- реакция диагностируемого устройства, $$S_{r}(R)$$, $$S_{r}(R^*)$$ - сигнатуры эталонного и диагностируемого устройства соответственно. В процессе тестирования последовательности любой длины преобразуются в $$r$$-разрядные ($$r$$ - число разрядов регистра $$S$$) кодовые слова, называемые сигнатурами. Если удается выбрать значение $$r$$ и характер обратных связей так, чтобы для исправного устройства и для его неисправных модификаций получались разные сигнатуры $$S_{r}(R^*)$$, то путем сравнения последних с эталонными сигнатурами $$S_{r}(R)$$ будет обеспечены как обнаружение неисправностей, так и их локализация.

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

(рис 26.3) Функциональная схема сигнатурного анализатора

Здесь элементы, содержащие $$c_i$$, - блоки умножения по модулю два. Другими словами, если $$c_i=1$$, то линия, на которой встречается соответствующий блок, замкнута. Если же значение $$c_i=0$$, то можно считать, что соответствующая линия разомкнута. Блоки $$S_1,S_2,\ldots S_r$$ представляют собой D-триггеры. Перед началом работы анализатора содержимое триггеров $$S_1,S_2,\ldots S_r$$ обычно обнуляется. После получения от диагностируемого ЦУ всей выходной последовательности $$R^*$$ содержимое сдвигового регистра (т. е. $$S_1,S_2,\ldots S_r$$) представляет собой вычисленную сигнатуру.

Математическую модель сигнатурного анализатора можно представить в виде линейного автомата над полем GF(2) [14] , функция переходов которого описывается уравнением

$$S'=\left [ \begin{array}{ccccc} c_{r-1} c_{r-2}\ldots c_{1} c_{0}\\ 1 0\ldots 0 0\\ 01\ldots 0 0\\ \vdots \vdots \ddots \vdots \vdots \\ 00\ldots 1 0 \end{array} \right ] S + \left [\begin{array}{c}1\\0\\0\\\vdots\\0\end{array}\right ] x$$

где $$S$$ и $$S'$$ - $$r$$-мерные вектора, представляющие содержимое триггеров $$S_1,S_2,\ldots,S_r$$ соответственно до и после подачи на вход СА очередного выходного значения $$x$$ объекта диагностирования, являющегося очередным входным значением автомата. Операции сложения и умножения в (26.2) выполняются по модулю два. Тогда получение сигнатуры $$S(X)$$ бинарной входной последовательности $$X=(x_1,x_2,\ldots,x_t)$$ можно описать следующим образом: из начального состояния $$S^0=[0]^T=(000\ldots 0)^T$$, получая последовательно входные сигналы из $$X$$, составляющие реакции диагностируемого устройства на подаваемый тест, линейный автомат такт за тактом переходит в определенные уравнением (26.2) состояния, последнее из которых и является сигнатурой $$S(X)$$.

Двоичные константы $$c_0,c_1,\ldots,c_{r-1}$$, определяющие обратные связи в функциональной схеме сигнатурного анализатора, рассматриваются как коэффициенты полинома

$$P(x)=x^r+c_{r-1}x^{r-1}+\ldots+c_2x^2+c_1x+c_0$$

который называют характеристическим многочленом для автомата. В этом случае процедура сжатия информации может рассматриваться как процедура деления полиномов над полем GF(2).При этом в качестве делимого используется поток сжимаемых данных, описываемых полиномом $$\varphi (x)$$ степени $$l - 1$$, где $$l$$ - количество бит в последовательности.. Так, например,

бинарная последовательность $$11110101$$ соответствует полиному $$\varphi (x) = x^7+x^6+x^5+x^4+x^2+1$$.Делителем служит примитивный полином $$\psi (x)$$, в результате деления на который получается частное $$q(x)$$ и остаток $$S(x)$$, связанные соотношением

$$\varphi (x) = q(x)\psi (x) + S(x).$$

Здесь остаток $$S(x)$$ представляет собой полином, степень которого меньше степени полинома $$\psi (x)$$. Именно этот остаток и является искомой сигнатурой.

По завершению подачи входной двоичной последовательности на D-триггерах сдвигового регистра фиксируется двоичный код, представляющий собой сигнатуру $$S(x)$$, обычно отображаемую в СА в виде 16-ричного кода.