Konvolution av sekvenser

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 november 2021; kontroller kräver 4 redigeringar .

Sekvensfaltning är en linjär transformation av två numeriska sekvenser . Resultatet av faltningen är en sekvens vars element erhålls genom att multiplicera och summera elementen i de ursprungliga sekvenserna på ett sådant sätt att medlemmarna i en sekvens tas med ökande index, och medlemmarna i den andra - med minskande (vilket tjänar som grund för det accepterade namnet på denna operation). Det finns linjära och cykliska faltningar, som används för ändliga respektive periodiska sekvenser.

Konvolutionen av sekvenser och betecknas som . $a$ $b$ $a*b$

Sekvensvikning är ett specialfall av funktionsvikning . Konvolution är också nära relaterat till korskorrelation .

Viktyper

De traditionella typerna av buntar inkluderar:

linjär (aperiodisk) faltning;
cyklisk (cirkulär, periodisk) faltning;
faltning med användning av den diskreta Fouriertransformen.

Konvolutionsberäkning

Tänk på reglerna och sekvensen för beräkning av varje typ av faltning.

Linjär faltningsberäkning

Låt två numeriska sekvenser ges:

a=\left\{a_{0},a_{1},\ldots ,a_{N_{1}-1}\right\},

b=\left\{b_{0},b_{1},\ldots ,b_{N_{2}-1}\right\}.

För att beräkna den linjära faltningen av dessa sekvenser måste du utföra följande steg:

beräkna antalet element i utdatasekvensen med formeln:

N_{{out}}=N_{1}+N_{2}-1,

var:

N_{{ut}}

är antalet element i utdatasekvensen;

N_1

är antalet element i den första sekvensen;

N_2

är antalet element i den andra sekvensen;

fylla båda sekvenserna med nollor så att antalet element i båda sekvenserna är lika med ; $N_{{ut}}$

visa symmetriskt en av sekvenserna med avseende på y-axeln;

multiplicera dessa två sekvenser.

Som ett resultat av att utföra alla operationer som beskrivs ovan får vi en linjär faltning av sekvenserna och , vars element beräknas med en av två formler: $c$ $a$ $b$

c_{i}=\sum \limits _{k=0}^{N_{1}-1}a_{k}b_{ik},\;i=0,\ldots ,N_{out}- ett,

eller

c_{i}=\sum \limits _{k=0}^{N_{2}-1}a_{ik}b_{k},\;i=0,\ldots ,N_{out}- ett.

Här antas det att för , elementen i motsvarande sekvens är lika med noll. $ik<0$

Du kan verifiera ekvivalensen av formlerna och, som ett resultat, kommutativiteten för faltningsoperationen genom att helt enkelt ersätta indexen i en av formlerna. $j=ik$

Cyklisk faltningsberäkning

Betrakta nu två numeriska sekvenser av samma längd : $N$

a=\left\{a_{0},a_{1},\ldots ,a_{N-1}\right\},

b=\left\{b_{0},b_{1},\ldots ,b_{N-1}\right\}.

För att få en periodisk cirkulär faltning är det nödvändigt att föreställa sig att dessa sekvenser är belägna på två cirklar, varav den ena är inuti den andra. Värdena för var och en av dessa sekvenser är lika långt från varandra. För att erhålla varje värde på den cirkulära faltningen är det nödvändigt att föreställa sig att en av sekvenserna rör sig i en cirkel i förhållande till den andra i medurs riktning. Ta först det första värdet av sekvensen som roterar, multiplicera successivt med värdena för en annan sekvens och summera resultatet av multiplikationerna och få det första värdet av utdatasekvensen . Sedan upprepar vi dessa åtgärder för varje värde i sekvensen som roterar i förhållande till det andra. Antalet element i utdatasekvensen kommer att vara . $c'$ $c'$ $N$

Med andra ord, elementen i den cykliska faltningen beräknas med formeln $c'$

c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{((ik))},\;i=0,\ldots ,N- ett,

var . $((ik))=(ik){\bmod {N))$

Den resulterande sekvensen är ekvivalent med faltningen av två periodiska signaler, det vill säga sekvenserna och kan betraktas som definierade för alla av formlerna och . $a$ $b$ $i\in \mathbb {Z}$ ${\displaystyle a_{i}=a_{((i))))$ ${\displaystyle b_{i}=b_{((i))))$

Beräkning av aperiodisk faltning

För att erhålla en aperiodisk faltning utförs alla samma operationer som för att erhålla en cirkulär faltning, men sekvenserna kan ha ett annat antal element (till exempel och ) och de måste fyllas med nollor till antalet . När man utför denna typ av faltning elimineras effekten av cirkulär överlagring, som inträffar med cirkulär faltning. Detta är ett alternativt sätt att beräkna linjär faltning. $N_1$ $N_2$ $N_{out}=N_{1}+N_{2}-1$

Förhållandet mellan linjära och cykliska faltningar

Det ovan beskrivna tillvägagångssättet gör det möjligt att upprätta ett samband mellan beräkningen av linjära och cykliska faltningar. För att göra detta, i formeln för elementen i den cykliska faltningen delar vi summan med två, motsvarande fallen och : $ik\geqslant 0$ $ik<0$

c'_{i}=\sum \limits _{k=0}^{i}a_{k}b_{ik}+\sum \limits _{k=i+1}^{N-1 }a_{k}b_{N+ik}.

Om vi antar nu i den första summan vid , och i den andra summan vid , kan vi ändra summeringsgränserna och få ett samband mellan linjära och cykliska faltningar i formen $b_{ik}=0$ $k>i$ $b_{N+ik}=0$ $k<i$

c'_{i}=\sum \limits _{k=0}^{N-1}a_{k}b_{ik}+\sum \limits _{k=0}^{N-1 }a_{k}b_{N+ik}=c_{i}+c_{N+i},\;i=0,\ldots ,N-1.

Linjär faltning kan beräknas som cyklisk om den andra termen i denna formel är lika med noll, det vill säga produkterna för alla och är lika med noll . För att säkerställa att detta villkor är uppfyllt kan man välja längden på den cykliska faltningen så att den inte är mindre än , samtidigt som man fyller ut inmatningssekvenserna med nollor. ${\displaystyle a_{k}b_{N+ik))$ $i$ $k$ $N$ $N_{out}=N_{1}+N_{2}-1$

Beräkna en faltning med Fourier-transformen

För att beräkna faltningen med hjälp av den diskreta Fouriertransformen är det nödvändigt att fylla båda inmatningssekvenserna med nollor så att antalet element i dessa sekvenser är lika med . Därefter är det nödvändigt att utföra direkta Fourier-transformationer av var och en av sekvenserna. Därefter multipliceras de transformerade sekvenserna element för element, varefter den inversa transformationen av multiplikationsresultatet utförs. $N_{{ut}}$

Beräkningen av faltningen på det beskrivna sättet är genomförbar tack vare faltningssatsen.

För att kontrollera korrektheten av beräkningar av en linjär, cyklisk eller faltning med Fourier-transformen kan du dessutom beräkna en av de andra två typerna av faltning, eftersom utgångssekvenserna måste vara lika när ingångssekvenserna är desamma.

Beräkningskomplexitet

Att beräkna en faltning kräver operationer. Detta antal kan reduceras avsevärt genom att beräkna faltningen med olika snabba algoritmer. $O(N^2)$

Oftast, för att minska antalet operationer, beräknas faltning med två Fourier-transformer, som var och en beräknas med hjälp av snabba algoritmer . Detta minskar beräkningskomplexiteten för faltningsoperationen till . $O(N\log N)$

Minska dimensionen av rymden med flerdimensionell faltning

Låt två diskreta komplexa signaler och ges i rymden . Vi definierar faltningen av dessa signaler som $\mathbb {Z} ^{n}$ $f$ $g$ $y=f*g$

y(k_{1},\ldots ,k_{n})=\sum \limits _{i_{1}=-\infty }^{+\infty }\ldots \sum \limits _{i_{ n}=-\infty }^{+\infty }f(i_{1},\ldots ,i_{n})g(k_{1}-i_{1},\ldots ,k_{n}-i_{ n}).

Låt oss också ställa in operationen för att minska utrymmets dimension genom att mäta eller summera signalen över som $I j}$ $I j}$

f[\mathbb {Z} ^{n}-i_{j}]=\sum \limits _{i_{j}=-\infty }^{+\infty }f(i_{1},\ ldots ,i_{n}),j\in 1...n.

Sats. För en godtycklig dimension av rymden är resultatet av faltning följt av summering över , vilket motsvarar preliminär summering över signaler och efterföljande faltning: . $I j}$ $\mathbb {Z} ^{n}$ $y=f*g$ $I j}$ $y[\mathbb {Z} ^{n}-i_{j}]$ $I j}$ $f$ $g$ $y[\mathbb {Z} ^{n}-i_{j}]=f[\mathbb {Z} ^{n}-i_{j}]*g[\mathbb {Z} ^{n} -I j}]$ [ett]

Programexempel

Nedan är ett exempel på implementering av linjär faltning, skrivet i C++ :

/* * Utdatasekvensstorleken är M + N - 1 */ vektor < double > conv ( const vektor < double >& x , const vektor < double >& h ) { if (( x . storlek () == 0 ) && ( h . storlek () == 0 )) { returvektor < dubbel > ( ); } vektor < dubbel > a ; vektor < dubbel > b ; if ( x .size () < h .size ( ) ) { a = x _ b = h _ } annat { a = h _ b = x ; } vektor < dubbel > resultat ( a . storlek () + b . storlek () - 1 , 0 ); för ( storlek_t k = 0 ; k < a . storlek (); k ++ ) { för ( storlek_t l = 0 ; l < b . storlek (); l ++ ) { resultat [ l + k ] += a [ k ] * b [ l ]; } } returnera resultat ; }

Se även

Sektionsfalsning

Anteckningar

↑ Grishentsev A. Yu., Korobeinikov A. G. Reducering av rymddimensionen under korrelation och faltning av digitala signaler // Izv. universitet. Instrumentation. : tryckt. - 2016. - Nr 3 . - S. 211-218 . — ISSN 0021-3454 . Arkiverad från originalet den 12 maj 2016.

Litteratur

Rabiner L., Gould B. Kapitel 2. Teori om linjära diskreta system // Teori och tillämpning av digital signalbehandling. - M .: Mir, 1978. - S. 72-81. — 848 sid.
Blahut R.Snabba digitala signalbehandlingsalgoritmer. — M.: Mir , 1989.