Convolució

De Viquipèdia
Dreceres ràpides: navegació, cerca
Convolució de dos polsos quadrats (La funció resultant acaba sent un pols triangular)
Convolució d'un pols qauadrat (com a senyal d'entrada) amb la resposta l'impuls d'un condensador per a obtenir el senyal de sortida (resposta del condensador a aquest senyal)

La convolució és una operació matemàtica que transforma dues funcions en una tercera funció que representa la magnitud de superposició de les dues funcions originals. La seva operació es representa amb el símbol *. Les seves aplicacions inclouen estadística, visió per ordinador, processament d'imatges i senyals, enginyeria de telecomunicació i equacions diferencials. Matemàticament es defineix de la següent manera:

(f * g )(t)\ \ \,{=}\ \int_{-\infty}^{\infty} f(\tau)*g(t-\tau)\,d\tau

A més a més, hi ha tres mètodes gràfics per resoldre les convolucions: el lineal, el de malles i el circular. La convolució de f i g es denota f*g, i es defineix com la integral del producte de les dues funcions després desplaçada una distància τ, com es mostra a continuació:

f (t) * g (t) = \int f(\tau) g(t - \tau) d\tau


El rang d'integració depèn del domini sobre el que estan definides les funcions. En el cas d'un rang d'integració finit, f i g es consideren com a esteses, periòdicament en dues direccions, tal que el terme g(t-τ) no implica una violació en el rang. Quan s'utilitzen aquests dominis periòdics la convolució a vegades es diu cíclica. També és possible estendre amb zeros els dominis. El nom utilitzat quan s'utilitza aquesta tècnica de dominis "zero-estesos" o bé els infinits és el de convolució lineal, especialment en el cas discret que es presenta també en aquest article. El resultat final de g(x) només serà determinat per la funció f(x) en el punt t, però no de la posició de t. Aquesta propietat s'anomena invariant respecte a la posició (position-invariant) i és una condició necessària en la definició d'integrals de convolució.

Si X i Y són dues variables aleatòries independents amb funcions de densitat de probabilitat f i g, respectivament, llavors la densitat de probabilitat de la suma X + Y vindrà donada per la convolució f * g.

Per les funcions discretes es pot utilitzar d'una manera discreta la convolució, és a dir:

 f[m] * g[m] = \sum_n {f[n] g[m - n]} \,

Quan es multipliquen dos polinomis, els coeficients del producte estan donats per la convolució de les successions originals de coeficients, en el sentit donat aquí (utilitzant extensions amb zeros com hem mencionat).

Generalitzant els casos anteriors, la convolució pot ser definida per qualssevol dues funcions quadrades-integrables definides sobre un grup topològic localment compacte. Una generalització diferent és la convolució de distribucions.

Tipus de Convolució[modifica | modifica el codi]

Convolució Discreta

Quan es tracta de fer un processament digital de senyal no té sentit parlar de convolucions aplicant estrictament la definició, ja que només disposem de valors en instants discrets de temps. Cal, doncs, una aproximació numèrica. Per a realitzar la convolució entre dos senyals, s'avaluarà l'àrea de la funció:  x(\tau)*h(t-\tau)\,. Per a això, disposem de mostrejos dels dos senyals en els instants de temps  nt \,, que anomenarem  x[k]\, y  h[n-k]\, (on n i k són enters). L'àrea és, per tant,

 y[n]=[\sum_{k=-\infty}^{\infty} t*x[k]*h[n-k]]=t*[\sum_{k=-\infty}^{\infty} x[k]*h[n-k]],

La convolució discreta es determina per un interval de mostreig  t=1  :

y[n]=x[n]*h[n]=[\sum_{k=-\infty}^{\infty} x[k]*h[n-k]]

Convolució Circular

Quan una funció g_T(t) és periòdica, amb un període de T, llavors les funcions, f, com ara f * g_T(t) existents, la seva convolució és també periòdica i igual a:

(f * g_T)(t) \equiv \int_{t_0}^{t_0+T} \left[\sum_{k=-\infty}^{\infty} f(\tau + kT)\right] g_T(t - \tau)\ d\tau,\,

On es tria arbitràriament. La suma és anomenada com una extensió periòdica de la funció f.

Si GT és una extensió periòdica d'una altra funció, g, llavors f * GT se sap que és circular, cíclica, o periòdica d'una convolució de fil g.

