Hvorfor bruges cirkulær konvolution i DSP? Hvorfor ikke lineær foldning?
On november 29, 2020 by admin-
Hvorfor bruger vi cirkulær konvolution i DSP?
-
Hvad er den væsentligste grund til brugen af det i digital behandling?
-
Hvorfor er begrebet cirkulær sammenfald kommer oftere end lineær sammenfald?
Kommentarer
- du vil bemærke, at alle dine svar inkluderer en omtale af den diskrete Fourier-transformation, der implementeres mest effektivt med FFT. DFT udvider iboende periodisk de endelige længdesekvenser, der sendes til den (som er cirkulær). cirkulær foldning er sjældent målet . normalt lineær foldning er målet. men når man multiplicerer DFT ‘ s $ X [k] $ og $ H [k] $ sammen, svarer det til cirkulær konvolution af de to periodisk udvidede sekvenser, $ x [n] $ og $ h [n] $ videregivet til DFTerne. Problemet er derefter på en eller anden måde at gøre dette til lineær konvolution.
Svar
Givet et diskret tids-LTI-system med impulsrespons $ h [n] $ , man kan beregne sit svar på ethvert input $ x [n] $ af en konvolution sum: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Uden noget andet er angivet, er ovenstående definition til lineær konvolution (aperiodisk konvolution) mellem $ h [n] $ og $ x [n] $ , som er aperiodiske diskrete tidssekvenser med muligvis uendelig længde, medmindre andet er angivet. Dette er forskellig fra en cirkulær konvolvering som er mellem to periodiske sekvenser af perioden $ N $ og beregnet over en enkelt periode.
Du kan beregne foldning i tidsdomæne ved ligning 1 eller i frekvensdomæne ved hjælp af følgende DTFT (diskret-time Fourier transform) egenskab: $$ y [n] = x [n] \ star h [n] \ antyder Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT er naturligvis relateret til den lineære foldning, da den beskæftiger sig med teoretisk eksisterende aperiodiske sekvenser, der kan strække sig fra $ – \ infty $ til $ \ infty $ afspejles i dets grænser for den definerende sum: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Når du vil lave en beregning ved hånden ved hjælp af symbolske udtryk for signaler, såsom $ x [n] = a ^ nu [n] $ og $ h [n] = b ^ nu [n] $ , du kan beregne resultaterne i tids- eller frekvensdomæner som beskrevet ovenfor.
Når du vil beregne det samme resultat ved hjælp af en computer, kan du også bruge tidsdomænetilgangen baseret på en LCCDE-rekursion (for IIR-systemer) eller en direkte endelig konvolutionssum (for FIR-systemer), MEN frekvensdomænetilgangen fungerer ikke med DTFT, da det hovedsagelig er et værktøj, der bruges til at udvikle matematikken i signaler & systemteori, og det er ikke egnet til digital computer implementeringer, da dens variabel $ \ omega $ er en ægte kontinuerlig nummer.
Hvad der bruges i stedet er DFT (diskret Fourier-transformation) defineret som $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
hvor $ k = 0,1, …, N-1 $ og $ N $ er længden af DFT, som derefter kaldes som en N-punkt DFT for signal $ x [n] $ .
Ligning 4 indebærer, at DFT-sekvensen $ X [k] $ opnås som ensartede prøver af DTFT $ X (e ^ {j \ omega}) $ , som er en periodisk funktion, derfor er DFT $ X [k] $ også periodisk, men vi betragter kun dens første periode fra $ k = 0 $ til $ N-1 $ .
Da DFT-sekvenser i sagens natur er periodiske, vil deres -konvolutter også være periodiske (cirkulære).Derfor, hvorimod en lineær sammenfald mellem aperiodiske signaler $ x [n] $ og $ y [n] $ er underforstået af I-DTFT-udtrykket $$ y [n] = \ matematisk {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ i stedet for en cirkulær sammenblanding mellem to periodiske sekvenser er underforstået af I-DFT-udtrykket $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Så i betragtning af at vi ønsker at beregne en lineær foldning mellem to aperiodiske sekvenser $ x [n] $ og $ h [n] $ af længder $ L_x $ og $ L_h $ henholdsvis ved hjælp af frekvensdomæne efter deres $ N $ point DFTer, $ X [k] $ og $ H [k] $ , er vi faktisk nødt til at beregne en cirkulær konvolution mellem de periodiske udvidelser af signalerne $ \ tilde {x} [n] $ og $ \ tilde {h} [n] $ af perioder $ N $ .
Nøglen er at vælge en passende længde $ N $ af DFTerne, som skal være lange nok til at undgå ethvert tidsdomæne aliasing i sekvensen $ \ tilde {y} [n] $ , returneres ved IDFT-beregning: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
hvor $ y [n] $ er resultatet af den lineære foldning, der ville blive returneret af den teoretiske inverse DTFT og $ \ tilde {y} [n] $ er det periodiske resultat af den periodiske (cirkulære) foldning, der er underforstået af den inverse DFT.
Bemærk, at hvis et af signalerne er af uendelig længde, så er det “s IKKE muligt at beregne deres lineære konvolution ved hjælp af DFT-tilgangen, da $ N $ ville gå til uendelig, praktisk talt umulig. Implementeringen af en lineær konvolution via DFT har derefter følgende trin:
-
Vælg N efter følgende kriterier: $$ N \ geq L_x + L_h -1 $$ som garanterer en alias-fri rekonstruktion af det inverse signal $ y [n] $ fra sin DFT $ Y [k] $ af den beregnede cirkulære opløsning via $ X [k] H [k] $ .
-
Beregn N-punkt DFTer $ X [k] $ og $ H [k] $ af $ x [n] $ og $ h [n] $ .
-
Beregn $ Y [k] = X [k ] H [k] $
-
Beregn N-punkt invers DFT af $ Y [k] $ for at producere output $ y [n] $
Svar
Besvarelse af dine spørgsmål:
- Hvorfor bruger vi cirkulær foldning i DSP?
I DSP beskæftiger vi os normalt med diskrete sekvenser med endelig længde (selvom det undersøgte signal er uendeligt, kan vi kun analysere en endelig del af det ad gangen ). Når det kommer til behandling af et signal, skal måden at behandle det være implementerbart på i en diskret logisk enhed (nemlig en enhed, der ikke kan gemme kontinuerlige værdier, fordi disse værdier er uendelige, og den har en begrænset mængde hukommelse, lager osv.). Dette forklarer, hvorfor Discrete Time Fourier Transform (DTFT), som omdanner en diskret tidssekvens til en kontinuerlig frekvenssekvens, ikke kan implementeres i hardware. Lineær foldning i tid svarer til multiplikationen af 2 sekvenser DTFTer, men da DTFT ikke kan implementeres i hardware, er dette ikke måden at opnå lineær foldning på. Diskret Fourier Transform (DFT) transformerer på den anden side en diskret tidssekvens til en diskret frekvenssekvens, og denne gør det muligt at implementere den i Alligevel er multiplikation af 2 sekvenser DFTs ækvivalent med cirkulær konvolution i princippet (lineær konvolution kan også opnås, hvis tidssekvenserne tidligere er polstret med nok nuller, se forklaring nedenfor).Årsagen til, at multiplikation af 2 DFT-sekvenser svarer til cirkulær og ikke lineær sammenfald, kommer af det faktum, at DFT for en endelig tidslængdesekvens svarer til Discrete Fourier Series (DFS) af den samme samme endelige tidslængdesekvens, der periodisk udvides (sammenkædning af endelig tidslængdesekvens uendeligt i tidsaksen) taget over en periode. DFS er også periodisk i frekvensdomæne, så lineær foldning gælder ikke der (se 8.2.5 og 8.6.5 i Oppenheims diskrete tidssignalbehandling 3. udgave)
- Hvad er den væsentligste grund til brugen af det i digital behandling?
Det opnås ved DFT-multiplikation, og DFT implementeres let i hardware. Desuden findes der meget effektive algoritmer som FFT til beregning af DFT
- Hvorfor kommer begrebet cirkulær konvolvering oftere end lineær foldning?
Det afhænger af applikationen. Cirkulær foldning kan også give den lineære foldning. Lad os f.eks. sige vi arbejder med signal A af længde N og signal B også af længde N (det kan også gøres i forskellige længder). Den cirkulære foldning vil have længde N. For at opnå lineær foldning skal både A og B polstres med nuller, indtil de opnår en længde på mindst 2 * N – 1. Påfør derefter DFT på begge, gang dem og anvend omvendt DFT giver dig den lineære sammenblanding
Svar
Her “en smule intuition:
Når du håndtere signaler digitalt, har du altid at gøre med et endeligt signal. Dette skyldes, at du kun kan behandle på en begrænset mængde datapunkter.
Problemet er dog, at når du udfører transformationer til frekvensdomænet ved hjælp af DFT, pr. definition, kan et signal ikke være endeligt. Derfor, når du udfører en DFT-operation, er der en implicit ændring af dit signal fra at være endeligt, til at være periodisk, selvom dit signal ikke er periodisk.
Dette periodicitet af signalet fører til behovet for at bruge foldning på en cirkulær måde.
Svar
DFT / FFT er en nyttig beregnings “hammer”, men alle dens transformationsbasisvektorer er cirkulære (heltal periodiske) i blænde og kan udvides uendeligt som periodiske funktioner, som nogle brugere forveksler med arten af deres inputdata.
Hvis du nulstiller med en tilstrækkelig mængde, producerer cirkulær foldning det samme resultat som lineær opløsning, men til en lidt større beregningsomkostning end cirkulær.
Skriv et svar