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

СОДЕРЖАНИЕ СПИСОК СОКРАЩЕНИЙ ВВЕДЕНИЕ РАЗДЕЛ 1. АНАЛИЗ МЕТОДОВ ДИАГНОСТИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ

1.1 Диагностирование ДУ детерминированными тестами

1.2 Анализ методов встроенного диагностирования ДУ

1.3 Псевдоисчерпывающее тестирование ДУ

1.4 Методы функционального диагностирования ДУ

1.5 Анализ методов преобразования автоматов в легко тестируемые

1.6 Постановка цели и задач исследования РАЗДЕЛ 2. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА СР С ЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

2.1 Анализ методов генерации тестов на сдвиговых регистрах с обратной связью

2.1.1 Сдвигово — регистровые последовательности, основные определения и анализ

2.1.2 Синтез ГПТ на сдвиговых регистрах с линейной обратной связью

2.2 Синтез ГПТ на основе структуры модифицированного СРЛОС/СР

2.3 Синтез ГПТ на основе параллельно функционирующих СРЛОС/СР

2.4 Синтез самотестируемых сигнатурных анализаторов

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

2.6 Выводы РАЗДЕЛ 3. ГЕНЕРАТОРЫ ТЕСТОВ НА СР С НЕЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

3.1 Методы генерации полных циклов на сдвиговых регистрах

3.2 Реализация логических функций однородной сетью Майтра

3.3 Синтез ГПТ на сдвиговых регистрах с нелинейной обратной связью

3.4 Минимизация длины проверяющей последовательности

3.5 Синтез ГПТ на основе использования примитивных многочленов

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

3.7 Выводы РАЗДЕЛ 4. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА КЛЕТОЧНЫХ АВТОМАТАХ

4.1 Анализ свойств клеточных автоматов

4.2 Матричные модели сетей КА

4.2.1 Характеристическая матрица правил СКА

4.2.2 Матричные модели СКА

4.3 Генераторы циклических последовательностей на клеточных автоматах

4.4 Изоморфизм СКА и СРЛОС

4.5 Генераторы последовательностей максимальной длины на СКА

4.6 Свойства последовательностей максимальной длины генераторов на СКА

4.7 Метод синтеза генераторов последовательностей максимальной длины на аддитивных СКА

4.8 Выводы РАЗДЕЛ 5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МОДУЛЕЙ СИГНАТУРНОГО МОНИТОРИНГА

5.1 Анализ сложности последовательностей де Брейна

5.2 Достоверность функционирования самопроверяемого многоканального сигнатурного анализатора

5.3 Краткое описание и анализ ПЛИС ALTERA MAX 7000

5.4 Моделирование модулей сигнатурного мониторинга, реализованных на ПЛИС ALTERA MAX 7000S

5.5 Выводы ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ПРИЛОЖЕНИЕ, А Доказательства утверждений раздела 4

ПРИЛОЖЕНИЕ Б Сети КА степени 5, генерирующие последовательности максимальной длины при нулевых граничных условиях ПРИЛОЖЕНИЕ В Исходные тексты программных модулей для генерирования тестовых последовательностей и анализа их свойств ПРИЛОЖЕНИЕ Г Функции обратной связи СРНОС степени 16 для получения последовательностей де Брейна и оценка их сложности ПРИЛОЖЕНИЕ Д Документы, подтверждающие внедрение результатов диссертации

СПИСОК СОКРАЩЕНИЙ ВВП — вход-выходные последовательности ГПТ — генератор псевдоисчерпывающих тестов ДП — диагностический процессор ДУ — дискретное устройство КА — клеточный автомат

КС — комбинационная схема КТД — контроллер тестового диагностирования ЛФ — логическая функция МДНФ — минимальная дизъюнктивная нормальная форма МК — микроконтроллер МСА — многоканальный сигнатурный анализатор МСРЛОС — модифицированный сдвиговый регистр с линейной обратной связью ОС — обратная связь

