Обучающая система методам компактной диагностики.

МИНИСТРЕСТВО ОБЩЕГО И ПРОФЕСИОНАЛЬНОГО
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
___________________________________________________________
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Физический факультет
Кафедра радиофизики
ДИПЛОМНАЯ РАБОТА
Обучающая система методам компактной диагностики.
Исполнитель: студент гр.644
Ким В.Л.
Руководитель: ст. преподаватель
каф. р/ф
Таюрская Г.В.
Казань - 1999 г.
Оглавление.
Введение. 4
Глава 1.
Обзор методов компактного тестирования и типы неисправностей
цифровых схем.
1.1 Классификация методов сжатия выходных реакций схем. 5
1.2 Типы неисправностей цифровых схем. 10
1.3 Генераторы тестовых последовательностей. 12
Глава 2.
Практическая реализация системы обучения методам компактного
тестирования.
2.1 Реализация графического интерфейса. 17
2.2 Разработка и реализация алгоритма моделирования цифровых
схем, позволяющая моделировать ЦС различной сложности,
использующие различные элементные базы.
19
2.3 Реализация алгоритма, моделирующая работу генераторов
тестовых последовательностей:
23
? генератор счётчиковой последовательности;
? генератор М-последовательности;
2.4 Разработка и реализация модуля моделирующего алгоритм
диагностики с использованием компактных методов тестирования:
24
? сигнатурный анализатор;
? метод счёта единиц;
2.5 Блок поиска неисправностей; 28
2.6 Определение оценки эффективности метода сигнатурного
анализа и метода счёта единиц.
31
? Достоверность сигнатурного анализа.
? Достоверность метода счёта единиц.
Глава 3.
Описание программы 35
Экспериментальная часть. 38
Заключение. 42
Литература. 43
Приложение 44
Введение.
Неуклонный рост сложности приборов обуславливает повышенный
интерес к вопросам диагностирования их технического состояния. Од-
ной из разновидностей методов технического диагностирования аппара-
туры является тестовая диагностика, позволяющая на этапе проектиро-
вания и изготовления решать основные задачи: определять
правильность функционирования, осуществлять поиск неисправностей
и определять тип неисправности. Для реализации этих задач требуется
интенсификация подготовки специалистов по вычислительной технике
и технической диагностике, владеющих методикой исследования и
проектирования сложных цифровых систем с использованием
современных методов технической диагностики.
Основной задачей дипломной работы является разработка автомати-
зированной системы обучения диагностике сложных цифровых схем,
позволяющей детально знакомить студентов с практическими
возможностями использования современных методов компактного
тестирования.
Она должна представлять собой программу, включающую в себя:
? Модуль, реализующий графический интерфейс. Обмен графической
информацией между пользователем и ЭВМ должно осуществляться в
форме диалога;
? модуль, реализующий логическое моделирование цифровых схем;
? модуль, моделирующий работу генераторов тестовых последователь-
ностей;
? блок, моделирующий процесс диагностики. В него входит: блок мо-
делирующий работу многоканального сигнатурного анализатора,
блок отображения и обработки полученных данных, блок поиска
неисправностей;
? блок, реализующий алгоритм определения оценки эффективности
диагностики при использовании компактных методов диагностики.
Глава1.
Обзор методов компактного тестирования и типы неисправностей
цифровых схем.
1.1 Классификация методов сжатия выходных реакций схем.
Классическая стратегия тестирования цифровых схем основана на
формировании тестовых последовательностей, позволяющих обнаружи-
вать заданные множества их неисправностей. При этом для проведения
процедуры тестирования, как правило, хранятся как сами последователь-
ности, так и эталонные выходные реакции схем на их воздействие. В про-
цессе самой процедуры тестирования на основании сравнения выходных
реакций с эталонными принимается решение о состоянии проверяемой
схемы.
Для ряда выпускаемых в настоящее время схем классический подход
требует временных затрат как на формирование тестовых последователь-
ностей, так и на процедуру тестирования. Кроме того на проведение тес-
тового эксперимента требуется наличие сложного оборудования. В связи
с этим стоимость и время, необходимые для реализации классического
подхода, растут быстрее, чем сложность цифровых схем, для которых он
используется. Поэтому новые решения, позволяющие значительно упро-
стить как процедуру построения генераторов тестовых последовательно-
стей, так и проведение тестового эксперимента.
Для реализации генератора тестовой последовательности использу-
ются алгоритмы, позволяющие избежать сложности их синтеза:
1. Формирование всевозможных тестовых наборов, т.е. полного пе-
ребора двоичных комбинаций. В результате генерируется так на-
зываемая счётчиковая последовательность.
2. Формирование случайных тестовых наборов с требуемыми веро-
ятностями появления единичного и нулевого символов по каждо-
му входу цифровой схемы.
3. Формирование псевдослучайной тестовой последовательности.
Основным свойством рассмотренных алгоритмов формирования
тестовых последовательностей является то, что в результате их
применения воспроизводятся последовательности очень большой длины.
Поэтому на выходах проверяемой цифровой схемы формируются её
реакции, имеющие такую же длину. Естественно возникает проблема их
запоминания, хранения и затрата на обработку этих последовательностей.
Простейшим решением, позволяющим значительно сократить объём
хранимой информации об эталонных выходных реакциях является
получение интегральных оценок, имеющих меньшую размерность. Для
этого используются алгоритмы сжатия информации.
В результате их применения формируются компактные оценки сжи-
маемой информации. Рассмотрим алгоритмы сжатия данных для случая
бинарной последовательности {y(k)}, состоящей из l последовательно
формируемых двоичных переменных.
Псевдослучайное тестирование.
Наиболее часто при формировании псевдослучайных последователь-
ностей используются два метода. Первый из них лежащий в основе боль-
шинства программных датчиков псевдослучайных чисел, использует ре-
куррентные соотношения. Этот метод обладает рядом недостатков, в ча-
стности, малой периодичностью. Применительно к проблеме тестирова-
ния цифровых схем периодичность может заметно снизить полноту кон-
троля. Кроме того, он отличается сложностью практической реализа-
ции. Поэтому наиболее широко применяется второй метод, основан-
ный на использовании соотношения
К – номер такта; - символы последовательности;
- постоянные коэффициенты; - операция суммиро-
вания по модулю два m логических переменных. При соответствующем
выборе коэффициентов на основании характеристического полинома
,
который должен быть примитивным, последовательность имеет мак-
симальную длину, равную 2м-1. Такая последовательность называется М-
последовательностью.
Использование таких последовательностей предполагает
применение сигнатурного анализа как метода сжатия реакций цифровой
схемы.
Типовая структурная схема сигнатурного анализатора состоит из ре-
гистра сдвига и сумматора по модулю два, на входы которого подключе-
ны выходы разрядов регистра в соответствии с порождающим
полиномом (рис.1.1).
Управляющими сигналами сигнатурного анализатора являются
СТАРТ, СТОП и СДВИГ. Сигналы СТАРТ и СТОП формируют времен-
ной интервал, в течение которого осуществляется процедура сжатия ин-
формации на анализаторе. Под действием сигнала СТАРТ элементы па-
мяти регистра сдвига устанавливаются в исходное состояние, как
правило нулевое, а сам регистр сдвига начинает выполнять функцию
сдвига на один разряд в право под действием синхронизирующих
импульсов СДВИГ. По приходу каждого синхронизирующего импульса в
первый разряд регистра сдвига записывается информация,
соответствующая выражению:
где y(K) {0,1} –к-й символ сжимаемой последовательности {y(K)},
К= ; - коэффициенты порождающего полинома ;
- содержимое i-того элемента памяти регистра сдвига 1 в (к-
1) такт. Процедура сдвига информации в регистре описывается соотно-
шением
Таким образом, полное математическое описание
функционирования сигнатурного анализатора имеет следующий вид:
аi(0)=0, i= , a1(k)=y(k) (1.3)
k= ,
причём l, как правило, принимается равным или меньше величины
(2м-1), и соответственно является длиной сжимаемой последовательно-
сти.
По истечении l тактов функционирования сигнатурного анализатора
на его элементах памяти фиксируется двоичный код, который представ-
ляет собой сигнатуру, отображенную в виде 16-ричного кода.
Синдромное тестирование.
Синдромом (контрольной суммой) некоторой булевой функции n пе-
ременных является соотношение
S=R5/2n,
Где R5 равно числу единичных значений функции согласно таблице
истинности для l=2n. Определение понятия синдрома однозначно предпо-
лагает использование генератора счетчиковых последовательностей для
формирования всевозможных двоичных комбинаций из n входных пере-
менных при тестировании схемы, реализующей заданную функцию.
Дальнейшим развитием синдромного тестирования является спектраль-
ный метод оценки выходных реакций цифровых схем и корреляционный
метод.
1.2 Типы неисправностей цифровых схем.
Проблема тестового диагностирования цифровых схем возникает на
различных этапах их производства и эксплуатации и включает взаимосвя-
занные задачи. Первая из них заключается в определении, в каком со-
стоянии находится исследуемая схема.
Основным состоянием цифровой схемы является исправное – такое
состояние схемы, при котором она удовлетворяет всем требованиям тех-
нической документации. В противном случае схема находится в одном их
неисправных состояний.
Если установлено, что схема неисправна, то решается вторая задача:
осуществляется поиск неисправной схемы, цель которого- определение
места и вида неисправности.
Неисправности ЦС появляются в результате применения неисправ-
ных компонентов, таких, как логические элементы, реализующие про-
стейшие логические функции, элементы памяти и др. кроме того, причи-
ной неисправностей могут быть возникновения разрывов или коротких
замыканий в межкомпонентных соединениях, нарушение условий экс-
плуатации схемы, наличие ошибок при проектировании и производстве и
ряд других факторов.
Из множества различных видов неисправностей выделяется класс
логических неисправностей, которые изменяют функции элементов ЦС
указанный тип неисправностей занимает доминирующее место среди
неисправностей ЦС. Для их описания в большинстве случаев используют
следующие математические модели:
? Константные неисправности;
? Неисправности типа «Короткое замыкание»;
? Инверсные неисправности;
Наиболее общей и часто применяемой моделью логических неис-
правностей являются константные неисправности: константный нуль и
константная единица, что означает наличие постоянного уровня логиче-
ского нуля или логической единицы на одном из полюсов логического
элемента. Такая модель неисправностей часто называется классической и
широко используется для описания других типов неисправностей. Неис-
правности типа «Короткое замыкание» появляются при коротком
замыкании входов и выходов логических элементов.
Инверсные неисправности описывают физические дефекты ЦС, при-
водящие к появлению фиктивного инвертора по входу или по выходу ло-
гического элемента. Инверсные неисправности в совокупности с кон-
стантными, в ряде случаев используются для построения полной модели
неисправной цифровой схемы.
1.3 Генераторы тестовых последовательностей.
Классическая стратегия тестирования цифровых схем основана на
формировании тестовых последовательностей, позволяющих обнаружи-
вать заданные множества их неисправностей. Для реализации генератора
тестовой последовательности желательно использовать простейшие мето-
ды, позволяющие избежать сложной процедуры их синтеза. К ним отно-
сятся следующие алгоритмы:
? формирование всевозможных тестовых наборов, то есть полного
перебора двоичных комбинаций. В результате применения подобно-
го алгоритма генерируются счётчиковые последовательности;
? формирование псевдослучайных тестовых последовательностей;
? формирование случайных тестовых наборов, с требуемыми
вероятностями единичного и нулевого символов по каждому входу
цифровой схемы.
Основным свойством вышеперечисленных алгоритмов является то,
что в результате их применения воспроизводятся последовательности
очень большой длины.
Для процесса обучения были выбраны два первых алгоритма по-
строения генераторов тестовых последовательностей. И разработаны два
модуля для эмуляции работы генераторов:
модуль эмуляция генератора счетчиковой последовательности;
модуль эмуляции работы многоканального генератора М-
последовательности, позволяющий генерировать псевдослучайную по-
следовательность и сравнительно просто регулировать ее максимальную
длину и число каналов в зависимости от числа входов цифровой схемы.
Генератор М-последовательности.
В аппаратурных псевдослучайных датчиках и узлах ЭВМ при гене-
рировании ПСЧП с равномерным распределением наиболее часто
используется метод, который заключается в получении линейной
двоичной последовательности по рекуррентному выражению:
где i - номер такта; символы выходной
последовательности; постоянные коэффициенты. При
соответствующем выборе коэффициентов {?к} генерируемая числовая
последовательность имеет максимальную (для данного m) величину
периода и называется М-последовательностью. Одним из главных
преимуществ метода генерирования ПС – последовательностей
максимальной длины является простота его реализации.
Генератор М-последовательности может быть построен двумя мето-
дами, отличающимися способом включения сумматоров по модулю два:
они могут включаться как в цепь обратной связи генератора, так и в меж
разрядные связи элементов памяти регистров сдвига.
Структурная схема генератора М – последовательности, построенно-
го по способу включения сумматоров в цепь обратной связи
представлена на рис.1.1
Генератор М-последовательности с сумматорами по модулю два,
стоящими в цепи обратной связи: аi,ai-1,ai-2,…ai-m – символы последователь-
ности; ?i – коэффициенты, определяющие вид обратной связи.
Алгоритм размножения М-последовательности.
Для того, чтобы обеспечить различные режимы испытаний, генера-
торы испытуемых сигналов должны удовлетворять ряду требований
(многоканальность, быстродействие, достаточная длина периода и т.д.). В
основе наиболее перспективного метода построения
быстродействующего параллельного генератора псевдослучайных
последовательностей испытательных сигналов лежит идея использования
( в качестве независимых последовательностей для формирования
разрядов очередного кода) участков одной и той же последовательности.
В данном случае генерирование различных участков осуществляется с
помощью ?-входовых сумматоров по модулю два, т.е. ??{2,m}, где m-
разрядность регистра сдвига. Соединения сумматоров по модулю два с
разрядами регистра сдвига определяются набором коэффициентов
?i(1)?{0,1}(i=1,2,3,..m), значения которых зависят от величины сдвига
l(l=1,2,3,…) и вида порождающего полинома.
Методика выбора коэффициентов ?i(1), однозначно определяющих
связи многовходового сумматора по модулю два, описывается на итера-
ционном подходе, когда на основании ?i(h), по расчётным соединениям
находятся ?i(1)(h=1,2,….hbr> Предположим, что коэффициенты ?i(1) и ?i(S), позволяющие полу-
чить сдвинутые копии М-последовательности на 1 и S тактов, известны;
тогда содержимое a1(k+1) первого разряда регистра сдвига в (к+1)-м
такте работы определяется следующим образом:
(1.3.1)
где аi(к) содержимое i-того разряда регистра сдвига в к-м такте его
работы, а символ означает операцию суммирования по модулю два.
Содержимое первого разряда регистра сдвига в (k+s)-м такте работы име-
ет вид
(1.3.2)
для определения содержимого первого разряда регистра сдвига в
(k+1+s)-м такте, аналогично как и для (1.3.1) и (1.3.2), необходимо пред-
варительно выбрать численное значение коэффициентов . С
другой стороны, a1(k+1+s) можно найти на основании (1.3.1) следующим
образом:
где с учётом (1.3.1) принимает вид
значения вычисляются по формуле
,
где -постоянные коэффициенты, оп-
ределяемые как:
Окончательно для получаем:
Глава2.
Практическая реализация системы обучения методам компактного
тестирования.
2.1 Реализация графического интерфейса.
Программа написана под операционную систему Windows 95. Так
как сама операционная система Windows 95 является графической, то ин-
терфейсы программ написанных под эту систему похожи друг на друга.
Вследствие этого обучение работе с данной программой облегчается.
Графический интерфейс построен таким образом, чтобы пользователю
было, как можно удобнее и понятней работать с программой. Все необхо-
димые команды доступны через главное меню. Главное меню — это спе-
циальная панель инструментов, расположенная в верхней части экрана,
которая содержит такие меню, как: Файл, Редактировать, Полином,
Состояние, Диагностика, Анализ, Стоп. Через эти меню становятся
доступны основные функции программы. На главной форме
расположены кнопки логических элементов, генераторов, индикаторов.
Интерфейс программы состоит из трёх форм:
1. Главной формы, на которой расположены меню и все элементы
необходимые для работы цифровых схем.
2. Форма свойств элементов. Отображает свойства элемента при его
выделении.
3. Форма «Конструктор» - на ней строятся цифровые схемы.
2.2 Разработка и реализация алгоритма моделирова-
ния цифровых схем.
Разработанная система обучения может быть представлена в виде
системы, основными функциональными узлами которой являются
генераторы тестовых последовательностей, блок моделирования
исследуемых схем, блок отображения и обработки выходных реакций и
сжатия информации, блок ошибок, блок определения вероятностей не
обнаружения ошибок:
Моделирование сложных логических схем на большом числе вход-
ных наборов эффективно можно осуществлять только при помощи ЭВМ.
Для того чтобы смоделировать работу устройства на ЭВМ, необходимо
описать математическую модель этого устройства.
Для моделирования цифровых схем, прежде всего, необходимо опи-
сать схему, для этого была смоделирована математическая модель опи-
сывающая цифровые схемы под данную систему.
Каждый элемент схемы это объект, который имеет порядковый но-
мер на схеме, тип, списки входов и выходов. Каждый вход элемента хра-
нит информацию о предыдущем элементе. Вследствие этого каждый эле-
мент может определить логическое состояние предыдущего, его тип, по-
рядковый номер на схеме, выход с которым он соединён.
Линии, соединяющие входы и выходы элементов являются такими
же объектами, как и элементы цифровой схемы, за исключением того,
что линия имеет только один вход и один выход, и не выполняет
логических функций.
В программе реализованы все типы логических элементов, вследст-
вие этого можно построить большое количество разнообразных цифро-
вых схем.
Программа была написана при помощи объектно-ориентированного
языка Паскаль в среде Delphi 3.
Объектно-ориентированный язык программирования характеризует-
ся тремя основными свойствами:
? Инкапсуляция - это объединение записей с процедурами и функ-
циями, работающими с полями этих записей, которое формирует
новый тип данных - объект.
? Наследование - определение объекта и дальнейшее
использование всех его свойств для построения иерархии
порождённых объектов с возможностью для каждого
порождённого объекта, относящегося к иерархии, доступа к коду
и данным всех порождающих объектов.
? Полиморфизм - присваивание определённому действию одного
имени, которое затем совместно используется по всей иерархии
объектов сверху донизу, причём каждый объект иерархии выпол-
няет это действие характерным именно для него способом.
Каждый элемент на схеме, будь это линия, логический элемент, ге-
нератор или индикатор - это есть отдельный объект. Иерархия объектов
представляется в виде:
BassClass - базовый класс для всех элементов электрической схемы.
В нем задаются основные логические характеристики элементов схемы.
такие как, выходы элемента - ListOutLine, входы элемента - ListInLines, и
методы обработки списка линий. А также абстрактный метод Execute, в
котором и описываются все действия для моделирования работы логиче-
ского элемента.
TPaintLogicElem - этот класс является родительским для всех
логических элементов схем. Этот класс занимается прорисовкой,
перемещением, установкой параметров элементов.
TAnd - логический элемент "И". В процедуре Execute выполняет ло-
гическую функцию типа "И".
TAndNot - логический элемент "И-НЕ". В процедуре Execute выпол-
няет логическую функцию типа "И-НЕ".
TOr - логический элемент "ИЛИ". В процедуре Execute выполняет
логическую функцию типа "ИЛИ".
TOrNot - логический элемент "ИЛИ-НЕ". В процедуре Execute вы-
полняет логическую функцию типа "ИЛИ-НЕ".
TNOT - логический элемент "НЕ". В процедуре Execute выполняет
логическую функцию типа "НЕ".
TGenerator - генератор счетчиковой последовательности;
TMGenerator - генератор М-последовательности.
TIndicator - объект производит вычисление и отображение получен-
ной информации. В нём так же находится модуль вычисления сигнатуры,
подсчет количества единиц.
TLine - объект "Линия" соединяет входные и выходные линии эле-
ментов.
TPoint - объект "точка".
2.3 Реализация алгоритма, моделирующая работу генераторов тесто-
вых последовательностей.
Генератор счётчиковой последовательности.
На схеме генератор счётчиковой последовательности отображается
как:
Генератор М-последовательности
Алгоритмы работы генераторов счётчиковой последовательности
описан и М-последовательности описан в [1.3]
2.4 Разработка и реализация модуля моделирующего алго-
ритм диагностики с использованием компактных методов
тестирования.
Для диагностики цифровых схем особый интерес представляют сиг-
натурный анализ, в частности, многоканальный, в основе построения ко-
торого лежит алгоритм сжатия информации, и метод компактного тести-
рования, использующий алгоритм счета единиц, который находит широ-
кое применение при реализации встроенного тестирования. Поэтому для
обучающей системы при моделировании процесса диагностики
цифровых схем были выбраны два вышеуказанных метода компактного
тестирования.
Сигнатурный анализатор.
Для диагностики цифровых схем особый интерес представляют сиг-
натурный анализ, в частности, многоканальный, в основе построения ко-
торого лежит алгоритм сжатия информации, и метод компактного тести-
рования, использующий алгоритм счета единиц, который находит широ-
кое применение при реализации встроенного тестирования. Поэтому для
обучающей системы при моделировании процесса диагностики
цифровых схем были выбраны два вышеуказанных метода компактного
тестирования.
Для описания процедуры сжатия информации, основанной на приме-
нении сигнатурного анализа, используются различные математические
модели и алгоритмы. Наиболее широко используются два алгоритма:
1. Метод свёртки, при котором значение эталонной сигнатуры по-
следовательности, формируемой на любой из полюсов ЦС, в част-
ности и на выходном, получается при обработке её символов по
отношению 1.1.
2. Алгоритм деления полинома на полином. При этом в качестве де-
лимого используется поток сжимаемой последовательности дан-
ных, описываемых полиномом к(х) степени (l,1), где l-количество
бит в последовательности. Делителем служит примитивный поли-
ном , в результате деления на который получается частное
q(x) и остаток S(x), связанные классическим соотношением вида
где остаток S(x) называется сигнатурой.
Наиболее предпочтительным методом синтеза многоканальных сиг-
натурных анализаторов является метод, позволяющий синтезировать
МСА с произвольным количеством входов и не зависящим от него мно-
жеством элементов памяти, определяемым только старшей степенью по-
рождающего полинома . Данный метод основывается на применении
примитивного полинома , где m=deg оп-
ределяет достоверность анализа, а также разрядность формируемых сиг-
натур.
Для произвольного функционирование одноканального сигна-
турного описывается системой уравнений
(2.1)
где содержимое j-го элемента памяти анализатора в к-й
такт его работы; значение двоичного символа, поступающего
на вход анализатора в к-й такт; коэффициенты, зависящие от
вида порождающего полинома .
Из выражения (2.1) следует, что содержимое первого элемента памя-
ти анализатора в (к+1)-й такт его работы определяется как
а в (к+2) –й такт
В общем случае для некоторого k+n-1-го такта можно записать
(2.2)
где - коэффициенты, позволяющие формировать
сдвинутую на n тактов копию М-последовательности, описываемую по-
линомом . Значение определяются как:
Кроме того, численные значения могут быть получены в
результате выполнения быстрых формальных процедур.
Коэффициенты определяются следующим образом:
.
Из выражения (2.2) для можно получить его значение на
основании n символов y(k),y(k+1),…y(k+n-1) последовательности {y(k)}
и m исходных значений В тоже время указанное
выражение используется для построения функциональной схемы
сигнатурного анализатора, который в каждый такт обрабатывает n
символов последовательности {y(k)}. При этом подобный анализатор
будет иметь n входов, что позволяет применять его для контроля
цифровых схем, имеющих n выходов, причём n выходных
последовательностей в этом случае преобразуются в одну вида:
(2.3)
где значение двоичного символа на v-ом выходе
исследуемой цифровой схемы в к-й такт её работы.
Функционирование анализатора, обрабатывающего последователь-
ность (2.3) в соответствии с (2.1) и (2.2),будет описываться следующей
системой уравнений:
(2.4)
Использую систему уравнений (2.4), оказывается возможным по-
строение многоканального анализатора, выполняющего за один такт те
же преобразования с последовательностью, что и одноканальный за n
тактов.
Синдромное тестирование или метод счёта единиц.
Синдромом (контрольной суммой) некоторой булевой функции n
переменных является соотношение
S=R/2n,
Где R вычисляется по выражению
R=
Для l=2n и равно числу единичных значений функции согласно таб-
лице истинности. Определение понятия синдрома однозначно предпола-
гает использование генератора счётчиковых последовательностей двоич-
ных комбинаций из n входных переменных при тестировании схемы, реа-
лизующей заданную функцию.
2.5 Блок поиска неисправностей.
С помощью многоканальных сигнатурных анализаторов можно су-
щественно ускорить процедуру контроля цифровых схем, которая увели-
чивается в n раз, где n-количество входов применяемого анализатора. В
случае совпадения реально полученной сигнатуры с её эталонным значе-
нием считается, что с достаточно высокой вероятностью проверяемая
схема находится в исправном состоянии. На этом процедура её исследо-
вания оканчивается. В противном случае, когда схема содержит неис-
правности, реальная сигнатура, как правило, отличается от эталонной,
что служит основным аргументом для принятия гипотезы о неисправном
состоянии схемы. В то же время вид полученной сигнатуры не несёт
никакой дополнительной информации о характере возникшей
неисправности. Более того остаётся открытым вопрос о том, какие из n
анализируемых последовательностей, инициирующих реальную
сигнатуру, содержат ошибки, т.е. возникает задача локализации
неисправности с точностью до последовательности, несущей
информацию о её присутствии.
Суммарная сигнатура S(x), полученная для последовательности
{yv(k)},v=1,n,k=1,l, на n-канальном сигнатурном анализаторе, равна по-
разрядной сумме по модулю два сигнатур Sv(x), v=1,n. Причём каждая
сигнатура Sj(x), j?{1,2,3,…n}, формируется для последовательности
{yj(k)} при условии, что {yq(k)}=0000…00, q?j?{1,2,…,n}.
Алгоритм контроля цифровой схемы с локализацией неисправности
до первой последовательности, содержащей вызванные ею ошибки.
1. В результате анализа n=2d реальных последовательностей
{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. Все множество входных последовательностей разбивается на две
группы, причём номера последовательностей {y1(k)}, {y2(k)},
{y3(k)},…., {yn/2(k)} составляют множество А2={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.
5. В результате анализа реальных последовательностей, номера ко-
торых задаются множеством А1, на n-канальном анализаторе при
условии, что последовательности, номера которых не
определены множеством А1, являются нулевыми, определяется
значение реальной сигнатуры S*(x).
6. На основании выражения получаем S(x).
7. Проверяется справедливость равенства S(x)=S*(x). В случае его
выполнения элементы множества А1 заменяются элементами
множества А2.
8. Значение переменной i увеличивается на единицу. Затем его ве-
личина сравнивается с величиной d. При i?d переходят к сле-
дующему пункту алгоритма, в противном случае выполняется
пункт 10.
9. По текущим значениям множества А1 формируются новые мно-
жества А1 и А2. Новыми элементами множества А1 будет первая
половина его текущих элементов, вторая половина
присваивается множеству А2. После определения множеств А1 и
А2 переходят к выполнению п. 5.
10. Единственный элемент множества А1представляет собой номер
ошибочной последовательности, формируемой на одном из по-
люсов исследуемой схемы.
11. Процедура контроля цифровой схемы считается оконченной.
2.6 Определение оценки эффективности методов сигна-
турного анализатора и счёта единиц.
Достоверность сигнатурного анализа.
Полнота не обнаружения неисправностей цифровой схемы в первую
очередь зависит от качества тестовых воздействий. Если определённая
неисправность не проявляется в виде искажения их символов, то она не
может быть обнаружена в результате применения сигнатурного анализа,
который является не более чем эффективным методом сжатия потока
данных. Поэтому если этот поток не несёт информации о неисправности,
то она и не появится после его сжатия.
Таким образом, под достоверностью сигнатурного анализа будем по-
нимать его эффективность обнаружения ошибки в потоке сжимаемых
данных. Для оценки этой характеристики сигнатурного анализа могут ис-
пользоваться разные подходы и методы. Наиболее широко применяемым
является вероятностный подход, сущность которого заключается в опре-
делении вероятности Рn не обнаружения ошибок в анализируемой после-
довательности данных. Причём в рассматриваемом случае оценивается
вероятность, зависящая только от метода сжатия, и не учитываются дру-
гие факторы.
Величина Рn рассчитывается для достаточно общего случая, прибли-
жённо соответствующего реальным примерам. Предполагается, что эта-
лонная последовательность данных может равновероятно принимать раз-
ное значение, а любая конфигурация ошибочных бит может быть равно-
вероятным событием. Далее, использую алгоритм деления полиномов как
математический аппарат формирования сигнатуры, показываем, что для
l-разрядного делимого вычисляются l-m-разрядное частное и m-
разрядный остаток (сигнатура). При этом соответствие реальной
последовательности, состоящей из l бит, эталонной оценивается только
по равенству их m - разрядных сигнатур. Для 2l-m различных частных
будет формироваться одинаковая сигнатура. Это свидетельствует о том,
что 2l-m-1 ошибочных l-разрядных последовательностей будут считаться
соответствующими одной - эталонной. Учитывая равно вероятность
ошибочных последовательностей данных, можно заключить, что 2l-m-1
ошибочных последовательностей, инициирующих эталонную сигнатуру,
не обнаруживаемы. Таким образом, вероятность Рn необнаружения
ошибок в анализируемой последовательности данных будет вычисляться
как отношение:
(2.6.1)
где 2l-1 равняется общему числу ошибочных последовательностей.
Выражение (2.6.1) для условия l>>m преобразуется к более простому
виду:
которое может служить основным аргументом для обоснования вы-
сокой эффективности сигнатурного анализа.
В качестве более точной меры оценки достоинств сигнатурного ана-
лизатора рассмотрим распределение вероятности необнаружения ошибки
в зависимости от её кратности ?, т.е. определим значение где
?=1,2,3,...2m-1.
Можно показать, что не обнаруживаемых ошибок определяется
следующим образом:
а количество возможных ошибок из ? бит определяется как
И тогда выражение для вероятности не обнаружения ошибки прини-
мает вид:
,
Анализ показывает, что для достаточно больших m
, т.е. при m>7 вероятность обнаружения ошибки
практически равняется единице.
Достоверность метода счёта единиц.
В качестве характеристики, позволяющей оценить метод компактно-
го тестирования целесообразно использовать распределение
вероятностей не обнаружения ошибки в зависимости от её кратности ?:
где ? -кратность ошибки, - вероятность возникновения ошибки
кратности ?; - вероятность не обнаружения возникшей ошибки
кратности ?, которая определяется как отношение количества не
обнаруживаемых ошибок кратности ? к общему количеству возможных
ошибок из ? неверных символов в последовательности длиной l.
Значение определяется видом проверяемой цифровой схемы,
множеством возможных её неисправностей, а также типом тестовых по-
следовательностей, причём распределение вероятностей может иметь
совершенно произвольный вид и значительно изменяться в зависимости
от возникшей неисправности, вида схемы и тестовой последовательно-
сти.
Значение характеризуется только методом компактного тестиро-
вания и позволяет провести его сопоставительную оценку в сравнении с
другими методами. Поэтому для различных методов в зависимости от их
распределения вероятностей могут быть получены оценки эффектив-
ности контроля ЦС в виде распределения . Анализ этого вида распре-
деления позволяет принять решение о целесообразности применения то-
го или иного метода компактного тестирования. Причём для упрощения
алгоритма принятия решения следует использовать более компактную ха-
рактеристику, например суммарную вероятность не обнаружения ошибки
, вычисляемую как
В данном случае величина будет характеризовать тот или иной
метод компактного тестирования для вполне конкретного распределения
вероятностей возникновения неисправностей в зависимости от её
кратности.
Глава 3.
Описание программы.
Интерфейс программы состоит из трёх окон:
? Главного - на котором находятся все основные функции програм-
мы, элементы цифровой схемы.
? Окна свойств, в котором отображается информация об элементе
? Окно "Конструктор" - в нём строится сама цифровая схема.
Для построения цифровой схемы, необходимо поочерёдно нажимая
в панели инструментов, на главной форме, на нужный элемент и нажимая
на форму конструктора создавать элементы, из которых будет состоять
цифровая схема. Элементы можно создавать и размещать в любом поряд-
ке, а также добавлять и удалять в уже созданной ЦС.
Чтобы соединить входы и выходы элементов линией, необходимо:
? При наведении курсора мыши на входную ножку элемента, ножка
выделяется и нажимая левую кнопку тянем до выходной ножки
другого элемента. Как только выходная ножка которую мы хотим
соединить также выделится отпускаем кнопку мыши. В
результате будет создана линии, соединяющая входную и
выходную ножки.
Также соединяется линией точка с входными и выходными ножками
элементов.
Для просмотра свойств элементов, достаточно выделить элемент и
свойства элемента отобразятся в окне свойств.
В этом окне можно изменять число входов или число выходов, вво-
дить ошибки. В нём также отображается тип элемента и порядковый но-
мер на схеме.
Если в схеме используется генератор М-последовательности, то для
него необходимо ввести примитивный неприводимый полином. Для это-
го в меню выбираем раздел Полином -->М-генератор и в появившемся
окне составляем полином.
Для сигнатурного анализатора, также необходимо составить поли-
ном. Из того же пункта меню Полином выбираем Сигнатурный анали-
затор.
Когда схема будет создана, нажимаем на Анализ. В появившемся
окне отображается сигнатура, число единиц, вероятности появления еди-
ниц и нулей.
Экспериментальная часть.
В качестве примера рассмотрим схему мультиплексора и получим
сигнатуру.
В качестве тестового генератора будем использовать генератор М-
последовательности и полином вида:
Для сигнатурного анализатора выберем полином также седьмой сте-
пени.
В результате моделирования, получим:
на входе:
на выходе
Сигнатура и число единиц:
Далее, вводим ошибки в схему через окно "Свойства элементов", ко-
торое находится в левой части экрана.
Затем из меню Диагностика выбираем "Поиск неисправностей"
В результате мы локализовали неисправные элементы и типы оши-
бок.
2
42