81 lines
3.3 KiB
Plaintext
81 lines
3.3 KiB
Plaintext
The convolution of two functions <math>\mathit{F}</math> and <math>\mathit{H}</math> of
|
|
an integer variable is defined as the function <math>\mathit{G}</math>
|
|
satisfying
|
|
|
|
:<math> G(n) = \sum_{m=-\infty}^{\infty} F(m) H(n-m) </math>
|
|
|
|
for all integers <math>\mathit{n}</math>. Assume <math>F(n)</math> can be non-zero only for <math>0</math> ≤ <math>\mathit{n}</math> ≤ <math>|\mathit{F}|</math>, where <math>|\mathit{F}|</math> is the "length" of <math>\mathit{F}</math>, and similarly for <math>\mathit{G}</math> and <math>\mathit{H}</math>, so that the functions can be modeled as finite sequences by identifying <math>f_0, f_1, f_2, \dots</math> with <math>F(0), F(1), F(2), \dots</math>, etc.
|
|
Then for example, values of <math>|\mathit{F}| = 6</math> and <math>|\mathit{H}| = 5</math> would determine the following value of <math>\mathit{g}</math> by definition.
|
|
|
|
:<math>
|
|
\begin{array}{lllllllllll}
|
|
g_0 &= &f_0h_0\\
|
|
g_1 &= &f_1h_0 &+ &f_0h_1\\
|
|
g_2 &= &f_2h_0 &+ &f_1h_1 &+ &f_0h_2\\
|
|
g_3 &= &f_3h_0 &+ &f_2h_1 &+ &f_1h_2 &+ &f_0h_3\\
|
|
g_4 &= &f_4h_0 &+ &f_3h_1 &+ &f_2h_2 &+ &f_1h_3 &+ &f_0h_4\\
|
|
g_5 &= &f_5h_0 &+ &f_4h_1 &+ &f_3h_2 &+ &f_2h_3 &+ &f_1h_4\\
|
|
g_6 &= & & &f_5h_1 &+ &f_4h_2 &+ &f_3h_3 &+ &f_2h_4\\
|
|
g_7 &= & & & & &f_5h_2 &+ &f_4h_3 &+ &f_3h_4\\
|
|
g_8 &= & & & & & & &f_5h_3 &+ &f_4h_4\\
|
|
g_9 &= & & & & & & & & &f_5h_4
|
|
\end{array}
|
|
</math>
|
|
|
|
We can write this in matrix form as:
|
|
|
|
:<math>
|
|
\left(
|
|
\begin{array}{l}
|
|
g_0 \\
|
|
g_1 \\
|
|
g_2 \\
|
|
g_3 \\
|
|
g_4 \\
|
|
g_5 \\
|
|
g_6 \\
|
|
g_7 \\
|
|
g_8 \\
|
|
g_9 \\
|
|
\end{array}
|
|
\right) = \left(
|
|
\begin{array}{lllll}
|
|
f_0\\
|
|
f_1 & f_0\\
|
|
f_2 & f_1 & f_0\\
|
|
f_3 & f_2 & f_1 & f_0\\
|
|
f_4 & f_3 & f_2 & f_1 & f_0\\
|
|
f_5 & f_4 & f_3 & f_2 & f_1\\
|
|
& f_5 & f_4 & f_3 & f_2\\
|
|
& & f_5 & f_4 & f_3\\
|
|
& & & f_5 & f_4\\
|
|
& & & & f_5
|
|
\end{array}
|
|
\right) \; \left(
|
|
\begin{array}{l}
|
|
h_0 \\
|
|
h_1 \\
|
|
h_2 \\
|
|
h_3 \\
|
|
h_4 \\
|
|
\end{array} \right)
|
|
</math>
|
|
|
|
or
|
|
|
|
:<math>
|
|
g = A \; h
|
|
</math>
|
|
|
|
For this task, implement a function (or method, procedure, subroutine, etc.) <code>deconv</code> to perform ''deconvolution'' (i.e., the ''inverse'' of convolution) by constructing and solving such a system of equations represented by the above matrix <math>A</math> for <math>\mathit{h}</math> given <math>\mathit{f}</math> and <math>\mathit{g}</math>.
|
|
|
|
* The function should work for <math>\mathit{G}</math> of arbitrary length (i.e., not hard coded or constant) and <math>\mathit{F}</math> of any length up to that of <math>\mathit{G}</math>. Note that <math>|\mathit{H}|</math> will be given by <math>|\mathit{G}| - |\mathit{F}| + 1</math>.
|
|
* There may be more equations than unknowns. If convenient, use a function from a [http://www.netlib.org/lapack/lug/node27.html library] that finds the best fitting solution to an overdetermined system of linear equations (as in the [[Multiple regression]] task). Otherwise, prune the set of equations as needed and solve as in the [[Reduced row echelon form]] task.
|
|
* Test your solution on the following data. Be sure to verify both that <code>deconv</code><math>(g,f) = h</math> and <code>deconv</code><math>(g,h) = f</math> and display the results in a human readable form.
|
|
<code>
|
|
h = [-8,-9,-3,-1,-6,7]<br>
|
|
f = [-3,-6,-1,8,-6,3,-1,-9,-9,3,-2,5,2,-2,-7,-1]<br>
|
|
g = [24,75,71,-34,3,22,-45,23,245,25,52,25,-67,-96,96,31,55,36,29,-43,-7]
|
|
</code>
|
|
|