ПМВС — программируемая матрица внутренних соединений

ПН — перемежающаяся неисправность ПС — периферийное сканирование ПСРЛОС — параллельные сдвиговые регистры с линейными обратными связями СА — сигнатурный анализатор

СБИС — сверхбольшая интегральная схема СВК — схема встроенного контроля СДНФ — совершенная дизъюнктивная нормальная форма

СКА — сеть клеточных автоматов

СР — сдвиговый регистр СРЛОС — сдвиговый регистр с линейной обратной связью СРНОС — сдвиговый регистр с нелинейной обратной связью СРОС — сдвиговый регистр с обратной связью ТПВ — таблица переходов-выходов ЦСР — циркулирующий сдвиговый регистр ЭК — элементарная конъюнкция

ВВЕДЕНИЕ

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

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

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

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

Весомый вклад в решение проблем тестового и функционального диагностирования, генерации тестов и моделирования неисправностей, создания встроенных средств самотестирования внесли ученые: П. П. Пархоменко, Е. С. Согомонян, А. П. Горяшко, В. Г. Тоценко, Д. В. Сперанский, В. А. Твердохлебов, А. М. Романкевич, Л. В. Дербунович, Ю. А. Скобцов, Р. Убар, Г. Ф. Кривуля, В. И. Хаханов, E.J. McCluskey, R.G. Bennets, S.K. Gupta, J. Savir, J.A. Abraham, M. Breuer и др.

Актуальность темы

исследования. Известно, что стоимость процедур генерации тестов и моделирования неисправностей растет с возрастанием размерности схемы, рабочей частоты и числа выводов СБИС. Необходимость учета особенностей субмикронных технологий производства СБИС, условий эксплуатации управляющих систем на их основе в рамках жестких стоимостных и временных ограничений приводит к необходимости объединения методов функционального и тестового диагностирования и реализации их в виде программно-аппаратных модулей сигнатурного мониторинга, встроенных на кристалл или печатную плату. В соответствии с международным стандартом проектирования цифровых систем IEEE 1149.1 «Boundary scan» архитектура системы в режиме тестирования реконфигурируется в сдвигово-регистровую сеть, через которую сканируется диагностическая информация с управляемых входов на наблюдаемые выходы. Методология тестопригодного проектирования предусматривает разбиение сложной схемы на макроблоки для обеспечения доступа к внутренним узлам схемы и сокращения трудоемкости тестового диагностирования макроблоков и иерархическое использование встроенных схем самотестирования, образующих систему сигнатурного мониторинга.

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

Связь работы с научными программами, планами, темами.

Разработка основных положений работы осуществлялась в соответствии с планами НИР и программами, выполняемыми на кафедре автоматики и управления в технических системах НТУ «ХПИ», а именно с планом прикладных работ МОН Украины: «Разработка методик оптимального управления состоянием динамических систем в условиях неопределенности» (№ ГР 0100U001691); «Разработка методов принятия решений в условиях неполной информации об объекте управления» (№ ГР 0103U001511); поисковая тема «Созвучие» НАН Украины «Разработка комплексов микропроцессорных технических средств контроля и регулирования уровня расплава при выращивании ЩГК» (№ ГР 0101U006612).

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

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

Сформулированная цель достигается решением следующих задач:

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

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

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

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

применение разработанных методов синтеза для реализации модулей сигнатурного мониторинга на ПЛИС.

Объект исследования — дискретные устройства и системы на одном кристалле, микроконтроллерные устройства управления, процессы их тестового и функционального диагностирования.

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

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

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

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

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

Практическое значение полученных результатов определяется:

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

расширением класса обнаруживаемых неисправностей, который включает устойчивые кратные константные неисправности и неисправности логического типа;

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

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

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

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

