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

  • Вид работы:
    Магистерская работа
  • Предмет:
    Информатика, ВТ, телекоммуникации
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    811,89 Кб
  • Опубликовано:
    2012-09-10
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

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

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ

ВВЕДЕНИЕ

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

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

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

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

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

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

.6 Постановка цели и задач исследования

РАЗДЕЛ 2. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА СР С ЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

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

.1.1 Сдвигово - регистровые последовательности, основные определения и анализ

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

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

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

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

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

.6 Выводы

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

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

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

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

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

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

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

.7 Выводы

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

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

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

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

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

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

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

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

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

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

.8 Выводы

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

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

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

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

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

.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]. Причиной возникновения отказов дискретных устройств могут быть дефекты, допущенные при проектировании, производстве и ремонте устройств, нарушения норм эксплуатации, естественные процессы старения и изнашивания, а также различные повреждения. Следует отметить, что дефекты и повреждения, возникающие в устройствах, некоторые авторы называют неисправностями [2].

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

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

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

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

На рис. 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 суток.

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

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

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

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

Анализ диагностического обеспечения микропроцессорных СБИС ведущих зарубежных фирм: 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].

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

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

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

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

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

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

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

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

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

Вст. ОЗУ - встроенная схема тестирования ОЗУ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 (1.1)

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

 для (1.2)

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

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

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




0

0

0

0

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

0


Рис. 1.4. Вычисление спектральных коэффициентов Уолша

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

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

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

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

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

Рис. 1.4. Диагностирование методом синдромного тестирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.6 Постановка цели и задач исследования

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

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

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

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

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

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

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

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

РАЗДЕЛ 2. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА СР С ЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

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

.1.1 Сдвигово - регистровые последовательности, основные определения и анализ

Внедрение нанометровых технологий в процесс производства интегральных схем и ДУ на их основе, повышение быстродействия логических элементов и сложности современных устройств на СБИС определяет актуальность использования встроенных средств диагностирования их исправности на рабочей частоте. В качестве генераторов тестов и схем сжатия выходных последовательностей ДУ находят широкое применение сдвиговые регистры с линейными и нелинейными обратными связями [4, 17, 20, 63, 64, 112].

Определение 2.1. Сдвиговый регистр (СР) размерности n с функцией f обратной связи - это цепь из n последовательно соединенных триггеров , состояния которых в момент времени t определяют значение функции  в последующий момент времени , где - выходы соответствующих разрядов СР (рис. 2.1).

Известно, что СР с обратной связью (СРОС) генерируют периодические последовательности, длина которых может принимать значения от 1 до 2n, а последовательность состояний СР с циклом максимальной длины порождает множество  всех двоичных n - мерных векторов [65]. Функция обратной связи СРОС , , индуцирует отображение F: , для которого , где  и .

СРОС есть конечный автомат, заданный уравнениями:

 где - вектор состояния СР,

- множество выходов СР, - длина СР,

- логическая функция ОС,

Рис. 2.1. n - разрядный сдвиговый регистр с функцией обратной связи .

Поэтому поведение СРОС также, как поведение любого конечного автомата, может представляться в трех формах: графом переходов, таблицей переходов - выходов и в матричной форме [65].

Граф  сдвигового регистра состоит из вершин (состояний СР) и  дуг (ребер), определяющих переходы из каждого состояния. На рис. 2.2 представлены конечно - автоматные модели СР длиной  и в виде графов переходов состояний и . Если дуги графа отметить 4 - кой, которая образуется 3 - кой, соответствующей предшествующей вершине графа , и значением функции обратной связи СР, вызывающей этот переход, то из графа  конструируется граф , как показано на рис. 2.2.

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


Для анализа свойств циклов в СР и способов их построения введём следующие определения.

Определение 2.3. Пусть  - вектор состояний СР длиной n. Будем называть вектор левосопряженным, а вектор правосопряженным вектору состояний X, если выполняется:

 (2.1)

Определение 2.4. Сдвиговый регистр, у которого функция обратной связи  будем называть СР с петлевой обратной связью или циркулирующим сдвиговым регистром (ЦСР).

Определение 2.5. Весом  будем называть число единиц в двоичном векторе начального состояния ЦСР.

ЦСР длиной n обладает очевидным свойством: циклический сдвиг его начального состояния порождает циклические последовательности двоичных векторов одного веса.

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

В [65] были определены необходимые и достаточные условия объединения ЦСР с различными весами в один цикл.

Теорема 2.1 [65]. Два смежных цикла  и  в графе  можно объединить в один цикл, если в  существует такая вершина  такая, что , а в  существует вершина  такая, что .

Пример 2.1. В графе с функцией обратной связи  имеется четыре цикла (рис. 2.3а):


Циклы  являются смежными. Применяя теорему 2.1 можно объединить эти циклы в один, как показано на рис. 2.3в и 2.3с.

Рис. 2.3. Циркулирующий СР длиной 3 и циклы в графе .

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

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

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

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

Минимальная дизъюнктивная нормальная форма этой функции

(2.2)

Однако простейшей аппаратной реализацией этой функции является форма ее представления в виде

(2.3)

Известно, что в графе  число k гамильтоновых циклов равно[39]

(2.4)

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

Так как функция обратной связи СР  равна 1 на  наборах n - мерных двоичных векторов, то ее всегда можно представить в виде разложения:

(2.5)

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

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

Как было показано в разделе 1, ограничения, связанные с экспоненциальным ростом числа тривиальных тестов с увеличением размерности ДУ и числа его входов, преодолеваются применением псевдоисчерпывающего тестирования, а требования стандарта IEEE 1149.1 при проектировании ДУ, а также правила тестопригодного проектирования позволяют свести процедуру диагностирования к проверке исправности комбинационной части ДУ. Анализ современных разработок ДУ показывает, что комбинационная схема (КС) с n входами и m выходами обладает конусной зависимостью m выходов от входных переменных. Число входов , от которых зависит каждый выход схемы, называют показателем зависимости соответствующего конуса.

Пусть  - максимальное значение показателя зависимости всех m выходов КС. Тогда схема с n входами, m выходами и k - максимальным показателем зависимости может быть проверена исчерпывающим тестом длиной .

Проблема генерации оптимальных псевдоисчерпывающих тестов исследуется в ряде работ [20, 63, 66] . Универсальные генераторы для  схем можно использовать для всех классов и структур логических схем с одинаковыми значениями n и k. Такие генераторы формируют n - мерные двоичные векторы, которые накрывают все k - мерные двоичные подпространства, т.е. любые k столбцов в последовательностях n - мерных двоичных векторов содержат все  возможных двоичных наборов. Построение универсальных генераторов тестов основано на использовании СРЛОС и кодов с постоянным весом [20], линейных кодов [67, 68] или циклических кодов [69]. Теория кодирования позволяет определить необходимые полиномы обратной связи в СР, однако для специфических  схем, не требующих соблюдения принципа универсальности, размерность тестовых последовательностей и аппаратурные затраты на реализацию встроенных генераторов намного меньше, чем у универсальных.

Генераторы псевдоисчерпывающих тестов (ГПТ) для заданной  схемы можно спроектировать путем использования двух подходов. В основе первого подхода используется структура СРЛОС/Сдвиговый регистр (СРЛОС/СР) (рис. 2.4а) [17]. Во втором подходе псевдоисчерпывающие тестовые последовательности длиной, приближающейся к нижней границе, можно генерировать комбинацией СРЛОС и логических элементов Исключающее ИЛИ (СРЛОС/XOR) как показано на рис. 2.4в.

Рис. 2.4 Структуры генераторов тестов на основе: а) СРЛОС/СР, в) СРЛОС/XOR

В структуре СРЛОС/СР (рис. 2.4а) первые  триггеров СР замкнуты линейной обратной связью в соответствии с примитивным полиномом  степени . Остальные  триггеров соединены последовательно, образуя цепь СР. Триггеры СРЛОС генерируют  - мерные тестовые сигналы, представляющие собой остатки от деления на полином  входной последовательности. Остаток , представляющий тестовый сигнал, генерируемый триггером , равен 1. Следовательно, множество остатков, формируемых триггерами  представляется как , и соответствует  независимым тестовым сигналам, генерируемым триггерами  СРЛОС.

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

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

Теорема 2.2 [17]. Выходной конус, который зависит от входов , проверяется исчерпывающим тестом тогда и только тогда, когда остатки  являются линейно независимыми.

Псевдоисчерпывающие тесты, генерируемые структурой СРЛОС/СР, чаще всего имеют длину значительно превышающую нижнюю границу . Для исключения этого недостатка используются генераторы со структурой СРЛОС/XOR (рис. 2.4в) [64, 113]. Это позволяет снизить длину тестовой последовательности для заданной  схемы, но требует повышения аппаратурных затрат.

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

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

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

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

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

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

а) остатки от деления, соответствующие входам схемы;

в) структура МСРЛОС/СР.

Процесс формирования разрядов ГПТ продолжается до тех пор, пока не завершится формирование разряда с линейно независимыми остатками, который запитывает последний вход схемы . Если для формирования тестовых последовательностей используется примитивный полином степени k, то область циклически повторяющихся остатков в цепи СРЛОС/СР равна [114].

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

Аппаратурные затраты на реализацию ГПТ на основе МСРЛОС/СР определяются количеством используемых вентилей XOR, а также вектором начальной установки. Так как СРЛОС не формирует тестового набора из всех нулей , то для его формирования необходимо использовать мультиплексоры 2 на 1 в тех разрядах СР, которые в соответствии с вектором начальной установки равны 1.

Пример 2.2. Пусть задана комбинационная схема (6, 5, 3), имеющая 6 входов и 5 выходных конусов , как показано на рис. 2.6.


Рис. 2.6. Комбинационная схема (6,5,3).

Так как k = 3, то для генерации тестовых наборов выбираем примитивный полином третьей степени . Остатки, формируемые цепью СРЛОС/СР с полиномом  в обратной связи, приведены на рис.2.7а. Выходы триггеров  можно приложить ко входам , так как остатки, соответствующие этим разрядам, являются линейно независимыми для всех выходных конусов схемы. Выход триггера  не может запитывать вход  так как множество остатков  для выходного конуса  являются линейно зависимыми. Пропуская разряд , запитаем входы  и  выходами триггеров  и  соответственно, как показано на рис. 2.7а. Такое отображение выходов ГПТ на входы проверяемой схемы обеспечивает линейную независимость множеств остатков для всех пяти выходных конусов схемы.

В структуре генератора СРЛОС/СР пропущенный триггер  создает дополнительную аппаратную избыточность, которую можно сократить путем использования 2 - входового вентиля XOR, заменяющего триггер  в цепи СРЛОС/СР. Так как выход  формирует остаток , который определяет формирование остатков в разрядах  и , то функция возбуждения триггера  в виде  обеспечивает генерирование остатков разрядами  и , как показано на рис. 2.7в. Такой МСРЛОС/СР генерирует (23-1) исчерпывающих тестов для всех пяти конусов схемы (6,5,3).

Теорема 2.3. Для  схемы существует ГПТ со структурой МСРЛОС/СР степени  тогда и только тогда, когда существует ГПТ со структурой СРЛОС/СР той же степени .

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

Достаточность. Любой генератор на основе МСРЛОС/СР можно преобразовать в эквивалентный генератор со структурой СРЛОС/СР путем замены элементов XOR триггерами СР, генерирующими соответствующие остатки, которые в структуре СРЛОС/СР не запитывают входы  схемы. Теорема доказана.

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

Рис. 2.7. Генераторы тестов:

а) на основе структуры СРЛОС/СР;

в) на основе МСРЛОС/СР

Процедура синтеза ГПТ на основе МСРЛОС/СР для тестирования заданной  схемы, который обеспечивает генерацию псевдоисчерпывающих тестов минимальной длины с минимальными аппаратурными затратами, предполагает выполнение следующих шагов:

вычисление остатков, генерируемых цепью СРЛОС/СР на основе примитивного полинома степени k и выше;

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

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

минимизация числа исключаемых разрядов СР;

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

Для реализации алгоритма и программы используются неприводимые полиномы степени n. В качестве примера в таблице 2.1 приведены неприводимые полиномы степени  [70].

Таблица 2.1

Неприводимые полиномы.

N

Формула полинома

N

Формула полинома

3

10



4

11



5

12



6

13



7

14



8

15



9

16




Алгоритм определения линейной зависимости остатков для синтеза ГПТ на МСРЛОС/СР.

Шаг 1.Инициализация массива остатков  (СРЛОС).

Шаг 2.Ввод n-степени полинома, ввод неприводимого полинома .

Шаг 3. Формирование диапазона остатков полинома СР. .

Шаг 4.Ввод интересующих остатков полинома СРЛОС и СР на предмет определения линейной зависимости;

Шаг 5.Проверка количества введенных остатков полинома . Если количество , то вернуться к шагу 4, в противном случае перейти к шагу 6.

Шаг 6. Преобразование введенных остатков СРЛОС в элементы массива . Функция READPOL.

Шаг 7. Формирование массива остатков и заполнение элементов “-1”.

Шаг 8. Начало цикла деления многочленов. От  до  выполнять деление.

Шаг 9.Формирование массива делителя .

Шаг 10.Запуск функции - деление полиномов. Формирование массива остатков .

Если , то перейти к шагу 8, в противном случае перейти к шагу 11.

Шаг 11. Считывание остатка СР и выполнение Шейкер-сортировки по убыванию степени остатка.

Шаг 12. Цикл поэлементного сравнения остатков СРЛОС и СР . Совпадение каждого следующего элемента увеличивает переменную результат rez на 1. Если , то вывод результата rez, в противном случае , выполнение сравнения следующего элемента.

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

Шаг 14.Конец алгоритма.

По вышеуказанному алгоритму составлена программа, которая осуществляет определение линейной зависимости остатков для схемы на основе МСРЛОС/СР. Листинг программы приведен в приложении В.1.

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

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

Генераторы на параллельных СРЛОС/СР (ПСРЛОС/СР) для заданной  схемы можно построить путем анализа остатков в цепи СРЛОС/СР [115]. Предположим, что остатки, формируемые разрядами СРЛОС/СР, которые запитывают входы  схемы, являются линейно независимыми, как показано на рис. 2.8а.

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

Триггеры  образуют цепь  СРЛОС/СР, как показано на рис. 2.8в. Обе схемы генерируют псевдоисчерпывающие тестовые последовательности с помощью СРЛОС, имеющих одну и ту же степень  примитивного полинома.

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

Пример 2.3. Спроектировать ГПТ на основе ПСРЛОС/СР для схемы (6,5,3), заданной на рис. 2.6. Выходы триггеров цепи СРЛОС/СР и соответствующие им остатки приведены на рис. 2.9а. Если исключить разряд , заштрихованный на рис. 2.9а, то обеспечивается линейная независимость остатков, которые формируются на входах всех пяти конусов проверяемой схемы.

В соответствии с вышеизложенной методикой синтезируется схема ПСРЛОС/СР, состоящая из двух (3,3) СРЛОС/СР, как показано на рис. 2.9в. Обе схемы СРЛОС/СР основаны на примитивном полиноме . Разряд первого СРЛОС генерируют остатки . Пусть начальное состояние первых трех разрядов равно . Тогда начальные состояния триггеров  определяются путем суммирования по mod2 начальных состояний триггеров первого СРЛОС/СР, что позволяет генерировать (23-1) псевдоисчерпывающих тестов на входах всех пяти конусов схемы в соответствии с рис. 2.9в.

Следующая ниже теорема определяет взаимосвязь между двумя структурами ГПТ на основе МСРЛОС/СР и ПСРЛОС/СР.

Теорема 2.4. Для  схемы существует генератор тестов на основе структуры  ПСРЛОС/СР  тогда и только тогда, когда для этой схемы существует генератор тестов на основе МСРЛОС/СР, у которого длина каждого сдвигово - регистрового сегмента по крайней мере не меньше .

Рис. 2.9. Генератор псевдоисчерпывающих тестов на основе ПСРЛОС/СР:

а) вычисление остатков в цепи СРЛОС/СР;

в) структура ПСРЛОС/СР для (6,5,3) схемы.

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

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

Из теоремы 2.3 следует, что генераторы на основе структуры ПСРЛОС/СР по аппаратурным затратам на их реализацию и по длине генерируемых тестовых последовательностей практически совпадают с генераторами МСРЛОС/СР в том случае, когда сдвигово - регистровые сегменты МСРЛОС/СР кратны степени  примитивного полинома. Если это условие не выполняется, то предпочтительнее использовать генераторы на основе структуры МСРЛОС/СР.

Пример 2.4. Пусть задана (6,7,3) схема, которая является расширением схемы рис. 2.6 путем добавления двух выходных конусов  и . Необходимо построить схему генератора псевдоисчерпывающих тестов минимальной длины.

Так как , то для построения генератора (3,6) на основе МСРЛОС/СР необходимо устранить разряды с линейно зависимыми остатками. Используя остатки, представленные на рис. 2.9а, находим, что выходы  и  не могут запитывать входы  и  (6,7,3) схемы, так как множество остатков  и  для выходных конусов  и , соответственно, являются линейно зависимыми. Следовательно, необходимо увеличить степень примитивного полинома на 1, что приводит к увеличению длины проверяющей последовательности: . Генератор тестов для этой схемы представлен на рис.2.10.

Рис. 2.10. ГПТ для (6,7,3) схемы.

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

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

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

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

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

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

Рис. 2.11. Сигнатурный мониторинг МК.

Схема СА, сохраняющего четность состояний, представлена на рис. 2.12.

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

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

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


(2.6)

(2.7)

Сложив равенства (2.6) по модулю два получаем:

(2.8)

Так как  и

являются элементами паритетного четного кода, то выполняются равенства:

(2.9)

(2.10)

и следовательно

(2.11)

Согласно равенствам (2.9) - (2.11) четный паритет состояния  анализатора сохраняется, если входные векторы имеют четный паритет.

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

Из (2.6) и (2.7) можно заключить, что

(2.12)

и

(2.13)

до тех пор, пока выполняется (2.11).

Покажем синтез многоканального сигнатурного анализатора сохраняющего четность на примере 2.5.

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

Функционирование этого сигнатурного анализатора описывается следующей системой уравнений:


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


Дополнительный триггер  обеспечивает сохранение четности сигнатурного анализатора.

Схема самопроверяемого сигнатурного анализатора сохраняющего четность приведена на рис. 2.13.

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

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


Таблица 2.2.

Значения функций в контрольных точках самопроверяемого МСА.

№ такта












1

1

0

0

0

1

0

0

0

0

0

0

0

2

1

0

1

1

1

1

0

0

0

1

0

0

3

0

1

1

1

1

1

1

1

1

0

0

0

4

1

1

0

0

0

0

0

0

0

0

0

0

5

0

0

1

0

1

1

1

0

0

0

0

0

6

1

1

0

1

1

0

1

0

0

1

0

0

7

1

0

1

0

0

1

1

1

1

0

0

0

8

0

1

0

0

1

1

1

0

1

1

1

1

9

0

0

1

1

0

1

0

1

0

0

1

1

10

1

1

1

0

1

1

1

1

0

1

1

1

11

0

0

0

1

1

0

0

0

1

1

1

1

12

1

1

1

1

0

1

0

0

1

0

1

1

13

1

0

0

1

0

0

0

1

1

0

1

1

14

0

1

0

1

0

1

0

0

0

1

0

0

15

0

1

1

0

0

0

0

0

1

1

1

1

16

1

0

0

0

1

1

1

1

0

1

1

1


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

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

В основу контроля правильности функционирования многоканального сигнатурного анализатора положено аддитивно - циклическое свойство М - последовательностей, т.е. сумма mod 2 циклических сдвигов М - последовательности является циклическим сдвигом той же М - последовательности. Следовательно, операцию сумма mod 2 можно использовать в качестве операции контроля правильности функционирования многоканального сигнатурного анализатора [112].

Проиллюстрируем этот метод на примере сигнатурного анализатора с порождающим многочленом  [70].

Поведение анализатора может быть описано следующими уравнениями:

(2.14)

Складывая равенства (2.14) по модулю два, получаем

(2.15)

Обозначив левую часть равенства через , а правую через , получаем уравнение самоконтроля: А = В

Схема синтезированного таким образом самопроверяемого многоканального сигнатурного анализатора приведена на рис. 2.14.

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



2.6 Выводы

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

Предложен новый метод синтеза ГПТ на основе структуры МСРЛОС/СР, который обеспечивает более простую реализацию ГПТ по сравнению с известными структурами. Для класса  схем определены необходимые и достаточные условия существования ГПТ со структурой МСРЛОС/СР степени .

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

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

РАЗДЕЛ 3 ГЕНЕРАТОРЫ ТЕСТОВ НА СР С НЕЛИНЕЙНОЙ ОБРАТНОЙ СВЯЗЬЮ

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

Различные алгоритмы нахождения этих последовательностей приведены в [65, 72]. Алгоритмы, представленные в этих работах, по своей эффективности оцениваются сложностью программных реализаций в битовых операциях и объемах памяти, необходимых для машинной генерации гамильтоновых циклов. Для реализаций этих вычислений требуется выполнить  побитовых операций и память  бит для вычисления значения функции ОС на каждом шаге генерации полной последовательности [67, 72]. В [74] предложен алгоритм генерации последовательностей Де Брейна, основанный на использовании рекурсивного метода [72], специального языка программирования NESL [73], обеспечивающего простоту сканирования примитивов и механизмов распараллеливания операций. Как отмечает автор этой работы, трансляция этого алгоритма с языка NESL на язык Си позволяет генерировать последовательность Де Брейна длиной  за 5 сек на Spartstation IPC [74].

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

Известно, что в графе   разрядного СР число различных гамильтоновых циклов равно числу остовных деревьев графа  [65]. Остовное дерево графа  есть связный ориентированный граф без циклов с числом вершин  и числом дуг .

Определение 3.1. Ориентированное дерево представляет собой ориентированный граф без циклов, в котором полустепень исхода каждой вершины, за исключением одной вершины (например, ) равна 1, а полустепень исхода вершины , называемой корнем этого дерева равна 0. Такое дерево часто называют входящим [76].

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

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

Этот подход позволяет определить число остовных деревьев для произвольного сильносвязанного графа. Так как граф  n - разрядного СР является сильносвязанным и правильно ориентированным графом, то для вычисления числа остовных деревьев можно воспользоваться более простой процедурой, основанной на использовании его матрицы смежности [77].

Пусть  - граф СР, в котором исключены петли в вершинах  и . Построим матрицу смежности графа  размерности  следующим образом: пересечение i-й строки и i-го столбца матрицы отмечаем числом  - полустепень захода вершины ; пересечение i-й строки и j-го столбца  - числом дуг из вершины  в вершину . В таблице 3.1 представлена матрица смежности графа  - трехразрядного СР, которая позволяет определить число остовных деревьев путем вычисления минора  - го порядка элемента  матрицы смежности . Вычисление определителя D минора элемента  дает величину . Таким образом, существует 16 остовных деревьев в графе  с корнем в вершине .

Таблица 3.1

Матрица смежности графа

Вершины








1-1000000









02-1-10000









0020-1-100









000200-1-1









-1-1002000









00-1-10200









0000-1-120









000000-11










С ростом n число остовных деревьев растет с ростом числа его дуг. В теории графов решению проблемы порождения всех остовных деревьев уделялось значительное внимание, так как выбор “наилучшего” дерева, являлось важным оптимизационным критерием при решении сложных технических задач (в теории управления, при прокладке дорог, газопроводов, линий электропередач, при вычислении определителей матриц в макроэкономической теории и т.д.) [77 - 79].

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

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

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

Таблица 3.2

Таблица переходов автоматных моделей 16-ти остовных деревьев графа .



1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16


















































































































По автоматным моделям остовных деревьев графа  можно найти множество Гамильтоновых циклов в графе  n - разрядного СР по предложенному ниже алгоритму.

Алгоритм 3.1

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

Например, для остовного дерева №1 из таблицы 3.2 построим таблицу переходов в соответствии с шагом 1 (Таблица 3.3)

Таблица 3.3

Таблица переходов.


















2. Построить ТПВ автоматной модели  разрядного СР. Для 3 - разрядного СР ТПВ представляется в виде (Таблица 3.4):

Таблица 3.4


























3. В таблице 3.4 отметим кружком все переходы, соответствующие таблице, полученной на шаге 1. Для наглядности остовное дерево (таблица 3.3) и граф  с отмеченными дугами представлен на рис.3.1

. Начальным состоянием выбрать состояние .

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

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

Процесс завершается при достижении первоначального состояния .

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

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

(3.1)

которая должна формироваться схемой обратной связи СР.

Из последовательности (3.1) СДНФ функции обратной связи СР определяется в виде:

(3.2)

где  - выходы триггеров СР;  - младший разряд.

Минимальная форма функции находится из карты Карно:

(3.2а)

Использование метода синтеза комбинационных схем, основанного на простой дизъюнктивной декомпозиции, позволяет упростить схемную реализацию функции (3.3) по сравнению с МНДФ, представив её в виде [77]:

(3.3)

;

Выражению (3.3) соответствует схема, представленная на рис. 3.2

Рис. 3.2. Схема, соответствующая выражению (3.3)

Анализ функции (3.2) обратной связи 4 - разрядного СР, порождающий Гамильтонов цикл в графе переходов , показывает, что эта функция удовлетворяет условиям реализуемости ее сетью Майтра [77], т.е. представляется в виде:

(3.4)

Выражению (3.4) соответствует схемная реализация функции обратной связи СР, на рис. 3.3.

Рис. 3.3. Реализация ОС сетью Майтра.

Для оценки аппаратурных затрат на реализацию встроенных схем диагностирования воспользуемся оценочной методикой фирмы Synopsys Inc., которая была разработана для КМОП технологии производства интегральных схем (0,6 мкм, 2 - слойная металлизированная подложка, 5V питание) [78]. В качестве единичного вентильного эквивалента (в.э.) используется 2 - входовый И-НЕ (ИЛИ-НЕ) элемент. Аппаратурные затраты оцениваются, исходя из технологических затрат на реализацию различных схемных элементов, представленных в вентильных эквивалентах (Табл. 3.5)

Таблица 3.5

Методика оценки аппаратурных затрат Synopsys Inc.

2-вх. И(ИЛИ)

1,3в.э.

2-вх. ИСКЛ.-ИЛИ

2,0в.э.

2 на 1 мультиплексор

1,7в.э.

D-триггер

3,6в.э.

3-вх. И- НЕ(ИЛИ-НЕ)

1,5в.э.

Инвертор

0,7в.э.


Представляя выражение (3.2а) и (3.4) в базисах И-НЕ элементов с целью сравнения затрат на реализацию функций обратной связи СР, порождающих Гамильтонов цикл в графе , и используя данные таблицы 3.5, получим:

Реализация по МДНФ -7,0 в.э.

Реализация декомпозиционным методом -5,7 в.э.

Реализация сетью Майтра -3,5в.э.

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

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

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

Однородными сетями Майтра называют одномерную структуру, состоящую из последовательно соединенных двухвходовых ячеек-вентилей, которые настраиваются на реализацию логической функций И, ИЛИ, Исключающее ИЛИ, И-НЕ, ИЛИ-НЕ [81]. На рис. 3.4 представлена одномерная сеть Майтра, которая настраивается на реализацию функции  путем приложения к вертикальным входам  входных переменных , а на крайний слева боковой вход подается 0(1).

        Рис. 3.4. Одномерная сеть Майтра.

Различают бесповторные и повторные сети Майтра [82]. В бесповторных сетях каждая переменная  запитывает вход только одной ячейки сети, в противном случае сеть называют повторной. Наиболее подробно свойства таких сетей и методы их настройки для реализации различных логических функций представлены в [81 - 84].

Известно, что любая функция двух переменных реализуется бесповторной сетью Майтра, состоящей по крайней мере из двух ячеек [81].Однако не все логические функции с  реализуемы бесповторными сетями Майтра. Для анализа реализуемости функций такими сетями и настройки и настроек ячеек сети чаще всего используются аналитические методы. Наиболее подробно и обоснованно эти методы представлены в [82]. Процедуры анализа реализуемости произвольной ЛФ и методы синтеза в этих подходах основаны на анализе ЛФ декомпозиционными методами, что требует на каждом шаге выполнения синтеза схемы применять разложение Шеннона относительно каждой переменной  для исходной ЛФ и всех остаточных функций.

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

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

Например, для ЛФ  минтермная матрица представлена в табл.3.6.

Таблица 3.6


x1

x2

x3

4

1

0

0

6

1

1

0

7

1

1

1


Совершенная дизъюнктивная нормальная форма функции (СДНФ) равна:

(3.5)

Выражение (3.5) можно представить в виде:

(3.6)

Из (3.6) следует, что последним элементом сети Майтра является элемент И, вход которого необходимо запитать переменной , как показано на рис. 3.5.

Рис. 3.5. Конечная ячейка сети Майтра для функции .

Выражение (3.6) и реализацию функции, как показано на рис. 3.5, можно получить путем анализа минтермной матрицы Табл. 3.6. Этот анализ осуществляется следующим образом: пусть  - число минтермов заданной ЛФ, а  - число единиц в столбце . Для рассматриваемой функции .

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

Доказательство. Если крайний правый элемент сети - элемент И, то ЛФ представляется в одной из двух форм:

(3.7)

Или

(3.8)

Следовательно, столбец  в минтермной матрице для выражения (3.7) состоит из единиц и , а для выражения (3.8) - из одних нулей и . Если число , то заданная ЛФ является тривиальной функцией - переменной . Если , то  единичных значений покрывается  и последним элементом не может быть И, так как функция представляется в виде

(3.9)

Следовательно,  . Утверждение доказано.

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

Доказательство. Если крайний правый элемент сети - ячейка ИЛИ, то ЛФ представляется двумя формами:

выражение (3.9), рассмотренное выше

или

(3.10)

В выражении (3.9)  минтермов ЛФ в столбце  должны иметь значение 1, чтобы обеспечить появление в правой части переменной . Следовательно, . В случае, когда в правой части выражения (3.10) появляется , то в столбце  минтермной матрицы должно быть  нулевых значений, а, следовательно, число единиц в столбце  в этом случае равно . Утверждение доказано.

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

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

Доказательство. Если крайним правым элементом сети является элемент Исключающее ИЛИ, то ЛФ представляется в виде:

(3.11)

Или

 (3.12)

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

Из доказательства Утверждений 3.2 и 3.3 следует, что остаточные функции после удаления столбца  минтермной матрицы можно выбирать двумя способами: удалением строк минтермной матрицы с “1” или “0” значениями входных наборов в столбце . В первом случае на вертикальный вход последнего элемента следует подавать переменную , во втором случае . Выбор остаточной функции с минимальным числом минтермов этой функции упрощает дальнейшую процедуру синтеза всей однородной сети Майтра.

Пример 3.1. Реализовать одномерной бесповторной сетью Майтра функцию . Минтермная матрица этой функции представлена в Табл. 3.7.

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

Для остаточной функции  и Таблица 3.8 содержит  минтермов, что в соответствии с Утверждением 3.3 позволяет утверждать: крайним правым элементом для  может быть только элемент Исключающее ИЛИ. Анализ Таблицы 3.8 показывает, что удаление столбца  обеспечивает условие реализуемости функции  сетью Майтра. При этом имеются два варианта для формирования остаточной функции : удаление строк минтермной матрицы для единичных и нулевых значений наборов в столбце  (Таблицы 3.9 и 3.10 соответственно). Это дает два варианта реализации функции сетью Майтра, как это показано на рис. 3.6а,в.

Для сравнения рассмотрим схемную реализацию функции примера 3.1 классическим методом по минимальной дизъюнктивной нормальной форме ЛФ. Из карты Карно функции (Таблица 3.11) ее МДНФ представляется в виде:

(3.13)

Реализация схемы в соответствии с выражением (3.13) уступает схемным реализациям этой функции бесповторной сетью Майтра (рис. 3.6) по аппаратурным затратам.

Рис. 3.6. Два варианта реализации ЛФ примера 3.1 одномерной бесповторной сетью Майтра.

Таблица 3.11

Карта Карно функции примера 3.1


Применяя эти оценки к реализациям функции на рис. 3.6 и к схеме в соответствии с МДНФ (3.13), получаем:

затраты на реализацию бесповторной сетью Майтра составляют 4,0 в.э.;

затраты на реализацию по МДНФ - 9,1 в.э.

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

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

Алгоритм 3.2 синтеза ЛФ одномерной бесповторной сети Майтра.

Шаг 1: Построить минтермную матрицу для заданной ЛФ  переменных.

Шаг 2: Вычислить число минтермов  заданной ЛФ. Если  - перейти к шагу 3. Если  - перейти к шагу 8.

Шаг 3: Вычислить для каждого столбца  минтермной матрицы число единиц . Если  перейти к шагу 4, если  перейти к шагу 6.

Шаг 4: Найти в минтермной матрице столбец , для которого  или . В этом случае крайним правым элементом сети является элемент И. Если , то на вертикальный вход подать , если . В противном случае перейти к шагу 11.

Шаг 5: Построить минтермную матрицу остаточной функции путем удаления столбца . Перейти к шагу 10.

Шаг 6: Найти в минтермной матрице столбец , для которого  или . В этом случае крайним правым элементом сети является элемент ИЛИ. Если , то на вертикальный вход подать , если , то подать . В противном случае перейти к шагу 11.

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

Шаг 8: Найти в минтермной матрице столбец , удаление которого дает остаточную минтермную матрицу с  различными строками. В этом случае крайним правым элементом является Исключающее ИЛИ, который следует запитать переменной . В противном случае перейти к шагу 11.

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

Шаг 10: Уменьшить  на единицу. Если , то определить функцию крайнего левого элемента сети. Перейти к шагу 12. Если , перейти к шагу 2.

Шаг 11: Заданная функция нереализуема бесповторной сетью Майтра.

Шаг 12: Конец алгоритма.

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

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

По аналогии со структурой ГПТ на СРЛОС/СР (рис.2.4а) генератор тестов на сдвиговых регистрах с нелинейной обратной связью (СРНОС) для псевдоисчерпывающего тестирования (n,m,k) схем имеет структуру, представленную на рис. 3.7. Первые k разрядов генератора на СР с нелинейной функцией обратной связи  формируют  различных двоичных векторов, которые через k тактов сдвигаются в цепи СР, определяя на каждом такте значения разрядов  в СР. Так как длина цикла СРНОС равна , то максимальная размерность цепи генератора на СРНОС/СР . Условие формирования в  разрядах СР различных двоичных k - мерных векторов определяется нижеследующим утверждением.

Рис.3.7. Структура ГПТ на СРНОС.

Теорема 3.2. Пусть задана схема ГПТ на СРНОС/СР длиной в n разрядов, в котором разряды  формируют полный цикл длиной  различных двоичных векторов с помощью функций нелинейной ОС , порождающей гамильтонов цикл в k - разрядном СР. Если начальные состояния всех n разрядов ГПТ совпадают со значениями функции , сдвинутых на  тактов, то на выходах любых k смежных разрядов ГПТ формируются  различных тестовых набора за  тактовых сдвигов регистра.

Доказательство.Так как на вход первого триггера СРНОС поступает двоичная последовательность, формирующая гамильтонов цикл в k - разрядном СР, то за  тактов на выходе  сформируется функция ОС , которая на выходе  будет сдвинута на k тактов, на  - на  тактов и т.д., а на выходе  - на  тактов. Следовательно, формирование на любых k смежных выходах , всех  тестовых наборов за  тактов возможно, если начальное состояние разряда  СРНОС/СР будет эквивалентно значению функции  на  такте, что обеспечит генерацию гамильтоновых циклов на любых k смежных разрядах СР цепи . Теорема доказана.

Для иллюстрации условий установки начальных состояний ГПТ на СРНОС/СР в соответствии с Теоремой 3.2 рассмотрим пример ГПТ для  и  (рис.3.8).

Нелинейная обратная связь формируется схемой, реализующей функцию ; которая формирует Гамильтонов цикл в разрядах СР  с начальной установкой . Начальная установка соответствует 0 - му такту функционирования генератора. Как видно из рис.3.8а, любые смежные три разряда генератора формируют 8 различных 3 - мерных векторов, при начальной установке их в соответствии с условиями Теоремы 3.2, что иллюстрируется на рис.3.8б.

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

Следствие 3.1. Разряды СРНОС/СР  являются смежными и образуют полный Гамильтонов цикл в k - разрядном СР.

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

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

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

       а)                                                     в)

Рис.3.8 Функциональная схема ГПТ на СРНОС/СР для ,  (а) и формирование начальной установки триггеров СР (в)

Рис.3.9 Схема ГПТ, эквивалентного по поведению схеме рис. 3.8

В общем случае если , схема ГПТ на СРНОС/СР в соответствии с Теоремой 3.2 генерирует k - мерные тривиальные тестовые наборы, подаваемые на n входов проверяемого устройства.

Определение 3.2. Последовательность k - мерных двоичных векторов длиной , в которой все векторы различны, будем называть счетчиковой последовательностью.

Пусть  - выходы разрядов СРНОС/СР, а  - входы проверяемой  схемы.

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

Определение 3.3. Пара входных переменных   схемы является зависимой, если существует по меньшей мере один выходной конус из множества m, который одновременно зависит от  и . В противном случае пара  является независимой.

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

Таким образом, задача синтеза ГПТ на СРНОС/СР для тестирования  схем псевдоисчерпывающими тестами сводится к нахождению минимального числа максимальных подмножеств независимых входных переменных , что позволяет для заданной схемы определить минимальную длину тестовой последовательности, которая может находиться в пределах .

Известно, что необходимость решения задач поиска подмножеств, которые обладают определенными наперед заданными свойствами, часто возникает при планировании исследовательских работ, в кластерном анализе, параллельных вычислениях на ЭВМ, решении ряда логических задач, при размещении источников и потребителей в энергосистемах и др. [85].

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

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

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

Процедура синтеза ГПТ на СРНОС/СР для  схем представлена следующим ниже алгоритмом.

Алгоритм 3.3.

Шаг 1.По заданной схеме вычислить подмножества переменных , где , от которых зависит j - ый конус схемы, и

Шаг 2.Установить .

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

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

Шаг 5. Выполнить операцию вычитания множеств переменных .

Шаг 6.Если , то множество переменных независимых с  записать в память. Если , то включить  в список полностью зависимых вершин .

Шаг 7.Установить . Если , то перейти к шагу 3. Если , то перейти к шагу 8.

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

Шаг 9. Поставить в соответствие каждой переменной  вершину графа  независимых переменных.

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

Шаг 11.Установить .

Шаг 12.Выполнить операцию пересечения  двух строк матрицы D. Множество вершин  является кликой графа . Записать  в регистр  клик графа .

Шаг 13.Выполнить операцию вычитания множеств ;

Шаг 14.Если , то определено полное множество клик, которые включают вершину . Перейти к шагу 15. Если , то перейти к шагу 12.

Шаг 15.Установить . Если , то перейти к шагу 12. В противном случае к шагу 16.

Шаг 16.Найти минимальное покрытие множества X входных переменных множеством клик  графа  независимых вершин, что определяет минимальную разрядность ГПТ на СРНОС/СР.

Шаг 17.Конец алгоритма.

Пример  схемы, приведенный ниже, иллюстрирует процедуру синтеза ГПТ на СРНОС/СР в соответствие с Алгоритмом 3.3.

Пример 3.2. Пусть заданы схема, имеющая 8 входов и 8 выходов. В результате выполнения шага 1 Алгоритма 3.3 определена конусная зависимость  в следующем виде:






Выполняя последовательность шагов 2, 3, 4 алгоритма находим подмножества переменных , связанных отношением зависимости с  в виде:


Выполнив операцию вычитания множеств  на шаге 5 алгоритма, с учетом поправок на множество полностью зависимых переменных  и , определяемых на шаге 6, 7, и 8, находим подмножества независимых переменных , которые представлены графом независимых вершин на рис.3.10 (шаг 9).

Рис.3.10 Граф независимых вершин примера 3.2

На шаге 10 строим матрицу достижимостей D вершин графа независимых вершин (рис.3.11).

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







100110







010111







001001







110101







110010







011101







Рис.3.11 Матрица достижимостей графа на рис. 3.10.

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

Для рассматриваемого примера матрица покрытий представляется в следующем виде (табл.3.12):

Таблица 3.12

Матрица покрытий для примера 3.2

Клики графа







100100







100010







010010







010101







001001







 

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



(3.14)






В (3.14) знак “+” обозначает логическую операцию дизъюнкции.

Множество решений системы уравнений (3.14) находится путем нахождения конъюнктивных термов, входящих в уравнение:

(3.15)

Так как a5 поглощает дизъюнкцию (а4+ a5), то уравнение (2.20) представляется в виде:

(3.16)

Из (3.16) следует, что существует два решения системы уравнений (3.14) с минимальным числом булевых переменных, входящих в конъюнктивные термы: .

Таким образом, минимальные множества клик, покрывающие все вершины графа независимых вершин исходной (8, 8, 4) схемы представляются в виде:

(3.17)

Объединяя множества  и  с множеством  полностью зависимых вершин , определенных на шаге 6 алгоритма, получаем:

(3.18)

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

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

(3.19)

Условие (3.19) не выполняется для блоков разбиения , так как . Обеспечивая выполнение условия (3.19) в  так, чтобы объединение всех блоков разбиения включало множество всех входных переменных , получаем:

(3.20)

Таким образом, разбиение  множества входов  схемы примера 3.2 на блоки, объединяющие подмножества независимых переменных, являются функциональным описанием трех схем генераторов псевдослучайных тестов для КС (8, 8, 4) с заданной конусной зависимостью. Так как мощность множеств , то выбрав функцию нелинейной обратной связи СР в виде:

(3.21)

можно легко построить три варианта схем ГПТ, которые представлены на рис. 3.12. Функция обратной связи  позволяет генерировать гамильтонов цикл в 5 - разрядном СР и реализуется сетью Майтра, что обеспечивает минимальность аппаратурных затрат на схему генератора. Выбор этих решений осуществляется на основе Алгоритмов, представленных в разделах 3.1. и 3.2.

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

Применение процедуры синтеза ГПТ на сдвиговых регистрах с нелинейной ОС, представленной в разделе 3.3, для схемы (8, 8, 4) примера 3.2 обеспечивает псевдоисчерпывающее тестирование схемы тестовой последовательностью длиной в 32 двоичных наборов. Это определяется отношением зависимости входных переменных, которое устанавливается путем нахождения минимального покрытия этих переменных множеством клик графа независимых входов и условиями генерации СРНОС/СР исчерпывающих тестов в соответствии с Теоремой 3.2.

а) Схема ГПТ, соответствующая разбиению .

) Схема ГПТ, соответствующая разбиению .

) Схема ГПТ, соответствующая разбиению .

Рис.3.12.Схема ГПТ на СРНОС/СР с функцией ОС (3.21) для КС (8,8,4) примера 3.2

Так как проверяемая схема имеет конусную зависимость ее выходов от входных переменных , то схема может быть проверена псевдоисчерпывающими тестами длиной . Возникает вопрос: существует ли схемная реализация такого генератора на основе СРНОС/СР?

Из Теоремы 3.2 следует, что в СРНОС/СР длиной  при СРНОС размерности k лишь любые смежные k разрядов формируют счетчиковые последовательности. Поэтому в СРНОС/СР не существует разряда, не смежного с  смежными разрядами СРНОС/СР, который в сочетании с ними позволяет сформировать k - разрядную счетчиковую последовательность. Следующее ниже утверждение определяет условия формирования разряда, обладающего таким свойством.

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

,

где  - нелинейная булевая функция.

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

Функции возбуждения триггеров цепи СРНОС равны:

(3.22)

Так как функция возбуждения разряда Sk+1 равна:

(3.23)

Суммируя по mod2 левые и правые части равенств (3.22) и (3.23) получаем:

(3.24)

Так как разряды СР  вместе с нелинейной обратной связью генерируют  различных двоичных векторов, т.е. счетчиковую последовательность тестовых наборов, то формирование k - мерного вектора  в сочетании с разрядом  обеспечивается, если . Так как , то левая и правая часть равенства (3.24) равны 0, т.е.

(3.25)

Так как текущие состояния разрядов СР  и последующие состояния  в сумме по mod2 эквивалентны, то равенство (3.24) выполняется для всех  наборов разрядов . Из равенства (3.25) следует, что

(3.26)

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

Предложенный подход определяет условие формирования в ГПТ на СРНОС/СР разряда, позволяющего в 2 раза сократить длину тестовой последовательности.

Обратимся вновь к примеру 3.2. Длина тестовой последовательности в этом примере определяется мощностью разбиения . Так как , то схема проверяется генератором псевдоисчерпывающих тестов в котором 5 выходов в любом сочетании должны обеспечить приложение к входам всех 8 конусов схемы различных двоичных наборов. В схеме СРНОС/СР это обеспечивается тестовой последовательностью длиной  и схемами на рис.3.12.

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

Схема ГПТ на основе СРНОС/СР, построенного в соответствии с предложенной методикой минимизации длины проверяющей последовательности, приведена на рис.3.13.

 

Рис.3.13 Схема ГПТ на СРНОС/СР,  (пример 3.2) .Аппаратурные затраты 5,4 в.э.

Для примера 3.2  схемы синтезируем ГПТ на основе метода МСРЛОС/СР, представленного в разделе 2.2. Обеспечить линейную независимость остатков для исчерпывающего тестирования заданной схемы (8, 8, 4) удается лишь для СР с линейной обратной связью на основе неприводимого полинома  разрядностью равной 5, что определяет длину теста . Так как начальная установка СР не равна 0, то для формирования вектора  необходимо использовать два мультиплексора 2 на 1. При этом схема управления процессом тестирования усложнится введением дополнительной процедуры. С учетом вышеуказанного аппаратурные затраты на реализацию схем генераторов на рис.3.13 и 3.14 равны 5,4 в.э. и 6,4 в.э. соответственно.

Преимущество ГПТ на СРНОС/СР как по длине псевдоисчерпывающего теста, так и по аппаратурным затратам, очевидно.

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

В [64] предложен простой подход к построению генератора последовательности де Брейна, состоящий из двух этапов:

формирование элементарной конъюнкции вида

(3.27)

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

если формирующий многочлен имеет вид

j(x) = xp + xa + xb + …+ xj + 1(3.28)

где j - наименьший показатель степени, входящий в j(x),

то функция обратной связи генератора последовательности де Брейна реализуется по формуле:

F(x) = xp Å xa Å xb Å … Å (xj + mj)(3.29)

где mj - элементарная конъюнкция.

Однако, при разрядности n > 7 генераторы с такой структурой не вырабатывают полный цикл длиной L = 2n.

Рис.3.14. Схема ГПТ на МСРЛОС/СР, полином f(x)=х5+х3+1, L=25=32,

В настоящем разделе предлагается расширение этого метода для получения генератора последовательности де Брейна разрядности  [116]. Для объединения всех смежных циклов предлагается ввести дополнительный элемент И - НЕ по следующему алгоритму:

формируется m циклов исходного СР, каждый из которых имеет начальное состояние xa = xb =…= xw = 0;

определяются смежные циклы, которые содержат левосопряженные состояния;

определяются отсутствующие в последовательности смежные циклы и соответствующие им левосопряженные состояния;

объединяются смежные циклы с помощью элемента И - НЕ для генерации полного цикла.

Дальнейшие исследования показали, что данный подход пригоден для синтеза генераторов последовательности де Брейна разрядности n = 16. В качестве примера рассмотрим СР с порождающим многочленом j(x) = x16 + x12 + x3 + x + +1.

Согласно [64] функционирование генератора описывается формулой:

(3.30)

Полученная таким образом последовательность имеет длину L = 63770 и содержит следующие левосопряженные состояния:

- 0000100000000100

- 0000100000000001

- 0000100000000000

- 0000100000000101

- 0000000000000100

- 0000000000000001

Отсутствующие левосопряженные состояния:

- 0000000000000101

- 0000000000000000

Подчеркнутые векторы в последовательности отсутствуют. Для введения в последовательность цикла с начальным состоянием 1000100000000000 включим в схему элемент И - НЕ.

Особыми точками последовательности являются те, в которых значения переменных x2, x4, x5, x6, x7, x8, x9, x10, x11, x13, x14, x15 равны нулю. Именно эти точки предшествуют левосопряженным состояниям и определяют переходы в смежные циклы. Согласно [116] отличительными являются значения элементов x1, x3, x12. Для получения нуля на выходе элемента И-НЕ в состоянии 0001000000000001 необходимо на входы элемента И-НЕ подать значения . Таким образом, функция обратной связи определяется по следующей формуле:

(3.31)

Схема генератора последовательности де Брейна показана на рис. 3.15.

По вышеуказанному алгоритму составлена программа, которая осуществляет синтез многочлена обратной связи СРНОС для генерации последовательностей де Брейна. Листинг программы приведен в приложении В.2. В приложении Г приведены все примитивные многочлены степени 16 с минимальным числом элементов в цепи обратной связи и соответствующие функции обратной связи для получения последовательностей де Брейна. При этом длина последовательности L будет равна максимальному значению (L = 65536).

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

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

Известно, что если ДУ описано моделью автомата Мили или Мура, представленного в минимальной форме, то сложность его схемной реализации определяется вариантом кодирования внутренних состояний автомата [117].

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


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

Таблица 3.13.

ТПВ автомата А3.1.

Z(t)

Z(t+1), l(t)


xi

x0

A

.

B , 1

B

.

C , 1

C

.

D , 0

D

.

E , 0

E

.

A , 0


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

Таблица 3.14.

Кодированная ТПВ автомата А 3.1.

z1

z2

z3

Z(t+1), l(t)




xi

x0

0

0

0

.

100 , 1

1

0

0

.

110 , 1

1

1

0

.

011 , 0

0

1

1

.

001 , 0

0

0

1

.

000 , 0


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

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

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

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

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

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

Рис. 3.16. Структурная модель модифицированного автомата.

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

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

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

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

На рис. 3.17 и 3.18 представлены схемы декадного двоично-десятичного счетчика и четырехразрядного счетчика, которые синтезированы предложенным выше методом. Счетчики имеют два выхода:  - выход переноса,  - диагностический выход, на котором формируется последовательность . Функции обратной связи реализуются цепями Майтра. Длина отличительной последовательности обоих схем равна . Введение дополнительного диагностического выхода  не влечет за собой введение дополнительных аппаратурных затрат для реализации выходных функций.

3.7 Выводы

Проведен анализ существующих методов и алгоритмов генерации исчерпывающих двоичных последовательностей Де Брейна на сдвиговых регистрах с нелинейной ОС. Показано, что задача синтеза ГПТ на СРНОС эквивалентна нахождению остовных деревьев в графе СР, которые порождают гамильтоновы циклы в этом графе.

Предложена универсальная конечно-автоматная модель остовных деревьев графа n - разрядного СР и разработан алгоритм нахождения гамильтоновых циклов в графе (n+1) разрядного СР по автоматным моделям графа n - разрядного СР. Показано, что существует класс остовных деревьев, которые порождают гамильтоновы циклы в графе СР с минимальной аппаратурной реализацией ОС в виде бесповторной сети Майтра.

а)


T1

T2

T3

T4

0

1

0

0

0

1

1

1

0

0

2

0

1

1

0

3

0

0

1

1

4

1

0

0

1

5

0

1

0

0

6

1

0

1

0

7

0

1

0

1

8

0

0

1

0

9

0

0

0

1

b)

Рис. 3.17. Декадный двоично - десятичный счетчик:

а) функциональная схема;

b) последовательность счета.

а)


T1

T2

T3

T4

0

0

0

0

0

1

1

0

0

0

2

1

1

0

0

3

1

1

1

0

4

1

1

1

1

5

0

1

1

1

6

1

0

1

1

7

0

1

0

1

8

1

0

1

0

9

1

1

0

1

10

0

1

1

0

11

0

0

1

1

12

1

0

0

1

13

0

1

0

0

14

0

0

1

0

15

0

0

0

1

b)

Рис. 3.18. Четырехразрядный двоичный счетчик

а) функциональная схема) последовательность счета.

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

Предложен метод синтеза ГПТ на основе СРНОС/СР. Определены условия начальной установки разрядов СР, обеспечивающие генерацию гамильтоновых циклов на любых “k” смежных разрядах генератора. Показано, что задача синтеза ГПТ на СРНОС/СР для тестирования (n, m, k) схем сводится к нахождению минимального числа максимальных подмножеств независимых входных переменных (клик графа СР) и нахождению минимального покрытия множества входных переменных кликами этого графа, что обеспечивает построение ГПТ минимальной размерности с минимальной длиной проверяющей последовательности. На основе предложенного подхода разработан алгоритм синтеза.

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

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

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

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

В последнее время растет число исследований, связанных с однородными сетями элементарных автоматов, т.е. с сетями, состоящими из однотипных и одинаково соединенных автоматов. Таким сетям под различными названиями - итеративные сети, однородные среды, автоматы Неймана - Чёрча, клеточные автоматы и т.д. посвящено большое число исследований [76, 86 - 96].

В конце 50-х годов теория однородных структур, у истоков которой стояли известные ученые Дж. Фон Нейман, С. Улам, А Чёрч, Э. Мур и др. привлекла к себе внимание многих исследователей. Интерес к таким объектам возник из двух различных источников. С одной стороны, это дальнейшее развитие идей Дж. Фон Неймана, который использовал понятие клеточного автомата для исследования условий, при которых машины способны к самовоспроизведению и самоорганизации [86]. С другой стороны, построение машин клеточных автоматов является перспективным направлением использования возможностей современных субмикронных технологий в электронной промышленности.

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

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

Для элементарных научных проблем эксперимент может потребовать вычисления миллиарда событий (событием является обновление одной клетки), для более сложных приложений может быть желательным значение в тысячу или миллион раз больше (т.е.  событий) [97].

В связи с этим существующие компьютеры мало пригодны для решения этих задач. Моделирование одного события в клеточном автомате может потребовать последовательного выполнения до нескольких десятков машинных команд, скажем 10 мксек, на быстродействующем компьютере. Для того, чтобы вычислить  событий при таком подходе потребуется 8 месяцев. Для сравнения двумерная сеть КА, содержащая  клеточных автоматов (это несколько грубее, чем разрешающая способность телевизионного кадра) выполнит моделирование  событий за 0,5 сек.

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

СКА характеризуется четырьмя основными параметрами: геометрия связей соседних КА, числом состояний КА и алгоритмом вычисления последующих состояний [98]. Изменение каждого из перечисленных выше параметров позволяет конструировать различные СКА, отличающиеся своими свойствами. Использование двумерных СКА для решения многих задач распознавания образов и связанных с ними проблемами, моделирование гидродинамических процессов и других физических явлений, в основе которых лежит статистическая механика, демонстрирует потенциальные возможности СКА с учетом простоты их схемной реализации на СБИС [97]. В качестве примера для этой демонстрации можно привести СКА, структуру которого и систему правил определил в 1970 г. известный математик Дж. Конвей для игры в «Жизнь» [87].

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

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

Такие СКА широко используются в качестве генераторов псевдослучайных последовательностей [88 - 95]. Достоинствами таких генераторов является простота (каждая клетка связана только с ближайшими соседними клетками) и регулярность структуры [99]. Увеличение разрядности устройств связано лишь с добавлением однотипных ячеек. В клеточных автоматах отсутствуют глобальные обратные связи, которые характерны для СРЛОС. Кроме этого, в КА отсутствует многовыходной элемент сумма mod 2, который вносит определенные временные задержки [99].

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

Различают одномерные и двумерные сети клеточных автоматов. Наибольшее практическое применение нашли структуры клеточных автоматов, у которых клеточные автоматы имеют два состояния [95].

Одномерные структуры КА представлены на рис. 4.1. Клеточный автомат имеет достаточно простую структуру и состоит из триггера M, имеющего два состояния, и комбинационной схемы (КС), реализующей функцию возбуждения М, равную

(4.1)

где  - текущие состояниия соседних КА, расположенных слева и справа от ячейки , соответственно.

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

Рис. 4.1. Структуры одномерных сетей КА:

Структурная схема клеточного автомата;

Структура одномерной сети КА длиной n с нулевыми граничными условиями;

Структура одномерной сети КА длиной n с обратными связями.

Правило настройки - это удобный способ представления зависимости состояния клетки от состояний соседних клеток. Например, правило 150, связанное со следующей таблицей переходов (табл. 4.1), реализуется комбинационной логикой следующим образом:


где z - состояние клетки в определенный момент времени.

Таблица 4.1

Таблица переходов СКА с правилом 150.




0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1


Номер правила - это десятичное значение, представляющее функцию таблицы переходов этой 3 - связной СКА. Существует 256 различных правил, определяющих таблицы переходов 3 - связных СКА.

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

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

Существует 10 различных правил настройки аддитивных СКА.

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

Все правила настройки в алгебраической форме представлены в таблице 4.2.

В [100] предложено правила настройки СКА, которые определяются логическими операциями сумма mod 2 называть безинверсными, а операциями эквивалентность называть инверсными правилами. Как видно из табл. 4.2. в гибридной СКА могут иметь место инверсные и безинверсные правила настройки.

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

Таблица 4.2

Аддитивные правила для СКА.

Правило

Функция

204

51

60

195

102

153

90

165

150

105


Правило 204: .

Это правило является просто правилом тождественности, которое не изменяет состояний СКА. Таким образом, правило 204 образует цикл длиной  для всех СКА. Поведение правила 51 такое же.

Правило 60: .

Утверждение 4.1. Правило 60 формирует циклы любой длины , где  - число клеток в СКА, .

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

Правило 102: .

Так как это правило является симметричным отображением правила 60, то СКА с этими правилами настройки имеет тот же порядок циклических последовательностей.

Правило 90: .

В [88] показано, что правило 90 образует циклические последовательности ограниченной длины тогда и только тогда, когда .

Правило 150: .

Для правила 150 экспериментально показано, что циклы формируются только при условии  [88].

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

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

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

Последовательность, генерируемая  - клеточной СКА, может быть однозначно представлена многочленом степени . Например, для 8 - клеточной СКА состояние, характеризуемое 8 разрядами, например 10111010, может быть представлено многочленом

(4.2)

На 8 - разрядном пространстве векторов это состояние может быть представлено вектором - строкой в виде:

(4.3)

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

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

Определение 4.3. Квадратная матрица размерности , представляющая правила настройки клеточных автоматов сети, называется характеристической матрицей СКА, в которой  - я строка матрицы представляет правило настройки  - го клеточного автомата.

В соответствии с определением 4.3 характеристическая матрица СКА размерности  с нулевыми граничными условиями и геометрией связей только с ближайшими соседями представляется в виде:

(4.4)

где  отображают правила настройки  - го клеточного автомата сети.

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

Например, характеристическая матрица СКА размерности  представляется в виде:

(4.5)

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

Пример 4.1. Пусть дана 4 - клеточная СКА с нулевыми граничными условиями со следующими правилами <90, 204, 60, 150>.

Воспользовавшись таблицей 4.2 и введенными обозначениями (4.5), характеристическую матрицу СКА представим в виде:


Первая строка представляет правило настройки 90:  и т.д. Если СКА имеет периодические граничные условия, то крайние столбцы матрицы являются соседними и отмечаются символами  при соответстсвующих настройках.

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

Характеристическая матрица СКА (в дальнейшем Т - матрица) позволяет представить функцию переходов автоматной модели аддитивной сети клеточных автоматов в виде:

(4.6)

где  - состояние СКА в момент времени , а  - состояние СКА в момент времени .

Если настройка СКА позволяет генерировать циклическую последовательность, то для всех  должно существовать целое число  такое, что [118]

(4.7)

где  - единичная матрица.

(4.8)

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

Правило 195 () является инверсией правила 60 (). Однако, поскольку операция эквивалентность не может быть представлена в мультипликативной форме, то обозначим ее . Таким образом,  представляет обозначение соответствующей функции сумма mod 2. Исходя из этого, последующее состояние СКА определяется через инверсное правило в виде:

(4.9)

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

Пример 4.2. Однородная 4 - клеточная СКА с нулевыми граничными условиями и аддитивным инверсным правилом 195 (), последовательно используемым на полном цикле, представляется в виде:


Где


где Т матрица соответствует правилу 60 .

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

(4.10)

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

Пример 4.3. Гибридную 4 - клеточную СКА с нулевыми граничными условиями и правилами <60, 51, 153, 153>, можно представить в матричной форме следующим образом:

 

где Т соответствует СКА с правилами  и задается в виде:


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

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


Соответственно,  представляется в виде


Таким образом, инверсные правила настройки однородной и гибридной СКА также можно представить в матричной форме.

Утверждение 4.2. Пусть обозначает последовательное применение инверсного правила   раз. Тогда

(4.11)

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

Доказательство: Так как

(4.12)

Тогда

(4.13)

Таким образом, может быть выражено через степени  (где Т - характеристическая матрица с безинверсными правилами). Утверждение доказано.

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

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

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

Пусть мы имеем , где  - квадратная матрица с элементами над полем .

Утверждение 4.3. Сеть клеточных автоматов генерирует множество векторов со свойствами группы тогда и только тогда, когда .

Доказательство приведено в приложении А.1.

Для алгебраически инверсных правил настройки СКА справедливы нижеследующие утверждения.

Утверждение 4.4. Если СКА с характеристической матрицей  генерирует группу, то ее инверсия  также имеет свойство группы.

Доказательство приведено в приложении А.2.

Утверждение 4.5. Если R - правила настройки, формирующие группу, то  также формирует группу, где  представляет собой правило, полученное путем одной из возможных перестановок правил R или  в каждой клетке СКА.

Доказательство приведено в приложении А.3.

Следствие: Если какая-либо перестановка  формирует группу, то  также будут формировать группу.

Этот вывод справедлив для любого числа правил и СКА любой длины .

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

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

Доказательство приведено в приложении А.4.

Утверждение 4.7. Если длина цикла является составным числом, то СКА генерирует циклические последовательности длиной, равной его множителям.

Доказательство приведено в приложении А.5.

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

Пример 4.4. Пусть 4 - клеточная СКА с нулевыми граничными условиями и правилом 90  имеет следующую характеристическую матрицу:


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


Следовательно, в соответствии с вышедоказанными утверждениями, при ненулевых начальных условиях СКА генерирует циклы длиной 3 и 6, но не 1 и 2.

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

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

СРЛОС с  разрядами можно представить в виде гибридной аддитивной СКА, в которой функция возбуждения крайней левой клетки (входной клетки) содержит  компонентов, а для остальных клеток - зависит только от ближайшей слева клетки.

На рис. 4.2 показан 4 - разрядный СРЛОС со следующим характеристическим многочленом:

(4.14)

Рис. 4.2. 4 - разрядный СРЛОС.

Соответствующая  матрица гибридной СКА с учетом того, что состояние крайней левой клетки зависит от всех клеток, представляется в виде:

(4.15)

Так как матрица  является невырожденной, то очевидно, что СРЛОС генерирует периодические последовательности.

Утверждение 4.8. Характеристический многочлен матрицы  СКА эквивалентен характеристическому многочлену  СРЛОС, генерирующему эквивалентную периодическую последовательность.

Доказательство: Пусть характеристический многочлен для  - разрядного СРЛОС имеет вид:

(4.16)

В соответствии с классической теорией матриц [102] характеристический многочлен Т матрицы СКА определяется путем присоединения к ней диагональной  матрицы, где  - характеристические числа оператора Т. Из  матрицы следует:

(4.17)

и характеристический многочлен матрицы Т равен:

(4.18)

Так как уравнения (4.17) и (4.18) совпадают с заменой  на , то утверждение справедливо.

Таким образом, СРЛОС является одним из вариантов настройки гибридной аддитивной СКА и все свойства СРЛОС, как генератора последовательности максимальной длины, рассмотренные в разделе 2, изоморфны свойствам гибридной аддитивной СКА при соответствующих правилах ее настройки.

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

Говорят, что  - разрядная СКА генерирует последовательности максимальной длины, если все возможные  ненулевые  - разрядные наборы содержатся в одном цикле. Для СРЛОС справедливо простое свойство, которое позволяет достичь того, что единый цикл содержит все 2n - 1 возможные ненулевые наборы [119].

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

Для СКА, которые генерируют последовательности максимальной длины, справедливы нижеследующие утверждения, доказательсва которых приведены в [95].

Утверждение 4.9. СКА с  клетками генерирует последовательность максимальной длины, если выполняется условие:


где наименьшее значение  равно .

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

В [95] приведены утверждения, на которых определен изоморфизм между СРЛОС и СКА, которые генерируют последовательности максимальной длины.

Утверждение 4.11. Сеть клеточных автоматов и СРЛОС, которые генерируют последовательности максимальной длины, изоморфны между собой.

Доказательство приведено в приложении А.6.

Утверждение 4.12. Сеть клеточных автоматов и СРЛОС, которые генерируют последовательности максимальной длины, имеют идентичные характеристические многочлены.

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

(1)

Правило 150:


(2)

Правило 90:



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

Длина СКА

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

4

4

5

12

6

12

7

36

8

32

9

96

10

120

11

352

12

288


В качестве примера в приложении Б приведены все 12 СКА степени 5, генерирующие последовательности максимальной длины при нулевых граничных условиях.

Для каждого примитивного многочлена степени  существует единственный СРЛОС, который генерирует последовательности максимальной длины для всех  клеток. В [70] приведены все примитивные многочлены для . Существует 2 примитивных многочлена степени 4; 6 многочленов степеней 5 и 6; 18 многочленов степени 7; 16 многочленов степени 8; 48 многочленов степени 9; 60 многочленов степени 10; 176 многочленов степени 11; 144 многочлена степени 12 и т.д.

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

Для приведенных в приложении Б СКА степени 5 можно отметить, что пары СКА (1, 7), (2, 9), (3, 5), (4, 11), (6, 12) и (8, 10) являются зеркальными отображениями друг друга. Сеть клеточных автоматов и ее зеркальное отображение имеют одинаковую структуру. На рис. 4.3 показана пара СКА (2, 9). Они имеют одинаковый характеристический многочлен, который является примитивным.

Рис. 4.3. Зеркальные отображения СКА

а) <150 150 90 90 90> с нулевыми граничными условиями

б) <90 90 90 150 150> с нулевыми граничными условиями

Поскольку  также равно числу различных примитивных многочленов степени , то можно сделать вывод, что для каждого примитивного многочлена степени  существует единственная СКА с нулевыми граничными условиями, использующая только правила 90 и 150.

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

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

Пример 4.5: Пусть выбран примитивный многочлен 4 степени  и СКА на его основе с нулевыми граничными условиями и правилами настройки . Матричная модель СКА представляется в виде:


Последовательность, генерируемая такой СКА, представлена на рис. 4.4.

0

0

0

1

0

0

1

1

0

1

1

0

1

0

1

1

0

0

1

0

0

1

0

1

1

1

0

1

1

0

0

1

0

1

1

1

1

0

0

0

0

1

0

0

1

1

1

0

1

1

1

1

1

1

0

0

1

0

1

0

Рис. 4.4. Последовательность векторов, генерируемых СКА с  характеристическим многочленом .

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

       d4,2 =

{ 011110001001101, 101111000100110, 010111100010011, 101011110001001, 110101111000100, 011010111100010, 001101011110001, 100110101111000, 010011010111100, 001001101011110, 000100110101111, 100010011010111, 110001001101011, 111000100110101, 111100010011010}

Рис. 4.5. Периодическая двоичная последовательность с периодом .

Последовательности в  обладают следующими свойствами [100]:

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

Равное число нулей и единиц: Поскольку  - разрядная СКА генерирует последовательности максимальной длины, то все возможные  - разрядные наборы, за исключением нулевого, присутствуют в одном цикле в диаграмме переходов состояний. Таким образом, сумма по mod 2 значений разрядов в любой клетке на всех  наборах должна быть равна 0, а любая последовательность из  содержит  единиц и  нулей.

Аддитивное свойство: Сумма по mod 2любых двух последовательностей из  равна последовательности, которая также принадлежит .

Доказательство: Пусть  - характеристическая матрица  - разрядной СКА, которая генерирует последовательности максимальной длины;  - ка  - начальное состояние СКА и , где .

Определим две операции следующим образом:

(а)  - обозначает исключение  - го разряда из общего  - разрядного набора.

(б) - - обозначает операцию конкатенации потока двоичных разрядов.

Тогда две различные клетки в могут быть представлены следующим образом:

(4.19)

И

(4.20)

где  - целое число и .

Следует отметить, что

(4.21)

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

(4.22)

Следует отметить, что  появляется один раз в  - разрядном наборе, который принадлежит одному циклу состояний. Таким образом, результат суммирования (4.22) является последовательностью, которая принадлежит .

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

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

Алгоритм 4.1.

Построить характеристическую матрицу в виде (4.4) для заданной размерности  СКА.

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

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

(4.23)

где


 - порядок матрицы

Составить систему уравнений по формуле п.3.

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

В качестве примера возьмем СКА длиной 4 с нулевыми граничными условиями [118,120]. Характеристическая матрица такой СКА имеет следующий вид:

(4.24)

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

(4.25)

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

Получаем следующую систему уравнений:

(4.26)

Решая систему уравнений, получаем:

(4.27)

Характеристическая матрица СКА имеет вид:

(4.28)

Следовательно, СКА реализуется в соответствии с правилами .

Используя этот алгоритм, были получены правила эволюции СКА длиной 4 - 20, которые генерируют последовательности максимальной длины. Результаты вычислений представлены в табл. 4.3.

Таблица 4.3.

Правила эволюции СКА для генерации последовательностей максимальной длины.

Длина n

Характеристический многочлен

Правила настройки СКА

4

150,90,150,90


5

150,150,150,150,90


6

90,150,150,90,90,90


7

90,150,150,150,90,150,90


8

90,150,150,90,90,90,90,90


9

90,150,90,90,150,150,150,90,90


10

150,150,150,150,90,90,90,90,150,150


11

90,150,90,150,150,90,90,90,90,150,90


12

90,150,150,90,150,150,90,90,90,150,150,90


13

150,90,90,90,150,90,90,90,90,150,150,90,90


14

90,90,150,90,150,150,150,90,90,150,90,150,90,90


15

90,150,150,90,150,90,150,150,150,150,90,150,90,90,90


16

150,90,150,90,90,90,90,90,90,90,150,150,150,90,90,150


17

150,90,90,150,150,90,90,150,150,90,90,90,150,150,90,90, 150


18

150,150,90,90,150,90,90,90,90,90,90,90,150,90,90,90,150, 150


19

150,90,150,90,90,150,90,150,90,90,150,90,90,150,90,90, 150,90,150


20

90,150,150,90,150,90,150,150,150,90,90,90,90,150,90,150, 90,150,150,90



По вышеуказанному алгоритму составлена программа, которая находит правила эволюции СКА для генерации М - последовательностей. Листинг программы приведен в приложении В.3.

.8 Выводы

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

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

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

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

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

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

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

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

Для повышения помехозащищенности в военных системах связи, системах связи с большим числом абонентов, спутниковых навигационных системах получили широкое распространение последовательности де Брейна, которые генерируются сдвиговыми регистрами с нелинейной обратной связью [104]. При этом одним из основных требований, предъявляемых к последовательностям, является степень ее непредсказуемости по известным символам. Степень непредсказуемости последовательностей определяется разрядностью эквивалентного СРЛОС. Например, для М - последовательностей достаточно иметь  символов ( - длина СРЛОС), идущих подряд, для раскрытия ее структуры [105]. Оценим сложность последовательностей де Брейна, полученных при помощи генераторов на СРНОС, метод синтеза которых предложен в разделе 3.5.

Пусть двоичная последовательность  генерируется  - разрядным СРЛОС. Тогда  полностью определяется начальной установкой СР  и линейной рекурсией в виде

(5.1)

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

Выражение (5.1) можно представить линейным разностным уравнением

(5.2)

где Е - оператор сдвига, т.е. .

Многочлен  является многочленом обратной связи СР.

Если последовательность  имеет период , то  и, таким образом, . Следовательно,  делится на  и сложность последовательности , которую будем обозначать , в этом случае равна

(5.3)

В [106] определены верхняя и нижняя граница сложности последовательностей, генерируемых  - разрядным СР, которые определяются неравенством

(5.4)

Пусть  - двоичная последовательность с периодом  - векторное пространство поля . Справедливо следующее утверждение [107].

Теорема 5.1. Пусть , а  - левая и правая половины двоичного вектора . Вычислим . Тогда выполняется:

а) если , то ;

б) если , то .

На основании теоремы 5.1 разработан алгоритм вычисления сложности последовательностей, генерируемых СРНОС, граф-схема которого представлена на рис. 5.1 [121]. Если длина последовательности , то  вычисляется за  шагов. В качестве примера вычислим сложность последовательности, генерируемой СРНОС с функцией обратной связи (3.21): :

(s) = 00000110010110111110101000100111

В соответствии с алгоритмом, представленным на рис. 5.1, выполняются следующие шаги:

Инициализация:





l

c(s)

Шаг 1.

R(a) = 1110101000100111




L(a) = 0000011001011011




 b = 1110110001111100

16




Шаг 2.

R(a) = 01111100




L(a) = 11101100




 b = 10010000

8

24




Шаг 3.

R(a) = 0000




L(a) = 1001




 b = 1001

4

28




Шаг 4.

R(a) = 01




L(a) = 10




 b = 11

2

30




Шаг 5.

R(a) = 1




L(a) = 1




 b = 0

0

30





т.к.  и , то 131




В результате .

По вышеуказанному алгоритму составлена программа расчета сложности последовательностей де Брейна. Листинг программы приведен в приложении В.4. В приложении Г приведены значения сложности последовательностей, генерируемых при помощи примитивных многочленов степени 16.

Проведенный анализ показал, что из 24 генераторов разрядности n = 16 четырнадцать генераторов вырабатывают последовательности максимальной сложности c(s) = 65535, четыре генератора вырабатывают последовательности со сложностью c(s) = 65534, пять генераторов вырабатывают последовательности со сложностью c(s) = 65533 и один генератор вырабатывает последовательность со сложностью c(s) = 65532.

Рис. 5.1. Блок - схема алгоритма определения сложности последовательности.

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

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

Оценим эффективность функционирования модуля самопроверяемого МСА, схема которого представлена в разделе 2.5.

Определение 5.1. Достоверность функционирования ДУ - это свойство, которое определяется способностью средств контроля фиксировать правильность или ошибочность его функционирования [108].

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

Достоверность работы ДУ характеризуется достоверностью функционирования и достоверностью правильного функционирования.

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

Определение 5.3. Пропуск ошибки - это ситуация, при которой устройство работает неправильно, но сигнал ошибки отсутствует.

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

Достоверность функционирования [122]:


где  - вероятность правильной работы устройства

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

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

где  - вероятность, что устройство работает неправильно, но сигнал ошибки отсутствует (вероятность пропуска ошибки средствами контроля)

Оценку достоверности работы самопроверяемого МСА проводем в соответствии с общей структурной схемой аппаратного контроля (рис. 5.2), где

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

 - вероятность безотказной работы схемы контроля;

 - вероятность безотказной работы схемы сравнения (решающего органа).

          Рис. 5.2. Структурная схема аппаратного контроля.

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

где  - вероятность обнаружения ошибок выбранным методом контроля.

При этом можно записать:


Вероятность безотказной работы в течение наработки t = 10000 ч [109]:


вероятность обнаружения ошибки методом контроля на четность [71]:


где  - кратность ошибки.

Теперь определим достоверность работы самопроверяемого МСА:


Надежность работы всего устройства снижается в результате ввода дополнительной аппаратурной избыточности, но при этом повышается вероятность обнаружения ошибки. Выполненные расчеты показывают, что ошибки нечетной кратности всегда обнаруживаются самопроверяемым МСА. Ошибки четной кратности обнаруживаются с вероятностью 0,9772. Следовательно, введение схемы встроенного контроля повышает достоверность работы многоканального сигнатурного анализатора и вероятность обнаружения ошибки.

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

Семейство ПЛИС ALTERA MAX 7000 представляет собой перепрограммируемые (EEPROM) устройства, основанные на архитектуре массивов матриц второго поколения. Характеристики семейства MAX 7000 приведены в табл. 5.1 [110].

ПЛИС MAX 7000 содержат от 32 до 256 макроячеек, которые объединены в группы по 16 макроячеек, называемые блоками сетевой логики. Каждая макроячейка состоит из матрицы с программируемыми элементами И и фиксированными элементами ИЛИ и реконфигурируемого регистра с независимо программируемыми функциями синхронизации, разрешения синхронизации, сброса и установки. Для реализации сложных логических функций каждая макроячейка может быть дополнена как общими расширителями элементарных конъюнкций (ЭК), так и высокоскоростными параллельными расширителями ЭК для обеспечения до 32 ЭК на макроячейку.

Архитектура MAX7000 (рис. 5.3), включает следующие элементы:

блоки сетевой логики (БСЛ);

расширители элементарных конъюнкций (ЭК);

матрица программируемых внутренних соединений;

блок управления вводом/выводом.

Таблица 5.1.

Краткие характеристики ПЛИС семейства MAX 7000.

Характеристика

EPM 7032

EPM 7064

EPM 7096

EPM 7128

EPM 7160

EPM 7192

EPM 7256

Число эквивалентных вентилей

600

1250

1800

2500

3200

3750

5000

Макроячейки

32

64

96

128

160

192

256

Блоки сетевой логики

2

4

6

8

10

12

16

Максимальное число выводов

36

68

76

100

104

124

164

Время задержки прохождения сигнала, нс

6

5

7,5

6

6

7,5

7,5

Тактовая частота, МГц

151,5

178,6

125

151,5

151,5

125

125


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

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

Макроячейки в устройствах МАХ7000 могут быть сконфигурированы для выполнения последовательностных либо комбинационных схем. Макроячейки состоят из 3 функциональных блоков: матрицы логических операций, матрицы выбора ЭК и программируемого регистра (рис. 5.4).

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


ПЛИС MAX 7000S программируются через стандартный JTAG интерфейс [3]. Архитектура MAX 7000S самостоятельно вырабатывает высокое напряжение, необходимое для программирования EEPROM - ячеек, что позволяет проводить программирование системы при помощи единого напряжения 5 В. Во время программирования входы/выходы ПЛИС находятся в состоянии высокого импеданса во избежание конфликтов на плате.

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

VHDL - модели модулей сигнатурного мониторинга реализованы на ПЛИС ALTERA MAX 7000S:

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

Генератор последовательности де Брейна на основе многочлена .

Генератор последовательности де Брейна на основе многочлена .

Генератор М - последовательности на СКА разрядности 12 со следующими правилами: 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

Генератор М - последовательности на СКА разрядности 16 со следующими правилами: 150, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

Исходными данными для программы моделирования MAX + PLUS II являются описания схем, выполненные на языке VHDL, представленные в приложении В.5. Схема самопроверяемого многоканального сигнатурного анализатора (1) реализована на ПЛИС EPM 7064 SLC 84 - 5. Схемы генераторов последовательностей де Брейна (2) и (3), генераторов М - последовательностей на СКА (4) и (5) реализованы на ПЛИС EPM 7032 SLC 44 - 6. Аппаратные затраты приведены в табл. 5.2. Временные задержки распространения сигнала от тактового входа на выход D - триггера приведены в табл. 5.3 и 5.4.

Таблица 5.2

Аппаратные затраты на реализацию схем пп. 1 - 5.

Устрой-ство

ПЛИС

Число входов

Число выходов

Число логич. клеток

Общие расширители

% использования ПЛИС

1

EPM7064SLC84-5

18

18

42

17

65 %

2

EPM7032SLC44-6

2

16

16

6

51 %

3

EPM7032SLC44-6

2

16

16

6

51 %

4

EPM7032SLC44-6

2

12

12

0

37 %

5

EPM7032SLC44-6

2

16

16

0

50 %


Таблица 5.3

Временные задержки самопроверяемого сигнатурного анализатора.

Выводы

А

В

D1

D2

D3

D4 - 16

Clk

21,8 нс

3,2 нс

3,2 нс

3,2 нс

3,2 нс

3,2 нс


Таблица 5.4

Временные задержки генераторов пп. 2 - 5.

Устройство

Выводы

D1

D2

D3

D4

D5

D6 - 16

2

Clk

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

3

Clk

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4

Clk

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

5

Clk

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс

4,0 нс


В результате проведенных экспериментов было установлено, что реализованная на ПЛИС EPM 7064 SLC 84 - 5 схема самопроверяемого многоканального сигнатурного анализатора (1) может работать на частоте 45 МГЦ, реализованные на ПЛИС EPM 7032 SLC 44 - 6 схемы генераторов последовательностей де Брейна (2) и (3) и схемы генераторов М - последовательностей (4) и (5) могут работать на частоте 150 МГЦ. При необходимости эту частоту можно увеличить путем выбора ПЛИС с меньшими временными задержками.

5.5 Выводы

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

Проведен анализ достоверности функционирования самопроверяемого МСА. Показано, что надежность работы всего устройства снижается на 1% из-за ввода дополнительной аппаратурной избыточности, однако при этом повышается вероятность обнаружения ошибки. Ошибки нечетной кратности всегда обнаруживаются самопроверяемым МСА. Ошибки четной кратности обнаруживаются с вероятностью 0,9772.

Получена реализация предложенных в разделах 2 - 4 методов синтеза самопроверяемого многоканального сигнатурного анализатора и генераторов тестовых последовательностей. Анализ временных характеристик синтезируемых устройств показал, что схема самопроверки МСА увеличила задержку распространения сигнала на этапе вход - контрольный выход (21,8 нс). Анализ аппаратной сложности показал, что схемы на основе КА реализованы без использования общих расширителей, в то время как для реализации генераторов последовательности де Брейна потребовалось использовать 6 расширителей.

ЗАКЛЮЧЕНИЕ

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

Основные научные и практические результаты:

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

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

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

Усовершенствована матричная модель сети клеточных автоматов (СКА), на основе которой определен изоморфизм генераторов на СКА и СРЛОС. Разработан метод синтеза генераторов последовательностей максимальной длины на СКА и определены статистические свойства генерируемых последовательностей.

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

Разработанные программно - аппаратные средства синтеза модулей сигнатурного мониторинга использовались при разработке диагностического обеспечения исполнительного автомата управления приводом ШЭМ - М системы управления и защиты реакторной установки, которые выполнялись на ОАО ХАРТРОН, в составе встроенных средств диагностирования системы автоматизированного управления выращиванием крупногабаритных монокристаллов в опытном производстве Института сцинтиляционных материалов НАН Украины (г. Харьков), в учебном процессе УкрГАЖТ и НТУ «ХПИ».

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Основы технической диагностики / Под ред. П.П. Пархоменко. - М.: Энергия. - 1976. - 460 с.

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

JTAG Boundary Scan Architecture Standard Proposal, Version 2.0. Technical Sub - Committee of the Joint Test Action Group. - March 30, 1988.

Беннетс Р.Дж. Проектирование тестопригодных логических схем: Пер. с англ. - М.: Радио и связь, 1990. - 176 с.

Aitken R.C. Nanometer technology effects on fault models for IC testing // Computer. - 1999. - № 11. - P. 46 - 51.K.T., Krstic A. Current Directories in Automatic Test-Pattern Generation // Computer. - 1999. - № 11. - P. 58 - 64.T.G. at al. Testing the 500-MHz IBM S/390 Microprocessor //IEEE Design & Test of Computers. - 1998. - № 3. - P. 83 - 89.

Новеллино Д. Стандарт по периферийному сканированию - в центре внимания международной конференции по методам и средствам тестирования // Электроника. - 1990. - № 16. - С. 7 - 12.

Закревский Л.А., Калоша Е.П., Хаткевич Н. Н., Ярмолик В. Н. Метод граничного сканирования и его использование для тестирования цифровых устройств // Автоматика и телемеханика. - 1994. - № 1. - С. 3 - 31.

Быков Ю.В., Ярмолик В. Н. Синтез преобразователей псевдослучайных чисел для реализации самотестирования цифровых устройств, удовлетворяющих требованиям стандарта IEEE // Автоматика и телемеханика. - 1996. - № 4. - С. 148 - 154.

Хаханов В.И., Сысенко И.Ю., Абу Занух Халиль И.М. Проектирование тестов для структурно - функциональных моделей цифровых схем // Радиоэлектроника и информатика. - 1999. - № 3. - С. 51 - 59.

Williams T.W., Parker K.P. Design for testability. A survey // IEEE Trans. On Computers. - 1982. - Vol. C-31, №1. - P. 2 - 15.E.J. A survey of design for testability scan techniques // VLSI Design. - 1984. - №12. - P. 38 - 61.M. Self-Exercising checkers for unified built-in self-test // IEEE Trans. On Computer-Aided Design. - 1989. - Vol. 8, № 3. - P. 203 - 218.S.K., Pradhan D.K. Can concurrent checkers help BIST? // Proc. IEEE Test Conference. - 1992. - P. 140 - 150.S.K., Pradhan D.K. Utilization of on-line (concurrent) checkers during built-in self-test and vice versa // IEEE Trans. On Computers. - 1996. - Vol. C-46, № 1. - P. 63 - 73.Z. et al. Exhaustive generation of bit patterns with applications to VLSI self - testing // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 2. - P. 190 - 194.E.J. Verification testing - a pseudoexhaustive test technique// IEEE Trans. On Computers. - 1984. - Vol. C-33. - № 6. - P. 495 - 500.E.J., Bozorqui-Nesbat S. Design for autonomous test // IEEE Trans. On Computers. - 1981. - Vol. C-30, № 11. - P. 866 - 875.D.T., Woo L.S. Exhaustive test pattern generation with constant weight vectors // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 9. - P. 1145 - 1150.D.K. Sequential network design using extra inputs for fault detection // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 3. - P. 319 - 323.

Бондаренко М.Ф., Кривуля Г.Ф., Рябцев В.Г., Фрадков С.А., Хаханов В.И. Проектирование и диагностика компьютерных систем и сетей. - К.: НМЦ ВО. - 2000. - 306 с.

Savir J. Syndrome - testable design of combinatorial circuits // IEEE Trans. On Computers. - 1980. - Vol. C-29, № 6. - P. 442 - 451.Z. at al. VLSI self-testing based on syndrome technique // Proc. IEEE Test Conference. - 1982. - P. 102 - 109.D.M., Muzio J.C. Spectral fault signatures for internally unate combinatorial networks // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 11. - P. 1058 -1062.A.K. Testing for verifying Walsh coefficients // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 2. - P. 198 - 201.J.P. Transition count testing of combinatorial circuits // IEEE Trans. On Computers. - 1976. - Vol. C-25, № 6. - P. 613 - 620.R. Signature of multi-output circuits // Proc. 14-th Annu. Int. Symp. Fault-Tolerant Computing. - 1984. - P. 366 - 371.

Уильямс Т.У., Паркер К.П. Проектирование контролепригодных устройствю - ТИИЭР, 1983. - Т. 71, № 1, с. 122 - 139.

Халчев В.Ф. Преобразование структурного автомата с памятью к пригодному для контроля виду // Автоматика и телемеханика. - 1975. - № 9. - с. 189 - 197.

Williams T.M., Parker K.P. Testing logic networks and designing for testability // Computer. - 1979. - № 10. - P. 42 - 53.

Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. - М.: Радио и связь, 1989. - 208 с.

Fujiwara E., Muto N., Matsuoka K. A self-testing group parity prediction checker and its use for built-in testing // IEEE Trans. On computers. - 1984. - Vol. C-33, №6. - P. 578 - 583.E.S., Goessel M. Design of self-testing and on-line fault detection combinatorial circuits with weakly inderendent outputs // Electronic Testing: Theory and Applications. - 1993. - № 4. - P. 267 - 281.

Согомонян Е.С. Достоверность самотестирования с использованием средств функционального диагностирования // Автоматика и телемеханика. - 1988. - №10. - с. 154 - 160.

Литиков И.П., Согомонян Е.С. Тестово-функциональное диагностирование цифровых устройств и систем // Автоматика и телемеханика. - 1985. - № 3. - с. 111 - 121.

Sedmak R.M. Design for self-verification. An approach for dealing with testability problems in VLSI-based design // Proc. IEEE Test Conference. - 1979. - P. 112 - 120.K. at al. On using signature registers as pseudo-random pattern generators in built-in self-testing // IEEE Trans. On Computer-Aided Design. - 1988. - Vol. 7, № 8. - P. 919 - 928.

Гессель М., Согомонян Е.С. Построение кодоразделительных самопаритетных комбинационных схем для самотестирования и функционального диагностирования // Автоматика и телемеханика. - 1996. - № 11. - с. 155 - 165.

Сперанский Д.В. Об одном методе синтеза схем встроенного контроля для комбинационных устройств // Автоматика и телемеханикаю - 1996. - № 4. - с. 155 - 161.

Friedman A.D. A functional approach to efficient fault detection in iterative logic arrays // IEEE Trans. On Computers. - 1994. - Vol. 43, № 12. - P. 1365 - 1375.M. Techniques for concurrent checking of VLSI processor operation // IEEE Test Conference. - 1982. - P. 461 - 468.

Устройство для контроля выполнения программ (его варианты): А.с. 1315981 СССР, МКИ G06 F 11/26/ В.В. Антосик, Л.В. Дербунович, А.Н. Мызь (СССР). - № 3888708/24; Заявл. 22.04.85; Опубл. 07.06.87, Бюл. № 21. - 58 с.

Романкевич А.М., Валуйский В.Н., Остафин В.А. Стркутурно - временная избыточность в управляющих системах. - К.: Вища школа. - 1979. - 160 с.

Скобцов Ю.А., Иванов Д.Е. Параллельное моделирование функциональных неисправностей // Техническая диагностика и неразрушающий контроль. - 1998. - № 3. - С. 43 - 47.

Миков И.Н., Дербунович Л.В., Нешвеев В.В., Мечникова Е.А. Программируемые контроллеры повышенной надежности для управления автоматическими линиями. Обзор. - М.: НИИмаш, 1984. - 52 с.

Беличенко Т.П., Белов Г.И., Дербунович Л.В. Нахождение кратчайшей различающей последовательности для конечного автомата // Гибридные вычислительные машины и комплексы. - К.: Наукова думка, 1980. - Вып. 3. - с. 36 - 39.

Белов Г.И., Дербунович Л.В. Синтез контролепригодных дискретных устройств с элементами памяти // Техническая диагностика, эксплуатация управляющих и вычислительных машин. - К.: Наукова думка, 1980. - с. 76 - 85.

Горяшко А.П. Синтез и проектирование легко тестируемых цифровых элементов и устройств: Дис. … докт. техн. наук: 05.13.05 - М., 1986. - 266 с.

Дербунович Л.В., Белов Г.И. Проверочный эксперимент для класса инициальных последовательных автоматов // Локальные автоматизированные системы автоматики. - К.: Наукова думка, 1979. - с. 93 - 102.

Каширова Л.Ф. Построение контролируемых автоматов. ч. 1, 2 // Автоматика и телемеханика. - 1983. - № 11. - с. 141 - 146. - № 12. - с. 115 - 121.

Сперанский Д.В. Методы преобразования структур дискретных систем с целью повышения их контролепригодности и оптимизации процессов диагностирования: Дисс. … докт. техн. наук: 05.13.05. - К., 1983. - 334 с.

Fujiwara H., Kinoshita K. Design of diagnosable sequential machines utilising extra outputs // IEEE Trans. On Computers. - 1974. - Vol. C-23, № 2. - P. 138 - 145.Z., Lavalee P. Design of sequential machines with fault detection capabalities // IEEE Trans. Electr. Comput. - 1967. - Vol. EC-16, № 8. - P. 473 - 484.H. et al. Easily testable sequential machines with extra outputs // IEEE Trans. On Computers. - 1975. - Vol. C-24, № 8. - P. 821 - 826.H., Kinoshita K. Checking experiments for stable memory faults in sequential machines // Journal of Design automation & Fault-Tolerant Computing. - 1978. - Vol. 2, № 1. - P. 3 - 14.S., Kinoshita K., Ozaki H. Sequential machines capable of fault diagnosis // IEEE Trans. On Computers. - 1970. - Vol. C-19, № 11. - P. 1079 - 1085.S.M., Abraham J.A. Test generation for microprocessors // IEEE Trans. On Computers. - 1980. - Vol. C-29, № 6. - P. 429 - 441.

Тоценко В.Г. Технический диагноз дискретных устройств с элементами памяти: Дис. … докт. техн. наук: 05.13.05. - К., 1975. - 298 с.

Bhattacharyya A. On novel approach of fault-detection in an easily testable sequential machine with extra inputs and extra outputs // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 3. - P. 323 - 325.S.R., Chen Z., Dai Y.L. Easily testable sequential machines with extra inputs and extra outputs // Electronic Letters. - 1980. - Vol. 16, № 2. - P. 119 - 121.F.C. Fault detection experiments for sequential circuits // Proc. 5-th Symp. On Switching Circuits Theory and Logical Design. - 1964. - P. 95 - 110.P.H., McAnney W.H., Savir J. Built-in Test for VLSI: Pseudorandom techniques. - New York: John Wiley & Sons, 1987. - 274 p.

Генератор псевдослучайных чисел: А.с. 1377167 CCCР, МКИ G06 F 11/26/ Л.В. Дербунович, В.Ф. Бохан, И.Г. Либерг (CCCР). - №4022981/21; Заявл.07.02.86; Опубл. 30.09.87, Бюл. № 39. - 112 с.H. A Survey of full length nonlinear shift register cycle algorithms // SIAM Review. - 1982. - Vol. 24, № 2. - P. 195 - 221.R., Gupta S.K., Breuer M.A.. Novel test pattern generators for pseudorandom testing // IEEE Trans. On Computers. - 2000. - Vol. C-49, № 11.- P. 1228 - 1240.D.T., Chen C.L. Logic test pattern generation using linear codes // IEEE Trans. On Computers. - 1984. - Vol. C-33, № 9. - P. 845 - 850. Z., Savir J., Markovsky G., Smith M.G. The weighted syndrome sums approach to VLSI testing // IEEE Trans. On Computers. - 1981. - Vol. C-30, № 12. - P. 996 - 1000.L.T., McCluskey E.J. Condensed linear feedback shift register testing - a pseudoexhaustive test technique // IEEE Trans. On Computers. - 1986. - Vol. C-35, № 4. - P. 367 - 370.

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976. - 600 с.

Гессель М., Согомонян Е.С. Функционально-тестовое диагнострование на основе сохраняющего четность сигнатурного анализатора // Автоматика и телемеханика. - 1998. - № 5. - С. 162 - 171.

Ralston A. De Bruijn sequences - a model example of interaction of discrete mathematics and computer science // Am. Math. Monthly. - 1982. - Vol.55,№3. - P. 131 - 143.A. On homomorphism of the de Bruijn graph and its application to the design of feedback shift registers // IEEE TC. - 1970. - Vol.19, №12. - P. 1204 - 1209.G.E. NESL: a nested data-parallel language // Tehnical report CMU - CS - 94, 1994.Ubar. Test synthesis with alternative graphs // IEEE Design & Test of Computers. - 1996. - 1. - P. 48 - 57.W.S. Shift register sequences. - Laguna Hills, CA: Aegean Park Press, 1982.- 341 p.

Пападимитриу Х. Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир,1995. - 512 с.

Annexstein F.S. Generating de Bruijn sequences: An efficient Implementation // IEEE Trans. On. Computers. - 1997. - Vol. C-46, №2. - P.198 - 200.

Басакер Р., Саати Т. Конечные графы и сети. - М.: Наука, 1974. - 482 с.

Fredricksen H., Maiorana J. Necklaces of beads in k colors and k-ary de Bruijn sequences // Discrete Mathematics. - 1978. - № 23. - P. 207 - 210.K.K. Cascaded switching networks of two-input flexible cells // IRE Trans. Electr. Computers. - 1964. - Vol. EC-13, № 4. - P. 136 - 143.

Варшавский В.И., Мараховский В.Б. и др. Однородные структуры. (Анализ. Синтез. Поведение.). - М.: Энергия, 1973. - 248 с.

Mukhopadhyay A. Unate cellular logic // IEEE Trans. On Computers. - 1969. - Vol. C-18, № 2. - P. 114 - 121.C.D. The characterization and properties of cascade realizable switching functions // IEEE Trans. On Computers. - 1969. - Vol. C-18, № 7. - P. 624 - 633.

Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.

L. Wang, M. Marhoefen, E.J. McCluskey. A self - test and self - diagnosis architecture for boards using boundary scan // Technical report, Center for Reliable Computing, 1989. - P. 20 - 27.E.R., Conway J.H., Guy R.K. Winning ways for your mathematical plays. - New York: Academic Press, 1982. - Vol. 2. - Chap. 25.. Pries, A. Thanailakis, and H.C. Card. Group properties of cellular automata and VLSI applications // IEEE Trans. Comput. - 1986. - vol. C-35. - p. 1013 - 1024. .D. Hortensius, R.D. McLeod, W. Pries, D.M. Miller and H.C. Card. Cellular automata - based pseudorandom number generators for built - in self - test. // IEEE Trans. CAD. - 1989. - № 8 - p. 842 - 859..R. Gloster, F. Borglez. Boundary scan with cellular - based built - in self - test // Proc. Intern. Test Conference - 1988. - p. 138 - 145..D. Gortensius, H.C. Card, R.D. McLeod, W. Pries. Importance sampling for using computers using one - dimensional cellular automata. // IEEE Trans. Comput. - 1989. - Vol. C-38, № 6. - p. 769 - 774..D. Gortensius, H.C. Card, R.D. McLeod. Parallel random number generation for VLSI systems using cellular automata. // IEEE Trans. Comput. - 1989. - Vol. C-38, № 10. - p. 1466 - 1473.D.J., Kime C.R. Cellular automata for weighted random pattern generation // IEEE Trans. On Computers. - 1997. - Vol. C-46,№ 11. - P. 1219 - 1228.P.D., McLeod R.D., Card H.C. Cellular automata-based signature analysis for built-in self-test // IEEE Trans. On Computers. - 1990. - Vol. C-39, № 10. - P. 1273 - 1283..K. Das, M. Pandey, A. Gupta, and. P. Pal Chaudhuri. Built - in self - test structures around cellular automata and counters. // IEE Proc. Part (E). - 1990. - Vol. 137, № 7. - P. 268 - 276.

Мур Е.Ф. Умственные эксперименты с последовательными машинами. // Автоматы: Пер. с англ. - М.: Физматгиз, 1956, с. 179 - 213.

E.J. McCluskey. Built - in verification test // Proc. Intern. Test Conference. - 1982. - P. 183 - 190.S. Computation theory of cellular automata // Communications in Mathematical Physics. - 1984. - Vol. 93. - P. 15 - 57.S. Statistical mechanics of cellular automata // Reviews of Modern Physics. - 1983. - Vol. 55, № 3. - P. 601 - 644.A.K. at al. Efficient characterization of cellular automata // IEE Proc. Part (E). - 1990. - Vol. 137, № 1. - p. 81 - 87.. Martin, A.M. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. // Communications in Mathematical Physics. - 1984. - Vol. 93. - p. 219.

Гантмахер Ф.Р. Теория матриц. - М.: Изд-во технико - теоретич. литературы, 1954. - 492 с.

Воеводин В.В. Вычислительные основы линейной алгебры. - М.: Наука, 1977. - 304 с.

Клименко Н.Н., Кисель В.В. , Замарин А.И. Сигналы с расширением спектра в системах передачи информации // Зарубежная радиоэлектроника. - 1983. - № 11. - С. 45 - 59.

Спельмашенко Б.Г., Тараненко П.Г. Нелинейные псевдослучайные последовательности в широкополосных системах передачи информации // Зарубежная радиоэлектроника. - 1988. - № 9. - С. 3 - 16.

Chan A.H., Games R.A., Key E.L. On the complexity of de Bruijh sequences // Journal of Combin. Theory. - 1982. - Vol. 33, № 4. - P. 233 - 246.R.A., Chan A.H. A fast algorithm for determining the complexity of a binary sequences with period 2n // IEEE Trans. On Inform. Theory. - 1983. - Vol. 29, № 1. - P. 144 - 146.

Щербаков Н.С. Влияние аппаратного контроля на критерии надежности дискретных устройств // Теоретические и прикладные вопросы проектирования систем управления. - Киев: Наукова думка, 1980. - С.141 - 149.

ALTERA reliability report 4.0 // www.altera.com/literature/rr/rr.pdf

ALTERA MAX 7000S СPLD Overview // www.altera.com/products/devices/max7k/ <#"579414.files/image640.gif"> необходимо, чтобы . Это следует из того факта, что если , то  при условии .

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

А.2. Доказательство утверждения 4.4: Пусть мы имеем характеристическую матрицу  такую, что , т.е. СКА генерирует циклическую последовательность. Из утверждения 4.1

:


где  - целое число.

Пусть  - целое число такое, что . Чтобы доказать, что  также образует циклические последовательности, покажем, что существует такое , что:


Для :


Поскольку выполняется операция сумма mod 2 и , то можно сделать вывод, что такое  существует. Утверждение доказано.

А.3. Доказательство утверждения 4.5: Пусть R - строгое правило эволюции СКА (т.е. все клетки описываются одинаковым правилом). Пусть  соответствует гибридной СКА длины  с любой перестановкой  и  соседних клеток СКА. Любая перестановка  может быть представлена общей формулой:


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

Если существует такое , что , то, согласно Лемме 4.4, также существует такое , что:


Утверждение доказано.

А.4. Доказательство утверждения 4.6: Если для  существует циклическая последовательность длиной , то

при условии, что  - ненулевой вектор. Из теории матриц известно, что если , то существует по крайней мере один ненулевой вектор  такой, что


Отсюда


Утверждение доказано.

А.5. Доказательство утверждения 4.7: Проведем доказательство от противного: Пусть порядок цикла равен  и существует цикл длиной  и при этом  не является делителем .

Так как


То

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

А.6. Доказательство утверждения 4.11: Рассмотрим отображение  цикла, содержащего наборы, которые вырабатываются СРЛОС (цикл 1), в цикл, содержащий наборы, которые вырабатываются СКА (цикл 2):

Для набора a в цикле 1 и набора b в цикле 2 можно записать:


и для всех  в цикле 1,

где  и  - характеристические матрицы соответственно для СРЛОС и СКА. Более того, поскольку  и  генерируют циклические последовательности, то эти матрицы невырожденные.

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


ПРИЛОЖЕНИЕ Б

Сети КА степени 5, генерирующие последовательности максимальной длины при нулевых граничных условиях:

(1) (2)


(3) (4)


(5) (6)


(7) (8)


(9) (10)


(11) (12)



ПРИЛОЖЕНИЕ В

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

В.1. Определение линейной зависимости остатков для (n, m, k) схемы на МСРЛОС/СР.

Программа написана на языке программирования Delphi 7. По алгоритму (раздел 2.2) программа осуществляет определение линейной зависимости остатков для (n,m,k) схемы на основе МСРЛОС/СР. Программа также хранит все остатки полинома СР, полученные делением многочленов. Деление многочленов, считывание остатков в массив, сравнение массивов, сортировка входного массива осущетвлены отдельными функциями. С помощью данной программы осуществляется синтез ГПТ  схем для степеней полиномов .

unit fMain;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, Spin, ComCtrls,Math, Grids, cxControls, cxContainer,, cxTextEdit, cxMaskEdit, cxSpinEdit, cxCheckBox, Buttons,, ExtCtrls, cxDropDownEdit;

= class(TForm): TStatusBar;: TStringGrid;: TPanel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TSpeedButton;: TSpinEdit;: TButton;: TSpinEdit;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TcxCheckBox;: TEdit;: TcxTimeEdit;: TcxTimeEdit;: TLabel;: TLabel;: TSplitter;: TcxComboBox;Button1Click(Sender: TObject);SetSi;FormCreate(Sender: TObject);SpinEdit1Change(Sender: TObject);SpeedButton1Click(Sender: TObject);cxCBClick(Sender: TObject);

{ Private declarations }

{ Public declarations };=array[1..16] of TcxCheckBox ;=array [0..16] of integer;=array of array of integer;

DevPOL (var x0,x1:Tx) :Tx;ReadPOL:Tx;SortSheiker(var x0:Tx;r:integer):Tx;: TfrmMain;:Cx;:Tx;

{$R *.dfm}

DevPOL (var x0,x1:Tx) :Tx;,x3,x4:Tx;:integer;,z2:integer;[0]:=1;x0[1]>=x1[1] do begini:=1 to x2[0] do x2[i]:=x0[1]-x1[1];i:=1 to x1[0] do x3[i]:=x1[i]+x2[1];[0]:=x1[0];[0]:=0;:=1;:=1;(z1<=x3[0]) or (z2<=x0[0]) do begin(z1<=x3[0]) and (z2<=x0[0]) then beginx3[z1]=x0[z2] then begin(z1);(z2);elsex3[z1]>x0[z2] then begin(x4[0]);[x4[0]]:=x3[z1];(z1);else begin(x4[0]);[x4[0]]:=x0[z2];(z2);;else if (z1>x3[0]) then begin(x4[0]);[x4[0]]:=x0[z2];(z2);else begin(x4[0]);[x4[0]]:=x3[z1];(z1);;;i:=1 to x4[0] do x0[i]:=x4[i];[0]:=x4[0];;:=x0;;

ReadPOL:Tx;:string;,j,z,k:integer;:Tx;:=frmMain.cxComboBox1.Text;:=1;:=1;:=2;k:=1 to Length(s) do(s[k]='+') then(z);;[0]:=z-1;i<=Length(s) do

//перебор символов(s[i]='x') or (s[i]='X') thenLength(s)<>i then(s[i+1]='+') then[j]:=1;(j);;;(s[i]='+') thenLength(s)<>i then(s[i+1]='1') then[j]:=0;(j);(i);;;[j]:=StrToInt(s[i]);(j);Length(s)<>i then(s[i+1]<>'x') and (s[i+1]<>'X') and (s[i+1]<>'+') then(j);[j]:=StrToInt(s[i]+s[i+1]);(j);(i);;;;(i);;:=x0;;

TfrmMain.SetSi;:integer;[1]:=cxCB1;[2]:=cxCB2;[3]:=cxCB3;[4]:=cxCB4;[5]:=cxCB5;[6]:=cxCB6;[7]:=cxCB7;[8]:=cxCB8;[9]:=cxCB9;[10]:=cxCB10;[11]:=cxCB11;[12]:=cxCB12;[13]:=cxCB13;[14]:=cxCB14;[15]:=cxCB15;[16]:=cxCB16;

i:=1 to SpinEdit1.Value do[i].Enabled:=TRUE;;i:=SpinEdit1.Value+1 to 16 do[i].Enabled:=FALSE;;

//.MinValue:=SpinEdit1.Value+1;.MaxValue:=Trunc(Power(2,SpinEdit1.Value))-1;.Value:=SpinEdit1.Value+1;;

SortSheiker(var x0:Tx;r:integer):Tx;,S,i,j:integer;

// проход вверхi:=1 to r dox0[i-1]<x0[i] then:=x0[i];:=x0[i-1];[i]:=B;[i-1]:=S;;;

// проход внизj:=r downto 1 dox0[j-1]<x0[j] then:=x0[j];:=x0[j-1];[j]:=B;[j-1]:=S;;;:=r-1;;r < 1;:=x0;;

TfrmMain.Button1Click(Sender: TObject);,x0,x1:Tx;:Ex;,i,j,q,k,rez,rez2:integer;.Time:=Now;

// n - степень полинома:=SpinEdit1.Value;

// q -:=Trunc(Power(2,n))-2;

// Проверка на сочетания

rez2:=0;

for i:=1 to 17 do

beginsi[i-1]<>-1 then inc(rez2);;rez2<=1 then

('Введите сочетания полинома P(x) !!!! ', mtError,[mbOk], 0);;;

// Сортировка массива Si=1-16 с прим. function SortSheiker

si:=SortSheiker(Si,16);

// обнуление счётчика для массива-остатков

k:=0;

// Создание массива-остатков

SetLength(y0,q-n+1,n);

// Чтение полинома с прим. function ReadPOL

x1:=ReadPOL;

// Заполнение массива-остатков -1

for i:=0 to q-n doj:=0 to n-1 do0[i,j]:=-1;

// Заполнение массива-остатков остатками с прим. function DevPOL

for i:=n to q do[0]:=1;[1]:=i;:=DevPOL(x0,x1);j:=1 to x[0] do y0[k,j-1]:=x[j];(k);

end;

// Отображение результата в гриде-------------------------------------//

StringGrid1.ColWidths[0]:=60;.ColCount:=n+1;.RowCount:=q-n+2;i:=0 to q-n do.Cells[0,i+1]:='S'+IntToStr(i+n+1);j:=0 to n-1 doy0[i,j]<>-1 then.Cells[j+1,i+1]:=IntToStr(y0[i,j]);;

end;

//--------------------------------------------------------------------//

// Сравнение Si+...+Sn c массивом-остатков

rez:=0;i:=1 to n doy0[SpinEdit2.Value-n-1,i-1]=Si[i-1] then inc(rez);;

//

cxTimeEdit2.Time:=Now;

// Вывод результата линейности

if rez=n then(Edit2.text+' и '+'S'+IntToStr(SpinEdit2.Value)+' '+'ЛИНЕЙНО ЗАВИСИМЫ', mtInformation,[mbOk], 0)(Edit2.text+' и '+'S'+IntToStr(SpinEdit2.Value)+' '+'ЛИНЕЙНО НЕЗАВИСИМЫ', mtError,[mbOk], 0);

;

TfrmMain.FormCreate(Sender: TObject);:integer;;

// Заполнение S i=1-16 =-1i:=1 to 17 do si[i-1]:=-1;

;

TfrmMain.SpinEdit1Change(Sender: TObject);;;TfrmMain.SpeedButton1Click(Sender: TObject);:integer;i:=1 to SpinEdit1.Value do Lab[i].Checked:=FALSE;.Text:='';

// очистка массиваi:=1 to 17 do si[i-1]:=-1;;

TfrmMain.cxCBClick(Sender: TObject);:integer;.Text:=Edit2.Text+(Sender as TComponent).Properties.Caption+';';

// заполнение массива:=TcxCheckBox(Sender as TComponent).Properties.ValueChecked;[i+1]:=i;;

.

В.2. Генератор последовательности де Брейна на основе примитивного многочлена.

Программа написана на языке программирования Visual C++ 6.0. По алгоритму (раздел 3.5) программа осуществляет формирование многочлена обратной связи СРНОС для генерации последовательностей де Брейна. С помощью данной программы вычисляются функции обратной связи СРНОС разрядности .

#include <stdio.h>

#include <process.h>main( void )

{name[] = "res1.txt";*F;( !(F = fopen(name,"w")) ) printf("Error open F\n"), exit(0);width = 16;height = 65538l;*x;= new item[height];( !x ) printf("Out of memory\n"), exit(0);*/x[2][width];( int w=0; w<width; x[0][w++] = 0 );( w=0; w<width; fprintf(F,"%d ",x[0][w++]) ); fprintf(F,"\n");go = 1;( long h=1; (h<height) & go; h++ )

{[1][0] = (x[0][0] | (!x[0][1] & !x[0][3] & !x[0][4] & !x[0][5] & !x[0][6] & !x[0][7] & !x[0][8] & !x[0][9] & !x[0][10] & !x[0][12] & !x[0][13] & !x[0][14] & !(!x[0][0] & !x[0][2] & x[0][11])))

^ x[0][2] ^ x[0][11] ^ x[0][15];( w=1; w<width; x[1][w] = x[0][w-1], w++ );

( w=0; w<width; fprintf(F,"%d ",x[1][w++]) ); fprintf(F,"\n");

( w=0; w<width; x[0][w] = x[1][w], w++ );( go=0, w=0; (w<width) & !go; go |= x[1][w++] );

}*F2;name2[] = "res1_2.txt";(F);( !(F = fopen(name,"r")) ) printf("Error open F again\n"), exit(0);( !(F2 = fopen(name2,"w")) ) printf("Error open F2\n"), exit(0);( long i=0; i<h; i++ )

{( w=0; w<width; fscanf(F,"%d ",*x+w++) ); fscanf(F,"\n");( !(x[0][1] | x[0][3] | x[0][4] | x[0][5] |[0][6] | x[0][7] | x[0][8] | x[0][9] |[0][10] | x[0][12] | x[0][13] | x[0][14]) )(F2,"line # %5ld: %d %d %d %d\n",i+1,x[0][15],x[0][11],x[0][2],x[0][0]);

}

fclose(F); fclose(F2);

}

В.3. Нахождение правил эволюции СКА для генерации М - последовательности.

Программа написана на языке программирования Visual C++ 6.0. По алгоритму (раздел 4.7) программа осуществляет поиск правил эволюции СКА для генерации М - последовательностей степени .

// Determ.cpp: implementation of the CDeterm class.

/

//////////////////////////////////////////////////////////////////////

#include "stdafx.h"

#include "matrix.h"

#include "Determ.h"

#include <math.h>

#ifdef _DEBUG

#undef THIS_FILEchar THIS_FILE[]=__FILE__;

#define new DEBUG_NEW

#endif

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

::CDeterm( BOOL** coefStr, byte length )

{= coefStr;= length;

}

::~CDeterm()

{

}

* CDeterm::Binom( BOOL** coefs )

{*res = new BOOL[2];[0] = coefs[0][0] ^ coefs[1][1];[1] = (coefs[0][0] & coefs[1][1]) ^ (coefs[0][1] & coefs[1][0]);res;

}

* CDeterm::GetPolynom( BOOL** coefs, byte dimen, byte col /* = -1 */)

{** currCoefs;

__try {( col == 255 ) currCoefs = coefs;{= new BOOL*[dimen-1];( byte i = 1; i < dimen; i++ ) {[i-1] = new BOOL[dimen-1];( byte j = 0, pos = 0; j < dimen; j++ )( j != col ) currCoefs[i-1][pos++] = coefs[i][j];

}-;

}( dimen == 2 ) return Binom(currCoefs);* polynom = new BOOL[dimen];* curr = GetPolynom(currCoefs,dimen,0);[0] = curr[0] ^ currCoefs[0][0];( byte i = 1; i < dimen-1; i++ ) polynom[i] = curr[i] ^ (currCoefs[0][0] & curr[i-1]);[dimen-1] = currCoefs[0][0] & curr[dimen-2];curr;( i = 1; i < dimen; i++ ) ( currCoefs[0][i]) {= GetPolynom(currCoefs,dimen,i);( byte j = 1; j < dimen; polynom[j] ^= curr[j-1], j++ );curr;

}polynom;

} __finally {( col != 255 ) {( int i=0; i<dimen; delete currCoefs[i++] );currCoefs;

}

}

}

CDeterm::IsPolynom( CString polynom )

{length = polynom.GetLength();( dimen != length ) return false;* currPolynom = GetPolynom(coefs,dimen);( int i = 0; i < dimen; i++ ) if( currPolynom[i] != (polynom[i] == '1')) {currPolynom;false;

}currPolynom;true;

}

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

Программа написана на языке программирования Visual C++ 6.0. По алгоритму (раздел 5.1) программа осуществляет оценку сложности последовательностей де Брейна степени .

// test3Dlg.cpp : implementation file

//

#include "stdafx.h"

#include "test3.h"

#include "test3Dlg.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILEchar THIS_FILE[] = __FILE__;

#endif

/////////////////////////////////////////////////////////////////////////////

// CAboutDlg dialog used for App About

CAboutDlg : public CDialog

{:();

// Dialog Data

//{{AFX_DATA(CAboutDlg){ IDD = IDD_ABOUTBOX };

//}}AFX_DATA

// ClassWizard generated virtual function overrides

//{{AFX_VIRTUAL(CAboutDlg):void DoDataExchange(CDataExchange* pDX); // DDX/DDV support

//}}AFX_VIRTUAL

// Implementation:

//{{AFX_MSG(CAboutDlg)

//}}AFX_MSG_MESSAGE_MAP()

};

::CAboutDlg() : CDialog(CAboutDlg::IDD)

{

//{{AFX_DATA_INIT(CAboutDlg)

//}}AFX_DATA_INIT

}

CAboutDlg::DoDataExchange(CDataExchange* pDX)

{::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CAboutDlg)

//}}AFX_DATA_MAP

}_MESSAGE_MAP(CAboutDlg, CDialog)

//{{AFX_MSG_MAP(CAboutDlg)

// No message handlers

//}}AFX_MSG_MAP_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CTest3Dlg dialog

Dlg::CTest3Dlg(CWnd* pParent /*=NULL*/)

: CDialog(CTest3Dlg::IDD, pParent)

{

//{{AFX_DATA_INIT(CTest3Dlg)_Length = _T("");_Comp = _T("");

//}}AFX_DATA_INIT

// Note that LoadIcon does not require a subsequent DestroyIcon in Win32_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);

}

CTest3Dlg::DoDataExchange(CDataExchange* pDX)

{::DoDataExchange(pDX);

//{{AFX_DATA_MAP(CTest3Dlg)_Control(pDX, IDC_EDIT_COMP, m_CompControl);_Control(pDX, IDC_EDIT_LENGTH, m_LengthControl);_Text(pDX, IDC_EDIT_LENGTH, m_Length);_Text(pDX, IDC_EDIT_COMP, m_Comp);

//}}AFX_DATA_MAP

}

_MESSAGE_MAP(CTest3Dlg, CDialog)

//{{AFX_MSG_MAP(CTest3Dlg)_WM_SYSCOMMAND()_WM_PAINT()_WM_QUERYDRAGICON()_BN_CLICKED(IDC_BUTTON_COMP, OnButtonComp)_BN_CLICKED(IDC_BUTTON_LENGTH, OnButtonLength)_BN_CLICKED(IDC_BUTTON_RUN_COMP, OnButtonRunComp)_BN_CLICKED(IDC_BUTTON_RUN_LEN, OnButtonRunLen)

//}}AFX_MSG_MAP_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CTest3Dlg message handlers

CTest3Dlg::OnInitDialog()

{::OnInitDialog();

// Add "About..." menu item to system menu.

// IDM_ABOUTBOX must be in the system command range.((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);(IDM_ABOUTBOX < 0xF000);

* pSysMenu = GetSystemMenu(FALSE);(pSysMenu != NULL)

{strAboutMenu;.LoadString(IDS_ABOUTBOX);(!strAboutMenu.IsEmpty())

{>AppendMenu(MF_SEPARATOR);>AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);

}

}

// Set the icon for this dialog. The framework does this automatically

// when the application's main window is not a dialog(m_hIcon, TRUE);// Set big icon(m_hIcon, FALSE);// Set small icon

// TODO: Add extra initialization here

TRUE; // return TRUE unless you set the focus to a control

}

CTest3Dlg::OnSysCommand(UINT nID, LPARAM lParam)

{((nID & 0xFFF0) == IDM_ABOUTBOX)

{dlgAbout;.DoModal();

}

{::OnSysCommand(nID, lParam);

}

}

// If you add a minimize button to your dialog, you will need the code below

// to draw the icon. For MFC applications using the document/view model,

// this is automatically done for you by the framework.

CTest3Dlg::OnPaint()

{(IsIconic())

{dc(this); // device context for painting

(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

// Center icon in client rectanglecxIcon = GetSystemMetrics(SM_CXICON);cyIcon = GetSystemMetrics(SM_CYICON);rect;(&rect);x = (rect.Width() - cxIcon + 1) / 2;y = (rect.Height() - cyIcon + 1) / 2;

// Draw the icon.DrawIcon(x, y, m_hIcon);

}

{::OnPaint();

}

}

// The system calls this to obtain the cursor to display while the user drags

// the minimized window.CTest3Dlg::OnQueryDragIcon()

{(HCURSOR) m_hIcon;

}

CTest3Dlg::OnButtonComp()

{dlg(TRUE,NULL,NULL,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,NULL,NULL);( dlg.DoModal() != IDOK ) return;_Comp = dlg.GetPathName();_CompControl.SetSel(0,255);_CompControl.ReplaceSel(m_Comp);

}

CTest3Dlg::OnButtonLength()

{dlg(FALSE,NULL,NULL,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT | OFN_OVERWRITEPROMPT,NULL,NULL);( dlg.DoModal() != IDOK ) return;_Length = dlg.GetPathName();_LengthControl.SetSel(0,255);_LengthControl.ReplaceSel(m_Length);

}

CTest3Dlg::OnButtonRunComp()

{();( m_Comp == "" ) { MessageBox("Введите имя файла ",MB_OKCANCEL | MB_ICONQUESTION); return; }MAX = 65536;list[MAX];div = RAND_MAX/2+1;( m_Comp.Find("Creature",0)!=-1 ) {tm = CTime::GetCurrentTime();(tm.GetTime());( int i=0; i<MAX; list[i++].Format("%d",rand()/div) );tmp = m_Comp.Mid(9);fileres(tmp,CFile::modeCreate | CFile::modeWrite);( i=0; i<MAX; tmp = list[i++], tmp += '\n', fileres.WriteString(tmp) );.Close();;

}fileres;

//MessageBox("Test Before","Test");.Open(m_Comp,CFile::modeRead);

//MessageBox("Test After","Test");( int i=0; i<MAX; i++ ).ReadString(list[i]);*b, *a = new short[MAX];( i=0; i<MAX; i++ )( list[i][0] ) {'0': a[i] = 0; break;'1': a[i] = 1; break;: return;

}c = 0,len = MAX,is1;( len != 1 ) {/= 2;= new short[len];( i=0, is1=0; i<len; i++ ) {[i] = a[i] ^ a[i+len];= is1 | (b[i] == 1);

}( is1 ) { a = b; c += len; };

}+= a[0] == 1;show;.Format("а вот и получи: %d",c);(show, "вот и результат :)",MB_OK | MB_ICONINFORMATION);

}

CTest3Dlg::OnButtonRunLen()

{z[7][128]; //определили массив последовательности m=0; //максимальная длина последовательности

CString line;/* = GetCommandLine();

char upto;( line[0] == '\"' ) upto = '"';upto = ' ';len = line.GetLength();( int i=1; (i<len) && (line[i] != upto); i++ );++, i+= upto=='"';arg = line.Mid(i);(arg,"test",MB_OKCANCEL | MB_ICONINFORMATION);*/();( m_Length == "" ) { MessageBox("Введите имя файла ",MB_OKCANCEL | MB_ICONQUESTION); return; }fileres(m_Length,CFile::modeCreate | CFile::modeWrite);( short n=0; n<128; n++ )

{.Format("%3d: ",n);.WriteString(line);( short t=6,k = n; t>=0; t-- )

{

z[t][0] = k % 2; //остаток от деления на 2

k /= 2; //частное от деления на 2

} //получили начальное состояние( short i=1,s=0; i<128 && s!=7; i++ )

{[0][i] = !z[0][i-1] | z[1][i-1];[1][i] = (z[0][i-1] & z[1][i-1]) | !(z[0][i-1] | z[1][i-1] | z[2][i-1]);[2][i] = (!z[1][i-1] & (z[2][i-1] | !z[3][i-1])) | (z[1][i-1] & !z[2][i-1]);[3][i] = (z[2][i-1] & !z[4][i-1]) | (!z[3][i-1] & z[4][i-1]);[4][i] = (z[3][i-1] & z[5][i-1]) | (z[4][i-1] & !z[5][i-1]);[5][i] = (!z[4][i-1] & z[5][i-1]) | (z[4][i-1] & !z[6][i-1]);[6][i] = !z[6][i-1];( short j=0; j<i && s!=7; j++ )

{( t=0,s=0; t<7; s += z[t][i] == z[t][j], t++ );( s==7 ) {.Format("длина: %3d начало: %3d конец: %3d\n",i-j,j,i);

//write(" длина",(i-j));

//write(" начало",j);

//writeln(" конец",i);.WriteString(line);( (i-j) > m ) m = (i-j);

}

}

}

}.Close();

}

В.5. VHDL - модели модулей сигнатурного мониторинга, реализованных на ПЛИС ALTERA MAX 7000S.

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

entity msa is(: in BIT;: in BIT;: in BIT_VECTOR (1 to 16);: buffer BIT_VECTOR (1 to 16);: out BIT;: out BIT

);msa;

-}} End of automatically maintained section

msa of msa is

- <<enter your statements here>>(clk,reset)v1,v2,v3,v4,v5:BIT;:=x(1) xor x(2) xor x(3) xor x(4) xor x(5) xor x(6) xor x(7) xor x(8)x(9) xor x(10) xor x(11) xor x(12) xor x(13) xor x(14) xor x(15) xor x(16);:=o(7) xor o(9) xor o(12) xor o(16);:=x(1) xor v2;

v4:=o(1) xor o(2) xor o(3) xor o(4) xor o(5) xor o(6) xor(8) xor o(10) xor o(11) xor o(13) xor o(14) xor o(15);reset='0' then<=B"1111_0000_0000_0000";<='0';clk='1' and clk'event then(1) <= v3;(2) <=x(2) xor o(1);(3) <=x(3) xor o(2);(4) <=x(4) xor o(3);(5) <=x(5) xor o(4);(6) <=x(6) xor o(5);(7) <=x(7) xor o(6);(8) <=x(8) xor o(7);(9) <=x(9) xor o(8);(10)<=x(10) xor o(9);(11)<=x(11) xor o(10);(12)<=x(12) xor o(11);(13)<=x(13) xor o(12);(14)<=x(14) xor o(13);(15)<=x(15) xor o(14);(16)<=x(16) xor o(15);<=v4 xor v1; if;if;process;(x,o)v1,v2,v3,v4,v5:BIT;:=x(1) xor x(2) xor x(3) xor x(4) xor x(5) xor x(6) xor x(7) xor x(8)x(9) xor x(10) xor x(11) xor x(12) xor x(13) xor x(14) xor x(15) xor x(16);:=o(7) xor o(9) xor o(12) xor o(16);:=x(1) xor v2;

v4:=o(1) xor o(2) xor o(3) xor o(4) xor o(5) xor o(6) xor(8) xor o(10) xor o(11) xor o(13) xor o(14) xor o(15);<=v2 xor v4; process; msa;

В.5.2. Генератор последовательности де Брейна с порождающим многочленом .

entity deBrein3 is(: in BIT;: in BIT;: buffer BIT_VECTOR (1 to 16)

);deBrein3;

deBrein3 of deBrein3 is

- <<enter your statements here>>(clk,reset)v1,v2,v3,v4:BIT;reset='0' then<=B"0000_0000_0000_0000";clk='1' and clk'event then:=not(not o(1) and not o(3) and o(12)); :=(not o(2) and not o(4) and not o(5) and not o(6) and not o(7)not o(8) and not o(9) and not o(10) and not o(11)not o(13) and not o(14) and not o(15) and v1);:=o(1) or v2;:=o(3) xor o(12) xor o(16) xor v3;(1)<=v4;(2)<=o(1);(3)<=o(2);(4)<=o(3);(5)<=o(4);(6)<=o(5);(7)<=o(6);(8)<=o(7);(9)<=o(8);(10)<=o(9);(11)<=o(10);(12)<=o(11);(13)<=o(12);(14)<=o(13);(15)<=o(14);(16)<=o(15);if;if;process;

deBrein3;

В.5.3. Генератор последовательности де Брейна с порождающим многочленом .

entity deBrein4 is(: in BIT;: in BIT;: buffer BIT_VECTOR (1 to 16)

);deBrein4;

-}} End of automatically maintained section

deBrein4 of deBrein4 is

- <<enter your statements here>>(clk,reset)v1,v2,v3,v4:BIT;reset='0' then<=B"0000_0000_0000_0000";clk='1' and clk'event then:=not(o(9) and not o(13)); :=(not o(1) and not o(2) and not o(3) and not o(4) and not o(5)not o(7) and not o(8) and not o(10) and not o(11)not o(12) and not o(14) and not o(15) and v1);:=o(6) or v2;:=o(9) xor o(13) xor o(16) xor v3;(1)<=v4;(2)<=o(1);(3)<=o(2);(4)<=o(3);(5)<=o(4);(6)<=o(5);(7)<=o(6);(8)<=o(7);(9)<=o(8);(10)<=o(9);(11)<=o(10);(12)<=o(11);(13)<=o(12);(14)<=o(13);(15)<=o(14);(16)<=o(15);if;if;process;

deBrein4;

В.5.4. Генератор М - последовательности на основе клеточного автомата со следующими правилами: 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

entity cell12 is(: in BIT;: in BIT;: buffer BIT_VECTOR (1 to 12)

);cell12;

cell12 of cell12 is(clk,reset)reset='0' then<=B"111111001100";clk='1' and clk'event then(1)<='0' xor o(2);(2)<=o(1) xor o(2) xor o(3);(3)<=o(2) xor o(4);(4)<=o(3) xor o(4) xor o(5);(5)<=o(4) xor o(6);(6)<=o(5) xor o(6) xor o(7);(7)<=o(6) xor o(8);(8)<=o(7) xor o(8) xor o(9);(9)<=o(8) xor o(10);(10)<=o(9) xor o(10) xor o(11);(11)<=o(10) xor o(12);(12)<=o(11) xor o(12) xor '0';if;if;process;

 cell12;

В.5.5. Генератор М - последовательности на основе клеточного автомата со следующими правилами: 150, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

entity cell16 is(: in BIT;: in BIT;: buffer BIT_VECTOR (1 to 16)

);cell16;

cell16 of cell16 is

- <<enter your statements here>>(clk,reset)reset='0' then<=B"1111_1100_1100_1111";clk='1' and clk'event then(1)<= '0' xor o(1) xor o(2);(2)<= o(1) xor o(2) xor o(3);(3)<= o(2) xor o(4);(4)<= o(3) xor o(4) xor o(5);(5)<= o(4) xor o(6);(6)<= o(5) xor o(6) xor o(7);(7)<= o(6) xor o(8);(8)<= o(7) xor o(8) xor o(9);(9)<= o(8) xor o(10);(10)<=o(9) xor o(10) xor o(11);(11)<=o(10) xor o(12);(12)<=o(11) xor o(12) xor o(13);(13)<=o(12) xor o(14);(14)<=o(13) xor o(14) xor o(15);(15)<=o(14) xor o(16);(16)<=o(15) xor o(16) xor '0';if;if;process;

 cell16;

ПРИЛОЖЕНИЕ Г

Функции обратной связи СРНОС степени 16 для получения последовательностей де Брейна и оценка их сложности.

№ п/п

Примитивный многочлен

Функция обратной связи для получения последовательностей де Брейна.

Сложность c(s).

1.

65533



2.

65535



3.

655535



4.

655534



5.

65533



6.

65533



7.

65535



8.

65535



9.

65535



10.

65535



11.

65535



12.

65533



13.

65533



14.

65535



15.

65535



16.

65535



17.

65535



18.

65534



19.

65535



20.

65535



21.

65534



22.

65532



23.

65534



24.

65535







ПРИЛОЖЕНИЕ Д

Документы, подтверждающие внедрение результатов диссертации.

УТВЕРЖДАЮ

материалов НАН Украины

_________________________ Бородавка Ю.П.

АКТ

внедрения результатов диссертационной работы Темникова Игоря Николаевича

Комиссия в составе: председатель комиссии - ст. научный сотрудник ИСМА, к.т.н. Звягинцев В.Н.; члены комиссии: ст. научный сотрудник ИСМА Епифанов Ю.М., ст. научный сотрудник Герасимчук Л.И. констатирует, что результаты диссертационной работы Темникова И.Н. использованы при выполнении поисковой темы «ТЕМП» НАН Украины № гос. рег. 0103U003476 (24.03.2003 - 21.12.2003) «Разработка новой системы и алгоритмов автоматизированного управления выращиванием крупногабаритных монокристаллов», которая выполнялась в ИСМА с участием Харьковского Национального технического университета «ХПИ».

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

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

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

схемные реализации многоканальных самопроверяемых сигнатурных анализаторов на ПЛИС ALTERA MAX 7000S.

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

Председатель комиссии:с.н.с. Звягинцев В.Н.

Члены комиссии:с.н.с. Епифанов Ю.Н.

с.н.с. Герасимчук Л.И.

УТВЕРЖДАЮ

Технический директор АО Хартрон, к.т.н.

_________________________ В.В. Новиков

АКТ

апреля 2004 г.

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

Комиссия в составе:

Председатель комиссии:Бутенко И.Н. - начальник центра координации работ

Члены комиссии:Бурьян А.Н. - главный специалист

Сирук В.А. - главный специалист

В период с 12 по 14 апреля 2004 года комиссия провела работу по определению внедрения в опытно - конструкторских работах ОАО ХАРТРОН результатов диссертационной работы И.Н. Темникова, представленной на соискание ученой степени кандидата технических наук.

Комиссией установлено, что при разработке исполнительного автомата управления приводом ШЭМ - М системы управления и защиты реакторной установки, которые выполнялись на ОАО ХАРТРОН, использовались разработанные И.Н. Темниковым методы синтеза и проектирования модулей генераторов и сигнатурно - синдромных анализаторов в качестве встроенных средств псевдоисчерпывающего тестирования блоков исполнительного автомата.

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

Председатель комиссии:Бутенко И.Н.

Члены комиссии:Бурьян А.Н.

Сирук В.А.

УТВЕРЖДАЮ

Проректор по учебной работе

Украинской Государственной Академии

Железнодорожного транспорта

_________________________ доц. Писаревский И.М.

СПРАВКА

февраля 2004 г.

г. Харьков

О внедрении программных средств синтеза модулей сигнатурного

мониторинга в учебный процесс УкрГАЖТ

В период с 02 по 05 февраля 2004 года была проведена работа по определению внедрения в учебный процесс аппаратно - программных методов синтеза модулей сигнатурного мониторинга, разработанных на кафедре автоматики и управления в технических системах Харьковского Национального технического университета «ХПИ» при непосредственном участии аспиранта Темникова И.Н.

Установлено, что методы синтеза позволяют проектировать на ПЛИС модули сигнатурного мониторинга:

генераторы псевдоисчерпывающих тестов и сигнатурные анализаторы для проверки исправности (n,m,k) схем широкой номенклатуры;

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

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

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

Разработанные аппаратно - программные средства используются для подготовки студентов в курсах «Электроника и микросхемотехника», «Надежность систем железнодорожной автоматики», в курсовом и дипломном проектировании.

Зав. кафедрой автоматики и д.т.н., проф.Загарий Г.И.

компьютерных систем управления

1.      

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

 

Не нашел материал для своей работы?
Поможем написать качественную работу
Без плагиата!