Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Серіалізм та паралелізм у обчислювальних алгоритмах
Інформація про навчальний заклад
ВУЗ:
Тернопільський національний економічний університет
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №3
з дисципліни “Теорія алгоритмів”
Тема роботи: : Серіалізм та паралелізм у обчислювальних алгоритмах
Тема роботи: Серіалізм та паралелізм у обчислювальних алгоритмах.
Мета роботи: Вивчення серіалізму та паралелізму структури обчислювальних алгоритмів на прикладі алгоритмів фільтрації сигналів.
Теоретичні відомості
При використанні обчислювальних алгоритмів часто суттєвими є не тільки функція, яку він реалізує, але і структура алгоритму. Особливо актуальним є це питання для алгоритмів цифрової фільтрації сигналів, реалізованих на основі спеціалізованих сигнальних процесорів. У цьому випадку з структурою алгоритму пов’язані питання максимальної швидкості обробки, та засобів апаратної реалізації спецпроцера, а отже і його вартості.
При розробці алгоритмів цифрової фільтрації використовуються різні форми опису алгоритмів. Найбільш поширеними формами є:
Опис у вигляді різницевого рівняння
Загальний вигляд рівняння:
, (1)
де x-послідовність відліків вхідного сигналу;
y-послідовність відліків вихідного сигналу;
M, N – цілі числа ();
ai , bi – коефіцієнти.
Рівняння (1) містить в собі нерекурсивну частину (сума по N), і рекурсивну частину (сума по M). Алгоритм фільтрації, який описується рівнянням (1) називають рекурсивним а фільтр називають фільтром з нескінченою імпульсною характеристикою. Число М називають порядком рекурсивного фільтру. Якщо вихідний сигнал залежить тільки від вхідного сигналу, тобто , то алгоритм фільтрації називають нерекурсивним а фільтр - з скінченою імпульсною характеристикою. Число N називають порядком нерекурсивного фільтру. Очевидно, що такий алгоритм вимагає по N+1 комірок пам’яті для зберігання відліків вхідного сигналу і коефіцієнтів аі і M+1 комірок пам’яті для зберігання відліків вихідного сигналу коефіцієнтів bi.
2. Опис у вигляді структурної схеми
Позначення основних елементів алгоритму:
Елемент
Графічне позначення
Зауваження
Вузол
(комірка пам’яті)
Вузли можуть довільно нумеруватися. Може мати довільну кількість вихідних зв’язків і лише один вхідний.
Зв’язок (помножувач на константу)
Одиничний коефіцієнт на схемі не позначають.
Суматор
Може мати довільну кількість вхідних зв’язків і лише один вихідний.
Одинична затримка
Може мати один вхідний і один вихідний зв’язок.
Елементи на структурній схемі можуть з‘єднуватись послідовно і паралельно. Структурна схема нерекурсивного алгоритму має вигляд рис.1.а. По суті вона являє собою згортку n+1 послідовних відліків вхідного сигналу послідовністю коефіцієнтів а0-аn Структурна схема рекурсивного алгоритму має вигляд рис.1.б. Вона являє собою згортку m послідовних відліків вихідного сигналу з послідовністю коефіцієнтів b1-bm
Опис алгоритму у вигляді графа
Позначення основних елементів алгоритму на граф-схемі:
Елемент
Графічне позначення
Зауваження
Вузол
(комірка пам’яті)
Вузли можуть довільно нумеруватися, можуть мати довільну кількість вхідних і вихідних зв’язків. Всі вхідні зв’язки сумуються (аналог суматора на структурній схемі).
Звязок (помножувач на константу
Одиничний коефіцієнт на схемі не позначають.
Одинична затримка
При використанні структурних схем та графів вводять поняття вхідних і вихідних вузлів
Вхідним називається вузол у який не входить жоден зв’язок.
Вихідним називається вузол з якого не виходить жоден зв’язок.
Для переходу від різницевого рівняння до структурної або граф-схеми необхідно:
позначити вузли, які відповідають необхідним коміркам пам‘яті;
позначити необхідні ланки затримки та з‘єднати їх з відповіними вузлами;
провести всі інші необхідні зв‘язки використовуючи при потребі суматори та ставлячи відповідні помножувачі на коефіцієнти .
Опис алгоритму з допомогою системи рівнянь
Опис алгоритму системою рівнянь можна реалізувати, записавши у систему рівняння для усіх внутрішніх та вихідних рівнянь системи. У правій частині рівнянь системи будуть суми значень у внутрішніх та вхідних вузлах системи, помножені на задані коефіцієнти або на затримки.
Приклад опису рекурсивного алгоритму другого порядку
Різницеве рівняння:
Структурна і граф-схеми адгоритму представлені на рис. 1,2.
Рисункам 1,2 відповідає наступна система рівнянь:
Вигляд структурної схеми, графсхеми та системи рівнянь може бути різним для одного і того ж різницевого рівняння. Перехід від одної форми структурної схеми до іншої еквівалентний групуванню змінних у різницевому рівнянні системи з допомогою операцій з дужками. Такі самі маніпуляції можна проводити і над спектральною формою запису різницевого рівняння. Оскільки у спектральній формі рівняння прийме вигляд (при використанні Z-перетворення), то методом переходу від одної форми структурної схеми до іншої є модифікація запису передаточної функції фільтра .
Та особливість, що при різних змінах структури алгоритму зберігається його передаточна функція, використовується для отримання найкращого за певним критерієм (швидкодія алгоритму, мінімальна вртість апаратної реалізації,…) методу реалізації алгоритму у спеціалізованих процесорах. При цьому актуальним є питання можливості паралеьного або послідовного виконання операцій алгоритму (паралелізму та серіалізму) та мінімальної кількрсті комірок пам‘яті та виконуючих елементів спецпроцесора (помножувачів, суматорів), необхідних для реалізації алгоритму.
Завдання до лабораторн ої роботи.
Для алгоритму, який описується заданою системою рівнянь (табл.1.)
Побудувути структурну та граф-схеми алгоритму;
Записати різницеве рівняння алгоpитму в часовій і частотній області;
Скласти програму реалізації такого алгоритму на ЕОМ у якій:
а. операції множення та сумування реалізувати у вигляді окремих підпрограм;
b. на вхід алгоритму подати послідовність з 20 відліків синусоїди;
с. забезпечити підрахунок кількості викликів підпрограм множення та додавання.
Оформити звіт по виконаній роботі.
Зміст звіту
Звіт повинен містити:
Завдання до роботи.
Структурну та граф-схему алгоритму.
Блок-схему програми.
Текст програми.
Результати роботи.
Висновки.
Контрольні запитання
Опис алгоритму у вигляді різницевого рівняння, перехід від диферинціального рівняння до різницевого.
Перетворення Фур’є, Лапласа, Z-перетворення. Перехід від часової до спектральної форми опису.
Опис структури алгоритму у вигляді структурної схеми, граф-схеми, системи рівнянь.
Особливості реалізації алгоритмів на спеціалізованих ЕОМ. Серіалізм та паралелізм операцій у обчислювальних алгоритмах.
Рекомендована література
Гоноровский И.С. Радиотехнические цепи и сигналы. М. Радио и связь. 1986.
Баскаков С.И. Радиотехнические цепи и сигналы. М. Высшая школа. 1988.
Бабак В.П. Хандецький В.С. Шрюфер Е. Обробка сигналів. К. Либідь 1996.
Залманзон Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М. Наука. 1989.
Голд. Цыфровая обработка сигналов.
Цыфровая обработка сигналов.
Карташев В.Г. Основы теории дискретных сигналов и цифровых фильтров. М. Высшая школа. 1982.
Варіанти завдань
Варіант
Варіант
1
6
2
7
3
8
4
9
5
10
07.02.2013 19:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора