UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika  1. stopnja Patrik Mikuº

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika 1. stopnja

Patrik Mikuº

Uporaba diskretne val£ne transformacije pri analizi telemetri£nih podatkov

Delo diplomskega seminarja Mentor: doc. dr. Jan Gro²elj

Ljubljana, 2022

Kazalo

1. Uvod 4

2. Osnovna ideja diskretne val£ne transformacije 5

2.1. Dviºni korak 6

3. Laurentovi polinomi 8

3.1. Denicija in lastnosti 8

3.2. Kolobar polinomov in matrik 10

3.3. Deljenje Laurentovih polinomov 11

3.4. Evklidov algoritem za Laurentove polinome 12

4. Algebrai£na predstavitev diskretne val£ne transformacije 14

4.1. Z-transformacija 14

4.2. Operatorja vzor£enja 15

4.3. Pogoj popolne rekonstrukcije 16

4.4. Polifazna predstavitev Laurentovih polinomov 18 4.5. Polifazna predstavitev pogoja popolne rekonstrukcije 19

5. Faktorizacija polifazne matrike 22

5.1. Dvig 23

5.2. Izrek o faktorizaciji polifazne matrike 25

6. Uporaba diskretne val£ne transformacije 29

6.1. Izpeljava D4 val£ka 29

6.2. Grupiranje 32

Slovar strokovnih izrazov 37

Literatura 37

Uporaba diskretne val£ne transformacije pri analizi telemetri£nih podatkov

Povzetek

V delu je predstavljena diskretna val£na transformacija in njena uporaba pri analizi podatkov. Transformacija zaporedje podatkov z uporabo ltrov razdeli na dva dela, pri £emer se ohrani en del, drugi del pa je potreben le pri rekonstrukciji zaporedja.

Ta postopek je opisan z Laurentovimi polinomi in Evklidovim algoritmom za La- urentove polinome. Vpeljan je pogoj popolne rekonstrukcije, ki zagotavlja, da je transformacija obrnljiv postopek. Predstavljen je v matri£ni obliki z uvedbo polifa- znih komponent in polifaznih matrik ltrov. Na koncu je predstavljen ²e konkreten primer uporabe diskretne val£ne transformacije na primeru grupiranja telemetri£nih podatkov.

Use of discrete wavelet transform in telemetry data analysis Abstract

In this thesis, the denition of discrete wavelet transform as well as its use in the data analysis eld is presented. The transform works in a way that, with the use of lters, it divides a sequence of data into two parts: one part is kept for later use and the other, the second part, is used for reconstruction purposes only. This procedure is described by Laurent polynomials and Euclidean algorithm for Laurent polynomials.

Furthermore the condition of perfect reconstruction, which ensures that the discrete wavelet transform is a reversible process, is introduced. The condition is represented in a matrix form, with the introduction of polyphase representation and polyphase matrix of lters. Finally, the use of discrete wavelet transform is demonstrated on an actual example of clustering of telemetry data.

Math. Subj. Class. (2020): 65T60

Klju£ne besede: diskretna val£na transformacija, Laurentovi polinomi, Evklidov algoritem, pogoj popolne rekonstrukcije, polifazna predstavitev, grupiranje

Keywords: discrete wavelet transform, Laurent polynomials, Euclidean algorithm, perfect reconstruction condition, polyphase representation, clustering

1. Uvod

V zadnjih letih smo pri£a skokovitemu napredku razvoja tehnologije zajemanja in posredovanja podatkov razli£nih meritev. V preteklosti so se meritve ve£inoma opravljale ro£no, zaradi £esar so se meritve od£itavale bolj poredko. Dandanes se je proces zajemanja podatkov meritev avtomatiziral, prav tako pa se je avtomatiziralo tudi po²iljanje podatkov na poljubno oddaljeno lokacijo. Tako pridobljene podatke imenujemo telemetri£ni podatki. Primeri telemetri£nih podatkov so recimo vremen- ski podatki, ki jih izmerimo v vremenski postaji, poraba in proizvodnja energentov kot recimo elektrika in zemeljski plin, primer iz medicine pa je lahko frekvenca srca pri bolniku. Tovrstne meritve hranimo v obliki £asovnih vrst, kar pomeni, da so

£asovno indeksirane in razporejene. Tak²ni obliki pravimo tudi signal.

Denicija 1.1. Indeksirano zaporedje realnih ²tevil (x_k)k∈Z imenujemo signal. Si- gnal je kon£en, £e je le kon£no mnogo £lenov zaporedja razli£nih od 0.

Signal je torej urejen nabor ve£ med seboj na£eloma neodvisnih podatkov. V smislu telemetri£nih podatkov pa razumemo signal le kot en podatek. ’e en primer signala je cena delnice na borzi. Obi£ajno bi nas zanimala le trenutna cena, v smislu telemetri£nega podatka pa nas zanima ²e celotna zgodovina, torej nabor vseh preteklih cen v to£no dolo£enem in urejenem vrstnem redu. Pri predstavitvi telemtri£nih podatkov najpogosteje uporabimo odsekoma linearni grakon, saj je obi£ajno bolj pregleden kot to£kovni grakon. Primer signala, ki predstavlja porabo elektri£ne energije, predstavlja slika 1. V primeru matemati£ne analize podatkov bi radi £im bolje spoznali £asovno obna²anje takih podatkov, torej dinamiko signala, ter predvideli njihovo dogajanje.

Na hitro bi lahko rekli, da nas tako predstavljen primer signala spominja na graf realne funkcije, £eprav gre v resnici za diskretno. Pri numeri£ni analizi zveznih re- alnih funkcij se najpogosteje uporabljata Fourierova in val£na transformacija. Pri obeh transformacijah funkcijo razvijemo v vrsto tako, da je funkcija predstavljena s sistemom funkcij, pri £emer spremenimo domeno signala, kar nam omogo£a ana- liziranje funkcije v druga£ni obliki. Pri Fourierjevi transformaciji so te funkcije izbrane tako, da funkcijo preslikajo iz £asovne domene v frekven£no domeno, kar lahko doseºemo s funkcijama sin (ωt)incos (ωt), pri £emer ω predstavlja frekven£no spremenljivko. Pri val£ni transformaciji pa ºelimo funkcijo preslikati iz £asovne do- mene v £asovnofrekven£no domeno. Preprost primer funkcije, ki se uporablja pri val£ni transformaciji in ga lahko najdemo v [3], je

ψ(t) =

⎧

⎪⎨

⎪⎩

1, t∈[0,¹₂),

−1, t∈[¹₂,1], 0, sicer. S pomo£jo te funkcije konstruiramo sistem funkcij

{︃

ψ_u,s= 1

√sψ

(︃t−u s

)︃

; u, s∈R }︃

.

Tak²en sistem funkcij se izkaºe kot primeren za zvezno obliko val£ne transforma- cije. Zaradi £asovnofrekven£ne domene nam val£na transformacija omogo£a bolj natan£no analizo lokalnega obna²anja funkcije. Cilj obeh transformacij se je ome- jiti na kon£no mnoºico sistema funkcij in pri tem dobiti £im bolj²o aproksimacijo za£etne funkcije. Obe transformaciji imata tudi diskretno obliko. Pri tem vlogo

Slika 1. Gra£ni primer signala. Podatki za signal so pridobljeni iz [6].

realne funkcije prevzame zaporedje (ali signal), ki ga razdelimo na ve£ podzaporedij (ali podsignalov), od katerega jih del zavrºemo, preostali pa tvorijo diskretno obliko transformacije.

V diplomski nalogi bomo predstavili diskretni primer val£ne transformacije s po- mo£jo dviºnih korakov, pri £emer bomo sledili viru [2]. Najprej bomo predstavili osnovno idejo diskretne val£ne transformacije in dviºnih korakov, v nadaljevanju pa bo sledilo nekaj teorije Laurentovih polinomov. Sledila bo algebrai£na predstavitev diskretne val£ne transformacije in povezava med Laurentovimi polinomi in signali.

S pomo£jo Laurentovih polinomov bomo spoznali ltre, s katerimi delujemo na si- gnalih, in pogoj popolne rekonstrukcije, ki zagotavlja obrnljivost diskretne val£ne transformacije. Vpeljali bomo pojma polifaznih komponent in polifaznih matrik, ki poenostavita pogoj popolne rekonstrukcije. Sledil bo izrek o dvigu, ki sluºi kot orodje pri konstrukciji zahtevnej²ih ltrov, teoreti£ni del pa bomo zaklju£ili z izre- kom o faktorizaciji polifazne matrike na dviºne korake. Na koncu si bomo ogledali ²e primer uporabe diskretne val£ne transformacije pri metodi grupiranja in primerjali dobljene rezultate z uporabo razli£nih ltrov.

2. Osnovna ideja diskretne val£ne transformacije

Pri diskretni val£ni transformaciji signal razdelimo na dva dela, obi£ajno kar na sodi in lihi del, in s tem, v trivialnem primeru, dobimo dva nova signala s in d. Pri tem signal s imenujemo signal reduciranih vrednosti in ga po transformaciji ohra- nimo in uporabljamo dalje. Signaldimenujemo signal ostankov in ga v nadaljevanju

