Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз обчислювальної похибки при виконанні базових операцій алгоритмів ЦОСЗ. Обчислення математичних функцій. Швидкі алгоритми обчислення дискретних тригонометричних перетворень.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Проектування комп’ютерних засобів обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Лабораторні роботи №1-3
з дисципліни “Проектування комп’ютерних засобів обробки сигналів та зображень”
(2005/2006 н.р., Х семестр, модуль №1, гр. СКС-5, КСМ-5)
Максимальна кількість балів - 20 (ЛР№1 – 7 балів, ЛР№2 – 6 балів, ЛР№3 – 7балів).
На виконання кожної роботи надається 4 год.
Термін здачі ЛР (для отримання балів):
ЛР№1: 20.02 - 25.02;
ЛР№2: 06.03 – 11.03;
ЛР№3: 20.03 – 25.03
Лабораторна робота № 1
Аналіз обчислювальної похибки при виконанні базових операцій алгоритмів ЦОСЗ.
Обчислення математичних функцій.
Мета роботи: Дослідити шляхи виникнення обчислювальної похибки та її вплив на точність обчислень. Проаналізувати величину похибки при обчисленні деяких математичних функцій.
Загальні відомості.
При реалізації обчислень на процесорах обробки сигналів чи НВІС, які характеризуються обмеженою розрядністю і роботою в форматі фіксованої крапки необхідно враховувати ефекти, які викликані, насамперед, наближеним представленням формули обчислень і кінцевою розрядністю використовуваних регістрів. До таких ефектів відносяться:
а) шум аналогово-цифрового перетворення;
б) некорельований шум заокруглення;
в) похибки, які викликані квантуванням коефіцієнтів.
Враховуючи методи представлення чисел, способи квантування, які використовуються для скорочення розрядності чисел до необхідної величини, а також особливості структурної схеми обчислень, в кожному конкретному випадку можна оцінити, як перераховані ефекти впливають на результат обчислень.
Квантування в цифрових пристроях.
При квантуванні використовують два стандартних способи: відкидання і заокруглення. Розглянемо їх особливості стосовно різних систем числення і похибки, які виникають при цьому. Припускається, що всі значення чисел по модулю менші від 1.0 (|X| < 1.0).
Відкидання. Відкидуються всі молодші розряди, що стоять після найменшого розряду, який зберігається. Тоді значення похибки для додаткового коду задовільняє нерівність:
-2 -b Xвдк - X 0,
де b - число розрядів, що зберігаються; Xвдк - відкинуте значення X.
Для чисел, які представлені в прямому і оберненому кодах для від’ємних значень справедлива нерівність:
0 Xвдк - X < 2-b , X < 0.
Hайважливіше, що похибка відкидання лежить між значеннями нуля і числа, що пропорційне 2-b .
Заокруглення. При заокругленні вихідне число X заміняється найближчим до нього b-розрядним числом. Тоді похибка заокруглення задовільняє нерівність:
-2-b / 2 Xок - X 2-b / 2
для всіх трьох методів представлення чисел (додаткового, прямого і оберненого коду).
Шум аналогово-цифрового перетворення.
В залежності від методу квантування вхідної послідовності шум квантування може мати різний амплітудний розподіл.
При найменшому кроці квантування Q похибка квантування e(n) лежить в границях:
-Q/2 e(n) Q/2 - для випадку заокруглення;
0 e(n) Q - для випадку відкидання;
а розподіл сигналу похибки є рівномірним. При цьому середнє значення похибки дорівнюватиме нулю при заокругленні і Q/2 при відкиданні, а її дисперсія в обидвох випадках дорівнюватиме Q 2/12. Як аналогію аналогово-цифрового перетворення в нашому випадку необхідно розглядати представлення вхідного (тестового) масиву чисел в заданій розрядній сітці b, тоді Q дорівнюватиме b.
Hекорельований шум заокруглення.
В цифровій обробці використовуються операції множення, додавання і зсуву. Їх виконання приводить до необхідності розширення розрядної сітки. Hаприклад, перемноження двох b-розрядних чисел приводить до 2b-розрядного результату, подальше перемноження може привести до безкінцевого збільшення розрядної сітки. Для подолання ефекту застосовують квантування результатів множення до вихідної b-розрядної сітки з заокругленням або відкиданням молодших розрядів. При цьому виникає шум заокруглення.
При додаванні в загальному випадку розширення розрядної сітки не виникає, але в деяких випадках може виникнути переповнення. Для подолання цього ефекту застосовують зсув результатів вправо і його квантування. Для квантування результатів множення і додавання застосовують заокруглення або відкидання, в залежності від вимог реалізації. Похибки, що виникають при цьому будуть мати випадковий характер.
Квантування коефіцієнтів.
Постійні коефіцієнти, які використовуються при обчисленні базових операцій алгоритмів ЦОСЗ також представляються у фіксованому розрядному просторі. Загального підходу до їх квантування нема, тому застосовується така оптимизація, щоб максимум взваженої різниці ідеальних і реальних обчисленнь був мінімальним. При цьому необхідно розглянути схему обчисленнь стосовно чутливості до розрядності коефіцієнтів. Для цього, необхідно, змінюючи спосіб квантування коефіцієнтів (відкидання, заокруглення), добитися найменшого розходження між ідеальною і розрахованою функцією.
Базові операціїі алгоритмів ЦОСЗ.
До основних базових операцій, які застосовуються в ЦОСЗ відносяться: множення, додавання і зсув. Оскільки, при виконанні цих операцій необхідно залишитися в заданій розрядній сітці розглянемо прийоми їх моделювання на мові Pascal.
Розрядна сітка: b = 8.
Множення.
x, k, y - 8-ми розрядні слова зі знаком;
work - 16-ти розрядне словo зі знаком;
work := k * x; { множення }
work := work + $80; {моделювання заокруглення }
y := work shr 8; { квантування до 8-ми розрядів }
Додавання.
x, k, y - 8-ми розрядні слова зі знаком;
work - 16-ти розрядне словo зі знаком;
work := k + x; {сумування}
work := work + 1; { моделювання заокруглення }
y := work shr 1; { квантування до 8-ми розрядів }
Порядок виконання роботи.
1. Записати в аналітичному вигляді формулу математичної функції, що є оптимальною за складністю обчислень.
2. Розробити схему обчисленнь, блок схему виконання алгоритму, для режиму з фіксованою крапкою, враховуючи спосіб реалізації (ПОС, НВІС). Рекомендується враховувати 3-5 членів ряду.
3. Проаналізувати можливі шляхи виникнення похибок обчислень, методи їх подолання.
4. Створити тестову послідовність для досліджуваної функції і провести розрахунок еталонного зразку в режимі з рухомою крапкою на довільній мові програмування.
5. Провести обчислення математичної функції в режимі з фіксованою крапкою в бітовому просторі 8, 16 біт на довільній мові програмування для вибраної кількості членів ряду (див.п.2)..
6. Провести порівняння результатів отриманих в п.4 і п.5 і пояснити причину їх розбіжності.
Вимоги до оформлення звіту з ЛР:
Титульний аркуш.
Завдання на лабораторну роботу.
Теоретичний матеріал стосовно поставленого завдання.
Блок - схема виконання алгоритму (схема обчислень).
Лістинг програми на довільній мові програмування.
Результати роботи – у відповідності з табл.1 і графіки абсолютної () і відносної () похибки.
Висновки
Таблиця 1 – Результати роботи:
Примітка:
1. Абсолютна похибка визначається як EMBED Equation.3 , де Fe – значення досліджуваної функції з рухомою крапкою, Fpi – значення досліджуваної функції з фіксованою крапкою для відповідних бітових просторів.
2. Відносна похибка визначається як = (/Fе)*100%.
Література
1. Е.Шрюфер. Обробка сигналів. Цифрова обробка дискретизованих сигналів.-К.:Либідь, 1992.-296 с.
2. Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.-М.:Мир, 1978.-848 с.
3. Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ.- К.: Наукова думка, 1984 –600 с.
4. Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
(варіанти завдань)
Лабораторна робота № 2
Швидкі алгоритми обчислення дискретних тригонометричних перетворень
Мета роботи. Дослідити швидкі алгоритми дискретних тригонометричних перетворень і порівняти їх з алгоритмами безпосереднього обчислення тpигонометpних перетворень.
Теоретичні відомості
Алгоритми швидкого перетворення Фур’є (ШПФ) можуть бути отримані за допомогою послідовного застосування операції розкладу одномірного масиву вхідних відліків сигналу на двохмірний. Ця операція здійснена тільки у випадку, коли N (довжина послідовності) є складним числом (N = N1 · N2 · ... · Nj). Якщо N просте, його неможливо розкласти на прості співмножники; для такої послідовності алгоритмів ШПФ не існує. В більшості практичних випадків вхідну послідовність штучно продовжують додаванням нульових відліків до отримання N як складного числа.
Для характеристики розкладу використовують поняття “основа”, якщо всі співмножники однакові (N1 = N2 = ... = Nj) і “розщеплена основа”, якщо співмножники неоднакові.
Приклад. N = 64 = 2 · 2 · 2 · 2 · 2 · 2 - основа 2.
N = 64 = 4 · 4 · 4 - основа 4.
N = 128 = 2 · 4 · 4 · 4 - розщеплена основа 2-4.
Дискретне перетворення Фур’є
Дискретне перетворення Фур’є (ДПФ) кінцевої послідовності {x(n)}, 0 n N-1 визначається як
EMBED Equation.2 , k = 0, 1, ..., N-1 (1)
де EMBED Equation.2 .
Суть алгоритмів ШПФ в тому, що якщо N складне число і є степенем двійки (N=2m), то вихідна послідовність розбивається на дві коротші послідовності, ДПФ яких можуть бути скомбіновані таким чином, щоб утворилось ДПФ вихідної послідовності.
Методика побудови алгоритмів ШПФ наступна. Введемо дві (N/2) - точкові послідовності {x1(n)} і {x2(n)} з парних і непарних членів x(n) відповідно, x1(n) = x(2n) і x2(n) = x(2n + 1), n = 0, 1, ..., N/2-1. Тоді формулу розкладу можна записати так:
EMBED Equation.2
де X1(k) і X2(k) є N/2 - точкові ДПФ парних і непарних відліків вихідної послідовності.
Застосовуючи цю формулу розкладу X1(k) і X2(k) до пори, поки X1(k) і X2(k) не стануть двохточковим ДПФ, отримаємо алгоритм ШПФ з прорідженням в часі.
Для отримання іншої розповсюдженої форми алгоритмів ШПФ вихідну послідовність розбивають на дві (N/2) - точкові послідовності таким чином: перша складається з перших N/2 відліків, а друга з решти, x1(n) = x(n) і x2(n) = x(n + N/2), n = 0, 1, ..., N/2-1.
При такому розбитті N - точкове ДПФ можна записати так
EMBED Equation.2
де X1(k) і X2(k) є N/2 - точкові ДПФ першої та другої половини відліків вихідної послідовності.
Алгоритми ШПФ, що отримані з застосуванням цієї методики називаються алгоритмами з прорідженням по частоті.
Порядок виконання роботи
1. Застосовуючи методики розкладу, отримати алгоритм обчислення заданого перетворення за певними “основою” і розмірністю.
2. Скласти процедуру на мові високого рівня для безпосереднього (прямого) обчислення тригонометричного перетворення.
3. Скласти процедуру на мові високого рівня для обчислення швидкого перетворення по алгоритму отриманому в п.1.
4. Виміряти часи виконання процедур п.2 і п.3.
5. Порівняти часи виконання процедур п.2 і п.3, і пояснити отримані результати.
Вимоги до оформлення звіту з ЛР:
1. Титульний аркуш.
2. Завдання на лабораторну роботу.
3. Теоретичний матеріал стосовно поставленого завдання.
4. Граф-алгоритм виконання ШПФ.
5. Лістинги програми на мові програмування високого рівня.
6. Часи виконання процедур п.2 і п.3 “Порядку виконання роботи”.
7. Висновки
Література
1. Е.Шрюфер. Обробка сигналів. Цифрова обробка дискретизованих сигналів.-К.:Либідь, 1992.-296 с.
2. И.З.Гоноровский. Радиотехнические цепи и сигналы.-М.:Радио и связь, 1986.- 512с.
3. Радиотехнические цепи и сигналы. Примеры и задачи. Учебное пособие для вузов/Под ред. И.З.Гоноровского.-М.:Радио и связь, 1989.-248 с.
Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.-М.:Мир, 1978.-848 з.
+5. Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Завдання до лабораторної роботи № 2.
Розробити процедуру дискретного тригонометричного перетворення вхідної послідовності x(n), розмірності N використовуючи алгоритм Algorithm. Формулу розкладу отримати за методом Кулі-Тьюкі. Algorithm : ШПФкі (швидке перетворення Фур’є за основою і) з прорідженням за часом (Т) чи частотою (F).
x(n) = EMBED Equation.2 ; n = 0, 1, ..., N-1. (1)
x(n) = EMBED Equation.2 ; n = 0, 1, ..., N-1. (2)
Варіанти завдань наведені в таблиці
Лабораторна робота № 3
Діагностика роботи цифрових фільтрів шляхом аналізу їх амплітудно-частотної характеристики
Мета роботи. Дослідити параметри амплітудно-частотної характеристики та вплив віконної обробки при спектральному аналізі сигналів.
Теоретичні відомості
Для адекватного відтворення вхідного сигналу, що використовується в системах обробки, які розв’язують задачі спектрального аналізу сигналів, опис вхідного діагностичного сигналу представляється у формалізованому вигляді. Зазначені задачі розв’язуються цифровими методами, на основі швидких дискретних ортогональних перетворень, що представляються узагальненим класом швидких перетворень Фур'є з різними системами базисних функцій. Дані перетворення відносяться до класу лінійних ортогональних перетворень, зв'язаних з обчисленням виразів виду
EMBED Equation.2 ,
де Х = [Х(0), Х(1), ... , Х(L-1)]Т , х = [х(0), х(1), ... , х(L-1)]Т - вектори, відповідно, вихідних гармонік і початкових відліків, А - відтворююча ортогональна матриця розміром L x L, L- кількість початкових відліків.
Системи, які реалізують ці алгоритми відносяться до стаціонарних систем з частотним коефіцієнтом передачі K(j):
EMBED Equation.2
де h(t) - імпульсна характеристика, що має таку інтерпретацію: якщо на вхід системи поступає гармонійний сигнал з відомою частотою і комплексною амплітудою EMBED Equation.3 , то комплексна амплітуда вихідного сигналу EMBED Equation.3 буде рівною:
EMBED Equation.3 EMBED Equation.2 (1)
Представлення частотного коефіцієнта передачі (див. формулу 1) в показниковій формі має вигляд :
EMBED Equation.2 ,
де EMBED Equation.2 - амплітудно-частотна характеристика (АЧХ). Оскільки для фільтрів з скінченою імпульсною характеристикою АЧХ є однією з визначальних характеристик, на основі її аналізу визначається достовірність побудови фільтра. Розглянемо варіант перевірки фільтра методом аналізу його АЧХ на прикладі системи опрацювання інформації когерентно-імпульсної РЛС з n каналами погоджених фільтрів. Для процесора, що виконує N-точкове амплітудне дискретне перетворення Фур’є згідно з формулою (2)
EMBED Equation.2 , (2)
де N визначає розмір перетворення, n-номер елемента віддалі, l – номер гармоніки, i-номер періоду повторення в межах інтервалу обчислення ДПФ, W(i) вагова функція, вхідний сигнал EMBED Equation.2 представимо у вигляді:
EMBED Equation.2 , (3)
де А - амплітуда сигналу, S - кількість частотних діапазонів між сусідніми l, Q – визначає смугу перевірки АЧХ ( EMBED Equation.2 , де m, p - кількість гармонік, в діапазоні яких (відносно l) перевіряється АЧХ, EMBED Equation.2 , EMBED Equation.2 , si – біжуче значення частотного діапазону між сусідніми l).
Процедура діагностики відбувається таким чином. Для процесора задається значення гармоніки lj. На інформаційні входи поступає вхідний сигнал EMBED Equation.2 . Зміна значень EMBED Equation.2 (синфазна і квадратурна складові) на вході процесора відбувається на кожному періоді повторення (по і). Одне значення EMBED Equation.2 визначається сумуванням по і (див.формулу 2). Після того змінюється частота поступлення EMBED Equation.2 , зміна задається значенням EMBED Equation.2 , і вираховується наступне значення EMBED Equation.2 . Повна АЧХ, для заданого lj, отримується після поступлення на вхід S*N значень вхідного сигналу. На практиці обмежуються перевіркою АЧХ для 3l, відносно lj. Після перевірки амплітудно-частотних характеристик для всіх гармонік і елементів віддалі процес діагностики завершується. В ідеальному випадку характеристики всіх АЧХ повинні бути ідентичними.
Тобто, при використанні такого підходу процес перевірки розбивається на три етапи:
- задання значень для отримання числової послідовності вхідних сигналів;
- визначення значень Y(n,l) реальної АЧХ;
- порівняння значень ідеальної і реальної АЧХ в кожній точці виміру.
Застосування підходу дозволяє:
- виявити помилки в роботі з точністю до функціонального вузла, наприклад помилки в заданні вагової функції, при сумуванні, в ОЗП проміжних результатів, при пересиланні інформації між процесорами, конструктивні та технологічні помилки при проектуванні цифрових вузлів і т.п.;
- проводити діагностику в режимі реального часу;
- перевірити правильність функціювання і рівень шумів зовнішніх пристроїв, наприклад, приймача проміжної частоти;
- оцінити вплив різних типів вагових функцій на значення вихідного сигналу;
- перевірити в РРЧ значення інформації, що поступає на вхід системи опрацювання шляхом її запису в ОЗП;
- перевірити точностні параметри роботи процесорів;
- перевірити реакцію фільтра на поступлення збійної інформації.
Найвживаніші вагові функції, що використовуються при обробці наведені в таблиці 1.
Таблиця 1
Примітка: Значення w(n) таблиці 1 відповідає значенню W(i) (див. формулу 2).
Алгоритм формування вхідних даних для формування АЧХ полягають у видачі на кожному етапі обчислень синусоїдальної і косинусоїдальної складової комплексного сигналу, фаза яких відрізняється на значення Q на двох сусідніх періодах, на кожному з яких обчислюється одне значення U (i)
Порядок виконання роботи
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Налаштувати фільтр на виконання заданого варіанту - сформувати масив синусоїдальної і косинусоїдальної складової згідно з виразом:
Сформувати вхідний масив (синусоїдальна і косинусоїдальна складові) згідно з формулою 3.
Сформувати масив вагової функції
Скласти процедуру на мові високого рівня для обчислення АЧХ згідно з формулою 2.
Скласти процедуру графічного виводу значень АЧХ: без вагової функції та з ваговою функцією.
Порівняти значення АЧХ, пояснити отримані результати.
Примітка: Передбачити можливість зміни в програмі всіх вхідних параметрів і констант.
Вимоги до оформлення звіту до лабораторної роботи
Титульний аркуш.
Завдання на лабораторну роботу.
Теоретичний матеріал.
Лістінг підпрограми і результати формування вхідного масиву (таблиця або графік).
Лістінг підпрограми і результати формування масиву вагової функції (таблиця або графік).
Лістінг програми і результати формування АЧХ (таблиця і графік) для двох випадків: без вагової функції та з ваговою функцією.
Висновки.
Література
1. Е.Шрюфер. Обробка сигналів. Цифрова обробка дискретизованих сигналів.-К.:Либідь, 1992.-296 с.
2. И.З.Гоноровский. Радиотехнические цепи и сигналы.-М.:Радио и связь, 1986.- 512с.
Радиотехнические цепи и сигналы. Примеры и задачи. Учебное пособие для вузов/Под ред. И.З.Гоноровского.-М.:Радио и связь, 1989.-248 с.
Л.Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов.-М.:Мир, 1978.-848 з.
Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства. Учебное пособие для вузов. 2-е изд. – Х.: Конус, 2001.- 398 с.
Варіанти завдань до лабораторної роботи № 3
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора