Sorozatok konvolúciója

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 9-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A szekvenciakonvolúció két numerikus sorozat lineáris transzformációja . A konvolúció eredménye egy sorozat, amelynek elemeit úgy kapjuk meg, hogy az eredeti sorozatok elemeit úgy szorozzuk és összegezzük, hogy az egyik sorozat tagjait növekvő, a másiké pedig csökkenő indexekkel vegyük (ami arra szolgál e művelet elfogadott elnevezésének alapjaként). Léteznek lineáris és ciklikus konvolúciók, amelyeket véges, illetve periodikus sorozatokhoz használunk.

A és sorozatok konvolúcióját jelöljük . $a$ $b$ $a*b$

A szekvenciális hajtogatás a funkciós hajtogatás speciális esete . A konvolúció szintén szorosan összefügg a keresztkorrelációval .

Hajtási típusok

A hagyományos kötegek a következők:

lineáris (periodikus) konvolúció;
ciklikus (körkörös, periodikus) konvolúció;
konvolúció a diszkrét Fourier transzformáció segítségével.

Konvolúció számítás

Tekintsük az egyes konvolúciótípusok kiszámításának szabályait és sorrendjét.

Lineáris konvolúció számítás

Adjunk meg két numerikus sorozatot:

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

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

Ezen sorozatok lineáris konvolúciójának kiszámításához a következő lépéseket kell végrehajtania:

számítsa ki a kimeneti sorozat elemeinek számát a képlet segítségével:

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

ahol:

N_{{out}}

a kimeneti sorozat elemeinek száma;

N_1

az első sorozat elemeinek száma;

N_2

a második sorozat elemeinek száma;

mindkét sorozatot nullákkal töltse be úgy, hogy mindkét sorozat elemeinek száma egyenlő legyen ; $N_{{out}}$

szimmetrikusan jelenítse meg az egyik sorozatot az y tengelyhez képest;

szorozzuk meg ezt a két sorozatot.

A fent leírt műveletek végrehajtása eredményeként a és sorozatok lineáris konvolúcióját kapjuk , amelynek elemeit két képlet egyikével számítjuk ki: $c$ $a$ $b$

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

vagy

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

Itt feltételezzük, hogy - esetén a megfelelő sorozat elemei egyenlők nullával. $ik<0$

A képletek ekvivalenciáját és ennek eredményeként a konvolúciós művelet kommutativitását úgy ellenőrizheti , hogy egyszerűen lecseréli az indexeket valamelyik képletben. $j=ik$

Ciklikus konvolúció számítása

Tekintsünk most két azonos hosszúságú numerikus sorozatot : $N$

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

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

A periodikus körkörös konvolúció eléréséhez el kell képzelni, hogy ezek a sorozatok két körön helyezkednek el, amelyek közül az egyik a másik belsejében van. Ezen sorozatok értékei egyenlő távolságra vannak egymástól. A körkörös konvolúció minden egyes értékének megszerzéséhez el kell képzelni, hogy az egyik sorozat a másikhoz képest körben mozog az óramutató járásával megegyező irányban. Először vegye a forgó sorozat első értékét, szorozza meg egymás után egy másik sorozat értékeivel, és összegezze a szorzások eredményeit, és kapja meg a kimeneti sorozat első értékét . Ezután megismételjük ezeket a műveleteket a sorozat minden egyes értékére, amely a másikhoz képest forog. A kimeneti sorozat elemeinek száma . $c'$ $c'$ $N$

Más szóval, a ciklikus konvolúció elemeit a képlet számítja ki $c'$

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

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

A kapott sorozat ekvivalens két periodikus jel, azaz a sorozatok konvolúciójával, és az és a képletekkel mindenkire meghatározottnak tekinthető . $a$ $b$ $i\in \mathbb {Z}$ ${\displaystyle a_{i}=a_{((i))))$ ${\displaystyle b_{i}=b_{((i))))$

Az aperiodikus konvolúció számítása

Az aperiodikus konvolúció eléréséhez ugyanazokat a műveleteket hajtjuk végre, mint a körkörös konvolúció esetén, de a sorozatok eltérő számú elemet tartalmazhatnak (például és ), és azokat nullákkal kell kitölteni a számhoz . Az ilyen típusú konvolúció végrehajtása során a körkörös átfedés hatása, amely körkörös konvolúciónál jelentkezik, megszűnik. Ez egy alternatív módszer a lineáris konvolúció kiszámítására. $N_1$ $N_2$ $N_{out}=N_{1}+N_{2}-1$

Lineáris és ciklikus konvolúciók kapcsolata

A fent leírt megközelítés lehetővé teszi a lineáris és ciklikus konvolúciók számítása közötti kapcsolat létrehozását. Ehhez a ciklikus konvolúció elemeinek képletében az összeget elosztjuk kettővel, az és eseteknek megfelelően : $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}.

Feltételezve, hogy most az első összegben van , és a második összegben at , megváltoztathatjuk az összegzési határokat, és összefüggést kaphatunk a lineáris és ciklikus konvolúciók között a következő formában: $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.

A lineáris konvolúció akkor számítható ciklikusnak, ha a képlet második tagja egyenlő nullával, vagyis az összes és a szorzata nullával egyenlő . Ennek a feltételnek a teljesülése érdekében kiválaszthatjuk a ciklikus konvolúció hosszát úgy, hogy az ne legyen kisebb, mint , miközben a bemeneti sorozatokat nullákkal töltjük fel. ${\displaystyle a_{k}b_{N+ik))$ $én$ $k$ $N$ $N_{out}=N_{1}+N_{2}-1$

Konvolúció kiszámítása a Fourier-transzformáció segítségével

A diszkrét Fourier-transzformáció segítségével történő konvolúció kiszámításához mindkét bemeneti sorozatot nullákkal kell feltölteni, hogy az elemek száma ezekben a sorozatokban egyenlő legyen . Ezután az egyes sorozatok közvetlen Fourier-transzformációját kell végrehajtani. Ezután a transzformált sorozatokat elemenként megszorozzuk, majd végrehajtjuk a szorzási eredmény inverz transzformációját. $N_{{out}}$

A konvolúció leírt módon történő kiszámítása a konvolúciós tételnek köszönhetően megvalósítható.

Egy lineáris, ciklikus vagy konvolúció számításának helyességének ellenőrzéséhez a Fourier-transzformáció segítségével a másik két konvolúciótípus egyikét is kiszámíthatja, mivel a kimeneti sorozatoknak egyenlőnek kell lenniük, ha a bemeneti sorozatok azonosak.

Számítási összetettség

A konvolúció kiszámítása műveleteket igényel . Ez a szám jelentősen csökkenthető a konvolúció különböző gyors algoritmusokkal történő kiszámításával. $O(N^2)$

Leggyakrabban a műveletek számának csökkentése érdekében a konvolúciót két Fourier-transzformáció segítségével számítják ki, amelyek mindegyikét gyors algoritmusokkal számítják ki . Ez a konvolúciós művelet számítási bonyolultságát -ra csökkenti . $O(N\log N)$

A tér dimenziójának csökkentése többdimenziós konvolúcióval

Legyen két diszkrét komplex jel és legyen megadva térben . Ezeknek a jeleknek a konvolúcióját a következőképpen definiáljuk $\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}).

Állítsuk be a tér méretének csökkentésének műveletét is úgy, hogy a jelet as -on mérjük vagy összegezzük $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.

Tétel. A tér egy tetszőleges dimenziója esetén a konvolúció eredménye, amelyet az összegzés követ , ami megegyezik a jelek feletti előzetes összegzéssel és az azt követő konvolúcióval: . $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}]$ [egy]

Programpélda

Az alábbiakban egy példa a lineáris konvolúció megvalósítására, C++ nyelven írva :

/* * A kimeneti sorozat mérete M + N - 1 */ vektor < double > conv ( const vektor < double >& x , const vektor < double >& h ) { if (( x . méret () == 0 ) && ( h . méret () == 0 )) { visszatérési vektor < double > (); } vektor < double > a ; vektor < double > b ; if ( x .size () < h .size ( ) ) { a = x _ b = h _ } másik { a = h _ b = x ; } vektor < double > eredmény ( a . méret () + b . méret () - 1 , 0 ); for ( méret_t k = 0 ; k < a . méret (); k ++ ) { for ( méret_t l = 0 ; l < b . méret (); l ++ ) { eredmény [ l + k ] += a [ k ] * b [ l ]; } } eredmény visszaadása ; }

Lásd még

Metszetkonvolúció

Jegyzetek

↑ Grishentsev A. Yu., Korobeinikov A. G. A tér dimenziójának csökkentése a digitális jelek korrelációja és konvolúciója során // Izv. egyetemek. Hangszerelés. : nyomtatott. - 2016. - 3. sz . - S. 211-218 . — ISSN 0021-3454 . Az eredetiből archiválva: 2016. május 12.

Irodalom

Rabiner L., Gould B. 2. fejezet: Lineáris diszkrét rendszerek elmélete // A digitális jelfeldolgozás elmélete és alkalmazása. - M . : Mir, 1978. - S. 72-81. — 848 p.
Blahut R.Gyors digitális jelfeldolgozó algoritmusok. — M.: Mir , 1989.