Xreferat.com » Рефераты по информатике » Методы компактной диагностики

Методы компактной диагностики

схему, для
этого была смоделирована математическая модель описывающая цифровые схемы под
данную систему.
Каждый элемент схемы это объект, который имеет порядковый номер на схеме, тип,
списки входов и выходов. Каждый вход элемента хранит информацию о предыдущем
элементе. Вследствие этого каждый элемент может определить логическое состояние
предыдущего, его тип, порядковый номер на схеме, выход с которым он соединён.
Линии, соединяющие входы и выходы элементов являются такими же объектами, как и
элементы цифровой схемы, за исключением того, что линия имеет только один вход и
один выход, и не выполняет логических функций.
В программе реализованы все типы логических элементов, вследствие этого можно
построить большое количество разнообразных цифровых схем.
Программа была написана при помощи объектно-ориентированного языка Паскаль в
среде 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.
Алгоритм деления полинома на полином. При этом в качестве делимого используется
поток сжимаемой последовательности данных, описываемых полиномом к(х) степени
(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}.
Алгоритм контроля цифровой схемы с локализацией неисправности до первой
последовательности, содержащей вызванные ею ошибки.
В результате анализа n=2d реальных последовательностей {y*(k)},v=1,nб на
n-канальном анализаторе определяется значение сигнатуры S*(x), которое
соответствует соотношению:
.
По выражениювычисляется эталонное значение сигнатуры S(x).
Реальное значение сигнатуры S*(x) сравнивается с эталонной сигнатурой S(x). В
случае выполнения равенства S*(x)=S(x) переходят к выполнению п.11 и процедура
контроля считается оконченной. В противном случае, когда S*(x)¹S(x), выполняется
следующий этап алгоритма.
Все множество входных последовательностей разбивается на две группы, причём
номера последовательностей {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.
В результате анализа реальных последовательностей, номера которых задаются
множеством А1, на n-канальном анализаторе при условии, что последовательности,
номера которых не определены множеством А1, являются нулевыми, определяется
значение реальной сигнатуры S*(x).
На основании выраженияполучаем S(x).
Проверяется справедливость равенства S(x)=S*(x). В случае его выполнения
элементы множества А1 заменяются элементами множества А2.
Значение переменной i увеличивается на единицу. Затем его величина сравнивается
с величиной d. При i£d переходят к следующему пункту алгоритма, в противном
случае выполняется пункт 10.
По текущим значениям множества А1 формируются новые множества А1 и А2. Новыми
элементами множества А1 будет первая половина его текущих элементов, вторая
половина присваивается множеству А2. После определения множеств А1 и А2
переходят к выполнению п. 5.
Единственный элемент множества А1представляет собой номер ошибочной
последовательности, формируемой на одном из полюсов исследуемой схемы.
Процедура контроля цифровой схемы считается оконченной.
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 преобразуется к более простому виду:

которое может служить основным аргументом для обоснования высокой эффективности
сигнатурного анализа.
В качестве более точной меры оценки достоинств сигнатурного анализатора
рассмотрим распределение вероятности необнаружения ошибки в зависимости от её
кратности m, т.е. определим значениегде m=1,2,3,...2m-1.
Можно показать, что не обнаруживаемых ошибок определяется следующим образом:

а количество возможных ошибок из m бит определяется как
И тогда выражение для вероятности не обнаружения ошибки принимает вид:
,

Анализ показывает, что для достаточно больших m , т.е. при m>7 вероятность
обнаружения ошибки практически равняется единице.
Достоверность метода счёта единиц.
В качестве характеристики, позволяющей оценить метод компактного тестирования
целесообразно использовать распределение вероятностей не обнаружения ошибки в
зависимости от её кратности m:

где m -кратность ошибки, - вероятность возникновения ошибки кратности m; -
вероятность не обнаружения возникшей ошибки кратности m, которая определяется
как отношение количества не обнаруживаемых ошибок кратности m к общему
количеству возможных ошибок из m неверных символов в последовательности длиной
l.
Значениеопределяется видом проверяемой цифровой схемы, множеством возможных её
неисправностей, а также типом тестовых последовательностей, причём распределение
вероятностейможет
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: