Міністерство освіти і науки України Тернопільський національний технічний університет імені Івана Пулюя Кафедра комп’ютерних наук ЛАБОРАТОРНА РОБОТА №5 з дисципліни “Теорія алгоритмів” Тема роботи: Нерекурсивні алгоритми Лабораторна робота №5 Тема роботи: Нерекурсивні алгоритми. Мета роботи: Вивчення властивостей нерекурсивних алгоритмів та методів їх побудови на прикладі алгоритмів фільтрації сигналів. Теоретичні відомості Числові алгоритми, які використовуються для цифрової обробки сигналів поділяюьться на два типи: рекурсивні і нерекурсивні. Нерекурсивним називається алгоритм у якому відліки вихідного сигналу отримують на основi тільки відліків вхідного сигналу. У рекурсивних алгоритмах крім відліків вхідного сигналу використовуються також віліки вихідного сигналу у попередні моменти часу. Нерекурсивні алгоритми обробки сигналів являють собою згортку послідовності відліків вхідного сигналу з послідовністю заданих коефіцієнтів. Рівняння нерекурсивного алгоритму можна записати у вигляді:
, (1) де x-послідовність відліків вхідного сигналу; y-послідовність відліків вихідного сигналу; N – ціле число; ai , – коефіцієнти. Структурна схема нерекурсивного алгоритму: Між рекурсивними та нерекурсивними алгоритмами існує взаємозвязок. Можна показати, що якщо за коефіцієнти нарекурсивного алгоритму взяти відліки імпульсної функції відгуку рекурсивного алгоритму, то дія нерекурсивного алгоритму на вхідний сигнал буде наближатись до дії рекурсивного алгоритму, тобто передаточні функції алгоритмів будуть близькими між собою. Чим більше відліків імпульсної функції відгуку рекурсивного алгортиму взяти, тим кращим буде наближення. Імпульсна функцію відгуку являє собою обернене перетворення Фур’є (Лапласа) від передаточної функції (при цьому отримують аналітичний вигляд імпульсної функції відгуку). Фізичний зміст імпульсної функції відгуку полягає в тому що функція відгуку являє собою реакцію системи на (-імпульс, поданий на вхід системи. Тому, для отримання на практиці імпульсної функції відгуку дискретного алгоритму фільтрації необхідно на вхід подати послідовність відліків [1,0,0,…] (дискретний аналог (-імпульсу) і записати значення відліків вихідного сигналу. Фільтрацію сигналів проводять з допомогою згортки відліків сигналу з відліками отриманої функції відгуку. Завдання до лабораторної роботи. Для рекурсивного алгоритму, який описується заданою системою рівнянь (таблиця 1): Отримати імпульсну функцію відгуку; Скласти програму реалізації нерекурсивного алгоритму фільтраціі на основі отриманої імпульсної функції відгуку у якій: а. операції множення та сумування реалізувати у вигляді окремих підпрограм; b. забезпечипи підрахунок кількості викликів підпрограм множення та додавання. с. на вхід алгоритму подати послідрвність відліків синусоїди; Оформити звіт по виконаній роботі. Зміст звіту Звіт повинен містити: Завдвння до роботи. Структурну схему нерекурсивного алгоритму. Блок-схему програми. Текст програми. Результати роботи. Висновки. Контрольні запитання Опис алгоритму у вигляді різницевого рівняння, перехід від диферинціального рівняння до різницевого. Перетворення Фур’є, Лапласа, Z-перетворення. Перехід від часової до спектральної форми опису. Взаємозв’язок між рекурсивними та нерекурсивними алгоритмами. Імпульсна функція відгуку та методи її отримання. Рекомендована література Гоноровский И.С. Радиотехнические цепи и сигналы. М. Радио и связь. 1986. Баскаков С.И. Радиотехнические цепи и сигналы. М. Высшая школа. 1988. Бабак В.П. Хандецький В.С. Шрюфер Е. Обробка сигналів. К. Либідь 1996. Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М. Наука. 1989. Голд. Цыфровая обработка сигналов. Карташев В.Г. Основы теории дискретных сигналов и цифровых фильтров. М. Высшая школа. 1982. Варіанти завдань Варіант  Варіант   1 
6 
 2 
7 
 3 
8 
 4 
9 
 5 
10