Mètode per calcular la convolució circular:

Tenim 2 cercles, un exterior i un altre interior. Anem girant el cercle interior i sumant els seus valors. Si els dos cercles tenen diferents mides, llavors el més petit hi afegim "0" a l'inici, al final o l'inici i final. [L >= L1 + L2-1]

Convolució lineal[modifica | modifica el codi]

Consisteix a fer unes taules on en cada cas els membres de les dues funcions es troben desplaçats una posició, de manera que es comença amb les dues funcions compartint un sol membre, en la segona taula en comparteixen 2, i així anar fent fins que les dues funcions s'han desplaçat una sobre l'altra i tornen a compartir un sol membre. En cada taula es fa el producte entre els membres que coincideixen en la mateixa columna i se sumen els productes de les columnes. A continuació hi ha un exemple:

x[n] = [4 1 3]
y[n] = [2 5]
c[n] = y[n]*x[n]
[0 4 1 3] i [2 5 0 0], resultat = 5*4 = 20
[4 1 3] i [2 5 0], resultat = 5*1 + 2*4 = 13
[4 1 3] i [0 2 5], resultat = 5*3 + 2*1 = 17
[4 1 3 0] i [0 0 2 5], resultat = 2*3 = 6

El resultat final de la convolució és el següent:

c[n] = [20 13 17 6].

Propietats[modifica | modifica el codi]

Les propietats dels diferents operadors de convolució són 12

Commutativitat[modifica | modifica el codi]

f * g = g * f \,

Associativitat[modifica | modifica el codi]

f * (g * h) = (f * g) * h \,

Distributivitat[modifica | modifica el codi]

f * (g + h) = (f * g) + (f * h) \,

Associativitat amb multiplicació escalar[modifica | modifica el codi]

a (f * g) = (a f) * g = f * (a g) \,

per a tot nombre complex o real a.

Regla de derivació[modifica | modifica el codi]

\mathcal{D}(f * g) = \mathcal{D}f * g = f * \mathcal{D}g \,

on Df és la derivada de f o, en el cas discret, l'operador diferència

\mathcal{D}f(n) = f(n+1) - f(n).

Teorema de convolució[modifica | modifica el codi]

\mathcal{F}(f * g) ={(\mathcal{F} (f)) \cdot (\mathcal{F} (g))}

on \mathcal{F} és la Transformada de Fourier de f. Aquest teorema també es compleix amb la Transformada de Laplace.

Matriu de convolució[modifica | modifica el codi]

A vegades és útil veure la convolució com un producte matricial, sigui x[n] una funció discreta de n elements, sigui h[n] un sistema discret de n elements i sigui y la resposta a la convolució de (2*n)-1 elements, llavors y[m]=x[n] * h[n] es pot expressar pel següent producte matricial.



 \begin{bmatrix}
 x[0] \\
 x[1] \\
 x[2] \\
. \\
. \\
. \\
 x[n]
 \end{bmatrix}

S'opera de la següent manera: 
 \begin{bmatrix}
 h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-1\\
 0 & h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-2\\
 0 & 0 & h[0] & h[1] & h[2] & ... & h[n] & 0_k & ... & 0_2*n-3\\
. \\
. \\
. \\
 0 & 0 & ... & h[0] & h[1] & h[2] & ... & h[n] \\
 \end{bmatrix}
= 
 \begin{bmatrix}
 y[0] \\
 y[1] \\
 y[2] \\
. \\
. \\
. \\
 y[2*n-1]
 \end{bmatrix}

exempl esigui

x[n]=  [4, 5, 1, 7] i sigui h[n]= [1, 2, 3, 1]

llavors la matriu de convolució serà 
 \begin{bmatrix}
 1 & 2 & 3 & 1 & 0 & 0 & 0\\
 0 & 1 & 2 & 3 & 1 & 0 & 0\\ 
 0 & 0 & 1 & 2 & 3 & 1 & 0\\ 
 0 & 0 & 0 & 1 & 2 & 3 & 1\\ 
 \end{bmatrix}

S'afegeixen zeros a tots dos cantons. Això es fa per a poder igualar i així poder fer la convolució. Aquesta tècnica és coneguda com a zero-padding.

Zero Padding[modifica | modifica el codi]

Consisteix en afegir 0 a una convolució o a l'espectre d'un senyal, en aquest últim cas augmentem el domini freqüencial del senyal, però no es millora la resolució.

