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

ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ РАН

На правах рукописи

СТОЛОВ Евгений Львович

МЕТОДЫ КОМПАКТНОГО ТЕСТИРОВАНИЯ ЦИФРОВЫХ СХЕМ

05. 13. 13 - вычислительные машины,

комплексы, системы и сети

Автореферат

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

МОСКВА - 1993

Работа выполнена в ордена Ленина и ордена Трудового Красного Знамени Казанском государственном университете им. В. И. Ульянова-Ленина.

Официальные оппоненты: доктор технических наук,

профессор Горяшко А. П., доктор технических наук, профессор Литиков И. П. , доктор технических наук, ведущий научный сотрудник Сагалович Ю. Л.

Ведущее предприятие: Казанский ордена Трудового Красного Знамени авиационный институт им. А. Н. Туполева

Защита диссертации состоится "_"_

1993 г. в _ час. _мин. на заседании

специализированного совета ¿002,68.01 Института проблем управления по адресу 117806,- Москва, Профсоюзная ул.,65

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

■ Автореферат разослан "_"_199 г.

Ученый секретарь специализированного совета к.т.н. Е.В. Юркеьич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность теш диссертации. Повышение надежности вычислительных устройств в настоящее время становится одним из основных направлений развития вычислительной техники. Это связано, в первую очередь , с тем, что отказ управляющего устройства может привести к серьезным последствиям. Одним из средств,

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

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

Исследования велись в следующих направлениях.

I. Исследования различных способов генерации тестов

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

III. Дальнейшее развитие методов кольцевого тестирования.

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

По первому направлению решались следующие задачи:

1. Исследование свойств тестовой последовательности, порождаемой произвольной линейной последовательн остной машиной.

'2. Разработка методов реализации тестовых последовательностей с заданной зависимостью между соседними сигналами.

3. Разработка алгоритма построения

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

По второму направлению решались ояедуюаше задачи.

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

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

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

По третьему направлению решались следующие задачи.

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

2. Обеспечение цикличности диаграммы переходов автономного устройства.

3. Исследование различных способов сжатия информации при кольцевом- тестировании и вычисление достоверности контроля.

4. Аппаратная реализация методов кольцевого тестирования.

По четвертому направлению решались следующие задачи.

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

2. Аппаратная реализация оптимального сигнатурного анализатора.

Методы исследований. Методы исследований

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

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

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

Практическая ценность работы. На основе результатов, полученных в работе, удается выбрать комбинации генератора и сигнатурного анализатора в схеме встроенного тестирования ПЛМ, обеспечивавшее 100?< обнаружение одиночных неисправностей в блоке И; строить системы встроенного контроля для конкретных устройств, находить достоверность контроля, обеспечиваемой дополнительным оборудованием, в рамках выбранной модели неисправностей.

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

Достоверность научных положений. выводов и

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

Реализация результатов работы. Теоретические

исследования по данной тематике проводились в рамках госбюджетной теш "Оценка критических параметров и характеристик систем "(номер гос.регистрации 0186012346), в' которой автор участвовал как исполнитель, и в рамках Межвузовской целевой научно-технической программы "Повышение качества и надежности продукции , программного обеспечения ЭВМ и технических средств обучения" С "КНП 2000"). Работы выполнялись по темам: 4.20 "Математическая теория построения отказоустойчивых цифровых устройств " и 5.48 "Разработка методов построения систем встроенного контроля". По данным темам автор являлся руководителем работ,

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

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

- б -

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

Использование результатов диссертационной работы подтверждено соответствующими актами."

. Апробация работы. Результаты работы докладывались на 7 Всесоюзном заседании секции теории информации Центрального правления НТО РЭС имени А.С.Попова ( Новгород 1981), на конференции "Прогнозирование и диагностика в повышении эффективности производства и эксплуатации РЭА" (Москва 1982), на конференции "Автоматизация проектирования ЭВМ и систем " (Ереван 1983), на Всесоюзной конференции "Теория, методология и практика системных исследований" (Москва 1984), на Всесоюзной научно-технической конференции "Повышение качества и надежности ЭВМ" (Куйбышев 1989 ), на Всесоюзных школах-семинарах по технической диагностике (Ростов-на-Дону 1987, Саратов 1989, Новороссийск 1991), на семинаре по технической диагностике в Институте проблем моделирования в энергетике (Киев), на семинаре кафедры ЭВМ Казанского авиационного института, на Московском городском семинаре по технической диагностике, на семинаре по технической диагностике в Институте проблем управления (Москва) и на итоговых конференциях Казанского государственного университета.

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

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, списка литературы и приложения. Объем диссертации 308 страниц . В приложение включены материалы, подтверждающие использование материалов диссертации.

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

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

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

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

после того, как фирма Хьюлетт-Паккард опубликовала свой подход к задаче, согласно которому в качестве СА следовало использовать регистр сдвига с линейными обратными связями. Популярность данного подхода была связана, на наш взгляд, с.несколькими обстоятельствами:

1) аппаратная простота;

2) универсальность, поскольку качество проверки в рамках простейшей модели неисправностей не зависело от вида последовательности и ее длины;

3) особенность СА, заключающаяся в- том, что он всегда обнаруживал единичную ошибку в последовательности независимо от длины последовательности и положения ошибки в последовательности.

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

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

По мере развития теории, возникла идея наряду с регистрами сдвига рассматривать в качестве СА и другие устройства : счетчики единиц и перепадов типа 0->1; в случае многовыходовых схем устройства, подсчитывающие в выходной последовательности определенные комбинации сигналов на выходах . Наиболее общая постановка задачи, когда в качестве СА берется произвольный конечный автомат, предложена Ефимовым А. Н. и Лук-Зильберманом Е. В.. В качестве СА брался произвольный конечный автомат, на вход которого подавалась контролируемая последовательность, а сигнатурой называлось конечное состояние, в которое автомат перейдет из начального под действием этой последовательности.

Первоначально все неисправности устройства формулировались в терминах выходной последовательности, при этом основное внимание уделялось вероятностным моделям. В последнее время появились работы, в которых рассматриваются модели неисправностей ТУ иного типа: модели, связанные с физическими неисправностями, характерными для данных устройств- ССагалович Ю. Л. , Ярмолик В. Н., Дяченко 0.Н.и др.). Вычисление достоверности контроля с помощью СА в рамках указанных моделей оказалось нетривиальной задачей. Оказалось, что даже для

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

Кольцевое тестирование - это еще один подход к компактному тестированию, в некотором смысле являющийся альтернативой сигнатурному анализу. Основная его идея заключается в следующем. ТУ переводится в автономный режим путем подачи на его входы сигналов с выходов того же убтройства через некоторое добавочное устройство С ДУЗ (Уа.}1та БЬ. .Литиков И.П.,Латыпов Р.X. и др.) . Известно, что диаграмма переходов автономного устройства с конечным числом состояний разбивается на связные компоненты, причем каждый компонент содержит единственный цикл, возможно состоящий только из одного состояния. Может случиться, что

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

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

2) каким образом выбирать ДУ, чтобы диаграмма переходов имела нужный вид;

3) какова достоверность метода контроля.

Известны различные методы , позволяющие строить ДУ таким образом, чтобы диаграмма переходов автономного устройства стала циклической. Оказалось, что для комбинационных схем это можно сделать достаточно проста (Дитиков И. П.), но для устройств с памятью сложность ДУ в общем случае приближается к сложности ТУ. И. П. Литшсовым показано, что когда в качестве ТУ с памятью берется линейная последовательностная машина СЯМ), с помощью ДУ малой сложности можно построить автономное устройство с циклами нужной длины. Выбор в качестве сигнатуры кольцевой диаграммы набора длин циклов представляется весьма естественным", однако, такая сигнатура является не достаточно информативной. В диссертации предложены более тонкие характеристики для таких диаграмм.

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

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

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

В первой главе "Генераторы тестовых последовательностей" рассматриваются вопросы , связанные с генерацией тестовых последовательностей. Обычно для этих целей используются генераторы на основе регистра сдвига с линейными обратными связями, однако в некоторых ситуациях приходится использовать генераторы, построенные на иных принципах. Регистр сдвига с линейными обратными связями является частным случаем линейной последовательностной машины (ЛПМ). Теория ЛПМ в настоящее время продвинута достаточно далеко, и многие факты , относящиеся к генераторам на регистрах сдвига, получаются из общей теории весьма просто. В данной главе

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

Вначале приводятся основные факты, относящиеся к теории ЛПМ, которые используются. в последующем изложении. Основная цель данного пункта заключается в фиксации терминологии. Тестовая последовательность ^си,-1=0,1,... образуется по правилу

Г(и= с А1 1X0), (1)

где ¡Л0) - состояние ЛПМ в начальный момент времени, а € и А матрицы над полем 6Г(2). Предлагаются новые доказательства некоторых известных фактов из теории ЛПМ, что представляет интерес с методической точки зрения. Особенно следует отметить систематическое использование понятия показателя матрицы, то есть наименьшего натурального числа р, для которого &р= 0, где Я единичная матрица. Это позволило выявить природу некоторых фактов, известных в теории генераторов на регистрах сдвига, и перенести их на генераторы общей структуры.

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

Рассматриваются генераторы с матрицей внутренних связей , отвечающей максимальному показателю, равному 2П -1, где п - порядок матрицы. Такие матрицы назовем МП-матрицами. Заметим, что матрица будет МП-матрицей тогда и только тогда, когда ее характеристический многочлен примитивен. Эти генераторы являются аналогами генераторов М-последовательностей. Приведено простое доказательство известного факта об изоморфности поля 6Г(2П) множеству, состоящему из степеней МП-матрицы вместе с нулевой матрицей, где п - порядок матрицы,

относительно обычных матричных операций. На основании этого доказывается, что при С=0 при любом КОЖ) порождаются все ненулевые векторы длины п. Отмеченное свойство часто используется для построения генераторов тестов, когда требуется, чтобы в каждом такте порождались векторы длины п, и соседние векторы , по возможности, не имели бы общей части. Схемы подобного рода используются давно, однако, все обоснование правильности работы строится на свойствах М-последовательнсстей. В данном пункте предлагается прямой подход к исследованию на основе показателя матрицы. Изучены свойства генераторов, в которых матрица С отлична от единичной. В случае, когда С есть тхп матрица, т<п, на выходе получаются все векторы, включая нулевые. Для схем частного вида это обстоятельство было известно ранее, но здесь дается доказательство в общем случае.

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

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

Однако, нельзя утверждать то же самое для частей этих векторов. Пусть у'С-Ц} - вектор составленный из некоторых компонентов вектора Найдены легко

проверяемые условия независимости векторов у'СЦ) при

различных Ц. Для этого необходимо вычислить ранг специальной матрицы, которая строится по матрицам А, С и значениям Ц и tg.

Изучен еще один способ получения случайных последовательностей. Он заключается в преобразовании с помощью ЛПМ входного случайного потока. В общем случае найти распределение, которому подчиняется выходная последовательность, достаточно трудно, однако имеется один частный случай, в котором удается это сделать. Предположим, что на вход ЛПМ подается .случайная последовательность векторов <а(0), а(1),...> , причем все векторы имеют одно и то же распределение , векторы a(t) являются независимыми для различных значений аргумента. Допустим , что фиксируется некоторое начальное состояние ЛПМ. В этом случае последовательность состояний описывается стохастическим процессом, который является однородной цепью Маркова. Это обстоятельство отмечалось многими авторами и использовалось для построения датчиков случайных последовательностей. В данном пункте

рассматривается ЛПМ общего вида с невырожденной матрицей ffl, когда на ее вход подаются многомерные векторы. Часто данный подход применяется для получения независимых случайных величин с равномерным распределением. Для этого выбирают некоторый интервал 1q и снимают сигналы с выхода в моменты времени ktQ (Кирьянов Б.Ф., Мансуров P.M.). Основная задача заключается в установлении связи между Iq и параметрами, в терминах которых определяется независимость выходных сигналов. Пусть И - матрица переходов марковского процесса. Под параметрами, характеризующими независимость, понимается близость

матрицы 01 ик матрице (Hq, все элементы которой равны 1/гл, где га - число состояний ЛПМ. В данном пункте такая связь установлена для случаев одновходовой и многовходовой ЛПМ.

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

- То -

Такими статистиками могут быть , например, относительная частота появления данного сигнала на выходе или сочетания некоторых сигналов. Эта частота и обозначается как Р*. Найдены формулы для относительных частот некоторых событий , связанных с порождаемыми последовательностями , когда А - МП-матрица. Доказано, что Р* (уСО = г^) может принимать только одно из трех значений: О, 2п_г/С2п-П, С2п-Г-1 )/ С2п-1), где г - ранг с. Так Ее, как и при вероятностном подходе, возникает вопрос о существовании зависимости между векторам? и у(Ц).

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

относительной частотой. Если ранг^

число строк матрицы С,то справедливы формулы, аналогичные определяющим независимость. Например , при * ©

= 21 < п, где 1 -

Р^гСи^о.^+Ю^-р = РхСгС13=)'0)РхС)'С1)=г1)(2п-1)/2п

Решается задача генерирования псевдослучайных чисел с заданной зависимость» между последовательным!! векторами. При- разработке тестов для комбинационных схем подобная задача не возникает, однако, когда объект тестирования есть устройство с памятью, такая потребность может возникнуть. Кроме того, эта же задача возникает при отладке различного рода анализаторов случайных последовательностей. Предположим, что имеется генератор, который в процессе прохождения цикла порождает сигналы , у2.' • • • ■ • Положим

и4= Р'ЧуСи^Э. ч^ = Р'ЧгСи^.ги+П =

ги = ииА1г

Рассмотрим матрицу Г , в которой элемент П !,.!] =

Очевидно, что эта матрица является характеристикой выходной последовательности. Содержательный синея этой матрицы заключается в следующем: элемент F[1.JJ равен относительной частоте появления у, при условии, что перед этим на выходе был сигнал В этом смысле матрица !Г похожа на матрицу переходов цепи Маркова. Доказано, что если ¥ неотрицательная неразложимая матрица порядка 1 с рациональными элементами , обладающая свойством стохастичности, то существует генератор, порождающий выходную последовательность, которой отвечает данная матрица. Описана реализация такого генератора. В основе данной реализации лежит ЛПМ с некоторой матрицей внутренних связей Д. Показано, что любую комбинационную . схему с такой матрицей можно реализовать в специальном базисе из одного элемента.

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

где а0 *0, а^.-.а^ - некоторые фиксированные числа , а (х - независимые случайные величины. На основе известной теории была предложена процедура вычисления коэффициентов aj таким образом, чтобы процесс ^ имел нужную автокорреляционную функцию. При этом оказалось, что необходимое нормальное распределение случайных величин ? j можно аппроксимировать при достаточно больших к: с помощью случайных величин С<, принимающих только два значения. Для

генерирования последних была использована программа, имитирующая работу регистра сдвига с линейными обратными связями. Для оценки эффективности программы приведем результаты одного просчета. Десять полей размера 160 X 160 для к=14 были сгенерированы за 9 минут на машине ЕС 1045 и при этом потребовалось 130К оперативной памяти.

Глава 2 "Сигнатурные анализаторы на основе ЛПМ" посвящена изучению сигнатурных анализаторов, построенных на основе ЛПМ.

Приводятся основные определения, относящиеся к данной проблематике. Показана, что последовательность ошибок ■ ••'^N-1 не йУДет обнаружена СА на основе

ЛПМ с матрицами Л и В тогда и только тогда, когда эта последовательность есть решение однородной системы

й г =0, (2)

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

Изучается достоверность обнаружения ошибок малой кратности в векторной последовательности. Ситуация с простой ошибкой для обычного СА с одномерным входом известна. Оказалось, ■что то же самое верно и для произвольной ЛПМ с числом входов большим 1. Свойство обнаруживать .две ошибки в последовательности, длина которой меньше показателя, переносится на случай МП-матрицы й и одномерного входа, но перестает быть справедливым в общем случае. Следовательно, примитивность многочлена обратной связи в регистре сдвига, которая предполагается во многих работах по сигнатурному анализу , как правило, не оказывает влияния на число последовательностей, пропущенных при контроле.

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

последовательность появляется на входе СА, количество тех из них, которые удовлетворяют системе (2), может зависеть от вида матриц Л и 1В. Некоторые такие модели рассмотрены в последующих пункта".

Исследуются возможности СЛ с одним входо?^ при обнаружении ошибок заданной кратности, когда матрица А есть МП-матрица порядка п. Если длина входной последовательности М=2п-1, то задача сводится к отысканию в коде Хэмминга количества векторов заданного веса . Если же N > 2п-1, то получить простую формулу в общем случае не удается. Для случая М=(2п-1)5 предложен алгоритм вычисления числа пропущенных ошибочных векторов с ошибками малой кратности. Ранее подобная задача другим способом была решена Ю. Д. Сагаловичем. '

Та же задача решается для СА на основе

многовходсвой ЛПМ. Разработанный подход применяется затем для решения следующей задачи. Имеется ТУ с а выходами и порождаемая им последовательность длины N=2^-1, М=пш. Для контроля этой последовательности можно использовать один т-входовый СА размерности М или ш одновходовых СА размерности п. Суммарная размерность ЛПМ (число элементов памяти) в обоих случаях будет одной и той же. Доказано, что при больших п для ошибок кратности не более 4 первый подход является более эффективным.

Рассматривается задача обнаружения неисправностей в комбинационной схеме , когда в ней возможны физические дефекты. Первые результаты в этом направлении принадлежат О. Л. Сагаловичу и В.Н.Ярмолику. В диссертации рассмотрен случай неисправностей в ПЛМ, в результате которых отсутствует нужное соединение входа с некоторым столбцом в блоке И , либо наоборот присутствует лишнее соединение. При этом весьма неожиданным оказалось то обстоятельство, что на первый план выходит способ генерации тестовых последовательностей. Предположим, что сжатие осуществляется с помощью СА с МП-матрицей й. Оказалось, что если в качестве ' генератора тестов используется генератор на основе ЛПМ с матрицей йц, причем матрица ДГ* подобна й}, то во многих случаях указанные дефекты не

будут обнаружены. Для некоторых частных случаев на это обстоятельство было обращено внимание в работах Е.П.Калоши и В.Н.Ярмолика. Интересная ситуация возникает, когда .в качестве генератора берется двоичный счетчик, а в качестве СА -'ЛПМ. Впервые возможность аналитического описания зависимости между дефектами и сигнатурами , когда размерности счетчика и анализатора совпадают, отмечалась 0.Н. Дяченко. В диссертации найдены другие случаи, когда такие зависимости существуют. Положим д(х)=(хР©1)/Сх®1),р=2п-1, где - п размерность счетчика.. Допустим, что на вход СА поступает свертка по модулю 2 сигналов с выходов столбцов блока И. Если минимальный многочлен ЬСх) матрицы й в СА делит многочлен дСх), то все одиночные неисправности рассмотренного вида будут обнаружены. В частности, при п=8 в качестве ИСх) можно взять х2©х©1.

- Изучены другие вероятностные модели, и вычислены достоверности контроля с помощью СА на основе произвольных ЛПМ. Рассмотрены равновероятная модель, модели с независимыми ошибками' , модель с многомерным входом и зависимостью между компонентами .В диссертации рассмотрен случай, когда вероятности ошибок и длины последовательностей малы. В этом случае предельные теоремы перестают быть верными. Оказалось, что в этом случае результат зависит от структуры обратных связей СА. Дано описание программы, с помощью которой можно вычислить вероятности пропуска ошибок, когда длина регистра не превышает 16 , и приведены результаты вычислений. Предложен и аналитический подход для оценки вероятности пропуска ошибки.

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

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

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

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

Дается строгое определение метода, когда в качестве

ТУ берется конечный автомат. Предложена схема, реализующая этот метод. Она является универсальной в том смысле, что ее можно настроить на проверку любого ТУ. Ее модификация приводится в следующей главе. Проводится изучение достоверности контроля предлагаемым методом. В качестве ТУ берется ЛПМ и предполагается , что в результате неисправностей возникает снова .ЛПМ той же размерности. Отдельно рассматриваются неисправности, в результате которых происходит замена в ЛПМ структурной матрицы й->Й и матрицы входов В->Ё. Рассмотрен случай одновходовых ЛПМ. Показано, что метод лучше обнаруживает неисправности первого типа и хуже - второго. Даны рекомендации по выбору последовательностей а и а'. После этого разбирается случай многовходовой ЛПМ .

Глава 4 "Кольцевое тестирование" посвящена кольцевому тестированию. Приводятся основные

определения.Показана возможность тестирования устройств с памятью без установку начального состояния . Она основана на следующем замечании. Пусть автономная схема, включающая ТУ, находится в произвольном состоянии. Это состояние лежит в некотором компоненте связности, который содержит циклическую часть. Начав работать, автономное устройство переходит в состояния циклической части. Его функционирование определяется последовательностью проходимых состояний а = ,. .,Предположим, что существует функция р, обладающая свойством: р(аЗ=р(а)+^(а'), где а есть результат сцепления строк а и а'. В этом случае существует предельное значение

Ига (рСсО/И, Н->оо,

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

- ¡¿г -

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

Известна теорема Гсломба, обеспечивающая

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

диссертации найдены простые достаточные условия, при которых диаграмма будет циклической. Например, в случае поля СК(2П) достаточно, чтобы

Г(У-У2.....Уп1=госУг.....Уп3®Г1(>'2" ■ ■

где ГдС'/¡р,. . . , у) - произвольная функция, а на функцию

^(уд.....УпУ наложено единственное условие: сна не

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

В случае поля 0РС2) рассматриваются уравнения вида

у^ип = 1 = 1,2.....п-2.

у^и+П = ^Су^и.у^и.....упС I"! 1,

УПСШ) = г2(у1(1.),у2(1).....УПС1)).

Доказано, что для цикличности диаграммы необходимо и достаточно, чтобы

*УУ1'У2.....уп)= ^0СУ2-УЗ.....-'п-1Н>

гз 1'СУг-Ь.....Уп-1:)]2(Уг:Уз.....^п-Р^п, •2■

где ^ - произвольные Функции, удовлетворяющие у-злою.) Г11Г22®Г12Г2Г:1-

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

указанных устройств. Отдельно рассматриваются схемы, основанные на обобщениях для поля вГС4) и вГСг). Все предложенные схемы, в отличие от предложенных ранее, обладают важным свойством: в них имеются параметры, меняя которые можно менять диаграммы переходов автономной схемы. Данное свойство представляется существенным, поскольку режим тестирования накладывает определенные ограничения на вид циклов: эти циклы должны быть достаточно длинными, чтобы ТУ за время тестирования прошло через нужное множество состояний; если длина цикла слишком велика, то желательно ее уменьшить с тем, чтобы время тестирования не оказалось очень 1ольшим. В качестве примера приводится способ включения блока И ПЛМ, в автономное устройство, при котором обнаруживаются все неисправности .блока, возникающие в результате отсутствия нужного соединения входа со столбцам. При этом разработан способ модификации регистра сдвига, лежащего в основе схемы, позволяющий стандартизировать способ подключения ПЛМ к схеме контроля, независящий от конкретного программирования ПЛМ.'

Разработано несколько схем неполного дублирования при кольцевом тестировании. На циклической части диаграммы переходов 0' автономного устройства функция Ф, вычисляющая следующее состояние по предыдущему, является взаимно однозначной. Обозначим ограничение Ф на 0' через Ф'. Согласно определению, д(и=Ф'~*Ф(д(0) для точек из кольцевой части диаграммы. Это соотношение можно взять в качестве основы для построения схемы неполного дублирования. Отображение ф'--* задается вектор-функцией Ф^Са^.ад.. •'• .ап)^=1,... ,п, а вместо проверки справедливости отмеченного равенства можно ограничиться проверкой выполнения соотношений

а^Ф-'Ч-Са^,а2.....ап), ^еГ,

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

^>1<-а1'а2" •' •ап'!=^а1 ,а2.....где ~ некоторая

функция, а 1 - один "из индексов, то такую проверку назовем прямым неполным дублированием. Приведены схемы.

реализующие оба полхода, которые проиллюстрированы примерами.

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

Описываются схемы включения произвольного комбинационного устройства в генератор с кольцевой диаграммой перехода, работа которого основана на обобщении теоремы Голомба для поля 6ГС4), и приводятся оценки достоверности контроля с помощью таких схем. Оценка достоверности производится в терминах искажений диаграммы переходов автономного устройства, не обнаруживаемых при выбранном способе вычисления сигнатур. Для случая контроля устройства с памятью без установки начального состояния предложены общие формулы вычисления достоверности при произвольном выборе функции р, отображающей множество состояний в множество выходных сигналов. Рассмотрен пример, когда множество состояний разбито на конечное число классов, а <рСа) совпадает с вектором, в котором 1-ая компонента равна количеству элементов последовательности а, принадлежащих 1-ому классу. Показано, каким образом можно упростить процедуру проверки, если имеется доступ к памяти ДУ.

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

