МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ імені Івана Пулюя Кафедра комп’ютерних наук ЛАБОРАТОРНА РОБОТА №5 з предмету Теорія алгоритмів та математичні основи представлення знань Тема: Нерекурсивні алгоритми. Тернопіль-2010 Лабораторна робота №5 Тема роботи: Нерекурсивні алгоритми. Мета роботи: Вивчення властивостей нерекурсивних алгоритмів та методів їх побудови на прикладі алгоритмів фільтрації сигналів. Теоретичні відомості Числові алгоритми, які використовуються для цифрової обробки сигналів поділяюьться на два типи: рекурсивні і нерекурсивні. Нерекурсивним називається алгоритм у якому відліки вихідного сигналу отримують на основi тільки відліків вхідного сигналу. У рекурсивних алгоритмах крім відліків вхідного сигналу використовуються також віліки вихідного сигналу у попередні моменти часу. Нерекурсивні алгоритми обробки сигналів являють собою згортку послідовності відліків вхідного сигналу з послідовністю заданих коефіцієнтів. Рівняння нерекурсивного алгоритму можна записати у вигляді:
, (1) де x-послідовність відліків вхідного сигналу; y-послідовність відліків вихідного сигналу; N – ціле число; ai , – коефіцієнти. Структурна схема нерекурсивного алгоритму: Між рекурсивними та нерекурсивними алгоритмами існує взаємозвязок. Можна показати, що якщо за коефіцієнти нарекурсивного алгоритму взяти відліки імпульсної функції відгуку рекурсивного алгоритму, то дія нерекурсивного алгоритму на вхідний сигнал буде наближатись до дії рекурсивного алгоритму, тобто передаточні функції алгоритмів будуть близькими між собою. Чим більше відліків імпульсної функції відгуку рекурсивного алгортиму взяти, тим кращим буде наближення. Імпульсна функцію відгуку являє собою обернене перетворення Фур’є (Лапласа) від передаточної функції (при цьому отримують аналітичний вигляд імпульсної функції відгуку). Фізичний зміст імпульсної функції відгуку полягає в тому що функція відгуку являє собою реакцію системи на (-імпульс, поданий на вхід системи. Тому, для отримання на практиці імпульсної функції відгуку дискретного алгоритму фільтрації необхідно на вхід подати послідовність відліків [1,0,0,…] (дискретний аналог (-імпульсу) і записати значення відліків вихідного сигналу. Фільтрацію сигналів проводять з допомогою згортки відліків сигналу з відліками отриманої функції відгуку. Завдання до лабораторної роботи. Для рекурсивного алгоритму, який описується заданою системою рівнянь
Отримати імпульсну функцію відгуку; Скласти програму реалізації нерекурсивного алгоритму фільтраціі на основі отриманої імпульсної функції відгуку у якій: а. операції множення та сумування реалізувати у вигляді окремих підпрограм; b. забезпечипи підрахунок кількості викликів підпрограм множення та додавання. с. на вхід алгоритму подати послідрвність відліків синусоїди; Структурна схема нерекурсивного алгоритму Блок-схема програми Текст програми unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series; type TForm1 = class(TForm) Button1: TButton; Chart1: TChart; Series1: TFastLineSeries; Button2: TButton; Label6: TLabel; Label7: TLabel; procedure Button1Click(Sender: TObject); function Mnog(m1:real; m2:extended): extended; function Dod(d1:extended; d2:extended): extended; procedure Button2Click(Sender: TObject); private { Private declarations } public { Public declarations } end; const n=20; var Form1: TForm1; k_dod, k_mnog:integer; i,s, d:integer; x2,x3,x5:real; x1:array[1..n] of real; a:array[0..n] of real; y:array[1..n] of real; x:array[1..n] of real; implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject); begin x1[1]:=1; for i:=2 to n do begin x1[i]:=0; end; x1[1]:=1; for i := 1 to n do begin x5:=a[i-1]*a[i]; a[i]:=x1[i-1]*12.3*x2+4*x3-x5; x3:=x2; x2:=-2*x3+11*x5+x1[i]; end; x[i]:=1; for i:=0 to n do begin y[i]:=Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Mnog(a[0],x[i]),Mnog(a[1],x[i+1])),Mnog(a[2],x[i+2])),Mnog(a[3],x[i+3])),Mnog(a[4],x[i+4])),Mnog(a[5],x[i+5])),Mnog(a[6],x[i+6])),Mnog(a[7],x[i+7])),Mnog(a[8],x[i+8])),Mnog(a[9],x[i+9])),Mnog(a[10],x[i+10])); end; Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod); Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog); series1.Clear; for i:=1 to n do begin Series1.Add(y[I]) ; end; end; procedure TForm1.Button2Click(Sender: TObject); begin close; end; function TForm1.Dod(d1:extended; d2:extended): extended; begin k_dod:= k_dod+1; Dod:=d1+d2; end; function TForm1.Mnog(m1:real; m2:extended):extended; begin k_mnog:= k_mnog+1; Mnog:=m1*m2; end; end. Результат роботи
Висновок: На цій лабораторні роботі я вивчив властивості нерекурсивних алгоритмів та методів їх побудови на прикладі алгоритмів фільтрації сигналів.