Sektionsfalsning

Sektionerad (partitionerad) faltning är en metod för att beräkna faltning som används när antalet element i en av ingångssekvenserna är många gånger större än antalet element i den andra [1] . Grundläggande metoder för beräkning av sektionsfaltning - Överlappning med summeringoch staplade överlappande metod.

Beräkning

Låta vara en obunden sekvens, vara en sekvens av längd , och vara något naturligt tal . ${\displaystyle x=\{x(1),x(2),\ldots \))$ ${\displaystyle h=\{h(1),\ldots ,h(N)\))$ $N$ $L$

Överlappningsmetod med summering

För att beräkna en linjär faltning med överlappningssummametoden är det nödvändigt att dela upp sekvensen i angränsande längdsektioner : $y=x*h$ $x$ $L$

x(n)=\sum \limits _{k=0}^{+\infty }x_{k}(n),

var

x_{k}(n)=\left\{{\begin{array}{rl}x(n),&n\in [kL,\,(k+1)L-1],\\0 ,&n\noti [kL,\,(k+1)L-1].\end{array}}\right.

Sedan

y(n)=\summa \limits _{m=0}^{N-1}h(m)\summa \limits _{k=0}^{+\infty }x_{k}(nm )=\summa \limits _{k=0}^{+\infty }h(n)*x_{k}(n)=\summa \limits _{k=0}^{+\infty }y_{k }(n).

Längden på var och en av de partiella varvningarna i denna summa är lika med , det vill säga det finns en längdsektion på vilken de -: e och -te partiella varvningarna överlappar varandra, så deras avläsningar i det överlappande området måste läggas till. Därav namnet på denna metod [2] . $L+N-1$ $N-1$ $k$ $(k+1)$

Staplad överlappningsmetod

Låt nu längden på sektionerna i sekvensen vara lika och dessa sektioner har överlappande längdsektioner . För varje avsnitt beräknas en cyklisk faltning och , som innehåller ett antal och betecknas med , . Det är nödvändigt att kassera de sista proverna av denna sekvens och bifoga resten till sekvensen . Efter att ha utfört denna procedur kommer den erforderliga sekvensen att erhållas för varje [3] . $x_k$ $x$ $L+N-1$ $N-1$ $h$ $x_k$ $L+N-1$ $y_{k}$ $N-1$ $y_{k-1}$ $k$ $y=x*h$

Notera

Det är bekvämt att välja ett tal så att talet blir en potens av två. Sedan kan var och en av de partiella faltningarna utföras effektivt med hjälp av snabba algoritmer , vilket avsevärt minskar beräkningskomplexiteten . $L$ $L+N-1$

Anteckningar

↑ Rabiner, Gould 1978 , sid. 76.
↑ Rabiner, Gould 1978 , sid. 76-78.
↑ Rabiner, Gould 1978 , sid. 78-81.

Litteratur

Rabiner, L. , Gould, B. Teori och tillämpning av digital signalbehandling. —M.:Mir, 1978.