Лекция 15 построение зависимости длины случайного теста icon

Лекция 15 построение зависимости длины случайного теста




Скачати 82.66 Kb.
НазваЛекция 15 построение зависимости длины случайного теста
Дата01.07.2012
Розмір82.66 Kb.
ТипЛекция
1. /lec1 Надежность вычислительных устройств.doc
2. /lec10 Подходы построения производственных тестов комбинационных схем.doc
3. /lec11 Случайное тестирование ВУ.doc
4. /lec12 Проектирование генераторов псевдослучайных тестов.doc
5. /lec13 Элементы вероятностной логики.doc
6. /lec14 Показатели неисправности при случайном тестировании.doc
7. /lec15 Построение зависимости длины случайного теста от вероятности обнаружения неисправностей.doc
8. /lec16 Оптимизация случайного теста ВУ.doc
9. /lec2 Дефекты элементов вычислительной техники.doc
10. /lec3 Структурные методы синтеза тестов комбинационных схем.doc
11. /lec4 Показатели тестируемости неисправностей.doc
12. /lec5 Булева производная и ее применение для вычисления наблюдаемости.doc
13. /lec6 Наблюдаемость и активизация путей схемы.doc
14. /lec7 Эквивалентность доминирование и совмещение КН.doc
15. /lec8 Синтез тестов КН комбинационных схем по методу булевой производной.doc
16. /lec9 Машинно-ориентированный синтез тестов комбинационных схем по D-алгоритму.doc
Лекция 1 надежность вычислительных устройств двумя важнейшими техническими категориями изделия вообще и вычислительного устройства, в частности, являются качество и надежность. Качеств о
Комбинационных схем
Тестирование ву на случайных тестовых воздействиях называется случайным
Проектирование генераторов псевдослучайных тестов
Аксиомы теории вероятностей
Лекция 15 построение зависимости длины случайного теста
Дефекты элементов вычислительной техники
Структурные методы синтеза тестов комбинационных схем
Лекция 4 показатели тестируемости неисправностей
Лекция 5 Булева производная и ее применение для вычисления наблюдаемости Определение бпx
Лекция 6 Hаблюдаемость и активизация путей схемы Наблюдаемость кт теснейшим образом связана с понятием схемного пути. Схемный путь
Синтез тестов кн комбинационных схем по методу булевой производной
Машинно-ориентированный синтез тестов

Л е к ц и я 15


ПОСТРОЕНИЕ ЗАВИСИМОСТИ ДЛИНЫ СЛУЧАЙНОГО ТЕСТА

ОТ ВЕРОЯТНОСТИ ОБНАРУЖЕНИЯ НЕИСПРАВНОСТЕЙ


Основной задачей при детерминированном тестировании, как является синтез теста минимальной длины. Среди же основных же задач случайного (псевдослучайного) тестирования можно выделить следующие:


  • расчет длины N СТ либо ПСТ по заданной вероятности обнаружения (Qзад) неисправностей ОД;

  • расчет вероятности обнаружения Q неисправностей ОД по заданной длине (Nзад) СТ либо ПСТ;

  • построение зависимости N(Q) длины N СТ либо ПСТ от вероятности обнаружения Q неисправностей ОД.


Последняя задача исключает необходимость в отдельном решении первой и второй, так как если построена зависимость N(Q), которая может быть выражена в аналитической, табличной либо в графической формах, то на ее основе всегда по Qзад можно рассчитать

N(Qзад), либо по Nзад - определить Q(Nзад).


Таким образом основной задачей случайного (псевдослучайного) тестирования является построение зависимости длины N ПСТ от вероятности Q обнаружения КН ОД.

Обычно зависимость N(Q) может строиться для одной неисправности либо для ОД в целом. Рассмотрим как решаются указанные задачи.


Построение зависимости N(Q) для одной неисправности



Пусть q(hк) - тестируемость (вероятность тестируемости) неисправности hк, которая означает вероятность обнаружения этой неисправности при подаче на входы ОД одного случайного тестового вектора. Тогда 1 - q(hк) есть вероятность необнаружения неисправности hк при подаче на входы ОД одного случайного тестового вектора.

Вероятность необнаружения hк при подаче на входы ОД двух независимых случайных векторов составит


[ 1 - q(hк) ] 2 .


После воздействия на ОД N случайных независимых векторов вероятность необнаружения hк составит


[ 1 - q(hк) ] N ,


а вероятность обнаружения неисправности


1 - [ 1 - q(hк) ] N .


Обозначим последнюю формулу через Q:


Q = 1 - [ 1 - q(hк) ] N . (*)


Формула (*) по известной длине случайного теста позволяет вычислять вероятность обнаружения неисправности, т.е. решается задача типа 1:


Q(Nзад) = 1 - [ 1 - q(hк) ] N зад . (**)


Для решения же задачи типа 2 необходимо наоборот N выразить через конкретное заданное значение вероятности обнаружения неисправности - Qзад. Логарифмируя выражение (*) получаем


(***)


где q - вероятность тестируемости неисправности ;

log - логарифм по произвольному основанию.


Третью задачу лучше всего решать, задаваясь различными значениями Q и вычисляя для них значения N по приведенной логарифмической формуле:


(****)


Такую зависимость можно выразить таблично либо графически. Например, зависимость N(Q) для КН 26=0 одноразрядного сумматора, тестируемость которой равна q = 0.125, построим задавая Q = 0.5, 0.25, 0.75, 0.9, 0.99, 0.999 и подставляя эти данные в формулу (****) - получим соответствующие значения длины теста. Результаты снесем в таблицу следующего вида ты снесем в таблицу следующего вида


N(Q) q = 0.125

───────┬──────┬─────┬──────┬─────┬──────┬──────┬──────┐

Q │ 0.25 │ 0.5 │ 0.75 │ 0.9 │ 0.95 │ 0.99 │ 0.999│

───────┼──────┼─────┼──────┼─────┼──────┼──────┼──────┤

N │ 2 │ 5 │ 10 │ 17 │ 22 │ 34 │ 51 │

───────┴──────┴─────┴──────┴─────┴──────┴──────┴──────┘


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

Построение зависимости N(Q) для ОД в целом




Зависимость N(Q) для ОД в целом также строится по логарифмической формуле:


(****)


где q - некоторый параметр ОД, вычисляемый в зависимости от выбранного способа построения зависимости.


В настоящее время наибольшую известность получили следующие основные способы построения зависимости N(Q):


  • способ "наихудшей комбинации" ;

  • способ "среднестатистической неисправности" ;

  • способ "наихудшей неисправности" .


Способ " н а и х у д ш е й к о м б и н а ц и и" базируется на вычислении параметра q по входному вектору, значения которого определяется по минимальным вероятностям входных сигналов:


n

q = qком = П Pimin ,

i=1


Pi, если Pi <= 0.5 ;

где Pimin =

1 - Pi, если Pi > 0.5 .


Зависимость N(Q) вычисляется по формуле





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


Способ " с р е д н е с т а т и с т и ч е с к о й н е и с п р а в н о с т и " предполагает вычисление параметра q как среднеарифметическое тестируемости всех неисправностей ОД:





где q(hк) - тестируемость неисправности hк ;

Hп - полный список неисправностей ОД ;

| Hп | - число неисправностей списка Hп .


Неисправность hср с тестируемостью qср называется среднестатистической - отсюда название способа.

Достоинством описанного способа является максимально точное отображение реальной зависимости N(Q). Однако способ является только гипотетическим, так как к настоящему времени не известны практические способы косвенного определения qср.

Наибольшее применение на практике нашел способ " н а и х у д ш е й н е и с п р а в н о с т и ".

Неисправность hт с минимальной вероятностью тестируемости qт называется наихудшей.

Пусть имеется полный список неисправностей ОД


Hп = { h1, ... , hк, ... , hf } .


Списку Hп поставим в соответствие список вероятностей тестируемости неисправностей:


Qп = { q1, ... , qк, ... , qf } ,


так что неисправности hк соответствует тестируемость qк . Тогда


qт = min { qк } .

к


Практическое значение нашли два способа определения наихудшей КН:


  • машинный (STAFAN) ;

  • машиннo-аналитический (МАС) .


М а ш и н н ы й способ базируется на вычислении тестируемости КН по методу STAFAN. В качестве наихудшей неисправности выбирается та, схема тестируемости которой генерирует наименьшую частоту - число лог."1". Тестируемость qт этой неисправности определяется как отношение частоты к длине моделируемого теста.

