Dlaczego potrzebny jest splot lub jaka jest filozofia splotu?

Pracuję w dziedzinie cyfrowego odtwarzania obrazów. Przeczytałem wszystkie rzeczy o splotie, że dla systemu LTI , jeśli znamy jego odpowiedź impulsową , wówczas możemy znaleźć jego wynik, używając po prostu splotu między odpowiedzią wejściową a odpowiedzią impulsową.

Czy ktoś może mi powiedzieć, że jaka jest za tym podstawowa filozofia matematyczna? Twoje wrażenia z powiedzą mi więcej niż tylko surfowanie po Internecie.

Idea konwolucji

Moja ulubiona prezentacja tego tematu znajduje się w jednym z wykładów Brada Osgooda na temat transformaty Fouriera . Dyskusja na temat splotu zaczyna się około 36:00, ale cały wykład ma dodatkowy kontekst, który warto obejrzeć.

Podstawową ideą jest to, że gdy definiujesz coś w rodzaju transformacji Fouriera, zamiast cały czas pracować bezpośrednio z definicją, przydatne jest uzyskanie właściwości wyższego poziomu, które upraszczają obliczenia. Na przykład jedną z takich właściwości jest to, że transformacja sumy dwóch funkcji jest równa sumie transformat, tj

$$F\{f + g\} = F\{f\} + F\{g\}.$$

Oznacza to, że jeśli masz funkcję z nieznaną transformacją i można ją rozłożyć na sumę funkcji ze znanymi transformacjami, zasadniczo otrzymujesz odpowiedź za darmo.

Ponieważ mamy tożsamość sumy dwóch transformacji, naturalnym pytaniem jest, jaka jest tożsamość iloczynu dwóch transformacji, tj.

$$F\{f\}F\{g\} = \space ?.$$

Okazuje się, że przy obliczaniu odpowiedzi pojawia się splot. Cała pochodna jest podana w filmie, a ponieważ twoje pytanie jest głównie koncepcyjne, nie podsumuję go tutaj.

Implikacja zbliżenia się do splotu w ten sposób jest taka, że ​​jest to nieodłączna część sposobu, w jaki transformata Laplace'a (której szczególnym przypadkiem jest transformata Fouriera) przekształca zwykłe równania różniczkowe zwyczajne o stałym współczynniku (LCCODE) w równania algebraiczne. Fakt, że taka transformacja jest dostępna, aby uczynić LCCODE możliwym do analizy analitycznym, jest dużą częścią powodu, dla którego są badane w przetwarzaniu sygnału. Na przykład, aby zacytować Oppenheim i Schafer :

Ponieważ są one stosunkowo łatwe do scharakteryzowania matematycznego i ponieważ można je zaprojektować do wykonywania użytecznych funkcji przetwarzania sygnałów, klasa systemów liniowych niezmiennych z przesunięciem zostanie gruntownie zbadana.

Tak więc jedna odpowiedź na pytanie brzmi: jeśli używasz metod transformacji do analizy i / lub syntezy systemów LTI, prędzej czy później dojdzie do splotu (pośrednio lub jawnie). Zauważ, że takie podejście do wprowadzenia splotu jest bardzo standardowe w kontekście równań różniczkowych. Na przykład zobacz wykład MIT Arthura Mattucka . Większość prezentacji albo przedstawia całkę splotu bez komentarza, a następnie czerpie jej właściwości (tj. Wyciąga ją z kapelusza), lub rąbka i maści o dziwnej formie całki, mówi o przerzucaniu i przeciąganiu, odwracaniu czasu itp. Itp. .

Powodem, dla którego podoba mi się podejście prof. Osgooda, jest to, że unika tego wszystkiego tsouris, a także, moim zdaniem, głęboki wgląd w to, w jaki sposób matematycy prawdopodobnie wpadli na ten pomysł. I cytuję:

Powiedziałem: „Czy istnieje sposób łączenia F i G w dziedzinie czasu, aby w dziedzinie częstotliwości widma się mnożyły, transformaty Fouriera mnożyły się?” Odpowiedź brzmi: tak, jest ta skomplikowana całka. To nie jest takie oczywiste. Nie wstawałbyś rano z łóżka i nie zapisywałbyś tego, i spodziewałeś się, że to rozwiąże ten problem. Jak to zdobyć? Powiedziałeś, załóżmy, że problem został rozwiązany, zobacz, co się stanie, a wtedy będziemy musieli rozpoznać, kiedy nadszedł czas, aby ogłosić zwycięstwo. I czas ogłosić zwycięstwo.

Teraz, będąc wstrętnym matematykiem, kryjesz swoje ślady i mówisz: „Cóż, po prostu zamierzam zdefiniować splot dwóch funkcji za pomocą tej formuły”.

Systemy LTI

W większości tekstów DSP splot jest zwykle wprowadzany w inny sposób (co pozwala uniknąć odniesienia do metod transformacji). Wyrażając dowolny sygnał wejściowy jako sumę skalowanych i przesuniętych impulsów jednostkowych,$x(n)$

$$x(n) = \sum_{k=-\infty}^\infty{x(k)\delta(n - k)}, \tag{1}$$

gdzie

$$\delta(n) = \begin{cases} 0, & n \ne 0 \\ 1, & n = 0, \end{cases} \tag{2}$$

definiujące właściwości liniowych układów niezmienniczych w czasie prowadzą bezpośrednio sumę splotu obejmującą odpowiedź impulsową . Jeśli system zdefiniowany przez operatora LTI L jest wyrażony jako y ( n ) = L [ x ( n ) ] , to przez zastosowanie właściwości repatywnych, a mianowicie liniowości$h(n) = L[\space \delta(n) \space]$$L$$y(n) = L[\space x(n)\space]$

$$\overbrace{L[\space ax_1(n) + bx_2(n)\space ]}^\text{Transform of the sum of scaled inputs} = \overbrace{aL[\space x_1(n)\space ] + bL[\space x_2(n)\space ]}^\text{Sum of scaled transforms} , \tag{3}$$

oraz niezmienność czasu / zmiany

$$L[\space x(n) \space] = y(n) \space \xrightarrow{\text{implies}} L[\space x(n-k) \space] = y(n-k), \tag{4}$$

system można przepisać jako

$$y(n) = \overbrace{L\left[ \sum_{k=-\infty}^\infty{x(k)\delta(n - k)}\right]}^\text{Tranform of the sum of scaled inputs} = \overbrace{\sum_{k=-\infty}^\infty{x(k)L[\delta(n - k)]}}^\text{Sum of scaled transforms} = \overbrace{\sum_{k=-\infty}^\infty{x(k)h(n-k) }. }^\text{Convolution with the impulse response}$$

To bardzo standardowy sposób prezentowania splotu i jest to całkowicie elegancki i użyteczny sposób na obejście tego. Podobne pochodne można znaleźć w Oppenheim i Schafer , Proakis i Manolakis , Rabiner i Gold i jestem pewien, że wiele innych. Niektóre głębszy wgląd [który idzie dalej niż standardowe wprowadzeń] jest dana przez Dilip w jego doskonałą odpowiedź tutaj .

Zauważ jednak, że to wyprowadzenie jest nieco magiczną sztuczką. Patrząc jeszcze raz na rozkład sygnału w , widzimy, że ma on już postać splotu. Gdyby$\left(1\right)$

$$\overbrace{(f * g)(n)}^\text{f convolved with g} = \sum_{k=-\infty}^\infty{f(k)g(n-k)},$$

