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

Роботу генератора М-послідовності, суматори за модулем два якого включені в міжрозрядні зв'язку, а породжує поліном дорівнює M (x) = 1 1x 2x2 ... 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) = xm M (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) = 1 1x1 2x2 ... 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)

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, якщо