Hello!
I'm student, planing to work with FPGA for my thesis. Totaly unexperienced. Here I'm wondering about the speed. Don't feel the speed of multipliers, shifting, adding,...
My plan is to implement circular Hough transform for images. There are many issues, here I'm wondering about one of them.
I'll try to present mathematical problem in short for those who are unfamiliar with Hough transform and ask you what do you think which solution is better, faster,... FPGA with embedded multipliers will be provided for me. I'll propose 2 solutions.
Also, you could just tell me how fast are multipliers compared to some other operations, like shifting, adding numbers.... Just to feel this numbers, anything :) I don't need 'ns', even to say this operation is 2x faster than this one... I'll be using 18-bit signals. So if you post just comparision of this operations, it will be very helpful for me. I still don't know to read 'data sheets' that good so...
What is the speed of this?
18-bit signed number (signal), multiply (with embedded multiplier), shifting, adding?-= Problem =-
It will be simplyfied...
I need to compute this: (1) x = R*gx/mag y = R*gy/mag
All of this are signed integers fitting in 18 bits. 'R'...constant gx,gy...inputs
'gx' & 'gy' represent vector (gx,gy) in Carthesian system.
'mag'...magnitude of vector (gx,gy)
I could rewrite (1) like this: (2) x = R*cos(fi) y = R*sin(fi)
'fi'...angle between vector (gx,gy) and x-axis
-= CORDIC =-
For CORDIC I like expression (2). Define this: grad = vector (gx,gy) sol = vector (R,0)
Using CORDIC I rotate vector 'grad' and 'sol'. They are rotate for the angle of 'fi'. 'grad' is rotated in one direction, 'sol' in the opposite. I don't need to compute 'fi'. Vectors are rotated until vector 'grad' becomes equal to (mag, 0), or just to say until the 2nd component of vector becomes 0. After this rotations, vector 'sol' holds the solution.
To be honest, haven't tryed implementing this one. I see that precision rotating angle in iterations can also effect this problem a lot. Anyway, if you can give me any kind of input for this problem, I'll be happy to hear.
-= arithmetic expression =-
Don't know how to call that. Hope you understand. I use this expression: x = (R*gx)/mag y = (R*gy)/mag
'mag' is computed like this: mag = abs(gx) + abs(gy)...it's precise enough for me
I'll be using embedded multipliers to compute 'R*gx', so no problem with that. Problem is divison. For division I'll use gold-smith algorithm. I think it should converge to my solution in 7 iterations, where in each iteration I have to multiply 2 numbers(actualy 2x times, but paralel, so no problem, I look at it like one operation) and then substract a number from one product (something like that).
Important part of pseudo-code: paralel: a1 = a1*m; b = b*m; following: m = constant - b;
-= help =-
I'm unexperienced. I wonder is it worth implementing both of them and comparing them. It could be interesting, but it's not my problem actually. I should implemented anything and my menthor would accept any solution since he's also unexperienced with it. If you think one solution is by far better, can you explain why you think so? If you think they are both good and fast comparing to each other, I'll probably try to implement both of them.
You can also propose anything else, if you feel so. There is an idea of distributed arithmetics, but still haven't spend time in learning about this solution.