wtedy to tylko x ∗ δ . Ponieważ funkcja delta jest elementem tożsamości dla splotu, powiedzenie, że dowolny sygnał może być wyrażony w tej formie, jest bardzo podobne do powiedzenia, że ​​dowolna liczba n może być wyrażona jako n + 0 lub n × 1 . Teraz wybór opisania sygnałów w ten sposób jest genialny, ponieważ prowadzi bezpośrednio do idei odpowiedzi impulsowej - po prostu idea konwolucji jest już „wypalona” do rozkładu sygnału.$\left(1\right)$$x * \delta$$n$$n + 0$$n \times 1$

Z tej perspektywy splot jest nierozerwalnie związany z ideą funkcji delta (tj. Jest to operacja binarna, w której funkcja delta jest elementem tożsamości). Nawet bez uwzględnienia jego związku ze splotem opis sygnału zależy w głównej mierze od idei funkcji delta. Powstaje więc pytanie: skąd pomysł na funkcję delta? O ile mi wiadomo, sięga co najmniej tak daleko jak artykuł Fouriera o Analitycznej Teorii Ciepła, gdzie pojawia się niejawnie. Jednym ze źródeł dalszych informacji jest ten artykuł o pochodzeniu i historii konwolucji autorstwa Alejandro Domíngueza.

Są to dwa główne podejścia do pomysłu w kontekście teorii systemów liniowych. Jeden opowiada się za wglądem analitycznym, a drugi za rozwiązaniem numerycznym. Myślę, że oba są przydatne do pełnego obrazu znaczenia splotu. Jednak w przypadku dyskretnym, całkowicie pomijając układy liniowe, istnieje poczucie, że splot jest znacznie starszym pomysłem.

Mnożenie wielomianowe

Jedną dobrą prezentację idei dyskretnego splotu po prostu wielomianowego zwielokrotnienia podał Gilbert Strang w wykładzie rozpoczynającym się około 5:46. Z tej perspektywy idea sięga wstecz aż do wprowadzenia systemów liczb pozycyjnych (które domyślnie reprezentują liczby jako wielomiany). Ponieważ transformata Z reprezentuje sygnały jako wielomiany w z, również w tym kontekście powstanie splot - nawet jeśli transformacja Z jest formalnie zdefiniowana jako operator opóźnienia bez uciekania się do złożonej analizy i / lub jako szczególny przypadek Laplace'a Przekształć .

Ja raz dał odpowiedź w Wikipedia stronie splot Dyskusja, która zwróciła się w zasadzie to samo pytanie: dlaczego inwersji czasowej? . Filozofia polega na tym, że przykładasz pojedynczy impuls w czasie 0 do filtra i rejestrujesz jego reakcję w czasie 0,1,2,3,4,… Zasadniczo odpowiedź będzie wyglądać jak funkcja, h (t). Możesz to wykreślić. Jeśli puls był n razy wyższy / wyższy, impulsy odpowiedzi będą proporcjonalnie wyższe (dzieje się tak, ponieważ zawsze zakłada się filtr liniowy). Teraz wszystkie DSP (i nie tylko DSP) dotyczą tego, co się stanie, gdy zastosujesz filtr do swojego sygnału? Znasz odpowiedź impulsową. Twój sygnał (szczególnie cyfrowy) to nic innego jak seria impulsów o wysokości x (t). Ma wysokość / wartość w czasie $x$$t$. Układy liniowe są fajne, że można zsumować wyjścia dla każdego takiego impulsu wejściowego, aby uzyskać funkcję odpowiedzi y (t) dla funkcji wejściowej x (t). Wiesz, że impuls wyjściowy y (t = 10) zależy od natychmiastowego wejścia x (10), co przyczynia się do h (0) * x (10). Ale jest też wkład, x (9) * h (1), w wyjście z poprzedniego impulsu, x (9), i wkład z jeszcze wcześniejszych wartości wejściowych. Widzisz, gdy dodajesz wkłady z wcześniejszych danych wejściowych, jeden argument zmniejsza się, a drugi rośnie. Ci MAC każdy wkład język Y (10) = h (0) * x (10) + h (1) * x (9) + h (2) * x (8) + ..., który jest uwypuklony.

Funkcje y (t), h (t) i x (t) można traktować jak wektory. Macierze są operatorami w algebrze liniowej. Biorą wektor wejściowy (szereg liczb) i wytwarzają wektor wyjściowy (kolejna seria liczb). W tym przypadku y jest iloczynem macierzy splotu z wektorem x,

$\vec y = \begin{bmatrix}y_0\\y_1\\y_2 \\ \vdots \end{bmatrix} = \begin{bmatrix}h_0 & 0 & 0 & \cdots \\ h_1 & h_0 & 0 & \cdots \\ h_2 & h_1 & h_0 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix}x_0\\x_1\\x_2 \\ \vdots \end{bmatrix} = H \vec x$

Teraz, z powodu splotu jest macierzą Toeplitza , to jest, a zatem operator splot (liniowy operatorów są przedstawione matryce, ale matrycy zależy również od masy) Fouriera eigenbasis miły macierzą diagonalną w domenie Fouriera

$\vec Y = \begin{bmatrix}Y_0\\Y_1\\Y_2 \\ \vdots \end{bmatrix} = \begin{bmatrix} \lambda_0 & 0 & 0 & \cdots \\ 0 & \lambda_1 & 0 & \cdots \\0 & 0 & \lambda_2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix}X_0\\X_1\\X_2 \\ \vdots \end{bmatrix} = diag(H)\vec X$

Note, much more zeroes and, thus, much simpler computation. This result is know as "convolution theorem" and, as first response answered, it is much simpler in the fourier domain. But, this is phylosophy behind the "convolution theorem", fourier basis and linear operators rather than ubiquitous need for convolution.

Normally, you do convolution because you have your input signal, impulse response and require output in time domain. You may transform into fourier space to optimize computation. But, it is not practical for simple filters, as I've seen in the DSPGuide. If your filter looks like $y[currentTime] = k_1 x[time-1] + k_2 x(time-2) + b * y[time-1]$, it makes no sense to fourier transform. You just do n multiplications, for computing every y. It is also natural for real-time. In real-time you compute only one y at a time. You may think of Fourier transform if you have your signal x recorded and you need to compute the whole vector y at once. This would need NxN MAC operations and Fourier can help to reduce them to N log(N).

Although the previous answers have been really good, I would like to add my viewpoint about convolution where I just make it easier to visualize due to the figures.

One wonders if there is any method through which an output signal of a system can be determined for a given input signal. Convolution is the answer to that question, provided that the system is linear and time-invariant (LTI).

Assume that we have an arbitrary signal $s[n]$. Then, $s[n]$ can be decomposed into a scaled sum of shifted unit impulses through the following reasoning. Multiply $s[n]$ with a unit impulse shifted by $m$ samples as $\delta[n-m]$. Since $\delta[n-m]$ is equal to 0 everywhere except at $n=m$, this would multiply all values of $s[n]$ by 0 when $n$ is not equal to $m$ and by 1 when $n$ is equal to $m$. So the resulting sequence will have an impulse at $n=m$ with its value equal to $s[m]$. This process is clearly illustrated in Figure below.

$\hspace{2cm}$

This can be mathematically written as

$$\begin{equation*} s[n] \delta [n-m] = s[m] \delta [n-m] \end{equation*}$$ Repeating the same procedure with a different delay $m'$ gives $$\begin{equation*} s[n] \delta [n-m'] = s[m'] \delta [n-m'] \end{equation*}$$

