Sekvenssien konvoluutio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Sekvenssikonvoluutio on kahden numeerisen sekvenssin lineaarinen muunnos . Konvoluution tuloksena saadaan sekvenssi, jonka alkiot saadaan kertomalla ja summaamalla alkuperäisten sekvenssien alkiot siten, että yhden sekvenssin jäsenet otetaan kasvavilla indekseillä ja toisen jäsenet - laskevilla indekseillä (mikä palvelee tämän operaation hyväksytyn nimen perustaksi). On olemassa lineaarisia ja syklisiä konvoluutioita, joita käytetään äärellisille ja jaksollisille sekvensseille, vastaavasti.

Sekvenssien ja konvoluutio on merkitty nimellä . $a$ $b$ $a*b$

Järjestystaitto on toimintotaiton erikoistapaus . Konvoluutio liittyy myös läheisesti ristikorrelaatioon .

Taittotyypit

Perinteisiä nipputyyppejä ovat:

lineaarinen (jaksollinen) konvoluutio;
syklinen (pyöreä, jaksollinen) konvoluutio;
konvoluutio diskreetin Fourier-muunnoksen avulla.

Konvoluutiolaskenta

Harkitse kunkin konvoluutiotyypin laskemisen sääntöjä ja järjestystä.

Lineaarinen konvoluutiolaskenta

Olkoon kaksi numeerista sarjaa:

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

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

Näiden sekvenssien lineaarisen konvoluution laskemiseksi sinun on suoritettava seuraavat vaiheet:

laske tulossekvenssin elementtien lukumäärä kaavalla:

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

missä:

N_{{out}}

on lähtösekvenssin elementtien lukumäärä;

N_1

on ensimmäisen sekvenssin elementtien lukumäärä;

N_2

on elementtien lukumäärä toisessa sekvenssissä;

täytä molemmat sekvenssit nollilla siten, että molempien sekvenssien elementtien määrä on yhtä suuri kuin ; $N_{{out}}$

esittää symmetrisesti yhden sarjoista y-akselin suhteen;

kerro nämä kaksi sekvenssiä.

Suorittamalla kaikki yllä kuvatut toiminnot saadaan lineaarinen konvoluutio sarjoista ja , joiden elementit lasketaan kahdesta kaavasta: $c$ $a$ $b$

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

tai

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

Tässä oletetaan, että , vastaavan sekvenssin elementit ovat nolla. $ik<0$

Voit varmistaa kaavojen vastaavuuden ja sen seurauksena konvoluutiooperaation kommutatiivisuuden yksinkertaisesti korvaamalla indeksit yhdessä kaavoista. $j=ik$

Syklisen konvoluution laskenta

Tarkastellaan nyt kahta samanpituista numeerista sarjaa : $N$

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

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

Jaksottaisen ympyräkonvoluution saamiseksi on välttämätöntä kuvitella, että nämä sekvenssit sijaitsevat kahdella ympyrällä, joista toinen on toisen sisällä. Kunkin näiden sekvenssien arvot ovat yhtä kaukana toisistaan. Ympyräkonvoluution jokaisen arvon saamiseksi on välttämätöntä kuvitella, että yksi sarjoista liikkuu ympyrässä suhteessa toiseen myötäpäivään. Ensin otetaan pyörivän sekvenssin ensimmäinen arvo, kerrotaan peräkkäin toisen sekvenssin arvoilla ja lasketaan yhteen kertolaskujen tulokset ja saadaan tulossekvenssin ensimmäinen arvo . Sitten toistamme nämä toimet kullekin sekvenssin arvolle, joka pyörii suhteessa toiseen. Lähtösekvenssin elementtien lukumäärä on . $c'$ $c'$ $N$

Toisin sanoen syklisen konvoluution alkiot lasketaan kaavalla $c'$

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

missä . $((ik))=(ik){\bmod {N}}$

Tuloksena oleva sekvenssi vastaa kahden jaksollisen signaalin, toisin sanoen sekvenssien, konvoluutiota, ja sen voidaan katsoa olevan määritelty kaikille kaavoilla ja . $a$ $b$ $i\in \mathbb {Z}$ ${\displaystyle a_{i}=a_{((i))))$ ${\displaystyle b_{i}=b_{((i))))$

Aperiodisen konvoluution laskenta

Ajajaksoisen konvoluution saamiseksi suoritetaan kaikki samat toiminnot kuin ympyräkonvoluution saamiseksi, mutta sarjoissa voi olla eri määrä elementtejä (esimerkiksi ja ) ja ne on täytettävä nollilla . Tämän tyyppistä konvoluutiota suoritettaessa pyöreän kierteen yhteydessä esiintyvän pyöreän päällekkäisyyden vaikutus eliminoidaan. Tämä on vaihtoehtoinen tapa laskea lineaarikonvoluutio. $N_1$ $N_2$ $N_{out}=N_{1}+N_{2}-1$

Lineaaristen ja syklisten konvoluutioiden välinen suhde

Edellä kuvattu lähestymistapa mahdollistaa yhteyden muodostamisen lineaaristen ja syklisten konvoluutioiden laskennan välille. Tätä varten jaamme syklisen konvoluution elementtien kaavassa summan kahdella, mikä vastaa tapauksia ja : $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}.

Olettaen nyt ensimmäisessä summassa kohdassa ja toisessa summassa at , voimme muuttaa summausrajoja ja saada lineaaristen ja syklisten konvoluutioiden välisen suhteen muodossa $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.

Lineaarinen konvoluutio voidaan laskea sykliseksi, jos tämän kaavan toinen termi on yhtä suuri kuin nolla, eli tulot kaikille ja ovat yhtä suuret kuin nolla . Tämän ehdon täyttymisen varmistamiseksi voidaan valita syklisen konvoluution pituus siten, että se ei ole pienempi kuin , samalla kun syötesekvenssit täytetään nolilla. ${\displaystyle a_{k}b_{N+ik))$ $i$ $k$ $N$ $N_{out}=N_{1}+N_{2}-1$

Konvoluution laskeminen Fourier-muunnoksen avulla

Konvoluution laskemiseksi diskreetin Fourier-muunnoksen avulla on tarpeen täyttää molemmat tulosekvenssit nollilla siten, että näiden sekvenssien elementtien lukumäärä on yhtä suuri kuin . Seuraavaksi on tarpeen suorittaa suorat Fourier-muunnokset jokaiselle sekvenssille. Sitten muunnetut sekvenssit kerrotaan elementti kerrallaan, minkä jälkeen suoritetaan kertolaskutuloksen käänteismuunnos. $N_{{out}}$

Konvoluution laskeminen kuvatulla tavalla on mahdollista konvoluutiolauseen ansiosta.

Lineaarisen, syklisen tai konvoluution laskelmien oikeellisuuden tarkistamiseksi Fourier-muunnoksen avulla voit lisäksi laskea toisen kahdesta muusta konvoluutiotyypistä, koska lähtösekvenssien on oltava samat, kun tulosekvenssit ovat samat.

Laskennallinen monimutkaisuus

Konvoluution laskeminen vaatii operaatioita. Tätä lukua voidaan vähentää merkittävästi laskemalla konvoluutio erilaisilla nopeilla algoritmeilla. $O(N^2)$

Useimmiten operaatioiden määrän vähentämiseksi konvoluutio lasketaan käyttämällä kahta Fourier-muunnosta, joista kukin lasketaan käyttämällä nopeita algoritmeja . Tämä vähentää konvoluutiooperaation laskennallisen monimutkaisuuden arvoon . $O(N\log N)$

Avaruuden ulottuvuuden pienentäminen moniulotteisella konvoluutiolla

Olkoon kaksi diskreettiä kompleksista signaalia avaruudessa . Määritämme näiden signaalien konvoluution seuraavasti $\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}).

Asetetaan myös tilan koon pienentäminen mittaamalla tai summaamalla signaali asteikolla $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.

Lause. Satunnaiselle avaruuden ulottuvuudelle konvoluution ja sitä seuraavan summauksen tulos on , mikä vastaa alustavaa signaalien summausta ja sitä seuraavaa konvoluutiota: . $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}]$ [yksi]

Ohjelmaesimerkki

Alla on esimerkki lineaarisen konvoluution toteutuksesta, joka on kirjoitettu C++ :lla:

/* * Lähtösekvenssin koko on M + N - 1 */ vektori < double > conv ( const vektori < double >& x , const vektori < double >& h ) { if (( x . koko () == 0 ) && ( h . koko () == 0 )) { paluuvektori < double > ( ); } vektori < kaksois > a ; vektori < kaksois > b ; if ( x .size ( ) < h .size ( ) ) { a = x _ b = h _ } muu { a = h _ b = x ; } vektori < double > tulos ( a . koko ( ) + b . koko ( ) - 1 , 0 ); for ( koko_t k = 0 ; k < a . koko (); k ++ ) { for ( koko_t l = 0 ; l < b . koko (); l ++ ) { tulos [ l + k ] += a [ k ] * b [ l ]; } } palauttaa tuloksen ; }

Katso myös

Poikkileikkauskonvoluutio

Muistiinpanot

↑ Grishentsev A. Yu., Korobeinikov A. G. Avaruuden ulottuvuuden pienentäminen digitaalisten signaalien korreloinnin ja konvoluution aikana // Izv. yliopistot. Instrumentointi. : painettu. - 2016. - Nro 3 . - S. 211-218 . — ISSN 0021-3454 . Arkistoitu alkuperäisestä 12. toukokuuta 2016.

Kirjallisuus

Rabiner L., Gould B. Luku 2. Lineaaristen diskreettien järjestelmien teoria // Digitaalisen signaalinkäsittelyn teoria ja sovellus. - M .: Mir, 1978. - S. 72-81. — 848 s.
Blahut R.Nopeat digitaaliset signaalinkäsittelyalgoritmit. - M.: Mir , 1989.