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

АКАДЕЮТ НАУК УКРАИНЫ

На правах рухонгти УДК 68Т.518.5: 68!.326.Об

ФИЛИМОНОВ Сергой Николаевич

МВТОф К СРЕДСТВА ПСЕЕДОСЛУЧШЮГО ТЕСТИРОВАНИЯ ПРОГР1ШВО УПРАВЛЯВШИ УСТРОЙСТВ

05.t3.05 - элементы и устройства вычислительно!!

техники и систем управления 05.13.13 - нмисхитсльше мзтяы, кскплэксы,

СПСТЗМ2 И С9ТИ

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

Киев 1993

Диссертация является рукописью Работа выполнена в Техническом Университете Молдовы

ОЦщщадышэ ошюнзнта:

доктор технических наук, профессор Байда Н. П.

доктор технических наук» Коросталь Ю. Ы.

доктор технических наук, профессор Романкевич А. Ы.

Ведущая организевдя: Институт 1т^х5лем регистрации шформацаи Академии наук Украины

Защита состоится 1993 г. в /4 часов

во заседании спеццв лкзированаслЧ) Совета Д 016.61.01 при Институте проблем моделирования в энергетике Академии наук Украины по адресу: 262660, КИев-164, ул. Генерала Наумова, 16.

С диссертацией можно ознакомиться в библиотеке Института проблем моделирования в энергетике АН. Украины.

Автореферат разослан " Э " Ио?*ь)у9 1993 г.

УчешА секретарь специализированного Совета,

кандидат технических наук С^—г____ Семагина Э. П.

ОБЩАЯ ХАРАКТЕРИСТИКА ДЙССЕРВДИОШЮИ РАБОТЫ

Актуальность проблецы. Широкое использование программно управляв!^ устройств (ПУУ) практически со всех сферах человеческой деятельности остро ставит проблему обеспечения их надежного функционирования. Отказы ПУУ, являющихся упрзвлявдим ядром многих сложных систем и движущихся в пространстве объектов, могут приводить к тякелнм последствиям. Всв это определяет важность и необходимость обеспечения высокого качество и достоверности их контроля на всех этппвх их гаэшнного цикла.

К сожалению развитие теории, методов и средств контроля ПУУ отстает от требований практики. Это обусловлено быстрым ростом функциональна! и структурной сложности ПУУ, степени янтегргц'л:-! поэлементной базы, усложнением технологических процессов производства, что влечет рост стоимости коитрольно-иыштптельпогс оборудования, увеличение трудоемкости и сюпсоние достоверное^ процессов контроля.

В последнее время приобретают все большее распространение и пользуются все болида-; е.{иканием специалистов я исследователей стохастические (псевдослучайное) изгоди и средства контроля цифровых устройств, отлтчакауюсл простотой технической реализации, сравнительно наэкоЗ трудоемкостью процесса синтеза тестгакх воздействий ) и тастоЕих программ (ТП), ■ относительно ш:акой стоимостью реикизукщкх такие метода средств контроля.

Псевдослучайные процессы, обладая осношш;.-зт хзр-актеряст:п:.:'':а случай* шх ■ ь то яе гремя к?зот ряд вгяшх преимупэгта, ероял которых:

- зоспро;.звсдимость, что, позволяет попользовать для п'кигпз реакция рагулярлле метода, обладая^© большой рзэреетгечк способностью;

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

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

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

Выявилась необходимость проведения строгого сравнительного

анализа детерминированных и стохастических методов контроля с целью опрадэлешя условий их наиболее эффективного пршешпия, а •Генка необходимость разработки формальных методов адаптация пар^етрс; ксевдо^чайвых процессов к особенностям конкретного тестеру« :».„ .-о устройства при генерации ТВ и ТП, разработки математических ветодэа щгализа пороадащих свойств используешх процессов, разработки алгоритмов функционирования, аппаратного, ♦ црогрвкзмого, методического и »»урологического обеспечения средств псевдослучайного тестировании программно управляешь устройств.

Необходимость» решения нсречисдашщх зада5! для оби си г яин высокого уровня надохгасти производимых и эксплуатируемых программно управляемых усгройств вычислительной техники и систем управления определяется актуальность диссертационной работы.

Объемен» пссяедсвшш явлазтеи тестовые воздействия и программы, связные управляете стохастические ¡¡роцзеен их генерация. а такие сродства псевдослучайного тестирования прогршлмно управляемых устройств.

Цель» диссертационной работы является ронение актуальной яроблеш автоиатазацам, нокмения аффеитямюста и достс-верности цроцъссое псевдослучайного таоырсв&шы программно управляемых устройств гвдчзяатвлыгоВ т&хинка и систем управлении.

Задачи исследования. Достпаеше доставленной доли требует решения следующих взаимосвязанных задач:

- исследование с едашх теоретических и методологических позиций условий, наиболее эффективного применения стохастических методов и средств для решзняя задач контроля сложных ЦЕЯрових, в том числе программно управляешь устройств;

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

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

- разработка методов анализа порождающих свойств связных стохастических процессов для обеспечения целенаправленного управл'чге.ч ттр?мо! рнда ттрируии-их алгортмс в;

,•-- разработка методики построения моделей слязнь" стохастических процессов, обеспечиванию« Зоряализэциг* -?зо£г.однмой информация о тестируемом устройства и фор»алК5ое О^пОрсКШаИПе юдслзй в »шчэричмя ф/ш'ционироваим автоматизирован»«« систем псевдослучайного тестирования;

- разработка устройств, програшиого, католического и мэтро-яогачепкэго обеспечения систем, реваввдх проблему автоматизации я товшания эффективности процесса псавдослучайног-р тестирован»«! прогршию управляема устройств Еннйсдапеяыгой ютпкасп п систем упрталэшя.

Метода нсследоввииЯ основаны на применения математического аппарата тбори игр, матомаппоскоЯ лингеестиш , матричного аиажзз, теории вероятностей и информации * о также» теории и ттодоп технической дяагнсстини.

Разработан новый аналитический ^втод псследовз;::'.- порождактас свойств связ!!ж: стохастических процессов, основанный на исчисления яияриц пал «ягефянн о операциями специального вида.

Научная яевмзяа дйссвртацяогоюй работы заключается в теоретическом обосновашэд с единых мзгодсмюгячвских псзшщЛ уаяопяй наиболее целесообразного и эффективного щмнвнетя стохастических катодов для резения задач контроля слошшх шаровых устройств, разрасютг.о на основе предложенной концепции моте •>':*; ^р.:алкяоцик этзформашм о тестируемом устройстве и ?о отображения в структуру и гтерпкотрь!' алгоритмов, г-:лзрирукздк: тестовые программы, методов иодевгрованпк и рнзлиза порождения*; свойств связиих управляй^ стохастяческнх процессов, ислаяьзуемнх в а&?сматну|фовагашх системах псевдослучайного тестировать.

Автор загниет:

- концепции ксзвдослучайного тестирования прогрзмшга упраш;я •эякх устройств, заклотамцукюя в кегю-льзовании доступной ю>форка!1ин о конкрзтном 'тестируемом устройстве, отображении ее формальным путем в структуру и параметры связных стохастических процессов, обеспечивая их адаптацию к особенностям тестируемого устройства, и реаения. на этой основе актуальных проблем автоматизации процесса синтеза тестовых воздействий и программ, повышения эффективности а дбстоверяости контроля программно управляемых устройств;

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

применения;

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

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

- метод определения погрешностей вероятностных оценок качества тестовых программ и достоверности процесса псевдослучайного »еслироввшш;

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

Свльь с госудЕрственшсш врограьашш и 1ШР. Результаты, изложишше в диссертации, получены ь процессе исследований и разработок, ьнполнешшх

в соответствии с координационным плане« ffiip Ali ССОР по проблею 1.(2.8, раздал 1.12.8.3, тема "Автоматизированные Ш5сте;.ы проектирования контроля и диагностики мнгфопроцессоркой техники", & ГР 0!86Ö022457;

в р&мк&х целевой коютюксноЯ программа к ш основвшш приказа J! 536 MB и ООО СССР о? 20.05.81 г. по -теме "Автоматизированные системы 'проектирования, контроля и оптимизации технологических процессов и технических объектов"5 % ГР 81035579;

на основании постановлений Правительство СССР 317-126 от 03.04.83 г. и ü 30 от 08.02.84 г. для контроля специализированных процессоров;

на основании постановления Правительства СССР .в 355 от 23.аз.87 г. для тестирования управлякщих процессоров ультразвуковых средств неразрущащего контроля;

в рамках НИР: "Исследование и разработка ггрограданого обеспе-чо ни я автоматизированных систем контроля электронной аппаратуры" № ГР 81013731, "Система (автоматизированного контроля и диагностики электронны? блоков ультразвуковых средств нэразрушаицего контроля" № IT 01060017617, "Диагностика - 90" ¡»г. » У 54443;

в рамках ОКР "Автомат", рог. # У 81337.

Образцы систем демонстрировались на ВДНХ СССР (удостоверение £ 34636) и на международной выставке "Связь - 86".

Практическая ценность диссертационной работы.

На основ* гозультатпв исследований,, рнорабоодшш: методов м^дилиргчтшч и ошитаа определены шредоктимшо нтгрпшшния

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

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

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

Реализация результатов диссертационной работы.

Основные результаты научных исследовагий и разработок реализованы в виде ряда устройств, программной подсистемы автоматизации процесса синтеза тестовых программ - ПАСГП, алгоритмов функционирования, программного, методического и метрологического обеспечения автоматизированных систем псевдослучайного тестирзва ния ТЕСТ-7901, ТЕСТ-8103, ЛПИГВИСТ-802, ЛШГВИСТг803, внедрены на ряде номшленных предприятий.

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

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

Апробация работы. Основные .научные результаты, положения и выводы диссертационной работы были представлены и одобрекн на Международном семинаре по проблеме реализации комплексной программы научно-технйческого прогресса стран - членов СЭВ до 2000 года (г. Кишинев 1987), Международной конференции по автоматиаировяяшм техническим системам (г.г. Евпатория, Москва 1990), 6-ом Международной симпозиуме "Системы, Моделирование, Управление'' (3!'0-6) (г. Закопане 1990), 18-ом конгрессе Румыно-Американской Академии науки и искусства (г. Кишинев 1993), Всесоюзной НТК "ИИС-81" (г. Львов 1981), на семинаре "Функциональна контроль изделий микроэлектроники" (г. Ленинград 1982), Республиканской НТК "Структурные метода повышения точности средств и систем автоматизации

экспериментальных исследований" (г. Киев 1989), на Б-й Всесоюзной НТК "Проблем метрологического обеспечения систем обработки измерительной ;'< 1юрмацк»Г (г.г. Суздаль, Москва 1984), Б-ом Всесоюзном симпозиуме vo модульным ИБО (г. Кишинев 1985), 7-й Всесоюзной НТК "ШО-87" (г. Ташкент 1987), 11-й Всесоюзной НТК "йетрологаческое обеспечение ШС и АСУ ИГ (г. Львов 1988), на XXX Всесоюзной ¡жоде-сеыетарв им. Ы. И. Гаврилова (г. Кишинев 1988), на XI 1ЕГК я11роблеш разработки измерительных приборов со встроенным интеллектом и перпективы их развития" (г. Каунас 1983), I Всесоюзной школе-семинаре "Разработка и внздроние в народах-* хозяйство персональных ЭВМ" (г. Минск 1988), XXIII Всесоюзной школе-семинаре по автоматизации научных исследований (г. Кш:шев 1989), Республиканском соминаре "Техническая диагностика и эксплуатация вычислит"»лышх управляющих систем" (г. Киев 1989), Республиканском семинаре "Вопросы разработки вычислительной техники" (г. Кишинев 5989), Республиканской НТК "Проблемы автоматизации . контроля электронных устройств" (г. Киев 1990), Всесоюзной !"."К "Мэделирова-шю - 91" (г. Кишинев 1991).

По теме диссертации оаубяшмвано 70 научках работ, в том числе б авторских свидетельств СССР im изобретения, статьи в журналах "Электронное моделирование", "Автоматика и телемеханика", "Автоматика и вычислительная техника", "Приборы и системы управления", "Управляйте системы и машины", "Приборостроение", "Известия Академии наук Молдовы", "Измерительная техника", "Техника средств связи", "Намерения, контроль, автоматизация", "Вопросы радиоэлектроники", "Вопросы специальной радиоэлектроники", "Fuazy System & A. I. Magaain", "Computer Sciences of Moldova".

Объем и структура доссертвцви. Диссертация содеряит 242 страницы основного текста, состоит из введения, семи глав, заключения списка использованной литературы из 222 наименований, а также iipiiJioüieiQiH, ' содержащего» информацию о внедрении результатов диссертационной риботн в промышленности. Работа иллюстрирована 26 рисунками.

Аьюр внршкает искреннюю благодарность Члену-корреспонденту АН Ыолдоы», заслуженному деятелю науки, д. т. н., профессору И. Ф. Юшсторину и д. т. и., профессору В. И. Борщевичу зе кон-гтрук'пншую критику результатов научных нсслндовшшй, о также за HOAbf!|i*tcy, мтянну» ими ь процессе сформлония работы.

3 КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Введение содеркит обоснование ^чмн диссертац ■-<ной работы, формулировка цели и задач исследований, изложение оемвнмх научны* положений, выносимых на защиту, а тзкжо данные о »губл-кащгах. и апробации основных научных результатов.

Первая глава диссертационной работы посвящен:: анализу современного состояния »методов и . средств псевдослучайного тестирования программно управляете устройств. Приведи! обзор математических моделей, используешх. для решения задачи автоматизации процесса синто за тестовых воздействий и программ, а такие И35зестш1х автоматизированных систем, ревлизущих стохастические методы тестирования.

Современные средства контроля ПУУ представляют собой сложные и громоздкие .автоматизированные системы, вилючаювддв упрввлящю» ЭРЧ и вспомогательные процессоры, значителькые объему уникальной аппаратуры, слойгное програ?®шое обеспечение.

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

Вдо одной вакной поблемой является автоматизация процессе синтеза тестовых программ. Большая фуяидаозальиз» сяозшость ГОУ как объектов контроля и наличие большого числа резнообрэзинх физических дэфектов, не сводимых к традиционно рассматрЕЕяемому классу константных логических, приводят к неадекватности ях кодолированяя дая целей автоматвзировашюго синтеза т&стовнх программ дэтэрмиюфсяпшяв! методами.

Пиэтому тестовая прогржмы .для контроля правяльности Функционирования ¡Г/У дорабатшзаэтея, а часто и составляется! вручную специалистами - разработчиками, требуют больших затрат времена и квалифицированного труда,

'■р5£)лема разработки методов синтеза тестовых программ созда-талжи автоматизированных систем не рассматривались и существовала как бы отдельно, в связи с чем практически не уделялось внимания разработке методического обеспечения создаваемых систем. Довольно често но этой причине возможности дорогостоящих систем, в том ч-дсле и закупаемых за рубежом, используются далеко не псчьностыо.

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

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

Особенностью решаемых задач контроля является с одной стороны большая размерность множеств событий, признаков, значений параметров, характертазуиадх сложный объект контроля (ОН), а с другой,-ограниченный ресурс, который в состоянии затратить "решатель задачи" (РЗ) па рассмотрение этих множеств и поиск решения.

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

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

Пусть имеется шокертво I) всевозможных решений (пространство выбора), в котором содержатся подавожэство 4)а решений, удовлетворявшим условиям задачи: с ш. Для решения вадачи двтерш-иироватшм способом РЗ выбкрает из етожества Я1 последовательность ж{ элементов, длина |х 41 = которой ограничена его ресурсом, точнее той частью ресурса, которая выделяется для реше-шя подзадачи выбора. Если в выбранной РЗ последовательности х{ окажется хотя Си один элемент, принадлежагшй подмнокеству 0)я, вадача считаотоя решенной, в противном случьо -- нерешенной.

Всевоэможше последовательности х{ элементов из 0), которые

РЗ может выбрать, будем называть его стратегиями. Стратегиями у противоположной стороны - объективной действительности - являются всевозможные варианты расположения подаюкоства (Us в множоствэ ÖJ. Каждую стратегию объективной действительности можно рассматривать как инъективноэ отображение вида у^: Шэ Ш. В сформулированних условиях имеет место игра

IT = < Я, УГ, !Н > , U )

где Ж = (х{> - множество стратега"! РЗ;

'й = {у^} - шюшство стратегий объективной действительности; Ш = ) - матрица выигрышей, в которой - выигрыш F3

при выборе им стратегии ду и реализации стратегии у^ объективней действительности, опроделпеглй выражением I 1, при X п V 0,

П. < (<-.)

lJ 10, при Xt п Ws= 0.

Обозначим И = - мощность пространства выбора, N = ¡4!sf

- мощность множества удовлетворительных решений. Тогда мощность

N

мнояеетва стратегий РЗ равна = N , а мощность множества

стратегий объективной действительности равна = Cfi , где Cf,

- биноминальный коэффициент. .

Выражение (1) задает конечную антагонистическую матричную

игру с чистыми стратегиями, в которой гараитировашшй выигрыш PS

определяется выражением

а = max min h,. (3)

t j lJ

В раяоте показано, что, для рассматриваемой игры, ит неравенства N,, $ N - Ns следует а = 0, а для обеспечения а = 1 должно выполняться неравенство Nr > N - Ns.

Это означает, что при детерминированном выборе стратегий РЗ, решение задачи гарантировано лишь в.случае, когда ресурс больше разницы между , мощностью пространства выбора и.мощностью множества искомых решений.- В случае, когда NB $ N - 1Г, не существует детерминированных стратегий РЗ, гарантирующих решение задачи.

Рассмотрим смешанное расширение исходной матричной игры (I), которое представим в следующем виде

' Ис=< IPx,tPv, Ис>, (I)

где 1РХ = С Рф(^) ) - множество дискретных распределений- вероятно-1

стей вида РфШ = ГРф(х()], <р =.1, |PJ, S P^ix,) = 1;

С^^ СРф(И?)> - множество выроадешшх дискретных разпроделе-1шй ьероятностей вида Р^Сй1) = ГРф(У^)Ь таких, что Рф(У^) = 1

