text:
Correlating to good effect
1 Comment
After reading this sentence, your brain will already have completed a correlation task far more complex than most applications require. In short, correlation is a mathematical way to carry out pattern recognition returning a value proportional to how good the match was. Taking lottery numbers as an example, a perfect correlation could change your life. Another example is being able to detect your name being said in a noisy room – the 'Cocktail Party Effect'.
Apart from our own in-built audio-visual recognition units, correlators are a surprisingly common part of everyday life. They are used in wireless systems such as mobile phones, WiFi, digital TV and remote controls, where a receiving device has to lock onto and interpret information that is being transmitted. They are also used to aid high-speed communication between devices even though physically they may only be a couple of centimetres apart. So how can correlators help you?
First, how does a correlator work in practice?
Going back to the Cocktail Party Effect, somewhere in the brain your name is stored and any incoming sounds are run past this template. We can imagine that for every letter that matches, a point is awarded. In the examples below, an incoming word is moved past our template and, as expected, the maximum score is obtained when the two words are aligned. In maths, this process of matching two patterns as a function of time is called cross-correlation.
In practice, the operation of matching each letter in the above example could be achieved by assigning values to the letters and using multipliers at each letter position. The final score would be the summation of all of these partial contributions.
For FPGA implementations, multiplication can rapidly consume valuable hardware resources. Fortunately the multiplications can usually be reduced to additions because the template word is very often a simple sequence of ±1. The summation can also quickly drain resources, however using a technique called sub-expression sharing we can make savings by taking advantage of any repeated bit patterns.
Canonic Signed Digit (CSD) arithmetic is another good optimisation tool when fixed value multiplications are required, because it uses digits +1, 0 or –1. As an example, rather than binary encoding 15 as "01111" (8+4+2+1), we can use "1000-" (16-1) and save arithmetic operations.