набор длин циклов, предлагается белее тонкая характеристика. Состояния циклов разбиваются на г классов, а в качестве сигнатуры берется набор чисел ,а2'■••• где ах ~ количество представителей 1-ого класса в дакнем цикле. Найдена оценка достоверности в этом случае. Наконец, находится оценка числа искаженных диаграмм перехода, пропущенных _ при неполном обратном дублировании. Она равна (5+1Г1'"1.^ . Для больших 5 последнее выражение можно заменить на е/Б. Рассмотрен метод тестирования, который ь идейном отношении близок к методу эквивалентных состояний, рассмотренному в главе 3. Предполагается, что ТУ может быть сброшено в начальное состояние ч0. Будем подавать на его входы постоянный сигнал х^. Поскольку входной сигнал не меняется во времени, ТУ ведет себя так же как и автономное устройство. Это означает, что через некоторое время после начала работы устройство войдет в цикл, длина которого зависит только от хг Таким образом, вычислив длину этого цикла и сравнив ее с найденной заранее длз исправного устройства, можно делать выводы об исправности ТУ. Предложены схема, реализующая данный подход , и способ оценки достоверности контроля указанным методом.

В главе 5 "Нелинейные сигнатурные анализаторы" рассматривается проблема построения СА, настраиваемого на проверку данной последовательности. При этом решается задача построения СА с предписанным размером памяти, обеспечивающего наибольшую достоверность при проверке заданной последовательности С оптимальный СА):

