The team investigates a plane crash and the shooting of the forest ranger who discovered the crash. Charlie uses a deconvolution algorithm to identify a smudged fingerprint, allowing them to identify the technician who tampered with the plane's software.

A convolution is means of creating a new function *h* from two other functions *f* and *g*. For discrete functions we write *h*(n)=(*f* **g*)(n)=&Sigma_{i}*f*(i)*g*(i-n). Usually convolutions involve functions that take on non-zero values a finite number of times, since the sum would often be undefined otherwise. For such functions the the convolution evaluated at n tells us how much *f* overlaps with the translation of *g* by n. Convolutions can also be done with continuous functions, where we trade the sum for an integral. In this case *h*(x)=(*f* **g*)(x)=&int_{-&infin}^{&infin} *f*(t)*g*(t-x) *d*t.

Calculate the following convolutions for

- 1.
*f***g* - 2.
*g***f* - 3.
*(2f)***g* - 4.
*f***(2g)*

The exercise hints at two basic properties of convolutions: they are commutative and associative with scalar multiplication. Convolutions are also associative, and the addition of functions distributes over convolutions.

Convolutions are frequently used in image processing. This is done by letting *f* represent the image data and letting *g* take on non-zero values only in a square centered at the origin. A square matrix is then used to represent *g*. For instance, the image below is shown before and after convolution with the matrix given below.

-1 | -1 | -1 |

-1 | 8 | -1 |

-1 | -1 | -1 |

Treat a white square as having value 0 and a black square as having some non-zero value(thus adding the value of two black squares will give you a black square). You should also assume that any square not shown below is white. Consider the matrix below.

0 | 0 | 1 |

0 | 0 | 0 |

1 | 0 | 0 |

The *Fourier transform* is another frequently used tool in signal processing. The Fourier transform takes a function and then produces a new one. If we view the original function as describing how a signal evolves over time the Fourier transform expresses that signal as a function of different frequency signals. For instance, a cosine function with frequency *a* has a Fourier transform that is zero everywhere except at *a* and -*a*.

Deconvolution involves finding *f* when we know *g* and *h*. This is a frequent problem in signal processing where *h* is the information we recieve from a device(like the Hubble telescope alluded to in the episode) and *g* is a distortion introduced to the original signal *f*. Often the exact form of *g*is unknown, but we know what kind of distortion it is. For example, if you look at a blurry picture you can often tell that the camera was moved while the picture was being taken, but you might not be able to tell exactly how much it was moved or in what direction. Finding the original signal is very difficult, and is usually done using one of several varieties of computer algorithms.

- Let
*h*be 1 for n = -1, 0, and 1, and 0 elsewhere. Let*g*be 0 everywhere except at the origin where it is 1. Find*f*such that*h*(n)=(*f***g*)(n). What does this tell you about the existence of an identity function for discrete convolutions? - Let
*h*and*g*be as above except that*g*(1)=-1. You won't be able to find*f*, but see what you can figure out about it (Hint: You should find that most of*f*is constant).