Д Е Иванов - Генетический алгоритм построения диагностических последовательностей цифровых устройств - страница 1

Страницы:
1  2 

УДК 681.518

Иванов Д.Е.

ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ ДИАГНОСТИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЦИФРОВЫХ УСТРОЙСТВ

В статье предлагается новый подход к построению диагностических (локализую­щих неисправность) последовательностей. Данный подход является двухуровне­вым. На верхнем уровне из всех текущих множеств неразличимых неисправностей происходит выбор одного целевого множества. На нижнем уровне с помощью гене­тического алгоритма для выбранного множества строится диагностическая после­довательность. Благодаря такой структуре алгоритм позволяет разработчику нахо­дить компромисс между затрачиваемым временем и точностью работы

1. Введение.

Наиболее сложными и трудоёмкими при разработке систем автоматизиро­ванного диагностирования являются задачи построения тестов. Чаще всего при по­строении тестов говорят о проверяющих тестах, которые позволяют проверить исправ­ность испытываемого дискретного устройства (ДУ). Задача в этом случае сводится к проверке отличимости некоторого исправного ДУ от неисправного.

Гораздо реже исследуется задача построения диагностических тестов, кото­рые позволяют дополнительно локализовать неисправность. Это связано с тем, что задача являет существенно более сложной. Фактически она заключается в разбиении всего класса исследуемых неисправностей на группы неразличимых неисправностей [1].

Наиболее часто при решении задачи диагностирования используется метод словарей неисправностей. Он заключается в подаче тестовой последовательности на входы схемы, наблюдении её выходов и сравнении полученных значений со значения­ми, которые сохранены в словаре [1]. Ряд работ посвящён построению таких входных последовательностей [2], поскольку именно они существенно влияют на эффектив­ность данного подхода. Описанный в [2] подход является детерминированным, т.е. гарантирует построение диагностической последовательности, если она существует. Однако недостатком таких методов является их ограниченная применимость к схемам большой размерности, что связано либо с невозможностью построения полного дерева решений, либо с невозможностью его обхода за приемлемое время.

Преодолеть ограничения структурных детерминированных методов помогли генетические алгоритмы (ГА) [3-4]. Фактически, при их построении происходит заме­на задачи синтеза задачей анализа: для оценки качества текущих последовательностей и продуцирования новых используются результаты моделирования. Генетические ал­горитмы обладают наилучшими глобальными поисковыми свойствами и позволяют находить субоптимальные решения за приемлемое время. При этом они относятся к классу недетерминированных алгоритмов в том смысле, что не гарантируют нахожде­ние именно оптимального решения.

Авторы также использовали генетические алгоритмы при решении задач технической диагностики. В частности, были предложены эффективные алгоритмы построения тестов [5], инициализирующих последовательностей [6] и последователь­ностей верификации эквивалентности [7].

В данной статье, основываясь на предыдущем опыте, авторы предлагают но­вый алгоритм построения диагностических последовательностей цифровых устройств. Его отличительными чертами являются двухуровневая организация и использование ГА на нижнем уровне для построения диагностической последовательности для неко­торого класса неразличимых неисправностей.

Данная статья имеет следующую структуру. Во введении показана актуаль­ность и связь с другими работами в этом направлении. Во втором разделе дана поста­комбинационный

Рис.1. Модель синхронной последо-вательностной схемы.

новка задачи и необходимые определения. В третьем разделе описывается двухуровне­вая структура алгоритма построения диагностических последовательностей. Четвёр­тый раздел посвящён описанию генетического алгоритма построения диагностической последовательности для выбранного класса неисправностей. В заключении делаются выводы и указываются направления дальнейших исследований.

2. Задача построения диагно­стических последовательностей.

В качестве модели ДУ мы будем использовать синхронные последовательно-стные схемы (рис.1). В данной модели вы­деляют комбинационные блоки и блоки элементов состояний, которые представле­ны D-триггерами. Комбинационные блоки представляют собой в общем случае сеть, вершинами которой являются логические элементы, внешние входы и выходы.

В качестве модели неисправности мы используем одиночные константные не­исправности. Отметим, что в приведённом

виде и без потери общности алгоритм может быть применён к другим распространён­ным типам неисправностей. От описанного в данной статье новый алгоритм будет от­личаться лишь процедурами диагностического моделирования.

Определение 1. Пусть задана исправная цифровая схема A0 и класс неис­правностей F = {f1v.., fn }, который соответственно порождает класс неисправных уст­ройств A = {A1,...,An} . Входная последовательность T, которая может отличить пове­дение произвольного устройства A от поведения исправного A0, а также поведения всех остальных неисправных устройств, называется диагностической.