The value $s[m']$ is extracted at this instant. Therefore, if this multiplication is repeated over all possible delays $-\infty < m < \infty$, and all produced signals are summed together, the result will be the sequence $s[n]$ itself.

$$\begin{align} s[n]&= \cdots + s[-2]\delta[n+2] + s[-1]\delta[n+1] + \nonumber \\ &\quad\quad\quad\quad\quad s[0]\delta[n] + s[1]\delta[n-1] + s[2]\delta[n-2] + \cdots \nonumber \\ &= \sum \limits _{m = -\infty} ^{\infty} s[m] \delta[n-m] \label{eqIntroductionSeqImpulses} \end{align}$$

In summary, the above equation states that $s[n]$ can be written as a summation of scaled unit impulses, where each unit impulse $\delta[n-m]$ has an amplitude $s[m]$. An example of such a summation is shown in Figure below.

$\hspace{3cm}$

Consider what happens when it is given as an input to an LTI system with an impulse response $h[n]$.

This leads to an input-output sequence as

During the above procedure, we have worked out the famous convolution equation that describes the output $r[n]$ for an input $s[n]$ to an LTI system with impulse response $h[n]$.

Convolution is a very logical and simple process but many DSP learners can find it confusing due to the way it is explained. We will describe a conventional method and another more intuitive approach.

Conventional Method

---

Most textbooks after defining the convolution equation suggest its implementation through the following steps. For every individual time shift $n$,

[Flip] Arranging the equation as $r[n] = \sum _{m = -\infty} ^{\infty} s[m] h[-m+n]$, consider the impulse response as a function of variable $m$, flip $h[m]$ about $m = 0$ to obtain $h[-m]$.

[Shift] To obtain $h[-m+n]$ for time shift $n$, shift $h[-m]$ by $n$ units to the right for positive $n$ and left for negative $n$.

[Multiply] Point-wise multiply the sequence $s[m]$ by sequence $h[-m+n]$ to obtain a product sequence $s[m]\cdot h[-m+n]$.

[Sum] Sum all the values of the above product sequence to obtain the convolution output at time $n$.

[Repeat] Repeat the above steps for every possible value of $n$.

An example of convolution between two signals $s[n] = [2\hspace{1mm}-\hspace{-1mm}1\hspace{2mm} 1]$ and $h[n] = [-1\hspace{2mm} 1\hspace{2mm} 2]$ is shown in Figure below, where the result $r[n]$ is shown for each $n$.

Note a change in signal representation above. The actual signals $s[n]$ and $h[n]$ are a function of time index $n$ but the convolution equation denotes both of these signals with time index $m$. On the other hand, $n$ is used to represent the time shift of $h[-m]$ before multiplying it with $s[m]$ point-wise. The output $r[n]$ is a function of time index $n$, which was that shift applied to $h[-m]$.

Next, we turn to the more intuitive method where flipping a signal is not required.

Intuitive Method

---

There is another method to understand convolution. In fact, it is built on the derivation of convolution equation, i.e., find the output $r[n]$ as

$$\begin{align} r[n] ~ &= ~ \cdots + \nonumber \\ &\qquad\quad s[-2]\cdot h[n+2] ~+ \nonumber \\ &\qquad\qquad \quad\quad\quad s[-1]\cdot h[n+1] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\quad \quad\quad \quad s[0]\cdot h[n] ~+ \nonumber \\ &\qquad\qquad \quad \qquad\qquad\qquad \quad \quad\quad~ s[1]\cdot h[n-1] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\qquad\qquad\qquad \quad\quad\quad \quad~ s[2]\cdot h[n-2] ~+ \nonumber \\ &\qquad\qquad \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\quad\quad\quad \cdots \label{eqIntroductionConvolution3} \end{align}$$ Let us solve the same example as in the above Figure, where $s[n] = [2\hspace{1mm}-~\hspace{-2mm}1\hspace{2mm} 1]$ and $h[n] = [-1\hspace{2mm} 1\hspace{2mm} 2]$. This is shown in Table below.

$\hspace{3cm}$

Such a method is illustrated in Figure below. From an implementation point of view, there is no difference between both methods.

$\hspace{3cm}$

To sum up, convolution tells us how an LTI system behaves in response to a particular input and thanks to intuitive method above, we can say that convolution is also multiplication in time domain (and flipping the signal is not necessary), except the fact that this time domain multiplication involves memory. To further understand at a much deeper level where flipping comes from, and what happens in frequency domain, you can download a sample section from my book here.