Приводятся основные определения. Под СА понимается конечный автомат МС X. 0,6, X, д0), а сигнатурой последовательности ы называется состояние , в которое перейдет М под действием Достоверность контроля

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

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

входного алфавита. Это матрица порядка |0|. в которой элемент в 1-ой строке и ,]-ом столбце равен количеству букв входного алфавита, переводящих автомат из состояния с номером 1 в состояние с номером j. В терминах этой матрицы определяется класс автоматов, изучаемых далее.

Затем вводятся С А с примитивной матрицей, и вычисляется предельное возможное значение достоверности , которое может быть достигнуто при . использовании нелинейного СА с п состояниями и примитивной матрицей соединений. Для больших длин последовательностей эта достоверность равна С5-1)/(5п-1), где 8 - количество букв во входном алфавите. Интересно отметить, что в отличие от линейного СА, это число зависит от количества элементов во входном алфавите. В случае двоичного алфавита получаем ^ 2~п. Если память СА реализована на к триггерах, то п=2,,с,,в то же время, для линейного СА с той же памятью значение достоверности ъ 2~'\ Найдены матрица соединений и. соответствующий ей СА, обеспечивающие указанную достоверность. Доказано, что эта матрица не зависит от проверяемой последовательности, но СА от этой последовательности зависит. Если входной алфавит состоит из Б букв, а СА имеет п состояний, то матрица имеет вид