Видно, что в такой постановке задача является более сложной в сравнении с задачей построения проверяющих тестов, в которой достаточно было отличить пове­дение неисправного устройства A от исправного A0. Фактически, диагностическая последовательность позволяет разбить весь класс неисправностей на классы эквива­лентных неисправностей, мощностью каждого из которых равна 1 [8-9]. Такую поста­новку задачи также часто называют локализацией неисправностей, подчёркивая тот момент, что выделение неисправности в отдельный класс неотличимости точно указы­вает на место (линию в схеме) возникновения неисправности.

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

задачи.

Определение 2. Для заданной схемы A и двух неисправностей f1 и /2 по­следовательность T называется различающей, если выходные реакции A1(T) и A2(T) различны хотя бы для одного входного вектора.

Определение 3. Все неисправности fj,..., fn, которые не различаются задан­ной входной последовательностью T для заданной схемы A , принадлежат к одному классу неразличимости относительно последовательности T .

Определение 4. Для заданной схемы A и заданного класса неисправностей F = { f1,... , fn} последовательность T называется различающей, если существует хотя

бы одна неисправность fj є F такая, что Aj(T) Ф At (T) (для i = 1, n кроме i = j) хотя

бы для одного входного вектора.

Последнее определение показывает, что при существовании последователь­ности T с указанными свойствами, класс неисправностей F разбивается на два класса неразличимых неисправностей. Также такую последовательность T часто называютразбивающей, поскольку она делит один класс неисправностей на несколько. Нефор­мально такую последовательность также можно назвать диагностической. Также по­следнее определение является конструктивным. Именно на его основе будет строиться наш алгоритм.

3. Общая структура алгоритма построения диагностических тестов.

Цель алгоритма - построение такой тестовой последовательности, которая способна разбить исходный класс одиночных константных неисправностей на макси­мальное число классов неразличимых неисправностей.

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

На практике результатом работы алгоритма является набор разбивающих по­следовательностей, с помощью которых полный список неисправностей разбивается на неразличимые классы, каждый из которых может содержать более одной неисправно­сти. Это значит, что алгоритму не удалось построить разбивающую последователь­ность для неисправностей, которые входят в данный класс. Однако это не говорит о том, что такая последовательность не существует в принципе. В этом смысле предла­гаемый алгоритм относится к классу недетерминированных.

Структурно алгоритм представляет собой итеративный процесс генерации диагностических последовательностей. Всякий раз, когда удаётся построить последо­вательность, которая разбивает выбранный класс неразличимых неисправностей на несколько классов, она добавляется в финальный тест.

Каждая итерация алгоритма состоит из трёх фаз.

1) выбор целевого класса из текущего множества классов неразличимости;

2) построение различающей последовательности для выбранного класса;

3) если в фазе 2 построена различающая последовательность, то выполняется модели­рование для других классов, чтобы проверить возможность того, что она также являет­ся расщепляющей для них.

При этом фаза 1 является подготовительной для фазы 2, а фаза 3 - заключи­тельной. Таким образом, указанные фазы 1 и 2 представляют собой верхний уровень алгоритма, а фаза 2 - нижний, причём именно последний основан на ГА. Видно, что такая структура алгоритма в общем виде повторяет структуру алгоритма генерации тестов для одиночных константных неисправностей [5]. Это позволяет говорить о том, что они оба относятся к классу двухуровневых недетерминированных алгоритмов. Особенностью данного класса является то, что генетический алгоритм используется только на нижнем уровне, тогда как цель его работы выбирается на верхнем уровне с помощью некоторых эвристик.

Укрупнённый псевдокод алгоритма приведён ниже.

