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

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

:: - од--

1 3 Ч'Ш) На правах рукописи

ЛАТЫПОВ Рустам Хафизович

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

05.13.13 - вычислительные машины,

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

Автореферат

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

МОСКВА - 1994

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

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

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

Ведущее предприятие: Казанский ордена Трудового Красного Знамени научно-исследовательский институт радиоэлектроники

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

1995 г.в _час. _мин. на заседании диссертационного совета Д002.68.01 Института проблем управления по адресу: 117806 Москва, Профсоюзная ул. , 65.

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

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

Ученый секретарь диссертационного совета, к. т. н.

Е. Е Юркевич

ОБЩАЯ ХАРАКТЕРИСТИКА "РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 5 -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- б -

теоретических основ встроенного тестирования,

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

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

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

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

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

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

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

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

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

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

Апробация работы. Диссертационная работа, отдельные ее разделы и результаты докладывались: на итоговых научных конференциях Казанского госуниверситета, научно-техническом семинаре "Прогнозирование и диагностика в повышении эффективности производства и эксплуатации РЭА"(Москва,

1982), Всесоюзном семинаре "Неразрушающие методы контроля" (Москва, 1982), Всесоюзном симпозиуме "Вероятностные автоматы и их приложения" (Казань, 1983), научно-технической конференции "Вероятностные методы и средства" (Новгород,

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

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

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

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

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

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

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

решения об исправности.

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

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

Стратегия исчерпывающего тестирования исключает трудоемкую процедуру построения тестовых наборов и дает высокую полноту тестирования. При тестировании многовходной комбинационной схемы подаются все возможные входные двоичные наборы. Однако даке при высокой скорости подачи тактовых импульсов время тестирования велико, что делает малопрактйчным исчерпывающее тестирование для п > 25. Для сохранения области применения стратегии исчерпывающего тестирования предложены методы разбиения логики на сегменты с числом входов меньше п. Такой подход носит название, псевдоисчерпывающэго тестирования (Е. Мэ^С1ивкву). При исчерпывающем или псевдоисчерпывающем тестировании на выходе обнаруживаются почти 100% неисправностей, причем нет необходимости в моделировании неисправностей. Обнаруживаются все неисправности, не выводящее устройство из класса комбинационных схем. Однако разбиение схемы на достаточно мелкие сегменты может потребовать больших усилий,и стоимость такого разбиения может быть очень высокой.

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

воспроизведения также требует большого количества времени тестирования. Однако для данного метода, по сравнению с упомянутыми, сравнительно невелики затраты на дополнительное оборудование. В псевдослучайных методах предполагается, что каждый разряд набора с некоторой вероятностью принимает значение 0 или 1, причем вероятности для каждого разряда одинаковы. Число наборов колеблется ■ от 10000 до 10000000, в зависимости от тестируемости проверяемого устройства и необходимой полноты тестирования. Трудность при использовании псевдослучайного тестирования заключается в том, что часть неисправностей не может быть обнаружена этим

ыЛОДОМ.

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

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

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

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

неисправности.

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

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

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

В других работах (Т. Литиков И. П.) предложены

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

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

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

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

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

1) множество Т расширяется и упорядочивается;

2) строится тестовый генератор на основе сдвигового регистра, воспроизводящий построенную последовательность.

Если задано тестовое множество Т, то строится последовательность Б, удовлетворяющая следующим условиям:

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

2) в Б нет одинаковых наборов;

3) для каждого набора ив Т найдется набор из Б, который содержит исходный набор в качестве поднабора.

Последовательность и, удовлетворяющую только пунктам 1) и 3), можно воспроизвести с помощью регистра сдвига, на вход которого подается некоторая последовательность.

- 15 -

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

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

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

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

Предложенный в данном разделе генератор сочетает

преимущества алгоритмического 'воспроизведения тестовой последовательности с достоинствами зоспроизведения минимального теста: время тестирования значительно уменьшается по сравнению с алгоритмическими методами и, с другой стороны, по сравнению с традиционными методами, значительно сокращается объем хранимой информации. Заметим, что чем больше разрядность 1 памяти, тем меньше приходится добавлять наборов в Т для получения £.

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

Полученные результаты позволяют ограничивать перебор при анализе поведения регистра сдвига с обратной связью типа &, если конъюнкция содержит переменные без отрицания, при этом указываются возможные длины циклов. Проведен отдельно анализ поведения регистра сдвига, когда конъюнкция состоит только из отрицаний переменных. Для цикла Б длины Ь вводится множество Н(Б), которое задает индексы переменных от 1 до Ь, которые могут входить в функцию обратной связи К с отрицаниями.

Определяется процедура построения множества <Э(Б), которое задает все функции обратной связи К из отрицаний переменных, порождающие заданный цикл состояний. Найдены необходимые и достаточные условия, при которых регистр сдвига с функцией обратной связи К содержит цикл Б длины Ь.

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

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

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

или v.

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

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

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

Предположим, что ПУ является ш - выходной комбинационной схемой и на ее выходах реализуется система булевых функций Г. Обозначим через N множество всех 1 двоичных входных наборов, для которых значение хотя бы одной функции из Р равно единице. Рассмотрим для множества N соответствующее множество конъюнкций К. Множество К задает объединение всех конъюнкций, входящих в СДНФ функций из Р. Введем двоичную (пх1)-матрицу и, которая определяет вхоздение или невхоядение конъюнкций в СДНФ фушсций из Р. Погсазано, что матрица и и 4хно«эство К однозначно определяют систему выходных функций ПУ.

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

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

Рассматривается реализация ПУ в виде программируемой логической матрицы (ПЛМ) типа И-ИЛИ, которая задается разложением выходных функций в виде СДН& И-матрица реализует конъюнкции полного ранга из множества К, а матрица ИЛИ реализует матрицу и, причем если элемент матрицы равен 1, то в соответствующем увле матрицы ИЛИ имеется соединение, в противном случае соединения нет.

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

Применение ЛПМ для сжатия выходной последовательности часто оправдано для некоторых классов схем. Таким примером может служить дешифратор. Тестовая система для проверки дешифратора содержит счетчик в качестве тестового генератора и замкнутый регистр сдвига в качестве сигнатурного анализатора. Рассмотрены различные классы константных неисправностей и показано, при каких условиях все они

- 19 -•

обнаруживаются предложенной тестовой системой.

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

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

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

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

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

характеристических матриц. Доказано, что если характеристический многочлен автономной ЛПМ является неприводимым многочленом простого периода , то доля необна-руживаемых искажений близка к 0 и уже для размерности ЛПМ, равной 8,9,10, эта доля меньше 0,0001.

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

Основной проблемой при построении системы неполного дублирования является построение неполного дублирующего устройства. Ясно, что в качестве ДУ нет смысла использовать точную копию проверяемой схемы, так как это сильно увеличивает сложность тестовой' системы. Для систем встроенного тестирования допустимой считается сложность дополнительных схем порядка log N, где N - длина тестовой последовательности. Такова сложность встроенного тестового генератора и встроенных схем сжатия в типичной структуре встроенного тестированния. Поэтому сложность дополнительного дублирующего устройства также должна быть порядка log N.

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

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

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

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

Задача синтеза ЛКС или задача построения выходной функции ЛКС сведена к известной задаче приближения заданной булевой функции с помощью линейной функции или к известной задаче из теории кодирования: по принятому слову восстановить слово из кода Рида-Маллера первого порядка (РЩ-код). Построен алгоритм синтезаДУ для заданного ПУ.

