Convoluția secvențelor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 9 noiembrie 2021; verificările necesită 4 modificări .

Convoluția secvenței este o transformare liniară a două secvențe numerice . Rezultatul convoluției este o secvență ale cărei elemente se obțin prin înmulțirea și însumarea elementelor secvențelor originale în așa fel încât membrii unei secvențe să fie luați cu indici crescători, iar membrii celeilalte - cu descrescători (ceea ce servește ca bază pentru denumirea acceptată a acestei operațiuni). Există convoluții liniare și ciclice, care sunt utilizate pentru secvențe finite și, respectiv, periodice.

Convoluția secvențelor și se notează ca . $A$ $b$ $a*b$

Plierea secvenței este un caz special de pliere cu funcție . Convoluția este, de asemenea, strâns legată de corelația încrucișată .

Tipuri de pliere

Tipurile tradiționale de pachete includ:

convoluție liniară (aperiodică);
convoluție ciclică (circulară, periodică);
convoluție folosind transformata Fourier discretă.

Calculul convoluției

Luați în considerare regulile și succesiunea pentru calcularea fiecărui tip de convoluție.

Calcul de convoluție liniară

Să fie date două secvențe numerice:

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

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

Pentru a calcula convoluția liniară a acestor secvențe, trebuie să efectuați următorii pași:

calculați numărul de elemente ale secvenței de ieșire folosind formula:

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

Unde:

N_{{out}}

este numărul de elemente din secvența de ieșire;

N_1

este numărul de elemente din prima secvență;

N_2

este numărul de elemente din a doua secvență;

tamponați ambele secvențe cu zerouri astfel încât numărul de elemente din ambele secvențe să fie egal cu ; $N_{{out}}$

afișați simetric una dintre secvențe în raport cu axa y;

înmulțiți aceste două secvențe.

În urma efectuării tuturor operațiilor descrise mai sus, obținem o convoluție liniară a șirurilor și , ale căror elemente sunt calculate prin una dintre cele două formule: $c$ $A$ $b$

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

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

Aici se presupune că pentru , elementele secvenței corespunzătoare sunt egale cu zero. $ik<0$

Puteți verifica echivalența formulelor și, ca urmare, comutativitatea operației de convoluție prin simpla înlocuire a indicilor într-una dintre formule. $j=ik$

Calculul convoluției ciclice

Luați în considerare acum două secvențe numerice de aceeași lungime : $N$

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

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

Pentru a obține o circumvoluție circulară periodică , este necesar să ne imaginăm că aceste secvențe sunt situate pe două cercuri, dintre care unul se află în interiorul celuilalt. Valorile fiecăreia dintre aceste secvențe sunt echidistante unele de altele. Pentru a obține fiecare valoare a convoluției circulare, este necesar să ne imaginăm că una dintre secvențe se mișcă într-un cerc față de cealaltă în sensul acelor de ceasornic. Mai întâi, luați prima valoare a secvenței care se rotește, înmulțiți succesiv cu valorile altei secvențe și însumați rezultatele înmulțirilor și obțineți prima valoare a secvenței de ieșire . Apoi repetăm aceste acțiuni pentru fiecare valoare a secvenței care se rotește față de cealaltă. Numărul de elemente din secvența de ieșire va fi . $c'$ $c'$ $N$

Cu alte cuvinte, elementele convoluției ciclice sunt calculate prin formula $c'$

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

unde . $((ik))=(ik){\bmod {N}}$

Secvența rezultată este echivalentă cu convoluția a două semnale periodice, adică secvențele și poate fi considerată ca definită pentru toate prin formulele și . $A$ $b$ $i\in \mathbb {Z}$ ${\displaystyle a_{i}=a_{((i))))$ ${\displaystyle b_{i}=b_{((i))))$

Calculul convoluției aperiodice

Pentru a obține o convoluție aperiodică se efectuează toate aceleași operații ca și pentru obținerea unei convoluții circulare, dar secvențele pot avea un număr diferit de elemente (de exemplu, și ) și trebuie completate cu zerouri la numărul de . La efectuarea acestui tip de convoluție, efectul de suprapunere circulară, care apare cu convoluția circulară, este eliminat. Aceasta este o modalitate alternativă de a calcula convoluția liniară. $N_1$ $N_2$ $N_{out}=N_{1}+N_{2}-1$

Relația dintre convoluțiile liniare și ciclice

