автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование методов моделирования и оценки мер тестопригодности логических схем

РГБ ОД

Томский государственный университет рщр

УДК 519.710, 519.718.7 На правах рукописи

Голубева Ольга Ивановна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ МОДЕЛИРОВАНИЯ И ОЦЕНКИ МЕР ТЕСТОПРИГОДНОСТИ ЛОГИЧЕСКИХ СХЕМ

Специальность 05.13.01 «Управление в технических системах»

Автореферат диссертации на соискание учёной степени кандидата технических наук

Томск - 2000

Работа выполнена в Томском государственном университете.

Научный руководитель:

доктор технических наук, профессор Матросова А.Ю.

Официальные оппоненты: член-корреспондент РАН,

профессор Пархоменко П.П.

кандидат технических наук, доцент Паршина Н.А.

Ведущая организация:

Томский политехнический университет, г. Томск.

Защита состоится июня 2000 г. в 14.30 на заседании диссертационного Совета Д 063.53.03 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина 36.

С диссертацией можно ознакомиться в библиотеке Томского государственного университета.

Автореферат разослан " мая 2000 г.

Ученый секретарь диссертационного Совета,

к.ф.-м.н., доцент

2

Б.Е. Тривоженко

- С^ НУ. О У- /-/¿Г О

Общая характеристика работы

Актуальность проблемы. Тестирование дискретных устройств занимает важное место при их проектировании, производстве и эксплуатации. В процессе тестирования на устройство подают специальные входные воздействия, называемые тестами. При построении тестов устройство обычно рассматривается на уровне математической модели -логической схемы.

Моделирование является одним из основных средств построения тестов для логических схем, особенно для схем с памятью. Под моделированием понимается получение выходной реакции схемы на заданную входную последовательность. Задача моделирования схемы при неизвестных значениях некоторых компонент векторов входной последовательности и вектора, представляющего начальное состояние (для синхронной последовательностной схемы), является недостаточно исследованной. Для решения этой задачи применяются методы, которые либо являются неточными, либо достаточно трудоемкими. Речь идет о методах троичного моделирования логических схем. При реализации неточного метода моделирования может быть вычислено значение х, интерпретируемое как «неизвестно 0 или 1», в то время, как на всех последовательностях булевых векторов, полученных из рассматриваемой троичной последовательности, вычисляется значение 1(0). Неточность моделирования ведет к увеличению длины тестовой последовательности, построенной на основе такого моделирования.

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

называют мерами тестопригодности.

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

Вышеизложенное показывает, что актуальность темы определяется:

• трудоемкостью известных методов точного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входного вектора;

• отсутствием практически применимых точных методов моделирования синхронной последовательностной схемы при неизвестных значениях некоторых компонент векторов входной последовательности и вектора начального состояния;

• трудоемкостью известных методов точного вычисления мер тестопригодности схемы.

Цель работы. Целью работы является разработка методов точного моделирования комбинационных и синхронных последователыюстных схем при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния (для синхронной последовательностной схемы), то есть методов точного троичного моделирования, а также разработка эффективных методов точного вычисления мер тестопригодности для комбинационных схем.

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

Научная новизна. Разработаны методы точного троичного моделирования. Предложен метод точного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов. Метод основан на представлении булевых функций, реализуемых схемой, в виде ортогональных ДНФ (ОДНФ) или BDD-графов (Binary Decision Diagram), являющихся компактным описанием ОДНФ. Такое описание проще ранее применяемых для решения задачи функциональных описаний. Для синхронных послсдовательностных схем

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

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

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

Реализация полученных результатов. Исследования выполнялись в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ), программа 1995-2000 гг. «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем»; министерства образования по разделу «Автоматика и телемеханика», направление - «Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники» (19961997гг. «Исследование проблемы повышения качества тестирования и контролепригодного проектирования»; 1998-2000 гг. «Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования»); ФЦП «Интеграция», раздел «Прикладная дискретная математика». Предложенные методы моделирования логических схем были реализованы в виде пакета прикладных программ в

рамках исследований по Минвузовской научно-технической программе «Конверсия и высокие технологии. 1997-2000 гг.» (проект №95-1-21 «Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»). Теоретические результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета: используются в курсе лекций «Диагностика дискретных устройств».

Апробация работы. Научные результаты диссертационной работы докладывались и обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ, а также на 3-ей международной научно-технической конференции «Актуальные проблемы электронного приборостроения» (Новосибирск, 1996), IEEE European Test Workshop 1997 (Italy, Cagliari, 1997), международной конференции «Всесибирские чтения по математике и механике» (Томск, 1997), международной конференции «Сибирская конференция по исследованию операций» (Новосибирск, 1998), 3-м международном симпозиуме «Application of the Conversion Research Results for International Cooperation» (Томск, 1999), 3-й международной конференции «Автоматизация проектирования дискретных систем» (Минск, 1999).

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка используемой литературы. Объем диссертации составляет страниц, в том числе: титульный лист -1 стр., оглавление - 2 стр., основной текст - /¿7/стр., список литературы из 81 наименования - 8 стр., приложение - 5 стр.

Основное содержание работы

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

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

Функциональной моделью, описывающей поведение комбинационной схемы на входных двоичных векторах, является система булевых функций, реализуемых выходами схемы. Функциональной моделью, описывающей поведение синхронной последовательностной схемы на входных последовательностях двоичных векторов, является логический автомат, структурные функции переходов и выходов которого сопоставлены выходам комбинационной составляющей последовательностной схемы. Будем говорить, что такой автомат реализуется схемой.

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

/

