Méthode de chevauchement – ​​ajout - Overlap–add method

Cet article utilise des notations abstraites courantes, telles que ou dans lesquelles il est entendu que les fonctions doivent être pensées dans leur totalité, plutôt qu'à des instants spécifiques (voir Convolution # Notation ) ${\ textstyle y (t) = x (t) * h (t),}$${\ textstyle y (t) = {\ mathcal {H}} \ {x (t) \},}$${\ textstyle t.}$

Dans le traitement du signal , la méthode de chevauchement-ajout est un moyen efficace d'évaluer la convolution discrète d'un signal très long avec un filtre à réponse impulsionnelle finie (FIR) :${\ displaystyle x [n]}$${\ displaystyle h [n]}$

Fig 1: Une séquence de cinq graphiques représente un cycle de l'algorithme de convolution avec chevauchement-ajout. Le premier tracé est une longue séquence de données à traiter avec un filtre FIR passe-bas. Le 2ème graphique est un segment des données à traiter par morceaux. Le troisième tracé est le segment filtré, y compris les transitoires de montée et de descente du filtre. Le 4ème graphique indique où les nouvelles données seront ajoutées avec le résultat des segments précédents. Le 5ème graphique est le flux de sortie mis à jour. Le filtre FIR est un passe-bas boxcar avec M = 16 échantillons, la longueur des segments est L = 100 échantillons et le chevauchement est de 15 échantillons.

${\ displaystyle y [n] = x [n] * h [n] \ \ triangleq \ \ sum _ {m = - \ infty} ^ {\ infty} h [m] \ cdot x [nm] = \ sum _ {m = 1} ^ {M} h [m] \ cdot x [nm],}$

( Éq.1 )

où h [ m ] = 0 pour m en dehors de la région [1, M ] .

Le concept est de diviser le problème en plusieurs convolutions de h [ n ] avec de courts segments de : ${\ displaystyle x [n]}$

${\ displaystyle x_ {k} [n] \ \ triangleq \ {\ begin {cases} x [n + kL], & n = 1,2, \ ldots, L \\ 0, & {\ text {sinon}}, \ end {cas}}}$

où L est une longueur de segment arbitraire. Puis:

${\ displaystyle x [n] = \ sum _ {k} x_ {k} [n-kL], \,}$

et y [ n ] peut être écrit comme une somme de courtes convolutions:

${\ displaystyle {\ begin {aligné} y [n] = \ left (\ sum _ {k} x_ {k} [n-kL] \ right) * h [n] & = \ sum _ {k} \ left (x_ {k} [n-kL] * h [n] \ right) \\ & = \ sum _ {k} y_ {k} [n-kL], \ end {aligné}}}$

où la convolution linéaire est nulle en dehors de la région [1, L + M - 1] . Et pour tout paramètre, il équivaut à la convolution circulaire à N points de avec dans la région [1, N ] . L'avantage est que la convolution circulaire peut être calculée plus efficacement que la convolution linéaire, selon le théorème de convolution circulaire :${\ Displaystyle y_ {k} [n] \ \ triangleq \ x_ {k} [n] * h [n] \,}$${\ Displaystyle N \ geq L + M-1, \,}$${\ displaystyle x_ {k} [n] \,}$${\ Displaystyle h [n] \,}$

${\ displaystyle y_ {k} [n] \ = \ \ scriptstyle {\ text {IDFT}} _ {N} \ displaystyle (\ \ scriptstyle {\ text {DFT}} _ {N} \ displaystyle (x_ {k} [n]) \ cdot \ \ scriptstyle {\ text {DFT}} _ {N} \ displaystyle (h [n]) \),}$

( Éq.2 )

où :

• DFT _N et IDFT _N font référence à la transformée de Fourier discrète et à son inverse, évaluée sur N points discrets, et
• L est habituellement choisi de telle sorte que N = L + M-1 est une puissance entière de 2, et les transformées sont implémentées avec l' algorithme FFT , pour plus d'efficacité.

Pseudocode

Ce qui suit est un pseudocode de l'algorithme:

(Overlap-add algorithm for linear convolution)
h = FIR_impulse_response
M = length(h)
Nx = length(x)
N = 8 × 2^ceiling( log2(M) )     (8 times the smallest power of two bigger than filter length M.  See next section for a slightly better choice.)
step_size = N - (M-1)  (L in the text above)
H = DFT(h, N)
position = 0
y(1 : Nx + M-1) = 0

while position + step_size ≤ Nx do
    y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H)
    position = position + step_size
end

Considérations d'efficacité

Fig 2: Un graphique des valeurs de N (une puissance entière de 2) qui minimise la fonction de coût ${\ displaystyle {\ tfrac {N \ left (\ log _ {2} N + 1 \ right)} {N-M + 1}}}$

Lorsque la DFT et l'IDFT sont implémentées par l'algorithme FFT, le pseudo-code ci-dessus nécessite environ N (log ₂ (N) + 1) multiplications complexes pour la FFT, le produit des tableaux et l'IFFT. Chaque itération produit N-M + 1 échantillons de sortie, donc le nombre de multiplications complexes par échantillon de sortie est d'environ :

${\ displaystyle {\ frac {N (\ log _ {2} (N) +1)} {N-M + 1}}. \,}$

( Éq.3 )

Par exemple, lorsque M = 201 et N = 1024, Eq.3 est égal à 13,67, alors que l'évaluation directe de l' Eq.1 nécessiterait jusqu'à 201 multiplications complexes par échantillon de sortie, le pire des cas étant lorsque x et h ont des valeurs complexes. Notez également que pour tout donnée M , Eq.3 a un minimum par rapport à N . La figure 2 est un graphique des valeurs de N qui minimisent l' Eq.3 pour une plage de longueurs de filtre (M).

Au lieu de l' Eq.1 , nous pouvons également envisager d'appliquer l' Eq.2 à une longue séquence d' échantillons de longueur . Le nombre total de multiplications complexes serait: ${\ displaystyle N_ {x}}$

${\ displaystyle N_ {x} \ cdot (\ log _ {2} (N_ {x}) + 1).}$

Comparativement, le nombre de multiplications complexes requises par l'algorithme de pseudo-code est:

${\ displaystyle N_ {x} \ cdot (\ log _ {2} (N) +1) \ cdot {\ frac {N} {N-M + 1}}.}$

D'où le coût de la méthode de chevauchement – ​​ajouter des échelles presque comme alors que le coût d'une seule grande convolution circulaire est presque . Les deux méthodes sont également comparées sur la figure 3, créée par la simulation Matlab. Les contours sont des lignes de rapport constant du temps nécessaire pour exécuter les deux méthodes. Lorsque la méthode de chevauchement-ajout est plus rapide, le rapport dépasse 1 et des rapports aussi élevés que 3 sont observés. ${\ displaystyle O \ left (N_ {x} \ log _ {2} N \ right)}$${\ displaystyle O \ left (N_ {x} \ log _ {2} N_ {x} \ right)}$

Fig 3: Gain de la méthode de chevauchement-ajout par rapport à une seule grande convolution circulaire. Les axes affichent les valeurs de longueur de signal N _x et de longueur de filtre N _h .

Voir également

• Méthode d'enregistrement par chevauchement

Remarques

Les références

Lectures complémentaires

• Oppenheim, Alan V .; Schafer, Ronald W. (1975). Traitement numérique du signal . Englewood Cliffs, NJ: Prentice-Hall. ISBN   0-13-214635-5 .
• Hayes, M. Horace (1999). Traitement numérique du signal . Série Outline de Schaum. New York: McGraw Hill. ISBN   0-07-027389-8 .

Liens externes