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

Вступ

Широке поширення радіоелектронних пристроїв із застосуванням цифрової обробки сигналів обумовлює підвищений інтерес до питань діагностування їх технічного стану.

Однією з різновидів діагностування цифрових вузлів і блоків є тестове діагностування, застосування якого на етапі проектування і виготовлення цифрових вузлів дозволяє визначити правильність їх функціонування та здійснити процедуру пошуку несправностей. При розробці тестової діагностики виникає складність у визначенні еталонних реакцій при тестуванні існуючих схем, у визначенні оптимального числа контрольних точок для зняття вихідний реакції діагностується цифрової схеми. Це можна зробити або створюючи прототип розробляється цифрового пристрою і проводячи його діагностику апаратурними методами, або здійснюючи моделювання на ЕОМ як цифрового пристрою, так і процесу діагностики. Найбільш раціональним є другий підхід, який передбачає створення автоматизованих систем діагностики [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) = 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 (< img src = "http://localhost/uploads/posts/2009-10/1255893819_Cifrovaya_obrabotka_signalov_166.gif" alt = "" width = "9" height = "19" />)... 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