Mathematician needed! Multiply then Add vs Add then Multiply

[Galaxyrise]

I can't argue this point because my colleague doesn't believe it...

I would think your proof by example was good enough.  On what grounds was it rejected? Here's a direct proof:

Let ADCn = (An*256 + Bn), where An and Bn are integers
Let SCALARn = Xn, where Xn is an integer

Ideally, the sum yields:

Code: [Select]

TRUNC(SUM(An*Xn) + SUM(Bn*Xn)/256)
Doing the divide before add changes this to: (assuming the MulDiv is done correctly)

Code: [Select]

SUM(An*Xn) + SUM(TRUNC(Bn*Xn/256))
Subtracting the two produces the difference between the two approaches:

Code: [Select]

TRUNC(SUM(Bn*Xn)/256) - SUM(TRUNC(Bn*Xn/256))

Let Bn*Xn = Cn*256 + Dn.  The difference can now be expressed as

Code: [Select]

TRUNC(SUM(Cn) + SUM(Dn)/256) - (SUM(Cn) + SUM(TRUNC(Dn/256)))

since Dn < 256, then that reduces to

Code: [Select]

TRUNC(SUM(Dn)/256)

Since the largest Dn can be is 255, the maximum error is SUM(255)/256 = 255*16/256 = 15.

[JacquesBBB]

I am not sure  I see exactly what you are doing, but  it seems that you could use
an additional 16 bit register to store all the remainders, multiplied by the numerator of the scaling factor.

I understand that you want to sum   16 values like  A_n* b_n/256 where b_n can change from  1 to 255
and A_n is a 12 bit number

I am doing a little bit rapidly so forgive me if there is some errors (not checked) but

R=0;
S=0;

for n= 1 to 16 {
  R += (A_n && FF)*b_n ;
  S += R>>8;
  R  = R && FF;
  S += (A_n >>  8 ) * b_n;
}

Should give  a proper  result  with only 16 bits for R and S.

That's 32 bits (16 for R and 16 for S).  If he can't swing 24 bits he certainly can't swing 32.

But you can just discard  R at the end and just transmit S.

The final result is on 16 bits, precise up to the latest bit.

The only thing that is discarded is  the fractionary part
R/256 where  R< 256

[Mechatrommer]

I can't argue this point because my colleague doesn't believe it...

then ask the dickhead to draw his proof. as for you, its as simple as trimming a skinhead proof...

Code: [Select]

12bits ADC x 8bits SCALAR value = log2(2^12 x 2^8) = 20bits
sum 16 of that = log2(2^20 x 16) = 24bits
integer division doesnt require extra bits
you laid your proof, now its his turn, ymmv..

edit: as for requiring 16bits, he has to proof some bits are insignificant and "binary division" (aka bitshift) or arithmetic precision loss is acceptable. that is the "application specific" we cant help.

[IanB]

If I round them down (lose the precision, decimal places, whatever) then the result is the same as the one significant number.  But all those little 15 numbers might add up to be a little bit significant and ignoring them early introduces an error.

Why round them down? Why not round to the nearest integer? If you do that some will round down, some will round up, and on average over many samples you will keep the original sampling precision.

[Mechatrommer]

whats with the "all round down" or "all round up" case that will lead to error accumulation? that needs some serious analysis well, 24 bits is not so bad, you only need list of 16millions number thats pretty easy with modern computer. i'm not going to do the statistical homework though...

[Phoenix]

Why not take the pragmatic approach and program each method into your favourite C compiler, with the appropriate truncations. Then just set up some test case inputs and see which method produces the output you want (vs say the ideal/floating point case).

[JacquesBBB]

As I said, not being familiar  with FPGA, I do not know if this applies but  compared to

R=0;
S=0;

for n= 1 to 16 {
  R += (A_n && FF)*b_n ;
  S += R>>8;
  R  = R && FF;
  S += (A_n >>  8 ) * b_n;
}

If  you need a parallel algorithm, you can just use the same in parallel form (A_n 12 bits numbers, b_n 8 bits numbers).
S is a 16 bit number.


S = SUM((A_n >>  8 ) * b_n) + SUM((A_n && FF)*b_n )>>8;


@3roomlab,  there is no overflow as the sum comprises only 16 (12 bits) numbers  that is <= 16 bits,
and in any case the total sum is less or equal to  16 bits.

 

[macboy]

Prove it in the simplest way possible to your challenged colleague:

You have 12 bit samples. The therefore can be up to 4095. Let's assume worst case scaling of 1/1, so all intermediate results may be up to 4095.

You sum 16 of these: 4095 * 16 is 65520. That is the absolute maximum result of all samples summed with worst case scaling.

A 16 bit integer goes up to 65535. Ask him if that is big enough or not!

EDIT:

The other way to scale would be to do the (variable 10~230) multiply portion in the individual FPGA, and the (fixed 256) divide portion in the master FPGA. This would then require a 20 bit bus, and a 24 bit accumulator, which after the divide by 256 (i.e. truncate lower 8 bits) becomes a 16 bit result. This way will significantly reduce rounding errors caused by scaling down individual samples, but since you want to limit the bus size, I assume that you won't be doing it this way.