Д=

Г5-1 1 0 . . О

3-1 0 1 . . О

¿-10 0' ' 1

15 0 0 ... О

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

Представлены реализации оптимального СА на основе счетчика и регистра сдвига .

'ТЕОРЕТИЧЕСКИЙ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

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

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

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

4. Найдены комбинации генератора и СА, обнаруживающие 100%' физических неисправностей, в результате которых появляется лишнее соединение либо исчезает нужное в блоках И ПЛМ. Показано, что сложность контрольной аппаратуры можно уменьшить, по сравнению с известными методами, без потери достоверности контроля.

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

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

Найдены оценки достоверности контроля, обеспечиваемой найденными методами.

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

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

Основные результаты диссертации опубликованы в следующих работах.

1.Столов Е. Л. Об одном классе генераторов псевдомарковских цепей// Исследования ' по прикладной математике.Казань: КГУ. - 1980, N 8. - С. 66-71.

2. Латыпов Р.Х., -Столов Е. Л. Статистический контроль линейных комбинационных схем//Испытания и защита радиоэлектронной аппаратуры. М.: ВЗМИ. -1983. -С.53-58.

3.Столов Е.Л.Комбинационные схемы, построенные в одноэлементном базисе//Исследования по прикладной математике, Казань: КГУ. -1984. -Л 12.-С.134-139.

4.Столов Е.Л. Линейные клеточные комбинационные схемы// Кибернетика.-1984. -И 2.-С. 106-107.

5. Мансуров Р.М., Столов Е. Л. Достоверность передачи данных в сетях ЭВМ при случайных ошибках // Автоматика и

" вьписл. техника. - 1985.-Я 2. - С. 56-57.

6.Мансуров Р. М. , Столов Е. Л. Кольцевое тестирование устройств с памятью без установки начального состояния //Автоматика и телемеханика.-1986.-Ы 8. - С. 163-165.

7.Столов Е. Л. Тестирование дискретных устройств с использованием эквивалентных состояний// Кибернетика 1986. -N1. - С. 123-124.

8. Мансуров Р.М., Столов Е.Л. Достоверность контроля мнеговыходовых цифровых схем методом сигнатур при случайных сбоях // Электрон, моделирование. - 1987. -И 1.

- С. 94-95.

9. Столов Е. Л. Достоверность обнаружения пакетов ошибок сигнатурным анализатором//Автоматика и телемеханика.-1987.-N 10.-С.182-184.

10. Столов Е. Л. .Чубаков Л.Г. Быстрая генерация случайных полей//Деп. ВИНИТИ.-N 1185-В88. -1988,10 с.

И.Латыпов Р.Х. ,Нурутдинов Ш.Р. .Столов Е.Л. .Фараджев Р. Г. Применение линейных последовательностных машин в системах диагностирования //Автоматика и телемеханика.-1988.-N 8.-С.3-27.

12.Нурутдинов Ш.Р. .Столов Е.Л. Реализация автомата