Булева функция /(хи...,х„) задает отображение {0,1}" —> {0,1}. Обозначим через М[ = {у е {0,1}" : /(у) = 1} (М{ = {у е {0,1}" : /(у) = 0}) -область единичных (нулевых) значений функции

г

Троичная функция g(xu...,x„) задает отображение {0,1,х}" -> {0,1,х}. Введем на множестве Е* = {0,1,х} отношение частичного порядка: 0 < х , 1<х, 1 и 0 не сравнимы. Троичные векторы а = (а!,...,ал) и р =(р,,...,р„) находятся в отношении а<р, если а,<р(, 1 = 1,п. Троичный вектор а = (а15...,а„) представляет интервал булевых векторов В(а) = {у е {0,1}": у < а} . Например, а = 01х1х, тогда В(а) = {01010, 01011,01110,01111}.

Определение. Назовем интервальным расширением булевой функции троичную функцию /"(*,,...,*„), значение которой на троичном векторе схе{0,1,х}" определяется по правилам:

1) /*(ос) = 1, если В(а) с М{ ;

2) Г (а) = 0, если В(а) с М{;

3) /*(а) = х , если В(а)Г)М{ * 0 иадПМо^0.

Это значит, что интервальное расширение /х булевой функции /

принимает значение 1(0) на троичном векторе а, если на любом булевом векторе из интервала В(а) функция / принимает значение 1(0), в

противном случае /х на троичном векторе а принимает значение к.

Под логическим автоматом с п входами, т выходами и р обратными связями будем понимать конечный автомат, заданный пятеркой N=(A,Q,B,4',Ф), где Л = {0,1}", Q={0,1}р и В = {0,1}'" - входной алфавит, множество состояний и выходной алфавит, соответственно. Функции f и Ф, называемые функциями переходов и выходов, являются векторными 4* = (v|/|,v|/2,...,vy ) и Ф =(<p,,(p2,...,q>m); компоненты функций

называются структурными функциями переходов и выходов и являются булевыми функциями, определенными в АхQ и принимающими значения

в Q и В, соответственно. Обозначим через А* множество входных последовательностей ак длины к, к = 1,2,... в алфавите А. Для описания функционирования логического автомата на входных последовательностях функции переходов-выходов распространяются на множество A* xQ следующим образом. Пусть ак е А и а е А, тогда фДаЧ5(0)) = ф,.(а,У(а*,5(0))), и Ч//а4а,5(0)) = Ч//а,Ч'(а*>5(0))),

xj/y(A,8(0)) = 8(0), j = \,p, где Л - пустая последовательность. Выходную последовательность логического автомата, соответствующую входной последовательности ак и начальному состоянию 5(0) будем обозначать через Ф(а*,5(0)) = (ф1(а<:,5(0)),...,фт(а^,5(0))). Длина выходной последовательности равна длине входной последовательности, и г'-ый вектор выходной последовательности равен значению функции выходов Ф автомата на входной последовательности, состоящей из первых i векторов входной последовательности ак. Последовательность состояний определяется аналогично и обозначается через

Ф(а*,5(0)) = ,8(0)),...,v¡)p(ai,6(0))).

Сопоставим алфавиту А множество переменных X =(х1,...,хп), алфавиту Q - множество переменных Z = (zl,...,zp), и алфавиту В -

множество Y - (yt,...,ym). Функционирование логического автомата задается системой канонических уравнений вида

Z(/) = 4W),Z(Í- i)).

Здесь X{t) = (xj(t),...,xn(t)) - переменные, которые представляют /-ый вектор входной последовательности ак, a Z(0) = (zl(0),...,zp(0)) -переменные, значения которых представляют начальное состояние 8(0).

Обозначим через yk(X(l),...,X(k),Z(0)), ге{1,...,/и}

{\ykj(X{\),...,X{k),Z(S>)), у е{1,...,/?}) булеву функцию, реализуемую функцией ф, (\\>j) на входной последовательности длины к. Функции <PÍ(*(1),...,X(A),Z(0)), i = и ykj{X{l),...,X(k),Zm, í = Vp реализуются выходами и псевдовыходами комбинационного эквивалента длины к синхронной последовательностной схемы. Обозначим Фк = ((pf ,...,(ркт) и Т* -(у/{,...,\\1кр) соответствующие векторные функции. Тогда выходные последовательности длины к логического автомата представляются значениями функций Ф', í = l,к - {Ф',...,ФА} . Аналогично последовательности состояний представляются значениями функций ГР1,.-,^}.

Определение. Назовем интервальным расширением логического автомата N пятерку N" = (A*,Q*, Вх,*¥х,ФХ), где А" = {0,1,х}",

Q*={0,1,х}>, В* = {0,1,х}'\ 4fx=(Vr,V2.....vp и Фх=(ФГ,ф^,...,ФГл) -

функции переходов и выходов; компоненты функций и ф* определены

в Ах* xQ* и принимают значения в Q* и В*, соответственно. Значение

функции ф* (V)/*) на входной последовательности длины к определяется

троичной функцией ф*" (X(1),...,X(£),Z(0)) (vf (X(l),...,X(k),Z(0))).

Для краткости будем последовательности троичных векторов называть троичными последовательностями. Обозначим выходную троичную последовательность интервального расширения N* логического автомата

N через Ф>\5(0)) = (ф*(<Д 5(0)),. ...^(а*. 6(0))) и через vPx(a<:,5(0)) = (ij;j<(a<r,6(0)),...,i(/p(ai,5(0))) - троичную последовательность состояний. Выходная троичная последовательность длины к представляется значениями функций {Ф1 ,...,Ф* }, троичная последовательность состояний интервального расширения Nх

■ X ,.х

представляется через функции {Ч' ,...,4' }.

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

Пусть комбинационная схема реализует систему булевых функций /¡(х\,...,хп), i-\,n. Моделирование комбинационной схемы на входном троичном векторе а = (a,,...,are) заключается в вычислении выходного троичного вектора ß = (ßj,...,ßm). В случае точного моделирования ß,- = /]*(а,,...,ая), i = l, т. При неточном моделировании ß, > /х(а,,...,а„). Это значит, что при неточном моделировании на выходе схемы может быть получено значение х как при условии В(а) с М{ , так и при условии В(а) с м[.

Точное (неточное) моделирование синхронной последовательностной схемы, реализующей логический автомат N = (A,Q,ß,lV,0), на входной

троичной последовательности ак и троичном векторе начального состояния 5(0) заключается в вычислении выходной троичной

последовательности ß* и троичной последовательности состояний 8к

таких, что ß* = $*(a*,5(0)) (ß* >Фх(а*,5(0))) и 8* = Тх(а*,5(0))

(6* £ (а*,5(0))).

Точное троичное моделирование схемы можно свести к двоичному моделированию. Для этого необходимо перебрать все двоичные векторы (двоичные последовательности), представляемые входным троичным вектором (входной троичной последовательностью) и выполнить их моделирование. Для моделирования синхронной последовательностной схемы на троичной последовательности длины к необходимо выполнить се

моделирование на 2kr'+r° двоичных последовательностях, где >) и г0-

число компонент со значением х во входном векторе и в векторе начального состояния, соответственно. Такой перебор практически не возможен уже при небольших значениях к. Предпочтительнее выполнять моделирование сразу на всем интервале входных воздействий, представленном троичным вектором. Широко известным методом, позволяющем выполнять такое моделирование, является моделирование по правилам троичной логики. Моделирование выполняется по структурному описанию схемы и заключается в получении значений интервальных расширений элементарных булевых функций, реализуемых логическими элементами и выполнении их суперпозиции. Моделирование по правилам троичной логики является неточным. Из-за простоты реализации такое моделирование широко применяется на практике при решении рассматриваемой задачи.

Вторая и третья главы диссертации посвящены разработке точных методов троичного моделирования комбинационных и синхронных последователыюстных схем.

Во второй главе диссертации предлагаются метод точного троичного моделирования комбинационной схемы и метод точного троичного моделирования синхронной последовательностной схемы.

Точное моделирование комбинационной схемы на троичном векторе есть вычисление значения интервального расширения f*(X) булевой функции f(X), X - (дГ|,...,хп), на троичном векторе а = (а,,...,а„). Это вычисление в работе сводится к вычислению вероятности единичного значешм булевой функции при заданном распределении вероятностей единичных значений её аргументов Р(Х) = (р(х{),р{х2),...,р{хп)). Распределение Р(Х) порождается вектором а и задается по правилу: если а, =1(0), то р(х,) = 1(0); если а, = х, то p(x¡) = р,, где 0<р; < 1. Обозначим через P(f(X)) вероятность P(f(X) = 1).

Утверждение 1. /*(а) = 1 (0) о P(f) = 1(0) ; иначе /х(а) = х.

Итак, для того, чтобы получить значение /х(а), необходимо вычислить вероятность P(f) при заданном распределешга Р(Х), определяемом вектором а. Для вычисления вероятности единичного

значения булевой функции в работе предлагается использовать известные методы, основанные на представлении функции в виде ортогональной ДНФ (ОДНФ) либо ВБВ. ЕШБ представляет компактное описание ОДНФ булевой функции в виде графа.

Точное моделирование синхронной последовательностной схемы на входной троичной последовательности а* и троичном векторе начального состояния 5(0) есть вычисление выходной троичной последовательности

Р* = Ф*(а',5(0)) и троичной последовательности состояний дк - Ч'*(а*,5(0)) интервального расширения //* логического автомата N = ({0,1}",{0,1}р,{0,1}"1,4Р,Ф), реализуемого схемой. В параграфе 2.2 диссертации предлагается метод точного троичного моделирования для логического автомата И, структурные функции переходов-выходов которого заданы в виде ОДНФ.

Каждая компонента вектора выходной последовательности вычисляется отдельно. Рассмотрим метод вычисления компоненты Р,(£), /е {1,...,/и} к-го вектора выходной последовательности; компоненты векторов из последовательности состояний вычисляются аналогично. Согласно

определению, р,(£) = ф,4 (а(1),...,а(&),5(0)). Метод вычисления значения

.к

функции ф,- {Х{\),...,Х(к),2(0)) основан на изложенном выше методе вычисления значения интервального расширения булевой функции. Вычисление вероятности Р(ф':) можно выполнить непосредственно по ОДНФ функции ф*. Однако, ОДНФ функции ф* зависит от к-п + р переменных, и получение ОДНФ функции практически невозможно уже для небольших к. В работе предлагается объединить процессы построения ОДНФ булевой функции ф* с вычислением вероятности ).

Вычисление выполняется за к шагов. На первом шаге выполняется подстановка в ОДНФ функции ^¡(Х(к),1(к -1)) вместо переменных множества Х{к) вероятностей, сопоставляемых вектору а (к); на шаге /,

1-2,к выполняется: 1) подстановка вместо переменных множества г(к-1 +1) ОДНФ функций из множества Ч'(Х(к -1 + 1), 2(к - /)); 2) раскрытие скобок, приведение конъюнкций к элементарным; 3)

подстановка вместо переменных множества Х(к-1 +1) вероятностей, сопоставляемых вектору а(к -1 + 1). На к-ом шаге вычисления выполняется также подстановка вместо переменных множества 2(0) вероятностей сопоставляемых вектору 5(0). Таким образом, в процессе вычисления Р(ф-') формулы зависят не более чем от п + р переменных. На 1-ом шаге вычисления формула после подстановки вместо переменных множества Х(к - / +1) соответствующих вероятностей имеют вид

р^) = %)-р{к,]{г{к-т , (2)

здесь к^(2(к-1)) - конъюнкции, зависящие от переменных множества 2{к -1).

В работе предлагаются два метода сокращения вычислительных затрат при получении Р(ф*). Первый метод сокращения вычислений основан на использовании результатов неточных методов троичного моделирования синхронной последовательностной схемы. Пусть при неточном моделировании получена выходная последовательность Р'* , Р'* > р* и последовательность состояний Ъ'к, о'к > 8к. Тогда, если &'(Л ~ КО), то 8,0') = КО); если р;0') = 1(0), то р,.(у) = 1(0). Поэтому, если р;(Л) = 1(0), то значение Р,(/г) вычислено. Согласно утверждению 1, если 5,0) = 1(0) , то Р(ц//) = 1(0) Тогда на соответствующем шаге вычисления Р((р?) формулы вида (2) можно упростить, подставляя в ее конъюнкции вместо переменной г, (/) значение 1(0).

Для вычисления Р,(&) нужно знать не точное значение ), а лишь то, какому из условий оно соответствует: 1)Р(ф*) = 1, 2)Р(ср*) = 0, 3) 0 < Р(ф') < 1. Это свойство используется во втором методе сокращения вычислений. В работе предлагается алгоритм оценки значения Р,(&) на /-ом шаге вычисления, по формуле (2), который позволяет при некоторых значениях коэффициентов а' сделать заключение о том, какому из условий

соответствует вероятность Р((р-). Если такая оценка не может быть сделана на 1-ом шаге, то выполняется следующий шаг вычисления.

Итак, методы сокращения вычислений позволяют уменьшить число шагов вычисления, выполняемых для получения ). Первый метод, кроме того, позволяет в процессе вычисления упрощать промежуточные формулы вида (2).

Пусть задано структурное описание комбинационной схемы, тогда для выполнения точного троичного моделирования предложенным методом необходимо получить функции, реализуемые выходами схемы в виде ОДНФ. Предлагается получать ОДНФ суперпозицией от выходов ко входам, заменяя очередную внутреннюю переменную соответствующей функцией элемента от его входов. Функции элементов при этом представляются в виде ОДНФ. Аналогично можно получить структурные функции переходов-выходов синхронной последовательностной схемы в виде ОДНФ.

Для оценки эффективности предложенных методов сокращения вычислений при реализации точного метода моделирования синхронных последовательностных схем были выполнены компьютерные эксперименты на схемах, заданных структурно в бенч-марках. В таблице 1 представлено среднее число шагов, которое потребовалось выполнить при совместном применении методов сокращения вычислений. Усреднение выполнялось по 30 входным последовательностям и по числу выходов. Без применения методов сокращения вычислений необходимо выполнить число шагов, равное длине входной последовательности. Здесь к - длина входной последовательности, 5 (г) - число компонент входного вектора (вектора начального состояния), принимающих значение х; п, т, р - число входов, выходов и линий обратных связей схемы, соответственно. ]/[ ([г]) - ближайшее сверху (снизу) целое от числа I. В заголовках столбцов в скобках указаны параметры схем (п,т,р).

Таблица 1.

к 5 1 3208x1 (10,1,8) 8298 (3,6,14) Б344 (9,11,15) 8386 (7,7,6) 8820 (18,19,5) 81488 (8,19,6) Б1494 (8,19,6)

20 р 5,67 3,84 2,30 1,11 1,94 3,31 1,80

20 р 5,33 5,93 1,75 2,26 3,23 4,52 4,64

20 1-К1 р 2,73 5,93 2,55 2,73 4,25 4,12 3,91

Выполнены сравнения результатов моделирования предложенным точным методом и методом моделирования по правилам троичной логики. В столбцах таблицы 2 для соответствующих схем указана доля в процентах неправильно полученных значений х при моделировании по правилам троичной логики по отношению к 0 и 1, полученным при точном моделировании. Доля достаточно велика для большинства рассмотренных схем. Это означает, что результаты традиционного моделирования по правилам троичной логики могут быть существенно улучшены предлагаемым точным методом моделирования.

Таблица 2.

к 5 г 8208x1 5298 8344 5386 5510 8820 51488 81494

2 1УЛ г/л 0,0 23,1 22,0 15,8 88,9 33,5 24,3 18,0

5 {■/,} 0,0 11,3 14,3 14,0 100,0 26,7 9,0 23,6

10 У/Л у/1 0,0 9,4 13,1 10,6 100,0 31,2 17,5 10,7

15 У/Л УЛ\ 0,0 2,2 6,8 10,4 100,0 18,4 15,3 9,1

Третья глава диссертации посвящена точному троичному моделированию синхронной последовательностной схемы. Метод моделирования схемы основан на использовании логического автомата Ы' специального вида. В автомате каждому состоянию схемы сопоставлена своя внутренняя переменная. Использование автомата такого вида позволило разработать метод пошагового моделирования, который выполняется непосредственно по функциям переходов-выходов без построения функций Фк, Ч'к, реализуемых автоматом на входных последовательностях длины к.

Логический автомат ЛГ имеет вид: И'= {А',()',В',Х Р',Ф')> где

Л'= {0,1}", В' = {0,1}'", б'с{0,1}/'', 2' состоит из р' различных векторов размерности р', в которых одна компонента принимает единичное, а остальные - нулевые значения. Функционирование автомата описывается системой канонических уравнений:

У1 (0 = Ч>! (*(0>2(1 -1)) = / -1) V... V 0?р,гр, (* -1), / = 1 г, (0 = ч>) (Х(0,г(1 -1))= -1) V... V 0%.2р. (/ -1), } = \~р.

Здесь Б?, Ор - ДНФ, зависящие от переменных множества Л'(/).

Функции , 7=1, р ортогональны друг другу и \у = 1.

В автомате Ы' число входов, выходов и состояний совпадает с числом входов, выходов и состояний автомата N = Ф), реализуемого

схемой; р' = 2Р, где р - число линий обратных связей схемы; А' = А, В' = В, а между элементами алфавитов и <2 имеет место взаимно однозначное соответствие. В работе показано, что моделирование синхронной последовательностной схемы на двоичных последовательностях сводится к моделированию автомата И', а на троичных последовательностях - к моделированию его интервального расширения Л"* (в работе понятие интервального расширения введено также для не всюду определенного логического автомата).

Для вычисления выходной троичной последовательности р* и

о/к

троичнои последовательности состоянии 5 интервального расширения М'* автомата Ы', соответствующих входной троичной последовательности ак длины к > 1 достаточно выполнять пошаговое вычисление непосредственно по системе (3), а именно: состояние 8'(0 и выходной вектор Р(/) на входной последовательности длины I вычисляются с использованием состояния 5'(/ -1), полученного на предыдущем М шаге вычисления и 1-го входного вектора. В работе доказывается теорема (теорема 3.4), устанавливающая корректность такого вычисления.

Предлагаются процедуры вычисления троичного состояния 5'(/) и троичного выходного вектора Р(/) на троичном векторе -1).

Процедура 1 вычисления значения 5'(0 -

1. Подставляем вектор а(/),5'(^-1) по правилам троичной логики в функции переходов системы (3). Результат подстановки обозначаем 5"(0-

2. Полагаем компоненты вектора 8'(/) равными соответствующим компонентам вектора 8"(г)- Однако, если 5/'(0> а 5/'(<)> то 5-ой компоненте вектора 8'(0 приписываем значение 1.

Доказанные в работе теоремы (теоремы 3.1-3.3) подтверждают корректность предложенной процедуры вычисления значения 5'(/).

Процедура 2 вычисления значения РД/).

Вычисляем значения В? (сф)), У/:8у(*-1)*0.

Если У/: 5}(0) ф 0 (а(/))= 1(0), то (3,(0 = 1(0); иначе [3,(0 = х .

Доказывается корректность процедуры вычисления значения РД/).

В параграфе 3.3 диссертации предлагается способ построения логического автомата ЛГ, с системой канонических уравнений вида (3) по структурному описанию синхронной последовательностной схемы.

Разработано программное обеспечение, реализующее предложенный метод моделирования автомата. В параграфе 3.4 приведены результаты экспериментов. Эксперименты проведены на синхронных последовательностных схемах, заданных структурно в бенч-марках. Рассматривались схемы, имеющие число линий обратных связей до 12. Для оценки эффективности предложенного метода было выполнено сравнение времени его работы со временем работы метода моделирования по правилам троичной логики. Установлено, что время работы этих методов сопоставимо. Время на построение системы (3) из системы ДНФ функций переходов-выходов схемы для рассмотренных схем оказалось очень незначительным (меньше секунды). Будем иметь ввиду, что система (3) строится один раз, а затем может быть использована для моделирования схемы на любых входных последовательностях.

В главах 2 и 3 предложены два метода точного троичного моделирования синхронных последовательностных схем. Метод, предложенный в главе 3, имеет большее быстродействие, поскольку является пошаговым. С другой стороны, применение этого метода эффективно для схем с числом линий обратных связей не большим 10-12. При большем числе линий обратных связей описание (3) автомата становится очень громоздким. В этом случае предлагается применять метод из главы 2.

Четвертая глава диссертации посвящена методам точного вычисления мер тестопригодности для комбинационных схем.

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

и наблюдаемости полюсов схемы.

Вероятность обнаружения неисправности / в схеме есть вероятность того, что эта неисправность обнаруживается случайным входным набором.

Рассматривается класс одиночных константных неисправностей, так как при оценке пригодности схемы для вероятностного тестирования, как правило, используются именно эти неисправности.

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

1(0 )-управляемость полюса схемы есть вероятность того, что случайный входной набор устанавливает рассматриваемый полюс в состояние 1(0).

Вычисление вероятности обнаружения константной неисправности, наблюдаемости и управляемости полюса V схемы сводится к вычислению вероятностей единичных значений соответствующих функций обнаружения неисправности, наблюдаемости и управляемости при заданном распределении Р(Х) вероятностей единичных значений входных переменных.

Рассмотрим комбинационную схему с п входами и т выходами. Пусть X = {х],...,хл} - множество входных переменных схемы. Обозначим через ср, (X) - функцию, реализуемую г'-ым, ¡' е {1,...,ш} выходом исправной схемы, , а е {0,1} - функцию, реализуемую 1-ым выходом схемы с

неисправностью константа а в полюсе V.

'Функция обнаружения неисправности константа а - Ва(Х) имеет вид:

Обозначим через /(X) функцию, реализуемую полюсом V схемы. Тогда функции 1-управляемости С1(Х) и О-управляемости С°(Х) имеют вид:

(4)

(6)

С\Х)=/(Х),С\Х) = ДХ). (8)

Для вычисления вероятности единичного значения булевой функции в работе используются известные методы, применяемые к описаниям функции в виде ОДНФ, либо в виде ЕШ1). Процесс получения ОДНФ и ВББ функций (5)-(7) может оказаться достаточно трудоемким. Решается задача сокращения вычислительных затрат, связанных с получением ОДНФ или ВОБ описаний этих функций и вычислением вероятностей их единичных значений. Это достигается за счет использования свойств специальных функций и их инверсий, зависящих от входных переменных и переменной, сопоставляемой полюсу и рассматриваемой в качестве входной.

Сопоставим полюсу V схемы переменную V. Рассматривая переменную у схемы в качестве входной, получим функцию т|,(А',у), реализуемую 1-ым,

г е {1,...,/?;} выходом схемы, и ее инверсию г|,(Х, у). г|,(Л',у) порождает функции <р'(Х) и ф'(Х) = т1,.(Х,1), ф°(Х) = л,ДО)). Функция

порождает функции ф) и ф°: ф|(Х) = "П,(А',1), ф-(А') = т|,.(А',0).

Получим функции ^¡{Х, у), лДА', у) в виде ОДНФ по структурному описанию схемы. Представим ОДНФ г|/(Х,у) в виде г\({Х, у) = К1 V К" ■ V V К} ■ V , здесь К1, А',-', К] - ОДНФ, не зависящие от переменной V. Тогда, ф) = К1 V К], = К1 V К■ .

Аналогично представим Ц^Х, у) в виде Ц^Х= ^ V К^ ■ V V К" ■ х>.

тогда, с?; = V к; , ф°=к, V к;.

Чтобы получить ОДНФ функции В(Х), необходимо выполнить ортогонализацию формулы (6) и представить Д(А) и В^Х) в виде ОДНФ. Ортогонализация выполняется следующим образом:

В{Х) = В1{Х)чЩх)-В2{Х)ч...чЩХ)ЩХ)-..,Вт_х(Х)-Вт{Х) (9)

Подставляя полученные выражения для функций ф), ф°, ф), ф° в формулу (7) и ее инверсию, получаем функцию наблюдаемости на /-ом выходе В;(Х) и ее инверсию В1(X):

я,. = а:,,-л',. V/:,.-к; у/г;-/:,, vк;,■к"¡ уа-, -а:,, V*,. -я? ^-а' V/:;-а:; , д. = к1 V а:,. • А:; V к,. • к,у V к; • А:; V к, V к, • к* V • к; V к" ■ к;.

Используя свойства ОДНФ А"(, /С,1", А',", , А^ и К^ , в работе выполнено сокращение формул: К» ■ ^ ч К] ■ К*,

щ{х) = А", V а:; • А:; V А\ V А; • А;; .

После соответствующего перемножения конъюнкций ОДНФ K¡, АГ,У, АГ,", , и АТ* функции и Л,(А') представляются в виде

ОДНФ.

Итак, вычисление наблюдаемости сводится к вычислению вероятности единичного значения функции В{Х), ОДНФ которой получается из

формулы (9) перемножением ОДНФ функций В^Х) и #,(X). Предложенные формулы, найденные при использовании свойств разложения функций г|,(ЛТ,у), у), позволяют сократить

вычислительные затраты, связанные с получением ОДНФ функций В1 (X) и В,{Х).

При вычислении Р(В), с целью сокращения вычислений, можно также воспользоваться приближенной оценкой наблюдаемости Р(В) Р(В) = Р(В] V Вг V... V Вт) > тах Р(В1).

1<л&т

Предложенный подход распространен на представление функции в виде ВИО и позволяет сократить вычислительные затраты, связанные с получением ЕЮЭ функции наблюдаемости.

Для получения функции обнаружения неисправности константа а используется формула: Оа(Х) = В(Х)-С^(Х).

Эта формула позволяет совместно решать задачи вычисления вероятности обнаружения неисправности и наблюдаемости и выделить общую часть при получении функций обнаружения неисправностей константа 1 и константа 0, сократив тем самым вычисления при нахождении вероятностей обнаружения неисправностей.

Для оценки эффективности предложенных методов были выполнены компьютерные эксперименты. Проведено сравнение времени вычисления мер тестопригодности по исходным формулам (4)-(8), где функции ср,, ф,а и их инверсии извлечены из структурных описаний комбинационных схем, и предложенными методами, использующими сокращенные формулы. Эксперименты показали, что при применении предложенных методов для схем размером до 800 полюсов имеет место сокращение во времени в 1,31,7 раза, для схем размером в «1500 полюсов - сокращение во времени в »2 раза.

Заключение

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

На защиту выносятся:

1. Метод точного троичного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входных векторов, основанный на ОДНФ представлении булевых функции, реализуемых схемой.

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

3. Эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

Список публикаций по теме диссертации

1. Голубева О. И. Троичное моделирование синхронных

последовательностных схем // Математическое моделирование.

Кибернетика. Информатика. - Томск: Изд-во ТГУ, 1999. - С. 53-59.

2. Матросова А.Ю., Голубева О.И., Коновалова А.А. К проблеме устойчивости вероятностного поведения синхронных последователыюстных устройств // Тр. 3-й междунар. науч.-техн. конф. «Актуальные проблемы электронного приборостроения». Новосибирск, 1996. - Т. 6. - 4.1. - С. 100-101.

3. A. Matrosova, О. Golubeva, S. Tsurikov. On correction of the results of a ternary simulation // Compendium of papers of IEEE European Test Workshop 1997. - Cagliari, 1997. - 2 c.

4. Голубева О.И., Матросова А.Ю., Ошлакова Т.А. Об оценке корректности моделирования дискретных устройств // Тез. докл. междунар. конф. «Всесибирские чтения по математике и механике». -Томск: Из-во ТГУ, 1997. - Т. 1. - С. 153-154.

5. Голубева О.И. Реализация троичного моделирования синхронных последовательностных устройств без потери точности // Материалы междунар. конф. «Сибирская конференция по исследованию операций». - Новосибирск: Изд-во ин-та математики СО РАН, 1998. - С. 124.

6. Матросова А.Ю., Голубева О.И. О коррекции результатов одного шага троичного моделирования // Докл. 2-й всероссийской конф. «Новые информационные технологии в исследовании дискретных структур». -Екатеринбург: ИМАШУрО РАИ, 1998. - С. 112-116.

7. Голубева О.И. Коррекция результатов троичного моделирования на последовательностях произвольной длины // Докл. 2-й всероссийской конф. «Новые информационные технологии в исследовании дискретных структур». - Екатеринбург: ИМАШУрО РАН, 1998. - С. 62-68.

8. A. Matrosova, О. Golubeva, Т. Oshlakova. On Correction of the Results of a Ternary Simulation and a Preliminary Estimation of the Correction Results // Proceedings of the 6-th Biennial Conference on Electronics and Microsystems Technology «Baltic Electronics Conference». - Tallinn, 1998. -P. 183-186.

9. Голубева О.И. Метод вычисления вероятности обнаружения неисправности, основанный на BDD-представлении функции // Тр. 3-го междунар. симпозиума «Application of the Conversion Research Results for International Cooperation». - Томск, 1999. - Т. 1. - С. 195-197.

ВВЕДЕНИЕ.

ГЛАВА 1. ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ, ПОСТАНОВКА ЗАДАЧ И

ОБЗОР МЕТОДОВ ИХ РЕШЕНИЯ.

1.1. Булевы функции и их интервальные расширения.

1.1.1. Булевы и троичные функции.

1.1.2. Интервальные расширения булевых функций.

1.2. Абстрактные автоматы, логические автоматы и их интервальные расширения.

1.2.1. Понятие абстрактного конечного автомата.

1.2.2. Интервальное расширение логического автомата.

1.3. Моделирование логических схем.

1.3.1. Логические схемы.

1.3.2. Постановка задачи моделирования.

1.4. Обзор методов моделирования.

1.5. Обзор методов вычисления мер тестопригодности для комбинационных схем.Т.

1.6. Задачи исследования.

ГЛАВА 2. МОДЕЛИРОВАНИЕ КОМБИНАЦИОННЫХ И СИНХРОННЫХ

ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ, ОСНОВАННОЕ НА ОДНФ-ПРЕДСТАВЛЕНИИ БУЛЕВЫХ ФУНКЦИЙ.

Введение.

2.1. Вычисление значения интервального расширения булевой функции, представленной в виде ОДНФ.

2.2. Вычисление реакции интервального расширения автомата на входную последовательность произвольной длины.

2.3. Моделирование логических схем.

2.4. Результаты экспериментов.

3.1. Постановка задачи. .61

3.2. Вычисление реакции интервального расширения логического автомата.63

3.2.1. Вычисление состояния интервального расширения автомата, соответствующего входной последовательности длины один.63

3.2.2. Вычисление выходных значений интервального расширения автомата на входной последовательности длины один.66

3.2.3. Вычисление реакции интервального расширения автомата на входную последовательность произвольной длины.67

3.3. Троичное моделирование синхронной последовательностной схемы.69

3.3.1. Троичное моделирование синхронной последовательностной схемы, заданной функционально. .69

3.3.2. Троичное моделирование синхронной последовательностной схемы, заданной структурно.74

3.4. Результаты экспериментов.75

3.5. Основные выводы по главе.76

ГЛАВА 4. МЕРЫ ТЕСТОПРИГОДНОСТИ ДЛЯ КОМБИНАЦИОННЫХ

СХЕМ.78

Введение.78

4.1. Постановка задачи.79

4.2. Оценка наблюдаемости.82

4.2.1. ОДНФ-представление функции наблюдаемости.82

4.2.2. ВБО-представление функции наблюдаемости.88

4.3. Оценка вероятности обнаружения неисправности.92

4.3.1. Получение функции обнаружения неисправности. .92

4.3.2. Вычисление вероятности обнаружения неисправности. .94

4.4. Результаты экспериментов.99

4.5. Основные выводы по главе.100

ЗАКЛЮЧЕНИЕ.102

СПИСОК ЛИТЕРАТУРЫ.104

ПРИЛОЖЕНИЕ.112

ВВЕДЕНИЕ

Актуальность проблемы.

Диагностирование дискретных устройств занимает важное место при их проектировании, производстве и эксплуатации. Несмотря на значительные теоретические и практические достижения в области технической диагностики дискретных устройств [1-8], постоянный рост их сложности требует дальнейшего исследования проблем диагностирования.

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

При построении тестов дискретное устройство, как правило, рассматривается на уровне математической модели. В настоящее время широко применяется построение тестов на основе структурной модели устройства - логической схемы. Неисправность в логической схеме является моделью неисправности в дискретном устройстве. При построении тестов выделяют класс рассматриваемых неисправностей.

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

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

Построение тестов, как правило, выполняется с применением процедуры моделирования схем [9-21]. Под моделированием понимается получение выходной реакции схемы на заданное входное воздействие. Моделирование является одним из основных средств при построении тестов для схем с памятью.

Идея построения тестов с помощью моделирования заключается в следующем [19]. На заданной входной последовательности выполняется моделирование схем с неисправностями из рассматриваемого класса. Получаемые выходные последовательности сравниваются с эталонной последовательностью, которая является реакцией исправной схемы на входную последовательность. Если некоторая выходная последовательность отличается от эталонной, то соответствующая неисправность считается обнаруженной, и она исключается из дальнейшего рассмотрения. Входные наборы, составляющие тест, могут генерироваться случайным образом либо предлагаться разработчиком схем. Для большей эффективности моделирование сочетается с регулярными методами построения тестов, которые позволяют строить тесты для труднообнаружимых неисправностей схемы (неисправностей, имеющих малую долю тестов среди всевозможных входных наборов). Сочетание регулярных методов с моделированием дает возможность эффективно строить тесты для схем большой сложности. Регулярным методам построения тестов посвящена обширная литература [2237].

При моделировании последовательностных схем на входной последовательности начальное состояние схемы может быть неизвестным, источником неизвестных значений в компонентах входных векторов могут являться неуправляемые входы схемы. Задача моделирования схемы при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния (для синхронной последовательностной схемы) является недостаточно исследованной. На практике, обычно применяется моделирование по правилам троичной логики [6,18] (троичное моделирование), которое в общем случае не дает точных результатов. Имеется ввиду, что результатом троичного моделирования на некотором выходе моделируемой схемы может быть значение х, интерпретируемое как «неизвестно 0 или 1», в то время как при моделировании соответствующих двоичных последовательностей для каждой из них на рассматриваемом выходе достигается значение 1 (значение 0). Неточность моделирования ведет к ухудшению качества тестовой последовательности, построенной на основе такого моделирования, то есть к увеличению ее длины или, при фиксированной длине тестовой последовательности, - к снижению ее полноты относительно рассматриваемого класса неисправностей. Для комбинационных схем известны методы точного троичного моделирования, но они требуют громоздких функциональных описаний схем. Для синхронных последовательностных схем специальных методов точного троичного моделирования на входных последовательностях произвольной длины не известно. Применение точных методов троичного моделирования, предложенных для комбинационных схем, в синхронных последовательностных схемах, хотя и возможно теоретически, практически приемлемо лишь для получения точных результатов на одном шаге моделирования, но не на последовательности в целом.

В настоящее время широко применяется вероятностное тестирование дискретных устройств [21,40-43]. Идея метода заключается в подаче на входы устройства случайных наборов и последующем сравнении полученного на выходе результата с эталонным значением.

При вероятностном тестировании возникает задача определения длины теста, обеспечивающего обнаружение неисправностей из рассматриваемого класса с заданной вероятностью. Оценка длины теста, как правило, выполняется с применением вероятностей обнаружения неисправностей из рассматриваемого класса [21].

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

В этом случае возникает задача обеспечения тестопригодности схемы. Одним из подходов к обеспечению тестопригодности является введение дополнительных контрольных точек в схему [2,21]. Для определения необходимых контрольных точек вычисляются управляемости и наблюдаемости внутренних полюсов схемы.

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

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

Вышеизложенное показывает, что актуальность темы определяется:

• трудоемкостью известных методов точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов;

• отсутствием практически применимых точных методов троичного моделирования синхронных последовательностных схем при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния;

• трудоемкостью известных методов точного вычисления мер тестопригодности схем.

Целью работы является

1. Разработка методов точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов, менее трудоемких, чем ранее предложенные методы.

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

3. Разработка эффективных методов точного вычисления мер тестопригодности для комбинационных схем.

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

Научную новизну полученных в работе результатов определяют:

• Метод точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов. Метод основан на представлении булевых функций, реализуемых схемой, в виде ортогональных ДНФ (ОДНФ) или ВБО-графов, являющихся компактным описанием ОДНФ.

• Методы точного троичного моделирования синхронных последовательностных схем на последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния.

Первый из предложенных методов основан на представлении функций переходов-выходов схемы в виде ОДНФ, второй - на представлении этих функций в специальном виде, где каждому состоянию схемы сопоставлена своя внутренняя переменная.

• Эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

Практическая значимость работы.

Моделирование применяется при построении тестов, при этом важными характеристиками моделирования являются скорость и точность. Чем выше скорость моделирования, тем меньше время построения тестовой последовательности. Чем точнее моделирование, тем выше качество тестов, построенных на основе моделирования.

Предложенные методы точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов являются менее трудоемкими по сравнению с ранее известными методами, так как выполняются по более простому функциональному описанию и, следовательно, позволяют повысить скорость моделирования.

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

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

Внедрение результатов.

Работа выполнялась в рамках проектов:

1. Госбюджетная тема Сибирского физико-технического института при Томском государственном университете (ТГУ), программа «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем», 1995-2000 гг., шифр «Диаконт», раздел «Разработка методик и аппаратуры исследований».

2. ФЦП «Интеграция». Раздел «Прикладная дискретная математика».

3. Министерства образования по разделу "Автоматика и телемеханика", направление - "Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники":

• 1996-1997гг. "Исследование проблемы повышения качества тестирования и контролепригодного проектирования",

• 1998-1999гг: "Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования".

Предложенные методы моделирования логических схем были реализованы в виде пакета прикладных программ в работах по межвузовской научно-технической программе «Конверсия и высокие технологии. 1997-2000 годы» (проект №95-1-21 «Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»).

Теоретические результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета: используются в курсе лекций «Диагностика дискретных устройств».

Апробация работы.

Научные результаты диссертационной работы докладывались и обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ, а также на следующих научных конференциях:

1. Третья международная научно-техническая конференция «Актуальные проблемы электронного приборостроения» . Новосибирск, 1996.

2. ШЕЕ European Test Workshop 1997. Italy, Cagliari, 1997.

3. Международная конференция «Всесибирские чтения по математике и механике. Томск, 1997.

4. Международная конференция «Сибирская конференция по исследованию операций». Новосибирск, 1998.

5. Третий международный симпозиум «Application of the Conversion Research Results for International Cooperation». Томск, 1999.

6. Третья международная конференция «Автоматизация проектирования дискретных систем». Минск, 1999.

Публикации.

По тематике диссертации опубликовано 10 печатных научных работ, в том числе: 1 статья, 5 докладов (из них 3 в рецензируемых материалах конференций) и 4 тезисов докладов в трудах всероссийских и международных конференций. Структура и объем работы.

Работа состоит из введения, четырех глав и заключения. Объем работы составляет 117 с. Список литературы включает 81 наименование. Личный вклад.

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

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

Во второй главе предлагаются: метод точного троичного моделирования комбинационной схемы на входном троичном векторе и метод точного троичного моделирования синхронной последовательностной схемы на входной троичной последовательности произвольной длины и троичном векторе начального состояния.

Методы основаны на сведении задачи вычисления значения интервального расширения булевой функции к вычислению вероятности единичного значения булевой функции при заданном распределении вероятностей значений ее аргументов. Метод моделирования комбинационной схемы применяется к булевым функциям, реализуемым схемой, представленным в виде ОДНФ. Метод моделирования синхронной схемы применяется к функциям переходов-выходов схемы (функциям комбинационного эквивалента длины один), представленным в виде ОДНФ.

Приведены результаты компьютерных экспериментов, оценивающие эффективность предлагаемого метода точного троичного моделирования путем сравнения результатов, полученных этим методом, и применяемым на практике известным методом троичного моделирования.

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

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

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

Получена формула для функции обнаружения неисправности, позволяющая совместно решать задачи вычисления наблюдаемости и вероятности обнаружения неисправностей константа 1 и константа 0.

Проведены компьютерные эксперименты, оценивающие эффективность предложенных методов.

В заключении перечисляются основные полученные в работе результаты.

14

Основные положения, выносимые на защиту.

1. Метод точного троичного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входных векторов, основанный на представлении булевых функций, реализуемых схемой, в виде ОДНФ.

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

3. Эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

4.5. Основные выводы по главе

В данной главе предлагаются методы точного вычисления мер тестопригодности (управляемости, наблюдаемости, вероятности обнаружения неисправности), основанные на ВОБ и ОДНФ представлениях функций 1(0)-управляемости - С1 (С0), наблюдаемости - В(Х), обнаружения неисправности константа 1(0) - 1)1( В{)).

1. Предложены формулы для получения в виде ОДНФ функции наблюдаемости на /-ом выходе схемы, позволяющие в несколько раз сократить число перемножаемых конъюнкций по сравнению с известной процедурой по

101 строения ОДНФ этой функции.

2. Предложен метод построения BDD-представления функции наблюдаемости полюса схемы на ее i-ом выходе, сводящийся к упрощению BDD-представления фрагмента исправной схемы, сопоставляемого этому выходу и полюсу.

3. Получена формула для функции обнаружения неисправности. Эта формула позволяет совместно решать задачи вычисления наблюдаемости, вероятности обнаружения неисправности константа 1 и константа 0.

4. Предложен ряд способов дополнительного сокращения времени вычисления вероятности обнаружения неисправности в некоторых частных случаях: при вычислении вероятности обнаружения неисправности для единственного распределения Р(Х) и при выяснении достижения этой мерой тес-топригодности пороговой величины.

5. Проведены эксперименты, подтверждающие эффективность предложенных методов построения функций В(Х) и D] (D°).

ЗАКЛЮЧЕНИЕ

В соответствии с поставленными целями исследования в диссертационной работе получены следующие результаты:

1. Разработан метод точного троичного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входных векторов. Метод основан на сведении задачи к задаче вычисления вероятности единичного значения булевой функции при заданном распределении вероятностей ее аргументов. Для реализации метода функции, реализуемые схемой, должны быть представлена в виде ОДНФ или ВШ)-графов, компактно представляющих ОДНФ.

2. Разработан метод точного троичного моделирования синхронной последовательностной схемы на входных последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния. Для реализации метода функции переходов-выходов схемы (функции системы канонических уравнений) должны быть представлена в виде ОДНФ.

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

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

103 процедура вычислений.

4. Разработаны эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

5. Предложенные в работе методы программно реализованы. Проведены эксперименты, подтверждающие работоспособность и эффективность предложенных методов.

1. Основы технической диагностики / В.В. Карибский, П.П. Пархоменко, Е.С. Согомонян, В.Ф. Халчев; Под ред. П.П. Пархоменко. М.: Энергия, 1976.-462 с.

2. Методы и средства диагностирования КМОП БИС: Учеб. пособие для вузов / С.Е. Артамонов, В.М. Кривошапко, Д.О. Левицкий и др.; Под ред.

3. B.М. Кривошапко. М.: Радио и связь, 1993. - 240 с.

4. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. -М.: Энергия, 1981. Ч. 2. - 320 с.

5. Автоматизированное проектирование цифровых устройств / Под ред.

6. C.С. Бадулина. М.: Радио и связь, 1981. - 235 с.

7. Abramovici M., Breuer М.А., Friedman A.D. Digital Systems Testing and Testable Design. New York: Computer Science Press, 1990.

8. Гольдман P.C., Чипулис В.П. Техническая диагностика цифровых устройств. М.: Энергия, 1976. - 224 с.

9. Казначеев В.И. Диагностика неисправностей цифровых автоматов. М.: Сов. радио, 1975. - 256 с.

10. Williams T.W. VLSI Testing. Slivier Science Publishers. - New York, 1986. -248 p.

11. Чжен Г., Мэннинг E., Метц Г. Диагностика отказов цифровых вычислительных систем: Пер. с англ. / Под ред. И.Б. Михайлова. М.: Мир, 1972.-232 с.

12. Гурвич Е.И., Куликовская Т.П. Метод анализа тестов цифровых устройств с помощью логического моделирования // Применение вычислительных машин для проектирования цифровых устройств. М.: Советское радио, 1968. - С. 81-98.

13. Hardie Т.М., Syhocki R.J. Design and Use of Fault Simulation for Saturn Computer Design // IEEE Trans. On Electronic Computers. 1967. - Vol. EC16, N4. P. 412-429.

14. Киносида К., Осада К., Карацу О. Логическое проектирование СБИС. -М.: Мир, 1988.-308 с.

15. Биргер А.Г., Бояршинов А.В., Гурвич Е.Т. и др. Автоматизированная система контроля и диагностики цифровых ячеек // Обмен опытом в радиопромышленности. 1978. - Вып. 4-5. - С. 40-46.

16. Биргер А.Г. Применение моделирования в автоматизированной системе построения тестов // Обмен опытом в радиопромышленности. 1978. -Вып. 4-5.-С. 97-101.

17. Seshu S., Freeman D.N. The Diagnosis of Asynchronous Sequential Switching Systems // IEEE Trans. On Electronic Computers. 1962. - Vol. EC-11, N 4. -P. 459-465.

18. Seshu S. On an Improved Diagnosis Program // IEEE Trans. On Electronic Computers. 1965. - Vol. EC-14, N 1. - P. 76-79.

19. Cheng. K.-T. Recent Advances in Sequential Test Generation // IEEE VLSI Test Symposium. 1992. - P. 241-246.

20. Breuer M.A. A Note on Three-Valued Logic Simulation // IEEE Trans, on Computers. 1972. - Vol. C-21, N 4. - P. 399-402.

21. Уткин А.А. Анализ логических сетей и техника булевых вычислений. -Минск: Наука и техника, 1979. 152 с.

22. Armstrong D.B. A Deductive Method for simulating faults in logical circuits // IEEE Trans, on Computers 1972. - Vol. C-21, N 5.

23. Bardell P., McAnney W., Savir J. Built-in Test for VLSI: Pseudo-random Techniques. New York: John Wiley & Sons, 1987. - 353 p.

24. Poage J.F. Derivation of Optimal Tests to Detect Faults in Combinational Circuits // Proc. Symp. On Mathematical Theoiy of Automata. Brooklyn: Polytechnic Press, 1963. - N 4. - P. 483-528.

25. Roth J.P. Diagnosis of Automata Failures: A Calculus and a Method // IBM

26. Journal of Research and Development. 1966. - Vol. 10, - N 4, - P. 278-291.

27. Armstrong D.B. On Finding of Nearly Minimal Set of Fault Detection Tests for Combinational Logical Nets // IEEE Trans. On Electronic Computers. 1966. -Vol. EC-15, N 1. - P. 66-73.

28. Amar V., Condulmari N. Diagnosis of Large Combinational Networks // IEEE Trans. On Electronic Computers. 1967. - Vol. EC-16, N 5. - P. 675-680.

29. Roth J.P., Bouricius W. G., Schneider P.R. Programmed Algorithm of Computer Tests to Detect and Distinguish between Failures in Logical Circuits // IEEE Trans. On Electronic Computers. 1967. - Vol. EC-16, N 5. - P. 567580.

30. Marinos P.N. Derivation on Minimal Complete Set of Test-Input Sequences Using Boolean Differences // IEEE Trans, on Computers. 1971. - Vol. C-20, Nl.-P. 25-32.

31. Chiang A.C.L., Reed I.S., Banes A.V. Path sensitization, partial Boolean difference, and automated fault diagnosis // IEEE Trans, on Computers. 1972. -Vol. C-21, N 2.

32. I. Berger, E. Kohavi. Fault Detection in Fanout-Free Combinational Networks // IEEE Trans, on Computers. 1973. - Vol. C-22, N 10. - P. 908-914.

33. Карепов C.A., Липский В.Б., Матросова А.Ю., Сергеева Л.Ф. Применение методов решения булевых уравнений в диагностике неисправностей комбинационных сетей // Тр. междунар. симпозиума «Дискретные системы». Рига: Изд-во «Зинатне», 1974. - С. 151-159.

34. Матросова А.Ю. Метод обнаружения неисправности в синхронном устройстве // Автоматика и телемеханика. 1977. - № 12. - С. 129-137.

35. Кузнецов С.С. Реализация алгоритма построения тестов для схем с памятью с использованием комбинационных моделей различной адекватности // Обмен опытом в радиопромышленности. 1978. - Вып. 45. - С. 92-97.

36. Roth P. Computer Logic. Testing and Verification. Philadelphia: Computer Science Press, 1980. - 176 p.

37. Goel P. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logical Circuits // IEEE Trans. On Electronic Computers. -1981.-Vol. C-30(3).-P. 215-222.

38. Fujiwara H., Shimono T. On the Acceleration of Test Generation Algorithms // 13th Annual Fault-Tolerant Computing Symposium. Milan, Italy. June, 1983. -P. 98-105.

39. Su S. Y., Cutler M., Wang M. Test Generation by Critical Backtracing with time Reducing Heuristics // Int. Test. Conf. Washington D.C. - 1987. - P. Ю35-1044.

40. Матросова А.Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Том. ун-та, 1990. 207 с.

41. Биргер Г., Бояршинов А.В., Винокур М.Ю. и др. Кондиция -автоматизированная система контроля и диагностирования цифровых ячеек // Электронное моделирование. 1980. - N 4. - С. 58-63.

42. Матросова А.Ю., Г.А. Реморенко. Уточнение результатов моделирования в алфавите С // Алгоритмы решения задач дискретной математики, вып. 2. Томск: Изд-во Томского ун-та, 1987. - 203 с.

43. Убар P.P. Проектирование контролепригодных дискретных систем: Учебное пособие. Таллин: Таллинский политехнический институт, 1988. - 68 с.

44. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля. Минск: Наука и техника, 1986. - 198 с.

45. Agrawal V. When to Use Random Testing // IEEE Trans. On Сотр. 1978. -Vol. C-27, № 11. - P. 1054-1055.

46. Wagner K.D., Chin C.K., McCluskey E.J. Pseudorandom Testing // IEEE

47. Trans. On Сотр. 1987. - Vol. C-36, № 3, P. 332-343.

48. Яблонский C.B. Введение в дискретную математику. М.: Наука, 1979. -272 с.

49. Eichelberger Е. В. Hazard Detection in Combinational and Sequential Switching Circuits // IBM Journal of Research and Development. 1965. - Vol. 9, N2.-P. 90-99.

50. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Элементы теории автоматов: Учебное пособие. М.: Изд-во Моск. ун-та, 1978. - 216 с.

51. Агибалов Г.П., Оранов A.M. Лекции по теории конечных автоматов: Учебное пособие. Томск: Изд-во Томск, ун-та, 1984. - 186 с.

52. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. -512 с.

53. Keim М., Becker В., Stenner В. On the (Non-)Resetability of Synchronous Sequential Circuits II 14th VLSI Test Symposium. 1996. - P. 240-245.

54. Stephenson J.E., Grason J.A Testability Measure for Register Transfer Level Digital Circuits It 6th Annual Fault-Tolerant Computing Symposium. Pittsburg, PA. June 1976. P. 101-107.

55. Grason J. TMEAS, A Testability Measurement Program // 16th Design Automation Conference. San Diego, CA. June, 1979. P. 156-161.

56. Goldstein L.H. Controllability/Observability Analysis of Digital Circuits // IEEE Trans. Circuits Systems. 1979. - CAS-26(9). - P. 685-693.

57. Goldstein L.H., Thigpen E.L. SCOAP: Sandia Controllability/Observability Analysis Program // 17th АСМЛЕЕЕ Design Automation Conference. Minneapolis, MN. June, 1980. P. 190-196.

58. Ratiu I.M., Sangiovanni-Vincentelli A., Pederson D.O. VICTOR: A Fast VLSI Testability Analysis Program // 1982 International Test Conference. Philadelphia, PA. November, 1982. P. 397-401.

59. Jain S. K., Agrawal V. D. Statistical Fault Analysis // IEEE Design Test Сотр.- 1985.-Vol. 2, № 1. P. 38-44.

60. Simeu E., Puissochet A., Rainard J.L., Tagant A.M., Poize M. A New Tool for Random Testability Evaluation Using Simulation and Formal Proof // IEEE VLSI Test Symposium. 1992. - P. 321-326.

61. Seth S.C., Pan L., Agrawal V.D. PREDICT-Probabilistic Estimation of Digital Circuits Testability // 15th Annual Fault-Tolerant Computing Symposium. Ann Arbor, MI. June, 1985. P. 220-225.

62. Brglez F., Pwnall P., Hum R. Application of Testability Analysis: from ATPG to Critical Delay Path Tracing // Proceedings of IEEE International Test Conference. Philadelphia, PA. October, 1984. P. 705-712.

63. Savir J., Ditlow G.S., Bardell P.H. Random Pattern Testability // IEEE Trans. On Сотр. 1984. - Vol. C-33, № 1. - P. 79-90.

64. Savir J. Improved Cutting Algorithm // IBM Journal of Research and Development. 1990. - V. 34, № 2/3. - P. 49-75.

65. Markowsky G. Bounding Signal Probability in Combinational Circuits // IEEE Transactions on Computers. 1987. - V. C-36, № 10. - P. 1247-1251.

66. Krishnamurthy В., Tollis I. Improved Techniques for Estimating Signal Probabilities // IEEE Trans. On Computers. 1989. - V. 38(7). - P. 1041-1045.

67. Wunderlich H.J. PROTEST: A Tool for Probabilistic Testability Analysis // Proc. Of the 22nd Design Automation Conf. 1985. - P. 204-211.

68. Евтушенко H.B., Матросова А.Ю. О вероятностном подходе к вычислению оценок управляемости и наблюдаемости узла дискретного устройства // Автоматика и телемеханика. 1993. - № 11. - С. 152-160.

69. Matrosova A., Bochun Т. Verification of the Test Quality // Baltic Electronics Conference. Tallinn Technical University. Tallinn. 1996.

70. Krieger R., Becker В., Okrnen C. OBDD-based Optimization of Input Probabilities for Weighted Random Pattern Generation // Fault Tolerant Computing Conference. 1995. - P. 120 - 129.

71. Bryant R.E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Trans, on Сотр. 1986. - Vol. C-35, № 8. - P. 677-691.

72. A. Matrosova, O. Golubeva, S. Tsurikov. On Correction of the Results of a Ternary Simulation // Compendium of Papers of IEEE European Test Workshop 1997. Italy. Cagliari. May 28-30 1997. 2 p.

73. Мерекин Ю.В. Решение задач вероятностного расчета однотактных схем методом ортогонализации // Вычислительные системы. 1963. - Вып. 5. -С. 10-21.

74. Голубева О.И. Троичное моделирование синхронных последовательностных схем // Математическое моделирование. Кибернетика. Информатика. Томск: Изд-во ТГУ, 1999. - С. 53-59.

75. Матросова А.Ю. О вероятностном моделировании дискретных устройств // Автоматика и телемеханика. 1995. - С. 156-164.

76. Brglez F., Bryan D., Kozminski К. Combinational Profiles of Sequential Benchmark Circuits // Proc. International Symposium on Circuits and Systems.-1989. P. 1929-1934.

77. Радюк JI.E., Терпугов А.Ф. Теория вероятностей и случайных процессов: Учебное пособие. Томск: Изд-во ТГУ, 1988. - 174 с.•siой -оо \ Щ, Ло <1. ЧЛ 'У

78. УТВЕРЖДАЮ» Проректор по учебной работе ТГУпрофе<?со|Ц^^7~^ Ревушкин А. С.2S~ » мая 2000 г.1. АКТо внедрении результатов диссертации Голубевой О.И. в учебный процесс ТГУ

79. Декан факультете прикладной математики и кибернетики ТГУпрофессор/ШГорцев A.M.

80. Зав. кафедрой программирования ФПМК, профессор /^Uo^h-^ Матросова А.Ю.1. УТВЕРЖДАЮ»сфти при тгу1. Колесник А.Г.1. ЩЦ—*//« » мая 2000 г.-1. СПРАВКА

81. Научный руководитель раздела, Евтушенко Н.В.1. Заведующий отделом 102профессор1. Семенов В.С.профессор15 » мая 2000 г.1. СПРАВКА