Курсовая работа: Цифровая обработка сигналов

При этом, порождающий полином (x) M-последовательности, генератор которой содержит сумматоры по модулю два в цепи обратной связи, является взаимно обратным к полиному M(x), т.е. (x)= M-1(x)=xmM(x-1).

1.5. Особенности построения генераторов тестовых последовательностей.

При компактном тестировании для реализации тестовой последовательности используются простейшие методы, позволяющие избежать сложной процедуры синтеза.[2] К ним относятся следующие процедуры синтеза:

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

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

Формирование псевдослучайных тестовых последовательностей.

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

Глава 2.Сигнатурный анализ.

2.1. Описание сигнатурного анализа.

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

Построить сигнатурный анализатор можно двумя способами: 1)метод деления полиномов и 2)метод свёртки.

Главная идея сигнатурного анализа при использовании метода деления полинома на полином основывается на выполнении операции деления многочленов. В качестве делимого используется поток данных, формируемых на выходе анализируемого цифрового узла, который может быть представлен как многочлен p(x) степени -1, где  - длина потока. Делителем служит примитивный неприводимый полином (x), в результате деления на который получается частное q(x) и остаток S(x), связанные соотношением

 p(x)= q(x) (x)+ S(x),

где остаток S(x), представляющий собой полином степени, меньшей чем m=deg(x), называется сигнатурой.

 M2 D TT M2 D TT M2 D TT

 P(x)

 C 0 C 1 C m-1

 ТИ

 & &  &

0=1 1  m-1

Рис.2.1. Функциональная схема сигнатурного анализатора, построенного

по методу деления полиномов.

  M2  M2

 P(x)  &  & &

 M2 D TT D TT D TT

 C 0 1 C 1 m-1 C m-1 m=1

ТИ

Рис.2.2. Функциональная схема сигнатурного анализатора, построенного

по методу свёртки.

При использовании метода свёртки сигнатурного анализа как метода сжатия реакций цифровой схемы сигнатура R6=a1()a2()...am() формируется по алгоритму:

 a1(0)=a2(0)=...=am(0)=0, (2.1.1)

 a1(k)=y(k)i ai(k-1), (2.1.2)

 aj(k)=aj(k-1), j=2,3...m, k=1,2... , (2.1.3)

где i{0,1}, i=1,2...m, определяются на основании порождающего полинома (x)=11x12x2...mxm, используемого для реализации сигнатурного анализатора.

Однако, результат свёртки c(x) последовательности на сигнатурном анализаторе не есть остаток s(x) от деления на полином (x). В то же время между c(x) и s(x) существует однозначная связь, определяемая соотношением

  1 2 ... m-1 1

 2 3 ... 1 0

s(x)= c(x) ........................................

 m-1 1 ... 0 0

  1 0 ... 0 0

2.2. Одноканальный сигнатурный анализатор.

Типовая структурная схема сигнатурного анализатора состоит из регистра сдвига и сумматора по модулю 2, на входы которого подключены выходы разрядов регистра в соответствии с порождающим полиномом(x) (рис. 2.3.) [5]. Управляющими сигналами сигнатурного анализатора являются СТАРТ, СТОП и СДВИГ. Сигналы СТАРТ и СТОП формируют временной интервал, в течение которого осуществляется процедура сжатия информации на анализаторе. Под действием сигнала СТАРТ элементы памяти регистра сдвига устанавливаются в исходное состояние, как правило, нулевое, а сам регистр начинает выполнять функцию сдвига на один разряд вправо под действием синхронизирующих сигналов СДВИГ. По приходу каждого синхронизирующего импульса в первый разряд регистра сдвига записывается информация, соответствующая выражению (2.1.2), где y(k){0,1} - k-й символ сжимаемой последовательности {y(k)}, k=1,2... ; i{0,1} - коэффициенты порождающего полинома (x); ai(k-1){0,1} - содержимое i-го элемента памяти регистра сдвига в k-1 такт. Процедура сдвига информации в регистре описывается соотношением (2.1.3). Причём , как правило, принимается равным или

  Сигнатура

 M2 RG

 Сдвиг Старт Стоп

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

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

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

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

2.3. Многоканальные сигнатурные анализаторы.

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

  (2.3.1)

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

Как показано в [6] эффективность алгоритма сжатия информации, реализующего соотношение (2.3.1) определяется как:

  (2.3.2)

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

Для оценки вида распределения вероятностей  рассмотрим конкретный пример n=3 – выходной цифровой схемы, длина  выходных реакций которой составляет 21. В результате преобразования трех исходных последовательностей  в последовательность , некоторые их ошибки станут необнаруживаемыми и будут оцениваться выражением:        

  (2.3.3)

которое справедливо для .

Ограничиваясь , определяем согласно (2.3.3) .

Анализ полученных численных значений вероятностей , а также общего выражения (2.3.2) показывает неравномерность закона их распределения, что свидетельствует о достаточно невысокой эффективности рассматриваемого алгоритма сжатия. Кроме того, необходимо отметить большую размерность результата сжатия, которая равна длине  выходных реакций схемы. Поэтому на практике чаще всего используется компромиссное решение, заключающееся в двухступенчатом преобразовании выходных реакций n – выходной цифровой схемы. Первоначально n выходных последовательностей  длиной  преобразуются в последовательность  по выражению (2.3.1). Далее сформированная таким образом последовательность  снимается в m – разрядную сигнатуру (рис. 2.4)

M2

Y1(k)   1 2 3 . . . j . . . m

Y2(k)  

Y0(k)   S(x)

Yn(k)

Рис. 2.4. Многоканальный сигнатурный анализатор.

Эффективность данного преобразования согласно [6] при m=4 определится как

  (2.3.4)

где m – старшая степень порождающего полинома.

Эта формула справедлива, когда .

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

 j1(k) j2(k) j3(k) j4(k)

M2  M2  M2  M2

  D TT  D TT D TT  D TT 

  C  C  C  C

 a1(k) a2(k)  a3(k)  a4(k)

 ТАКТ

  M2

Рис. 2.5. Четырехканальный сигнатурный анализатор.

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

Можно показать, что схема, приведённая на рис.2.5, эквивалентна относительно конечного результата простейшей сигнатуры двухступенчатого сжатия информации (рис. 2.4). А это значит, что в обоих случаях для оценки эффективности можно применять формулу (2.3.3). Оба подхода получения сигнатур отличаются неравномерностью закона распределения вероятностей  необнаружения ошибки кратности m, а, следовательно, невысокой эффективностью. Кроме того, сигнатура многоканального сигнатурного анализатора (МСА), а также размерность сигнатуры S(y) однозначно определяется количеством выходов n исследуемой схемы. Поэтому с увеличением n сложность устройства сжатия и количество бит, используемых для представления сигнатуры S(y), принимает практически недопустимые размеры. Попытка использовать идею каскадирования многоканальных сигнатурных анализаторов позволяет уменьшить размерность результирующей сигнатуры, однако в этом случае оказывается сложным оценить достоверность такого анализатора [6], которая будет зависеть от организации взаимосвязи МСА и их конкретной реализации.

2.4.Многоканальный сигнатурный анализатор использованный в данной работе.

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

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

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

Коэффициенты определятся следующим образом:

2.5. Алгоритм построения многоканального сигнатурного анализатора.

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

1. Вычисляются постоянные коэффициенты

где

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

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

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

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

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

Предварительно докажем следующую теорему.

Теорема. Суммарная сигнатура S(x), полученная для последовательностей  на n – канальном сигнатурном анализаторе, равна поразрядной сумме по модулю два сигнатур , , причём каждая из сигнатур , формируется для последовательности  при условии, что .

Доказательство. В n – канальном анализаторе n входных последовательностей преобразуются в одну вида:

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

 , (2.6.1)

который состоит из суммы по модулю два полиномов вида:

 , (2.6.2)

описывающих выходные последовательности . Каждый полином  можно представить в виде соотношения:

 , (2.6.3)

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

Просуммировав по модулю два правые и левые части равенства (2.6.3), получим, что полином  будет определяться как

 (2.6.4)

для которого также справедливо соотношение , т.е.

 (2.6.5)

В результате сравнения двух последних равенств можно заключить, что суммарная сигнатура S(x), полученная для последовательностей  равна поразрядной сумме по модулю два сигнатур  каждой из входных последовательностей:

  (2.6.6)

что и требовалось доказать.

Основной результат данной теоремы, выраженный соотношением (2.6.5), справедлив для примитивного полинома  и произвольных значений n и l. Следствием этой теоремы является возможность определения эталонной сигнатуры для произвольного множества входных последовательностей. Так, эталонное значение сигнатуры для первой, второй и пятой последовательностей будет вычисляться как

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

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

В результате анализа n=2d реальных последовательностей  на n – канальном анализаторе определяется значение сигнатуры S*(x), которое соответствует соотношению:

По выражению

вычисляется эталонное значение сигнатуры S(x).

Реальное значение сигнатуры S*(x) сравнивается с эталонной сигнатурой S(x). В случае выполнения равенства S*(x) и S(x) считается процедура диагностики оконченной. В противном случае, когда S*(x)¹S(x) выполняется следующий этап алгоритма.

Все множество входных последовательностей разбивается на две группы, причём номера последовательностей  составляют множество А1={1,2,3…n/2}, а номера последовательностей  составляют множество А2={n/2+1,n/2+2,…n}. Значению i присваивается значение 1.

В результате анализа реальных последовательностей, номера которых задаются множеством А1 на n – канальном сигнатурном анализаторе при условии, что последовательности, номера которых определяет множество А2, являются нулевыми, определяется значение реальной сигнатуры.

На основании выражения

определяем S(x).

Проверяется справедливость равенства S*(x)=S(x), в случае выполнения множество А1 заменяется элементами множества А2.

Значение переменной i увеличивается на 1 и сравнивается с величиной n, если i<n, то совершают вышеприведённые действия с элементами множества А2.

Единственный элемент множества А1 представляет собой номер ошибочной последовательности.

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

2.7. Оценка достоверности многоканального сигнатурного анализатора.

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

Это соотношение справедливо для любого соотношения  и , произведение которых равно 2m-1.[6] Приведённая интегральная характеристика эффективности МСА, также как и характеристика одноканального сигнатурного анализатора, является достаточно приближённой оценкой, справедливой для общих допущений. Более полной характеристикой МСА будет распределение вероятностей  необнаружения возникшей ошибки кратности m в анализируемых последовательностях . При этом численное значение указанных вероятностей, как и в случае одноканального анализатора, определяется выражениями:

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

Теорема. Множество ошибок последовательности  необнаруживаемых одноканальным СА, реализованном на основании примитивного полинома , старшая степень которого равна m, соответствует множеству необнаруживаемых ошибок n = 2d – канальным анализатором, (d – целое положительное число) при условии отсутствия ошибок в последовательностях .

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