при и Рж(У;) = 0 при Ф * Ф = 1.|РУЬ 3 = причем ¡Г-, | = ;

ОС - г&траца оредгшх Быигрышев РЗ, элемент которой определяется по формуле ЬЧр^. Рф) = 2] Е

Вырозденность стратегий объективной действительности обусловлена детерминизмом конкретной ситуации, в которой решается ведача,

Миокеетва и 1Ру могут быть представлены в виде матрицу размора Ф * Нв, где Ф = |РХ|, и матрица (К,, размера Ф « ф, где © - = |КГ|,

Матрица [И* может бить получена как произведение матриц вида

И' = В^* 1Н * (5)

где И* - транспонированная матрица йу.

Для смешанного расширения игры в еоотвествии с теоремой фон Неймана существует оптимальная стратегия РЗ, определяемая из выражения

р = иах шШ Ь'(Р(0,Г,ь), (6)

а кроме того, если выполняется условие ) /01, то

справедливо неравенство р > 0. В отличии от игры с чистыми стратегиями, игра со смешанными стратегий)® имеет гарантированные положителышо выигрыши для любых. положительных объемов ресурса.

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

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

Напримзр, задача поиска в множестве 1М воздействий такого воздействия к,, , которое обнарушвает неисправность е из заданного некоторым образом множества £ шксправностей ОК, имеет детерм 1'лиромнное решение, если в множестве В? содержится непустое подмножество й_ воздействий, обнвруяиьахлдих неисправность е и выполняется условие N.. > N - IIе , где ¡^ - число воздействий, которое монет быть проввроно на принадлакность к ва допустимое вр«мп, N = '|М| - мощность пространства выбора, = |1Не| - мощность мноиестпа удовлетворительных решений задачи.

При стохастическом методе решения задачи, выбор элементов из а бурит производиться случайно в соотвнтс ,'вии с некоторым

распределением вероятностей на миокетьо стратегий К>,

Показано, что , при равномерном распределении г /оя'пюстей на множестве стратеги!! РЗ, гарантированный шгигрнш совпадает по величине с гарантированным значением вероятности с-•-оружрння неисправности

г N лК

Р(е.Н_) = 1 - |1 - — 1 (7)

I 11 >

Задав некоторый приемлемый уровень Я надетости успеха, тглгай, что Р(в ,НИ) ^ и использовав разложение натурального логарифма в степенной ряд с учетом (Г1е / Н) << 1, получим выражение для оценю? необходимого ресурса

Н 1

> — 1п--. (8)

* К 1 -К е

Для детерминированного метода трэбуемгй тесу." определяется разностью И - Н , которая бистро растет с ростом размерности решпемой задачи. Для стохастического ко метода требуемой ресурс определяется отношением И / К , которое растет заметно медленнее разности при одновременном росте мощности пространства выбора й и мощностл множества удовлетворительных реШЭНИЙ задачи.

•' Рассмотрена задача выбора способа сжатия рзакций тестируемого устройства, обеспечивающего наибольшую достояло::".. ремсшл о его состоянии, принимаемого в результате анализа' снятых рескш*Я.

Процесс скатил реакций в сигнатуры Можно представить как процесс реализации сюръективного отображения Т множества Ш всевозможных реакций нн множество сигнатур, » |?л|).

Определил множество стратегий следующим образок :

Ж = { 1: Г (г) е г <? Г }, |>1[ = . (9)

У= {<г0.г„> : го>гн - К, г0.^гн} (10)

гдо Ж .- множество отображений из Ш на Я; "И - множество пар реакций; го- реакция исправного устройства; гн- реакция неис-ьранногс устройства.

3 этой игре РЗ стремится выбрать такое отображение £{, чтобы по возможности всегда иметь различие сигнатур исправного и неиенрпчзого устройства, т.е. Г{(го) / Г{(гн). В этом случае функция выигрыша будет определятся матрицей

И = I Иту|. (11) '

где й - индикаторная функция события обнаружения неисправности:

Г 1 , при Г (г ) Ф f(r) , h - < ° " (12) ** [ О , при f(ro) = f(rH) .

Поскольку всегда выполняется ]К| >> |S|, гарантированного детерминированного решения не существует.

Для смешанного расширения игры, при равномерном распределении вероятностей, гарантированный выигрыш равен

h'OPo-V = «V и " = 1 ~ 15Г'> 03)' 1'дз 1Ро - вектор строка, состоящая из элементов, кавдый из которых равен величине р(Г{) = = |S|~!RI.

Если сигнатура имеет вид двоичного n-разрядного вектора,

то гарантирог-нная вероятность различения сигнатур исправного и

-п

неисправного устройства равна p[f(r0) * f(rM)] = I - 2 , что численно совпадает с оценкой этого параметра для n-рэзрядных сигнату-раторов на основе сдвиговых регистров с линейной обратной связью.

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

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

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

Предложенная концепция включает следующие положения:

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

еадар контроля;

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

3) управление процессом генерации тестовых воздействий и программ осуществляется на основе доступной формализованной информации о конкретном тестируемом устройстве;

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

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

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

Hw - {0( = «С, р. Р(р»>, (14)

элемента которых упорядочены в соответствии с синтаксической схемой (С, зависяцзй от количества и назначения входов тестируемого устроСстзс, а кавдый текст рассматривается пек результат отображения | : ^ А в алфавит А множества шзпцкЯ

синтаксической схемы С = < !р,зе >, где г? - отаоиение порядка iia позициях из ф; р - {<Я*я>} - n-арнсе отнопение предяествоезния (n.= |W| + 1), И' - подмножество, поровдегада. элементов воздействия, от которых зависит элемент w (W*s W); на элементах отноаэния задел набор 1Р(р) = { p(w{/W*) ') вероятностных мэр, в общем случае условных, удовлетворяющих ограничению ' .

а

2р (w/W*)' =1. (15)

• ' w га 1

г > Г f

Здесь w рассматривается как переменная, принимаизпя злтш-

ния в алфавите Я = Са/,а2.......ап), который определяется еидои,

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

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

Грщг.'йтька, как математический объект, является комбинаторной полутуэй' ::ой системой яолнгвнного типа, правила подстановки которой являются разрешительнами, т.е. задают некоторое исчисление и обладай?, в общем случае, рекурсией. Это позволяет получать большое разнообразие текстов путем применения незначительного числа правил подстановки.

Стохастическая грамматика, в общем случае, имеет вид :

(Б = <У, Я, Р(Щ), 5>, (16)

где V = ¥т о множество теряшальшх \УГ и нетерминальных символов; Я = {г{} - множество правил подстановки, кмощих вид г{: а^ « р^, левая часть правила, правая часть правила, « £/*; Р(3?)~ набор вероятностных мер на множестве И; Б - начальный (стартовый) символ - аксиома грашатики ©.

Правила используемых в модели грамматик юле»? следущий вид: г{ : =» 17а{ + ;ег', где £ - левый контекст; V - правый

контекст; 5,1»« V*; А, е И^Б; 7,6 е V*, 171-- 0.

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

Предложена ' и исследована ыатематичоская модель тестовой ! программы, опирающаяся на понятиь функционально полной программы (5Ш), сформулированное В. А. Гулявши. Исследованы основные свойства <ОТП определяющие ее способность обнаруживать функциональные неисправности программно управляемого устройства.

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

Множаство функциональных неисправноетой определяется на основе сформулированного В. И. Борщевичом представления функции НУ,У кпк отображошш множества допустоммх для него операндов в М.юкегтмо <~го рняульч'чч-ев.

! <

.Шредлохэна и исследована математическая мод*- связного • стохаст!Г1Рского процесса генерации тестов'« программ, Л'дсгавляю-щих собой конкатенацию ФПП, обладаниях. заданными свойствами.

Модель представляет собой стохастический регулярны? ис очник

I = <Г(1). <р« (ОТ)®, РШ*,,^)]». (1Т)

где Г(1) - порождающий размеченный мультигрсф

Г(Г) = <№, Б, ¡Р№)>, (18)

каггдой верпмк'э « « ?! которого соответствует множество состояний одного или нескольких программно доступных функциональных узлов ПУУ, а дугам й ^ 1) соответствует отногсение связности мевду иночеством состояний, причем на подмножестве дуг графа задан нчо'ор-!Р(В) распределений вероятностей;

9 - функция, сопоставляющая дугам графа цепочки символов из алфавита К, соответствующего множеству команд ПУУ, итерация алфавита.

,1гк) - множество путей в грсфэ начинающихся в выделенной начальной вершине . ?? и заканчивающихся в ваделенноЯ коночной вершке «?к;

¡РЕ2(7;Н,??К)] -- набор вероятностных зр, распространенных с дуг графа на множество пут°й.

Вероятностные меры на подмножествах дуг графа задаются в гиде

дискретных распределений вероятностей .Г , где и = I,(|Я|-1), воеггаяно выропденных.

Каждое распре деление врролтнеотей Р„= "задано на

подмножестве Ъ = {(1 } дуг, внходяиих из вэргины V , л удовлетворяет условию £ о(<1 ,) --- 1, где .1 - 1, ¡0

Источник вида (г.ор-ождаэт сшгасткческлй язкк

И(1) = О, : Г 3 аИК1# « : ф(^). = 1,]) (19)

дня которого вероятность реализации цепочки команд равна вероятности прохождения по соответствующему пути zHKJ граф? Г(1) и определяется выражением

= Р<Ь> П "р(^). (20)

где й есть 1-ая дуга из подмножества параллельных дуг," приипдяэкадах пути ZИKj^

Множество ©и состояний, соответствующих вершине пи графа,

определяется выражением

®u = {<ytj W : (7 = 1+ 1>A(J = 4». <21>

где eu с 0, u=1,|b'|, v,l = 1, |K|, 3,q<al.

Выделенной начальной вершине wH графа соответствует множество состояний, принимаемых ЮТ с вне-шей шины, а выделенной конечной ■вершине wK - мнокество состояний, выдаваемых из функциональных узлов ГШ на его внешнюю шину.

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

Множество Z(wH, wx) путей пороадащэго графа стохастического источника включает только те пути, прохокдешю какдого из которых с сопутствувдей конкатенацией меток па дугах, влечет пороэдэ-ипб цепочки команд, являющейся функционально полной программой.

Набор Р(Б) дискретных распределений вероятностей Р , задаваемых на подмножествах, выходящих из одной вершины w графа, pTpasitDeT прагматические аспекта процесса контроля и определяет стиль стохастического языка 0.(1), порождаемого источником.

В качество примера приведены фрагменты пороадаэдего графе, построенного для системы команд микропроцессора Intel 80386.

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

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

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

и-

представителей каких классов последовательностей из алиментов воздействия способен нороадать roiispa'/cp за заданное число г-я тор, его работы;

поровдавтея ли генератором некоторая кониреть • поело дою тельность элементов воздействия или £Ш с иоьест;шми , -,ойс :'вагд.:;

какова экстремальные значения вероятности поровде-ния последовательностей или за заданное число тактов;

каково количество различающихся последовательностей .ля <ШП, пороядаеких генератором за заданное число trhtoi:.

Для решет«! этой проблемы разработан матрматьчеекий метод, основанный на ?!счисленш матриц над алгебра!.».»! <■■ операциям1« елецкэлького вида.

Область значений функции q> стохастического ис-гочиикн представим п видь алфавите S = (gt : fgt - <р (d{)lMgt <? й'*)), где 1 = !.|D|, G с 3<й.

Стохастический источник (17) преобразуем к следу кхцкьч' вич,у

I = <Г(1), f * (f, Z('VS1 ">х), 1Р!й(«„ v,, )!. (22)

где Г(1) - пороадакшй граф вида (!3).

Представим неточнее; (22) в виде пара .кнадратьих w.гриц корядко |«|. Порвал матрица, которую будем ¡¡.'.«нвать "¿«трицн?. регулярна вгарааений,. имеет вид

- 1^3. <га>

где S'. . - регулярное Енраяение вада (S{, = »£ , !.J -- 1. •

Yi ■■' знак операции сумям, задшшсХ mi гаолястве» рогулиргно выражений, в - регулярное вкражбнкв, соотиетс-нукчео собю-н* порождения источником символа g « i(d ), к « v, d «• I1.,,

1 t °.t u ~n u t,»

D. - шокес-1-йо наралелышх дуг порикцвк»:--5го грс^и, ир

вертинн wt в napiiK'v wf n -- ¡.¡i>tij.

Причем 0« где 0 - регулярное eppavnnte, .'^угк.усщг« •

i4t-o пустому множеству, опта мнскество П{ ^ пусто, и --- е, т,пм

е - единичное регулярное вираже пне, если g(j = е, где е -- цепочка

со свойством единицы относительно конкатенации. .

Вторая матрица, которую будем называть матрицей вероятностей, имеет вид

VP>-= lP-A)

¡■во }Г- - (р,, .. .рц. . • .ри. ) - вектор вероягиоотг-tt ЛЯ !,!НС»ТСГПЭ

гнраллелышх дуг ViJ, ш=

Обозначим гп - множество путей в графе Г(1) стохастического регулярного источника, имеющих длину п, - множество путей, ведущих из вершины графа в вершину ч¡ .

На множестве матриц вида (23) зададим операцию конкатенации матриц регулярных выражений

Р^й • = ИЗ^Н. (25)

где 3{1 = £ (®»и - сумма конкатенация регулярных выражений.

V

Операция (25) ассоциативна в силу ассоциативности операции конкатенации регулярных выражений. Это дает возможность обозначить п-кратную конкатенацию матрицу (Ир самой на себя в виде (0!р)п.

Характеристической матрицей порождающего графа для символа е д назовем матрицу вида

= (26) где Ьи = 1 при еи е Г(В^) и = О при « ИБ^).

Па множестве характеристических матриц зададим операцию к*.;нгьюнкцап матриц

где II * * * = V (Ь* А IV'.), 7 и А обозначение логических опера-

I»

цнй дизъюнкции и конъюнкции соответственно, определенных не множестве элементов характеристической матрицы, принимающих значения из множества CO.1I.

Операция конъюнкции характеристических матриц ассоциативна, но не коммутативна.

На множестве; значений вероятностей реализации событий зададим операцию вычисления минимума следующим образом

ш!л (р,.р2). если р, * 0 и рг * О;

р,, если р2 = 0;

Мр;>р2)

(28)

р2, если р? = 0;

О , если р1 = р2 := о. Матрицей минимальных вероятностей назовем матрицу видя

Ир(РМп) = §РГО,П „I. (29)

полученную из матрицы (24) по правилу рт1п ^ = Мри)11 .

где ри - ВврОЯТНОСТЬ прохождения дуга е ЪiJ.

. Матрицей максимальных вероятностей назовем матрицу вида

■УР«,) = <з°)

полученную из матрицы (24) по правилу р { = шах (ри),..

и

На множестве матриц минимальных вероятностей зададим операцию минимального умножения

Кы »,.1 - ар;;; юп

гда р;;; и -; <р;«п Кы vJ)^

Матрицу [1Нг(рп(п)]п назовем минимальной п-ой степенью матрицы 0^(Рв|п>.

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

^ „я « = ЗР,^; „I. (32)

гда Р™; и = <р^х «„

Матргщу [(М^,(ря1а:в) 1п назовем максимальной п-ой стопупью матрицы И^Р^Ь

Для заданных алгебр доказаны следящие утверждения:

Утверждение 1. Элемент )п матрицы (!МГ)" соответствует

множеству цепочек ) = ), поровдаеиых при ррототдоч-"!«

путей-из графа (18).

Следствие 1. Элемент №ИУ)п матрицы (В^,)" соответствует множеству цепочек, принадлежащих языку 1(1) источника (22).

Утверждение 2. Цепочка 1 = в1 ... ... я^ порождается источ1Шсом (22) тогда и только тогда, когда выполняется

[^(8,)] & ... & ПН^,,)! & ... & [1^.(^)1 * ЗОЛ, .(Я?)

где ДО| - нулевая матрица.

Следствие 2. Цепочка 1 принадлежит языку 0.(1) источника (22) тогда и только тогда, когд-.з нч равен нул» элемент матрица, являющейся результатом конъюнкции характеристич*><-\чих матриц символов, входящих в цепочку I.

Утверждение з.). Мшшмгып-чоо значение вероятности пороет"»«»?»

цоночки e i<Z™ ), при прохождении в Грефе путей длины п из ZlJt pai":: зиачрак» злшеш-р <рм(п tJ)n матрицы t!Mr(pm{n)]n, где ^r^'nir»- матрица в;-да (29).

Утверждение 3.2. Максимальное значение вероятности порождения цепочки- l4i е 1"(), пр.г прохождении в графе путей длины п из '¿tJ, равно значению элемента (р^, tJ )п матрицы ГИр(рв1сц,) Jn, где (ретах) - матрица вида (30).

Следствие 3.1. Минимальное значение вероятности порождения ■Ш1 стохастическим источником за п событий резл5!зацки цепочек из множества Cl.) = i(D) равно значению элемента (р . ) матрицы flHj.ip^^)]".

Следствие 3.2. Максимальное значение вероятности порождения <ЙШ стохастическим источником за п событий реализации цепочек из множества tl,} = i(D) равно значению глемеята (р )

„ * tТЬО/СС К 1С 1%

матрицы ^(р^)]".

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

Праведен также • способ вычисления коллчества различающихся ЗШ, реализукщихск за заданное члсло тактов генерации.

Аналогичное исчисление прздлошно* для анализа модели на основе стохастсчэских гремматик. СущэстЕв;шнщз отличиями являются форма юатриш регулярных выражений¿' ажтштаки которой, в случае представления используемых стохастических грамматик матрицей, являются билинейные регулярные внрЕжэним, соотьэтствувдиэ событиям реализации "билинейных терминальных структур, порождаемых грамматикам;: нспольвуешх вздов, и свойства операции конкатенации, р-адапкой на множестве билинейные регулярных выражений.

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

управления, и энтропией процесса, параметры кото; ..го зидаьы в соответствии с ограничениями, определяемыми особенна--.яки коЯкр-зт ного тестируемого устройства.

Энтропия процесса порождения цепочки 1 команд ; сюхас-тическим источником равна

HCl) = - 41 я qt 2 <1и log2Pu. (31)

t J

где = mtj / m(J q( = ia( / m, ii\ = |zä,K|, ntu - чисио раз прохождения по дуге d(J из подмюжоетва D{ пцраллеяышх дуг, принадлежащих пути 2ик порождающего грсфп, mt - число ргл прохождения по любой дуге из подмножеств Г)(^.

В работе найдены условия, при которых функционал (3-1) достигает условною минимума Hmt (1). С учетом stoi-o энтропия процесса • может быть представлена в виде

Н(1) = ш 2 Ч4ГН( m,n(D + Я,(1)1, (35)

где ^ Е I l0S2(p"j / P,j) информационное уклонение

заданного распределения р{ = fp{,} от оптимальном- ¡к - Гi, при котором фующионал (34) достигает условнох-о минимума.

При отсутствии iüiH игнорировании инфордашш о тестируемом устройстве, распределения задаются равномерными, »пч> соответствует минимаксному решеш!» в условиях неопределенности.

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

J(l) - Н, и(1) - К(1) = ) - 91(1). (36)

где J (1) = Н ,,(1) - I! , (1) - моксзмальюэ количество иифор-

"»чаэг JR Я min 1

мации, которое моьео попользовать с келью ол-гатезащга процесса.

Характеристикой качества стохастического процесса генерации

являете:; его "постоянная времени" т = At / Р(1), где At -

среднее'ьремя, а Р(1) - вероятность порождения <ШП.

В условиях управления процессом генерации справедливо

-IJ (1) - Я(1)] т = ти1(2 (3Y)

где т - постоянная времени в случае минимаксного ретеннч.

Постоянная времени уменьшается в степенной япвистхт? от количества информации, использованной для ущшил-мшя «.•тот.пстичо'?-

птцьо .-ом го 1 к;рации 'ГШ,

;м

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

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

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

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

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

Разработан машинный алгоритм,"реализующий процедуру преобразования элементарных графов в порождающий.

Приведена примеры синтеза модели процесса генерации тестовых программ для микропроцессора Intel 80386.

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

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

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

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

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

Получено аналитическое выракение для интегральной оценки относительной погрешности вероятности реализации функционально полной программы

1п£чЛои> (г/,)

6Р (1) = 12 ' - 1] « ——---- (ПЯ)

а

ехр(1/а)

где 91<п(1.) - информационное уклонение заданного распределения р( = } вероятностей реализации событий от реализованного распределения, содержащего сумму погрешностей р = (р

. ' и Р и р^

ш - длина ФПИ, q - параметр алгоритма генерации, I - время процесса генерации, т = - постоянная времени процесса генерации, М - среднее время генерации элемента ФИЛ, Р - минимальная вероятность реализации элемента ФПП за один эксперимент порождения.

Важным для практики фактом является быстрое уменьшение ветчины относительной погрешности вероятности реализации ФПН ю временем процесса генерации. При изменении времени от % до Н.п относительная погрешность уменьшается на три десятичных норпдьп. Устойчивость стохастических методов генерации т^стоеч; в'.^пеПсп^й и прпгрчум к погрешностям является их ршетшм I г| • т - - !■:>-> г I ••■<

гч

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

Ис^о-г/кование иредшкениой концепции в качестве единой 1«1тодолопт-"..,ской основы разработки методов и средств псевдослучайного тестирования программно управляемых устройств позволило создать ряд технических средств: устройств, алгоритмов функциони-роамом, программное, аппаратное, методическое и метрологическое обеспечение автоматизированных систем псевдослучайного ¡тестирования програьмно управляемых устройств. •

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

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

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

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

Реальный экономический, эффект от внедр ния результатов диссертационной работы в промышленности составляет 830 тысяч рублей (в ценах 1991 года).

В приложении приведены сведения о внедрении результатов диссертационной работы в промышленности.

Р 4

ОСНОВНЫЕ Ж?УЛ1.ТАТЫ РАБОТЫ

В диссзртациокноЯ работа в качестве методоло; \ хкой основы исследовании а разработок стохаетичош.;а (нсевдослу¥«№>шх) методов и реализующих ах средств тестирования щюгрсммио у^овляемьх устройств предложена и использована ковцетдея, ааклныящаяся в формальном отображении достушгой информации о >■ ..■-чкретнсм тестируемом устройстве в структуру и параметры апгорпмо« стохастической генерации, обеспечивая их адаптацию к особенностям конкретного тестируемого устройства, решении на атой остове актуальных проблем автоматизации процесса синтеза тостов«:» аоэдействай и программ и повышения вффективноети и достоверности тестирования программно управляемых устройств.

К основным результатам диссертационной работы необходимо отнести следувдев:

1. Анализ усдоЕИЙ эффективного применения детерминировании и стохастических методов для решения ззд&ч контроля сходных цифровых устройств, шполнешшй с единых теоретических и методологически позиций, позволил установить, что критерием аф^ектииаостк того пли иного метода является соотношение комбинаторной слояюсти задачи и объема ресурса, выделенного на ее решение.

В условиях априорного недостатка информации, характерного для процесса контроля слокинх цифровых устройств, когда объем ресурса значительно меньше одьека пространства вариантов к«5ор&, в которого происходит поиск удовлетворительного варианта решения, стохастические методы являются наиболее ьффоктигашми и позволяют решить задачу с гарантированным'среднестатистическим качеством.

Одаако,' етохастечесюш метода решения рядач контроля в рамках »грэдлояеняой концепции не противопоставляются детерминированным. Напротив, разрйботанше метода, используя сяязниэ ото/астичесчне процессу с . укравлкйллчи - параметрами, : позволяя1« «лглтировять процесеи генерации тестовых чоздействий и программ к конкретному тествру^мему устройству путем введения в процессы необходимой доли детерми-'И'.'ма, объединяя тем сами достоинства как стохастических, так с детерминированных методов.

7. Предложена и исследована математическая модель тестовых ноздййстгий, нмеицзя пил текста иа входном языке тестируемого устрсйс-Пча, отрачашдая отношение рр^тчес! пепачип элементов гордой -'•'ггмн, ч "пкур матемащч^сг чп модель Функципип и-чо полис л |»|*ч рам-

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

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

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

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

Разработанный метод анализа позволяет:

- исследовать поровдащие свойства стохастических процессов (генераторов) путем вычисления генерируемых ими последовательностей элементов тестовой программа или тестового воздействия;

- определять возможность порождения стохастическим процессом (генератором) функционально полных программ;

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

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

5. Исследованы информационные свойства моделей стохастических процессов генерации тестовых воздействий и программ.

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

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

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

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

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

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

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

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

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

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

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

8. РозрпЮтены устройства, релизу нщчэ смятю управляемы» ^тохясип« промессы гпц-п.шти« я 1г-м?>итр тс-'т^р^х Р'",г>.ирй<,твиР и

■ /

прогрею* t а такяе устройства для анализа свойств и измерения нара>&»трсв стохастических цроцессоя яа входах, доступных внутрзин«.? точках s* выходах тестируемых объектов.

Новияла T8Kis< ч-зских рьаениЯ; использованных в разработанных устройствах, подтверждена авторскими свидетельствами на изобретения.

IIa предлогашсй методики построения моделей связных

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

9- Разработаны и внедрены в промышленность овтомотизирован-ные системы типа ТЕСТ к .ЛИНГВИСТ, реализуицяе в своем методическом, программном и аппаратном обеспечетш основные теоретические результаты, положения и вывода диссертационной работы.

Внедроние результатов диссертационной работы в промышленность позволило, получить экономический эффект в размере SSO тысяч рублей (в ценах 1991 года).

Основные положения диссертационной работы изложены в бредущих публикациях:

1. Филшовов С. 11. Аппроксимация псевдослучайных тестов цифровых устройств к оадшшому уровшо качества // Контроль и диагностика цифровых узлоз на микросхемах.- М. : ВДИИТЭИ, 1983.- С.66-69.

2. Филкмоцов С. И. йзтод построения псевдослучайных тестов цифровых устройств // Тоз. докл. VI Всесаюзн. научно-техн. конф. "!*н^ормацио!Я'о-иэ?.!эрвтелыш9 системы-S3 (№10-83)".- Куйбышев: Лом техники, 1983.- С. 245-246.

3. Филимонов С. Н. Грамматическая ашроксимация псевдослучайных тестов цифровых устройств к вадшыому уровню качества // Тез.докл. Республ. семинара "Информащюкно-к'юр-лтельные системы для контроля и диагностики электронной аппаратура".- Кишинев: ЦАМ АН МССР, 1503.- С.'8.

4. 5Чшмопов С. Н., Александрова А. Ф., Пе-ркин А. Н. Программное обеспечение автоматизированной системы контроля узлов ЭВМ // Тез. докл. Республ. научно-техн. конф. "Управляющие ■ rai- .и микро-ЭВМ и их применение в народном хозяйстве.- Кишинев: Дом техники, 1934.- С. 142.

5. Филимонов С. Н., Зойчикова 0. В., Филатов-В. Д. Процес-

сор, реапизуювдгЯ управляемые сгохвстпчйскяв граыматда,--: // Тоорчя и прокпыа конструирования и обессечзшм надежности и '.■•••гэстил электронной 8%'п<:ратуры и приборов.- М : Радио И снясь, 1v.- С. 86.

6. Фшшшнов 0. Я., Александрова А. Ф. Программное иЗеспо--ченне систем» хонт1>оля, иснольиуещей управляемые исевдо • «учаЯ^.^ процессы '// Материалы Респуйи. каучяо-тзхн. сешшара Jho-mí контроля параметров влэктрошшх у строй с ги и прибора, л:".- Ки-л- г РДЭНТП, 1984.- С. 50-51.

7. Еоркез'лч В. И., Клйсторин И. Ф., Филимонов С. 11. Инфор-лз-цпонше аспекты процесса генерации стохвс.'ичеекпк -к'скгч // Пзеостия Акадыяш наук Молдавской ССР.- 1984.- .« I. 0. й4-б5.

8. Всрдевяч В. И., Клисторин И. Ф., Филимонов ('.. И. Ыодали-ровашзе процесса псевдослучайного тестирования и ъго itííJ.opcjwii-ные аспекта // Электронное модялирование.- 1984.- № р.,- с. 57-61.

9. Фаяихюнов 0. Н. Алгоритма и средстьп управляемой генерации псевдослучайных воздействий в :ш|юрмационн0">-'змпрагольвай системе контроля цифровых устройств: Диссертация на поискание ученой стотт канд. техн. н.- Ктчтв, 1985.- 176 с.

10. Ктаоуорин К. Ф., Ворщевич 3. И., ©шшоиов С, н. и др.. Микропроцессор для управления ресйнши проверок при контроле ц»£рою8 аппаратуры // Приборы и системы у»«рпэдаягая.- 1935.>? 10. - с. 21

11. Борщевнч в. й., Ювюторин л. ф. , яйлимсь;-,: с. и. кодэли-ровапае процесса генерации псевдоелучоЛщх '¡остов цифровых устрой • стн посредством стохастических грамматик // Электронной модолиро-вагко.- 1985.- Ü 2.- С. 5?.-57.

12. Еоррдэвмч В. И., Филемонов G, Н., Александрова А. Программное об^ечечеш»1- системы кэдтролл ¡пфрових устройств "ЛИШтасТ-бОЮ" // Лтрчелшдте vhorem л нашим.- 19В5.~ •? 5.-С. 47-50.

13. Системы псевдослучайного тестирования цифровой аппаратуры "ЛШВ1СТ-601С", ЯЛ1ШГВИСТ-802МПЯ и "ЛИИГВИСТ-ОТД" / Клисторин И. Ф.', Борщевич В. И, Филимонов С. Н. и др. // Ученые высших учебных заведений Молдавии народному хозяйству.- Кишинев: МолДИШГГИ, 1985. С. 25-27.

14. ?«лимонов С. Н. Оценка полноты и оптимальности псевдослучайна тестов цифровых устройств // Унрявлянпир системы и япгсини,- |Ч86.- Л 3.- П. 10-42.

15. Г^рщовтн П. И., Фч.иимоиоп i*, Н. Структурно- .т.шгристцчос.-

кий подход к диагностированию микрогпюце с сорнн х средств // Структурное и покомпонентное диагностирование устройств радио-влоктрониой аппаратуры.- М.: ЦНИИТЭИ, 1986.-0. 12-14.

16. Борщэвич В. И., Уланов В, Д., Морщгаин Е. В., Фшш.-онов С.Н. Методическое обеспечение системы контроля дискретных устройств ЛЖГВИСТ-802 // Системы автоматизированного проектирования в машиностроении и тфиборостроении.- Кишинев: АН Ь'ССР, 1986.0. 131-133.

17. Автоматизированный комплекс ЛИНГВИСТ в стандарте КАШК для контроля микропроцессорных устройств / Клисторин И. Ф., Ворщевич В. И., Филимонов С. Н. и др. // Тез.докл. Международного семинара но проблзмо реализации комплексной программы ноучно-тохнпчэского прогресса стран-членов СЭВ до 2000 года.- Кишинев: Штиинца, 1987.- С. ¡9-21.

18. Клисторин И. Ф., Борщевич В. Я., Филимонов С. Н. и др. Астрологическое обеспечение стохастического функционального контроля микропроцессорных устройств // Тез. докл. 11 Всесоюз. научно-техн. :<онф. "Метрологическое обеспечение ИИС и АСУ ТП".-¡Львов: НПО СИСТЕМА, 1938.- С. 35-41.

19. Борщевич В. И. Клисторин М. Ф., Филимонов С. Н. Структурно-лингвистический подход к псевдослучайному тестированию микропроцессорных устройств // Тез. докл. XXX Всесоюз. школы-семинара им. М. И. Гаврилова.- Кишинев: АН МССР, 1938.- С. 76-79.

20. Борщэвич В; Й., Цггнов В. Д., Сидоренко В. В., Филимонов С. Н. Метод оценки достоверности псевдослучайного тестирования микропроцессорных устройств // Автоматика и вычислительная техника - 1988.- Л 4^- С. 76-81.

21. Борщэвич В. И., Филимонов'С. Н., Кирьяк Л. Т. Контролепригодность СБИС относительно методов стохастического функционального контроля // Тез. докл. XXX Всесоюз. школы-семинара им. М.А. Гаврилова.- Кшинев: АН МССР, 1988.- С. 124-125.

22. Филимонов С. Н. Кирьяк Л. Т. Модель процессора ПЭВМ для целей функционального контроля // Тез. докл. I Всесоюз. школы -семинара "Разработка и внедрение в народное хозяйство персональных ЭВМ". Ч.1У: Проблемы обеспечения надежности, эксперементальные системы, обучающие программ.- Минск: МПОВТ, 1988.- С. 60-о..

23. Филимонов С. Н. Применения языковых вхождений в задаче псевдослучайного тестирования цифровых устр#.ств // Тез. донл. Республ. семинара "Техническая диагностика и эксплуатация вычисли-

■шышх и управляющих систем".- Киев: АН УССР, 1989.

24. Филимонов С. Н., Гуиаи В. Ф., Макаров В. А. Исследовали« свойств генераторов псевдослучайных ьоследопателыюстеЯ // Тез. докл. Республ. научно-гехн. конф.- Кишинев: КНО МС.СР, КИИ им. С.Лазо, 1989.- С. 13.

25. Автоматизированная система стохастического функционального контроля микропроцессоров / Клнсторш И. Ф., Борщевич В. И., Филимснон С. Н., и др. // Приборы и системы управления. 1939.--

№ 8.- С. 20-21.

26. Еорщевнч В, II., Бодан Г. К., Филимонов С. Н. Млтод максимума онтропиа в задачах нсовдослучай!мго тестирования ¡лп-ролр' цес--сорш1х устройств // Приборостроение.-• 1989.- & 9.- С. ГП 39.

2'Г. Еор-звнч В. И., Кмрьяк Л. Т., Филимонов С. И. !|я!?кач1б псевдослучайно геиер :руемых воздвйстй для кои. \ лля к.'яглоо обне-на информацией. // ьонрэсы. радиоэлектроники: Сер. ЭВТ, !Вып. 3.- С. 12-16.

28. Борцргач я. И., Зилимонов С. II., Жданов В. Д., Сидоренко

B. В. Оценка достс-ис-рюсти стохастического контроля микр^лрсцоссо-ров // Элеятрошюо моделирование.- 1989.- !$ 1.- с. 65-59.

29. Оорщевач а. Л., Филимонов С. II., Кирьяк Л. Т. 1Ьтсд генерации тестовых программ, иоиишаюнгЛ надежное!*!. процессоров /' Вопросы специальной радиоэлектроники: Сер. ЭВТ, И«9.- Вни. 1.

30. Клисторкн и. Ф., Борщэвич В. й., «йышмоиов С,. П. и пр. Исслэдовахше сбс2сть геиораторов псеедослг.аАпкх поелдовяг элмюе-теЯ // Измерительная техника, 1989.- й 11.

31 .Клнсторш И. Ф., Еорщевнч В. И., Фшчшонов С. II. Структурно-лингвистический подаод - перспективное направление р снятия методов и средств контроля микропроцессорных устройств // Измерения,'контроль, автоматизация.- 1990,- №3.- С. 38-43.

32. "{данов В. Д., Кройтор И. В., «млнмопов С.- И. Подсистема синтеза тестовых программ для функционального контроля микропроцессоров // Тез. Республ. научно-техн. конф. "Проблемы автоматизации контроля электронных устройств".- Киев; УкрПШГГИ, 1990.-

C. 4-6.

33. Борцевич В. И., Филимонов С. Н. Моделирование микропроцессоров для цели стохастического функционального контроля // Тер., Республ. научно-техн. конф. "Проблем?! автемягиягами контроля елен-трошшх устройств".- Киев: УкрПШГГИ, 1<"П, ■ с. л,

31. Кирьяк Л. Т. * 'Тилимонов п. II, Мол»лирчвптк- вр^иг-е'Ч'П

для синтеза тестовых программ // Тез. докл. Всесоюз. . научно-техн. конф. "Нячеигость машин, математическое и мааиаое моделирование задач дшшмзгки. Моделирование - 91".- Ккпине$: АН МССГ, 19,91.-

С. 1''".

35. .'..;рв;ввич В. И., Зштмонов С. К. Стохастические штоды в диагностике // Автоматика и телемеханика.- 1992.- Л 11.- С. 127-133.

3ь. КЗistorin I., BoraLcUevich V., Filimonov S. CAD subsys tem >vlth artificial intelligence elements // The Integration of Purpose Specialists' Training System and Automation Technical Systems of various Purpose.- Moseou: CNCRPS, 1990.- P. 18.

37. Klletorin I. F., Bora'achevich V. I., Filimonov S. N. Systems for tqatirig oi micrprocessors // Proe. of the 6th System Modelling Co.:\.rol Symp. (SMC-6).- Zakopane: Institute of Informatics, 1990.- F. 191-192.

38. Borscevici V. I., Filimonov S. H., Oleinik V. L., Pusne-ac Y. A. Spectral analysis of fiizsy seta ana applicftions in image recognition // FusH-y Systems к A.I.Magazin.- V 11991.- N 3-4.

- P. 6-7.

39. Borsfierlch V. I., Kilatoi-in I. •?., S.tdorenco V. V., filimonov S. N. Structural r.nd Linguistic Approach to Test Patterns Generation and Quality Evaluation // XVIII Ui Congress of the Romanian A'nsrlcan Academy of Sciences and Arts.- Vol. 2.-(!h.l9hineu: ASH, 1993, P. 44. ; '

40. Filic-oaov S. It. Tiio model of the stochastic generator of the teot programs and laethod of its analyse // Computer Sciences of Moldova.- 1993.- V. 1,- a 3.- P. 81-86.

Личный вклад й'вгорэ в работах, опубликованных в соавторства.

. В работах ИЗ, 17, 25, 36, 37) автору принадлежат структурные, алгоритмические н схемотехнические рэа»ийя, в работах 14-6, 10, 12, 24, 27, 29] тя поставляй водачк и аре.адояены методы их решения. В остальных совместно написаншх работах автору прпнвдлэкат результаты кпслодовпнйя закономерностей псевдослучайного -тестирования программно управляемых устройств и Формулировка тодо.го.пт'ч"е ских основ но следов шгай и разработок. .

nstiiu

Глава 1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ ПСЕВДОСЛУЧАЙНОГО ТЕСТИРОВАНИЯ ПРОГРАММНО УПРАВЛЯЕМЫХ УСТРОЙСТВ

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

1.2. Средства псевдослучайного тестирования программно управляемых устройств

1.3. Выводы

Глава 2. ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ РАЗРАБОТКИ И ИССЛЕДОВАНИЯ СТОХАСТИЧЕСКИХ МЕТОДОВ И СРЕДСТВ КОНТРОЛЯ ПРОГРАММНО УПРАВЛЯЕМЫХ УСТРОЙСТВ

2.1. Условия эффективного применения стохастических методов для решения задач контроля цифровых устройств

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

2.3. Выводы

Глава 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОЦЕССОВ ГЕНЕРАЦИИ

ТЕСТОВЫХ ВОЗДЕЙСТВИИ И ТЕСТОВЫХ ПРОГРАММ

3.1. Модель тестового воздействия

3.2. Модель процесса генерации тестового воздействия

3.3. Модель тестовой програшм

3.4. Модель функционально полной программы

3.5. Модель процесса генерации тестов/ых программ

3.6. Выводи

Глава 4. МЕТОД АНАЛИЗА ПОРОЯЩАПЦИХ СВОЙСТВ СТОХАСТИЧЕСКИХ ПРОЦЕССОВ ГЕНЕРАЦИИ

ТЕСТОВЫХ ВОЗДЕЙСТВИЙ И ПРОГРАММ

4.1. Эквивалентное представление порождающего графа стохастического регулярного источника

4.2. Анализ порождающих свойств стохастического регулярного источника

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

4.4. Эквивалентное представление порождающего графа стохастической билинейной

КС-грамматики

4.5. Анализ порождающих свойств стохастической грамматики

4.6. Информационные свойства моделей процессов генерации тестовых воздействий и програкм

4.7. Выводы

Глава 5. МЕТОДИКА ПОСТРОЕНИЯ МОДЕЛЕЙ СТОХАСТИЧЕСКИХ

ПРОЦЕССОВ ГЕНЕРАЦИИ ТЕСТОВЫХ ПРОГРАШ

5.1. Особенности архитектуры микропроцессоров, учитываемые при генерации тестовых программ

5.2. Анализ системы команд тестируемого микропроцессора и синтез элементарных графов

5.3. Синтез порождающего графа стохастического регулярного источника

5.4. Выводы

Глава 6. МЕТРОЛОГИЧЕСКОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННЫХ СИСТЕМ ПСЕВДОСЛУЧАЙНОГО ТЕСТИРОВАНИЯ ПРОГРАММНО УПРАВЛЯЕМЫХ УСТРОЙСТВ

6.1. Типовой тракт формирования событий с заданной вероятностью

6.2. Метрологическая аттестация генераторов псевдослучайных последовательностей

6.3. Анализ применяемых дискретных шкал вероятностей и вносимых ими погрешностей

6.4. Интегральная оценка относительной погрешности вероятности порождения элементов тестовых воздействий и програмл 1Т

6.5. Метод построения оптимальной дискретной шкалы вероятностей

6.6. Выводы

Глава 7. АППАРАТНОЕ, ПРОГРАММНОЕ И МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННЫХ СИСТЕМ псевдослучайного тестирования программно

УПРАВЛЯЕМЫХ УСТРОЙСТВ

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

7.2. Устройства анализа стохастических процессов

7.3. Подсистема автоматизации процесса синтеза тестовых программ

7.4. Автоматизированная система

ТЕСТ

7.5. Автоматизированная система

ЛИНГВИСТ

7.6. Автоматизированная система

ЛИНГВИСТ

7.7. Вывода

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

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

Исследовании в области разработки теории, методов и средств контроля устройств вычислительной техники и систем управления посвящены работа многих ученых и руководимых ими научных коллективов, в частности П. П. Пархоменко, В. А. Гуляева, Н. П. Байды, В. Г., Тоценко, И. Ф. Клисторина, С. Г. Шаршунова, А. А. Аракеляна, Г. М. Ясинявичене, S. Thatt, С. Robach, G. Cancler, С. Bellon и др.

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

Разработке и исследованию стохастических методов и средств контроля посвящены работы А. М. Романкевича, С. М. Берштейна, В. И. Ярмолика, В. И. Борщевича, А. А. Гремальского, Y. Agraval, К. Parker, R. David, Thevenod-Fosse и др.

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

Профессором В. И. Борщевичем выделены, например, следующие области применения стохастических методов [641:

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

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

- статистические испытания разработанных ранее тестов для определения их качества (полноты) относительно заданного класса неисправностей;

- псевдослучайное отображение множества реакций тестируемого устройства во множество сигнатур, как средство сжатия реакций и условие реализации метода сигнатурного анализа, разработанного специалистами фирмы Hewlett Packard;

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

Под тестированием устройства мы, в соответствии с [74,75], будем понимать активный процесс определения его технического состояния.

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

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

- простота реализации псевдослучайных генераторов с заданными свойствами посредством программных и аппаратных средств АСК;

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

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

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

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

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

Задачи исследования. Достижение поставленной цели требует решения следующих взаимосвязанных задач:

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

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

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

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

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

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

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

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

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

Автор защищает:

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

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

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

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

- метод определения погрешностей вероятностных оценок качества тестовых программ и достоверности процесса псевдослучайного тестирования;

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

Связь с государственными программами и НИР.

Разработки устройств, алгоритмов, программного, методического и метрологического обеспечения систем контроля выполнялись: в соответствии с координационным планом НИР АН СССР по проблеме 1.12.8, раздел 1.12.8.3, тема "Автоматизированные системы проектирования контроля и диагностики микропроцессорной техники",

ГР 01860022457; в рамках целевой комплексной программы и на основании приказа N 535 MB и ССО СССР от 20.05.81 г. по теме "Автоматизированные системы проектирования, контроля и оптимизации технологических процессов и технических объектов", * ГР 81035579; на основании постановлений Правительства СССР £ 317-126 от 08.04.83 г. и * 30 от 08.02.84 г. для контроля специализированных процессоров; на основании постановления Правительства СССР J& 355 от 23.03.87 г. для тестирования управляющих процессоров ультразвуковых средств неразрушающего контроля; в рамках НИР: "Исследование и разработка программного обеспечения автоматизированных систем контроля электронной аппаратуры"

ГР 8I0I373I, "Система автоматизированного контроля и диагностики электронных блоков ультразвуковых средств неразрушающего контроля"

ГР 0I8600I76I7, "Диагностика - 90" per. * У 54443; в рамках ОКР "Автомат", per. * У 81337.

Образцы систем демонстрировались на ВДНХ СССР (удостоверение

24535) и на мездународной выставке "Связь - 86".

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

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

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

Реализация результатов диссертационной работы.

Основные результаты научных исследований и разработок реализованы в виде ряда устройств, программной подсистемы автоматизации синтеза тестовых программ - ПАСТП, алгоритмов функционирования, базового программного, методического и метрологического обеспечения автоматизированных систем псевдослучайного тестирования ТЕСТ-7901, ТЕСТ-8103, ЛИНГВИСТ-802, ЛИНГВИСТ-803, внедренных на ряде промышленных предприятий.

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

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

Апробация работы. Основные научные результаты, положения и выводы диссертационной работы были представлены и одобрены на Международном семинаре по проблеме реализации комплексной программы научно-технического прогресса стран - членов СЭВ до 2000 года (г. Кишинев 1987), Международной конференции по автоматизированным техническим системам (г.г. Евпатория, Москва 1990), 6-ом Международном симпозиуме "Системы, Моделирование, Управление" (SMC-6) (г. Закопане 1990), 18-ом конгрессе Румыно-Американской Академии науки и искусства (г. Кишинев 1993), Всесоюзной НТК "ИИС-81" (г. Львов 1981), на семинаре "Функциональный контроль изделий микроэлектроники" (г. Ленинград 1982), Республиканской НТК "Структурные методы повышения точности средств и систем автоматизации экспериментальных исследований" (г. Киев 1989), на 5-й Всесоюзной НТК "Проблемы метрологического обеспечения систем обработки измерительной информации" (г.г. Суздаль, Москва 1984), 5-ом Всесоюзном симпозиуме по модульным ИБС (г. Кишинев 1985), 7-й Всесоюзной НТК "ИМС-87" (г. Ташкент 1987), 11-й Всесоюзной НТК "Метрологическое обеспечение ЛИС и АСУ ТП" (г. Львов 1988), на XXX Всесоюзной школе-семинаре им. М. И. Гаврилова (г. Кишинев 1988), на XI НТК "Проблемы разработки измерительных приборов со встроенным интеллектом и перпективы их развития" (г. Каунас 1988), I Всесоюзной школе-семинаре "Разработка и внедрение в народное хозяйство персональных ЭВМ" (г. Минск 1988), XXIII Всесоюзной школе-семинаре по автоматизации научных исследований (г. Кишинев 1989), Республиканском семинаре "Техническая диагностика и эксплуатация вычислительных управляющих систем" (г. Киев 1989), Республиканском семинаре "Вопросы разработки вычислительной техники" (г. Кишинев

1989), Республиканской НТК "Проблемы автоматизации контроля электронных устройств" (г. Киев 1990), Всесоюзной НТК "Моделирование - 91" (г. Кишинев 1991), а также на некоторых других конференциях, совещаниях и семинарах.

По теме диссертации опубликовано 70 научных работ, в том числе б авторских свидетельств СССР на изобретения, статьи в журналах "Электронное моделирование", "Автоматика и телемеханика", "Автоматика и вычислительная техника", "Приборы и системы управления", "Управляющие системы и машины", "Приборостроение", "Известия Академии наук Молдовы", "Измерительная техника", "Техника средств связи", "Измерения, контроль, автоматизация", "Вопросы радиоэлектроники", "Вопросы специальной радиоэлектроники", "Fuzzy System & A. I. Magazin", "Computer Sciences of Moldova" и других изданиях.

Объем и структура диссертации. Диссертация содержит 242 страницы основного текста, состоит из введения, семи глав, заключения, списка использованной литературы из 222 наименований, а также приложения, содержащего информацию о внедрении результатов диссертационной работы в промышленности. Работа иллюстрирована 26 рисунками.

7.7. Выводы

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

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

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

3. Разработаны и внедрены в промышленность автоматизированные системы типа ТЕСТ и ЛИНГВИСТ, реализующие в своем методическом, метрологическом, программном и аппаратном обеспечении основные теоретические результаты, положения и выводы диссертационной работы.

Внедрение результатов диссертационной работы в промышленность изволило получить экономический эффект в размере 830 тысяч рублей (в ценах 1991 года).

ЗАКЛЮЧЕНИЕ

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

К основным результатам диссертационной работы необходимо отнести следующее:

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

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

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

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

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

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

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

Разработанный метод анализа позволяет:

- исследовать порождающие свойства стохастических процессов (генераторов) путем вычисления генерируемых ими последовательностей элементов тестовой программы или Истового воздействия;

- определять возможность порождения стохастическим процессом (генератором) функционально полных программ;

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

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

5. Исследованы информационные свойства моделей стохастических процессов генерации тестовых воздействий и программ.

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

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

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

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

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

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

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

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

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

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

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

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

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

9. Разработаны и внедрены в промышленность автоматизированные системы типа ТЕСТ и ЛИНГВИСТ, реализующие в своем методическом, программном и аппаратном обеспечении основные теоретические результаты, положения и выводы диссертационной работы.

Внедрение результатов диссертационной работы в промышленность позволило получить экономический эффект в размере 830 тысяч рублей (в ценах 1991 года).

1. Автоматизированная система контроля цифровых устройств ТЕСТ-7901 / Амбарников М. И., Сарачев В. С., Сидоренко В. В., Филатов В. Д., Филимонов С. Н., Чикликчи В. В. // Докл. Всесоюзн. научно-техн. конф. ИИС-81Львов: НПО СИСТЕМА, 1981.- 4 с.

2. Автоматизированная система контроля микропроцессорных систем ТЕСТ-8103 // Связь-86. Международная отраслевая выставка. М.: Внешторгиздат, 1986.- С. 172.

3. Автоматизированная система контроля с псевдослучайным тестированием ТЕСТ-8103 : Отчет об ОКР (заключит.) / НИИ Квант.

4. ГР Г45897; Инв. * 02.07.84 00165.- Кишинев, 1983.- 39 с.

5. Автоматизированная система контроля и диагностики микропроцессорных устройств ЛИНГВИСТ-802: Отчет о НИР (заключит.) / КПИ им. С. Лазо.- * ГР 01860017617; Инв. * 02880045289.- Кишинев, 1988.- 77 с.

6. Автоматизированная система стохастического функционального контроля микропроцессоров / Клисторин И. Ф., Борщевич В. И., Филимонов С. Н., и др. // Приборы и системы управления. 1989.- * 8.-С. 20-21.

7. Автоматизированный комплекс ЛИНГВИСТ в стандарте КАМАК для контроля микропроцессорных устройств / Клисторин И. Ф., Борщевич

8. B. И., Филимонов С. Н. и др. // Тез.докл. Международного семинара по проблеме реализации комплексной программы научно-технического прогресса стран-членов СЭВ до 2000 года.- Кишинев: Штиинца, 1987,1. C. 19-21.

9. Александрова А. Ф., Гушан В. Ф., Жданов В. Д., Филимонов

10. С. Н. Структурно-лингвистическое тестирование микропроцессорных средств ИБС // Тез. докл. V Всесоюз. симпозиума по модульным информационно-вычислительным системам.- Кишинев: Штиинца, 1985.-С. 9-10.

11. Алферова 3. В. Теория алгоритмов.- М.: Статистика, 1973. 163 с.

12. Амбарников М. И., Колесник Н. И., Сидоренко В. В., Филатов В. Д., Филимонов С. Н., Чикликчи В. В. Программное обеспечение автоматизированной системы контроля цифровых устройств ТЕСТ-7901 // Средства связи.- 1982.- * 3.- С. 50-52.

13. Амбарников М. И., Сарачев В. С., Сидоренко В. В., Филимонов С. Н., Чикликчи В. В. Критерий эффективности автоматизированных систем контроля // Техника средств связи : Сер. Технология производства и оборудование, 1982.- Вып.3(8).- С. 115-118.

14. Амбарников М. И.Сарачев В. С., Сидоренко В. В., Филатов В. Д., Филимонов С. Н., Чикликчи В. В. Проблемно-ориентированныйязык ТЕКОС для автоматизированных систем контроля цифровой аппаратуры.- Деп. в НИИЭИР.- 1983.- 17 с. * 3-7264.

15. Амбарников М. И., Клисторин И. Ф., Сидоренко В. В., Филимонов С. Н., Чикличи В. В. Метод поиска неисправностей синхронных цифровых устройств // Надежность и диагностика полупроводниковых приборов.- Кишинев: Штиинца, 1984.- С. 83-86

16. Араке л ян А. А., Саядян Г. А., Огаджанян с. Р. Алгоритмы автоматического синтеза микропрограмм функционального контроля БИС // Автоматика и вычислительная техника.- 1983.- * 3. С. 55-59.

17. Аракелян А. А., Саядян Г. А., Огаджанян С. Р. и др. Пакет прикладных программ для автоматической генерации тестов функционального контроля БИС // Автоматика и вычислительная техника.-1984.- Л 1.- С. 67-71.

18. А. с. 527707 СССР, МКИ G 06 F 11/00. Устройство для статистического контроля логических блоков / М. С. Берштейн, А. М. Романкевич (СССР).- Опубл. 05.09.76, Бюл. * 33.

19. А. с. 600699 СССР, МКИ Н 03 К 3/295. Триггер ШМитта / И. Ф. Клисторин, В. К. Лефтер, С. Н. Филимонов (СССР).- Опубл. 30.03.78, Бюл. * 12.

20. А. с. 696510 СССР, МКИ G 07 С 15/00. Генератор псевдослучайных кодов / О. В. Викторов, Л. Ф. Карачун, А. М. Романкевич (СССР). Опубл. 05.11.79, Бюл. * 41.

21. А. с. 742910 СССР, МКИ2 G 06 Р 1/02, G 07 С 15/00. Генератор псевдослучайных двоичных последовательностей /3. А. Главин-ская, Л. Ф. Карачун, В. Н. Кущ, А. М. Романкевич (СССР).- 1980. Бюл. * 23.

22. А. с. 1383368 СССР, МКИ G 06 Р 11/26. Устройство для контроля цифровых блоков / В. И. Борщевич, В. Д. Жданов, Г. К. Бодян, В. В. Сидоренко, С. Н. Филимонов, Е. В. Морщинин (СССР).- Опубл. 23.03.88, Бюл. * 11.

23. А. с. 1499350 СССР, МКИ G 06 Р 11/00. Устройство для анализа состояний логических схем / В. И. Борщевич, С. Н. Филимонов, Е. В. Морщинин, А. М. Бобичев (СССР). Опубл. 07.08.89., Бюл. * 29.

24. А. с. 1608657 СССР, МКИ G 06 F 7/58. Преобразователь код-вероятность / В. И. Борщевич, В. Д. Я^анов, с. Н. Филимонов, В. Ф. Гушан, Ю. А. Пушняк (СССР).- Опубл. 23.11.90, Бюл. * 43.

25. А. с. 1640687 СССР, МКИ G 06 Р 7/58. Генератор случайной последовательности / Л. Т. Кирьяк, С. Н. Филимонов, И. Г. Балык (СССР).- Опубл. 07.04.91, Бюл. * 13.

26. А. с. 1728868 СССР, МКИ G 06 Р 15/36. Следящий стохастический интегратор / В. И. Борщевич, С. Н. Филимонов, Е; В. Морщинин, М. С. Загороднюк.- Опубл. 23.04.92. Бюл. * 15.

27. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, т. 1 Синтаксический анализ.- М.: Мир, 1978.612 с.

28. Байда Н. П., Кузьмин И. В., Шпилевой В. Т. Микропроцессорные системы поэлементного диагностирования. М.: Радио и связь, 1987.- 286 с.

29. Байда Н. П., Месюра В. И., Роик А. М. Самообучающиеся анализаторы производственных дефектов РЭА.- М.: Радио и связь, 1991.-256 с.

30. Баканов Ю. С. Проверка исправности сложных дискретных устройств с помощью случайных входных сигналов // Техника средств связи: Сер. Радиоизмерительная техника, 1981.- Вып. 2.- С. 98-104.

31. Берлекэмп Э. Р. Алгебраическая теория кодирования.- М.: Мир.- 1971.

32. Берштейн М. С., Романкевич А. М. Метод статистического контроля логических схем // Кибернетика.- 1974.- * 1.- С. 58-67.

33. Берштейн М. С., Романкевич А. М. О статистическом контроле многотактных схем // АВТ.- 1975.- * 2.- С. 14-20.

34. Берштейн М. С., Романкевич А. М. О статистическом контроле логических схем с произвольным потоком сигналов на их входах // Кибернетика.- 1976.- * 4.- С. 35-40.

35. Биргер А. Г. Многозначное дедуктивное моделирование цифровых устройств // АВТ.- 1982.- * 4.- С. 77-82.

36. Биргер А. Г., Бояршинов А. В., Винокур М. Ю. и др. Автоматизированная система построения тестов для цифровых ячеек повышенной степени интеграции // Обмен опытом в радиопромышленности. Вып. 4.- С. 4-9.

37. Бодян Г. К. Методы и средства повышения эффективности псевдослучайного тестирования микропроцессоров: Автореф. дис. на соискание уч. степени канд. техн. н. / Кишиневский политехнический институт им. С. Лазо.- Кишинев, 1990.- 18 с.

38. Борщевич В. И., Филимонов С. Н. Исследование стохастических грамматик для целей описания процессов псевдослучайного тестирования сложных цифровых устройств // Докл. семинара "Функциональный контроль изделий микроэлектроники".- Л.- 1982.

39. Борщевич В. И., Филимонов С. Н. Способ получения эффективных контролирующих псевдослучайных воздействий для сложных цифровых устройств // Деп. МолдНИИНТИ, 1983.- 17с. * 3461М-Д83.

40. Борще вич В. И., Филимонов С. Н. Контроль сложных цифровых устройств с памятью псевдослучайными методами // Надежность и диагностика полупроводниковых приборов.- Кишинев: Штиинца, 1983.1. С. 80-83.

41. Борще вич В. И., Филимонов С. Н,, Кройтор И. В. Исследование дискретных шкал вероятностей для систем псевдослучайного тестирования.- Деп. в МолдНИИНТИ, 1983.- 14 с. # 383М-Д83.

42. Борщевич В. И., Жданов В. Д., Сидоренко В. В., Филимонов С. Н. Метод семантических и синтактических ограничений при генерации тестов для микропроцессоров.- Деп. в МолдНИИНТИ.- 1983.17 с. * 334М-Д83.

43. Борщевич В. И., Клисторин И. Ф., Филимонов С. Н. Исследование процесса псевдослучайного тестирования цифровых устройств на основе лингвистического подхода // Контроль и диагностирование цифровых узлов на микросхемах.- М.:ЩШИТЭИ, 1983.- С. 28-32.

44. Борщевич В. И., Сидоренко В. В., Филимонов С. Н. Лингвистический подход к задачам контроля микропроцессоров // Информационно измерительные системы для контроля и диагностики электронной аппаратуры.- Кишинев: ЦАМ АН МССР, 1983.- С. 9.

45. Боряцевич В. И., Клисторин И. Ф., Филимонов С. Н. Информационные аспекты процесса генерации стохастических тестов // Известия Академии наук Молдавской ССР.- 1984.- * 1. С. 64-65.

46. Борщевич В. И., Клисторин И. Ф., Филимонов С. Н. Моделирование процесса псевдослучайного тестирования и его информационные аспекты // Электронное моделирование.- 1984.- * 2.- С. 57-61.

47. Борщевич В. И., Жданов В. Д., Сидоренко В. В., ^лимонов С. Н. Метод контроля микропроцессоров // Теория и практика конструирования и обеспечения надежности и качества электронной аппаратуры и приборов.- М.: Радио и связь, 1984.- С. 85-86.

48. Борщевич В. И., Клисторин И. Ф., Филимонов С. Н. Моделирование процесса генерации псевдослучайных тестов цифровых устройств посредством стохастических грамматик // Электронное моделирование.- 1985.- * 2.- С. 53-57.

49. Борщевич В. И., Филимонов С. Н., Александрова А. Ф. Программное обеспечение системы контроля цифровых устройств "Лингвистист-601 С" // Управляющие системы и машины.- 1985.- * 5. С. 47-50.

50. Борщевич В. И. Лингвистический подход к моделированиюинформационных потоков и задачи псевдослучайного тестирования // Электронное моделирование.- 1985.- Л 4.- С. 47-51.

51. Борщевич В. И., ^лимонов С. Н. Структурно-лингвистический подход к диагностированию микропроцессорных средств // Структурное и покомпонентное диагностирование устройств радиоэлектронной аппаратуры.- М.: ЦНИИТЭИ, 1986.- С. 12-14.

52. Борще вич В. И. Клисторин И. Ф., Филимонов С. Н. Структурно-лингвистический подход к псевдослучайному тестированию микропроцессорных устройств // Тез. докл. XXX Всесоюз. школы-семинара им. М. И. Гаврилова.- Кишинев: АН МССР, 1988.- С. 76-79.

53. Борщевич В. И., Жданов В. Д., Сидоренко В. В., Филимонов С. Н. Метод оценки достоверности псевдослучайного тестирования микропроцессорных устройств // Автоматика и вычислительная техника 1988.- * 4.- С. 76-81.

54. Борщевич В. И., Филимонов С. Н., Кирьяк Л. Т. Контролепригодность СБИС относительно методов стохастического функционального контроля // Тез. докл. XXX Всесоюз. школы-семинара им. М.А. Гаврилова.- Кишинев: АН МССР, 1988.- С. 124-125.

55. Борщевич В. И., Бодян Г. К., Филимонов С. Н. Метод максимума энтропии в задачах псевдослучайного тестирования микропроцессорных устройств // Приборостроение.- 1989.- Л 9.- С. 33-39.

56. Борщевич В. И., Кирьяк Л. Т., Филимонов С. Н. Применение псевдослучайно генерируемых воздействий для контроля каналов обмена информацией. // Вопросы радиоэлектроники: Сер. ЭВТ, 1989.-Вып. 3.- С. 12-16.

57. Борщевич В. И., Кирьяк Л. Т, Филимонов С. Н. Устройство контроля каналов обмена информацией псевдослучайными воздействиями // Тез. Республ. семинара "Вопросы разработки вычислительной техники". Кишинев: АН МССР, 1989.- С. 124.

58. Борщевич В. И., Филимонов С. Н., Жданов В. Д., Сидоренко В. В. Оценка достоверности стохастического контроля микропроцессоров // Электронное моделирование.- 1989.- * 1.- с. 55-59.

59. Борщевич В. И., Филимонов С. Н., Кирьяк Л. Т. Метод генерации тестовых программ, повышающий надежность процессоров // Вопросы специальной радиоэлектроники: Сер. ЭВТ, 1989.- Вып. 1.

60. Борцевич В. И. Структурно-лингвистический подход к псевдослучайному тестированию микропроцессорных устройств // Автоматика и телемеханика.- 1990.- * 5.- с. 147-156.

61. Борщевич В. И., Филимонов С. Н. Моделирование микропроцессоров для цели стохастического функционального контроля // Тез. Республ. научно-техн. конф. "Проблемы автоматизации контроля электронных устройств".- Киев: УкрНИИНТИ, 1990.- С. 4.

62. Борщевич В. И., Филимонов С. Н. Стохастические методы в диагностике // Автоматика и телемеханика.- 1992.- J§ 11.- С. 127-133.

63. Брамм П., Брамм Д. Микропроцессор 80386 и его программирование.- М.:Мир, 1990.- 448 с.

64. Бухараев Р. Г. Основы теории вероятностных автоматов.- М. : Наука, 1985.- 288 с.

65. Галлагер Р. Теория информации и надежная связь.- М.: Советское радио, 1974.- 720 с.

66. Городецкая О. М. Машинное моделирование и синтез тестов дня микропроцессоров с использованием микропрограмм.- Электронное моделирование.- 1985.- * 3.- С. 63-65.

67. ГОСТ 27.001-81. Ситема стандартов "Надежность в технике" Основные положения.- М.: Изд-во стандартов, 1981.- 3 с.

68. ГОСТ 27.103-83. Надежность в технике. Критерии отказов и предельных состояний. Основные положения.- М.: Изд-во стандартов, 1983.- 5с.

69. ГОСТ 20.911-75. Техническая диагностика. Основные термины и определения.- М.: Изд-во стандартов, 1978.- 14 с.

70. ГОСТ 19.919-74. Контроль автоматизированный технического состояния изделий авиационной техники. Термины и определения.- М.: Изд-во стандартов, 1974.- 12 с.

71. ГОСТ 20.417-75. Техническая диагностика. Общие положенияо порядке разработки систем диагностирования.- М.: Изд-во стандартов, 1975.- 6 с.

72. Гренандер У. Лекции по теории образов. Т.1. Синтез образов.- М.: Мир, 1979.- 384 с.

73. Гремальский А. А. Генерация случайных марковских процессов при стохастическом контроле микропроцессорных устройств // В сб.: Вероятность и ее применения.- Кишинев.: Штиинца.- 1990.с. 47-50.

74. Гремальский А. А. Теория и методы псевдослучайного функционального контроля дискретных устройств: Автореф. дис. на соискание уч. степени доктора техн. н./ Институт проблем моделирования в энергетике АН Украины.- Киев, 1992.- 34 с.

75. Гретцер Г. Общая теория решеток.- М.: Мир, 1982.- 452 с.

76. Гробман Д. М. Статистический способ определения полноты тестов // Тез. докл. IV Всесоюзного совещания по технической диагностике.- М.: ИНЭУМ, 1979.- С. 27-29.

77. Гросс М., Лантен Л. Теория формальных грамматик.- М.: Мир, 1971.- 279 с.

78. Гуляев В. А. Синтез функциональнных тестов для проверки блоков вычислительных машин // Автоматика и вычислительная техника.- 1977.- * 1. с. 78-82.

79. Гуляев В. А. Выбор математических моделей для построения тестовых программ проверки автоматизированных систем обработки данных // Точность и надежность кибернетических систем.- Киев: Наукова думка, 1977.- Вып. 5.- С,61-64.

80. Гуляев В. А. Некоторые вопросы организации процессов диагностирования в отказоустойчивых информационно-вычислительных системах // Электронное моделирование.- 1980.- * 4.- С. 49-55.

81. Гуляев В. А., Макаров С. М., Новиков В. С. Диагностика вычислительных машин.- Киев: Техн1ка, 1981167 с.

82. Гуляев В. А. Техническая диагностика управляющих систем.-Киев: Наукова думка, 1983.- 208 с.

83. Дынкин Е. В., Юшкевич А. А. Управляемые марковские процессы и их приложения.- М.: Наука, 1975.- 338 с.

84. Жуков М. В. Метод построения тестов дискретных устройств с помощью настраиваемого генератора случайных входных воздействий // АВТ.- 1980. * 4.- С. 122-131.

85. Жданов В. Д., Кройтор И. В., Филимонов С. Н. Подсистема синтеза тестовых программ для функционального контроля микропроцессоров // Тез. Республ. научно-техн. конф. "Проблемы автоматизации контроля электронных устройств".- Киев: УкрНИИНТИ, 1990.-С. 4-6.

86. Зайчикова О. В., Филатов В. Д., Филимонов С. Н. Специализированный процессор для системы контроля цифровой аппаратур! //

87. Тез. докл. Республ. семинара "Информационно-измерительные системыдля контроля и диагностики электронной аппаратуры".- Кишинев: ЦАМ АН МССР, 1983.- С. 12.

88. Исследование и разработка методов псевдослучайного тестирования сложных цифровых устройств : Отчет о НИР (заключит.) / Кишиневский политехи, ин-т им. С.Лазо; Руководитель Клисторин И. Ф.-* ГР 81013731; Инв. * 033779.- Кишинев, 1983.- 76 с.

89. Кирьяк Л. Т., Филимонов С. Н. Моделирование процессора для синтеза тестовых программ // Тез. докл. Все союз, научно-техн. конф. "Надежность машин, математическое и машиное моделированиезадач динамики. Моделирование 91п,- Кишинев: АН МССР, 1991.-С. 173.

90. Кирьяк Л. Т. Системы стохастического функционального контроля специализированных процессоров: Автореф. дис. канд. техн. н. // Кишиневский политехнический институт им. С.Лазо.- Кишинев, 1992.- 18 с.

91. Клисторин И. Ф., Борщевич В. И., Гремальский А. А. Автоматизированный контроль микропроцессорных средств ИБС // Тез. докл. V Всесоюзного симпозиума по модульным информационно-вычислительным системам.- Кишинев: Штиинца, 1985.- С. 29-30.

92. Клисторин И. Ф., Борщевич В. И., Филимонов С. Н. и др. Микропроцессор для управления режимами проверок при контроле цифровой аппаратуры // Приборы и системы управления.- 1985.- * 10.-с. 21-22.

93. Клисторин И. Ф., Борщевич В. И., Филимонов С. Н. и др. ИИС функционального контроля микропроцессоров // VII Всесоюзная научно-техн. конф. "Измерительные информационные системы" (ИИС-87) : Тез.докл.- Ташкент, 1987.- с. 80.

94. Клисторин И. Ф., Борщевич В. И., Филимонов С. Н. и др. Исследование свойств генераторов псевдослучайных последовательностей // Измерительная техника, 1989.- * 11.

95. Клисторин И. Ф., Борщевич В. И., Филимонов С. Н. Перспективное направление развития методов и средств контроля микропроцессорных устройств // Тез. докл. ХХЗII Всесоюз, школы по автоматизации научных исследований.- Кишинев: Штиинца, 1989.- С. 7-11.

96. Клисторин И. Ф., Борщевич В. И., Филимонов С. Н. Структурно-лингвистический подход перспективное направление развития методов и средств контроля микропроцессорных устройств // Измерения, контроль, автоматизация.- 1990.- * 3.- С. 38-43.

97. Колмогоров А. Н. Основные понятия теории вероятностей.- М.: Наука, 1974.- 120 с.

98. Колмогоров А. Н. Теория вероятностей и математическая статистика.- М.: Наука, 1986.- 534 с.

99. Колмогоров А. Н. Теория информации и теория алгоритмов.- М.: Наука, 1987.- 304 с.

100. Корнеева Т. В. Толковый словарь по метрологии, измерительной технике и управлению качеством.- М.: Русский язык, 1990.464 с.

101. Кофман А. Введение в прикладную комбинаторику.- М.: Наука, 1975.- 480 с.

102. Кульбак С. Теория информации и статистика. М.: Наука, 1967.- 408 с.

103. Кэпс И., Стаффорд P. VAX : Программирование на языке ассемблера и архитектура.- М.: Радио и связь, 1991.- 412 с.

104. Ландвебер П. Проблемы разрешения в грамматиках непосредственных составляющих // Кибернетический сборник. Вып. 5.- М.: Мир, 1968.- С. 103-127.

105. Матрицы и квадратичные формы. Основные понятия. Терминология / Отв. ред. М. А. Красносельский.- М.: Наука, 1990.- 80 с.

106. Марков А. А. Введение в теорию кодирования.- М.: Наука, 1982.- 192 с.

107. Математическое моделирование микропроцессоров для целей контроля: Отчет о НИР (заключит.) / Кишиневский политехи, ин-т им. С.Лазо; Руководитель Клисторин И. Ф.- * ГР 01840004673; Инв.028600053792.- Кишинев, 1985.- 59 с.

108. Морщинил Е. В. Статистические анализаторы процессов псевдослучайного тестирования цифровых устройств: Автореф. дис. на соискание уч. степени канд. техн. н. / Кишиневский политехи, ин-т им. С.Лазо.- Кишинев, 1988.- 18 с.

109. Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонентов // Автоматы.- М. 1956.- С. 68-139.

110. Осипов Г. С. О формировании модели для плохо структурированной предметной области // Изв. Ан СССР: Техн. кибернетика. 1987.- * 5.- С. 198-200.

111. ОСТ 11 305.009-84 Микропроцессорные средства вычислительной техники. Контроль технического состояния и поиск дефекта. Термины и определения.- М.: ВНИИ Электронстандарт, 1985.- 39 с.

112. Основы технической диагностики: Модели объектов, методы и алгоритмы диагноза, т. 1 / Под ред. П. П. Пархоменко.- М.: Энергия, 1976.- 464 с.

113. Пархоменко П. П., Согомонян Е. С. Основы технической диагностики: Оптимизация алгоритмов диагностирования, аппаратурные средства.- М.: Энергия, 1981.- 320 с.

114. Партхасаратхи Т., Рагхаван Т. Некоторые вопросы теории игр двух лиц.- М.: Мир, 1974.

115. Поиск неисправностей в логических ТЭЗ с помощью псевдослучайных кодов / Головистиков П. П., Громаковский В. А., Зимарев А. Н. и др. // Тез. 8-й Все союз, школы-семинара по технической диагностике.- Рига: Дом техники, 1981.- С. 23-26.

116. Преобразование псевдослучайных кодов как метод испытательных последовательностей для контроля логических ТЭЗ / Головистиков П. П., Громаковский В. А., Зимарев А. Н. и др. // Там же.1. С. 16-18.

117. Проблемно-ориентированный язык программирования ТЕСТ // Под ред. И. Ф. Клисторина.- Кишинев: Штиинца, 1978.- 128 с.

118. Романкевич А. М. О направленном поиске отказов в вероятностных системах диагностирования цифровых объектов // Управляющие системы и машины.- 1981.- * 1.- С. 47-49.

119. Романкевич А. М., Вилинский Ю. С. Система автоматизации синтеза псевдослучайных испытательных последовательностей для контроля отказов в логических блоках // Управляющие системы и машины. 1982.- Л 1.- С. 62-66.

120. Саломаа А. Жемчужины теории формальных языков.- М.: Мир, 1986.- 159 с.

121. Самофалов К. Г., Карачун Л. Ф., Лупанова Р. И., Рубаник С. М. Управляемый генератор псевдослучайных последовательностей для систем диагностирования цифровой аппаратуры // Управляющиесистемы и машины.- 1984.- #2.- С. 32-33.

122. Саядян Г. А. Автоматическая генерация входных данных для микропрограмм функционального контроля БИС // Электронное моделирование. 1984.- £ 2.- С. 68-71.

123. Саядян Г. А., Аракелян А. А., Алексанян Н. А. К вопросу автоматизации синтеза функциональных тестов для блоков микро-ЭВМ // Автоматика и вычислительная техника.- 1981.- * 1.- С. 29-33.

124. Севастьянов Б. А. Теория ветвящихся случайных процессов // Успехи мат. наук.- 1951.- * 6.- с. 47-99.

125. Сергеев В. Г., Щумский Л. Д. Универсальная аппаратура для динамического функционального контроля сложных логических блоков // Приборы и системы управления.- 1984.- Вып. 4.- С. 20-21.

126. Серийно выпускаемое и перспективное оборудование. М. ЦНИИТЭИ, 1978.- 102 с.

127. Сидоренко В. П., Руккас О .Д., Берштейн М. С., ЧИчирин Е. Н. Контрольно диагностический автоматический комплекс // При-бори и системы управления.- 1981.- * 5.- С. 4-6.

128. Систематизированный сборник отечественных и зарубежных средств технологического контроля электронной аппаратуры и изделий электронной техники.- Пенза: НИИ Контрольприбор, 1991.- 121 с.

129. Смит Б. Э. Джонсон М. Т. Архитектура и программирование микропроцессора INTEL 80386. М.: ТЭО Конкорд, 1992.- 334 с.

130. Тоценко В. Г. Алгоритм технического диагностирования цифровых устройств.- М.: Радио и связь , 1985.- 240 с.

131. Тоценко В. Г., Пимахов С. С. Метод построения тестов для микропроцессоров // Автоматизация контроля вычислительных устройств и систем: Тез. докл. Республ. научно-техн. конф.- Киев: РДНТП.- 1988.- С. 84-86.

132. Тоценко В. Г., Федорчук Ю. А. Применение экспертных систем для технической диагностики вычислительных систем // Тез. докл. Республ. научно-техн. конф. "Автоматизация контроля вычислительных устройств и систем".- Киев: РДНТП, 1988.- С. 86-87.

133. Уильяме Г. Б. Отладка микропроцессорных систем.- М.: Энергоатомиздат, 1988.- 253 с.

134. Успенский В. А., Семенов А. П. Теория алгоритмов: Основные открытия и приложения.- М.: Наука, 1987.- 288 с.

135. Феллер В. Введение в теорию вероятностей и ее приложения.- М.: Мир, 1964.- 498 с.

136. Филимонов С. Н. Аппроксимация псевдослучайных тестов цифровых устройств к заданному уровню качества // Контроль и диагностика цифровых узлов на микросхемах.- М.: ЦНИИТЭИ, 1983.- С.66-69.

137. Филимонов С. Н. Метод построения псевдослучайных тестов цифровых устройств // Тез. докл. VI Всесоюзн. научно-техн. конф. "Информационно-измерительные системы-83 (ИИС-83)".- Куйбышев: Дом техники, 1983.- С. 245-246.

138. Федер Дж. Плекс языки // Сб. Научная информация.- 1971.* 3.- С. 225-241. (Перевод с англ.)

139. Филимонов С. Н., Зайчикова 0. В., Филатов В. Д. Процессор, реализующий управляемые стохастические грамматики // Теория и практика конструирования и обеспечения надежности и качества электронной аппаратуры и приборов.- М.: Радио и связь, 1984.- С. 86.

140. Филимонов С. Н. Алгоритмы и средства управляемой генерации псевдослучайных воздействий в информационно-измерительной системе контроля цифровых устройств: Диссертация на соискание ученой степени канд. техн.н.- Кишинев, 1985.- 176 с,

141. Филимонов С. Н. Оценка полноты и оптимальности псевдослучайных тестов цифровых устройств // Управляющие системы и машины.- 1986.- * 3.- С. 40-42.

142. Филимонов С. Н. Применение языковых вхождений в задаче псевдослучайного тестирования цифровых устройств // Тез. докл. Республ. семинара "Техническая диагностика и эксплуатация вычислительных и управляющих систем".- Киев: АН УССР, 1989.

143. Филимонов С. Н., Гушан В. Ф., Макаров В. А. Исследование свойств генераторов псевдослучайных последовательностей // Тез. докл. Республ. научно-техн. конф.- Кишинев: MHO МОЛР, КПИ им. С.Лазо, 1989.- С. 13.

144. Фон Нейман Дж., Моргенштейн О. Теория игр и экономическое поведение.- М.: Наука.- 408 с.158. фу К. С. Лингвистический подход к распознаванию образов: Класифпсация и кластер.- М.: Мир, 1980.- С. 168-207.

145. Фу К. С. Структурные методы в распознавании образов.-М.: Мир, 1977.- 320 с.

146. Функциональный контроль и ремонт логических ячеек с помощью псевдослучайных кодов / П. П. Головистиков, В. А. Громаковский, Р. И. Дружинина и др.- М.: ИТМ и ВТ АН СССР, 1980.- 27 с.-(Препр. / Ин-т точной механики и вычислительной техники; N 2).

147. Харрис Т. Теория ветвящихся случайных процессов.- М.: Мир, 1966.- 355 с.

148. Хомский Н. Три модели описания языка // Кибернетический сборник.- Вып. 2.- М.: Изд-во инстранной лит, 1961.

149. Хомский Н. Формальные свойства грамматик // Кибернетический сборник: Новая серия.- Вып. 6.- М.: Мир, 1969.

150. Хомский Н. Аспекты теории синтаксиса / Пер. с англ.- М.: Изд-во Московского ун-та, 1972.- 259 с.

151. Чипулис В. П., Шаршунов С. Г. Построение тестов микропроцессоров: Проверка хранения и передачи данных // Автоматика и телемеханика.- 1986.- С. 139-150.

152. Чжен Г., Мэннинг Е., Метц Г. Диагностика отказов цифровых вычислительных систем.- М.: Мир, 1972.- 232 с.

153. Шеннон К. Э. Работы по теории информации и кибернетике.-М.: Изд-во иностранной лит., 1963.- С. 243-333.

154. Шепул Дж. Полные испытания специализированных ИС с помощью новых программных средств // Электроника.- 1990.- * 10.-с. 5-7.

155. Яковлев В. В., Федоров Р. Ф. Стохастические вычислительные машины.- Л.: Машиностроение, 1974.- 344 с.

156. Ярмолик В. Н. Контроль и диагностика цифровых узлов ЭВМ. Минск: Наука и техн1ка, 1988.- 238 с.

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

158. Минск: Наука и техн!ка, 1986.- 200 с.

159. Ясинявичене Г. М., Бургис Б. В., Мецаев Е. А., ГреОли-кас И.-А. К. Тестовый контроль микропроцессорных БИС на производстве.- М.: Радио и связь, 1989.- 120 с.

160. Abraham J. A., Fuchs К. W. Fault and Error Models for VLSI // IEEE Trans, on Сотр.- 1986.- * 5.- P. 639-654.

161. Agrawal P., Agrawal V. D. Probabilistic analysis о f random test generation method for lrredundant combinational logic networks // IEEE transactions on computers.- 1975.- V.C-24.- N7.-P. 691-695.

162. Agrawal V., Chung C. Probabllistlcalll qulded test generation // Int. Symp. on circuits and systems.- 1985. P. 687-690.

163. Agrawal V. D. Statistical testing // Testing and Diagnosis of VISI and ULSI.- Kluwer Academic Publishers.- 1988.- P. 3347.

164. Aho A. U., Ulman J. D. The theory of languages // J. Mat. Syst. Theory.- 1968.- V 2.- P. 97-125.

165. Bending M. J. HITEST: A knowledge-based test generation system // Proc. of Inc. test Conf.- 1986.- P. 85-92.

166. Bellon C., Gobbi J., Sander G. Automatic generation of microprocessor test programs // 19th Autom. Conf. Proc.-Las-Vegas, 1982.- P. 566-573.

167. Borscevlcl V. I., Fllimonov S. N., Olelnik V. L., Pusne- ее- V. A. Spectral analysis of fuzzy sets and appllcftlons in imagerecognition // Fuzzy Systems & A.I.Magazln.- V 1.- 1991.- N 3-4. v 6-7,

168. Borshevlch V. I., Kllstorin I. F., Sldorenco V. V.,

169. Flllmonov S. N. Structural and Linguistic Approach to Test Patterns Generation and Quality Evaluation // XVIII th Congress of the Romanian American Academy of Sciences and Arts.- Vol. 2.-Chlshlneu: ASM, 1993, P. 44.

170. Brahme D., Abraham A. Functional tesning of microprocessor // IEEE Trans, on Hardware Engineering.- 1984.- N 6.- P. 475-485.

171. Broadbend S. R., Hammersley J. M. Percolation processes: Crlstals and mazes // Processing of the Cembrldge Philosophical Society.- 1957.- * 53.- P. 629-641.

172. Chomsky N. On certain formal properties of grammars // Information and Control.- 1959.- N 2.- P. 137-167.

173. Chomscky N. A note on phrase-structure grammars // Ibid. P.393-395.

174. David R., Thevenod-Fosse P. Panorama des me tods de test non deterministes des circuits logique // R.A.I.R.O. Automatique systems analisls and control.- 1979.-V. 13.- N 1.- P. 5-38.

175. David R., Thevenod-Fosse P. Minimal detecting transition sequenses: Application to random testing // IEEE Trans, on Comp.-1980.- V. C-29.- P. 514-518.

176. Duran J. W. An evaluation of random testing // IEEE transactions on software engineering.- 1984.- V. SE-10.- N 4.-P. 438-444.

177. Fedi X., David R. Experimental results from random testing of mlcroprocesspr // Fault-Tolerant Сотр. Symp. (FTCS-14) Digest of Papers.- 1984.- P. 225-230.

178. Flllmonov S. N. The model of the stochastic generatorof the test programs and method of Its analyse // Computer Scinces of Moldova.- 1993.- V. 1.- * 3.- P. 81-86.

179. Pu K. S. Slntactic Pattern Recognition and Applications. New Jersy: Purdue University, 1982.- 245 p.

180. Gallay J., Crouzet Y., Vergnlault M. Phlslcal versus logical fault models MOS ISI circuits: Impact on their testability // IEEE Trans, on Сотр.- 1980.- V. C-29.- N 6.- P. 527-531.

181. Hess Ь. M., Tlmoc C. G. Hardware fault simulator for MP circuits // Electronics test.- 1984.- V. 7.- N 4.- P. 26.

182. Huang Т., Pu К. S. On stochastic context-free languages // Information Sci.- 1971.- N 3.- P. 201-224.

183. Kllstorln I. P., Borshchevlch V. I., Flllmonov S. N. Systems for testing of mlcrprocessors // Proc. of the 6th System Modelling Control Symp. (SMG-6).- Zakopane: Institute of Informatics, 1990.- P. 191-192.

184. Kllstorln I., Borshchevlch V., Flllmonov S. CAD subsystem with artificial intelligence elements // The Integration of Purpose Specialists* Training System and Automation Technical Systems of various Purpose.- Evpatory, Moscou: CNCRPS, 1990.- P. 18.

185. Llsanke R., Brglez F. Testability-driven random test-pattern generation // IEEE Trans, on Сотр.- 1987.- CAD-6.- * 6.-P. 1082-1087.

186. Luclw W. Can an user test LSI Microprocessor effectively. // IEEE Trans, on Manufacturing Technology.- 1976.- MFT-5.-* 1.- P. 21-23.

187. Membrain MB 7760S test system: Pierreboll.- 1986.- P. 2.

188. Mllgram D. L., Rosenfeld A. A note on "Grammers with

189. Coordinates" // Graphic Languages.- Amsterdam: North-Holland Publ.- 1972.- P. 112-137.

190. Parker K. P., McCluskey E. J. Analysis of loglk circuit with faults using input signal probabilities // IEEE Trans, on Сотр.- 1975.- V. C-24.- №5.- P. 573-578.

191. Parker K. P. Adaptive random test generation // J. des Auto and Fault-Tolerant Сотр.- 1976.- V. 1.- P. 62-83.

192. Parker K. P., McCluskey E. J. Seguential circuit output probabilities from regular expression // IEEE Trans, on Comp.-1978.- * 3.- P. 222-231.

193. P.S. Board Testers 3000 series. Fluke Catalog.- 1982/83.- John Fluke MFG Co. Inc.- P. 158-163.

194. Pat. 4125763 USA G 06 F 11/00 Automatic tester for microprocessor board // R. D. Drab lug, T. Y. Lam, C. 0. Heard. Fluke Trendar Corp.- * 815961; Filled 15.06.77; Pat 14.11.78.- 7 p.

195. Pat. 25535401 Frans. 4 G 06 F 11/30; G 06 F 7/58; G 01 R 31/28. Dispositiv de test aleatoire pour circuits loglques, notam-ment microprocesseurs / R. David, X. Fedi; Depot 13.01.83; Mise 19.04.85.- 8 p.

196. Pat. 4503536 USA, 2 G 06 F 11/00; US CI. 371/25. Digital circuit unit testing system utilising signatur analysis / G. W. Panz; General Dynamics; Filed 13.09.82; Pat. 5.03.85.- 9 p.

197. Pfaltz J. L., Rosenfeld A. Web grammars // Proc. Int. Joint Conf. Artificial Intelligence.- Washington: D.C., 1969.1. P 609-619.

198. Robach C., Sancler G., Alconard C. Microprocessor system testing // EUROMICRO J., 1979.- * 12.- P.31-37.

199. Robach С., Sancier G. Microprocessor fault testing // IEEE Test Conf. Philadelphia, 1990.- P.433-443.

200. Savlr J., Bardell P. H. On random pattern test length // IEEE Trans, on Сотр.- 1984.- V. C-33.- N 6.- P. 467-474.

201. Seshu S. On an improved diagnosis program // IEEE Trans 1965.- V. EC-14.- N 1.- P. 76-79.

202. Shedletsky J., McClusky E. The error latentsy of a fault in sequental digital circuits // IEEE Trans.- 1976.- V. C-25.1. P. 655-659.

203. Thatte S. M., Abraham J. A. A metodology for functional level testing of microprocessors // 8th Int. Conf. on Fault-Tolerant Сотр. Toulouse, 1978.- P. 90-95.

204. Thatte S. M., Abraham J. A. Test generation for miropro-cessors // IEEE Trans.- 1980.- V. C-29, N 6.- P. 429-441.

205. Thevenod-Fosse P. Asinchronus random testing of sequential networks // Int. Symp. on Fault-Tolerant Сотр. Systems. Toulouse, 1978.- P. 213.

206. Thevenod-Fosse P., David R. Random testing of the data processing section of a microprocessor // FTCS-11.- Portland, 1981.- P. 275-280.

207. Thevenod-Fosse P., David R. Random testing of the control section of a microprocessor // FTCS-13.- Milano, 1983.1. P. 336-373.

208. Timoc C., Stoff F., WIckman K., Hess L. Adaptive probabilistic testing of a microprocessor // ICCAD-83. IEEE International Conference Computer-aided Design.- Santa-Clara, 1983.- P. 71-72.

209. Timoc C.t Stoff P., Wickman K.f Hess L. Adaptiv Self-test for a microprocessor // Int. test Conf.: Test changing role.- Cherri-Hill: Silver Springs, 1983.- P. 701-703.

210. Williams T. W., Parker K. P. Testing logik network and designung for testability // IEEE Trans, on Сотр.- 1979.- V. 12.* 10.- P. 9-12.

211. Williams T. W., Parker K. P. Design for testability a survey // IEEE Trans, on Сотр.- 1982.- V. 31.- * 1.- P. 2-14.