Interested in learning about correlation and how to implement it in a digital signal processing system? In Circuit Cellar 299, Robert Lacoste addresses the subject without going overboard with complicated mathematics. He explains how a simple correlation calculation can drastically improve a system’s performance.
Imagine a situation in which you have a noisy signal that includes replications of a given pattern. Each replication is more or less accurate, has a varying amplitude, and could be situated anywhere in the signal (see Figure 1). The pattern is known, even if it could have any shape. Also imagine that your boss or client asked you to find an algorithm that will locate each occurrence of the pattern in the signal and give an estimation of its amplitude. Not obvious, right? Well, it’s actually quite easy. This is a classic situation for which you can apply a simple mathematical operation: correlation.
Figure 1: This figure shows a given pattern (top) replicated two times in a noisy signal at different amplitudes (middle). The goal of the game is to identify the two replications (bottom).
Before I define correlation and explain how to implement it in a DSP system, let’s cover a few typical applications first. A radar system includes a transmitter and a receiver. The former sends out some pulses. The receiver must recognize the echoed pulses, which each corresponding to an obstacle. That’s exactly what a correlation is made for! Even if a radar is one of the best examples, there are thousands of other possible applications. Want to improve the performance of a sensor with information about the shape of the signal being detected? Use correlation. Need to identify a given vibration on an accelerometer-based system? Correlation is answer once again. The list is endless.
ALGORITHMS
The good news about correlation is that the calculations are quite simple to explain and even simpler to implement in a software-based project or in an FPGA. Since I’m talking about digital systems, you can safely assume that the signal is digitized (by an analog-to-digital converter) and defined by N successive samples. Similarly, the pattern to be found is a set of M successive samples, which are also some numeric values. Let’s assume that the pattern is shorter than the input signal so that M < N. How should you proceed?
The correlation calculation works as follows. Start by positioning the pattern above the first M points of the signal. For each sample of the pattern, multiply the corresponding pattern and signal values and then sum all the results. You’ve got the first point of the correlation. Then shift the pattern by one sample on the right and do the same calculation again to find the second point of the correlation. Continue up to the end of the signal and you’ve got the correlation of the pattern and signal, which has N – M + 1 points in that case. Refer to Listing 1 if you prefer pseudocode to a description (assuming the index are numbered from 0 to N – 1).
Listing 1: This pseudo-code implements the correlation algorithm.
Very simple, right? The process is illustrated on Figure 2. How does this calculation answer to our problem? Very simply: The calculated correlation is higher when the signal and pattern matches.
Figure 2: A correlation works by progressively shifting the pattern (middle relatively to the signal (top). At each position, the two curves are multiplied term-by-term and summed, giving one point on the resulting correlation (bottom).
So you have just to locate peaks on the calculated correlation. The position of the peaks shows where the pattern are located in the signal, and their amplitudes are directly proportional to the amplitude of the replica.—Robert Lacoste (Circuit Cellar 299, 2015)
This article appears in Circuit Cellar 299 (June 2015).
Circuit Cellar's editorial team comprises professional engineers, technical editors, and digital media specialists. You can reach the Editorial Department at editorial@circuitcellar.com, @circuitcellar, and facebook.com/circuitcellar