Недостатком машинного способа является сложность моделируемой схемы (ОД плюс схемы тестируемости для каждой КН) и большое время моделирования.

Оптимальным способом определения наихудшей КН и построения по ней зависимости N(Q) является машинно-аналитический способ.


Машинно-аналитический способ (МАС) построения зависимости N(Q)


МАС можно представить следующей последовательностью этапов.


1. Определение вероятностей сигналов КТ ОД машинно-аналитическим способом.

2. Поиск "труднотестируемых" КН ВУ по алгоритму "dQ" и построение минимального списка неисправностей Hmin = {q(hk)}, подозреваемых на наихудшую.

3. Определение вероятности тестируемости труднотестируемых КН машинным способом по методу STAFAN.

4. Выбор наихудшей КН из труднотестируемых и определение qт как минимальной вероятности тестируемости одной из труднотестируемых КН:


qт = qmin = min { q(hk) } .

k


5. Построение зависимости N(Q) по формуле





где log - логарифм по произвольному основанию.


Поиск труднотестируемых КН суммирующих схем будем производится по так называемому алгоритму "dQ", который можно представить следующим образом.


1. Определение вероятностей сигналов.


На базе вероятностей сигналов входных последовательностей {Pxi} определяются вероятности сигналов на выходах логических элементов - {Pyj}:


{Pxi} ? {Pyj}


2. Ранжирование элементов схемы.


Входам схемы присваивается нулевой ранг - R0. ЛЭ Vj присваивается ранг r, если максимальный ранг ЛЭ, подключенных выходом ко входу элемента Vj, составляет r-1.


3. Инициализация.


Hтmin = 0, r=1, все ЛЭ объявляются "непомеченными".


4. Определение hт ЛЭ типа И, И-НЕ ранга r.


Для каждого ЛЭ типа И, И-НЕ ранга r, кроме инвертора, находится вход Хmax с максимальной вероятностью сигнала Рmax.

Если Pmax > 0.5 и вход Xmax принадлежит многополюсной линии связи (ЛСn), либо вход подключен к непомеченному ЛЭ, то неисправность Xmax=1 заносится в список Hтmin.


5. Определение hт ЛЭ типа ИЛИ, ИЛИ-НЕ ранга r.


Для каждого ЛЭ типа ИЛИ, ИЛИ-НЕ ранга r, кроме инвертора, среди всех входов, принадлежащих двухполюсным линиям связи (ЛС2) находится вход Хmin с минимальной вероятностью сигнала Рmin. Если Pmin < 0.5 и вход Xmin, если таковой будет найден, под

ключен к непомеченному ЛЭ, то в Hтmin заносится неисправность Xmin=0. Xmin=0.


6. Инкремент ранга.


Если r < max , то r=r+1 и производится переход на п.4 алгоритма. ритма.


7. Удаление связывающих неисправностей.


Из списка Нтmin, полученном после выполнения пп 1-6 алгоритма, удаляются все "связывающие" КН, вероятность управляемости которых выше вероятности управляемости соответствующих им "связанных" неисправностей.


8. Конец.


КН h1 и h2 называются "связанными" ( h1·h2 ), если существует одномерный схемный путь, одновременно проходящий через обе неисправности. Если путь проходит в направлении от h1 к h2, то h1 называется "связывающей", а h2 - "связанной".


В качестве примера построим зависимость N(Q) для одноразрядного сумматора.


0.5 ┌───┐ 0.25 E1 ┌───┐ 0.125

e1────*────┤ & │10=0 ┌─────────*────┤ & │26=0

│ │ ├y1┐ │ │ │ ^ ├─f1─┐

a1────┼*───┤ │ │ │ a1────*─┼────┤V15│ │

││ └───┘ │ ┌───┐ │ │ │ └───┘ │ ┌───┐

││ ┌───┐ └──┤ 1 │ │ │ │ ┌───┐ └───┤ 1 │

│└───┤ & │11=0 │ │ │ │ *────┤ & │27=0 │ │ __

│ │ ├y2───┤ ^ о───┘ │ │ │ ^ ├─f2─────┤ ^ о────> S1

│┌───┤ │ │ │ b1────┼*┼────┤V16│ │ │

││ └───┘ ┌──┤V14│ │││ └───┘ ┌───┤ │

││ ┌───┐ │ └───┘ │││ ┌───┐ │ │ │

b1────┼*───┤ & │12=0 ││└────┤ & │28=0│┌──┤V19│

│ │ ├y3┘ ││ │ ^ ├─f3─┘│ └───┘

└────┤ │ e1────┼┼*────┤V17│ │

└───┘ │││ └───┘ │

│││ ┌───┐ │

││└────┤ & │29=0 │

│└─────┤ ├─f4──┘

└──────┤V18│

└───┘


Рисунок - Oдноразрядный сумматор с труднотестируемыми КН


Помеченные ЛЭ с зависимыми входами и соответствующие им КТ отражены на рисунке. Здесь же показаны вероятности сигналов в помеченных КТ, полученные путем моделирования в подсистеме моделирования вероятностей сигналов (ПМВС) и вероятности сигналов в непомеченных КТ, рассчитанные аналитически по алгоритму "Э2". Труднотестируемые КН СМП, построенные по алгоритму "dQ", показаны на схеме. Результаты моделирования в подсистеме моделирования вероятностей тестируемости труднотестируемых КН (ПМВТ) показали, что наихудшей КН являются 26=0 с вероятностью тестируемости qt = 0.125.


В о п р о с ы д л я с а м о к о н т р о л я :


1. Приведите постановку задач при случайном тестировании. Перечислите объекты, подлежащие расчету.

2. Приведите обоснование формулы построения зависимости длины N случайного теста от вероятности обнаружения неисправностей Q.

3. Как определить длину случайного теста КН по заданной вероятности ее обнаружения?

4. Как определить вероятности обнаружения КН случайным тестом заданной длины ?

5. Перечислите способы построения зависимости N(Q) для объекта диагностики в целом.

6. Поясните термины "наихудшая комбинация", "наихудшая неисправность", "среднестатистическая неисправность".

7. Как определяется "наихудшая неисправность" ?

8. Перечислите этапы машинно-аналитического способа построения зависимости N(Q).

9. Дайте сравнительную характеристику способов построения зависимости N(Q).

Схожі:

Лекция 15 построение зависимости длины случайного теста iconДокументи
1. /XML-Лекция 1. концепция Семантического Веб.doc
2. /XML-Лекция...

Лекция 15 построение зависимости длины случайного теста iconДокументи
1. /Лекция 1. Основы РС.docx
2. /Лекция...

Лекция 15 построение зависимости длины случайного теста iconЛекция № Библиографическое описание документа. Рассмотрим, какие виды библиографических описаний документов в зависимости от объекта библиографического описания бывают. Различают
Монографическое описание содержит сведения, характеризующие однотомное издание в целом, а также отдельные тома многотомного или сериального...
Лекция 15 построение зависимости длины случайного теста iconОтветы на вопросы теста по предмету «Системы технологий в менеджменте»

Лекция 15 построение зависимости длины случайного теста iconПрактическая работа № Тема: Интервальная переменная. Табулирование функции и построение её графика в системе
Тема: Интервальная переменная. Табулирование функции и построение её графика в системе MathCad. Форматирование графиков
Лекция 15 построение зависимости длины случайного теста iconПеречень публикаций кафедры аикит за 2008год
Анализ экспериментальных исследований на устойчивость оболочных металлокконструкций ограниченной длины
Лекция 15 построение зависимости длины случайного теста iconПерелік публікацій кафедри екології за 2008 рік
Анализ экспериментальных исследований на устойчивость оболочечных металлоконструкций ограниченной длины
Лекция 15 построение зависимости длины случайного теста iconСписок используемых источников т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн Алгоритмы: построение и анализ. М.: Вильямс, 2005. 1296
Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн Алгоритмы: построение и анализ. М.: Вильямс, 2005. 1296 с
Лекция 15 построение зависимости длины случайного теста iconОсновные стратегии организационных изменений ситуация Примеры процесса изменения в зависимости от скорости и сложности изменения
Ситуация Примеры процесса изменения в зависимости от скорости и сложности изменения
Лекция 15 построение зависимости длины случайного теста icon2. 11. Способы реализации случайного механизма выбора стратегий
Для реализации применения игроком его активных стратегий с оптимальными вероятностями (относительными частотами), необходимо иметь...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи