Hvorfor brukes sirkulær konvolusjon i DSP? Hvorfor ikke lineær konvolusjon?
On november 29, 2020 by admin-
Hvorfor bruker vi sirkulær konvolusjon i DSP?
-
Hva er den viktigste solide årsaken til bruken av den i digital behandling?
-
Hvorfor gjør begrepet sirkulær konvolusjon kommer oftere enn lineær konvolusjon?
Kommentarer
- vil du legge merke til at alle svarene dine inkluderer en omtale av Discrete Fourier Transform som er implementert mest effektivt med FFT. DFT utvider iboende periodisk de endelige lengdesekvensene som sendes til den (som er sirkulær). sirkulær konvolusjon er sjelden målet . vanligvis lineær konvolusjon er målet. men når du multipliserer DFT ‘ s $ X [k] $ og $ H [k] $ sammen, tilsvarer det sirkulær konvolusjon av de to periodisk utvidede sekvensene, $ x [n] $ og $ h [n] $ overført til DFT-ene. Problemet er å gjøre dette på en eller annen måte til lineær konvolusjon.
Svar
Gitt et diskret tid LTI-system med impulsrespons $ h [n] $ , kan man beregne sitt svar på alle innganger $ x [n] $ av en konvolusjon sum: $$ y [n] = x [n] \ star h [n] = \ sum_ {k = – \ infty} ^ {\ infty} {h [k] x [nk]} \ tag {1} $$
Uten noe nærmere angitt, er definisjonen ovenfor for lineær konvolusjon (aperiodisk konvolusjon) mellom $ h [n] $ og $ x [n] $ , som er aperiodiske diskrete tidssekvenser med mulig uendelig lengde, med mindre annet er oppgitt. Dette er forskjellig fra en sirkulær konvolusjon som er mellom to periodiske sekvenser av perioden $ N $ , og beregnet over en enkelt periode.
Du kan beregne konvolusjon i tidsdomene ved Eq.1, eller i frekvensdomene ved bruk av følgende DTFT (diskret-time Fourier transform) -egenskap: $$ y [n] = x [n] \ star h [n] \ innebærer Y (e ^ {j \ omega}) = X (e ^ {j \ omega}) H (e ^ {j \ omega}) \ tag {2} $$
DTFT er naturlig relatert til den lineære konvolusjonen, da den omhandler teoretisk eksisterende aperiodiske sekvenser som kan strekke seg fra $ – \ infty $ til $ \ infty $ gjenspeiles i grensene for den definerende summen: $$ X (e ^ {j \ omega}) = \ sum_ {n = – \ infty} ^ {\ infty} x [n] e ^ {- j \ omega n} \ tag {3} $$
Når du vil lage en beregning på for hånd ved å bruke symbolske uttrykk for signaler, for eksempel $ x [n] = a ^ nu [n] $ og $ h [n] = b ^ nu [n] $ , kan du beregne resultatene i tids- eller frekvensdomener som beskrevet ovenfor.
Når du vil beregne det samme resultatet ved hjelp av en datamaskin, kan du også bruke tidsdomene-tilnærmingen basert på en LCCDE-rekursjon (for IIR-systemer) eller direkte endelig konvolusjonssum (for FIR-systemer), MEN frekvensdomene-tilnærmingen vil ikke fungere med DTFT; den er hovedsakelig et verktøy som brukes til å utvikle matematikken til signaler & systemteori, og den er ikke egnet for digital datamaskin implementeringer, da variabelen $ \ omega $ er en ekte kontinuerlig nummer.
Det som brukes i stedet er DFT (diskret Fourier-transform) definert som $$ X [k] = X (e ^ {j \ omega}) | _ {\ omega = \ frac {2 \ pi k} {N}} \ tag {4} $$
der $ k = 0,1, …, N-1 $ og $ N $ er lengden på DFT, som deretter kalles som en N-punkt DFT av signal $ x [n] $ .
Ligning 4 antyder at DFT-sekvensen $ X [k] $ er oppnådd som de ensartede prøvene til DTFT $ X (e ^ {j \ omega}) $ , som er en periodisk funksjon, derfor er DFT $ X [k] $ også periodisk, men vi vurderer bare den første perioden fra $ k = 0 $ til $ N-1 $ .
Siden DFT-sekvenser iboende er periodiske, vil -konvolusjonene også være periodiske (sirkulære).Derfor, mens en lineær konvolusjon mellom aperiodiske signaler $ x [n] $ og $ y [n] $ er underforstått av I-DTFT-uttrykket $$ y [n] = \ mathcal {I-DTFT} \ {X (e ^ {j \ omega}) H (e ^ {j \ omega}) \} $$ i stedet for en sirkulær konvolusjon mellom to periodiske sekvenser er underforstått av I-DFT-uttrykket $$ \ tilde {y} [n] = \ mathcal { I-DFT} \ {X [k] H [k] \} $$
Så gitt at vi ønsker å beregne en lineær konvolusjon mellom to aperiodiske sekvenser $ x [n] $ og $ h [n] $ av lengder $ L_x $ og henholdsvis $ L_h $ , og bruker frekvensdomene av deres $ N $ punkt DFT, $ X [k] $ og $ H [k] $ , må vi faktisk beregne en sirkulær konvolusjon mellom periodiske utvidelser av signalene $ \ tilde {x} [n] $ og $ \ tilde {h} [n] $ av perioder $ N $ .
Nøkkelen er å velge riktig lengde $ N $ av DFT-ene, som må være lange nok til å unngå et tidsdomene aliasing i sekvensen $ \ tilde {y} [n] $ , returnerte ved IDFT-beregning: $$ \ tilde {y} [n] = \ sum_ {r = – \ infty} ^ {\ infty} y [n-rN] \ tag {5 } $$
der $ y [n] $ er resultatet av den lineære konvolusjonen som vil bli returnert av den teoretiske inverse DTFT og $ \ tilde {y} [n] $ er det periodiske resultatet av den periodiske (sirkulære) konvolusjonen implisert av den omvendte DFT.
Merk at hvis noen av signalene er uendelige, så er det «s IKKE mulig for å beregne deres lineære konvolusjon ved hjelp av DFT-tilnærmingen, da $ N $ ville gå til uendelig, praktisk talt umulig. Implementeringen av en lineær konvolusjon via DFT har deretter følgende trinn:
-
Velg N i henhold til følgende kriterier: $$ N \ geq L_x + L_h -1 $$ som garanterer en aliasfri rekonstruksjon av det inverse signalet $ y [n] $ fra DFT $ Y [k] $ av den beregnede sirkulære konvolusjonen via $ X [k] H [k] $ .
-
Beregn N-punkt DFTs $ X [k] $ og $ H [k] $ av $ x [n] $ og $ h [n] $ .
-
Beregn $ Y [k] = X [k ] H [k] $
-
Beregn N-punkt invers DFT av $ Y [k] $ for å produsere utgangen $ y [n] $
Svar
Svar på spørsmålene dine:
- Hvorfor bruker vi sirkulær konvolusjon i DSP?
I DSP håndterer vi normalt diskrete sekvenser med endelig lengde (selv om signalet som studeres er uendelig, kan vi bare analysere en endelig del av det om gangen ). Når det gjelder behandling av et signal, må måten å behandle det på, være implementerbart i en diskret logisk enhet (nemlig en enhet som ikke kan lagre kontinuerlige verdier fordi disse verdiene er uendelige og den har en endelig mengde minne, lagring osv.). Dette forklarer hvorfor Discrete Time Fourier Transform (DTFT) som transformerer en diskret tidssekvens til en kontinuerlig frekvenssekvens ikke kan implementeres i maskinvare. Lineær konvolusjon i tid tilsvarer multiplikasjonen av 2 sekvenser DTFT, men da DTFT ikke kan implementeres i maskinvare, er dette ikke måten å oppnå lineær konvolusjon. Diskret Fourier Transform (DFT), derimot, forvandler en diskret tidssekvens til en diskret frekvenssekvens, og denne lar den implementeres i Hardware. Likevel er å multiplisere 2 sekvenser DFTs ekvivalent med sirkulær konvolusjon i prinsippet (lineær konvolusjon kan også oppnås hvis tidssekvensene tidligere er polstret med nok nuller, se forklaring nedenfor).Årsaken til at multiplisering av 2 DFT-sekvenser tilsvarer sirkulær og ikke lineær konvolusjon, kommer av det faktum at DFT for en endelig tidslengdesekvens tilsvarer Discrete Fourier Series (DFS) av den samme endelige tidslengdesekvensen periodisk utvidet endelig tids lengdesekvens uendelig i tidsaksen) tatt over en periode. DFS er også periodisk i frekvensdomene så lineær konvolusjon gjelder ikke der (se 8.2.5 og 8.6.5 i Oppenheims Discrete Time Signal Processing 3. utgave)
- Hva er den viktigste solide årsaken til bruken av den i digital behandling?
Det oppnås ved DFT-multiplikasjon, og DFT implementeres enkelt i maskinvare. Videre er det veldig effektive algoritmer som FFT for beregning av DFT
- Hvorfor kommer begrepet sirkulær konvolusjon oftere enn lineær konvolusjon?
Det er avhengig av applikasjonen. Sirkulær konvolusjon kan også gi den lineære konvolusjonen. La oss for eksempel si vi jobber med signal A med lengde N og signal B også av lengde N (det kan også gjøres for forskjellige lengder). Den sirkulære konvolusjonen vil ha lengde N. For å oppnå lineær konvolusjon må både A og B polstres med nuller til de oppnår en lengde på minst 2 * N – 1. Påfør deretter DFT på begge, multipliser dem og bruk invers DFT vil gi deg den lineære konvolusjonen
Svar
Her «litt intuisjon:
Når du håndtere signaler digitalt, har du alltid å gjøre med et endelig signal. Dette er fordi du bare kan behandle på en begrenset mengde datapunkter.
Problemet er imidlertid at når du utfører transformasjoner til frekvensdomenet ved hjelp av DFT, per definisjon, kan et signal ikke være endelig. Derfor, når du utfører en DFT-operasjon, er det en implisitt endring av signalet ditt fra å være endelig, til å være periodisk, selv om signalet ditt ikke er periodisk.
Dette periodisiteten til signalet fører til behovet for å bruke konvolusjon på en sirkulær måte.
Svar
DFT / FFT er en nyttig beregnings «hammer», men alle dens transformasjonsbasisvektorer er sirkulære (heltall periodiske) i blenderåpning, og kan utvides uendelig som periodiske funksjoner, som noen brukere forveksler med arten av deres inndata.
Hvis du nullstiller med en tilstrekkelig mengde, gir sirkulær konvolusjon det samme resultatet som lineær konvolusjon, men til en noe større beregningskostnad enn sirkulær.
Legg igjen en kommentar