В следующем разделе определяется эффективность предлагаемой системы неполного дублирования. Пусть i(j)-число классов смежности по РШ-коду, вес лидеров которых равен j, причем j = 0,...,г, где г - радиус кода. Получена формула для вычисления среднего объема v класса эквивалентности после модификации. Для нахождения точного значения величины v необходимо знать распределение весов лидеров смежных классов по коду РШ, то есть распределение чисел i(j). К сожалению, для больших значений п это пока нерешенная задача. Приведена таблица значений v для известных величин п. Для сравнения приведены объемы классов эквивалентности v' для метода сигнатур, полученные при увеличении размеров анализатора на число к, где к - количество элементов, необходимых для построения ДУ. Таблица иллюстрирует возрастающую в среднем эффективность предлагаемого метода неполного дублирования по сравнению с сигнатурным анализом при увеличении числа входов проверяемой схемы. Эффективнее всего использовать предлагаемый метод для выходных функций,

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

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

Далее рассматривается вариант системы неполного дублирования, в которой используется сравнение выходов на каждом шаге. Ранее предполагалось, что тестовый генератор воспризводит исчерпывающий тест для проверки ПУ. Однако из результатов предыдущего раздела можно видеть, что чем меньше длина входной последовательности, тем эффективнее неполное дублирование, при, условии сохранения полноты тестовой последовательности. Предполагается, что ПУ специально спроектировано для облегчения тестирования и в качестве тестовой последовательности используются универсальные тестовые последовательности типа "бегущий ноль" или "бегущая единица". Первая кз этих последовательностей состоит из (п+1) наборов разрядности п: (1...1), (01. ..1), (101... 1), ...,(1... 10), причем п - количество входных вершин схемы. Другая последовательность также состоит из (п+1) наборов разрядности п: (00. ..0), (10. ..0), (010. ..0), ..., (0. ..01). Показано, что для такой системы тестирования всегда' можно ' построить неполное линейное ДУ, так что выходные последовательности ДУ и ПУ полностью совпадают для тестовой последовательности, фи этом схема сжатия есть одноразрядная схема обнаружения единичного сигнал® в последовательности, эта схема гораздо проще стандартного сигнатурного анализатора фи тестировании обнаруживаются все

неисправности ив заданного класса, которые проявляются на выходе ПУ.

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

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

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

В первом разделе рассматривается реализация выходной переключательной функции в виде полинома в базисе, состоящем из конъгакции, двоичного сумматора и отрицания (примером такого разложения является разложение функции в виде полинома йэгалкина (полинома Рида-Мадлера)). Предлагается структура комбинационной схемы, реализованной в специальном базисе, состоянии из элементов И, ИСКЛЮЧАЮЩЕЕ-ШШ и инвертора. Вводятся дополнительные средства в ко'йинацконную схему: управляющий вход, дополнительная конъюнкция и усложняется реализация инвертирования, что приводит к удорожанию схемы. Однако эти недостатки компенсируются следующими преимуществами: нет необходимости в трудоемкой процедуре построения тестового множества; обнаруживаются все одиночные неисправности; тестирование производится с помощью универсальной тестовой последовательности, что экономит время тестирования, и стоимость тестового генератора - простой генератор для воспроизведения универсальной тестовой последовательности представлен в первой главе.

В следующем разделе предложены две структуры ПЛУ, пригодных для компактного тестирования.

Рассматриваются ШШ на элементах И и ШШЯАЩБЕ-ИЖ ПЛЫ на элементах И и КСЙЛЮЧАВДЕЕ-ИЖ строятся на основе разложения выходных функций ПУ в базисе из конъюнкции, двоичного сумматора и инвертора Вводятся следующие дополнительные средства в матрицы ПЛЫ. Добавляются один или два дополни-

тельных столбца в И-матрицу, добавляется дополнительная-строка в матрицу ИСКЛЮЧАЮЩЕЕ-ИЛИ. Показано, что универсальный тест позволяет обнаружить все константные неисправности предложенных структур ПШ

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

Далее строится система кольцевого тестирования для первой из предложенных структур ПЛМ. Вводится регистр сдвига с разрядами 1, 2, ..., п, п+1, который совмепщет функции тестового генератора и схемы сжатия. Число разрядов регистра на единицу больше числа строк И-матрицы. Добавлена схема проверки на четность (многовходной элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ), соединенная со всеми выходами ПЛМ. Тогда система кольцевого тестирования в исправном состоянии на разрядах 1,...,п воспроизводит универсальный тест. Предложенная система кольцевого тестирования позволяет* обнаружить всякую одиночную константную неисправность как в исходной ПЛМ, так и в дополнительных схемах.

В последнем разделе предлагается тестовая система для второй из разработанных структур ПЛМ. Система встроенного тестирования построена на основе стратегии неполного дублирования. Тестовый генератор подает на входы тестируемой ПЛМ универсальную последовательность тестовых наборов. Добавлена схема проверки на четность (многовходной элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ), соединенная со всеми выходами ПЛМ. Схема проверки на четность преобразует многоразрядную выходную последовательность в одноразрядную. Так как используется

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

В пятой главе предлагаются устройства,

построенные на основе полученных теоретических результатов.

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

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

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

Рассматривается класс неисправностей, при которых на выходе блока умножения матрицы на случайный вектор вместо вектора У = ВХ, где В - невырожденная матрица, появляется вектор У = В'Х, где В' - вырожденная матрица. В этом случае последовательность на Еыходе блока умножения на

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

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

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

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

В приложении приведены акты об использовании результатов диссертационной работы.

- 27 -

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

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

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

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

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

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

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

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

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

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

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

9. Предложена легкотестируемая структура комбинационных схем. Схема реализуется в специальном базисе, состоящем из элементов И, ИСКЛЮЧАЮЩЕЕ-ИЛИ и инвертора. Вводятся дополнительные управляющие входы и дополнительная конъюнкция. Эти дополнительные затраты компенсируются тем, что для тестирования используется универсальное тестовое множество, что экономит время тестирования и стоимость тестового генератора Обнаруживаются все одиночные неисправности схемы.

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

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

- 29 -

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

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

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

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

1. Латыпов Р. X Изменение яордановой структуры матриц при возмущениях и применение в теории линейной последовательностной машины // Изв. вузов. Математика. -1983. - N 6. - С. 63-64.

2. Латыпов Р. X Штод сигнатурного анализа многовыходных схем //Автоматика и вычислительная техника - 1983. - N 6. -С. 84-86.

3. Латыпов Р. X. ' О . достоверности кольцевого тестирования линейных последовательностей машин // Автоматика и вычислительная техника- 1984.- N 4.- С.89-91.

4. Латыпов Р. X Автономное тестирование линейных последовательностных машин //Автоматика и телемеханика . -1985.- N 1.- С. 168-172.

5. Латыпов Р. X. Сравнение сигнатурного анализа с тривиальным способом сжатия при обнаружении отказов линейной комбинационной схемы // Автоматика и телемеханика . - 1985 .-N 2.- 0.165-167.

6. Латыпов Р. X К воспроизведению заданного множества тестовых наборов // Электронное моделирование . -1985 . - N 6 .- С. 90-92.

7. Латыпов Р. X. Применение кодов Рида-Маллера при самотестировании схем //Автоматика и телемеханика . -1986.- N 9 . -С. 145-151.

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

9. Латыпов Р. X Аналитический метод вычисления сигнатур для многовыходных дискретных структур // Автоматика и вычислительная техника . - 1989 . - N 2 . -С. 94.

10. Латыпов Р. X Периодические последовательности, порождаемые регистром сдвига с нелинейной обратной связью // Известия вузов. Штематика . - 1989 . - N 5 . -С. 3-17.

11. Латыпов Р. X Воспроизведение тестовых наборов и сжатие данных с помощью нелинейного регистра сдвига // Автоматика и телемеханика .- 1989 N 10 .-С. 167-174.

12. Латыпов Р. X Тестовое диагностирование на основе метрических свойств схем // Автоматика и телемеханика. . -1991 .-N2.-0.171-178. ' -

13. Латыпов Р. X Тестовый генератор на основе линейного регистра сдвига // Автоматика и телемеханика . - 1991 . - N 6 .-С. 148-151.

14. Латыпов Р. X Синтез диагностируемых схем для кольцевого тестирования // Автоматика и телемеханика . - 1992 . - N 2

С. 132-135.

15. Латыпов Р. X Программируемые логические матрицы, пригодные для кольцевого тестирования // Автоматика и телемеханика . - 1992 . - N 8 . - С. 170-174.

16. Мусин Ы.Ф. .Юсупова А. Ф. .Латыпов Р. X Шследовательность диагностических методов при деструктивных заболеваниях легких // Вестник рентгенологии и радиологии . - 1989 . - N 3.- С. 39-43.

17. Генератор псевдослучайных чисел: А. С. 1108614 СССР / Г.Г.Баранов.' В. М. Захаров, Ю. С. Комаров, Е. Л. Столов, Р. X Латыпов.- N 3537239.- Заявл. 6.01.83.- Опубл. 15.04.84.- Бюл. N 30.- 6 с.

18. Генератор псевдослучайных -чисел: А. С. 1224992 СССР / Г.Г.Баранов. В. к. Захаров, Ю. С. Комаров, Р. X Латыпов,

- 31 -

Е. Л Столов. - N 3537239.- Заявл. 12.12.83.- Опубл. 15.12.85. - Бюл. N 14. - 3 с. 1.9. Устройство для контроля цифровых блоков: А. С. 1302285 СССР / P. X Латыпов, Р. М. Мансуров, Ш. Р. Нурутдинов, Е. Л. Столов . - N 3984780 . - Заявл. 3.12.85 . - Опубл. 8.12. 86 . - Бюл. N 13 . - 4 с.

20. Устройство для i встроенного контроля цифровых блоков: А.С. 1397920 СССР / Г.Г.Баранов, Ю. С.Комаров, P. X Латыпов, IIL Р. Нурутдинов, Е. JL Столов .- N 4149073 . -Заявл. 17.11.86 . - Опубл. 22. 01.88 . - Бюл. N 19 . - 4 с.

21. Устройство для оперативного контроля цифровых блоков: А. С. 1619276СССР / P. X Латыпов, Ш. Р. Нурутдинов, Е. Л. Столов N 4435076 .. - Заявл. 3.06.88 .- Опубл. 8. 09. 90 . - Бюл. N 1 . - 3 с.

22. Устройство для контроля цифровых блоков: А. С. . 1695304 СССР / P. X Латыпов, Ш. Р. Нурутдинов, Е. Л. Столов . - N 4661293.- Заявл. 10. 03.89. - Опубл. 1.08.91 Бюл. N 44.-Зс.

23. Устройство для контроля двоичных последовательностей: А. С. 1714604 СССР / P. X Латыпов, Ш. Р. Нурутдинов, Е. Л. Столов . -N 4804827.- Заявл. 26. 01. 90. - Опубл. 22.10.91 .- Бюл. N 7. - Зс.

24.Latypov R.Kh. Built-in self-testing of logic circuits using imperfect duplication // in:L.Budach, R. G. Bukharajev, 0. B. Lupanov, eds., Fundamentals of Computation Theory (Lecture Notes in Computer Science).-Springer-Verlag. -1987.- vol.289 .- P. 197-203.

25. Latypov R. Kh. Comments on "Optimizing Error Masking in BIST by Output Data Modification"// Journal of Electronic Testing : Theory & Applications .- 1991 .- vol.2 . - N 3 .- P. 203-204.

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

В работе С8] автору принадлежат части разделов, относящихся к вопросам синтеза тестовых генераторов и сигнатурных анализаторов, а так*? раздел по неполному дублированию схем.

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

В работах С17-23] автор участвовал в разработке математической модели устройств и их технической реализации.

Сдано в набор 8.12.94 г. Подписано в печать 9.12.94 г. Форм.бум. 60 х 84 1/16. Печ.л.2. Тираж 100. Заказ 464.

Лаборатория оперативной полиграфии КГУ 420008 Казань, Ленина, 4/5