Моделирование сигнатурного анализатора

ВВЕДЕНИЕ.
Широкое распространение радиоэлектронных устройств с применением
цифровой обработки сигналов обуславливает повышенный интерес к вопросам
диагностирования их технического состояния.
Одной из разновидностей диагностирования цифровых узлов и блоков
является тестовое диагностирование, применение которого на этапе
проектирования и изготовления цифровых узлов позволяет определить
правильность их функционирования и осуществить процедуру поиска
неисправностей. При разработке тестовой диагностики возникает сложность в
определении эталонных реакций при тестировании существующих схем, в
определении оптимального числа контрольных точек для снятия выходной
реакции диагностируемой цифровой схемы. Это можно сделать либо создавая
прототип разрабатываемого цифрового устройства и проводя его диагностику
аппаратурными методами, либо осуществляя моделирование на ЭВМ как
цифрового устройства, так и процесса диагностики. Наиболее рациональным
является второй подход, который предполагает создание автоматизированных
систем диагностики [1], позволяющих производить диагностику цифровых
схем на стадии проектирования и способных решать следующие задачи:
1. Производить логическое моделирование цифровых схем с помощью
ЭВМ. Цель логического моделирования состоит в том, чтобы выполнить
функцию проектируемой схемы без её физической реализации. Проверка на
правильность моделирования может быть различной в зависимости от уровня
представления цифровой схемы в ЭВМ. Если, например, осуществляется
проверка только значений логической функции на выходе схемы, то достаточно
представить схему на уровне логических элементов. Для того чтобы проверить
состояния сигналов в схеме, необходимо точно описать задержки срабатывания
всех элементов в условиях синхронизации.
2. Моделирование неисправностей. Задача обнаружения неисправностей в
цифровых схемах состоит в том, чтобы определить, обладает ли цифровая
схема требуемым поведением. Для решения этой задачи необходимо, прежде
всего, установить модель цифровой схемы как объекта контроля, затем метод
обнаружения неисправностей и, наконец, модель неисправностей. С точки
зрения особенностей поведения цифровых схем их можно разделить на
комбинационные и последовательностные. В отношении обнаружения
неисправностей комбинационные схемы являются сравнительно простой
моделью. Последовательностные схемы в отношении поведения
характеризуются наличием внутренних контуров обратной связи, поэтому
обнаружение неисправностей в них в общем случае чрезвычайно затруднено.
3. Моделирование процесса тестовой диагностики.
Классическая стратегия тестирования цифровых схем основана на
формировании тестовых последовательностей, позволяющих обнаруживать
заданные множества их неисправностей. Для реализации генератора тестовой
последовательности желательно использовать простейшие методы,
позволяющие избежать сложной процедуры их синтеза. К ним относятся
следующие алгоритмы:
1) формирование всевозможных входных тестовых наборов, т.е. полного
перебора двоичных комбинаций. В результате применения подобного
алгоритма генерируются счётчиковые последовательности;
2) формирование случайных тестовых наборов с требуемыми вероятностя-
ми единичного и нулевого символов по каждому входу цифровой схемы;
3) формирование псевдослучайных тестовых последовательностей.
Основным свойством распространённых алгоритмов формирования тесто-
вых последовательностей является то, что в результате их применения воспро-
изводятся последовательности очень большой длины. Поэтому на выходах про-
веряемой цифровой схемы формируются её реакции, имеющие ту же длину.
Естественно возникают проблемы их запоминания и хранения. Простейшим
решением, позволяющим значительно сократить объём хранимой информации
об эталонных выходных реакциях, является получение интегральных оценок,
имеющих меньшую размерность. Для этого используются алгоритмы сжатия
информации.
Для того чтобы применять метод компактного сжатия тестирования, необ-
ходимо рационально выбирать алгоритм формирования тестовых последова-
тельностей и метод сжатия информации.[2]
Для диагностики любой комбинационной схемы особый интерес представ-
ляет сигнатурный анализатор, в частности многоканальный сигнатурный ана-
лизатор, в основе построения которого лежит алгоритм сжатия информации -
сигнатурный анализ.
4. Анализ методов оценки эффективности компактного тестирования.
Построение сложных цифровых устройств требует повышенного внимания к
компактным методам тестирования для каждого конкретного применения. По-
этому возникает необходимость в оценке эффективности того или иного метода
компактного тестирования. В настоящее время в литературе рассматриваются
способы сравнения методов компактного тестирования.
Было предложено разработать моделирующий алгоритм, позволяющий
строить многоканальные сигнатурные анализаторы.
Для этого необходимо было решить следующие задачи:
1) Логическое моделирование цифровых схем.
2) Разработка моделирующего алгоритма построения ГПСЧ.
3) Разработка моделирующего алгоритма построения многоканального сиг-
натурного анализатора.
4) Оценка эффективности работы многоканального сигнатурного анализато-
ра.
5) Разработка алгоритма поиска неисправностей
ГЛАВА 1. Существующие методы логического моде-
лирования и диагностики с использованием компакт-
ных оценок.
1.1. Моделирование логических схем на ЭВМ.
Моделирование сложных логических схем на большом числе входных на-
боров эффективно можно осуществлять только при помощи ЭВМ. Для того
чтобы смоделировать работу устройства на ЭВМ, необходимо описать матема-
тическую модель этого устройства в памяти ЭВМ [3].
Логическая схема N считается структурно описанной, если указаны сле-
дующие её характеристики: внешние входы схемы - множество X = {x}; внеш-
ние выходы схемы - множество Z = {z}; элементы схемы - множество D = {d};
внутренние связи между элементами в виде матрицы связей C = {ci,j}, где
ci,j {0,1}; ci,j=1 - если выход элемента di связан со входом элемента dj, для всех
элементов d D.
Другим способом описания схемы является описание схемы в виде спи-
сков: списка входов схемы - описание множества X, списка выходов - описание
множества Z и списка логических элементов и связей между ними - описание
множества D и матрицы C. Списки, описывающие схему, могут быть прямыми
и обратными.
Прямой схемный список - это описание схемы по входам элементов. Для
каждого элемента схемы указывается его порядковый номер на схеме, тип и
номера элементов, выходы которых являются входами для данного элемента.
Обратный схемный список - это описание схемы по выходам элементов.
Для каждого элемента указывается его номер на схеме, тип и номер элементов,
со входами которых соединён выход данного элемента.
Прямой и обратный схемный списки представляют собой компактное опи-
сание матрицы связей между элементами C = {ci,j}, причём для задания матри-
цы достаточно одного из них. Прямой схемный список может быть построен на
основе обратного списка, и наоборот.
В большинстве случаев для моделирования достаточно иметь прямой
схемный список. Обратный схемный список используется для выделения на-
правления распространения сигналов в схеме при моделировании сложного
цифрового устройства с большим числом элементов. В этом случае, если, на-
пример, изменится какая-то подсхема из общей схемы устройства, то модели-
рованию подвергаются только те подсхемы, которые связаны с данной. При
этом значительно сокращается объём моделируемой схемы и объём выводимой
для анализа информации, так как моделирование проводится направленно, т.е.
по пути распространения сигналов в схеме. Если какой-либо элемент схемы из-
меняет своё значение на текущем шаге моделирования, то все подсхемы, свя-
занные с выходом этого элемента, моделируются.
Прямой схемный список удобно использовать при диагностике схемы и
локализации неисправностей в ней, так как он позволяет выделить все возмож-
ные пути распространения ошибочной информации (определить по номеру
элемента, на выходе которого обнаружена ошибка, элементы, которые могут
быть источниками этой ошибки).
В данной работе был использован прямой схемный список.
1.2. Методы анализа.
Методы анализа схем можно разделить на прямые и косвенные. Прямые
методы анализа опираются на различные алгебраические или иные формы, от-
ражающие в том или ином виде структуру схемы. Они позволяют непосредст-
венно синтезировать входные последовательности, необходимые для получения
заданной реакции схемы. Например, синтезировать входные наборы, обеспечи-
вающие появление на выходе схемы нулевого сигнала.
К косвенным методам анализа относятся различные виды моделирования,
позволяющие воспроизводить поведение схемы или отдельных её элементов
при подаче на схему набора входных воздействий, например, оценить правиль-
ность работы спроектированной схемы. Моделируя работу схемы, содержащей
неисправный элемент, на наборах, составляющих контролирующий тест, мож-
но оценить полноту этого теста.
Отметим преимущества и недостатки этих методов. Для прямых методов
требуются построения алгебро-структурных описаний схем на основе схемных
списков; как правило, эти методы ориентированы на определённый класс схем,
например синхронные и асинхронные. Для косвенных методов не требуется по-
строения иных описаний схем, кроме схемного списка, кроме того, они не зави-
сят от класса анализируемых схем. Однако для косвенных методов, по сравне-
нию с прямыми, может потребоваться значительно больше времени для опре-
деления нужного входного воздействия. Косвенные методы анализа носят уни-
версальный характер и применяются в том случае, когда прямые методы не
разработаны или слишком сложны для какого-либо класса схем. Прямые и кос-
венные методы анализа дополняют друг друга. Если, например, тест для схемы
был составлен "вручную" с использованием прямых методов, то моделирова-
ние может быть применено для анализа теста на полноту.
В данной работе предлагается косвенный метод анализа.
1.3. Описание тестовой диагностики.
Проблема тестового диагностирования цифровых схем возникает на раз-
личных этапах их производства и эксплуатации и включает взаимосвязанные
задачи. Первая из них заключается в определении, в каком состоянии находится
исследуемая схема.[3] Основным состоянием цифровых схем является исправ-
ное - это такое техническое состояние схемы, при котором она удовлетворяет
всем требованиям, установленным технической документацией. В противном
случае схема находится в одном из неисправных состояний.
Если установлено, что цифровая схема неисправна, то решается вторая за-
дача: осуществляется поиск неисправности схемы, цель которого - определение
места и вида неисправности.
Из множества различных видов неисправностей выделяется класс логиче-
ских неисправностей, которые изменяют логические функции элементов циф-
ровой схемы. Для их описания в большинстве случаев используются следую-
щие математические модели.
1. Константные неисправности: константный нуль и константная единица,
что означает наличие постоянного уровня логического нуля или логиче-
ской единицы на входах и выходе неисправного логического элемента.
2. Неисправности типа "короткое замыкание" (мостиковые неисправности)
появляются при коротком замыкании входов и выходов логических эле-
ментов и подразделяются на два вида: неисправности, вызванные корот-
ким замыканием входов логического элемента, и неисправности типа
обратной связи.
3. Инверсные неисправности описывают физические дефекты цифровых
схем, приводящие к появлению фиктивного инвертора по входу или вы-
ходу логического элемента, входящего в данную схему.
4. Неисправности типа "перепутывание" заключаются в перепутывании
связей цифровой схемы и вызываются ошибками, возникающими при
проектировании и производстве цифровых схем, которые изменяют
функции, выполняемые схемой.
Классическая стратегия тестирования цифровых схем основана на форми-
ровании тестовых последовательностей, позволяющих обнаруживать заданные
множества их неисправностей. При этом, для проведения процедуры тестиро-
вания, хранятся как сами тестовые последовательности, так и эталонные вы-
ходные реакции схем на их воздействие. В процессе тестирования при соответ-
ствии полученных реакций схемы эталонным она считается исправной, в про-
тивном случае схема содержит неисправность и находится в неисправном со-
стоянии.
Структурные блоки, на которые разбивается задача диагностики, приведе-
ны на рис. 1.1.
Рис.1.1. Основные функциональные блоки, используемые при тестирова-
нии цифровой схемы.
ГТВ – генератор тестовых воздействий (генератор М- последовательности)
ЦС – цифровая схема
МСА – многоканальный сигнатурный анализатор
Блок эталонных реакций - блок, хранящий сжатые выходные реакции
Логическая взаимосвязь функциональных блоков построена следующим обра-
зом: с генератора тестовых воздействий через цифровую схему сигналы посту-
пают на схему сжатия информации (сигнатурный анализатор). Сжатые выход-
ные реакции (сигнатуры) попадают на схему сравнения, где они сравниваются с
эталонными сигнатурами, которые хранятся в блоке эталонных реакций. Далее
информация попадает в устройство вывода информации о состоянии схемы.
Все данные блоки реализованы в виде математической модели на компьютере.
В данной работе в качестве блока сжатия информации смоделирован многока-
нальный сигнатурный анализатор.
1.4. Принципы генерирования случайных и псевдослучайных по-
следовательностей.
В задачах активных экспериментальных исследований современных слож-
ных технических систем с применением статистических методов важное место
принадлежит генерированию сигналов возбуждения.[4] Диктуется это не толь-
ко необходимостью подачи на объект требуемого числа воздействий с задан-
ными свойствами, но и максимальной скорости их выработки. Одним из наибо-
лее распространённых в настоящее время методов формирования таких процес-
сов является преобразование сигналов, получаемых с помощью так называемых
генераторов белого шума (ГБШ). В применении к цифровым методам генери-
рования под белым шумом понимается последовательность некоррелированных
чисел или цифр, распределённых, как правило, по равномерному закону.
Известны два основных метода получения цифрового белого шума: физи-
ческий - генерирование случайных двоичных чисел с помощью специальных
устройств - генераторов случайных чисел (ГСЧ); математический - формирова-
ние псевдослучайных числовых последовательностей (ПСЧП) по специальным
программам или с использованием генераторов псевдослучайных чисел
(ГПСЧ).
Принцип действия ГСЧ состоит в преобразовании случайного сигнала на
выходе физического источника шума в импульсную последовательность с ве-
роятностью появления импульса p(1)=0,5.
Общими и наиболее существенными недостатками, затрудняющими при-
менение ГСЧ, являются ограниченное быстродействие, определяемое первич-
ным аналоговым источником шума; низкая стабильность основных вероятност-
ных характеристик, объясняемая нестабильностью первичных источников,
дрейфом параметров преобразующих схем, источников питания и др., что тре-
бует периодической статистической проверки качества генерируемой последо-
вательности; сложность аппаратурной реализации, вызываемая наличием не-
скольких источников питания; невозможность воспроизведения и предсказания
генерируемых последовательностей в силу их случайной природы и т.д.
Указанные недостатки физических ГСЧ явились причиной всё более ши-
рокого распространения математических методов получения шумовых число-
вых последовательностей. Мгновенные значения таких псевдослучайных по-
следовательностей в отличие от случайных в принципе могут быть предсказаны
заранее. В то же время все оценки статистических характеристик конкретной
реализации ПСЧП совпадают с оценками соответствующей ей случайной вы-
борки. Любую статистическую характеристику псевдослучайной числовой по-
следовательности можно получить, используя реализацию длиной в один пери-
од повторения ПСЧП. Для истинно случайной последовательности это потре-
бовало бы бесконечно большую длину реализации. Искусственное увеличение
периода ПС - сигнала неограниченно приближает его структуру к структуре
одной из возможных реализаций истинно случайного процесса. Однако и при
ограниченных величинах периода в определённых условиях псевдослучайные
числовые последовательности могут заменить случайные. При анализе псевдо-
случайной реализации равной или меньшей длине периода вообще практически
невозможно определить, является ли она отрезком регулярной или случайной
последовательности. С другой стороны, если записать конкретную случайную
реализацию на каком-либо носителе, и периодически воспроизводить её, то по-
лучим регулярную ПСЧП.
Таким образом, с точки зрения реальных характеристик трудно установить
границу между случайными и псевдослучайными числовыми последовательно-
стями. В то же время применение ПСЧП имеет ряд существенных преиму-
ществ: периодический характер псевдослучайного сигнала обуславливает низ-
кий уровень дисперсии оценок, получаемых при усреднении в течение целого
числа периодов; характеристики ПСЧП абсолютно стабильны и определяются
алгоритмом формирования псевдослучайных чисел; последовательность можно
повторить с любого желаемого участка реализации, для чего не требуется
сложных запоминающих устройств и др.
Работу генератора М-последовательности, сумматоры по модулю два ко-
торого включены в межразрядные связи, а порождающий полином равен
M(x)= 1 1x 2x2 ... mxm, можно описать выражением
AM(k)=VMAM(k-1),
где m-мерные вектора AM(k)=(a1M(k), a2M(k),..., amM(k)) и AM(k-1)= =(a1M(k-1),
a2M(k-1),..., amM(k-1)) определяют состояния РС генератора в k-й и (k-1)-й такты
работы соответственно, а матрица VM, описывающая структуру генератора,
имеет вид:
0 0 0 . . . 0 1
1 0 0 . . . 0 1
VM= 0 1 0 . . . 0 2
. . . . . . . .
0 0 0 . . . 1 m-1
Структурная схема генератора М - последовательности, построенного по
способу включения сумматоров в межразрядные связи регистра сдвига пред-
ставлена на рис.1.2.
1 2 m-1
a1(k) a2(k) a3(k) am(k)
Рис.1.2. Генератор М - последовательности с сумматорами по модулю два,
стоящими в межразрядных связях регистра сдвига:
Можно показать [5], что между состояниями AM(k) и A(k) РС генераторов
обоих типов при AM(0)= A(0)=1000...0 существует зависимость, определяемая со-
отношением:
a1M(k) m m-1 m-2 . . . 2 1 a1(k)
a2M(k) 0 m m-1 . . . 3 2 a2(k)
a3M(k) = 0 0 m . . . 4 3 a3(k)
. . . . . . . . . . . . . . . . . . . . .
amM(k) 0 0 0 . . . 0 0 am(k)
При этом, порождающий полином (x) M-последовательности, генератор
которой содержит сумматоры по модулю два в цепи обратной связи, является
взаимно обратным к полиному M(x), т.е. (x)= M-1(x)=xm M(x-1).
1.5. Особенности построения генераторов тестовых последова-
тельностей.
При компактном тестировании для реализации тестовой последовательно-
сти используются простейшие методы, позволяющие избежать сложной проце-
дуры синтеза.[2] К ним относятся следующие процедуры синтеза:
1. Формирование всевозможных входных тестовых наборов, т.е. полного пе-
ребора двоичных комбинаций. В результате применения подобного алго-
ритма генерируются так называемые счётчиковые последовательности.
2. Формирование случайных тестовых наборов с требуемыми вероятностями
появления единичного и нулевого символов по каждому входу ЦС.
3. Формирование псевдослучайных тестовых последовательностей.
Основным свойством этих алгоритмов является то, что в результате их при-
менения воспроизводятся последовательности очень большой длины. Поэтому
на выходах проверяемой ЦС формируются её реакции, имеющие ту же длину.
При этом если для генераторов тестовых последовательностей, формирующих
счётчиковые, случайные и псевдослучайные последовательности, не существу-
ет проблемы их запоминания и хранения, то для выходных реакций каждой
схемы такая проблема имеет место быть. Простейшим решением, позволяющим
сократить объём хранимой информации об эталонных выходных реакциях, яв-
ляются методы компактного тестирования.
ГЛАВА 2.Сигнатурный анализ.
2.1. Описание сигнатурного анализа.
В настоящее время в новой технике тестирования цифровых схем сигна-
турный анализ применяется наиболее часто. Это было предопределено не-
сколькими причинами [5], например такими: Равномерность закона распреде-
ления вероятности необнаружения ошибки кратности i и Множество не-
обнаруживаемых ошибок V кратности i включает в себя маловероятные кон-
фигурации ошибочных бит в последовательности данных.
Построить сигнатурный анализатор можно двумя способами: 1)метод де-
ления полиномов и 2)метод свёртки.
Главная идея сигнатурного анализа при использовании метода деления по-
линома на полином основывается на выполнении операции деления многочле-
нов. В качестве делимого используется поток данных, формируемых на выходе
анализируемого цифрового узла, который может быть представлен как много-
член p(x) степени -1, где - длина потока. Делителем служит примитивный
неприводимый полином (x), в результате деления на который получается ча-
стное q(x) и остаток S(x), связанные соотношением
p(x)= q(x) (x)+ S(x),
где остаток S(x), представляющий собой полином степени, меньшей чем
m=deg (x), называется сигнатурой.
M2 D TT M2 D TT M2 D TT
P(x)
C 0 C 1 C m-1
ТИ
& & &
0=1 1 m-1
Рис.2.1. Функциональная схема сигнатурного анализатора, построенного
по методу деления полиномов.
M2 M2
P(x) & & &
M2 D TT D TT D TT
C 0 1 C 1 m-1 C m-1 m=1
ТИ
Рис.2.2. Функциональная схема сигнатурного анализатора, построенного
по методу свёртки.
При использовании метода свёртки сигнатурного анализа как метода сжа-
тия реакций цифровой схемы сигнатура R6=a1( )a2( )...am( ) формируется по ал-
горитму:
a1(0)=a2(0)=...=am(0)=0, (2.1.1)
a1(k)=y(k) i ai(k-1), (2.1.2)
aj(k)=aj(k-1), j=2,3...m, k=1,2... , (2.1.3)
где i {0,1}, i=1,2...m, определяются на основании порождающего поли-
нома (x)=1 1x1 2x2 ... mxm, используемого для реализации сигна-
турного анализатора.
Однако, результат свёртки c(x) последовательности на сигнатурном анали-
заторе не есть остаток s(x) от деления на полином (x). В то же время между
c(x) и s(x) существует однозначная связь, определяемая соотношением
1 2 ... m-1 1
2 3 ... 1 0
s(x)= c(x) ........................................
m-1 1 ... 0 0
1 0 ... 0 0
2.2. Одноканальный сигнатурный анализатор.
Типовая структурная схема сигнатурного анализатора состоит из регистра
сдвига и сумматора по модулю 2, на входы которого подключены выходы раз-
рядов регистра в соответствии с порождающим полиномом (x) (рис. 2.3.) [5].
Управляющими сигналами сигнатурного анализатора являются СТАРТ, СТОП
и СДВИГ. Сигналы СТАРТ и СТОП формируют временной интервал, в течение
которого осуществляется процедура сжатия информации на анализаторе. Под
действием сигнала СТАРТ элементы памяти регистра сдвига устанавливаются в
исходное состояние, как правило, нулевое, а сам регистр начинает выполнять
функцию сдвига на один разряд вправо под действием синхронизирующих сиг-
налов СДВИГ. По приходу каждого синхронизирующего импульса в первый
разряд регистра сдвига записывается информация, соответствующая выраже-
нию (2.1.2), где y(k) {0,1} - k-й символ сжимаемой последовательности {y(k)},
k=1,2... ; i {0,1} - коэффициенты порождающего полинома (x);
ai(k-1) {0,1} - содержимое i-го элемента памяти регистра сдвига в k-1 такт.
Процедура сдвига информации в регистре описывается соотношением (2.1.3).
Причём , как правило, принимается равным или
Сигнатура
M2 RG
Сдвиг Старт Стоп
Рис.2.3. Структурная схема сигнатурного анализатора.
меньше величины 2m-1 и соответственно определяет длину сжимаемой после-
довательности. По истечении тактов функционирования сигнатурного анали-
затора на его элементах памяти фиксируется двоичный код, который представ-
ляет собой сигнатуру, отображаемую в виде 16-ричного кода.
Таким образом, путём формирования тестовой последовательности на вхо-
дах анализируемого цифрового устройства для каждого его полюса находим
эталонные значения сигнатур, множество которых запоминается и в дальней-
шем используется для сравнения со значениями сигнатур, снимаемых с прове-
ряемых устройств. Любое отличие реально полученной сигнатуры от эталонной
свидетельствует о том, что полюс схемы функционирует отлично от случая ис-
правного состояния устройства. Причина, вызвавшая отличие сигнатур на дан-
ном полюсе, может быть установлена последовательным анализом сигнатур от
указанного полюса к входам устройства.
Эффективность использования такого сигнатурного анализатора ограни-
чивается наличием в нём только одного информационного входа, в то время как
количество выходов сложных цифровых узлов достигает значительных вели-
чин. Исследование подобных узлов осуществляется с использованием несколь-
ких сигнатурных анализаторов, путём свёртки по модулю два выходных после-
довательностей или с применением некоторых других схемных решений.[1]
Применение таких подходов для анализа многовыходных цифровых схем при-
водит или к существенному увеличению аппаратурных затрат, или к уменьше-
нию величины вероятности P обнаружения ошибки. Поэтому для многовыход-
ных цифровых узлов создание высокоэффективных цифровых анализаторов
весьма актуально.
2.3. Многоканальные сигнатурные анализаторы.
Проблема анализа многовыходных цифровых схем и процесс их тестирова-
ния заключается в определении возникновения неисправности схемы по её вы-
ходным реакциям. Отличительной особенностью подобного анализа является
необходимость исследования достаточно большого количества выходных реак-
ций схемы (число их может достигать нескольких сотен). Поэтому использова-
ние традиционных методов компактного тестирования, применяемых для одно-
выходных цифровых схем, в данном случае не позволяет получить желаемого
эффекта.[5] Действительно, попытка провести анализ n - выходной цифровой
схемы одноканальным СА приводит к увеличению в n раз времени, необходи-
мого для анализа схемы, или оборудования, требуемого для реализации n сиг-
натурных анализаторов. При этом остаётся открытым вопрос о разрядности
сигнатуры, которая также может увеличиться в n раз. Поэтому на практике ча-
ще всего используют специальные методы и приёмы. Наиболее часто приме-
няемым из них является метод, основанный на преобразовании n выходных по-
следовательностей длиной в одну последовательность
по выражению:
(2.3.1)
Практическая реализация этого метода может быть выполнена как процедура
сжатия в пространстве или во времени. В том и другом случае реализуется идея
получения компактных оценок, характерная для методов компактного тестиро-
вания.
Как показано в [6] эффективность алгоритма сжатия информации, реали-
зующего соотношение (2.3.1) определяется как:
(2.3.2)
где ? - кратность ошибки, причём для нечётных значений ? ( - это ве-
роятность необнаружения ошибки кратности ?).
Для оценки вида распределения вероятностей рассмотрим конкретный
пример n=3 – выходной цифровой схемы, длина выходных реакций которой
составляет 21. В результате преобразования трех исходных последовательно-
стей в последовательность , некоторые их
ошибки станут необнаруживаемыми и будут оцениваться выражением:
(2.3.3)
которое справедливо для .
Ограничиваясь , определяем согласно (2.3.3) .
Анализ полученных численных значений вероятностей , а также общего
выражения (2.3.2) показывает неравномерность закона их распределения, что
свидетельствует о достаточно невысокой эффективности рассматриваемого ал-
горитма сжатия. Кроме того, необходимо отметить большую размерность ре-
зультата сжатия, которая равна длине выходных реакций схемы. Поэтому на
практике чаще всего используется компромиссное решение, заключающееся в
двухступенчатом преобразовании выходных реакций n – выходной цифровой
схемы. Первоначально n выходных последовательностей длиной пре-
образуются в последовательность по выражению (2.3.1). Далее сформи-
рованная таким образом последовательность снимается в m – разрядную
сигнатуру (рис. 2.4)
Y1(k) 1 2 3 . . . j . . . m
Y2(k)
Y0(k) S(x)
Yn(k)
Рис. 2.4. Многоканальный сигнатурный анализатор.
Эффективность данного преобразования согласно [6] при ?=4 определится
как
(2.3.4)
где m – старшая степень порождающего полинома.
Эта формула справедлива, когда .
Наиболее распространенная структура многоканального сигнатурного ана-
лизатора для исследования многовыходных цифровых схем, которая построена
на базе порождающего полинома , приведена на рис. 2.5.
?1(k) ?2(k) ?3(k) ?4(k)
M2 M2 M2 M2
D TT D TT D TT D TT
C C C C
a1(k) a2(k) a3(k) a4(k)
ТАКТ
M2
Рис. 2.5. Четырехканальный сигнатурный анализатор.
Она используется для анализа выходных реакций четырехвыходных циф-
ровых схем. При этом конечное значение кода является ре-
зультирующим значением сигнатуры S(y), представляющей собой компактную
оценку сжатия четырех последовательностей
Можно показать, что схема, приведённая на рис.2.5, эквивалентна относи-
тельно конечного результата простейшей сигнатуры двухступенчатого сжатия
информации (рис. 2.4). А это значит, что в обоих случаях для оценки эффек-
тивности можно применять формулу (2.3.3). Оба подхода получения сигнатур
отличаются неравномерностью закона распределения вероятностей необна-
ружения ошибки кратности ?, а, следовательно, невысокой эффективностью.
Кроме того, сигнатура многоканального сигнатурного анализатора (МСА), а
также размерность сигнатуры S(y) однозначно определяется количеством вы-
ходов n исследуемой схемы. Поэтому с увеличением n сложность устройства
сжатия и количество бит, используемых для представления сигнатуры S(y),
принимает практически недопустимые размеры. Попытка использовать идею
каскадирования многоканальных сигнатурных анализаторов позволяет умень-
шить размерность результирующей сигнатуры, однако в этом случае оказыва-
ется сложным оценить достоверность такого анализатора [6], которая будет за-
висеть от организации взаимосвязи МСА и их конкретной реализации.
2.4.Многоканальный сигнатурный анализатор использованный в
данной работе.
Предположим, что рассмотренный одноканальный анализатор используется
для анализа цифрового узла, имеющего каналов, причём выходных после-
довательностей в данном случае преобразуются в одну последовательность ви-
да
где - значение двоичного символа на -м выходе цифрового узла в
-й такт его работы, а тактовая частота работы анализатора в раз выше часто-
ты синхронизации исследуемого узла. При этом в каждый такт работы анализа-
тора на его вход последовательно, начиная с первого выхода, поступают значе-
ния . Функционирование одноканального анализатора в многоканальном
режиме, когда количество каналов равняется , описывается системой уравне-
ний
где численное значение коэффициентов определяется на основании
следующей системы уравнений
Коэффициенты определятся следующим образом:
2.5. Алгоритм построения многоканального сигнатурного анали-
затора.
Для заданных значений и , где определяет достоверность диагности-
рования, алгоритм построения многоканального сигнатурного анализатора со-
стоит из следующих этапов.
1. Вычисляются постоянные коэффициенты
где
2. Определяются коэффициенты причём
значения коэффициентов вычисляются на основании соответствующей
системы уравнений, а значения остальных коэффициентов определяются
согласно выражению
3. Строится функциональная схема многоканального сигнатурного анализатора
на основании полученной системы уравнений
При этом используются результаты этапов 1 и 2, позволяющих однозначно оп-
ределить топологию связей многовходовых сумматоров по модулю два, на вы-
ходах которых формируются значения .
2.6. Применение многоканальных анализаторов для диагностики
неисправностей.
С помощью многоканальных сигнатурных анализаторов можно существенно
ускорить процедуру контроля цифровых схем, которая практически увеличива-
ется в n раз, где n – количество входов применяемого анализатора. В случае
совпадения реально полученной сигнатуры с её эталонным значением считает-
ся, что с достаточно высокой вероятностью проверяемая цифровая схема нахо-
дится в исправном состоянии. На этом процедура её исследования оканчивает-
ся. В противном случае, когда схема содержит неисправности, реальная сигна-
тура, как правило, отличается от эталонной, что служит основным аргументом
для принятия гипотезы о неисправном состоянии схемы. В тоже время вид по-
лученной сигнатуры не несёт никакой дополнительной информации о характе-
ре возникшей неисправности. Более того, остаётся открытым вопрос о том, ка-
кие из n анализируемых последовательностей, инициирующих реальную сигна-
туру, содержат ошибки, т.е. возникает задача локализации неисправности с
точностью до последовательности, несущей информацию о её присутствии.
Рассмотрим возможные варианты решения данной задачи для случая примене-
ния n – канальных анализаторов.
Предварительно докажем следующую теорему.
Теорема. Суммарная сигнатура S(x), полученная для последовательностей
на n – канальном сигнатурном анализаторе, равна поразряд-
ной сумме по модулю два сигнатур , , причём каждая из сигнатур
, формируется для последовательности при условии, что
.
Доказательство. В n – канальном анализаторе n входных последовательно-
стей преобразуются в одну вида:
Такая входная последовательность, анализируемая n канальным сигнатурным
анализатором, описывается следующим двоичным полиномом:
, (2.6.1)
который состоит из суммы по модулю два полиномов вида:
, (2.6.2)
описывающих выходные последовательности . Каждый полином
можно представить в виде соотношения:
, (2.6.3)
где -полином, взаимно обратный полиному , используемому для реа-
лизации n – канального сигнатурного анализатора; - сигнатура последова-
тельности .
Просуммировав по модулю два правые и левые части равенства (2.6.3), полу-
чим, что полином будет определяться как
(2.6.4)
для которого также справедливо соотношение , т.е.
(2.6.5)
В результате сравнения двух последних равенств можно заключить, что сум-
марная сигнатура S(x), полученная для последовательностей рав-
на поразрядной сумме по модулю два сигнатур каждой из входных после-
довательностей:
(2.6.6)
что и требовалось доказать.
Основной результат данной теоремы, выраженный соотношением (2.6.5),
справедлив для примитивного полинома и произвольных значений n и l.
Следствием этой теоремы является возможность определения эталонной сигна-
туры для произвольного множества входных последовательностей. Так, эта-
лонное значение сигнатуры для первой, второй и пятой последовательностей
будет вычисляться как
Используя результаты теоремы, можно формализовать процедуру контроля
цифровой схемы. При этом входными последовательностями
этого анализатора в общем случае могут быть последова-
тельности, формируемые на входных, промежуточных и выходных полюсах
схемы, для которых в результате предварительных исследований определены
значения эталонных сигнатур . Не нарушая общности, предполо-
жим, что n=2d, и представим процедуру контроля в виде следующего алгорит-
ма.
Алгоритм контроля цифровой схемы локализацией неисправности до первой
последовательности, содержащей вызванные ею ошибки.
1. В результате анализа n=2d реальных последовательностей на n
– канальном анализаторе определяется значение сигнатуры S*(x), которое
соответствует соотношению:
2. По выражению
вычисляется эталонное значение сигнатуры S(x).
3. Реальное значение сигнатуры S*(x) сравнивается с эталонной сигнатурой
S(x). В случае выполнения равенства S*(x) и S(x) считается процедура диаг-
ностики оконченной. В противном случае, когда S*(x)?S(x) выполняется
следующий этап алгоритма.
4. Все множество входных последовательностей разбивается на две группы,
причём номера последовательностей составляют
множество А1={1,2,3…n/2}, а номера последовательностей
составляют множество А2={n/2+1,n/2+2,…n}.
Значению i присваивается значение 1.
5. В результате анализа реальных последовательностей, номера которых за-
даются множеством А1 на n – канальном сигнатурном анализаторе при ус-
ловии, что последовательности, номера которых определяет множество А2,
являются нулевыми, определяется значение реальной сигнатуры.
6. На основании выражения
определяем S(x).
7. Проверяется справедливость равенства S*(x)=S(x), в случае выполнения
множество А1 заменяется элементами множества А2.
8. Значение переменной i увеличивается на 1 и сравнивается с величиной n,
если ibr> ва А2.
9. Единственный элемент множества А1 представляет собой номер ошибочной
последовательности.
10. Процедура контроля цифровой схемы считается законченной.
2.7. Оценка достоверности многоканального сигнатурного анали-
затора.
Учитывая эквивалентность функционирования n - канального сигнатурного
анализатора и соответствующего ему одноканального анализатора относитель-
но результата сжатия n входных последовательностей ло-
гично оценить достоверность МСА, используя результаты, полученные для од-
ноканального сигнатурного анализатора. Действительно, в случае применения
примитивного полинома вероятность необнаружения ошибок в последова-
тельностях многоканальным сигнатурным анализатором для
где m – старшая степень порождающего полинома, будет опреде-
ляться соотношением:
Это соотношение справедливо для любого соотношения и , произведе-
ние которых равно 2m-1.[6] Приведённая интегральная характеристика эффек-
тивности МСА, также как и характеристика одноканального сигнатурного ана-
лизатора, является достаточно приближённой оценкой, справедливой для об-
щих допущений. Более полной характеристикой МСА будет распределение ве-
роятностей необнаружения возникшей ошибки кратности ? в анализируе-
мых последовательностях . При этом численное значение указанных ве-
роятностей, как и в случае одноканального анализатора, определяется выраже-
ниями:
Попытка применить это выражение для оценки значений при анализе по-
следовательности , когда на n – канальном анализаторе не
всегда позволяет получить верные результаты.
Теорема. Множество ошибок последовательности необна-
руживаемых одноканальным СА, реализованном на основании примитивного
полинома , старшая степень которого равна m, соответствует множеству
необнаруживаемых ошибок n = 2d – канальным анализатором, (d – целое поло-
жительное число) при условии отсутствия ошибок в последовательностях
.
Таким образом, достоверность многоканального сигнатурного анализатора
может быть оценена либо интегральной величиной , либо распределени-
ем вероятностей необнаружения ? - кратной ошибки в анализируемых по-
следовательностях . Более предпочтительным значением n
является значение, удовлетворяющее требованию n = 2d. Анализ последова-
тельности для на подобном анализаторе будет эквивален-
тен анализу на соответствующем одноканальном анализаторе.
24
4
1111111стр. 23 из 1