Cirkulær konvolvering - Circular convolution

Cirkulær konvolvering , også kendt som cyklisk konvolvering , er et specielt tilfælde af periodisk konvolvering , som er konvolvering af to periodiske funktioner, der har samme periode. Periodisk konvolvering opstår f.eks. I forbindelse med diskret-tid Fourier-transformationen (DTFT). Især er DTFT af produktet af to diskrete sekvenser den periodiske konvolvering af DTFT'erne i de enkelte sekvenser. Og hver DTFT er en periodisk summering af en kontinuerlig Fouriertransformationsfunktion (se DTFT § Definition ). Selvom DTFT'er normalt er kontinuerlige frekvensfunktioner, er begreberne periodisk og cirkulær konvolvering også direkte anvendelige på diskrete datasekvenser. I den sammenhæng spiller cirkulær konvolvering en vigtig rolle for at maksimere effektiviteten af ​​en bestemt slags fælles filtreringsoperation.

Definitioner

Den periodiske konvolvering af to T-periodiske funktioner og kan defineres som :${\ displaystyle h _ {_ {T}} (t)}$${\ displaystyle x _ {_ {T}} (t)}$

${\ displaystyle \ int _ {t_ {o}}^{t_ {o}+T} h _ {_ {T}} (\ tau) \ cdot x _ {_ {T}} (t- \ tau) \, d \ tau,}$  

hvor t _o er en vilkårlig parameter. En alternativ definition, med hensyn til notationen for normal lineær eller aperiodisk foldning, følger ekspression og som periodiske summationer af aperiodiske komponenter og , dvs :${\ displaystyle h _ {_ {T}} (t)}$${\ displaystyle x _ {_ {T}} (t)}$${\ displaystyle h}$${\ displaystyle x}$

${\ displaystyle h _ {_ {T}} (t) \ \ triangelq \ \ sum _ {k =-\ infty}^{\ infty} h (t-kT) = \ sum _ {k =-\ infty}^ {\ infty} h (t+kT).}$

Derefter :

${\ displaystyle \ int _ {t_ {o}}^{t_ {o}+T} h _ {_ {T}} (\ tau) \ cdot x _ {_ {T}} (t- \ tau) \, d \ tau = \ int _ {-\ infty}^{\ infty} h (\ tau) \ cdot x _ {_ {T}} (t- \ tau) \, d \ tau \ \ triangleq \ (h*x_ { _ {T}}) (t) = (x*h _ {_ {T}}) (t).}$

( Ligning 1 )

Begge former kan kaldes periodisk konvolvering . Udtrykket cirkulær konvolvering stammer fra det vigtige særlige tilfælde med at begrænse ikke-nul-dele af begge og til intervallet Så bliver den periodiske summering til en periodisk forlængelse , som også kan udtrykkes som en cirkulær funktion :${\ displaystyle h}$${\ displaystyle x}$${\ displaystyle [0, T].}$

${\ displaystyle x _ {_ {T}} (t) = x (t _ {\ mathrm {mod} \ T}), \ quad t \ in \ mathbb {R} \,}$( ethvert reelt tal )

Og grænserne for integration reduceres til funktionens længde :${\ displaystyle h}$

${\ displaystyle (h*x _ {_ {T}}) (t) = \ int _ {0}^{T} h (\ tau) \ cdot x ((t- \ tau) _ {\ mathrm {mod} \ T}) \ d \ tau.}$

Diskrete sekvenser

Tilsvarende kan vi for diskrete sekvenser og en parameter N skrive en cirkulær konvolution af aperiodiske funktioner og som :${\ displaystyle h}$${\ displaystyle x}$

${\ displaystyle (h*x _ {_ {N}}) [n] \ \ triangleq \ \ sum _ {m =-\ infty}^{\ infty} h [m] \ cdot \ underbrace {x _ {_ {N }} [nm]} _ {\ sum _ {k =-\ infty}^{\ infty} x [nm-kN]}}$

