Сжатие информации в системах встроенного тестирования цифровых схем Латыпов, Рустам Хафизович

Введение к работе

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

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

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

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

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

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

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

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

В соответствии с этой целью, исследования проводились в следующих направлениях.

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

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

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

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

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

5. Исследование периодических свойств диаграмм состояний регистров сдвига с нелинейной обратной связью типа конъюнкции или дизъюнкции.

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

7. Разработка алгоритма синтеза гибридного тестового

генератора на основе регистра сдвига и памяти.

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

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

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

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

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

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

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

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

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

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

3. Определение достоверности, обеспечиваемой системой неполного дублирования.

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

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

Научная новизна работы заключается в разработке

- б -

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

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

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

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

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

устройств" и 5.48 "Разработка методов построения систем встроенного контроля". По первой из этих тем автор являлся руководителем работ, по второй - ответственным исполнителем.

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

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

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

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

(Ростов-на-Дону, 1987, Саратов, .1989), международной конференции FCT (Казань, 1987), на семинарах: в Казанском НИИ радиоэлектроники, по технической диагностике в Институте проблем моделирования в энергетике (Киев), по математической кибернетике в Институте кибернетики (Киев), на кафедрах прикладной математики и математической кибернетики Казанского университета, на кафедре ЭВМ Казанского технического университета, по математической кибернетике в МГУ, по технической диагностике в Институте проблем управления.

Публикации. По результатам выполненных исследований опубликованы 32 статьи и получены 7 авторских свидетельств на изобретения. Ряд результатов включен в учебное пособие "Тесты и диагностика отказов ЭВМ" (Издательство Казанского университета, 1982).

Структура и объем диссертации, диссертация состоит из введения, пяти глав, приложения и списка литературы. Объем диссертации 278 страниц, диссертация содержит 29 рисунков и 3 таблицы.