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