Algoritmes ràpids de convolució[modifica | modifica el codi]

En moltes situacions, convolucions discretes es poden convertir en convolucions circulars de manera que podem aplicar transformacions ràpides amb una determinada caràcteqistica de la convolució i implementar-ho al computador. Per exemple, la convolució de seqüències de dígits és el funcionament del nucli d'un computador en la multiplicació de nombres de diversos dígits, que per tant pot ser implementat de manera eficient amb les tècniques de transformació (Knuth 1997, § 4.3.3.C; von zur Gather i Gerhard 2003, § 8.2).

Convolucions de grups[modifica | modifica el codi]

Si G és un grup dotat d'una mesura m i si f i g són funcions reals -o complexes- valuades i m-integrables de G, llavors podem definir la seva convolució com:

(f * g)(x) = \int_G f(y)g(xy^{-1})\,dm(y) \,

En aquest cas també és possible donar, per exemple, un teorema de convolució, encara que sigui molt més difícil de presentar i que requereixi la teoria de la representació per a aquests tipus de grups així com el Teorema de Peter-Weyl de l'Anàlisi harmònica. És molt difícil fer aquests càlculs sense més estructura i els grups de Lie són els marcs on s'han de fer les coses.

Convolucions amb deltes de Dirac[modifica | modifica el codi]

 f(t) * \delta(t) = f(t) \,
 f(t) * \delta(t-to) = f(t-to) \,
 f(t-t1) * \delta(t-to) = f(t-to-t1) \,

Bialgebra[modifica | modifica el codi]

Sigui (X, Δ, ∇, εη) una bialgebra amb comultiplicatió Δ, multiplicació ∇, unitat η, i counitat ε. La convolució és un producte definit en l'endomorfisme algebraic End(X). Sigui φ, ψ ∈ End(X), això és, φ,ψ : X → X són funcions que respecten tota 'estructura algebraica de X, llavors la convolució φ∗ψ és definida com una composició.

X \xrightarrow{\Delta} X\otimes X \xrightarrow{\phi\otimes\psi} X\otimes X \xrightarrow{\nabla} X. \,

La convolució apareix sobretot en la definició de l'àlgebra de Hopf (Kassel 1995, §III.3). Un biàlgebra és un àlgebra de Hopf si i només si té un antípoda: un endomorfisme a S de manera que:

S * \operatorname{id}_X = \operatorname{id}_X * S = \eta\circ\varepsilon.


Aplicacions[modifica | modifica el codi]

La convolució i les operacions relacionades es troben a moltes aplicacions en enginyeria i matemàtica:

  • A enginyeria de telecomunicació i en altres disciplines, la sortida d'un sistema lineal (estacionari, invariable en el temps, o invariable en l'espai, el que es coneix com a Sistema LTI) és la convolució de l'entrada amb la resposta del sistema a un impuls determinat.
  • Al processament digital d'imatges, la convolució es un dels algorismes més importants alhora de tractar les imatges. Millora del contrast, millora de la resolució, detecció de vores, són alguns dels processos afins que mitjançant "filtres" utilitzem més freqüentment.
  • A l'òptica, molts tipus de "taques" es descriuen amb convolucions. Una ombra (per exemple, l'ombra sobre la taula quan tenim la mà entre aquesta i la font de llum) és la convolució de la forma de la font de llum que crea l'ombra i de l'objecte l'ombra del qual s'està projectant. Una fotografia desenfocada és la convolució de la imatge correcta amb el cercle borrós format pel diafragma de l'iris. El terme fotogràfic d'aquest efecte és enfocament selectiu (bokeh).
  • A l'acústica, un eco és la convolució del so original amb una funció que representi els objectes variats que el reflecteixin.
  • A la física, on hi hagi un sistema lineal amb un "principi de superposició", apareix una operació de convolució.
  • A l'estadística, una mitjana mòbil ponderada és una convolució.
  • A la teoria de la probabilitat, la distribució de probabilitat de la suma de dues variables aleatòries independents és la convolució de cadascuna de les seves distribucions de probabilitat.
  • Als sistemes de planificació de tractament per radioteràpia, gran part de tots els codis de càlcul moderns apliquen algorismes de convolució-superposició.
  • La convolució amplifica o atenua cada component de freqüència de l'entrada de forma independent dels altres components.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Convolució Modifica l'enllaç a Wikidata