Convolution: Difference between revisions
No edit summary |
Sudleyplace (talk | contribs) No edit summary |
||
| Line 31: | Line 31: | ||
<td><apll>2</apll></td> | <td><apll>2</apll></td> | ||
<td><apll>1 2</apll></td> | <td><apll>1 2</apll></td> | ||
<td><apll> | <td><apll> 1 2</apll></td> | ||
<td><apll> | <td><apll> 1 2</apll></td> | ||
<td><apll> | <td><apll> 1</apll></td> | ||
<td> multiply the rows together</td> | <td> multiply the rows together</td> | ||
</tr> | </tr> | ||
<tr> | <tr> | ||
<td><apll>1 3 2 1 | <td><apll>1 3 2 1 </apll></td> | ||
<td><apll>1 3 2 1 | <td><apll>1 3 2 1 </apll></td> | ||
<td><apll>1 3 2 1 | <td><apll>1 3 2 1 </apll></td> | ||
<td><apll>1 3 2 1 | <td><apll>1 3 2 1 </apll></td> | ||
<td><apll>1 3 2 1</apll></td> | <td><apll>1 3 2 1</apll></td> | ||
</tr> | </tr> | ||
| Line 49: | Line 49: | ||
<td><apll>2</apll></td> | <td><apll>2</apll></td> | ||
<td><apll>1 6</apll></td> | <td><apll>1 6</apll></td> | ||
<td><apll> | <td><apll> 3 4</apll></td> | ||
<td><apll> | <td><apll> 2 2</apll></td> | ||
<td><apll> | <td><apll> 1</apll></td> | ||
<td> add the products</td> | <td> add the products</td> | ||
</tr> | </tr> | ||
</table> | </table> | ||
<apll> | <apll> L+⍡×R | ||
2 7 7 4 1</apll> | 2 7 7 4 1</apll> | ||
| Line 62: | Line 62: | ||
<p>Polynomial multiplication is illustrated in the above example using the functions <apll>+</apll> and <apll>×</apll>. Overlapping string searching uses the functions <apll>∧</apll> and <apll>=</apll> as in</p> | <p>Polynomial multiplication is illustrated in the above example using the functions <apll>+</apll> and <apll>×</apll>. Overlapping string searching uses the functions <apll>∧</apll> and <apll>=</apll> as in</p> | ||
<apll> | <apll><pre> | ||
L←'abababc' ⋄ R←'aba' | |||
1 0 1 0 0 0 0</apll> | (0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R | ||
1 0 1 0 0 0 0</pre></apll> | |||
where we need to drop leading elements of the convolution result to remove the leading prefix comparisons. | |||
Latest revision as of 18:48, 15 April 2018
|
||||
| L and R are vectors; scalars are promoted to one-element vectors. | ||||
| f and g are functions. | ||||
| Z is a vector whose shape is (⍴L)+(⍴R)-1. |
The result is obtained by dragging the reverse of the shorter argument through all positions of the longer argument (as in a moving window) and performing an f.g inner product between the two, including leading and trailing prefixes. For example,
L←1 3 2 1 ⋄ R←2 1 ⋄ L+⍡×R
| 2 | 1 2 | 1 2 | 1 2 | 1 | multiply the rows together |
| 1 3 2 1 | 1 3 2 1 | 1 3 2 1 | 1 3 2 1 | 1 3 2 1 | |
| 2 | 1 6 | 3 4 | 2 2 | 1 | add the products |
L+⍡×R 2 7 7 4 1
Interestingly, this algorithm solves a diverse set of problems such as weighted moving average (used to remove pixelization from a digital image), polynomial multiplication, and overlapping string searching.
Polynomial multiplication is illustrated in the above example using the functions + and ×. Overlapping string searching uses the functions ∧ and = as in
L←'abababc' ⋄ R←'aba'
(0⌈¯1+(⍴L)⌊⍴R)↓L∧⍡=⌽R
1 0 1 0 0 0 0
where we need to drop leading elements of the convolution result to remove the leading prefix comparisons.
