Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз обчислювальної похибки при виконанні базових операцій алгоритмів ЦОСЗ. Обчислення математичних функцій. Швидкі алгоритми обчислення дискретних тригонометричних перетворень.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Проектування комп’ютерних засобів обробки сигналів та зображень
Частина тексту файла (без зображень, графіків і формул):
Лабораторні роботи №1-2
з дисципліни “Проектування комп’ютерних засобів обробки сигналів та зображень”
(2006/2007 н.р., Х семестр, модуль №1, гр. СКС, КСМ)
Максимальна кількість балів, при виконанні роботи в повному обсязі і вчасній здачі - 15 (ЛР№1 – 8 балів, ЛР№2 – 7 балів).
Термін здачі ЛР:
ЛР№1: 4 - навчальний тиждень;
ЛР№2: 7 - навчальний тиждень.
Лабораторна робота № 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)
Варіанти завдань наведені в таблиці
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора