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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для этого необходимо было решить следующие задачи:

Логическое моделирование цифровых схем.

Разработка моделирующего алгоритма построения ГПСЧ.

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

Оценка эффективности работы многоканального сигнатурного анализатора.

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

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

Моделирование логических схем на ЭВМ.

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

Логическая схема N считается структурно описанной, если указаны следующие её характеристики: внешние входы схемы - множество X = {x}; внешние выходы схемы - множество Z = {z}; элементы схемы - множество D = {d}; внутренние связи между элементами в виде матрицы связей C = {ci,j}, где ci,j{0,1}; ci,j=1 - если выход элемента di связан со входом элемента dj, для всех элементов d D.

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

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

Обратный схемный список - это описание схемы по выходам элементов. Для каждого элемента указывается его номер на схеме, тип и номер элементов, со входами которых соединён выход данного элемента.

Прямой и обратный схемный списки представляют собой компактное описание матрицы связей между элементами C = {ci,j}, причём для задания матрицы достаточно одного из них. Прямой схемный список может быть построен на основе обратного списка, и наоборот.

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

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

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

Методы анализа.

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

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

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

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

1.3. Описание тестовой диагностики.

Проблема тестового диагностирования цифровых схем возникает на различных этапах их производства и эксплуатации и включает взаимосвязанные задачи. Первая из них заключается в определении, в каком состоянии находится исследуемая схема.[3] Основным состоянием цифровых схем является исправное - это такое техническое состояние схемы, при котором она удовлетворяет всем требованиям, установленным технической документацией. В противном случае схема находится в одном из неисправных состояний.

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

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

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

Неисправности типа “короткое замыкание” (мостиковые неисправности) появляются при коротком замыкании входов и выходов логических элементов и подразделяются на два вида: неисправности, вызванные коротким замыканием входов логического элемента, и неисправности типа обратной связи.

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

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

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

Структурные блоки, на которые разбивается задача диагностики, приведены на рис. 1.1.

Рис.1.1. Основные функциональные блоки, используемые при тестировании цифровой схемы.

ГТВ – генератор тестовых воздействий (генератор М- последовательности)

ЦС – цифровая схема

МСА – многоканальный сигнатурный анализатор

Блок эталонных реакций - блок, хранящий сжатые выходные реакции

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

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

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

1.4. Принципы генерирования случайных и псевдослучайных последовательностей.

В задачах активных экспериментальных исследований современных сложных технических систем с применением статистических методов важное место принадлежит генерированию сигналов возбуждения.[4] Диктуется это не только необходимостью подачи на объект требуемого числа воздействий с заданными свойствами, но и максимальной скорости их выработки. Одним из наиболее распространённых в настоящее время методов формирования таких процессов является преобразование сигналов, получаемых с помощью так называемых генераторов белого шума (ГБШ). В применении к цифровым методам генерирования под белым шумом понимается последовательность некоррелированных чисел или цифр, распределённых, как правило, по равномерному закону.

Известны два основных метода получения цифрового белого шума: физический - генерирование случайных двоичных чисел с помощью специальных устройств - генераторов случайных чисел (ГСЧ); математический - формирование псевдослучайных числовых последовательностей (ПСЧП) по специальным программам или с использованием генераторов псевдослучайных чисел (ГПСЧ).

Принцип действия ГСЧ состоит в преобразовании случайного сигнала на выходе физического источника шума в импульсную последовательность с вероятностью появления импульса p(1)=0,5.

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

Указанные недостатки физических ГСЧ явились причиной всё более широкого распространения математических методов получения шумовых числовых последовательностей. Мгновенные значения таких псевдослучайных последовательностей в отличие от случайных в принципе могут быть предсказаны заранее. В то же время все оценки статистических характеристик конкретной реализации ПСЧП совпадают с оценками соответствующей ей случайной выборки. Любую статистическую характеристику псевдослучайной числовой последовательности можно получить, используя реализацию длиной в один период повторения ПСЧП. Для истинно случайной последовательности это потребовало бы бесконечно большую длину реализации. Искусственное увеличение периода ПС - сигнала неограниченно приближает его структуру к структуре одной из возможных реализаций истинно случайного процесса. Однако и при ограниченных величинах периода в определённых условиях псевдослучайные числовые последовательности могут заменить случайные. При анализе псевдослучайной реализации равной или меньшей длине периода вообще практически невозможно определить, является ли она отрезком регулярной или случайной последовательности. С другой стороны, если записать конкретную случайную реализацию на каком-либо носителе, и периодически воспроизводить её, то получим регулярную ПСЧП.

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

Работу генератора М-последовательности, сумматоры по модулю два которого включены в межразрядные связи, а порождающий полином равен M(x)= 11x2x2...mxm, можно описать выражением

AM(k)=VMAM(k-1),

где m-мерные вектора AM(k)=(a1M(k), a2M(k),..., amM(k)) и AM(k-1)= =(a1M(k-1), a2M(k-1),..., amM(k-1)) определяют состояния РС генератора в k-й и (k-1)-й такты работы соответственно, а матрица VM, описывающая структуру генератора, имеет вид:

 0 0 0 . . . 0 1

1 0 0 . . . 0 1

VM= 0 1 0 . . . 0 2

. . . . . . . .

0 0 0 . . . 1 m-1

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

1 2 m-1

 a1(k) a2(k)  a3(k)  am(k)

Рис.1.2. Генератор М - последовательности с сумматорами по модулю два,

стоящими в межразрядных связях регистра сдвига:

Можно показать [5], что между состояниями AM(k) и A(k) РС генераторов обоих типов при AM(0)= A(0)=1000...0 существует зависимость, определяемая соотношением:

a1M(k) m m-1 m-2 . . . 2 1 a1(k)

a2M(k) 0 m m-1 . . . 3 2 a2(k)

a3M(k) = 0 0 m . . . 4 3 a3(k)

. . . . . . . . . . . . . . . . . . . . .

amM(k) 0 0 0 . . . 0 0 am(k)

При этом, порождающий полином (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