. асинхронной сеть».//Кибернетика. - 1988 - N 5. -С. 108-109.

13.Столов Е.Л. Обнаружение ошибок в выходной последовательности при кольцевом тестировании // Электронное моделирование. -1989.-N 1.-С.95-95.

14. Столов Е.Л. Кольцевое тестирование:схемы и достоверность//Автоматика и телемеханика. -1989. -N 1.-С. 155-161.

15. Столов Е.Л..Чубаков Л. Г. Алгоритм сегментации изображения на основе иерархического подхода к срединной линии//Кибернетика.-1990.-N 3.-С.115-117.

16. Столов Е. Л. Функциональное диагностирование комбинационны/ схем методами компактного тестирования// Автоматика и телемеханика. -1990. -N 4.-С. 161-165.

17.Столов Е.Л. Обнаружение ошибочных последовательностей нелинейным сигнатурным анализатором. //Автоматика и телемеханика.-1991.-N 7.-С.151-158

18.Столов Е.Л. Исчерпывающее тестирование и сигнатурный аналиэ//Автоматика и телемеханика.-1992. -N 6. -

. С.167-172.

19.А.С. 943722 СССР.МКИ3 G06 F 7/58. Генератор псевдослучайных чисел/ Баранов Г.Г., Захаров В. М.,

. Комаров Ю.С. .Столов Е.Л.

20.А.С. 1224992 СССР.МКИ3 НОЗ К 3/84. Генератор псевдослучайных чисел/ Баранов Г.Г., Захаров В.М., Комаров Ю.С. , Латыпов Р.Х. .Столов Е.Л.

21. А. С. 1108614 СССР.МКИ3 НОЗ К 3/84. Генератор псевдослучайных чисел/ Баранов Г.Г., Захаров В. М.,

Комаров Ю. С. , Латылов P. X., Столов Е. Л.

22.A.C. 1278854 СССР.МКИ3 G06 F 11/26. Устройство для контроля цифровых блоков / Мансуров Р. М. ,Столов £. Л. .Левченко Г. М..

23.А.С. 1619576 СССР.МКИ3 G06 F 11/16. Устройство для оперативного контроля цифровых блоков/Баранов Г. Г. , Латыпов Р.Х.,Столов Е.Л.

24.А.С. 1196876 СССР.МКИ3 G06 F 11/26. Устройство для контроля цифровых блоков / Бикмухаметов Р. Р. .Мансуров Р. М. .Столов Е. Л.

25. А. С. 1302285 СССР.МКИ3 G06 F 11/26. Устройство для контроля цифровых блоков/Латьшов Р.Х. .Мансуров P.M., Нурутдинов Ш. Р. .Столов Е. Л..

26.А. С. 1397920 СССР.МКИ3 G06 F 11/26. Устройство для встроенного контроля цифровых блоков / Баранов

Г. Г. .Комаров ¡0. С. , Латыпов P. X. .Нурутдинов Ш. Р. .Столов Е.Л.

27.А. С. 1339567 СССР.МКИ3 G06 F 11/26. Устройство для контроля цифровых блоков / Столов Е.Л..Мансуров P.M.

28.А.С. 1513446. СССР.МКИ3 G06 F 7/58.Генератор псевдослучайных чисел / Глова В.И..Мансуров P.M. .Столов Е.Л.

29.А. С. 1695304 СССР, МКИ3 G06 F 11/00. Устройство для контроля логических блоков/Латьшов Р.Х. .Нурутдинов Ш. Р. .Столов Е. Л..

30.А. С. 1714604 СССР, МКИ3 G06 F 11/00. Устройство для контроля двоичных последовательностей/Яатьтпов P. X. , Нурутдинов Ш. Р. , Столов Е. Л..

51.Столов Ё.Л. Реализация оптимального сигнатурного анализатора//Автоматика и телемеханика.-1992.- N11

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

В работах [5,83 автору принадлежит постановка задачи

и построение математической модели для распределения ошибок в последовательности.

В работе [2] автору принадлежит формула для

вероятности сбоя в случае линейной схемы с невырожденной

матрицей.

В работе [11] автору принадлежит раздел, посвященный кольцевому тестирований.

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

В работах [10,15] автору принадлежит идея генерации однородного изотропного поля с предписанными свойствами и ее реализация на ЭВМ.

В работе [12] автору принадлежит идея реализации полиномиальной функции параллельной структурой.

В работах [19-30] автору принадлежат математические модели устройств. Кроме того, в устройстве [29] автор предложил способ модификации сдвигового регистра.