Личный вклад соискателя. Соискателем предложены новые методы синтеза модулей сигнатурного мониторинга — самопроверяемого многоканального сигнатурного анализатора, генератора поледовательности де Брейна на СРНОС, генератора М-последовательности на СКА; метод синтеза ГПТ, основанный на модификации структуры СРЛОС/СР путем формирования линейно независимых остатков; метод нахождения последовательности двоичных символов, порождающих гамильтонов цикл в СР, циклических сдвиг которых обеспечивает оптимальный по тестопригодности вариант кодирования автомата; а также алгоритмы и программы, обеспечивающие решение поставленных задач. Вся практическая работа по разработке и исследованию новых методов синтеза модулей сигнатурного мониторинга выполнена соискателем лично, а работы по внедрению этих методов на предприятиях — при его личном участии.

Апробация результатов работы. Научные результаты диссертационной работы по мере их получения обсуждались на совместных семинарах кафедры «Автоматика и управление в технических системах» Харьковского национального университета «ХПИ» и кафедры «Автоматизация проектирования вычислительной техники» Харьковского Национального университета радиоэлектроники. Эти результаты докладывались на следующих научных конференциях и семинарах: на 7-й Международной конференции «Теория и техника передачи, приема и обработки информации» (Харьков, 2001), на международной конференции «Проблемы информатики и моделирования — 2001» (Харьков, 2001), на 15-й Международной школе-семинаре «Перспективные системы управления на железнодорожном, промышленном и городском транспорте» (г. Алушта, Крым, Украина, 13 — 20 сентября 2002 г.), на 10-й юбилейной конференции «Проблемы автоматизированного электропривода. Теория и практика» (Крым, 2002).

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

РАЗДЕЛ 1. АНАЛИЗ МЕТОДОВ ДИАГНОСТИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ

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

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

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

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

В области генерации детерминированных тестов главная проблема заключается в создании эффективной системы генерации тестов общего назначения, обеспечивающих проверку исправности дискретных устройств большой размерности. Попытки создания таких систем ведущими фирмами-производителями СБИС показали, что такую систему полностью автоматической сделать невозможно, если не ввести определенные ограничения на проектируемое изделие, чтобы уменьшить сложность решаемой задачи. Считается, что эта проблема разрешима, если генерировать тесты только для комбинационных схем. На этом основании были приложены усилия для развития методов сканирования, которые в конечном итоге были объединены в международном стандарте проектирования ДУ IEEE 1149.1 «Boundary scan» — периферийное сканирование (ПС).

На рис. 1.1. представлена структура ДУ, которая спроектирована в соответствии со стандартом периферийного сканирования. Интерфейс ПС — порт JTAG, который включает 4 — 5 выводов: TDI/TDO (Вх/Вых Тестов сканирования), TCK (test clock — тактовая частота тестирования), TMS (test mode select — выбор режима тестирования), TRST (test reset — начальная установка тест — контроллера по выбору разработчика).

Входные и выходные регистры используются для параллельного приема и передачи входных и выходных данных, а также для последовательного ввода-вывода данных через выводы порта JTAG TDI/TDO. В режиме тестирования все элементы памяти (за исключением встроенных ОЗУ, ПЗУ) реконфигурируются в сдвигово-регистровые цепи, что позволяет последовательно вводить/выводить данные в/из внутренних узлов логического ядра схемы. Управление процессом диагностирования осуществляется специальным встроенным контроллером тестового диагностирования (КТД).

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

Рис. 1.1. Структура ДУ с периферийным сканированием через порт JTAG.

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

Известны оценки трудоемкости генерации множества детерминированных тестов и оценки их эффективности путем использования систем моделирования неисправностей в зависимости от числа эквивалентных вентилей схемы [4]:

число тестов, обеспечивающих покрытие 100% одиночных константных неисправностей ;

затраты на генерацию этих тестов ;

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

полное время тестирования для ДУ со стандартом периферийного сканирования .

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

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

1.2 Анализ методов встроенного диагностирования ДУ Внедрение нанометровых технологий в процесс производства интегральных схем и ДУ на их основе, повышение тактовой частоты работы устройств до ГГц создает проблемы в области тестового диагностирования СБИС. Генерация тестов основана на принятых моделях неисправностей и нахождения условий их проявления и транспортировки на наблюдаемый выход. Дефекты (неисправности) константного типа или «короткое замыкание» между соседними линиями и соединениями, перепутывание связей имеют место при производстве СБИС в современных технологиях.

Повышение быстродействия логических элементов и соизмеримость задержек сигналов в активных элементах и линиях связи приводят к появлению неисправностей типа (slow-to-rize) задержка фронта импульса и (slow-to-fale) задержка среза импульса, что при высокой частоте синхронизации может приводить к искажению функциональных характеристик схемы. Для обнаружения такого типа неисправностей существует два подхода: 1) тестирование на рабочей частоте; 2) генерирование специальных векторных пар, воздействующих на комбинационную часть ДУ, что позволяет обнаружить изменения в скорости распространения сигналов.

Анализ диагностического обеспечения микропроцессорных СБИС ведущих зарубежных фирм: Pentium Pro (Intel Corporation); S/390 (IBM); Power PC; MC 202−206 (Motorola); AMD-K6 (Advanced Micro Devices), показывает, что 5 — 8% площади кристалла СБИС занимают встроенные схемы тестирования, которые позволяют обнаружить практически 100% дефектов, перечисленных выше типов. Например, диагностическое обеспечение микропроцессора S/390 (транзисторов, 500 МГц тактовая частота) (рис. 1.2) включает:

Иерархическую структуру встроенных диагностических средств;

ОЗУ, кэш, память, схемы их управления с встроенными схемами самотестирования;

Триггеры, регистровые сети, образующие в режиме тестирования сканируемый путь по методу Level Sensitive Scan Design (LSSD);

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

Встроенный многоканальный сигнатурный анализатор;

Порт JTAG в соответствии со стандартом IEEE 1149.1.

На нижнем транзисторном уровне все комбинационные модули проверяются методами исчерпывающего тестирования. На макроуровне используются методы сканирования, что вместе с проверкой транзисторного уровня позволяет обнаруживать 95% константных неисправностей. Использование весовых псевдослучайных последовательностей, а также специальных вход/выходных последовательностей обеспечивает 99,9% покрытия всех неисправностей СБИС.

Анализ диагностического обеспечения СБИС микропроцессоров, устройств на ПЛИС показывает, что существует два основных подхода к реализации методов встроенного диагностирования. Первый подход — разбиение сложного устройства на макроблоки с числом входов и генерация тривиальных (исчерпывающих) тестов с помощью счетчиковых структур или сдвиговых регистров с линейной обратной связью (СРЛОС) в сочетании с методами сканирования памяти [7 — 11]. Второй подход — тестопригодное проектирование ДУ, обеспечивающее простоту и регулярность генерации тестовых последовательностей типа бегущей 0(1), кодовые слова линейных блоковых кодов, обладающих высоким покрытием неисправностей для класса однородных структур типа ОЗУ, ПЗУ, устройств на ПЛИС [12, 13].

В работе введено понятие универсального встроенного самотестирования (UBIST).

Рис. 1.2. Структура встроенной системы тестового диагностирования

КМОП IBM S/390 микропроцессора:

Ф Вх/Выхфункциональные входы/выходы;

ГПТП — генератор псевдослучайных тестовых последовательностей (ПТП);

Вх/Вых ТСК — вход/выход тестов сканирования;

М — мультиплексор;

УСТ — управление самотестированием (СТ);

СЦ — сканируемые цепи;

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

В работах [15, 16] исследованы вопросы обнаружения ошибок с помощью паритетного кода и сигнатурного анализатора. На основе теории кодирования получены оценки вероятности обнаружения ошибок. Как и в [14], в работах [15, 16] паритетные схемы встроенного контроля и сигнатурные анализаторы реализованы в виде отдельных блоков.

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

1.3 Псевдоисчерпывающее тестирование ДУ Метод исчерпывающего тестового диагностирования комбинационных схем (КС) основан на приложении к проверяемой схеме с входами всех входных наборов. Это позволяет обнаружить неисправности КС комбинационного класса, которые не приводят к преобразованию КС в последовательностную схему. Главным достоинством такого подхода является исключение дорогостоящих и трудоемких процедур генерации проверяющих тестов и моделирования неисправностей. Простота генерации тестовых последовательностей с помощью счетчиковых структур, сдвиговых регистров с линейной обратной связью и клеточных автоматов в сочетании с эффективными методами сигнатурного сжатия выходных реакций КС позволяет осуществить процедуру проверки КС с использованием простых схем диагностирования [17 — 20].

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

Рассмотрим КС с входами и выходами (рис. 1.3). Будем называть выходным конусом часть КС, которая связана с определенным выходным полюсом. Число входов, от которых зависит каждый выход называют показателем зависимости соответствующего конуса. Пусть — максимальное значение показателя зависимости всех выходов КС.

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

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

Рис. 1.3. Топологическая структура КС.

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

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

Проанализируем кратко основные результаты исследований в области синтеза синдромно тестируемых КС [24 — 27].

Определение 1.1. Синдромом логической функции называется число, где — число минтермов функции.

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

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

Определение 1.3. Логическая функция называется однородной, если она положительно (отрицательно) однородна по .

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

Определение 1.4. Логическая схема из элементов И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ, является однородной, если для любого соединения схемы выполняется условие, что каждый путь от к ее выходу содержит число инверторов одинаковой четности, иначе — схема называется неоднородной.

Определение 1.5. Логическая схема является частично однородной, если она однородна по всем внутренним соединениям и неоднородна по меньшей мере по одному первичному входу.

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

К этому же классу относятся древовидные схемы из И, ИЛИ, ИЛИ-НЕ, И-НЕ, НЕ элементов, не имеющие ветвлений входных и внутренних переменных.

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

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

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

(1.1)

где — матрица-столбец размером, представляющая таблицу истинности функции; - константная матрица размерности преобразования Уолша, рекурсивно определяемая равенствами:

для (1.2)

Процедура вычисления спектральных коэффициентов Уолша КС, реализующей функцию (табл. 1.1), показана на рис. 1.4.

Спектральные коэффициенты имеют следующую интерпретацию: — число единичных значений функции (синдром в [26]); характеризуют меру корреляции функции с переменными соответственно. Остальные коэффициенты представляют меру корреляции заданной функции с суммой по mod2 соответствующих переменных. Например, является мерой корреляции функции с .

Таблица истинности

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

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

Так как условие теоремы 1.1 значительно расширяет класс синдромно тестируемых схем по сравнению с [23], то в дальнейшем изложении будем понимать под синдромным тестированием процедуру проверки двух синдромов, соответствующих и. Реализация процедуры синдромного тестирования может осуществляться по схеме, представленной на рис. 1.5.

Диагностирование выполняется в двух режимах:

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

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

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

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

1.4 Методы функционального диагностирования ДУ В системах функционального диагностирования рабочие воздействия ДУ используются для анализа его исправности в процессе реализации его алгоритма функционирования. Средства системы функционального диагностирования структурно сопряжены с объектом диагностирования. ДУ имеет средства встроенного контроля (СВК), как это показано на рис. 1.6.

Рис. 1.6. Структура ДУ со схемой встроенного контроля.

Вопросы функционального диагностирования исследовались в [33 — 41]. Показано, что использование средств функционального диагностирования при самотестировании значительно повышают достоверность самотестирования. Достоинством систем функционального диагностирования ДУ является их способность обнаруживать перемежающиеся неисправности и сбои.

Опыт промышленного использования микроконтроллерных систем управления показал, что этот класс неисправностей имеет место в большинстве случаев при выполнении управляющих программ. Для обнаружения этих неисправностей и последующего восстановления работоспособности МК в настоящее время широко используются методы сигнатурного мониторинга, для реализации которого необходимо решить три задачи: 1) разбиение управляющих программ МК на сегменты и нахождение оптимального числа контрольных точек программ для обнаружения неисправностей; 2) вычисление эталонных сигнатур для каждой контрольной точки и определение минимального объема информации для повторной «прокрутки» программного сегмента; 3) восстановление работоспособности системы управления с помощью простых аппаратных средств, которые называют «watchdog» или диагностическими процессорами (ДП) [42, 43, 44, 111]. Известны два основных подхода для реализации сигнатурного мониторинга в системах управления на основе МК, которые отличаются способом вычисления эталонных сигнатур. В первом подходе используются различные блоковые коды, обнаруживающие ошибки в потоках команд процессора и данных, а на этапе компиляции управляющих программ для каждого сегмента вычисляются контрольные суммы, являющиеся эталонными сигнатурами сегментов. Во втором — контролируется правильность переходов и ветвлений программных сегментов с помощью блоковых кодов и время выполнения программных сегментов [43, 46].

Для обнаружения ошибок МК используется ДП, функционирующий параллельно и одновременно с основным процессором (рис. 1.7). Для сопряжения ДП с интерфейсной магистралью МК используются шинные формирователи данных (ШФД) и шинные формирователи адреса (ШФА).

Схема формирования сигнала ответа (СФО) управляет обменом управляющими командами между ДП и МК. Детектор (ДТ) предназначен для обнаружения на шине данных последней команды программного сегмента. Блок управления (БУ) вырабатывает сигналы начала и окончания контроля проверяемого сегмента.

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

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

Рис. 1.6. Структурная схема диагностического процессора.

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

Восстановление правильного функционирования МК рассмотренным выше методом осуществимо при выполнении следующих условий:

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

латентный период обнаружения ошибки меньше цикла управляющей программы МК;

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

Таким образом, можно повысить отказоустойчивость МК для класса ПН путем использования ДП для обнаружения ошибок в процессе функционирования МК и восстановление путем повторной «прокрутки» части программы, на которой обнаружена ошибка.

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

Известны методы преобразования автоматных моделей ДУ, позволяющие упростить процедуру их тестового диагностирования, т. е. синтезировать легко тестируемые устройства [47 — 52]. Это достигается либо путем введения дополнительных выходов [52 — 54] в ТПВ автомата, либо путем введения дополнительных входов [48, 55 — 58], либо введением дополнительных входов и выходов одновременно [49, 51, 59 — 61]. Следует отметить, что для автомата с состояниями и выходными символами первые из вышеупомянутых методов дают верхнюю границу длины проверяющего эксперимента, вторые, а сочетание этих двух подходов дает оценку. Приведенные оценки верхних границ длины проверяющих последовательностей получены в большинстве работ на основе построения проверяющего эксперимента с автоматом по методу Хенни для обнаружения класса функциональных неисправностей, вызывающих произвольное изменение ТПВ автомата при ограничении, что неисправность не приводит к увеличению числа состояний автомата. Тем не менее, практическое использование предложенных методов преобразования автоматных моделей ДУ и построение полных проверяющих экспериментов для ДУ, содержащих свыше 40 — 50 триггеров, является практически невыполнимой задачей.

Среди большого числа работ отечественных авторов в этой области следует в первую очередь выделить результаты, полученные в докторских диссертациях А. П. Горяшко, Д. В. Сперанского и В. Г. Тоценко [49, 52, 59].

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

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

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

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

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

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

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

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

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

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

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

Сформулированная цель достигается решением следующих задач:

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

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

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

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