Лекция 6
.pdf
Рис.6.5: Схема кольцевого тестирования для дешифратора К155ИД7.
Сигналы управления моделью микросхемы и схемой сравнения не вводятся конечным пользователем в ПЛИС, а логически привязываются к самой системе диагностики при помощи элементов VCC(логическая 1) и
GND(логический 0). Перед началом тестирования, при помощи вых одного сигнала preset, регистр сдвига логически (без управления ПЛИС)
устанавливается в произвольное исходное (начальное) состояние.
Сигналами start и clock зап ускается процесс тестирования. По истечении 7
тактов работы регистр сдвига, при исправной рабо те цифровой схемы,
должен верн уться в исходное состояние. Проверку этого условия осуществляет схема сравнения, которая сравнивает состояния регистра перед началом тестирования и по его завершению . Низкий уровень выходного сигнала rezsravn (логический 0), с видетельствует об исправном состоянии тестируемой ЦС , и напротив, высокий уровень сигнала
(логическая 1), позволяет утверждать , что тестируемая ЦС находится в неисправном состоянии.
Рез ультаты симуляции работы системы диагностики в редакторе временных диаграмм выглядят так:
Рис.6.7: Временные диаграммы тестирования исправной микросхемы К155ИД7.
Как видно из диаграмм, по истечении 7 тактов работы, регистр сдвига возвращается в начальное состояние (на рис.22 это состояние 101). На выходе rezsravn логич еский 0, т . е. тестируемая модель микросхемы дешифратора исправна.
Теперь иск усственно введем ошибк у в тестируемую модель дешифратора.
Рис.6.8: Временные диаграммы тестирования неисправной микросхемы К155ИД7.
Как и ожидалось , по истечении 7 тактов рабо ты, регистр не возвращается в свое исходное состояние (на рис.23 исходное состояние 101, конечное -
001). Сигнал rezsravn принимает значение логической 1, таким образом,
тестируемая модель дешифратора неисправна.
6.2 Достоверность для максимального периода.
Под линейной последовательной системой (ЛПОС) понимается конечный автомат,
заданный уравнениями :
R( 1) AR( ) BX ( ), |
|
|
||
|
Z ( ) CR( ), |
|
|
|
|
|
|
||
где X |
есть входной, |
Z выходной векторы, |
R вектор состояния, |
A, B, C |
векторы над полем GF (2) . |
Матрица A называется матрицей внутренней сети ЛПОС, а |
|||
многочлен det( A I ) называется характеристическим многочленом ЛПОС [2] .
При кольцевом тестировании (КТ) результат проверки получается при наблюдении поведения автономного генератора, в который преобразуется проверяемый элемент. В
тестовом режиме генератор устанавливается в начальное состояние, затем подаются T
тактовых сигналов, где T - период генератора. Если конечное состояние генератора совпадает с начальным, то проверяемое устройство считается исправным, в противном случае — неисправным.
При проверке исправности в системе КТ из-за отсутствия потактного сравнения фактических ответов ДУ с эталонными ответами существует риск принять неисправное ДУ за исправное. Поскольку решение об исправности принимается в результате сравнения рекуррентной свертки этих ответов с эталоном, то возможно появление неправильных ответов, не изменяющих результата свертки. Подобный риск существует в большинстве диагностических систем, использующих сжатие ответов. Для оценки степени этого риска
будем применять такой показатель, как достоверность тестирования.
Множество |
неисправных модификаций |
ЛПОС |
разбивается |
на классы |
эквивалентности 1,..., d , которые представляются |
многочленами g z |
(deg g r) |
||
над GF (2) . Тем |
самым рассматриваются неисправности, |
преобразующие систему в |
||
линейные неисправные модификации. Предполагается, что исправная ЛПОС описывается
неприводимым нормированным многочленом r той степени, |
а появление любого из |
|
2r 1 "неисправных" многочленов происходит с вероятностью |
2 r . Здесь r n для |
|
комбинационного ДУ, r |
для не зависящего от входа |
ДУ, r n для не |
зависящего от выхода ДУ, r |
или n для зависящего от входа и выхода ДУ, |
|
q r |
для произвольного ДУ в системе КД. |
Определим достоверность |
|
тестирования в множестве представителей классов |
1 ,..., d . Для этого достоверность |
||
будем находить по формуле: |
|
|
|
Q r 1 P r , |
|
(6.6) |
|
где |
P r вероятность необнаружения |
неисправностей, вычисляемая при |
|
предположении о равновероятностном появлении дефектов.
Имеется несколько методов определения достоверности, но все они сводятся к определению достоверности по формуле (6.6) Таким образом, разница в определении достоверности различными способами заключается в разнице определения вероятности необнаружения неисправностей P(r) . Рассмотрим эти методы .
1. Произведём подсчёт Q(r) для случая примитивного g z , для которого
формула (6.6) допускает нижнюю оценку. В этом случае система тестирования имеет максимальный период T 2r 1. Поскольку исправность ДУ устанавливается по факту выполнения равенства:
X |
r |
( ) X |
r |
(0) ( T 2r 1) , |
|
(6.7) |
|||
|
|
|
|
|
|
|
|
||
то с учётом неисправностей ДУ это равенство будет выполняться для всех |
|||||||||
неприводимых |
нормированных многочленов g z |
(deg g r) , |
принадлежащих |
||||||
показателю T |
и показателям, являющимся делителями числа T . Число таких |
||||||||
многочленов равно: |
|
|
|
||||||
(r) |
1 |
(k)2r / k , |
|
(6.8) |
|||||
|
|
||||||||
|
|
|
r k \r |
|
|
|
|||
где суммирование проводится по всем делителям |
k числа r ; |
(k) функция |
|||||||
Мёбиуса: |
|
|
|
|
|
|
|
|
|
(k) 1, |
если k 1; |
|
|
||||||
(k) 0, |
если k делится на квадрат простого числа; |
|
|||||||
(k) ( 1)l , если k p1 p2 ...pl .
Формула (1.3) может быть переписана в виде:
|
1 |
|
2r / pi |
|
|
|
r /( p p |
j |
) |
|
|
|
(r) |
|
2r |
2 |
i |
|
... ( 1)l 2r /( p1 p2...pl ) , |
(6.9) |
|||||
|
|
|
|
|||||||||
|
r |
|
i |
ij |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
где r pr1 pr2 |
...prl ; |
p , p |
2 |
,...,p |
различные простые делители |
числа r ; |
||||||
|
|
1 2 |
l |
1 |
|
l |
|
|
|
|
|
|
r1, r2 ,...,rl кратность делителей. Учитывая, что появления исправной и неисправной модификаций системы представляют собой равновероятные и взаимоисключающие
исходы, для системы максимального периода имеем:
P(r) 2 r (r) 1 .
2. |
Второй способ отличается от первого иным определением (r) . А сама |
||||
достоверность рассчитывается по формуле: |
|
|
|||
Q(r) 1 2 r (r) 1 . |
(6.10) |
||||
Если решение об исправности ДУ принимается по результату выполнения |
|||||
равенства |
(6.7) в такте T и невыполнения 1.2 в тактах |
1,2,…,T 1, |
то |
||
неисправные модификации системы с примитивным многочленом |
g z (deg g r) |
не |
|||
будут обнаружены. Число примитивных многочленов равно: |
|
|
|||
(r) |
1 |
(T ) , |
(6.11) |
||
|
|||||
|
|
r |
|
|
|
где |
T 2r 1; (T ) функция Эйлера, которая может быть выражена через |
||||
функцию Мёбиуса следующим образом: |
|
|
|||
(T ) (T / k)k . |
|
|
|||
k\T
Вэтом случае для выражения (6.11) имеет вид :
(r) |
1 |
T |
T |
|
T |
... |
T |
...( 1)l |
T |
|
, |
(6.12) |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
p1 |
|
p2 |
p1 p2 |
|
|
|
|
||
|
T |
|
|
|
p1 p2 ...pl |
|
|
||||||
где |
p1, p2 ,..., pl |
простые делители числа T . Оценка 6.11 |
обычно для |
||||||||||
выражения (6.12) оказывается выше, чем для выражения (6.10).
Оба способа определения достоверности кольцевого тестирования дают примерно одинаковые результаты.
Если T 2r 1- простое число, то неравенство 1.5 для обоих случаев анализа
результатов превращается в равенство:
Q(r) 1 r 1 2 r (2r 1 1) 1 r 1.
Это выражение является нижней границей определения достоверности кольцевого тестирования.
Верхней границей определения достоверности КТ является выражение:
Q(r) 1 1 . 2r
Таким образом, достоверность КТ лежит в пределах:
1 |
1 |
Q(r) 1 |
1 |
. |
(6.13) |
|
|
||||
|
r |
|
2r |
|
|
3. Определим далее достоверность тестирования во множестве неисправных модификаций ЛПОС. Пусть проверяемая ЛПОС преобразована в автономную ЛПОС
(АЛПОС) введением обратной связи, так что уравнение переходов состояний АЛПОС имеет вид:
S( 1) US( ) ,
где S( ) (s1( ),...,sr ( )) вектор-столбец состояний |
АЛПОС; U |
характеристическая матрица над GF (2) , имеющая размер r r . |
Дополнительное |
оборудование, необходимое в тестовом режиме, состоит из дополнительных входов и выходов ЛПОС, используемых только в тестовом режиме, а также дополнительной ЛПОС, включаемой в контур обратной связи проверяемой ЛПОС. Под неисправностью проверяемой ЛПОС будем понимать физический дефект, приводящий к искажению матрицы U АЛПОС. Зададим неисправности в виде множества искажённых матриц
U :U U U , |
где U матрица размера |
r r . |
Так |
как достоверность |
||
определяется по |
формуле 1.1, где P(r) |
вероятность |
необнаружения |
искажения |
||
U U U матрицы U при условии равновероятности всех искажений. |
|
|||||
Таким образом, мощность множества |
оказывается равной числу 2r2 |
различных |
||||
матриц U . Рассмотрим систему простого максимального периода |
T 2r 1. В этом |
|||||
случае каждый примитивный многочлен det(U U zE) g(z) представляет один из классов 1 ,..., d , имеющих одинаковые мощности:
|
r1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 r (2r |
2i ) . |
|
|
|
|
|
|
|
|
|
(6.14) |
||||||
|
i0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Имеет место теорема. |
|
|
|
|
|
||||||||||||
Теорема. |
Пусть характеристический многочлен АЛПОС является неприводимым |
||||||||||||||||
многочленом |
степени |
r |
простого периода |
T . Тогда достоверность кольцевого |
|||||||||||||
тестирования: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
r1 |
|
|
|
|
|
|
|
|
|
|
|
2r2 r |
|
|
(T 1) (2r 2i ) |
|
|||||||
|
|
|
|
|
|
|
|
|
|
i0 |
|
|
|
|
|||
Q(r) 1 |
|
|
|
r 2r |
|
||||||||||||
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
. |
(6.15) |
||||||||
|
|
|
|
2r2 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Формула (6.15) для достоверности Q(r) |
допускает нижнюю и верхнюю оценки. |
||||||||||||||||
|
|
|
|
|
|
|
|
1 |
r1 |
|
|
|
|
|
|||
Так как r T 1 2r , а |
(2r |
2i ) 1, тогда получаем: |
|||||||||||||||
4 |
|||||||||||||||||
|
|
|
|
|
|
|
i0 |
|
|
|
|
|
|||||
1 |
1 |
|
|
1 |
Q(r) 1 |
|
5 |
. |
|
|
(6.15а) |
||||||
2r |
r |
|
2r |
|
|
||||||||||||
|
|
|
|
|
|
|
4 |
|
|
|
|
||||||
Причём это выполняется даже если максимальный период не является простым числом.
Недостатком данного способа определения достоверности КТ по формуле (6.15)
является то, что он даёт точное значение достоверности лишь для простого максимального периода, хотя формула (6.15а) верна для произвольного максимального для данного r периода T . Этого недостатка лишён следующий способ определения достоверности для максимального периода.
4. Повторяя аналогичные третьему способу рассуждения до получения формулы
1.9, определим число "неисправных" многочленов, приводящих к выполнению 1.2, равно
1r (2r 2) , следовательно, для достоверности в полном множестве неисправностей получаем :
|
2r 2 |
|
r1 |
|
1 |
|
|
|
Q(r) 1 |
|
|
(2r 2i ) 1 |
|
|
. |
(6.16) |
|
r 2r r |
2 |
r |
||||||
|
i0 |
|
|
|
Часто на практике не требуется высокой точности вычислений. Поэтому, исходя из выражения 1.8, достоверность может быть грубо определена по формуле:
Q(r) 1 1r .
Но при этом необходимо учесть, что реальная достоверность не может превышать
значения 1 1 .
2r
Таким образом, метод КТ является эффективным способом проверки логической сети из ЛПОС, так как достоверность проверки высока и большинстве случаев требуется небольшое количество дополнительного оборудования. Значения достоверности,
определяемые в полном множестве неисправностей и в множестве представителей классов эквивалентностей, оказываются близкими. Этот факт согласуется с практическим опытом тестирования не только в кольцевых системах.
Достоверность КТ для произвольного периода.
Недостатком определения достоверности КТ в предыдущем разделе является невозможность определения достоверности при произвольном периоде T Tr 2r 1
при фиксированном значении r [1]. Как оказывается на практике, снижение периода T
значительно снижает время на проведение теста (время уменьшается в Tr раз), но при
T
этом возникает вопрос о том, как изменяется достоверность КТ. То есть задача состоит в том, чтобы определить достоверность КТ Q(r) как функцию периода T :
Q Q(r,T ) .
Очевидным фактом является то, что с понижением периода T достоверность КТ должна уменьшаться.
Для начала определим верхнюю границу достоверности для произвольного периода, а саму достоверность определим как функцию:
Q Q(T ) .
Чтобы определить значение верхней границы воспользуемся правой частью неравенства (6.13):
Q(r) 1 1 . 2r
Значение правой части этого неравенства является частным случаем для
максимального периода T |
2r |
1. Более того, эта формула не показывает |
||||||||||||||
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
зависимости достоверности Q от периода T . Если установить зависимость |
||||||||||||||||
достоверности Q от максимального периода T |
2r |
1, тогда это будет справедливо |
||||||||||||||
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
для произвольного периода. Найдем эту зависимость: |
|
|
|
|
|
|
||||||||||
Q(r) 1 |
1 |
1 |
1 |
|
1 |
|
1 |
|
|
|
Tr |
|
|
T |
|
Q(Tr ) . |
2r |
|
|
Tr |
|
|
|
|
T 1 |
||||||||
|
|
2r 1 1 |
|
1 Tr 1 |
|
|
||||||||||
Тогда достоверность для произвольного периода определиться как:
Q |
|
T |
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(6.17) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
T 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
Если период T является простым числом, то можно преобразовать формулу |
||||||||||||||||||||||||||||
(6.15), используя вышеприведённые рассуждения. Тогда получим: |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r 1 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
2r2 r |
|
(T 1) (2r 2i ) |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i 0 |
|
|
|
|
|||||||
Q(r,T ) 1 |
|
|
|
|
r 2r |
|
= |
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
2r2 |
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r 1 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
2r |
2 |
|
|
|
|
|
|
(T 1) (2r 2i ) |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|
||||||
= 1 |
|
T 1 |
|
|
|
r (T 1) |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2r2 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
(T 1) |
r 1 |
|
|
|
|
||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2r 2i ) . |
|
|
|||||||||
T 1 |
|
|
|
r2 |
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
r 2 |
(T 1) i 0 |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
При больших значениях периода T отношение |
T 1 |
1, тогда формула для |
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T 1 |
|
определения достоверности произвольного (не обязательно максимального |
||||||||||||||||||||||||||||
T 2r 1) простого периода примет вид: |
|
|
|
|
||||||||||||||||||||||||
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
r 1 |
|
|
|
|
|
|
|
||||
Q(r,T ) 1 |
|
|
|
|
|
|
(2r 2i ) . |
|
|
(6.18) |
||||||||||||||||||
|
T 1 |
r 2r |
2 |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|||||||||
Верхние и нижние оценки достоверности КТ для формулы 1.10, приведённые по формуле (6.15а), выполняются для произвольного максимального периода
Tr 2r 1. Обобщим их для произвольного периода.
Нижняя оценка примет вид:
|
|
|
|
|
|
1 |
1 |
|
1 |
|
1 |
1 |
1 |
|
Tr |
1 |
|
||||||
Q(r,T ) 1 |
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|||||
2r |
r |
2r 1 1 |
r |
Tr 1 |
r |
Tr 1 |
r |
||||||||||||||||
|
T |
|
|
1 |
; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T 1 |
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Верхняя граница примет вид:
|
|
|
5 |
|
5 |
|
|
|
5 |
5 |
|
||||
Q(r,T ) 1 |
|
1 |
|
1 |
|
1 |
|
. |
|||||||
4 2r |
4 (2r 1 1) |
4 (Tr 1) |
4 (T 1) |
||||||||||||
Итак, для произвольного не обязательно максимального периода получаем |
|||||||||||||||
оценку достоверности КТ: |
|
|
|
|
|
|
|
|
|||||||
|
T |
|
|
1 |
Q(r,T ) 1 |
5 |
. |
|
|
|
(6.19) |
|
|||
T 1 |
|
4 (T 1) |
|
|
|
|
|||||||||
|
r |
|
|
|
|
|
|
|
|||||||
Таким образом, формулы (6.13), (6.15) и (6.15а) являются частными случаями |
|||||||||||||||
формул соответственно (6.17), (6.18 )и (6.19) когда период |
T является максимальным |
||||||||||||||
для данного значения r , то есть равен T T |
2r 1. |
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
r |
|
|
|
|
|||