Построение диагностического теста(схема) {

чтение описания схемы();

построение полного списка неисправностей  F (); while( не достигнут критерий остановки() ) {

// фаза 1 - выбор целевого множества

Fj =выбрать целевое множество();//случайная генерация

if( Fj ==NULL )

{

ге1;игп;//целевое множество не выбрано-конец алгоритма

}

иначе

{

// фаза 2 - генетический алгоритм

T=ГА построения ДП(схема,  Популяция,  множество  Fj );

if(  Ti  диагностическая для  Fj )

{

добавить в финальный тест ( Ti );

// фаза 3 - дополнительная проверка

дополнительная проверка для всех других множеств ( Ti ); }// конец if - вызов Фазы 3 алгоритма }     // конец if - выбрана целевое множество }        // конец while - не достигнут критерий остановки } // конец алгоритма

Опишем подробнее общую структуру алгоритма.

Фаза 1 алгоритма представлена процедурой «Выбрать_целевое_множество». В ней происходит генерация набора случайных входных последовательностей {Ti} . Далее производится моделирование на каждой из данных последовательностей для всех классов неразличимости Fj, которые построены на текущий момент. Для каждого

из них происходит вычисление оценочной функции Ej (Ti, Fj) (см. следующий раз­дел). Если в данном месте ни для одной из последовательностей не получено значение, которое превышает некоторое пороговое: Ej (Ti,Fj) < Епор, то происходит генерация

нового множества последовательностей {Ti } . Такая попытка производится не более, чем предопределённое число раз.

Если же для некоторого класса неразличимости Fj  получено значение

Ej (Ti, Fj) > Епор, то данный класс выбирается в качестве целевого для фазы 2 алго­ритма, причём последний набор последовательностей {Ti} выбирается в качестве на­чальной популяции генетического алгоритма.

В фазе 2 алгоритма для выбранного класса неразличимости Fj строится, по

возможности, диагностическая последовательность. Этап основан на генетическом алгоритме и подробно описан в следующем разделе.

Фаза 3 алгоритма является дополнительной. В ней на построенной диагно­стической последовательности производится моделирование для всех неразличимых классов неисправностей (кроме Fj - целевого класса фазы 2), которые построены к

текущему моменту времени. Цель данного моделирования проверить: является ли по­строенная для Fj диагностическая последовательность разбивающей для других клас­сов неразличимости.

Фазы 1-3 алгоритма повторяются итеративно, но не более чем заранее задан­ное число раз.

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

4. Генетический алгоритм построения диагностических тестов.

В данном разделе будет описан генетический алгоритм построения разли­чающей последовательности для выбранного множества неисправностей. Известно [4], что для построения генетического алгоритма необходимо описать его основные ком­поненты: кодирование особей и популяций, оценочную функцию для особи, генетиче­ские операции (выбор, скрещивание, мутация, построение новой популяции).

Поиск алгоритмом производится в пространстве всех возможных входных последовательностей с заданной шириной входного вектора, которая равна числу внешних входов схемы. Кодирование особи является классическим в задачах построе­ния входных последовательностей [5]. Особь это последовательность, которая состоит из некоторого числа входных двоичных наборов. Набор таких особей представляет собой популяцию.

Оценочная функция является одним из важнейших элементов всего алгорит­ма. Эффективная оценочная функция позволяет находить необходимые решения. С другой стороны скорость её вычисления влияет на скорость всего алгоритма.

Очевидно, что для некоторой входной последовательности Tj и класса неис­правностей Fj достаточно легко определить является ли она диагностической, т.е. раз­бивает ли она данный класс как минимум на два класса неразличимости. Для этого достаточно выполнить моделирование поведения схем для всех неисправностей, кото­рые входят в Fj. Однако оценить, насколько близко данная последовательность Tj

подошла к решению такой задачи, гораздо труднее. В задачах построения входных идентифицирующих последовательностей [10] оценочная функция часто строится на основании показателя активности схемы: чем больше различных значений в двух срав­ниваемых схемах, тем выше оценка данной входной последовательности. В описывае­мом алгоритме оценочная функция вычисляется на основе двух следующих парамет­ров:

- число триггеров с различными значениями в неисправных схемах, которые соот­ветствуют неисправностям, входящим в текущий класс неразличимости;

- число выходов вентилей с различными значениями в неисправных схемах, кото­рые соответствуют неисправностям, входящим в текущий класс неразличимости.

Для вычисления оценочной функции всей последовательности сначала вы­числяются оценочные функции каждого входного вектора, который входит в данную последовательность. Для класса неразличимости Fj и к -го вектора последовательно­сти T j данная функция имеет следующий вид

E(Tk,F,) = к -f R\(Tk,F,) + к2 f R2n(T}k,F,), (1)

П=1 2=1

где:

Rln (Tk, Fj) - функция различия выходов триггеров; R2 (T*, Fj) - функция различия выходов вентилей;

к1 и к2 нормирующие коэффициенты, показывающие, что различия значений на выходах триггеров важнее различия на выходах элементов; N    и Ывент - число триггеров и выходов элементов в схеме соответственно.

Функции различия определяются следующим образом:

[0, если выходы элементов с идексом n, которые принадлежат

классу Fj, одинаковы после подачи набораTk; (2) 1, иначе;

где а = 0,1 для множества триггеров и выходов элементов схемы соответственно.

На основании оценки каждого вектора, входящего в последовательность, вы­числяется её оценочная функция, которая имеет вид:

Страницы:
1  2 


Похожие статьи

Д Е Иванов - Взаимодействие компонент в распределённых генетических алгоритмах генерации тестов

Д Е Иванов - Генетические алгоритмы построения идентифицирущих последовательностей для цифровых схем с памятью

Д Е Иванов - Генетический алгоритм оптимизации рассеивания тепловой энергии входных тестовых последовательностей

Д Е Иванов - Генетический алгоритм построения диагностических последовательностей цифровых устройств

Д Е Иванов - Генетический подход проверки эквивалентности последовательностных схем