x

s

d

Slika 2. Shema enonivojske diskretne val£ne transformacije.

x

s₁

d₁

s₂

d₂

s₃

d₃

Slika 3. Shema trinivojske diskretne val£ne transformacije.

ne uporabljamo ali prikazujemo. Sluºi nam le kot pomo£ pri rekonstrukciji za£etnega signala, v kolikor se za to odlo£imo. Z diskretno val£no transformacijo torej ohra- nimo le polovico za£etnega signala. Tak²no transformacijo imenujemo enonivojska diskretna val£na transformacija, kar je shemati£no prikazano na sliki 2.

Idejo diskretne val£ne transformacije lahko ponovimo na signalu reduciranih vre- dnosti in tako pridemo iz enonivojske diskretne val£ne transformacije na ve£nivojsko.

Shemo trinivojske diskretne val£ne transformacije prikazuje slika 3.

2.1. Dviºni korak. Glavno vpra²anje je, kako lahko konstruiramo nova, ne trivi- alna, signalasind. Osnovna ideja je, da za£nemo s signalomx, ki ga torej razdelimo na dva nova signala. Izhajamo iz predpostavke, da signal predstavlja neko zvezno realno funkcijo, ki jo opazujemo le v kon£no mnogo diskretnih, enako oddaljenih to£kah. Deniramo sodi del signalax_e = (x_2k)k∈Zin lihi del signala x_o = (x_2k+1)k∈Z. V primeru, ko je razdalja med to£kami dovolj majhna, bosta signala x_e in x_o kore- lirana in s pomo£jo teh dveh signalov lahko konstruiramo kon£na signala ostankov in reduciranih vrednosti, ki ju bomo spoznali v nadaljevanju.

Sedaj dolo£imo prvi operator, s katerim bomo delovali na signalu. Imenujemo ga prediktor in ga ozna£imo s P. Prediktor uporabimo na sodih vrednostih signala.

Razliko med lihim delom signala in vrednostmi sodega dela po uporabi prediktorja ozna£imo z d in dobimo

d=xo−P(xe).

x razdelimo x_e

x_o

P

−

U

−

d s

Slika 4. Osnovna ideja diskretne val£ne transformacije.

s

U

d

+

+ P

x_o x_e

zdruºimo x

Slika 5. Inverz osnovne ideje diskretne val£ne transformacije.

šelimo, da ima signal razlik majhne vrednosti, torej da z uporabo prediktorja na sodem delu signala £im bolje aproksimiramo lihi del signala. S tem ko dolo£imo prediktor in ga uporabimo na signalu, re£emo, da smo naredili en dviºni korak.

Dobljeni signal bo v osnovni ideji ºe predstavljal kon£ni signal razlik. Sedaj imamo na voljo sodi del signala x_e in signal razlik d. Ponovno izberemo operator, ki ga tokrat imenujmo korektor in ga ozna£imo z U. Korektor uporabimo na signalu razlik in dobljene vrednosti od²tejemo od sodega dela signala ter tako dobimo

s=x_e−U(d).

S tem smo naredili ²e en dviºni korak in dobili ravno kon£ni signal reduciranih vrednosti. Z uporabo prediktorja in korektorja smo tako za£etni signal preoblikovali do kon£nih signalov. Shema opisanega postopka z dvema dviºnima korakoma je prikazana na sliki 4.

Najpomembnej²a lastnost opisanega postopka je obrnljivost, torej lastnost, da lahko iz predpostavke, da poznamo kon£na signala s ind ter operatorja, ki sta bila uporabljena pri transformaciji, vedno rekonstruiramo signala x_e inx_o in posledi£no za£etni signal x. To lahko preverimo tako, da iz izrazov za signal reduciranih vre- dnosti s in signal ostankov d izrazimo x_e in x_o ter tako dobimo

x_e =s+U(d), xo =P(xe) +d.

Dobljena signala za konec le ²e ustrezno zdruºimo, da spet dobimo za£etni signal.

Shemo postopka rekonstrukcije signala x prikazuje slika 5.

(a) Originalen signal (b) Signal reduciranih vre-

dnosti (c) Signal ostankov

Slika 6. Primer originalnega signala, signala reduciranih vrednosti in signala ostankov pri uporabi Haarovega val£ka.

Najbolj znan primer diskretne val£ne transformacije je tako imenovana Haarova val£na transformacija ali kraj²e Haarov val£ek. Kako dolo£imo tovrstna elementarna operatorja, torej prediktor in korektor, bomo natan£neje pojasnili v poglavjih 4 in 5, zaenkrat pa kar kot znano privzemimo operatorja, ki sta podana v naslednjem zgledu.

Zgled 2.1. V primeru Haarovega val£ka za prediktor P izberemo kar identiteto, za korektor U pa identiteto, pomnoºeno s koecientom −¹₂. Tako lahko dobimo eksplicitni zapis za signal ostankov in signal reduciranih vrednosti

d =x_o−x_e, s =x_e+1

2d.

Za tako izbrana operatorja P in U signal ostankov predstavlja ravno razliko med lihimi in sodimi £leni. Signal reduciranih vrednosti je potem kar sodi del signala, popravljen s polovi£no vrednostjo signala razlik. Prepoznamo, da je to ravno signal povpre£nih vrednosti med sodimi in lihimi £leni signala x. V nadaljevanju bomo spoznali, kako smo dolo£ili tako izbrana operatorjaP inU ter zakaj ustrezata ravno

Haarovemu val£ku. ♢

Operacije na signalih izvajamo po £lenih. To pomeni, da pri se²tevanju se²tejemo

£lena z istim indeksom, pri mnoºenju s konstanto pa vsakega izmed £lenov pomno- ºimo s konstanto. Primer uporabe Haarovega val£ka na signalu prikazuje slika 6.

Slika 6a prikazuje originalen signal, 6b pa signal reduciranih vrednosti, torej signal, ki ga ohranimo in uporabljamo v nadaljevanju. Slika 6c prikazuje signal ostankov, ki ga obi£ajno ne shranjujemo, razen v primeru, ko se odlo£imo za rekonstrukcijo.

3. Laurentovi polinomi

3.1. Denicija in lastnosti. Pri predstavitvi ltrov, ki jih bomo spoznali v po- glavju 4 in jih uporabljamo pri predstavitvi val£ne transformacije, si pomagamo z znanjem Laurentovih polinomov. Uporabna je predvsem njihova algebrska struk- tura.

Denicija 3.1. Laurentov polinom a :R→Rdeniramo s koecientia_i ∈R, i∈Z, pri £emer velja, da je le kon£no mnogo koecientova_i razli£nih od0. Tako deniran Laurentov polinom pi²emo kot

a(z) = ∑︂

i∈Z

a_izⁱ.

Opomba 3.2. V nadaljevanju bomo zaradi priro£nosti in nedvoumnosti pisali La- urentov polinom a skupaj z argumentom z v oblikia(z).

Tudi Laurentovemu polinomu lahko, tako kot obi£ajnemu polinomu, dolo£imo stopnjo. V primeru ni£elnega Laurentovega polinoma a(z) ≡ 0 je stopnja kar 0. Sicer pa lahko najdemo tak²na indeksa k in l, za katera velja, da je k najmanj²i indeks, za katerega je a_k ̸= 0, l pa najve£ji indeks, za katerega je a_l ̸= 0. Stopnjo polinoma a(z) potem deniramo kot

dega(z) = max

i∈Z

{i | a_i ̸= 0} −min

i∈Z

{i |a_i ̸= 0}=l−k.

Oglejmo si sedaj nekaj lastnosti, zna£ilnih za Laurentove polinome in njihovo algebrsko strukturo. Najprej si poglejmo trditev v povezavi s sodimi in lihimi Lau- rentovimi polinomi.

Trditev 3.3. Naj bo a(z) Laurentov polinom ter b(z) =∑︂

i∈Z

a2iz²ⁱ, c(z) = ∑︂

i∈Z

a2i+1z²ⁱ⁺¹.

Laurentov polinom b(z) imenujemo sodi Laurentov polinom, c(z) pa lihi Laurentov polinom Laurentovega polinoma a(z). Zanju velja

b(z) = a(z) +a(−z)

2 , c(z) = a(z)−a(−z)

2 .

Poleg tega velja ²e a(z) = b(z) +c(z). Laurentov polinom je torej vsota svojega sodega in lihega Laurentovega polinoma.

Dokaz. Naj bo a(z) =a_kz^k+· · ·+a_lz^l. Oglejmo si polinom

a(−z) = (−1)^ka_kz^k+ (−1)^k+1a_k+1z^k+1+· · ·+ (−1)^l−1al−1z^l−1+ (−1)^la_lz^l. Laurentova polinomaa(z)ina(−z)imata enako predzna£ene sode £lene in nasprotno predzna£ene lihe. Ko ju se²tejemo, se lihi £leni ravno od²tejejo, sodi £leni pa se²tejejo in tako dobimo

2·(a2nz²ⁿ+a2(n+1)z²⁽ⁿ⁺¹⁾+· · ·+a2(m−1)z^2(m−1)+a2mz^2m),

za ustrezna n, m∈Z. Po deljenju z2 dobimo ravno sodi Laurentov polinom b(z). V drugem primeru pa od Laurentovega polinoma a(z) od²tejemo a(−z). Pri od²tevanju se od²tejejo ravno enako predzna£eni koecienti in tako dobimo

2·(a_2n+1z²ⁿ⁺¹+a_2n+3z²ⁿ⁺³+· · ·+a2m−1z^2m−1+a_2m+1z^2m+1),

spet za ustrezna n, m ∈ N. Delimo z 2 in vidimo, da smo dobili lihi Laurentov polinom c(z).

Razmislimo ²e o vsoti sodega in lihega Lauretovega polinoma. Upo²tevamo zvezi, ki smo ju pravkar dokazali, in tako dobimo

b(z) +c(z) = a(z) +a(−z) +a(z)−a(−z)

2 =a(z).

Vidimo, da je Laurentov polinom a(z) res vsota svojega sodega in lihega dela. □

3.2. Kolobar polinomov in matrik. V smislu raz²iritve kolobarjev si lahko mno- ºico Laurentovih polinomov predstavljamo kot kolobar realnih polinomov R[z], raz-

²irjen z elementom z⁻¹. Tako dobimo mnoºico R[z, z⁻¹]. Naslednji izrek nam pove, da je tudi ta mnoºica kolobar.

Izrek 3.4. Mnoºica realnih Laurentovih polinomovR[z, z⁻¹]tvori komutativen kolo- bar za operaciji se²tevanje, ki je denirano s se²tevanjem koecientov pri isti potenci, in mnoºenje, denirano z diskretno konvolucijo koecientov.

Dokaz. Dokazati je treba zaprtost, komutativnost in asociativnost se²tevanja in mnoºenja, obstoj enote ter distributivnostni zakon.

Laurentove polinome se²tevamo kot obi£ajne polinome, torej komutativnost in asociativnost sledita iz komutativnosti in asociativnosti se²tevanja realnih ²tevil.

Prav tako kot pri obi£ajnih polinomih tudi pri Laurentovih deniramo mnoºenje kot konvolucijo. Naj bosta a(z) = a_kz^k +· · ·+a_nzⁿ in b(z) = b_lz^l +· · ·+b_mz^m Laurentova polinoma, pri £emer so k, l, n, m ∈ Z in a_i, b_j ∈ R za ustrezne indekse i, j. Produkt Laurentovih polinomov a(z) inb(z)je deniran kot

a(z)b(z) =

n+m

∑︂

i=k+l

⎛

⎜

⎝

∑︂

s,t∈Z s+t=i

a_sb_t

⎞

⎟

⎠zⁱ.

Pri tem seveda velja, da je a_s = 0, kadar indeks s ni v mnoºici indeksov {k, k+ 1, . . . , n}, inbt= 0, kadar indekstni v mnoºici indeksov {l, l+ 1, . . . , m}. Komuta- tivnost in asociativnost produkta tako tudi sledi iz komutativnosti, asociativnosti in distributivnosti se²tevanja in mnoºenja v realnih ²tevilih. Distributivnost se²tevanja in mnoºenja lahko rutinsko preverimo z razpisovanjem £lenov v konvoluciji tako, da pi²emo a_s = f_s+g_s za neka Laurentova polinoma f(z) in g(z), pri £emer f_s in g_s ozna£ujeta koecienta pri £lenu z^s. Enota mnoºenja je enaka kot pri kolobarju na- vadnih polinomov, in sicer je to konstanten polinom e(z) = 1. Sledi, da je mnoºica realnih Laurentovih polinomov komutativen kolobar. □ Oglejmo si ²e enkrat rezultat produkta dveh Laurentovih polinomov iz dokaza izreka 3.4. Iz zapisa produkta vidimo, da je najmanj²i indeks enak k+l, najve£ji pa n+m. Stopnja produkta je potem enaka

(n+m)−(k+l) = (n−k) + (m−l),

kar je ravno enako vsoti stopenj Laurentovih polinomov. Za tako denirano mnoºe- nje znotraj kolobarja R[z, z⁻¹] velja naslednja posledica o stopnji produkta.

Posledica 3.5. Naj bosta a(z) in b(z) Laurentova polinoma. Potem velja dega(z)b(z) = dega(z) + degb(z).

Naslednje, kar nas zanima, so obrnljivi elementi kolobarja Laurentovih polinomov.

Po posledici 3.5 je stopnja produkta enaka vsoti stopenj. Naj bo a(z) obrnljiv Laurentov polinom in b(z) njegov inverz, torej je njun produkt enak 1, stopnja enote pa je 0. Ker je stopnja polinoma naravno ²tevilo ali pa 0, je po posledici 3.5 edina moºnost, da sta stopnji a(z)in b(z) enaki 0. Obrnljivi elementi kolobarja Laurentovih polinomov so torej ravno monomi, to so Laurentovi polinomi oblike

a(z) =akz^k, ak ∈R\{0}, k ∈Z.

Omeniti velja tudi kolobar matrik Laurentovih polinomov. Uporabljali bomo le 2×2 matrike, zato se omejimo na matrike oblike

M(z) =

[︃a(z) b(z) c(z) d(z) ]︃

.

Kolobar obrnljivih matrik Laurentovih polinomov ozna£imo z GL(2,R[z, z⁻¹]). Se- veda velja, da je matrika obrnljiva natanko tedaj, ko je njena determinanta obrnljiva, torej ko je detM(z) =a(z)d(z)−b(z)c(z) monom. Kolobar matrik z determinanto 1 standardno ozna£imo SL(2,R[z, z⁻¹]).

3.3. Deljenje Laurentovih polinomov. Za za£etek si poglejmo osnovni izrek o deljenju za Laurentove polinome.

Izrek 3.6. Naj bosta a(z), b(z) ∈ R[z, z⁻¹], b(z) ̸= 0, Laurentova polinoma in naj velja, da je stopnja a(z) ve£ja ali enaka stopnji b(z). Potem obstajata Laurentova polinoma q(z), r(z)∈R[z, z⁻¹], da velja:

a(z) = b(z)q(z) +r(z),

kjer je degr(z)<degb(z) in degq(z) = dega(z)−degb(z).

Dokaz. Naj bo dega(z) = n in degb(z) = m. Oba Laurentova polinoma lahko pomnoºimo s koecientoma z^a inz^b, pri £emer sta a, b∈Z, da doseºemo, da je naj- manj²i koecient obeh polinomov z⁰. (To pomeni, da sta sedaja(z)inb(z)navadna polinoma). Dobljena polinoma delimo kot realne polinome in dobimo kvocient q(z) ter ostanek r(z). V tem primeru se polinoma a(z) in b(z)q(z) ujemata v najvi²jih n−m+ 1potencah in ostanekr(z)je stopnjem−1. Kvocient in ostanek moramo na koncu ²e pomnoºiti z z^b−a, da dobimo spet Laurantova polinoma, ki smo ju iskali.

Oglejmo si ²e primer, ko se a(z) in b(z)q(z) ujemajo v vseh £lenih. Tedaj je ostanek r(z) enak 0 in polinom a(z) je razcepen, razcep pa tvorita faktorja b(z) in

q(z). □

Pri konstrukciji polinoma q(z) v dokazu izreka 3.6 smo izbrali tak Laurentov polinom, da se a(z) in b(z)q(z) ujemata v £lenih z najvi²jimi potencami. Seveda to ni nujno, saj bi lahko izbrali recimo najniºje potence. Da to doseºemo, moramo le druga£e zapisati realna polinoma pri deljenju. Ena moºnost je, da polinoma pri deljenju zapi²emo od najniºje proti najvi²ji potenci namesto obratno. Tako bi dobili druga£en kvocient q(z) in posledi£no tudi druga£en ostanek r(z). Od tu sklepamo, da deljenje znotraj kolobarja Laurentovih polinomov ni nujno enoli£no dolo£eno. O tem se lahko prepri£amo z naslednjim zgledom.

Zgled 3.7. Naj bosta a(z) = z⁻¹+ 2 +z in b(z) = z⁻¹−1 Laurentova polinoma.

I²£emo Laurentov polinomq(z), da se bo produktb(z)q(z)ujemal za(z)v vsaj dveh

£lenih. To lahko doseºemo na razli£ne na£ine:

z⁻¹+ 2 +z = (1−z)(z⁻¹−1) + 4, z⁻¹+ 2 +z = (1 + 3z)(z⁻¹−1) + 4z, z⁻¹+ 2 +z = (−3−z)(z⁻¹−1) + 4z⁻¹.

Vidimo, da smo v vsakem primeru dobili druga£en kvocient q(z) in posledi£no tudi druga£en ostanek r(z). Od tu lahko sklepamo, da deljenje znotraj kolobarja Lau-

rentovih polinomov res ni enoli£no dolo£eno. ♢

Poglejmo si ²e primer, pri katerem dobimo ostanek enak 0.

Zgled 3.8. Naj bosta tokrat a(z) = z⁻¹ + 2 +z in b(z) = z⁻¹ + 1 Laurentova polinoma. V tem primeru dobimo:

z⁻¹+ 2 +z = (1 +z)(z⁻¹+ 1) + 0.

Ker je ostanek enak 0, se deljenje izide in Laurentov polinoma(z) je razcepen. ♢ V [1] je podana naslednja denicija evklidskih kolobarjev.

Denicija 3.9. Cel kolobar K se imenuje evklidski kolobar, £e obstaja preslikava δ :K\{0} →N∪ {0} z naslednjima lastnostima:

• Za poljuben par elementov a, b ∈ K, kjer b ̸= 0, obstajata taka elementa q, r ∈K, da je a=qb+r in je r= 0 ali pa jeδ(r)< δ(b).

• δ(a)≤δ(ab) za vse a, b∈K\{0}.

Pravimo, da je kolobar cel, £e je komutativen in nima deliteljev ni£a. Za kolobar Laurentovih polinomov smo ºe v izreku 3.4 navedli, da je komutativen. ƒe bi kolobar imel delitelje ni£a, bi po posledici 3.5, moral biti delitelj ni£a stopnje 0. Torej oblike akz^k, pri £emer je ak ∈ R in k ∈ Z. To pa ni mogo£e, saj realna ²tevila nimajo deliteljev ni£a. Torej je kolobar realnih Laurentovih polinomov cel.

ƒe nam uspe najti ²e ustrezno preslikavo δz lastnostmi, opisanimi v deniciji 3.9, bo sledilo, da je kolobar Laurentovih polinomov evklidski, in lahko bomo denirali deljenje Laurentovih polinomov. Izkaºe se, da je tak²na preslikava δ kar stopnja polinoma, torej δ(a(z)) = dega(z). Kot smo ºe razmislili pri stopnji produkta pri posledici 3.5, je takδres ustrezen. Torej je kolobar Laurentovih polinomov evklidski kolobar.

3.4. Evklidov algoritem za Laurentove polinome. Za kolobar celih ²tevil po- znamo u£inkovit algoritem, ki nam pomaga najti najve£ji skupni delitelj dveh celih

²tevil. To je Evklidov algoritem, ki ga lahko ustrezno preoblikujemo in uporabljamo tudi znotraj kolobarja Laurentovih polinomov. V3. poglavju v [5] je najprej znotraj izreka 3.1 predstavljeno deljenje Laurentovih polinomov, v nadaljevanju pa sledi ²e celoten razmislek kako pridemo do Evklidovega algoritma, ki ga predstavlja naslednji izrek.

Izrek 3.10. Naj bosta a(z)in b(z)̸= 0 realna Laurentova polinoma, za katera velja degb(z) ≤ dega(z). Naj bo a₀(z) = a(z) in b₀(z) = b(z) ter naj bodo q_i(z), i = 1,2, . . . Laurentovi polinomi, ki jih dobimo v Evklidovemu algoritmu:

ai(z) = bi−1(z),

b_i(z) = r_i(z) = ai−1(z)−bi−1(z)q_i(z), i= 1,2, . . . , n,

pri deljenju a_i(z) z b_i(z). Potem obstaja tako naravno ²tevilo n, da je b_n(z) = 0, Laurentov polinom a_n(z) pa je najve£ji skupni delitelj Laurentovih polinomov a(z) in b(z), ki ga standardno ozna£imo z gcd(a(z), b(z)).

V vsakem koraku velja degb_i+1(z) < degb_i(z) in ker je stopnja polinoma na- ravno ²tevilo ali pa 0, se bo iteracija gotovo zaklju£ila. Naj bo degb_m(z) = 0 in predpostavimo, da na vsakem koraku izberemo tak kvocient qi(z), da bo veljalo degbi+1(z)−degbi(z) = 1. Potem bo ²tevilo korakovn enakon=m+ 1, pri tem pa je mravno stopnja polinoma b(z). Torej velja ocena, ki jo podaja naslednja trditev.

Trditev 3.11. Naj bo n ²tevilo korakov, ki jih izvedemo pri Evklidovem algoritmu za Laurentova polinoma a(z) in b(z). Tedaj velja ocena:

n ≤degb(z) + 1.

Razcep, ki smo ga dobili po izteku Evklidovega algoritma, lahko priro£no zapi²emo v eni izmed dveh ekvivalentnih matri£nih oblik. Prva oblika je

(1) [︃a_n(z)

0 ]︃

=

[︃0 1

1 −q_n(z) ]︃

· · ·

[︃0 1

1 −q₁(z) ]︃ [︃

a(z) b(z) ]︃

=

n

∏︂

i=1

(︃[︃0 1

1 −q_n−i+1(z) ]︃)︃ [︃

a(z) b(z) ]︃

. Prepri£ajmo se v njeno veljavnost. Razmislimo najprej, da to velja v primeru, ko izvedemo le en korak Evklidovega algoritma. Tedaj dobimo

[︃0 1

1 −q₀(z) ]︃ [︃

a₀(z) b₀(z) ]︃

=

[︃ b₀(z)

a₀(z)−q₀(z)b₀(z) ]︃

=

[︃a₁(z) b₁(z) ]︃

Zadnja enakost velja po deniciji oznak znotraj Evklidovega algoritma. Ko tak²en postopek ponovimo n-krat, dobimo po zadnjem mnoºenju ravno

[︃a_n(z) b_n(z) ]︃

=

[︃a_n(z) 0

]︃

,

kar potrjuje zvezo (1). Matrike, s katerimi mnoºimo v (1), so obrnljive z inverzom [︃0 1

1 −qi

]︃−1

=

[︃q_i 1 1 0 ]︃

.

Po kon£nem ²tevilu mnoºenj ena£be (1) z leve z inverzi matrik dobimo ekvivalentno obliko matri£nega zapisa

(2)

[︃a(z) b(z) ]︃

=

[︃q₁(z) 1

1 0

]︃

· · ·

[︃q_n(z) 1

1 0

]︃ [︃

a_n(z) 0

]︃

=

n

∏︂

i=1

(︃[︃q_i(z) 1

1 0

]︃)︃ [︃

a_n(z) 0

]︃

. Opomba 3.12. Z zapisom produkta si bomo le skraj²ali zapis mnoºenja matrik. ’e vedno razumemo, da pri uporabi matrike na signalu ra£unamo od desne proti levi, torej da na vektorju uporabimo najprej matriko pri indeksu i = n in kot zadnjo matriko pri indeksu i= 1.

Oglejmo si enostaven primer Evklidovega algoritma na Laurentovih polinomih in matri£ni zapis rezultata.

Zgled 3.13. Naj bosta spet a(z) = a₀(z) = z⁻¹ + 2 +z in b(z) = b₀(z) = z⁻¹+ 1 Laurentova polinoma. Iz zgleda 3.7 ºe vemo:

a₁(z) =z⁻¹−1, b₁(z) = 4, q₁(z) = 1−z.

’e enkrat ponovimo deljenje in dobimo:

a₂(z) = 4, b₂(z) = 0, q₂(z) = 1

4z⁻¹−1 4. Po izteku algoritma vidimo, da je gcd(a(z), b(z)) =a₂(z) = 4.

Dobljeno faktorizacijo predstavimo ²e v oblikah (1) in (2):

[︃4 0 ]︃

=

[︃0 1

1 −¹₄z⁻¹+¹₄ ]︃ [︃

0 1

1 −1 +z ]︃ [︃

z⁻¹+ 2 +z z⁻¹+ 1

]︃

, [︃z⁻¹+ 2 +z

z⁻¹+ 1 ]︃

=

[︃1−z 1

1 0

]︃ [︃₁

4z⁻¹−¹₄ 1

1 0

]︃ [︃

4 0 ]︃

.

Analogno lahko ponovimo Evklidov algoritem za ostala moºna deljenja in pridemo

do podobnih rezultatov. ♢

4. Algebrai£na predstavitev diskretne val£ne transformacije Teorijo Laurentovih polinomov bi radi povezali s signali in operatorji, ki se upora- bljajo pri diskretni val£ni transformaciji. Videli bomo, da si lahko signale in operacije na njih laºje predstavljamo, £e jih predstavimo z Laurentovimi polinomi.

4.1. Z-transformacija. Najprej spoznajmo pojem ltra, s katerim delujemo na signalih.

Denicija 4.1. Filter h je linearen £asovno invarianten operator, ki deluje na si- gnalu in je enoli£no dolo£en s sliko signala h(x) = (h_k)_k∈Z, h_k ∈ R, pri £emer za signal izberemo x = (x_k)k∈Z, kjer je x₀ = 1 in x_k = 0 za k ̸= 0 in ga imenujemo impulz. Za lter h pravimo, da je kon£en, £e je le kon£no mnogo £lenovh_k razli£nih od 0.

Naslednja trditev nam predstavi ²e delovanje ltra na splo²nem signalu x. Trditev 4.2. Naj bo x = (xk)k∈Z signal in h = (hk)k∈Z lter. Naj bo x˜ = (x˜k)k∈Z

signal, ki ga dobimo po uporabi ltra h na signalu x. Tedaj velja x˜_k = ∑︂

i,j∈Z i+j=k

h_ix_j.

Prepoznamo ravno diskretno konvolucijo ltra h in signala x.

Dokaz. Dokaz sledi iz denicije ltra kot linearnega, £asovno invariantnega opera- torja. Naj bo yⁱ = (yⁱ_k)k∈Z impulz, ki ima y_kⁱ = 1 za k = i in yⁱ_k = 0 sicer, pri

£emer jei∈Z. Impulzy⁰ predstavlja ravno impulz iz denicije 4.1. Zaradi £asovne invariantnosti je denicija ltra neodvisna od izbire impulza yⁱ in velja

h(yⁱ) = (hk−i)k∈Z.

Signal x = (xk)k∈Z lahko zapi²emo kot vsoto impulzov yⁱ = (yⁱ_k). Tako dobimo zapis signala x kot

x=∑︂

k∈Z

x_ky^k.

Ko uporabimo lterh na signalu xin upo²tevamo linearnost ltra h, dobimo ravno x

˜_k=∑︂

i∈Z

x_ih(yⁱ) = ∑︂

i∈Z

h_k−ix_i = ∑︂

i,j∈Z i+j=k

h_ix_j.

Dobimo diskretno konvolucijo, ki smo jo ºeleli dokazati. □ Delovanje ltra na signalu nas spominja na mnoºenje Laurentovih polinomov zno- traj kolobarja R[z, z⁻¹], kot smo videli v dokazu izreka 3.4. Od tu se nam porodi ideja, da bi povezali idejo ltrov in signalov z algebrai£no strukturo Laurentovih polinomov. To idejo formaliziramo z naslednjo denicijo Z-transformacije.

Denicija 4.3. Z-transformacija je preslikava, ki kon£nemu signalu x = (xk)k∈Z

priredi Laurentov polinom x(z). Deniramo jo kot:

Z :x↦→x(z) =∑︂

k∈Z

x_kz^−k.

Pri tem razumemo, da je x_k = 0 za tiste indekse k, ki se ne pojavljajo v kon£nem signalu x

S pomo£jo Z-transformacije lahko signalu x priredimo Laurentov polinom x(z), ltru h pa priredimo Laurentov polinom h(z). V trditvi 4.2 smo videli, da pri uporabi ltra na signalu uporabljamo diskretno konvolucijo. V dokazu izreka 3.4 pa smo premislili, da se tudi pri mnoºenju Laurentovih polinomov pojavlja diskretna konvolucija. Uporaba ltra na signalu se torej po uporabi Z-transformacije pretvori na mnoºenje dveh Laurentovih polinomov. Ko torej lter h uporabimo na signalu x, dobimo signal x˜, ki pripada Laurentovemu polinomu x˜(z) =h(z)x(z).

Opomba 4.4. Ker si lahko kon£ne ltre razlagamo kot Laurentove polinome, bomo ta dva pojma ena£ili. Zaradi uskladitve oznak bomo ltre pisali kot h, pripadajo£e Laurentove polinome pa koth(z). Podobno signaluxpredpi²emo Laurentov polinom x(z).

4.2. Operatorja vzor£enja. V podrazdelku 4.1, smo spoznali ltre, s katerimi delujemo na signalih. Sedaj pa spoznajmo ²e pomembna operatorja, ki delujeta na signalih in imata klju£no vlogo pri diskretni val£ni transformaciji.

Denicija 4.5. Operator podvzor£enja (↓ 2) je operator, ki signal x = (x_n)n∈Z

preslika v signal (↓ 2)x = (y_n)n∈Z s komponentami y_n = x_2n. Operator nadvzor-

£enja (↑ 2) je operator, ki signal x = (x_n)n∈Z preslika v signal (↑ 2)x = (y_n)n∈Z s komponentami

y_n=

{︄x_k, n = 2k, k∈Z, 0, n = 2k+ 1, k ∈Z. S skupnim izrazom ju imenujemo operatorja vzor£enja.

Operator podvzor£enja nam vrne le vrednosti signala pri sodih indeksih, ostale pa zanemari. Operator nadvzor£enja pa za razliko od operatorja podvzor£enja dodaja vmesne vrednosti. Ko ga uporabimo na signalu, nam med vsaki dve vrednosti vrine vrednost 0.

Ker operator podvzor£enja izpusti vrednosti pri lihih indeksih, ne more imeti inverza. Nasprotno pa je operator podvzor£enja ravno levi inverz operatorja nadv- zor£enja. Vse ni£elne vrednosti, ki jih operator nadvzor£enja doda, bo operator podvzor£enja spet odvzel. Tak²en razmislek nam poda zvezo (↓ 2)(↑ 2)x = x, pri

£emer jex signal. Ko pa najprej uporabimo operator podvzor£enja in nato operator nadvzor£enja, nam podvzor£enje vrne samo signal vrednosti pri sodih indeksih si- gnalax, nadvzor£enje pa na lihe indekse vrine ni£elne elemente. Torej lahko re£emo, da(↑2)(↓2)vrne signal, v katerem lihe indekse nadomestimo z0. To je ravno sodi del signala.

Trditev 4.6. Naj bosta v = (↓ 2)x in u = (↑ 2)v = (↑ 2)(↓ 2)x signala, ki ju priredimo signalu x. Potem sta Z-transformaciji signalov v in u podani z

v(z) = 1

2(x(z¹²) +x(−z¹²)), u(z) =v(z²) = 1

2(x(z) +x(−z)).

Dokaz. Oglejmo si najprej uporabo podvzor£enja na signalu x. Naj bo v = (↓ 2)x. Po deniciji so vrednosti signala v enake vrednostnim signala x pri sodih indeksih.

Po trditvi 3.3 lahko sodi del Laurentovega polinoma x(z), kateremu pripada signal x, zapi²emo kot b(z) = ^x(z)+x(−z)₂ , torej je v(z²) = b(z). Pri tem smo uporabili

x(z)

h˜(z⁻¹)

g

˜(z⁻¹)

↓2

↓2

s(z)

d(z)

↑2

↑2

h(z)

g(z)

+ x˜(z)

Slika 7. Splo²na ideja val£ne transformacije. Prvi del slike prikazuje val£no transformacijo, predstavljeno s parom analiti£nih ltrov (h˜, g˜). Drugi del prikazuje inverzno val£no transformacijo ali rekonstrukcijo signala, predstavljeno s parom sinteti£nih ltrov (h, g).

argument z², saj tako doseºemo, da so vrednosti pri koecientih z lihimi potencami enake 0. Uvedemo substitucijoz² ↦→z in tako dobimo

v(z) = b(z¹²) = x(z¹²) +x(−z¹²)

2 .

Razmislimo ²e, kako izgleda Laurentov polinom za u= (↑ 2)(↓2)x. Vemo ºe, da je signaluenak signalux, pri £emer lihe vrednosti nadomestimo z0, sode pa ohranimo.

To pa je ravno sodi del signala x. Torej velja u(z) = x(z) +x(−z)

2 .

Dobili smo ravno Laurentova polinoma, ki smo ju ºeleli. □ 4.3. Pogoj popolne rekonstrukcije. Oglejmo si, kako lahko predstavimo diskre- tno val£no transformacijo s pomo£jo operatorjev vzor£enja in ltrov. Val£no trans- formacijo standardno predstavimo z dvema paroma ltrov in sicer analiti£nim parom (h˜, g˜)in sinteti£nim parom (h, g). Slika 7 prikazuje standardno val£no transformacijo in rekonstrukcijo za£etnega signala.

Signal x predstavimo z Laurentovim polinomom x(z) in na njem uporabimo l- ter, dolo£en z Laurentovim polinomom h˜(z⁻¹), in nato ²e operator podvzor£enja, s

£imer dobimo Laurentov polinom s(z), ki predstavlja signal reduciranih vrednosti.

Podobno naredimo v spodnji veji: na signalu x uporabimo lter, dolo£en z Lau- rentovim polinomom g˜(z⁻¹), in operator podvzor£enja, s £imer dobimo Laurentov polinom d(z), ki predstavlja signal ostankov.

Drugi del slike 7 prikazuje rekonstrukcijo signala oziroma inverzno val£no transfor- macijo. Na Laurentovemu polinomus(z)uporabimo najprej operator nadvzor£enja, nato pa ²e lter, ki ga dolo£a Laurentov polinom h(z). Analogno na Laurentovemu polinomu d(z) uporabimo operator nadvzor£enja in lter, dolo£en z g(z). Dobljena signala na koncu zdruºimo (se²tejemo) in tako dobimo obnovljeni signal, ki ga ozna-

£imo z x˜. V splo²nem signala x in x˜ nista nujno enaka, zato ºelimo izpeljati zvezo med ltri h, g, h˜, g˜, da bo veljala enakost za£etnega in kon£nega signala.

Trditev 4.7. Za£etni signal je enak kon£nemu signalu natanko tedaj, ko za ltre h, g, h˜, g˜ velja pogoj popolne rekonstrukcije

h(z)h˜(z⁻¹) +g(z)g˜(z⁻¹) = 2, h(z)h˜(−z⁻¹) +g(z)g˜(−z⁻¹) = 0.

(3)

Dokaz. Oglejmo si, kaj dobimo po uporabi obeh ltrov in operatorjev vzor£enja na obeh vejah sheme na sliki 7. Z mnoºenjem Laurentovih polinomov in uporabo operatorjev kot v trditvi 4.6 dobimo

h(z)(↑2)(↓2)h˜(z⁻¹)x(z) = 1

2(h(z)h˜(z⁻¹)x(z) +h(z)h˜(−z⁻¹)x(−z)), g(z)(↑2)(↓2)g˜(z⁻¹)x(z) = 1

2(g(z)g˜(z⁻¹)x(z) +g(z)g˜(−z⁻¹)x(−z)).

Zaradi jasnosti in enostavnosti zapisa uvedemo oznaki A(z) = h(z)h˜(z⁻¹) +g(z)g˜(z⁻¹), B(z) = h(z)h˜(−z⁻¹) +g(z)g˜(−z⁻¹).

Se²tejemo oba signala in izpostavimo x(z) inx(−z)ter tako dobimo x˜(z) = 1

2(A(z)x(z) +B(z)x(−z)). (4)

šelimo, da je kon£ni signal enak za£etnemu, torej da velja x˜(z) = x(z) za vsak signalx. Dovolj je preveriti za sodi in lihi Laurentov polinom, torej le za Laurentova polinoma x1(z) = 1 inx2(z) =z ter tako dobimo sistem dveh ena£b z neznankama A(z) inB(z). Upo²tevamo x₁(z) =x₁(−z) inx₂(z) = −x₂(z) in tako dobimo

A(z) +B(z) = 2, A(z)−B(z) = 2.

Re²itev sistema je ravno A(z) = 2 in B(z) = 0. Vidimo, da je to ravno pogoj popolne rekonstrukcije, ki smo ga ºeleli dokazati.

Premislimo ²e, da izrek velja tudi v drugo smer. Torej da iz predpostavke (3) sledi, da sta za£eni in kon£ni signal enaka. Pri tej predpostavki se izraz (4) poenostavi ravno v x˜(z) = x(z), torej sta za£etni in kon£ni signal res enaka. Tako iz pogoja popolne rekonstrukcije sledi, da sta za£etni in kon£ni signal enaka. □ V nadaljevanju uvedimo pojma dualni par ltrov in modulacijska matrika, s ka- terimi bomo pogoj popolne rekonstrukcije zapisali v enostavnej²i in preglednej²i obliki.

Denicija 4.8. Para ltrov (h, g) in (h˜, g˜), za katera je izpolnjen pogoj popolne rekonstrukcije (3), imenujemo dualni par ltrov.

Denicija 4.9. Naj bo (h, g) par ltrov. Modulacijsko matriko para ltrov (h, g) deniramo kot

M(z) =

[︃h(z) h(−z) g(z) g(−z) ]︃

(5) .

Dualnemu paru ltrov (h˜, g˜) na enak na£in priredimo dualno modulacijsko matriko in jo ozna£imo M˜︂(z).

S pomo£jo modulacijske matrike in dualne modulacijske matrike lahko sedaj zapi-

²emo pogoj popolne rekonstrukcije v matri£ni obliki. To nam pove naslednja trditev.

Trditev 4.10. Naj bosta M(z) in M˜︂(z) modulacijski matriki parov ltrov (h, g) in (h˜, g˜) ter I identi£na matrika velikosti 2×2. Potem je

(6) M˜︂(z⁻¹)^TM(z) = 2I

natanko tedaj, ko sta (h, g) in (h˜, g˜) dualna para ltrov.

Dokaz. Oglejmo si produkt matrik iz (6). Velja M˜︂(z⁻¹)^TM(z) =

[︃ h˜(z⁻¹) g˜(z⁻¹) h˜(−z⁻¹) g˜(−z⁻¹)

]︃ [︃

h(z) h(−z) g(z) g(−z) ]︃

=

[︃ h˜(z⁻¹)h(z) +g˜(z⁻¹)g(z) h˜(z⁻¹)h(−z) +g˜(z⁻¹)g(−z) h˜(−z⁻¹)h(z) +g˜(−z⁻¹)g(z) h˜(−z⁻¹)h(−z) +g˜(−z⁻¹)g(−z)

]︃

V prvem stolpcu prepoznamo ravno izraza iz pogoja popolne rekonstrukcije (3). V drugem stolpcu pa lahko uvedemo substitucijo z ↦→ −t in tako spet prepoznamo ravno pogoj popolne rekonstrukcije. Torej velja zveza M˜︂(z⁻¹)^TM(z) = 2I. □ Tako predstavljen pogoj popolne rekonstrukcije nam bo skraj²al dokazovanje trdi- tve, ki bo pogoj popolne rekostrukcije predstavila s pomo£jo polifaznih komponent in polifaznih matrik, ki so predstavljene v nadaljevanju.

4.4. Polifazna predstavitev Laurentovih polinomov. V osnovni ideji val£ne transformacije smo signal razdelili na sodi in lihi del, zato ºelimo tudi ltre, oziroma pripadajo£e Laurentove polinome, razdeliti na sodi in lihi del. Iz trditve 3.3 ºe poznamo delitev na sodi in lihi del

h(z) =b(z) +c(z).

Ko tako denirana sodi in lihi del Laurentovega polinoma razumemo kot signala, se med posameznimi vrednostmi pojavijo ni£le. V nadaljevanju bi sodi in lihi del radi predstavili v tak²ni obliki, da dobljena ltra, oziroma pripadajo£a Laurentova polinoma, ne bosta vsebovala ni£el med posameznima £lenoma.

Denicija 4.11. Naj bo h(z) Laurentov polinom s koecienti h_i, kjer so h_i ∈ R za i ∈ Z. Soda polifazna komponenta Laurentovega polinoma h(z) je podana s predpisom

h_e(z) =∑︂

k

h_2kz^−k, liha polifazna komponenta pa je podana s

h_o(z) =∑︂

k

h_2k+1z^−k.

Pravimo, da smo Laurentov polinom h(z) razdelili na polifazni komponenti.

Polifazna predstavitev Laurentovega polinoma nam bo olaj²ala izpeljavo zveze med analiti£nim in sinteti£nim parom ltrov pri pogoju popolne rekonstrukcije. S pomo£jo zveze, ki jo podaja naslednja trditev, lahko vsak Laurentov polinom pred- stavimo kot kombinacijo sode in lihe polifazne komponente.

Trditev 4.12. Naj boh(z) Laurentov polinom inh_e(z), h_o(z) njegovi polifazni kom- ponenti. Tedaj velja

(7) h(z) = he(z²) +z⁻¹ho(z²).

Dokaz. Naj bo h(z) Laurentov polinom in naj bostah_e(z)inh_o(z)njegovi polifazni komponenti kot v deniciji 4.11. Oglejmo si vrednosti polifaznih komponent pri argumentu z². Dobimo

h_e(z²) =∑︂

k∈Z

h_2k(z²)^−k=∑︂

k

h_2kz^−2k =b(z),

h_o(z²) =∑︂

k∈Z

h_2k+1(z²)^−k =z∑︂

k

h_2k+1z^−2k−1 =z∑︂

k

h_2k+1z^−(2k+1) =zc(z).

V zadnji enakosti prepoznamo ravno sodi in lihi del Laurentovega polinoma, iz trditve 3.3. Po tej isti trditvi tudi vemo, da je vsak Laurentov polinom enak vsoti sodega in lihega dela, pri £emer je sodi del enakh_e(z²)lihi del paz⁻¹h_o(z²). Dobimo

ravno zvezo, ki smo jo ºeleli dokazati. □

Z upo²tevanjem trditve 3.3 lahko polifazni komponenti izrazimo le z Laurentovima polinomoma h(z) inh(−z).

Posledica 4.13. Veljata zvezi h_e(z²) = h(z) +h(−z)

2 , h_o(z²) = z(h(z)−h(−z))

2 .

Opomba 4.14. Polifazne komponente bi lahko denirali tudi s pomo£jo operatorja podvzor£enja. Opazimo lahko namre£, da za lter h s pripadajo£im Laurentovim polinomom h(z) in lter h^′, deniran z Laurentovim polinomom zh(z), dobimo polifazni komponenti kot

h_e = (↓2)h, h_o = (↓2)h^′.

Polifazne komponente Laurentovih polinomov bodo imele pomembno vlogo pri konstrukciji dviºnega koraka. Ker so vsi ra£uni in dokazi preglednej²i v matri£ni obliki, bomo tako zapisali tudi pare polifaznih komponent. Najprej denirajmo polifazno matriko, s pomo£jo katere bomo ²e bolj poenostavili pogoj popolne rekon- strukcije.

Denicija 4.15. Naj bo(h, g)par ltrov terh_e(z), h_o(z), g_e(z), g_o(z)polifazne kom- ponente pripadajo£ih Laurentovih polinomov h(z) in g(z). Matrika

P(z) =

[︃h_e(z) g_e(z) h_o(z) g_o(z) ]︃

je polifazna matrika Laurentovih polinomov h(z) in g(z). Polifazno matriko, ki pripada dualnemu paru ltrov (h˜, g˜), imenujemo dualna polifazna matrika in jo ozna£imo s P˜︁(z).

4.5. Polifazna predstavitev pogoja popolne rekonstrukcije. Za za£etek si poglejmo, kako lahko polifazno matriko predstavimo zgolj z modulacijsko matriko ltrov (h, g).

Trditev 4.16. Naj bo M(z) modulacijska matrika,P(z)pa polifazna matrika ltrov (h, g). Tedaj velja zveza

P(z²)^T = 1 2M(z)

[︃1 z 1 −z

]︃

.

Dokaz. Za matriko M(z) velja 1

2M(z)

[︃1 z 1 −z

]︃

= 1 2

[︃h(z) +h(−z) z(h(z)−h(−z)) g(z) +g(−z) z(g(z)−g(−z)) ]︃

=

[︃h_e(z²) h_o(z²) g_e(z²) g_o(z²) ]︃

. Zadnja enakost velja po posledici 4.13. Prepoznamo ravno matriko P(z²)^T. □

Po trditvi 4.10 ºe vemo, da lahko pogoj popolne rekonstrukcije predstavimo le z modulacijskimi matrikami. S pomo£jo trditve 4.16 pa bi radi pogoj popolne rekon- strukcije predstavili zgolj s polifaznimi matrikami. To nam pove naslednja trditev.

Trditev 4.17. Naj bo P(z) polifazna matrika Laurentovih polinomov h(z) in g(z), matrika P˜︁(z) pa polifazna matrika Laurentovih polinomov h˜(z) in g˜(z). Pogoj po- polne rekonstrukcije (3), izraºen s polifaznima matrikama, je

P(z)P˜︁(z⁻¹)^T =I, pri £emer je I identi£na matrika velikosti 2×2.

Dokaz. Oglejmo si produkt P(z)P˜︁(z⁻¹)^T. Najprej se spomnimo zveze med modu- lacijsko in polifazno matriko iz trditve 4.16. Uvedemo substitucijo z ↦→ t² in tako dobimo

P(t²)P˜︁(t⁻²)^T = (︃1

2M(t) [︃1 t

1 −t ]︃)︃T (︃

1

2M˜︂(t⁻¹)

[︃1 t⁻¹ 1 −t⁻¹

]︃)︃

= 1 4

[︃1 1 t −t

]︃

M(t)^TM˜︂(t⁻¹)

[︃1 t⁻¹ 1 −t⁻¹

]︃

. Produkt M(t)^TM(t˜︂ ⁻¹)je po trditvi 4.10 enak 2I. Tako dobimo

1 2

[︃1 1 t −t

]︃ [︃

1 t⁻¹ 1 −t⁻¹

]︃

= [︃1 0

0 1 ]︃

,

iz £esar sledi, da res velja P(z)P˜︁(z⁻¹)^T =I. □ V dokazu izreka opazimo, da sta polifazna matrika in dualna polifazna matrika obrnljivi. To nam poda ²e enostavnej²o zvezo med polifazno matriko in dualno polifazno matriko ter posledi£no zvezo, ki mora veljati med dualnima paroma ltrov.

Posledica 4.18. Za polifazno matrikoP(z)in pripadajo£o dualno polifazno matriko P˜︁(z) velja

P(z)⁻¹ =P˜︁(z⁻¹)^T.

Opomba 4.19. Polifazni matriki sta obrnljivi, zato je po razmisleku iz poglavja 3.2 njuna determinanta monom oziroma Laurentov polinom stopnje 0. Ker je to obrnljiv element kolobarja Laurentovih polinomov, lahko bodisi h(z) bodisi g(z) delimo z determinanto in tako doseºemo, da bo determinanta polifazne matrike in dualne polifazne matrike enaka1. Torej je dovolj obravnavati zgolj polifazne matrike iz SL(2,R[z, z⁻¹]).

Denicija 4.20. Filtra h in g sta komplementarna, £e je determinanta njune poli- fazne matrike P(z)enaka 1.

Opomba 4.21. V primeru, ko je determinanta polifazne matrike P(z) enaka 1, je po posledici 4.18 tudi determinanta dualne polifazne matrike P˜︁(z) enaka 1. Torej sta tudi dualna ltra h˜ in g˜komplementarna.

x(z)

z

↓2

↓2

s(z)

d(z)

↑2

↑2 z⁻¹

+ x˜(z) P˜︁(z⁻¹)^T P(z)

Slika 8. Diskretna val£na transformacija predstavljena s polifaznimi matrikami. V prvem delu sodo in liho polifazno komponento x mno- ºimo s polifazno matriko P˜︁(z⁻¹) in tako dobimo signal reduciranih vrednosti ter signal ostankov. V drugem delu signal reduciranih vre- dnosti in signal ostankov pomnoºimo s polifazno matrikoP(z)in tako dobimo polifazni komponenti za£etnega signala x.

Shemo diskretne val£ne transformacije lahko sedaj predstavimo kot mnoºenje po- lifazne matrike s polifaznima komponentama signala. To prikazuje slika 8. Ideja je, da signal razdelimo na sodo in liho polifazno komponento, nato pa na komponentah uporabimo dualno polifazno matriko. Rezultat mnoºenja sta ravno signala reduci- ranih vrednosti in signal ostankov. Na vektorju [x_e, x_o] torej uporabimo P˜︁(z⁻¹) in tako dobimo [s(z), d(z)]. Pri ra£unanju inverza pa za£nemo s signalom reduciranih vrednosti in signalom ostankov, na katerih uporabimo polifazno matriko in tako do- bimo ravno polifazni komponenti za£etnega signala. To pomeni, da na [s(z), d(z)]

uporabimoP(z)in dobimo[x_e(z), x_o(z)]. Za£etni in kon£ni signal sta pri tem enaka, saj po trditvi 4.17 velja pogoj popolne rekonstrukcije.

Za£etni pogoj popolne rekonstrukcije (3), ki podaja zvezo med ²tirimi Laurento- vimi polinomi, smo tako poenostavili na zvezo med polifazno in dualno polifazno matriko. To bi radi poenostavili v eksplicitno zvezo med polifaznimi komponentami para ltrov (h, g)in dualnega para ltrov (h˜, g˜), kar nam podaja naslednji izrek.

Izrek 4.22. Naj bosta (h, g) in (h˜, g˜) dualna para komplementarnih ltrov. Potem veljajo naslednje zveze:

h˜_e(z) =go(z⁻¹), h˜_o(z) = −ge(z⁻¹), g

˜_e(z) =−h_o(z⁻¹), g˜_o(z) = h_e(z⁻¹).

Dokaz. Naj bo P(z) podana polifazna matrika za h(z) in g(z). I²£emo taka Lau- rentova polinoma h˜(z) ing˜(z), da bo za pripadajo£i polifazni matriki P(z) in P˜︁(z) veljala trditev 4.17. Problem razumemo kot problem re²evanja sistema ena£b

[︃he(z) ge(z) h_o(z) g_o(z)

]︃ [︃

h˜_e(z⁻¹) g

˜_e(z⁻¹) ]︃

= [︃1

0

]︃ [︃

he(z) ge(z) h_o(z) g_o(z)

]︃ [︃

h˜_o(z⁻¹) g

˜_o(z⁻¹) ]︃

= [︃0

1 ]︃

. Z uporabo Cramerjevega pravila dobimo naslednje zveze

h˜

e(z⁻¹) = go(z)

detP(z) =g_o(z), g˜_e(z⁻¹) = −ho(z)

detP(z) =−h_o(z), h˜

o(z⁻¹) = −g_e(z)

detP(z) =−g_e(z), g˜_o(z⁻¹) = h_e(z)

detP(z) =h_e(z),

saj je detP(z) = 1. Torej res veljajo zveze iz izreka. □ Oglejmo si sedaj nekaj zgledov ltrov in pripadajo£ih polifaznih matrik.

Zgled 4.23. V najosnovnej²em primeru je polifazna matrika P(z)kar identiteta I, torej velja P(z) =P˜︁(z)^T. Pripadajo£i elementi polifazne matrike P(z)so torej

h_e(z) = 1, h_o(z) = 0, g_e(z) = 0, g_o(z) = 1.

Od tu po izreku 4.22 dobimo Laurentova polinoma

h(z) =h˜(z) = 1, g(z) = g˜(z) = z⁻¹.

Val£ni transformaciji s tako podanima ltroma pravimo leni val£ek. ♢ Zgled 4.24. Spomnimo se primera operatorjev Haarovega val£ka iz zgleda 2.1.

Znano je, da je Haarov val£ek podan s sinteti£nim parom ltrov h(z) = z⁻¹ + 1 in g(z) = ¹₂z⁻¹− ¹₂. Modulacijska matrika Haarovega val£ka je

M(z) =

[︃ z⁻¹+ 1 −z⁻¹+ 1

1

2z⁻¹− ¹₂ −¹₂z⁻¹− ¹₂ ]︃

. Polifazne komponente polinomov h(z) ing(z) so podane z

h_e(z²) = 1 +z⁻¹+ 1−z⁻¹

2 = 1, g_e(z²) =

1

2z⁻¹− ¹₂ − ¹₂z⁻¹−¹₂

2 =−1

2, h_o(z²) =z1 +z⁻¹ −1 +z⁻¹

2 = 1, g_o(z²) =z

1

2z⁻¹− ¹₂ +¹₂z⁻¹+ ¹₂

2 = 1

2. Pripadajo£a polifazna matrika je tako

P(z) =

[︃1 −¹₂ 1 ¹₂

]︃

.

Dualno polifazno matriko lahko najdemo s pomo£jo izreka 4.22 ali pa ²e laºje kar s pomo£jo posledice 4.18. Torej je dualna polifazna matrika

P˜︁(z⁻¹)^T =P(z)⁻¹ = [︃ ₁

2 1

−1 12

]︃

. Od tu z zvezo 7 dobimo dualna polinoma h˜(z) in g˜(z) kot

h˜(z) = 1 2+ 1

2z⁻¹, g˜(z) = −1 +z⁻¹.

Tako smo dobili analiti£ni in sinteti£ni par ltrov, ki ju uporabljamo pri Haarovemu val£ku. V nadaljevanju bomo utemeljili, da val£na transformacija, podana s tak²nim parom ltrov, ustreza transformaciji iz zgleda 2.1. ♢

5. Faktorizacija polifazne matrike

Spoznali smo, kako lahko diskretno val£no transformacijo, podano s paroma l- trov, z uporabo polifaznih komponent in Laurentovih polinomov pretvorimo na mno- ºenje s polifazno matriko. To bi radi ²e bolj poenostavili in mnoºenje s polifazno matriko preoblikovali v dviºne korake, kot so bili predstavljeni v osnovni ideji v po- glavju 2. Najprej si bomo ogledali metodo dviga, s pomo£jo katere, £im poznamo en par komplementarnih ltrov, konstruiramo celotno druºino komplementarnih ltrov.

5.1. Dvig. Za za£etek si oglejmo trditev, ki pove, kak²ni polifazni komponenti do- bimo, £e Laurentov polinom pomnoºimo z drugim Laurentovim polinomom.

Lema 5.1. Naj bosta h(z) in p(z) Laurentova polinoma. Potem sta polifazni kom- ponenti Laurentovega polinoma f(z) = h(z)p(z²) podani z

f_e(z) = h_e(z)p(z), f_o(z) =h_o(z)p(z).

Dokaz. Uporabimo zapis sode in lihe polifazne komponente iz posledice 4.13 in tako dobimo

fe(z²) = h(z)p(z²) +h(−z)p(z²)

2 = h(z) +h(−z)

2 p(z²) =he(z²)p(z²), f_o(z²) = h(z)p(z²)−h(−z)p(z²)

2z⁻¹ = h(z)−h(−z)

2z⁻¹ p(z²) = h_o(z²)p(z²).

Naredimo substitucijo z² ↦→z in dobimo iskani zvezi. □ Opomba 5.2. Povsem enak razmislek bi lahko uporabili pri ra£unanju polifaznih komponent Laurentovega polinomaf(z) =h(z)p(z⁻²). Le da v tem primeru dobimo polifazni komponenti Laurentovega polinoma h(z) pomnoºeni s p(z⁻¹).

S pomo£jo leme 5.1 bomo sedaj dokazali naslednji izrek, ki nam pove, kako lahko v komplementarnem paru ltrov(h, g), nadomestimo lterg s ltromg^′, da je(h, g^′)

²e vedno komplementaren par ltrov. Temu pravimo dvig.

Izrek 5.3 (Dvig). Naj bo (h, g) par komplementarnih ltrov. Potem je vsak kon£en lter g^′, ki je komplementaren h, oblike

g^′(z) = g(z) +h(z)p(z²) (8)

za neki Laurentov polinom p(z).

Dokaz. Najprej bi radi dokazali, da je lterg^′, ki je podan z Laurentovim polinomom g^′(z) = g(z) +h(z)p(z²), komplementaren ltruh. Po lemi 5.1 sledi, da sta polifazni komponenti g^′(z) enaki

g_e^′(z) =g_e(z) +h_e(z)p(z), g_o^′(z) =g_o(z) +h_o(z)p(z).

Polifazna matrika ltrov (h, g^′) je torej enaka P^′(z) =

[︃h_e(z) g_e(z) +h_e(z)p(z) h_o(z) g_o(z) +h_o(z)p(z) ]︃

=

[︃h_e(z) g_e(z) h_o(z) g_o(z)

]︃ [︃

1 p(z)

0 1

]︃

=P(z)

[︃1 p(z)

0 1

]︃

. (9)

Ker sta ltra h in g komplementarna, je determinanta matrike P(z) enaka 1. Po- tem pa je tudi determinanta matrike P^′(z) enaka 1, torej sta si ltra h in g^′ res komplementarna.

Naj bo sedaj g^′ poljuben kon£en lter, komplementarenh. Naj boP(z)polifazna matrika komplementarnega para komplementarnih ltrov (h, g) in P^′(z) polifazna

matrika para ltrov (h, g^′). Pomnoºimo P^′(z) s P(z)⁻¹ in dobimo:

P(z)⁻¹P^′(z) =

[︃ g_o(z) −g_e(z)

−h_o(z) h_e(z) ]︃ [︃

h_e(z) g_e^′(z) h₀(z) g_o^′(z) ]︃

=

[︃h_e(z)g_o(z)−h_o(z)g_e(z) g_o(z)g_e^′(z)−g_e(z)g_o(z) 0 −h_o(z)g^′_e(z) +h_e(z)g_o^′(z)

]︃

=

[︃1 g_o(z)g_e^′(z)−g_e(z)g_o(z)

0 1

]︃

.

Zadnja enakost velja, saj v diagonalnih elementih prepoznamo ravno izraz za de- terminanti polifaznih matrik, ki sta po predpostavki enaki 1. Deniramo p(z) = g_o(z)g^′_e(z)−g_e(z)g_o(z) in tako dobimo, da velja

P^′(z) = P(z)

[︃1 p(z)

0 1

]︃

.

Zmnoºimo matriki na desni in dobimo polifazni komponenti Laurentovih polinomov h(z) in g^′(z). Po lemi 5.1 sledi, da je Laurentov polinom za lterg^′ podan v obliki

(8). □

Ko izvedemo dvig na komplementarnem paru ltrov (h, g), moramo posledi£no izvesti dvig tudi na paru ltrov (h˜, g˜), da bosta to ²e vedno dualna para ltrov. S pomo£jo zapisa pogoja popolne rekonstrukcije v polifazni obliki iz trditve 4.17 in dviga iz trditve 5.3 lahko izpeljemo naslednjo trditev o dualnem dvigu.

Trditev 5.4 (Dualni dvig). Naj bosta (h, g) in (h˜, g˜) dualna para komplementarnih ltrov. Naj bosta g^′ in h˜^′ ltra, ki sta dolo£ena z Laurentovima polinomoma g^′(z) = g(z)+h(z)p(z²)inh˜^′(z) = h˜(z)−g˜(z)p(z⁻²)za neki Laurentov polinomp(z). Potem sta tudi (h, g^′) in (h˜^′, g˜) dualna para komplementarnih ltrov.

Dokaz. Naj bosta (h, g)in(h˜, g˜)dualna para komplementarnih ltrov s polifaznima matrikama P(z) in P˜︁(z). Po posledici 4.18 vemo, da velja P(z)⁻¹ = P˜︁(z⁻¹)^T. Imejmo ²e lter g^′ in naj bo P^′(z) polifazna matrika za (h, g^′). Naj bo sedaj P˜︁^′(z) dualna polifazna matrika matrike P^′(z). Upo²tevamo zvezo (9) in vidimo, da velja

P^′(z)⁻¹ = (︃

P(z)

[︃1 p(z)

0 1

]︃)︃⁻¹

=

[︃1 −p(z)

0 1

]︃

P(z)⁻¹ =

[︃1 −p(z)

0 1

]︃

P˜︁(z⁻¹)^T

= (︃

P˜︁(z⁻¹)

[︃ 1 0

−p(z) 1 ]︃)︃T

=P˜︁^′(z⁻¹)^T. Naredimo substitucijo z ↦→z⁻¹ in tako dobimo

P˜︁^′(z) =P˜︁(z)

[︃ 1 0

−p(z⁻¹) 1 ]︃

.

Po lemi 5.1 in ob upo²tevanju opombe 5.2 sledi h˜^′(z) = h˜(z)−g˜(z)p(z⁻²) in s tem

je trditev dokazana. □

S pomo£jo trditev 5.3 in 5.4 lahko torej takoj, ko poznamo en komplementarni par ltrov (h, g), konstruiramo poljubne nove pare komplementarnih ltrov in po- sledi£no tudi nove pare dualnih ltrov. Tako lahko vedno za£nemo z lenim val£kom,