Abordarea descrisă mai sus face posibilă stabilirea unei legături între calculul convoluțiilor liniare și ciclice. Pentru a face acest lucru, în formula pentru elementele convoluției ciclice, împărțim suma la două, corespunzătoare cazurilor și : $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}.

Presupunând acum că în prima sumă la , și în a doua sumă la , putem schimba limitele de însumare și obținem o relație între convoluțiile liniare și ciclice sub forma $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.

Convoluția liniară poate fi calculată ca ciclică dacă al doilea termen din această formulă este egal cu zero, adică produsele pentru toate și sunt egale cu zero . Pentru a se asigura că această condiție este îndeplinită, se poate alege lungimea convoluției ciclice astfel încât să nu fie mai mică de , în timp ce se completează secvențele de intrare cu zerouri. $a_{k}b_{N+ik)$ $i$ $k$ $N$ $N_{out}=N_{1}+N_{2}-1$

Calcularea unei convoluții folosind transformata Fourier

Pentru a calcula convoluția folosind transformata Fourier discretă, este necesar să se adauge ambele secvențe de intrare cu zerouri, astfel încât numărul de elemente din aceste secvențe să fie egal cu . În continuare, este necesar să se efectueze transformări Fourier directe ale fiecărei secvențe. Apoi secvențele transformate sunt înmulțite element cu element, după care se realizează transformarea inversă a rezultatului înmulțirii. $N_{{out}}$

Calculul convoluției în modul descris este fezabil datorită teoremei de convoluție.

Pentru a verifica corectitudinea calculelor unei convoluții liniare, ciclice sau convoluții folosind transformata Fourier, puteți calcula suplimentar unul dintre celelalte două tipuri de convoluție, deoarece secvențele de ieșire trebuie să fie egale atunci când secvențele de intrare sunt aceleași.

Complexitate computațională

Calcularea unei convoluții necesită operații. Acest număr poate fi redus semnificativ prin calcularea convoluției prin diverși algoritmi rapizi. $O(N^2)$

Cel mai adesea, pentru a reduce numărul de operații, convoluția este calculată folosind două transformări Fourier, fiecare dintre acestea fiind calculată folosind algoritmi rapizi . Aceasta reduce complexitatea de calcul a operației de convoluție la . $O(N\log N)$

Reducerea dimensiunii spațiului cu convoluție multidimensională

Fie două semnale complexe discrete și date în spațiu . Definim convoluția acestor semnale ca $\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}).

Să setăm și operația de reducere a dimensiunii spațiului prin măsurarea sau însumarea semnalului ca $i_{j}$ $i_{j}$

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

Teorema. Pentru o dimensiune arbitrară a spațiului, rezultatul convoluției urmat de însumarea peste este , ceea ce este echivalent cu însumarea preliminară peste semnale și convoluția ulterioară: . $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}]$ [unu]

Exemplu de program

Mai jos este un exemplu de implementare a convoluției liniare, scris în C++ :

/* * Mărimea secvenței de ieșire este M + N - 1 */ vector < dublu > conv ( vector const < dublu >& x , vector const < dublu >& h ) { dacă (( x . dimensiune () == 0 ) && ( h . dimensiune () == 0 )) { vector return < dublu > (); } vector < dublu > a ; vector < dublu > b ; dacă ( x .size () < h .size ( ) ) { a = x _ b = h _ } altfel { a = h _ b = x ; } vector < dublu > rezultat ( a . dimensiune () + b . dimensiune () - 1 , 0 ); pentru ( size_t k = 0 ; k < a . size (); k ++ ) { pentru ( dimensiunea_t l = 0 ; l < b . dimensiunea (); l ++ ) { rezultat [ l + k ] += a [ k ] * b [ l ]; } } returnează rezultatul ; }

Vezi și

Convoluția secțională

Note

↑ Grishentsev A. Yu., Korobeinikov A. G. Reducerea dimensiunii spațiului în timpul corelării și convoluției semnalelor digitale // Izv. universități. Instrumentaţie. : imprimat. - 2016. - Nr 3 . - S. 211-218 . — ISSN 0021-3454 . Arhivat din original pe 12 mai 2016.

Literatură

Rabiner L., Gould B. Capitolul 2. Teoria sistemelor discrete liniare // Teoria și aplicarea procesării semnalelor digitale. - M . : Mir, 1978. - S. 72-81. — 848 p.
Blahut R.Algoritmi rapidi de procesare a semnalului digital. — M.: Mir , 1989.