Denne funktion er N -perioden. Den har højst N unikke værdier. I det særlige tilfælde, at ikke-nul-omfanget af både x og h er ≤ N , kan det reduceres til matrixmultiplikation, hvor kernen af ​​den integrale transformation er en cirkulerende matrix .

Eksempel

Cirkulær konvolvering kan fremskyndes af FFT -algoritmen, så den bruges ofte med et FIR -filter til effektivt at beregne lineære omdrejninger. Disse grafer illustrerer, hvordan det er muligt. Bemærk, at en større FFT -størrelse (N) forhindrer overlapning, der får graf #6 til ikke helt at stemme overens med #3.

Et tilfælde af stor praktisk interesse er illustreret i figuren. Varigheden af x -sekvensen er N (eller mindre), og varigheden af h -sekvensen er signifikant mindre. Derefter er mange af værdierne for den cirkulære konvolusion identiske med værdierne for x ∗ h , hvilket faktisk er det ønskede resultat, når h -sekvensen er et endeligt impulsresponsfilter (FIR). Endvidere er den cirkulære konvolvering meget effektiv at beregne ved hjælp af en hurtig Fourier transform (FFT) algoritme og den cirkulære konvolutions sætning .

Der er også metoder til behandling af en x -sekvens der er længere end en praktisk værdi for N . Sekvensen er opdelt i segmenter ( blokke ) og behandlet stykkevis. Derefter deles de filtrerede segmenter forsigtigt sammen igen. Kanteffekter elimineres ved enten at overlappe inputblokkene eller outputblokkene. For at hjælpe med at forklare og sammenligne metoderne diskuterer vi dem begge i sammenhæng med en h -sekvens med længde 201 og en FFT -størrelse på  N  = 1024.

Overlappende inputblokke

Denne metode anvender en blokstørrelse svarende til FFT -størrelsen (1024). Vi beskriver det først i form af normal eller lineær konvolvering. Når en normal foldning udføres på hver blok, der er start-up og henfald transienter ved de blokkanter, på grund af filtret latenstid (200-prøver). Kun 824 af konvolutionsudgangene påvirkes ikke af kanteffekter. De andre kasseres, eller simpelthen ikke beregnes. Det ville forårsage huller i output, hvis inputblokkene er sammenhængende. Mellemrummene undgås ved at overlappe inputblokkene med 200 prøver. På en måde "gemmes" 200 elementer fra hver inputblok og overføres til den næste blok. Denne metode kaldes overlap-gem , selvom den metode, vi beskriver derefter, kræver en lignende "gem" med output-prøverne.

Når en FFT bruges til at beregne de 824 upåvirkede DFT-prøver, har vi ikke mulighed for ikke at beregne de berørte prøver, men de forreste og bagkantseffekter overlappes og tilføjes på grund af cirkulær konvolvering. Følgelig indeholder 1024-punkts invers FFT (IFFT) output kun 200 prøver af kanteffekter (som kasseres) og de 824 upåvirkede prøver (som opbevares). For at illustrere dette viser den fjerde ramme i figuren til højre en blok, der periodisk (eller "cirkulært") er forlænget, og den femte ramme viser de enkelte komponenter i en lineær konvolution udført på hele sekvensen. Kanteffekterne er, hvor bidragene fra de udvidede blokke overlapper bidragene fra den originale blok. Den sidste ramme er den sammensatte udgang, og sektionen farvet grøn repræsenterer den upåvirkede del.

Overlappende outputblokke

Denne metode er kendt som overlap-tilføjelse . I vores eksempel bruger den sammenhængende inputblokke af størrelse 824 og puder hver med 200 nulværdierede prøver. Derefter overlapper den og tilføjer 1024-elementets outputblokke. Intet kasseres, men 200 værdier for hver outputblok skal "gemmes" for tilføjelsen med den næste blok. Begge metoder fremfører kun 824 prøver pr. 1024-punkts IFFT, men overlap-gemme undgår den indledende nulpolstring og sidste tilføjelse.

Se også

• Konvolutionssætning
• Cirkulerende matrix
• Diskret Hilbert -transformering

Sideanvisninger

Referencer