What is the difference between convolution and correlation?

Answer 1

Courtesy: Mr.Steven W. Smith, Ph.D & Geoff Martin, B.Mus., M.Mus., Ph.D. Culled by : Nandakumar.R,VLSI Design Engineer Let's think back to the process of real convolution with the example of convolving an audio signal with the impulse response of a room. The first sample of the signal is multiplied by the first tap (sample) in the impulse response first. The two signals (the audio signal and the impulse response) move through each other until the last sample of the audio signal is multiplied by the last tap in the impulse response. This is conceptually represented in Figure 9.60. {| |+ align="bottom" |Figure 9.60: A block diagram of the concept of convolution. Notice that one of the signals is time-reversed. |- | |} Notice in that figure that the two signals are opposite each other - in other words, the audio signal in the diagram reads start to end from right to left while the impulse response reads from left to right. What would happen if we did exactly the same math, but we didn't time-reverse one of the signals? This idea is shown in Figure 9.61. {| |+ align="bottom" |Figure 9.61: A block diagram of a process similar to convolution, but it's not. Notice that neither of the signals is time-reversed. |- | |} You may be asking yourself what use this could possibly be. A fair question. Let's have a look at an example. We'll start by looking at a series of 16 completely random numbers, shown in Figure 9.62. If I were a statistician or a mathematician, I would say that these were random numbers. If I were a recording engineer, I would call it white noise. {| |+ align="bottom" |Figure 9.62: |- | |} Let' s take that signal, and put it thought the process shown in Figure 9.61. Instead of using two different signals, we're going to use the same signal for both. So, we start as in Figure 9.63, with the two signals lined up, ready to multiply by each other. In this case, we're multiplying each sample by its corresponding sample (see the caption). We then add all the results of the multiplications and we get a result. In this case, since all the multiplications resulted in 0, the sum of all 32 zero's is 0. {| |+ align="bottom" |Figure 9.63: The top graph shows the original noise signal from Figure 9.62. The middle graph shows the same signal, but offset in time. We multiply sample 1 from the top graph by sample 1 from the middle graph and the result is sample 1 in the bottom graph. We then add all the values in the bottom graph to each other, and the result is 0. |- | |} Once we get that result, we shift the two signals closer together by one sample and repeat the whole process, as is shown in Figure 9.64. {| |+ align="bottom" |Figure 9.64: The same two signals as in Figure 9.63, moved closer together by one sample. After these are multiplied, sample by sample, and all the results are added together, the result in this particular case will be 0.15. |- | |} Then we move the signals by one sample and do it again, as is shown in Figure 9.65. {| |+ align="bottom" |Figure 9.65: The process again, with the signals moved by one sample. The result of this addition is 0.32. |- | |} We keep doing this over and over, each time, moving the two signals by one sample and adding the results of the multiplications. Eventually, we get to a point where the signals are almost aligned as in Figure 9.66. {| |+ align="bottom" |Figure 9.66: The process again, after the signals have been moved until they're almost aligned. The result of this addition is -0.02. |- | |} Then we get to a point in the process where an important thing happens. the two signals are aligned, as can be seen in Figure 9.67. Up until now, the output from each set of multiplications and additions has resulted in a fairly small number, as we've seen (the list of all the values that I haven't shown will be given later...). This is because we're multiplying random numbers that might be either positive or negative, result in numbers that might be either positive or negative, and adding them all together. (If the two signals are very long, and completely random, the result will be 0.) However, when the two signals are aligned, the result of all the individual multiplications will be positive (because any number other than 0, when multiplied by itself, gives a positive result). If the signals are very long and random, not only will we get a result very close to zero for all other alignments, we'll get a very big number for this middle alignment. The longer the signals, the bigger the number will be. {| |+ align="bottom" |Figure 9.67: The process again, when the signals have been aligned. The result of this addition is 2.18. Notice that this is a much bigger number than the other ones we've seen. |- | |} We keep going with the procedure, moving the signals one sample in the same direction and repeating the process, as is shown in Figure 9.68. Notice that this looks very similar to the alignment shown in Figure 9.66. In fact, the two are identical, it's just that the top and middle graphs have swapped places, in effect. As expected, the result of the addition will be identical in the two cases. {| |+ align="bottom" |Figure 9.68: The process again, after the signals have been moved one sample past the point where they are aligned. The result of this addition is -0.02. |- | |} The process continues, providing a symmetrical set of results, until the two signals have moved apart from each other, resulting in a zero again, just as we saw in the beginning. If we actually do this process for the set of numbers initially shown in Figure 9.62, we get the following set of numbers: 0.15, 0.32, -0.02, -0.20, 0.08, -0.12, 0.01, 0.43, -0.11, 0.38, 0.02, -0.59, 0.24, -0.35, -0.02, 2.18, -0.02, -0.35, 0.24, -0.59, 0.02, 0.38, -0.11, 0.43, 0.01, -0.12, 0.08, -0.20, -0.02, 0.32, 0.15. If we then take these numbers and graph them, we get the plot shown in Figure 9.69. {| |+ align="bottom" |Figure 9.69: The result of the multiplications and additions for the whole process using the signal shown above. There are two things to notice. First, that the resulting signal is symmetrical. Second, that there is a big spike right in the middle - the result of when the two signals were aligned. |- | |} The result of this whole thing actually gives us some information. Take a look at Figure 9.69, and you'll see three important characteristics. Firstly, the signal is symmetrical. This doesn't tell us much, other than that the signals that went through the procedure were the same. Secondly, most of the values are close to zero. This tells us that the signals were random. Thirdly, there's a big spike in the middle of the graph, which tells us that the signals lined up and matched each other at some point. What we have done is a procedure called autocorrelation - in other words, we're measuring how well the signal is related (or co-related, to be precise) to itself. This may sound like a silly thing to ask - of course a signal is related to itself, right? Well, actually, no. We saw above that, unless the signals are aligned, the result of the multiplications and additions are 0. This meant that, unless the signal was aligned with itself, it is unrelated to itself (because it is noise). What would happen if the we did the same thing, except that our original signal was periodic instead of noise? Take a look at Figure 9.70. Notice that the output of the autocorrelation still has a big peak in the middle - essentially telling us that the signal is very similar (if not identical) to itself. But you'll also notice that the output of the autocorrelation looks sort of periodic. It's a sinusoidal wave with an envelope. Why is this? It's because the original signal is periodic. As the we move the signal through itself in the autocorrelation process, the output tells us that the signal is similar to itself when it's shifted in time. So, for example, the first wave in the signal is identical to the last wave in the signal. Therefore a periodic component in the output of the autocorrelation tells us that the signal being autocorrelated is periodic - or at least that it has a periodic component. {| |+ align="bottom" |Figure 9.70: The top plot is the signal. The bottom is the result of the autocorrelation of the signal. |- | |} So, autocorrelation can tell us whether a signal has periodic components. If the autocorrelation has periodic components, then the signal must as well. If the autocorrelation does not, and is just low random numbers, with a spike in the middle, then the signal does not have any periodic components. Now a different source Explains

The concept of correlation can best be presented with an example. Figure 7-13 shows the key elements of a radar system. A specially designed antenna transmits a short burst of radio wave energy in a selected direction. If the propagating wave strikes an object, such as the helicopter in this illustration, a small fraction of the energy is reflected back toward a radio receiver located near the transmitter. The transmitted pulse is a specific shape that we have selected, such as the triangle shown in this example. The received signal will consist of two parts: (1) a shifted and scaled version of the transmitted pulse, and (2) random noise, resulting from interfering radio waves, thermal noise in the electronics, etc. Since radio signals travel at a known rate, the speed of light, the shift between the transmitted and received pulse is a direct measure of the distance to the object being detected. This is the problem: given a signal of some known shape, what is the best way to determine where (or if) the signal occurs in another signal. Correlation is the answer. Correlation is a mathematical operation that is very similar to convolution. Just as with convolution, correlation uses two signals to produce a third signal. This third signal is called the cross-correlation of the two input signals. If a signal is correlated with itself, the resulting signal is instead called the autocorrelation. The convolution machine was presented in the last chapter to show how convolution is performed. Figure 7-14 is a similar

illustration of a correlation machine. The received signal, x[n], and the cross-correlation signal, y[n], are fixed on the page. The waveform we are looking for, t[n], commonly called the target signal, is contained within the correlation machine. Each sample in y[n] is calculated by moving the correlation machine left or right until it points to the sample being worked on. Next, the indicated samples from the received signal fall into the correlation machine, and are multiplied by the corresponding points in the target signal. The sum of these products then moves into the proper sample in the cross-correlation signal. The amplitude of each sample in the cross-correlation signal is a measure of how much the received signal resembles the target signal, at that location. This means that a peak will occur in the cross-correlation signal for every target signal that is present in the received signal. In other words, the value of the cross-correlation is maximized when the target signal is aligned with the same features in the received signal. What if the target signal contains samples with a negative value? Nothing changes. Imagine that the correlation machine is positioned such that the target signal is perfectly aligned with the matching waveform in the received signal. As samples from the received signal fall into the correlation machine, they are multiplied by their matching samples in the target signal. Neglecting noise, a positive sample will be multiplied by itself, resulting in a positive number. Likewise, a negative sample will be multiplied by itself, also resulting in a positive number. Even if the target signal is completely negative, the peak in the cross-correlation will still be positive. If there is noise on the received signal, there will also be noise on the cross-correlation signal. It is an unavoidable fact that random noise looks a certain amount like any target signal you can choose. The noise on the cross-correlation signal is simply measuring this similarity. Except for this noise, the peak generated in the cross-correlation signal is symmetrical between its left and right. This is true even if the target signal isn't symmetrical. In addition, the width of the peak is twice the width of the target signal. Remember, the cross-correlation is trying to detect the target signal, not recreate it. There is no reason to expect that the peak will even look like the target signal. Correlation is the optimal technique for detecting a known waveform in random noise. That is, the peak is higher above the noise using correlation than can be produced by any other linear system. (To be perfectly correct, it is only optimal for random white noise). Using correlation to detect a known waveform is frequently called matched filtering. More on this in Chapter 17. The correlation machine and convolution machine are identical, except for one small difference. As discussed in the last chapter, the signal inside of the convolution machine is flipped left-for-right. This means that samples numbers: 1, 2, 3 … run from the right to the left. In the correlation machine this flip doesn't take place, and the samples run in the normal direction.

Since this signal reversal is the only difference between the two operations, it is possible to represent correlationusing the same mathematics as convolution. This requires preflipping one of the two signals being correlated, so that the left-for-right flip inherent in convolution is canceled. For instance, when a[n] and b[n], are convolved to produce c[n], the equation is written: a[n] * b[n] = c[n]. In comparison, the cross-correlation of a[n] and b[n] can be written: a[n] * b[-n] = c[n]. That is, flipping b[n] left-for-right is accomplished by reversing the sign of the index, i.e., b[-n]. Don't let the mathematical similarity between convolution and correlation fool you; they represent very different DSP procedures. Convolution is the relationship between a system's input signal, output signal, and impulse response. Correlation is a way to detect a known waveform in a noisy background. The similar mathematics is only a convenient coincidence

Courtesy: Mr.Steven W. Smith, Ph.D & Geoff Martin, B.Mus., M.Mus., Ph.D. Culled by : Nandakumar.R,VLSI Design Engineer Let's think back to the process of real convolution with the example of convolving an audio signal with the impulse response of a room. The first sample of the signal is multiplied by the first tap (sample) in the impulse response first. The two signals (the audio signal and the impulse response) move through each other until the last sample of the audio signal is multiplied by the last tap in the impulse response. This is conceptually represented in Figure 9.60. {| |+ align="bottom" |Figure 9.60: A block diagram of the concept of convolution. Notice that one of the signals is time-reversed. |- | |} Notice in that figure that the two signals are opposite each other - in other words, the audio signal in the diagram reads start to end from right to left while the impulse response reads from left to right. What would happen if we did exactly the same math, but we didn't time-reverse one of the signals? This idea is shown in Figure 9.61. {| |+ align="bottom" |Figure 9.61: A block diagram of a process similar to convolution, but it's not. Notice that neither of the signals is time-reversed. |- | |} You may be asking yourself what use this could possibly be. A fair question. Let's have a look at an example. We'll start by looking at a series of 16 completely random numbers, shown in Figure 9.62. If I were a statistician or a mathematician, I would say that these were random numbers. If I were a recording engineer, I would call it white noise. {| |+ align="bottom" |Figure 9.62: |- | |} Let' s take that signal, and put it thought the process shown in Figure 9.61. Instead of using two different signals, we're going to use the same signal for both. So, we start as in Figure 9.63, with the two signals lined up, ready to multiply by each other. In this case, we're multiplying each sample by its corresponding sample (see the caption). We then add all the results of the multiplications and we get a result. In this case, since all the multiplications resulted in 0, the sum of all 32 zero's is 0. {| |+ align="bottom" |Figure 9.63: The top graph shows the original noise signal from Figure 9.62. The middle graph shows the same signal, but offset in time. We multiply sample 1 from the top graph by sample 1 from the middle graph and the result is sample 1 in the bottom graph. We then add all the values in the bottom graph to each other, and the result is 0. |- | |} Once we get that result, we shift the two signals closer together by one sample and repeat the whole process, as is shown in Figure 9.64. {| |+ align="bottom" |Figure 9.64: The same two signals as in Figure 9.63, moved closer together by one sample. After these are multiplied, sample by sample, and all the results are added together, the result in this particular case will be 0.15. |- | |} Then we move the signals by one sample and do it again, as is shown in Figure 9.65. {| |+ align="bottom" |Figure 9.65: The process again, with the signals moved by one sample. The result of this addition is 0.32. |- | |} We keep doing this over and over, each time, moving the two signals by one sample and adding the results of the multiplications. Eventually, we get to a point where the signals are almost aligned as in Figure 9.66. {| |+ align="bottom" |Figure 9.66: The process again, after the signals have been moved until they're almost aligned. The result of this addition is -0.02. |- | |} Then we get to a point in the process where an important thing happens. the two signals are aligned, as can be seen in Figure 9.67. Up until now, the output from each set of multiplications and additions has resulted in a fairly small number, as we've seen (the list of all the values that I haven't shown will be given later...). This is because we're multiplying random numbers that might be either positive or negative, result in numbers that might be either positive or negative, and adding them all together. (If the two signals are very long, and completely random, the result will be 0.) However, when the two signals are aligned, the result of all the individual multiplications will be positive (because any number other than 0, when multiplied by itself, gives a positive result). If the signals are very long and random, not only will we get a result very close to zero for all other alignments, we'll get a very big number for this middle alignment. The longer the signals, the bigger the number will be. {| |+ align="bottom" |Figure 9.67: The process again, when the signals have been aligned. The result of this addition is 2.18. Notice that this is a much bigger number than the other ones we've seen. |- | |} We keep going with the procedure, moving the signals one sample in the same direction and repeating the process, as is shown in Figure 9.68. Notice that this looks very similar to the alignment shown in Figure 9.66. In fact, the two are identical, it's just that the top and middle graphs have swapped places, in effect. As expected, the result of the addition will be identical in the two cases. {| |+ align="bottom" |Figure 9.68: The process again, after the signals have been moved one sample past the point where they are aligned. The result of this addition is -0.02. |- | |} The process continues, providing a symmetrical set of results, until the two signals have moved apart from each other, resulting in a zero again, just as we saw in the beginning. If we actually do this process for the set of numbers initially shown in Figure 9.62, we get the following set of numbers: 0.15, 0.32, -0.02, -0.20, 0.08, -0.12, 0.01, 0.43, -0.11, 0.38, 0.02, -0.59, 0.24, -0.35, -0.02, 2.18, -0.02, -0.35, 0.24, -0.59, 0.02, 0.38, -0.11, 0.43, 0.01, -0.12, 0.08, -0.20, -0.02, 0.32, 0.15. If we then take these numbers and graph them, we get the plot shown in Figure 9.69. {| |+ align="bottom" |Figure 9.69: The result of the multiplications and additions for the whole process using the signal shown above. There are two things to notice. First, that the resulting signal is symmetrical. Second, that there is a big spike right in the middle - the result of when the two signals were aligned. |- | |} The result of this whole thing actually gives us some information. Take a look at Figure 9.69, and you'll see three important characteristics. Firstly, the signal is symmetrical. This doesn't tell us much, other than that the signals that went through the procedure were the same. Secondly, most of the values are close to zero. This tells us that the signals were random. Thirdly, there's a big spike in the middle of the graph, which tells us that the signals lined up and matched each other at some point. What we have done is a procedure called autocorrelation - in other words, we're measuring how well the signal is related (or co-related, to be precise) to itself. This may sound like a silly thing to ask - of course a signal is related to itself, right? Well, actually, no. We saw above that, unless the signals are aligned, the result of the multiplications and additions are 0. This meant that, unless the signal was aligned with itself, it is unrelated to itself (because it is noise). What would happen if the we did the same thing, except that our original signal was periodic instead of noise? Take a look at Figure 9.70. Notice that the output of the autocorrelation still has a big peak in the middle - essentially telling us that the signal is very similar (if not identical) to itself. But you'll also notice that the output of the autocorrelation looks sort of periodic. It's a sinusoidal wave with an envelope. Why is this? It's because the original signal is periodic. As the we move the signal through itself in the autocorrelation process, the output tells us that the signal is similar to itself when it's shifted in time. So, for example, the first wave in the signal is identical to the last wave in the signal. Therefore a periodic component in the output of the autocorrelation tells us that the signal being autocorrelated is periodic - or at least that it has a periodic component. {| |+ align="bottom" |Figure 9.70: The top plot is the signal. The bottom is the result of the autocorrelation of the signal. |- | |} So, autocorrelation can tell us whether a signal has periodic components. If the autocorrelation has periodic components, then the signal must as well. If the autocorrelation does not, and is just low random numbers, with a spike in the middle, then the signal does not have any periodic components. Now a different source Explains

The concept of correlation can best be presented with an example. Figure 7-13 shows the key elements of a radar system. A specially designed antenna transmits a short burst of radio wave energy in a selected direction. If the propagating wave strikes an object, such as the helicopter in this illustration, a small fraction of the energy is reflected back toward a radio receiver located near the transmitter. The transmitted pulse is a specific shape that we have selected, such as the triangle shown in this example. The received signal will consist of two parts: (1) a shifted and scaled version of the transmitted pulse, and (2) random noise, resulting from interfering radio waves, thermal noise in the electronics, etc. Since radio signals travel at a known rate, the speed of light, the shift between the transmitted and received pulse is a direct measure of the distance to the object being detected. This is the problem: given a signal of some known shape, what is the best way to determine where (or if) the signal occurs in another signal. Correlation is the answer. Correlation is a mathematical operation that is very similar to convolution. Just as with convolution, correlation uses two signals to produce a third signal. This third signal is called the cross-correlation of the two input signals. If a signal is correlated with itself, the resulting signal is instead called the autocorrelation. The convolution machine was presented in the last chapter to show how convolution is performed. Figure 7-14 is a similar

illustration of a correlation machine. The received signal, x[n], and the cross-correlation signal, y[n], are fixed on the page. The waveform we are looking for, t[n], commonly called the target signal, is contained within the correlation machine. Each sample in y[n] is calculated by moving the correlation machine left or right until it points to the sample being worked on. Next, the indicated samples from the received signal fall into the correlation machine, and are multiplied by the corresponding points in the target signal. The sum of these products then moves into the proper sample in the cross-correlation signal. The amplitude of each sample in the cross-correlation signal is a measure of how much the received signal resembles the target signal, at that location. This means that a peak will occur in the cross-correlation signal for every target signal that is present in the received signal. In other words, the value of the cross-correlation is maximized when the target signal is aligned with the same features in the received signal. What if the target signal contains samples with a negative value? Nothing changes. Imagine that the correlation machine is positioned such that the target signal is perfectly aligned with the matching waveform in the received signal. As samples from the received signal fall into the correlation machine, they are multiplied by their matching samples in the target signal. Neglecting noise, a positive sample will be multiplied by itself, resulting in a positive number. Likewise, a negative sample will be multiplied by itself, also resulting in a positive number. Even if the target signal is completely negative, the peak in the cross-correlation will still be positive. If there is noise on the received signal, there will also be noise on the cross-correlation signal. It is an unavoidable fact that random noise looks a certain amount like any target signal you can choose. The noise on the cross-correlation signal is simply measuring this similarity. Except for this noise, the peak generated in the cross-correlation signal is symmetrical between its left and right. This is true even if the target signal isn't symmetrical. In addition, the width of the peak is twice the width of the target signal. Remember, the cross-correlation is trying to detect the target signal, not recreate it. There is no reason to expect that the peak will even look like the target signal. Correlation is the optimal technique for detecting a known waveform in random noise. That is, the peak is higher above the noise using correlation than can be produced by any other linear system. (To be perfectly correct, it is only optimal for random white noise). Using correlation to detect a known waveform is frequently called matched filtering. More on this in Chapter 17. The correlation machine and convolution machine are identical, except for one small difference. As discussed in the last chapter, the signal inside of the convolution machine is flipped left-for-right. This means that samples numbers: 1, 2, 3 … run from the right to the left. In the correlation machine this flip doesn't take place, and the samples run in the normal direction.

Since this signal reversal is the only difference between the two operations, it is possible to represent correlationusing the same mathematics as convolution. This requires preflipping one of the two signals being correlated, so that the left-for-right flip inherent in convolution is canceled. For instance, when a[n] and b[n], are convolved to produce c[n], the equation is written: a[n] * b[n] = c[n]. In comparison, the cross-correlation of a[n] and b[n] can be written: a[n] * b[-n] = c[n]. That is, flipping b[n] left-for-right is accomplished by reversing the sign of the index, i.e., b[-n]. Don't let the mathematical similarity between convolution and correlation fool you; they represent very different DSP procedures. Convolution is the relationship between a system's input signal, output signal, and impulse response. Correlation is a way to detect a known waveform in a noisy background. The similar mathematics is only a convenient coincidence