Convolution
geokonst
Posts: 48
Dear all. Out of curiosity; Has anyone attempted to use the propeller for convolution (or crosscorelation)? If yes, has anyone attempted to use it for convoluting analogue sources?
Thank you
Thank you
Comments
I can explain you what I know by convolution... :
Imagine you have a protein, when you electrospray it it will be mutlple times charged with some gaussian amplitude distribution. In a low mass range mass spectrometer it will show as several peaks with different m/z and *ideally* a gaussian amplitude distribution. But that spectrum is not *real*. because ideally you should get one peak per substance, but as it is a protein it can be bind more ions, resulting in different ions with different m/z (from there more than one peak).
Now, Mass_protein = any_m/z*charge
That means that from two or more peaks you can deconvolute the signal and reconstruct the original peak mass.
An example !
Aprotinin has a mass of 6511.51 amu, but in a low mass rage spectrometer (z.B. TSQ 700 or TSQ7000), you will see three or four peaks at : 1085.25, 1302.3, 1627.87, 2170.5 m/z.
Applying the formula above you get 5611.51, when the charges are 6, 5, 4 and 3.
Has anything to do with this ? (If not, enlighten me please).
From wikipedia:
·
In the discrete domain what is usually done is first reverse one waveform in the time axis. Then slide one waveform in the time axis (delay by samples) and multiply them together.
·
If the two functions are even remotely alike the convolution will give a spike at the sample delay that they were most alike.
·
From there it’s up to your imagination what you can do. You can for example use the result and trigonometry to localise a sound source (what I am trying to do). Or use it for machine stereo vision or a 1000 more uses.
Leon
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Amateur radio callsign: G1HSM
Suzuki SV1000S motorcycle
Rayman: do you usually do in the frequency domain using the prop or in general? Isn't swiping through all frequencies more computationally expensive? Please tell me more as I have never tryed using the freq domain.
Leon
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Amateur radio callsign: G1HSM
Suzuki SV1000S motorcycle
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer
Parallax, Inc.
Here is a 512 point integer fft, data is in HUB RAM, sin and cos are calculated with the tables (the only routine I know works). Disclamer: I did not test it. But it is writen
I wrote it around july, I made a post about it. I hope it works. Put it to good use !
Ale
Graham
Paul: I would love to do the fft for the Prop... But, it's hard to justify for me now, because I'm not doing anything that needs it at the moment. I've coded fft and ifft in few different languages in the past and it wasn't that hard. But, now realize that the lack of native floating point might be an issue... I know there are integer versions of fft though, but maybe not in Numerical Recipes...
I think time domain for small delays (as small as the mem allows) is much easier.
Marty
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Lunch cures all problems! have you had lunch?
As convolution is nothing more than multiplying and shifting why not just code it up, it won't take you long and you have an audience of people that are happy to assist.
Graham
Leon
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Amateur radio callsign: G1HSM
Suzuki SV1000S motorcycle
We have to start with an excurse on vectors. A vector can be represented by a list of values, normally written: (1, 0 , 2, 3, 4, ...), where every single number is a component and the count of numbers N is the dimension of this vector. The length of the vector is the square root of the sum of the squares of all components. This length is called "scalar product". The square of one component can more generally be seen as the product of component times component. This little difference in point of view is very important. It gives you the ability to determine, if two different vectors are equal. Two vectors are equal, when they are of the same length AND if their scalar product equals this length.
Whenever you compare to vectors to get a measure for their similarity, you have to follow these steps:
1. Determine the length of the individual vectors and divide every component by this value. The result is a vector of length 1. This is called "normalisation".
2. Determine the scalar product of these two vectors.
If the result is 1, the vectors are equal. The original vectors at least show the same direction, the vector are colinear. The result can be less one, even zero.
If the result is 0, the vectors are perpenticular and have no similarity.
The closer the result comes to 1, the more similar the two vectors are.
What has this to do with "convolution" and "correlation"?
Let's start with correlation. This operation answers the question, if a given signal is hidden into another signal. Indeed, it is nothing but computing the scalar product.
The most simple case is:
two signals of same dimension:
( 1, 0, 1, 0, 1, 0, 1, 0, 0) , ( 1, 0, 1, 0, 1, 0, 1, 0, 0). Both signals are obviously identical, but can I get this result by "computation"?
The length of the first vector: Sqrt ( 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 0*0 ) = 2
The length of the second vector: Sqrt ( 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 0*0 ) = 2
The scalar product of first and second vector: Sqrt ( 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 1*1 + 0*0 + 0*0 ) = 2
-> They are equal!
But what, if the two vectors are not of same dimension, the first one is longer?
( 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0)
Now the scalar product is not defined! What to do?
We have to compute the scalar product for the first 9 components and then we shift the shorter vector by one and recalculate and do this until we reach the end. For every shift we get a scalar product as an result and we can plot this as a function of shiftvalue. This function we call the correlation function.
To correlate answers the question, if there is a signal hidden in another signal.
Now let us analyse this situation:
Signal 1: ( 1, 0, 1, 0, 1, 0, 1, 0, 0)
Signal 2: ( 0, 1, 0, 1, 0, 1, 0, 1, 0)
Obviously, these signals are perpenticular, for the scalar product is 0. But the second signal is made from the first by shifting one step. How to find this out by simple calculation?
We just double the first vector:
Signal 1: ( 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0)
and then compute the correlation function. And we will see, there is one position with scalar product 1, other positions show a value between 0 and 1. According to the problem we are talking about we can say: a signal is hidden into another signal, if the scalarproduct exceeds a certain threshold value, may .9, maybe .9999. It depends.
Convolution is nothing but the same play, seen from another point of view. If you have the correlated function as an input, you can ask the question: what was the original function? Backward computing is called "deconvolution". But, then you have to know the vector, which was used to compute the correlated function.
How to solve all these problems depends on different conditions. Do you have computing power and memory? What is the timescale. Can you make a good first guess? And so on. FFT is for certain reasons used, but there is principle limit: FFT can only be computed for dimensions of 2power N. You can not deconvolute a signal with 112 values.
Problem is I have very little experience coding in spin and since I need to do convolution between the inputs of two microphones, I wonder if I have to implement it in assembly for better timing (which is even worse for a newbie). This is why I asked if anyone had already tried to do convolution with the propeller. Coding something like this sounds trivial for an experienced developer but it’s huge for me.
This is why I was (and still am) trying to feed the adc output to the stereo spatializer object which does the delay and then figure out a way to do the multiplication. The more I am trying this approach the more this seems like an overkill so I will probably try my best to write some convolution code instead during the next week(s).
I am sorry but I do not understand what you are trying to say. The mechanism i have in mind is a DAQ running in one cog that stores a fixed nunber of stereo sound samples in a circular buffer (the size really depends on sampling frequency and required minimum delay (which depends in the distance between the microphones)). Then another cog taking different delays (different starting points within the buffer) and corelating the waveforms. Ideally it would swipe through all available delays but a few fixed delays could also be used in order to do this as fast as possible.
I hope I was clear enough. Again; thanks for all the responses.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer
Parallax, Inc.
First you create a short pulse and watch for the reflection. This gives you an impression, if there is an echo at all and what the rough runtime is. There might come different reflections from different reflectors, hopefully in different directions.
Now you generate a periodical pulse train, the rate small enough to have the reflections separated.
To lower the noise and increase precision, you then start the correlation, which is more an auto- then a crosscorrelation, for you receive twice the same signal, only timeshifted. The first estimation for the shift-value you know from the first pulse.
The scalar product (multiply, add) reaches the highest value, if you timeshift is correct. Therefore you can calculate values for three shifts: one to short, one correct and a third to long, with same distance. If the peak is symmetrical, the short and long value will be equal. In the case, the correct one is really maximal. Test this presumption by slightly modifing the shift value. This is similar to a phase locked loop.
After this works, you can proceed by creating a noise signal and correlate it, but I think, then a FFT is better to do the correlation.
Just note that I am not interested in sound impulses which is much easier. I am more interested in continuous sounds. Thanks for the replies.