Содержание к диссертации
Введение
Глава 1. Анализ современного состояния систем цифрового вычислительного синтеза частот и методов обеспечения отказоустойчивости 14
1.1 Классификация ЦВС и их декомпозиция на типовые узлы 14
1.2 Анализ современных методов обеспечения отказоустойчивости электронных средств 30
1.3 Анализ методов тестового диагностирования цифровых устройств 42
1.4 Задачи перспективных исследований 55
Глава 2. Анализ и выбор методов автоматизированной генерации тестов для основных узлов ЦВС 57
2.1 Выбор моделей дефектов и сигналов цифровых узлов ЦВС 57
2.1.1 Выбор модели дефектов цифровых узлов 57
2.1.2 Выбор модели сигналов цифровых узлов 64
2.2 Выбор метода генерации тестов для основных узлов ЦВС 71
Глава 3. Анализ и программная реализация методов документирования для поиска неисправностей на этапе производства ЦВС 81
3.1 Выбор и обоснование типа диагностического словаря дляСАГТ 81
3.2 Использование сигнатурного анализа для сокращения объема и сложности диагностических словарей 86
3.3 Программная реализация метода сокращения объема диагностических словарей с помощью сигнатурного анализа 91
Глава 4. Разработка и экспериментальное исследование структуры самотестируемой БИС ЦВС и средств автоматизированного поиска неисправностей 98
4.1 Разработка структуры самотестируемой БИС ЦВС
Разработка программного обеспечения для автоматизированного поиска неисправностей. Заключение
Литература
Сведения о внедрении результатов
- Анализ современных методов обеспечения отказоустойчивости электронных средств
- Анализ методов тестового диагностирования цифровых устройств
- Выбор метода генерации тестов для основных узлов ЦВС
- Использование сигнатурного анализа для сокращения объема и сложности диагностических словарей
Введение к работе
Актуальность работы.
В настоящее время в бортовых РЭС летательных аппаратов для нормального функционирования навигационных, связных и других систем подчас необходимо наличие нескольких периодических гармонических сигналов различной частоты, которые должны быть высокостабильными. Для решения этой задачи обычные генераторы неприменимы, так как имеют большие габариты и массу, и, кроме того, не могут обеспечить требуемой синхронности и стабильности частоты сигналов. Поэтому для указанных целей применяются цифровые вычислительные синтезаторы (ЦВС), лишенные всех вышеперечисленных недостатков. Такие достоинства ЦВС, как устойчивость к воздействию дестабилизирующих факторов, малое время переключения частот при непрерывности фазы формируемых колебаний, способность формирования сложных сигналов, возможность полной микроминиатюризации и программируемости параметров, позволили существенно повысить технико-экономические показатели многих радиотехнических систем.
Основы теории и техники вычислительного метода синтеза частот, заложенные зарубежными специалистами (А. Боли, В. Кроупом, Б. Гоулдом, Дж. Тирнеем, Р. Хоскиным, Н. Купером), успешно разрабатывались видными отечественными учеными Н.И. Чистяковым, В.В. Шахгильдяном, И.Н. Гуревичем, М.И. Жодзинским, В.Н. Кочемасовым и другими. Весомый вклад в это направление внесли ученые нижегородской (горьковской) школы синтеза частот: Ю.И. Алехин, Ю.К. Богатырев, В.И. Логинов, С.С. Сухотин, С.Я. Шишов, В.С. Станков, Н.П. Ямпурин.
В то же время, согласно современным требованиям Международного Авиационного Комитета, к эксплуатации не принимаются системы, не имеющие средств самодиагностики, поскольку их выход из строя может иметь фатальные последствия для связанного с ними объекта. Основы теории контролепригодности и диагностики систем при помощи сигнатурного анализа заложены в работах Р. Фроверка и Х. Надига и успешно развиты отечественными учеными П.П. Пархоменко, К.Г. Кирьяновым, У.С. Согомоняном и другими.
Однако, вопрос возможности быстрого и достоверного контроля работоспособности ЦВС в интегральном исполнении в процессе производства и эксплуатации до нынешнего времени не решен. Недостаточно развиты на современном уровне компьютерной техники средства автоматизированного контроля и обеспечения отказоустойчивости ЦВС на этапе проектирования. Разработке структуры перспективных самотестируемых ЦВС посвящена диссертационная работа.
Цель и задачи работы
Целью настоящей работы является обеспечение самотестируемости ЦВС путем совершенствования известных и создания новых эффективных структур, а также программного обеспечения для автоматизированного контроля на всех этапах жизненного цикла ЦВС.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
анализ известных структур ЦВС с целью определения обобщенной структуры ЦВС для ее декомпозиции на отдельные узлы.
анализ методов обеспечения самодиагностики ЭС с целью выбора оптимального применительно к технике ЦВС.
анализ методов генерации тестов для цифровых схем с целью выбора оптимального для программной реализации ПЭВМ.
разработка программного модуля для автоматизированной генерации тестов на ПЭВМ на базе процессоров семейства Intel Pentium.
разработка структуры ЦВС сложных сигналов для перспективных систем связи с элементами самотестирования.
возможное внедрение в промышленность разработанной автором структуры самотестируемых ЦВС частот и сигналов.
На защиту выносятся:
-
Новые структурные решения построения отечественной БИС ЦВС, которая, на момент ее разработки, превосходила лучшие зарубежные аналоги по уровню обеспечения контролепригодности.
-
Алгоритм моделирования сигнатурного анализатора, предусматривающий возможность выбора разрядности анализатора и его вида (последовательный или параллельный).
-
Система автоматизированной генерации тестов для цифровых устройств, позволяющая моделировать работу проектируемой схемы и синтезировать для нее оптимальный тест.
Методы исследований
При решении поставленных задач в работе использованы методы математичес-
кой логики, математического моделирования, теории надежности, теории вероятностей и теории информации. Ряд результатов получен экспериментально.
Научная новизна
Научная новизна работы состоит в следующем:
1. Предложена структура перспективного самотестируемого ЦВС. Ее отличительной особенностью является возможность самоконтроля схемы в процессе производства и эксплуатации. В качестве метода обеспечения отказоустойчивости использовано контролепригодное проектирование и методика избыточного кодирования.
2. Предложен алгоритм моделирования сигнатурного анализатора, предусматривающий возможность выбора разрядности анализатора и его вида (последовательный или параллельный).
3. Разработана структура и состав математического и программного обеспечения системы автоматизированной генерации тестов для диагностирования цифровых узлов ЦВС на ПЭВМ на базе процессоров семейства Intel Pentium с комплектом штатной периферии.
Практическая значимость
-
Разработаны структурные решения построения самотестируемых ЦВС.
-
Предложена и реализована система автоматизированной генерации тестов (САГТ) для цифровых устройств на ПЭВМ на базе процессоров Intel Pentium. Система реализована на основе компактной и быстродействующей версии D - алгоритма на языке С++. Основной особенностью системы является возможность интерактивного синтеза тестов. Обозначены основные направления дальнейших исследований в этой области в связи с внедрением CALS – технологий.
-
Разработан и программно реализован на С++ алгоритм моделирования сигнатурного анализатора, предусматривающий возможность выбора его разрядности и вида (последовательный или параллельный). Данная реализация интегрируется с разработанной САГТ и служит для уменьшения объема диагностических словарей точного соответствия.
Реализация результатов работы
Результаты исследований, изложенные в диссертационной работе, использованы в НПП «Полет» при разработке возбудителей для радиопередающих устройств. Кроме того, материалы диссертации используются в учебном процессе Арзамасского политехнического института (филиала) Нижегородского государственного технического университета им. Р.Е. Алексеева.
Апробация работы
Основные результаты работы докладывались и обсуждались:
-
На международных научно-технических конференциях:
IV Международной научно-технической конференции «Радио, навигация и связь», Воронеж, 1998 г.
IV Международной молодежной НТК «Будущее технической науки», Н.Новгород, НГТУ, 2005 г.
-
На Всероссийских научно-технических конференциях:
Всероссийской научно-технической конференции "Технологии в машино- и приборостроении на рубеже XXI века". Арзамас, 2000г.;
Всероссийской научно-технической конференции "Аэрокосмическая техника и высокие технологии – 2000". Пермь, 2000г.;
LV, LVI, LXI, LXIII Всероссийских научных сессиях РНТО РЭС им. А.С.Попова, посвященных Дню радио. Москва, 2000, 2001, 2006, 2008, 2009 гг.;
Всероссийских научно-технических конференциях «Прогрессивные технологии в машино- и приборостроении», Нижний Новгород – Арзамас, 2001, 2002, 2004, 2005 гг.
15 Межрегиональной конференции Московского и нижегородского отделений НТОРЭС им А.С. Попова «Обработка сигналов в системах наземной радиосвязи и оповещения», Москва - Н.Новгород: РНТО РЭС им. А.С. Попова, 2007 г.
Всероссийском научно-техническом семинаре «Системы синхронизации, формирования и обработки сигналов для связи и вещания», г. Воронеж, 2009 г.
Публикации
По материалам диссертационной работы опубликовано 17 научных статей.
Структура и объём работы
Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 225 наименований и приложений. Общий объём работы 130 страниц, основной текст изложен на 118 страницах машинописного текста. Диссертация содержит 26 рисунков и 9 таблиц на 28 страницах.
Анализ современных методов обеспечения отказоустойчивости электронных средств
Под отказом системы понимается [81, 203, 220] ошибочное состояние ее аппаратного или программного обеспечения. Исследование этого определения показывает, что источники возможных ошибок имеют несколько уровней, которые можно связать с процессом разработки системы. Высшим уровнем, с которого начинается разработка, является исполнительская формулировка задачи, от которой зависят пути решения. На основе принятой формулировки (спецификации) разрабатываются конкретные алгоритмы и архитектура системы. Затем проводится детальная разработка аппаратного и математического обеспечения системы. Следующей ступенью является процесс конструирования, изготовления и испытания аппаратного и математического обеспечения, конечным результатом которого является законченная рабочая система. Проблемы, разрешаемые на любом из уровней разработки, могут привести к следующим типам ошибок (рис. 1.11):- ошибки спецификации, включая ошибки выбора алгоритма, архитектуры и ошибки в спцификации аппаратного и программного обеспечения.- ошибки исполнения, т.е. процесса преобразования спецификаций в аппаратуру и программы. В процессе этого преобразования часто вносятся ошибки в результате плохого конструирования, отбора компонент, монтажа или неправильного кодирования матобеспечения.- дефекты компонентов: производственные дефекты, дефекты полупроводниковых приборов, перегорание компонентов и старение.- отказы в результате внешних воздействий: радиация, электромагнитные воздействия, механические повреждения или экстремальные условия внешней среды.
Четыре явных случая: ошибки спецификации, исполнения, внешние воздействия и отказы компонент приводят к дефектам в математическом и аппаратном обеспечении. Действие дефектовпроявляется в погрешности, изменяющей правильные значения данных в системе. В результате поведение системы становится неправильным или неопределенным.
Существуют три способа улучшить или поддержать нормальное функционирование системы: предотвращение отказов, маскировка отказов, отказоустойчивость.
Как следует из приведенной выше классификации, задачи по предотвращению отказов должны решаться на стадии разработки элементной базы (защита от внешних воздействий и предотвращение отказа компонент) и на стадии разработки УЦОС (исключение ошибок спецификации и исполнения).
Ограничившись периодом нормальной эксплуатации аппаратуры, для которого характерна модель внезапных отказов и экспоненциальный закон их распределения [173], для устройства, имеющего в своем составе N компонентов с одинаковыми интенсивностями отказов А,, имеем среднее время наработки до отказа
Поскольку величина А, при любом уровне развития технологии ограничена снизу в силу физических причин, основные из которых рассматриваются в [1, 2, 83, 149], легко видеть, что средняя наработка на отказ убывает обратно пропорционально сложности системы, характеризуемой количеством входящих в нее компонентов N.
Исходя из того факта, что, как правило, разработчик УЦОС не имеет возможности влиять на базовую величину А, применяемых им компонентов, легко сделать вывод, что единственным реальным путем увеличения среднего времени безотказной работы сложных УЦОС является придание этим устройствам свойств отказоустойчивости.
Отказоустойчивость характеризуется четырьмя основными признаками [203]:- обнаружение отказа - способность системы распознать тот факт, что отказ произошел. Обнаружение ошибки чаще всего необходимо для приведения в действие каких-либо механизмов восстановления;- локализация отказа - способность системы определить, где произошел отказ; - маскировка отказа - процесс изоляции отказа и предотвращения распространения его эффекта в системе;- «перекрытие» отказа - способность системы сохранять или восстанавливать работоспособность посредством реконфигурации даже в присутствии отказов.
Ключевой составляющей техники отказоустойчивости являетсяизбыточность, т.е. добавление информации, ресурсов или временисверх того, что необходимо для нормального функционированиясистемы. Различают несколько видов избыточности:информационная, аппаратная, программная и временная. Рассмотрим кратко основные особенности этих видов избыточности.
Информационная избыточность заключается в применении кодов, обнаруживающих и исправляющих ошибки. Принципы использования кодирования для повышения надежности цифровых устройств изложены в [150, 169]. В [177] описано применение при построении самокорректирующегося компьютера кодов «2 из 5».
Широко известные коды Хемминга позволяют обнаруживать двойные и исправлять однократные ошибки. Эти коды образуются добавлением к m информационным битам к проверочных.
Широкое применение для обнаружения ошибок находят также разные формы контрольных сумм, вычисляемые для целого блока данных.
Все перечисленные, а также некоторые другие коды используются для проверки логических, запоминающих устройств и при передаче данных по линиям связи.
Для проверки устройств, выполняющих арифметические операции, используются арифметические коды. В основном это коды, переводящие слово данных X в кодовое слово А(Х) такое, что A(XWY)=A(X)GA(Y), где и - какая-либо арифметическая операция, а Y - проверочное слово. В [54] для использования в линейных процессорных матрицах предлагается метод кодирования на основе взвешенной контрольной суммы.
Кроме вышеперечисленных, для обнаружения и коррекции ошибок используются и другие коды. Общим недостатком применяемых в настоящее время кодов, применительно к ЦВС, является невозможность определения точного места отказа. Эти коды способны лишь обнаружить наличие ошибки и, в некоторых случаях исправить ее.
Аппаратурная избыточность является наиболее общим приемом обеспечения отказоустойчивости и заключается в физическом резервировании аппаратных средств. Все более широкому распространению этого метода способствует непрерывное снижение стоимости полупроводниковых компонентов.
Основываясь на главных чертах отказоустойчивости (обнаружение, локализация, маскировка отказов и реконфигурация), различают три основные формы резервирования: пассивную, активную и гибридную. Пассивный метод маскирует ошибки, но исключает обнаружение, локализацию и замену отказавшего модуля. Активный метод не маскирует ошибки, но обнаруживает и локализует источники ошибок, создавая тем самым условия для подключения запасного компонента взамен отказавшего. Третий - гибридный метод, соединяет привлекательные особенности обоих предыдущих. Он использует маскировку ошибок для предотвращения неправильных значений на выходе блока и обнаружение, позволяющее включить запасной модуль взамен отказавшего.
Широко известным примером пассивного метода является тройное модульное резервирование (ТМР), описанное в [149].
Возможность ТМР - маскировка одиночного отказа посредством утроения аппаратуры и голосования между результатами. При этом используется стандартное мажоритарное голосование. Голосование может проводиться как при помощи аппаратных средств (мажоритарный элемент), так и программным способом.
Концепция активного резервирования [149] объединяет способность к обнаружению и регенерации отказов ценой исключения способности маскировать ошибки. Реализацией данной концепции являются:
Анализ методов тестового диагностирования цифровых устройств
В современных цифровых электронных средствах (ЭС) на базе БИС, СБИС и БГИС существует и постоянно увеличивается громадное разнообразие схемотехнических решений [28, 66, 72, 90, 93, 94, 98, 101, 147, 179, 184, 209]. Причем их воплощение средствами цифровой техники, как правило, сложнее для восприятия, чем схемы аналоговой РЭА [175]. Эти обстоятельства затрудняют понимание промышленным персоналом, занятым производственным контролем, принципов работы отдельных узлов ЭС, что естественно отражается на качестве интуитивных процедур контроля.
Необходимо также учитывать сокращение сроков морального старения ЭС. Для цифровой техники они составляет примерно 3..5 лет [30, 78, 101, 170], а через 5...7 лет происходит полное обновление ее технологической и элементной базы, конструктивных и схемотехнических методов построения, структуры математического обеспечения (МО) [28, 95]. Быстрая смена поколений цифровой аппаратуры препятствует накоплению и распространению опыта интуитивных процедур контроля. Поэтому на практике он довольно часто носит самый общий, точнее говоря, функциональный характер. Это допустимо при эксплуатации, но недостаточно в процессе производства, когда требуется контролировать работоспособность изделий.
Повышение функциональной значимости ЭС происходит не только вследствие роста степени интеграции ИС, но и за счет увеличения размеров его конструктивов, благодаря которому они могут содержать больше компонентов. Теоретические исследования [28, 93, 133] и практический опыт [175, 218] показывают, что с ростом количества компонентов возрастает среднее число неисправностей в устройстве, а также быстро уменьшается процент исправных устройств (выход годных). Понятно, что проверка работоспособности микроэлектронных устройств вручную при наличии подобной закономерности будет отнимать все больше времени. А поскольку время, отводимое на контроль, в условиях производства всегда ограничено, неизбежно будет страдать его качество [93].
Рассмотренные значительно осложнили проблему диагностирования цифровых устройств, и промышленные предприятия были поставлены перед необходимостью его автоматизации. Разработка формальных методов тестового диагностирования (ТД), легко реализуемых автоматическим оборудованием, позволила персоналу невысокой квалификации контролировать в приемлемые сроки работоспособность цифровых устройств современной ЭС, выпускаемых крупными сериями и широкой номенклатурой [25, 26, 57, 74, 151, 214].
В основе формальных методов ТД лежит известный кибернетический принцип, согласно которому объект диагностирования (ОД) — цифровое устройство любой степени сложности или его часть — рассматривается как «черный ящик» со множеством входов и выходов и неизвестной внутренней структурой [25, 34, 57, 58, 98, 101, 133, 209]. Работоспособность «черного ящика» устанавливается путем подачи на его входы специальным образом сформированного набора сигналов и наблюдения за корректностью ответных сигналов на выходах. Для краткости в дальнейшем входные наборы сигналов будем называть воздействиями, а соответствующие им отклики на выходах - реакциями.
Каждый из перечисленных методов характеризуется определенным сочетанием способов формирования воздействий и получения реакций. Применяемые сочетания представлены в табл. 1.1, составленной автором на основе анализа и систематизации сведений, содержащихся в литературе [25, 34, 57, 89, 133, 135, 145, 181, 195, 197, 209].
Метод ТД сравнением с эталоном предполагает наличие заведомо годного устройства того же типа, что и контролируемое. На этот «безупречный эталон», или «золотой стандарт», как он еще иногда называется в литературе, и ОД «подаются одни и те же входные сигналы от общего источника, а выходные сигналы сравниваются и фиксируются на компараторах» [89]. Поскольку в цифровой технике компаратором чаще всего служит схема сложения по модулю 2, сравнение с эталоном в ряде источников фигурирует как метод исключающего или [133].
В этом методе в качестве тестовых воздействий чаще всего используются тривиальный последовательный двоичный код (ТП код) и псевдослучайные последовательности (ПСП коды). Генерация ТП кода осуществляется с помощь двоичного счетчика, число разрядов которого равно числу входов контролируемого устройства [57]. ПСП коды получают, применяя линейный сдвиговый регистр (ЛСР) с обратными связями (ОС) [40, 57, 134, 140, 174]. Существуют также программные методы генерации ПС кодов [34, 159].
Использование ТП кодов целесообразно для контроля работоспособности цифровых устройств ЭС с небольшим числом входов (менее 30). Когда число входов велико (30...2000), больший эффект дают ПСП коды [57].
Тесты на основе ТП и ПСП кодов получаются обычно слишком длинными, так как они предназначены для простого перебора всех возможных состояний цифровой последовательностной схемы, число которых может быть очень велико. Ограничение длины тестов ведет к снижению их полноты.
Наибольшие трудности применения ТП и ПСП кодов вызывает существование в последовательностных схемах запрещенных входных наборов. Подача такого набора может привести неопределенному состоянию каких либо выходов (например, RS -триггеров) или к возникновению динамических состязаний сигналов («гонке фронтов») [40, 41, 72, 145, 152]. Удаление запрещенных комбинаций из стандартных ТП и ПСП последовательностей является довольно сложной задачей [57].
Выбор метода генерации тестов для основных узлов ЦВС
Процесс тестового диагностирования (ТД) можно разделить на три этапа [3,5]:- выбор тестовых воздействий;- проведение испытания (подача на входы ОД тестовой последовательности и контроль откликов на выходах);- анализ полученных результатов и получение технического диагноза в виде заключения типа «да/нет» (объект работоспособен/неработоспособен) или объект неработоспособен и в нем имеется такая - то неисправность.
В предыдущей главе было показано, что наилучшим способом обеспечения отказоустойчивости цифровых БИС является их самодиагностирование путем сравнения с кодовым эталоном, наиболее простым методом организации которого является СА на основе генерации ПСП. Однако, на этапе производства, для этой же цели может быть использован и генератор тестовых воздействий с применением специально разработанного хранимого теста, который обладает большей эффективностью по сравнению с ПСП. При ТД с применением хранимого теста определяющим является первый этап. Именно он должен выполняться на стадии проектирования ЦВС. Два других этапа - неотъемлемая часть процесса производства и эксплуатации, и их эффективность во многом зависит от правильного выбора и использования алгоритма генерации тестов.
Подробный анализ состояния проблемы автоматической генерации тестов для РЭС за рубежом приведен в работе [182] на материале 18 ведущих компаний и государственных лабораторий, из которых три расположены в Японии, три - в Европе, а остальные в США. Результаты анализа свидетельствуют о том, что генерация тестов, занимающая в среднем от 10 до 22% времени полного цикла автоматизированного проектирования РЭС, остается одной из наименее развитых областей, в которой наблюдается повышенная деловая активность многих фирм и научно - исследовательских учреждений. Точные данные для отечественной промышленности автору неизвестны, но по некоторым данным [5, 26, 35, 111, 114, 145, 207] можно предположить, что и в России наблюдается примерно такая же картина.
В настоящее время изготовители РЭС вкладывают большие средства в САПР и рабочие места разработчиков на базе ПЭВМ, позволяющие снизить стоимость и сократить продолжительность работ, осуществляемых конструкторско - технологическими подразделениями предприятий. Однако, получаемая при этом выгода быстро теряется по мере дополнительных затрат на закупку устройств и разработку программного обеспечения для подразделений, занимающихся испытаниями РЭС. Между тем, давно известно [37, 74, 151], что САПР и система автоматизированной генерации тестов (САГТ) выполняют весьма сходные функции. Необходима интеграция САПР и САГТ в единую систему (далее ИСАПРГТ), программные модули которой должны функционировать на АРМ в тесной взаимосвязи, совместно используя его базу данных [141, 154]. Характерный пример, приведенный в [74], показывает, что за счет этого затраты на автоматизированное проектирование могут быть снижены примерно на 24%.
Следует отметить, что интеграция САПР и САГТ на основе единой базы данных способна не только снизить производственные затраты и улучшить качество продукции, но и создает условия, позволяющие улучшить сам производственный процесс. В настоящее время при автоматизированном контроле годные изделия просто отделяются от бракованных. На предприятии же, с интегрированной ИСАПРГТ можно будет отслеживать любые изменения характеристик изделия и использовать эти данные с целью корректировки на ранних стадиях проектирования и производства, чтобы в реальном времени совершенствовать технологические процессы и повышать выход годных [74].
Кроме того, при проектировании схемы следует учитывать ее тестируемость при эксплуатации. Сложность СБИС растет неизмеримо быстрее, нежели число доступных для контроля внешних контактов. Полное тестирование для СБИС вообще невозможно, поэтому необходимо, чтобы система САПР обладала возможностью имитации функционирования схемы и ее неисправностей. Имитация неисправностей является расширением логической имитации и позволяет установить степень обнаруживаемости заданного класса неисправностей. Программа - имитатор должна позволять сгенерировать как специфицируемые, так и неисправные отношения в схеме. Сравнение имитируемого и эталонного результатов указывает на возможные отклонения в работе схемы и приводит к минимизации числа тестовых наборов. Чтобы улучшить тестируемость схемы, необходимо исключить в ходе проектирования возможность появления труднотестируемых динамических неисправностей и улучшить наблюдаемость и управляемость внутренних сигналов схемы [71].
Создание ИСАПРГТ является, таким образом, актуальной задачей. Решение этой проблемы в принципе возможно. Если раньше возможности АРМ ограничивались малой мощностью персональных ЭВМ, то в настоящее время ПЭВМ семейства IBM - совместимых компьютеров на базе процессоров семейства Intel Pentium обладают достаточными ресурсами для реализации на них подобных систем [121, 129].
Следует, однако, иметь в виду, что задача генерации тестов относится к классу NP - полных, то есть время построения теста в общем случае растет экспоненциально с ростом объема схемы и числа ее внутренних состояний [202, 217]. Чтобы поддерживать его в разумных пределах, на практике используют два подхода. Первый предполагает проектирование схем по специальной методике, направленной на улучшение их диагностируемости [142]. Второй, оставляя схемы без изменений, предусматривает генерацию тестов с применением разного рода эвристик плюс интерактивное взаимодействие с человеком - оператором [32, 118, 156]. Неприспособленность схем или конкретной РЭС к проведению диагностирования является в настоящее время основным ограничением на ее производство [189]. Поэтому появилось такое направление научных исследований, как контролепригодное проектирование [77, 142, 195]. Диапазон принципов контролепригодного проектирования простирается от специализированных методов типа разбиения схем на подсхемы, введения в них дополнительных контрольных точек, встроенных средств СА и т.п. приемов до структурных методов. В общем случае, методы генерации тестовых воздействий можно условно поделить на две основные группы: структурно - ориентированные и функционально — ориентированные методы.
Использование сигнатурного анализа для сокращения объема и сложности диагностических словарей
В методе СА для преобразования двоичных последовательностей в сигнатуры используется известный способ генерации циклических кодов при помощи линейного сдвигового регистра (ЛСР) с ОС [62, 63, 190, 212]. Циклические коды получили широкое распространение благодаря высокой обнаруживающей способности и относительной простоте схем кодирования и декодирования. Задолго до появления СА они применялись в цифровой технике для контроля передачи данных по каналу связи, а также между ЭВМ и внешними ЗУ [59, 134].ЛСР с ОС, сигналы которых после каждого сдвига суммируются по модулю 2 с очередным битом входной последовательности, образует сигнатурный анализатор. В общих чертах принцип преобразования двоичных векторов в сигнатуры с его помощью был изложен в параграфе 1.3 данной диссертации. Рассмотрим теперь более подробно математические основы построения сигнатурных анализаторов и дадим количественную оценку обеспечиваемой ими точности преобразования двоичных последовательностей в код.
Структура п - разрядного ЛСР с ОС математически описывается порождающим полиномом Р(х) [71]:где х - фиктивная переменная, р;е{0, 1} (i=0,...,n). Индексы ненулевых коэффициентов р; указывают номера разрядов ЛСР с которых снимается ОС.
Степень п порождающего полинома Р(х) определяет число контрольных разрядов, а также обнаруживающую и корректирующую способность циклического кода. Поэтому для полинома определенной степени всегда полагается, что ро=рп=1- Следовательно, со старшего (п - го) разряда ЛСР всегда отводится ОС.
Двоичную последовательность длиной m бит в математической форме удобно представить в виде информационного полинома G(x) степени т-1:где х - фиктивная переменная, gje{0, 1} (j=0,...,m). Значение коэффициента gj информационного полинома равно значению j — го бита последовательности.
Из теории кодирования известно, что процесс генерации циклического кода для двоичной последовательности, которой соответствует информационный полином вида (3.2), при помощи ЛСР с порождающим полиномом вида (3.1) математически описывается следующим выражением [59, 63, 71, 134]:где Q(x) — частное, a R(x) - остаток от деления полиномов в левой части (3.3); - знак сложения по модулю 2.
Согласно выражению (3.3) подача на вход п - разрядного ЛСР двоичной последовательности означает умножение ее информационного полинома G(x) на хп. Очевидно, что п младших коэффициентов полинома xn- G(x) будут равны нулю, а старшие m коэффициентов будут полностью идентичны коэффициентам полинома G(x). Это свойство ЛСР позволяет получать систематические коды с разделенными информационными и контрольными разрядами. Оно же, как будет показано ниже, обеспечивает постоянство длины сигнатур.
Продвижение двоичной последовательности через ЛСР, как видно из выражения (3.3), соответствует делению ее информационного полинома G(x) на порождающий полином регистра Р(х). Данные, последовательно сдвигаемые из разряда в разряд ЛСР, суть значения коэффициентов полинома - частного Q(x). После того, как деление будет закончено (сигнатурный анализатор остановлен) в ЛСР останутся значения п младших коэффициентов Q(x), которые и образуют сигнатуру.
Алгоритм работы сигнатурного анализатора существенно отличается от алгоритма работы схем кодирования - декодирования циклических кодов, хотя описываются они сходным выражением (3.3). Разница заключается в неодинаковом подходе к использованию правой части этого выражения. Схемы кодирования - декодирования работают с полиномом - остатком R(x), коэффициенты которого определяют значения контрольных разрядов систематического кода. Для сигнатурного анализатора, как следует из вышеизложенного, важен лишь вид полинома — частного Q(x).
Поясним процесс сжатия двоичных последовательностей в сигнатуры следующими математическими выкладками. Пусть деление G(x) на Р(х) дает частное Q (x) и остаток R (x):здесь степень полинома G(x) равняется т-1. Порождающий полином Р(х) имеет степень п. значит, степень полинома - частного Q (x) равна m-n-1, а общее количество его коэффициентов, как единичных, так и нулевых, составляет m-n.
Сигнатурный анализатор в соответствии с (3.3) делит на свой порождающий полином Р(х) не G(x), a xn-G(x). Умножим поэтому обе части (3.4) нахп:
Выражение (3.5) означает, что в процессе деления полиномов поформуле (3.3) встретится такой момент, когда будут полученызначения старших коэффициентов частного Q(x), идентичныекоэффициентам Q (x), и увеличенный в х" раз остаток R (x). С этогомомента дальнейший процесс деления можно выразить формулойкоторая показывает, что младшие п разрядов частного Q(x) фактически получаются делением полинома xn-R (x) на порождающий полином Р(х).В результате процесса деления образуется некоторое частное S(x) и остаток R(x):
Проанализируем выражение (3.9). Полином xn-Q (x) с учетом замечаний к формуле (3.4) имеет степень т-1 и, соответственно, m коэффициентов. Степень полинома S(x) согласно (3.7) не превышает п-1. Число его коэффициентов, стало быть, не больше п. Легко видеть, что младшие п коэффициентов полинома xn-Q (x) (при степенях х, меньших п) равны нулю. Поэтому сложение по модулю 2 указанных полиномов в соответствии с (3.9) означает, что старшие m-n коэффициентов Q(x) идентичны коэффициентам Q (x), а младшие п коэффициентов - коэффициентам S(x). Если число коэффициентов S(x) меньше п, допустим к, то оставшиеся n-к младших коэффициентов Q(x), естественно сохраняют нулевые значения.
Количество коэффициентов полинома Q (x) по определению (3.4) непостоянно и зависит от разности степеней информационного полинома двоичной последовательности G(x) и порождающего полинома ЛСР Р(х). Для длинных последовательностей (при m»n) число коэффициентов Q (x) и G(x) отличается незначительно. Следовательно, сжатие информации практически отсутствует, и коэффициенты Q (x), а значит, и старшие m-n коэффициентов Q(x), не могут использоваться в качестве сигнатуры.
Количество младших коэффициентов полинома Q(x) (при степенях х, меньших п), как было показано выше, фиксировано и равно числу разрядов ЛСР п. Единичными из них согласно (3.9) являются только те, что имеют значение 1 и в полиноме S(x). Таким образом, полином S(x) полностью определяет значения младших п коэффициентов полинома Q(x).
В свою очередь, полином S(x) по правилу (3.8) может быть поставлен в соответствие полиному G(x) (обратного соответствия не существует). Значит, любой двоичной последовательности произвольной длины соответствует определенная комбинация значений младших п коэффициентов полинома Q(x). Эту комбинацию длиной п бит удобно трактовать как компактный образ двоичной последовательности, или ее сигнатуру.
Теперь нетрудно оценить точность вышеописанного преобразования. Всего различных последовательностей длиной m бит существует 2т. Сигнатурный анализатор на основе п — разрядного ЛСР способен сформировать 2П различных сигнатур. Если m n, для каждой последовательности будет получена своя сигнатура.
Следовательно, любые две последовательности различимы с вероятностью 100 % независимо от того, отличаются они одним битом или несколькими.
При m n последовательности, отличающиеся одним битом, также распознаются с вероятностью 100 % [63, 71]. Совпадение сигнатур различных последовательностей возможно только в том случае, когда они отличаются более чем одним битом и последующие искажения компенсируют влияние предыдущих.
Поскольку старшие m-n коэффициентов полинома Q(x) не участвуют в формировании сигнатуры, очевидно, может быть 2m"n-l последовательностей, которые не идентичны данной, но имеют одинаковую с ней сигнатуру. Всего последовательностей длины т, отличных от данной, существует 2ш-1. Вероятность ошибки преобразования сигнатурного анализатора составляет тогда
