# Derivation of the Optimal Matched Filter - Convolution vs. Correlation

On the Wikipedia page for Matched Filters here, there is a matrix algebra derivation for an optimal matched filter. Now, considering the output of an LTI system is found using the convolution operator, why is the first step of the proof on the page is to consider:

$$y = \sum_{k=-\infty}^{\infty} h^{*}[k]x[k]$$

$$y[n] = \sum_{k=-\infty}^{\infty} h[n-k]x[k]$$

the convolution operation? And is $$h^{*}$$ the complex conjugate of the impulse response?

Convolution commutes $$y[n]=\sum_k h[n-k]x[k]=\sum_k h[k] x[n-k]$$ for $n=0$ $$y[n=0]=\sum_k h[-k] x[k]$$ If $H(e^{-\jmath \omega})$ is the Fourier Transform of $h[n]$, $H(e^{\jmath \omega})$ is the Fourier Transform of $h[-k]$,

The maximization for the matched filter is at the point $n=0$.

In communications $n=0$ corresponds to synchronization.

In a RADAR/SONAR problem the maximum output of the matched filter is the estimate of where $n=0$

The calculation shown is the correlator equivalent of the LTI filter operation. The signal/sequence $x[\cdot]$ is being correlated (with zero time offset) with the signal/sequence $h[\cdot]$, and the value of the crosscorrelation function (at zero time offset) is defined to be $$C_{h,k} = \sum_{k=-\infty}^\infty (h[k])^*x[k]$$ though there are people who march to the beat of a different drummer and define it to be $$C_{h,k} = \sum_{k=-\infty}^\infty h[k](x[k])^*.$$ And yes, that $\,^*$ denotes complex conjugation. For an understanding of how the correlator output equals the matched filter output at the sampling instant ($t=0$ in this instance), see the last part of this answer of mine. In the answer cited, the matched filter with sampling instant $0$ is called the matched filter.

The Matched Filter is an optimum correlation to a particular waveform that may be buried in additive white noise. By multiplying by the complex conjugate of the waveform of interest, we can optimally increase the SNR of the final result once the summation is complete. (Note that in this case we are doing the summation over the k samples and the one final result is the one sample of interest that would have maximum SNR for purposes of signal detection or decision).

To see how this works, consider two independent identically distributed random variables; when we sum the two, the mean will double, but the standard deviation (which is the magnitude of the noise component) only goes up by the square root of two when the two samples are uncorrelated (as in white noise). If we added 100 samples, the sum will go up by 100 (equal mean samples) but the standard deviation will only go up by 10. This is called Processing Gain and leads to the relationship $PG = 10Log_{10}(N)$ where PG is the processing gain in dB (which is the increase in SNR due to this process).

Below is a graphic demonstrating this specifically. Here we show a waveform of interest $x(t) = e^{j\omega_o t}$, that is received as $y(t)$ with the addition of additive white Gaussian noise. Noting that $Ke^{j\phi}$ is simply a phasor of magnitude K and angle $\phi$, the graphic below shows both $y(t)$ and $x^*(t)$ (yes * is the complex conjugate) at three successive samples in time as $x(n)$ and $y(n)$ (n = 0, 1 2). $y(n)$ additionally has noise represented by a dashed line in the graphic at its standard deviation. (So given additive white Gaussian Noise, there is a 63% chance our actual sample for $y(n)$ in each case is inside the dashed line circle shown.)

Again to be very clear, the application here is that we received $y(t)$, and we may believe that $x(t)$ is buried in our received signal, so we correlate using x(t) to optimize our chances of detection, or similarly the received SNR of our known waveform. Below we will see how when the signals are indeed matched (and importantly aligned in time), we will get the best SNR by using the complex multiplcation and sum process that is inherent in the matched filter.

The process of the matched filter (or any correlation) is to multiply and accumulate (in a discrete system, or integrate in continuous time). So the correlation of the three samples shown will simply be $x^*(0)y(0)+x^*(1)y(1)+x^*(2)y(2)$.

At the first sample, when n=0, both $y(0)$ and $x^*(0) = e^{j0}$ which is a phasor with magnitude 1, angle 0. $y(n)$ additionally has noise represented by the dashed line as noted earlier. So the result of the first product $x^*(0)y(0)$ is simply y(0) since x(0) in this case = 1. Importantly after the first product we still have the same standard deviation on the noise.

On the processing of the second sample (n=1) we begin to see the beauty of the matched filter (and the reason why complex conjugate is so important!). So at sample n=1 we have transitioned forward in time, and with x(t) is a phasor rotating in time counter clockwise (increasing phase). Therefore the complex conjugate is a phasor rotating clockwise, as represented by the red phasor in the middle graphic. Meanwhile the received signal y(t) has rotated counter-clockwise as represented by the black phasor at y(1). Multiplying phasors results in their angles adding, so in this case as a result of the product of the two we have simply rotated the black phasor y(1) back to the real axis! It is this result that is then added to the first sample due to the summation. The the signal level itself sums to 2 at this point but the noise in the first sample is added to the noise in the second sample. These two samples have uncorrelated noise, so the standard deviation has only gone up by $\sqrt{2}$. And again following this to the third sample, the signal goes up by 3 and the noise (it's standard deviation) goes up by $\sqrt{3}$, and thus the SNR has increased by $10\log_{10}(3) = 4.7$ dB Below shows what occurs with a slight frequency offset. Here the reference phasor (as coefficients in our matched filter) is not exactly a match to the waveform of interest within y(n). The standard deviation of the noise still goes up the same amount ($\sqrt{3}$), but because our signal component was not exactly matched, we did not get the maximum gain for the signal. This shows and demonstrates matching with waveform that had constant magnitude but the phase was the temporal change being matched (and the importance of using complex conjugate for properly aligning the phase specifically). To add an intuitive understanding of matching the amplitude within the matched filter, consider that we are scaling the received signal (reducing both signal AND noise) when the signal component is known to be small (and reduced to zero if we know the signal component is zero!), and maximizing the received signal when the signal component is known to be large. So each sample is properly scaled prior to accumulating the result in such a way that would similarly maximize the SNR.

• Good information here, but one thing to note that a matched filter is the optimum detector on the AWGN channel. If your channel has interference other than additive white Gaussian noise, a matched filter is not necessarily optimal. – Jason R Sep 20 '18 at 11:56
• Yes absolutely! Thanks Jason - I will make that clearer explicitly. I think the key thing is that it is white (all samples uncorrelated) and really doesn't depend on the magnitude distribution (uniform, Gaussian, etc)-- would you agree with that? – Dan Boschen Sep 20 '18 at 11:58
• Thank you for the explanation! Would you perhaps know of a reference text which has the derivation of the matched filter in more detail than in the Wikipedia article? – Trent Park Sep 20 '18 at 17:30
• No unfortunately not; the Wikipedia article and its references seem quite detailed! – Dan Boschen Sep 20 '18 at 18:22