Re: Integer FFT

Hi all,

I am trying to compute the FFT of signal using the integer FFT method.
In this I am able to represent the twiddle factors in sum of powers of
two, to do the multiplication operations using the shift and addition
operations.
Example how to multiply 0.7071 with 0.255 using shift and addition
operators only by representing the data in binary form.

But the thing is I am not able to get the proper results of
multiplications, as I am getting in the fraction multiplication. Here
I am getting some precision error.
To compensate this error do I need to add the extra value. If yes how
to do that one.

If any one know about this, please help me.

Eagerly waiting for your replay.
Thanking you in advance.

On 1/10/2012 7:17 AM, Sangamanath Kalashetty wrote:
> Hi all,
>
> I am trying to compute the FFT of signal using the integer FFT method.
> In this I am able to represent the twiddle factors in sum of powers of
> two, to do the multiplication operations using the shift and addition
> operations.
> Example how to multiply 0.7071 with 0.255 using shift and addition
> operators only by representing the data in binary form.
>
> But the thing is I am not able to get the proper results of
> multiplications, as I am getting in the fraction multiplication. Here
> I am getting some precision error.
> To compensate this error do I need to add the extra value. If yes how
> to do that one.
>
> If any one know about this, please help me.
>
> Eagerly waiting for your replay.
> Thanking you in advance.

I don't usually respond to private emails that ought to have been posted 
to the group, but I did respond to yours. I hope you find the response 
helpful.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On 1/10/12 7:17 AM, Sangamanath Kalashetty wrote:
> Hi all,
>
> I am trying to compute the FFT of signal using the integer FFT method.
> In this I am able to represent the twiddle factors in sum of powers of
> two, to do the multiplication operations using the shift and addition
> operations.
> Example how to multiply 0.7071 with 0.255 using shift and addition
> operators only by representing the data in binary form.
>

by "binary form", you mean as a 2's complement integer, right?

one of your numbers is a coefficient (i'll bet it's the 0.7071) and the 
other is a signal (the 0.255).  if W is the word width in bits, then to 
do this with scaled integers, you must first decide what the *range* of 
your coefficients and signals are.  for the moment i will assume that 
both have range of -1 <= x < 1.  then the integer version has range of 
-2^(W-1) <= X < 2^(W-1)  .   so what that means is that

         X = x * 2^(W-1)
and
         x = X * 2^(1-W)

make the same definition for the number y and it's scaled integer 
version, Y.  then as what is x times y?

        x*y = X * 2^(1-W) * Y * 2^(1-W)

            = X*Y * 2^(2-2W)

we know that x*y is also constrained to be between -1 and +1 and we want 
the product to also have a scaled integer version just like x and y 
have.  that is what we want is:

        x*y * 2^(W-1)

that is the answer we want.  so you plug and chug and get:


        x*y * 2^(W-1)  =   X*Y * 2^(1-W)

so you take your two integer values and multiply them together.  make 
sure the product register or variable has enough bits (2W).  if you're 
doing this in C, multiplying two longs together should be a long long 
and you will have to cast one of the values to long long first, before 
multiplying (that is a deficit in the C language, in my opinion).  then 
after multiplying you have to arithmetic shift the result to the right 
by W-1 bits (which is the same as multiplying be 2^(1-W)) and take your 
result out of the lowest W bits.

if you want to round to the nearest, you must first add something like 
2^(W-2) to the result because shifting right always truncates.

another method to deal with rounding is to add a random number that 
ranges from 0 to just under 2^(W-1) (we call that "dither") or to save 
the bits that you are dropping and add them in the next time (but i am 
not sure how you do that for an FFT).  some of us call that "fraction 
saving" and it is a form of noise shaping or error shaping.


> But the thing is I am not able to get the proper results of
> multiplications, as I am getting in the fraction multiplication. Here
> I am getting some precision error.

need more bits.

> To compensate this error do I need to add the extra value. If yes how
> to do that one.
>
> If any one know about this, please help me.

simple matter of scaling and integer arithmetic.  the rounding makes it 
slightly more complicated, but not much.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Jan 10, 12:17&#4294967295;pm, Sangamanath Kalashetty <pintu2...@gmail.com>
wrote:
> Hi all,
>
> I am trying to compute the FFT of signal using the integer FFT method.
> In this I am able to represent the twiddle factors in sum of powers of
> two, to do the multiplication operations using the shift and addition
> operations.
> Example how to multiply 0.7071 with 0.255 using shift and addition
> operators only by representing the data in binary form.
>
> But the thing is I am not able to get the proper results of
> multiplications, as I am getting in the fraction multiplication. Here
> I am getting some precision error.
> To compensate this error do I need to add the extra value. If yes how
> to do that one.
>
> If any one know about this, please help me.
>
> Eagerly waiting for your replay.
> Thanking you in advance.

Think of it like this:

0.7071 X 10^4 X 0.255 X 10^3 = 0.7071 X 0.255 X 10^7 right?

So whatever the result you have to divide by 10^7 or multiply by 10^-7
to get the correct answer

0.7071 X 10^4 X 0.255 X 10^3 = 7071 X 255 = 1803105

apply the 10^-7 factor leaves 0.1803105


All you have to do is repeat this using binary arithmetic and you are
somewhere along the way to understanding what fixed point arithmetic
is all about.

A couple of golden rules:

1. You can multiply any two numbers which have different scaling
factors applied (like the above example)
2. It is only meaningful to add numbers if they have the SAME scaling
factor (try it)

I'm afraid as others have said, you have to go through the basics of
fixed point arithmetic before you can think about an application such
as the FFT algorithm.