um, a sorta dumb question is, if you know that all signals are mixed
with equal weight, then why not just sum the fixed-point values into a
big long word? if you're doing this in C or C++, the type "long long"
is, i believe, 64 bits. i cannot believe that your sum needs any more
than that. is N greater than 2^32? are your original samples more than
32 bits?
of course, if the N inputs being mixed are not coherent (which is what
they will be if they come from independent sources), then the power or
energy of each signal adds. if the sources are roughly equal in power,
the power of the result grows as the sqrt(N), not N.
to be totally confident that no overflow goes unseen, the bit width
grows 1 bit for every time N doubles. but if the signals are
uncorrelated, it's likely (not guaranteed) that the bit width grows 1
bit when N is quadrupled. you might be able to do this with a single
long word accumulator, depending on what your input is and the maximum
value N can ever be.
it's not a sophisticated problem and i doubt that any algorithm that
gets named after anybody is what you will need to solve it optimally.
--
r b-j r...@audioimagination.com
"Imagination is more important than knowledge."
On 12/9/12 8:18 PM, Alessandro Saccoia wrote:
That is really interesting, but I can't see how to apply the Kahan's algorithm
to a set of signals.
In my original question, I was thinkin of mixing signals of arbitrary sizes.
I could relax this requirement, and forcing all the signals to be of a given
size, but I can't see how a sample by sample summation, where there are M sums
(M the forced length of the signals) could profit from a running compensation.
Also, with a non linear operation, I fear of introducing discontinuities that
could sound even worse than the white noise I expect using the simple approach..
On Dec 10, 2012, at 1:43 AM, Brad Smith<rainwarr...@gmail.com> wrote:
I would consider storing N and your sum separately, doing the division
only to read the output (don't destroy your original sum in the
process). I guess this is the first thing that Bjorn suggested, but
maybe stated a little differently.
There's a technique called Kahan's Algorithm that tries to compensate
for the running errors accumulated during summation. It can help
increase the precision a bit:
http://en.wikipedia.org/wiki/Kahan_summation_algorithm
Also, there's the simple technique of recursively dividing the sums
into pairs, which will prevent later results from having greater error
than earlier ones, though you'd probably need to know N in advance for
this to be practical: http://en.wikipedia.org/wiki/Pairwise_summation
-- Brad Smith
On Sun, Dec 9, 2012 at 7:32 PM, Alessandro Saccoia
<alessandro.sacc...@gmail.com> wrote:
Thanks Bjorn,
On Dec 9, 2012, at 2:33 PM, Alessandro Saccoia wrote:
Hi list,
given a large number of signals (N> 1000), I wonder what happens when adding
them with a running sum Y.
1 N - 1
Y = ----- * X + ( -------) * Y
N N
Yes, your intuition is correct: this is not a good way to go, although how bad
it is depends on your datatype. All I can say here is that this formula will
result in N roundoff errors for one of your signals, N-1 for another, and so on.
You might *need* to use this formula if you don't know N in advance, but after
processing the first sample, you will know N, (right?) so I don't see how that
can happen.
It's going to be a sort of comulative process that goes on in time, so I won't
necessarily know N in advance. If had a strong evidence that I should prefer
one method over the other, I could decide to keep all the temporary X1, X2,…
and recompute everything each time. Performance and storage are not a strong
concern in this case, but the quality of the final and intermediate results is.
When you do know N in advance, it would be better to:
1
Y = --- * ( X + X + ..... X )
N 1 2 N
or
1 1 1
Y = ---- * X + --- X + ..... + --- X
N 1 N 2 N N
Exactly which is better depends on your datatype (fixed vs floating point,
etc). If you are concerned about overflow, the latter is better. For
performance, the former is better. For precision, without thinking too
carefully about it I would think the former is better, but, obviously, not in
the presence of overflow.
I think I will use floating points, and maybe spend some time trying to figure out
what is the transfer function for N->+inf and seeing if something (thinking of
a sort of dithering) could help in keeping the rounding error limited to a certain
region of the spectrum to avoid white noise. I am not sure I will make it, but I
could definitely give it a try. cheers,
alessandro
bjorn
Given the limited precision, intuitively something bad will happen for a large
N.
Is there a better method than the trivial scale and sum to minimize the effects
of the loss of precision?
If I reduce the bandwidth of the inputs signals in advance, do I have any
chance of minimizing this (possible) artifacts?
Thank you
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp
-----------------------------
Bjorn Roche
http://www.xonami.com
Audio Collaboration
http://blog.bjornroche.com
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp
