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

Г 8 3 3

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

На правах рукописи

Кобяк Игорь Петрович

АППАРАТНЫЕ УЗЛЫ СВСТЕИЫ КОНПАКТНОГО ТЕСТИРОВАНИЯ ШМРОВЫХ УСТРОЙСТВ

Спепиальность 03. !3.05 "Элементы и устройства вычислительной

техники и систем травления*.

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

Нинск 1992

Работа выполнена на кафедре электронных вычислительных нашив Минского радиотехнического инститгга.

Научный руководитель - доктор технических наук.

профессор Ярколик в. н.

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

профессор Норозевич А. Н. кандидат технических наук, доцент Цирульников А. Н.

Ведущее предприятие - НИН средств автоматизации.

Зашита состоится 21 января 1993 г. на заседании специализированного совета Минского радиотехнического института по адресу; 220600. Г. Минск. УЛ. п. БРОВКИ 6.

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

Автореферат разослан " ■ 1\ _ 19 9 г г.

Ученый секретарь специализированного совета, кандидат технических наук, допент

А. П. Пашкевич

'о-;,, . \л

В!-! аУ.и^ I и'ЛМ

Общая характеристка работы

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

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

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

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

Цель работы. Целью работы является анализ и синтез основных аппаратных блоков выбранной системы компактного тестирования цифровых объектов. В соответствии о поставленной целью ос-

новные задачи работы сформулированы следующим образом:

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

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

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

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

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

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

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

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

Научная новизна;

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

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

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

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

Практическая ценность;

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

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

- по предложенной оригинальной методике синтеза изготовлен' экспериментальный образец 8-канального параллельного статистического анализатора на БИС ПЛЛ К 556 PTI, подготовлена техническая документация для внедрения устройства в производственный процесс.

Реализация в народном хозяйстве. Результаты исследований внедрены на Минском заводе ЭВМ им. Г.К.Орджоникидзе при построении системы 'вероятностного контроля и диагностики; в учебном процессе на кафедре ЭВМ Минского радиотехнического института. Суммарный экономический эффект составил более 30 тыс. рублей.

Настоящая работа выполнялась в рамках хоздоговорных работ NN 11/83, 39/84, проводимых на кафедре ЭВМ МРТИ.

Апробация работы. Основные результаты диссертационной работы обсуждались, на Всесоюзной НТК "Системные исследования и автоматизация в метрологическом обеспечении ШС и управлении качеством" (г.Львов, 1986), на Республиканской НТК "Пути совершенствования технологических процессов в производстве современных изделий радиоэлектроники" (г.Минск, 1983), на III Всесоюзном симпозиуме "Вероятностные автоматы и их приложения" (г.Казань, 1983), на научно-техническом семинаре "Вопросы вибросостояния. Методы формирования и анализа случайных вибраций" (г.Минск, 1984), на I Всесоюзной конференции "Проблемы

создания супер-ЭВМ и супер-систем и эффективность их применения" (г.Минск, 1987), на XXXII конференции молодых ученых ИПУ (г.Москва, 1986).

Публикации. По теме диссертационной работы опубликовано 17 работ, в том числе 6 статей в республиканских и всесоюзных изданиях, 5 авторских свидетельств СССР^ 1 отчет по ПИР, 6 тезисов докладов на НТК.

Содержание работы. Диссертационная работа содержит страниц текста, 43 рисунков и таблиц, список литературы 106 наименований на 11 страшщ.

Результаты, приведенные в диссертационной работе, получены в процессе исследоващ1й, проводимых на кафедре ЭВМ Минского радиотехнического института в период с 1982 по 1991 годы.

Краткое содержание работы

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

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

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

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

В-третьих, недостаточно полно исследованы вопросы синтеза многоразрядных генераторов стохастических тестов с эталонными вероятностными характеристиками.

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

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

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

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

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

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

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

обратной связи, '

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

Решение некоторых из поставленных задач лежит в основе диссертационной работы.

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

1) обеспечение требуемого быстродействия;

2) возможность сочетания детерминированных и вероятностных сигналов в пространстве и во времени;

3) повторяемость входных тестовых наборов;

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

5) изменение мерности закона равномерного распределила формируемых кодов;

6) обеспечение высокоточных вероятностных характеристик;

7) простота управляемости аппаратным генератором;

8) минимальные габариты и сложность устройства.

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

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

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

б

При синтезе тестовой последовательности донным методом возникает задача определения набора коэффициентов 5^(1) (1=1,т), характеризующих топологию соединения выходных сумматоров по модулю два, по заданному сдвигу 1.

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

m

а (К+1) = Е « (1)а.(К), 1 1=1 1 1

где а^(К) -содержимое 1-го разряда, регистра сдвига в К-ый момент времени.

С учетом формулы, описывающей работу последовательного ГПСЧ выражение а^(К+1), 3=2,m примет следующий вид:

т-3+1 3-1

aj(K+l) = £ Sm_.,+l+1<l)ara(K-l),

или

m

aq(K+l) ^^píDOq^ . P,q=Tja

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

а,(К) аа(К) . .. а (К) Г) 1 0 0 ■

а2(К) аэ(К) . 1 0 0 0

1 О . 0 0 0 0

0 0 0 0 0 1

0 0 0 0 1 . ajK-m+2)

0 0 0 1 а (К-п-2) . . am(K-m+1)

m m

гдэ п=-§ -1 при ш -четном и -1 при и -нечетном.

Используя аналитическое отшние ГПСЧ и матрицу Од. р., можно показать, что:

а (К)=а,

а ,(К)=а, + £ а а , ,(К), 1=1,п-1.

п-1 1»1 J

Аналогично, для нижнего треугольника матрицы коэффициентов Од.р., имеем:

а^к-п-г-р^.^ ат(К-п-1-Я

1=1,т-3-1.

Тогда для 1=2,п+1

51(1)=ав+|(К+1) 1 6№ ^ в/1)а»-|*10(К).

а при 1=1,т-п-2 получим:, 6 (1)=а(К+1)

. 1

г„ 1(1)=а„*а+!(К+1> + 1 6т.1 в (К-п-2-1-3).

т-1 п + 2+1' —1 т

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

Известно, однако, что вычисление очередного состояния разрядов регистра сдвига ГПСЧ производится путем умножения исходного вектора на матрицу А:

а. а а . а

1 2 го- 1

1 0 0

О 1 0

О 0 1

При использовании порождающего полинома общего вида р(х)=1+а.|х + а2х2 + ...+ а ц "задача формирования матрицы А может быть реиена с использованием сдвигового регистра, блока конъипкторов и сумматоров по модулю два.

Обозначим через Ъ^(р), 1=1 ,т, 1 -й влемент первой строки матрицы А:

ъ,(1) ъа(1) . .. Ъ^И) ъ

1 0 . 0

0 1 . 0

0 О 1

В общем случае:

Ь,(К+р) 1 1 1=1 Ь,(р)=й.(К+р*1+1) +.Е а 1 (К+р+1-п-1) 11 п=1 " "

1=2, ш

где Д) -значения регистра сдвига, моделирующего сопутствующую матрицу.

Процесс быстрого формирования вектора описывается следующим соотношением:

и • _

а,(К+рт)= Е Ь,(р-1+1)а.(К+п), 1=1,т.

1 3=1 1 *

Как видно из выражения, зависиость величины сдвига вектора а^(К+р+п) от Значений р п п носит неодназначный характер, т.е. не каждому значения р+п соответствует целочисленное значение 1.Поэтому формирование сдвинутого кода осуществляется за несколько итераций. На этапе предварительных расчетов определяется число итераций и количество тактовых импульсов, подава-

А

емых на вход генератора на каждой итерации моделирования работы ГПСЧ. Расчет ведется в соответствии с алгоритмом, приведенным на рис.1. Вычисленные значения поочередно

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

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

ш

а,(К+£). £ (е~Л+1)а.(К).

^ 1=1 1 1

где коэффициенты определяются согласно соотношению

«1 аа яэ • а т а4(К+5-1)

«а<«> "а аз а* • . 0 аа(К+{-1)

= а* ае • . 0 X аэ(К+5-1) •

а а 0 0 . . 0 а (К+5-1) Ю

Для частного случая вто векторно - матричное произведение можно записать в виде:

ва(Е)

«3<«) п

а1 аа ' .. а ю- 1 а ю 1

аа аэ ' .. а т 0 0

"з .. 0 0 X 0

а ю 0 . . 0 0 1

Отсюда выражаем конкретные значения 5^(5) как функцию коэффициентов а^, и, подсталяя результаты в соотношниэ для а^(К+5), имеем:

Ю

Рис. I . Граф—схема алгоритма

1В

Рис. 2. Функциональная схема ГПСМ на Г-григгорах

и

Vi(K+É)=affl-iw + 1=0'и"2

a^K+O^OO + a^K+1)

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

В работе доказано, что в случае, когда код 1000...О имеет первый номер состояния последовательного ГПСЧ, а код III...I имеет номер 1, справедливо*равенство £=2т-1.

Для получения полного периода псевдослучайных кодов в предложенном генераторе необходимо выполнение условия (2га—1,2m—1)=1 в противном случае период следования кодов меньше, чем 2т-1. Таким образом, определение значения 1 или 2ш-1 является одной из главных задач при построении ГПСЧ с минимальными затратами аппаратуры. Эта задача решена для полиномов вида:ф(х)=1+х<1+хш(ч=1,2,4,811б...).

Так при решении задачи было получено сравнение пергой степени с одним неизвестным:'

q*l=m (mod Ы).

Решением данного сравнння будет искомая величина 1, характеризующая сдвиг М-последовательности в синтезированном генераторе:

1 = 2В~1 • и (mod II).

I = loggq

Для удобства вычисления величины 1 вручную ыохно записать:

, _ 11 [m(mod q)l + m

q

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

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

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

, Известно, что сигнатурный анализ порождает разбиение множества реакций объекта контроля на равномощные классы эквивалентности:

B=2n-m

где п -длина реакции объета контроля, m-разрядность анализатора. Для метода счета единиц ата формула имеет вид:

qn

где q -вероятность появления логического уровня в цифровой последовательности длиной п.

Для решния поставленной задачи рассмотрено отношение чисел А и В. Из условия раенства данного отношния единице могут быть определены искомые границы величины вероятности q: qn

А — П * Оп _ 4 — _ 1Л« п

~~В = - - 1, Ш = log2n.

Докажем ряд положений, имеющих непосредственное отношение к решнию данной задачи.

Теорема I. Если период псевдослучайной тестовой последовательности стремиться к бесконечности, то область значений вероятности q эффективного ипользования сигнатурного анализа стягивается в точку. q=0,5., т.е. q-»0,5 при п-»+<*.

Используя фрмулу Стерлинга, соотношение для А/В может быть преобразовано к виду:

1п2 + qlnq + plnp = ^ In ^ + ± (VVV'

Обозначим левую часть соотношения через P(q). Можно покаать, что

lim F(q) = lim (1п2 + qlnq + plnp) я 0.

n-><* n>«

Очевидно, что корнем этого уравнения является q=0,5 и, о

учетом ошибки вычилений, в общем случае можно записать:

д = 0.5 ±-^14 ^ + (е1.ва-ва).

Оценим ошибку вычислений.

Лемма I. Для любых значений п>4 область значений вероятности ч лежит в пределах:

0,25<ч<0,75

Доказательство следует из непосредственной подстановки граничных значений ч в отношние А/В.

Следствие I. Для любых п>4 произведение (рч) удовлетворяет неравенству:

4 < (РЧГ1^ .

Следствие 2.

Докажем лемму 2, из которой вытекает решение задачи. Лемма 2. Если Р(ч)=(а-0,5) то 2<Г(д)<10/3.

Доказательство. Разложим в ряд Тейлора по степеням

(4-0,5), коэффициенты ряда определим по формуле:

(г)

а = ^_(0.5)

г г!

где Р^г^(0,5) г -ая производная функции 1Чч) при ч=0,5. Так для любых г=0,1,2,3... имеем:

О, при г=0 и г=2^-1, _г

при г=23 (3=1,2,3...); В этом случае функция Р(ч) будет иметь вид:

Очевидно, что Г (ч)-сумма положительных членоЕ. Следовательно, Г(ч) всегда больше первого слагаемого, равного 2. С другой стороны данная функция достигает максимума при ч=0,25

или q=0,75. Тогда: Г(0,25)=1(0,75)=10/3. Лемма доказана.

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

Теорема 2. При псевдослучайном тестировании цифровых схем для всех значений

1 1 1П I Г" 1 . 1 ,П 8п , Г

"2---Г'ПГ ~3я~ ^ IT *~Г'Гп- ln "3JT + -¿S

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

Доказательство. Для ?($) можно получить следуюцее соотношение:

= -к 1п -2Щ + -й- <V V V •

Используя ограничения для произведения (pq) и разности (Q1-Q2—Q^). запишем:

P(q) < -¿р 1П -g_ + -Xj .

С другой стороны, учитывая, что ?(q)=(q-0,5) I(q) имеем неравенство вида:

(q-0.5)2X(q) < -4- In- 8n

Отсюда:

2n T 2na

I«" 4-1 </а -Ж + > '

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

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

Обобщим полученные результаты на структуру многоканального сигнатурного анализатора. Обозначили через 1 число.входов мно-

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

1 1 ,/ 1 1n 8in , V гп, 1 , 1 ,/ 1 8in , V

2 " ГУIH 1п 3Г + p^i <q< 2 + 2 VIH 121 Ж + ¡i^i •

Данное соотношение говорит о существнном сужении области значений q, т.к. произведение (1п) убывает значительно быстрее, чем растет логарифмическая функция ln 8in.

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

Нетрудно заметить, что в данных условиях отношение А/В

примет вид! qn

А _ пСп _ 1

Б g!)-*

Решением задачи в данной постановке является соотношение

вида:

\ [1-R(n,x)J < q < I [1+R(n,x)], где радикал R(n,x) есть:

R(n.x) = Ш Щ + -L + ¡ Щ2 .

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

нии величины q. Логарифмируя по основанию два правую часть от-отношения А/В получше:

х = п - ш - .

3 П

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

Обобщая выражение для многоканального устройства с I входами, окончательно имеем:

К(Ш,Х) =(¿11" + -1-а + Щ 2 .

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

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

а1(К+1) = а4(К) + у0

?„м(К+1> = *«♦.<*> +Даз(к)у0

х = 1,2,3,...

где П -конъюнкция х переменных; а (К) -содержимое ячеек устройства в К -ый момент времени: у -входной импульс. (О или I) анализируемой последовательности.

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

рядных слов длиной п преобразуется и поступает на вход однока-нального устройства как однобитовая последовтельность длиной 1п (рис.3).В втом случае содержимое ячеек памяти а1(К+1) однока-нального анализатора будет соответствовать содержимому разрядов а^(К+1) многоканального устройства однозначно.

Решая поставленную задачу, получим описание многоканального устройства для подсчета единиц в алгебре полиномов Рида-Малле-ра:

1-1

а.(К+1)=а (К) + Е у , 1 1 в 1=0

2-1 х

а (К+1)=а (К) + Е [ П а^(К№ (х,у)] " к Р=0 3=1 J р

2-1 х а

а (К+1)=а ,(К) + Е„ [ П а^(К)И (г,у)] «♦> х*1 р=2"-1 3=1 > р

1 ,

X 2-1 ' X в (К+1)=а (К) + П Е_ [ П а^(КЖ (г.у)] Х+1 г=г+1 р=2 -1 3=1 р

Z<X<intlOga(in) ,

где коэффициенты канонического полинома Ир(х,у) вычисляются на основании соотношения:

1-1; l-t+1 1-1 Л (х,у)= Е у Е у ... Е у Д=2х-р. р в^=0 82=0^1 8^8^+1 "Ч

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

У«

-

0101 I I 10100 1110 10 0 110 1 0 111110 0 110

1110 10 0 1110

I1101001 I 10

а)

01ШШ010

6)

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

а П1( к ) ... а4(к)

Выходы

Рис. 4.

Структура анализатора, равмещаемого на одном ТЗЗе

л

п

1-1

1 -1 X

£ [П (х,у) ],

р=г 3=1 3 р

а ,(К+1)=а .(К) + а (К)а (К+1),

К+1 X* 1 XX

1пис^21 < х < 1п1;1ой 1п.

Структура аализатора приведена на рис. 4.

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

Диссертационная работа содержит три приложения. В приложении N I приведена программа моделирования генератора псевдослучайных чисел и исследования вероятностных свойств 'подпоследовательностей. Приложение N 2 содержит технологические таблицы, которые необходимы для автоматизированного прожига матричных БИС. Приложение N 3 содержит акты внедрения результатов НИР.

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

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

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

ЗАКЛЮЧЕНИЕ

го

щего случая порождающего полипома.

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

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

5. Аналитически поставлена и решена задача определения границ интервала вероятностей вффективного использования методов сигнатурного анализа и счета единиц.

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

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

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

Публикации

1. Ярмолик В.Н., Кобяк И.II. Генератор испытательных сигналов для автоматизированных систем тестового контроля. -В сб.: Автоматизация вкспориментальных исследований. - Минск, НТК АН БССР, 1982, с. 95-102.

2. Кобяк И.П., Липшщкий В.А. Аналитический расчет областей применения методов компактного тестирования цифровых

схем. - В кн.: Сиотемные исследования и автоматизация в метрологическом обеспечении ШС и управлении качеством. Тезисы докладов Всесоюзной конференции. - Львов, 1986, 16-18 октября, с. 63-64.

3. Кобяк И.П., Ярмолик В.Н. Использование аппаратных генераторов тестов для вероятностных систем контроля и диагностики. Тезисы докладов Республиканской НТК "Пути совершенствования технологических процессов, материалов и оборудования в производстве современных изделий радиоэлектроники". - Минск, 29 - 30 ноября, 1983, с. 141.

4. Исследовать и разработать аппаратные генераторы для тестирования цифровых узлов ЕС ЭВМ: Отчет по НИР, N гос. регистрации 01830027084, 1983, с. 75.

5. Ярмолик В.Н., Кобяк И.П. Построение генераторов псевдослучайных последовательностей испытательных сигналов для контроля и диагностики узлов ЭВМ. -В сб.: Автоматика и вычислительная техника. - Минск, 1983, вып. 13, с. 95-99.

6. А.о. 966864 (СССР). Устройство для формирования сдвинутых копий псевдослучайной последовательности / Минский радиорадиотехнический институт; авт. изобрет. В.Н.Ярмолик, И.П.Кобяк. -Заявл. 02.12.1980, N 3210981/18-21; опубл. в Б.И. N 38, 1982.

7. Кобяк И.П., Ярмолик В.Н. Высокоэффективный параллельный генератор псевдослучайных последовательностей. - В кн.: Вероятностные автоматы и их приложения. Тезисы докладов III Всесоюзного симпозиума. - Казань, 6-8 июля, 1983.

8. Кобяк И.П. Синтез экономических генераторов равномерно распределенных псевдослучайных испытательных последовательностей. -Изв. ЫВ и ССО СССР. Приборостроение, 1985, N 6, с. 32-36.

9. Кобяк И.П. Метод формирования белого шума в устройствах виброиспытания. - В кн.: Вопросы вибросостояния. Методы формирования и анализа случайных вибраций. Тезисы докладов научно-техничеокого семинара.- М.: ЦНШГГЭИ, 1984, 5-6 мая. с. 52-53.

10. Ярмолик В.Н., Кобяк И.П. Экономический генератор тестовых последовательностей, для контроля узлов ЭВМ.- В сб.:

Автоматика и вычислительная техника, Минск, 1984, вып. 14, о. 86-90, ил.

11. Кобяк И.П., Липницкий В.А. 0 границах применения методов статистического контроля и сигнатурного анализа при псевдослучайном тестировании. - Электрон, моделирование, 1987. т. 26, N 6, с. 74-77.

12. Кобяк И.П. Построение многоканальных статистических анализаторов для контроля цифровых блоков ЭВМ. Электрон, моделирование, 1987, т.9, N 4, с. 41-49.

13. Кобяк И.П., Липницкий В.А. Проектирование аппаратуры самотестирования для схемных плат супер-ЭВМ и систем. - В кн.: Проблемы создания супер-ЭВМ и супер-систем и вффективнооть их применения. - Минск, 1987. 14-17 сентября, с. 149-150.

14. A.c. 1387177 (СССР). Генератор псевдослучайных чисел/ Минский радиотехнический институт; авт. изобрет. В.Н.Ярмолик, И.П.Кобяк. - Заявл. 20.02.85; N 3861006/24-21; опубл. в Б.И. N 13. 1988.

15. A.c. 1170453 (СССР). Генератор тестовых последовательностей/ Минский радиотехнический институт; авт. изобрет. В.Н.Ярмолик, И.П.Кобяк. - Заявл. 30.06.83, N 3613399/24; опубл. в Б.И. N 28, 1985.

16. A.C. 1406741 (СССР). Генератор тестовых последовательностей/ Минский радиотехнический институт; авт. изобрет. И.П.Кобяк, В.И.Шилинговский, В.М. Галецкий. -Заявл. 08.12.1986, N 4156736/24-21, опубл. в Б.И. N 24. 1988.

17. A.C. 1297059 (СССР). Устройство для формирования тестов/ Минский •радиотехнический институт; авт. изобрет. В.Н. Ярмолик, И.П.Кобяк, С.В.Зинькевич. - Заявл. 12.02.85. N 3855602/24-21, опубл. в Б.И. N 10.