Re: [music-dsp] Precision issues when mixing a large number of signals
On Mon, Dec 10, 2012 at 01:39:48PM +1100, Ross Bencina wrote: avoid any loss of precision due to truncation... etc. There is also arbitrary precision arithmetic if you don't want to throw any bits away. This seemed most pertainent to Alessandro's requirement that N was unknown and might become very large. Although I cannot imagine the exact application for a varying and unbounded number of signal sources where you also need to potentially know the sum divided by N at _any_ step to a perfect accuracy, then variable length fixed point seems the way to go. If you can afford the space of adding a bit on every step of the accumulation then accumulate and shift right without truncation will keep arbitrary precision and magnitude. At some point however I guess you need to turn that into a more modest representation for some real hardware, and you defer some cost till that time. -- 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
Re: [music-dsp] Precision issues when mixing a large number of signals
I don't think you have been clear about what you are trying to achieve. Are you trying to compute the sum of many signals for each time point? Or are you trying to compute the running sum of a single signal over many time points? Hello, thanks for helping. I want to sum prerecorded signals progressively. Each time a new recording is added to the system, this signal is added to the running mix and then discarded so the original source gets lost. At each instant it should be possible to retrieve the mix run till that moment. What are the signals? are they of nominally equal amplitude? normalized (-1,1) Your original formula looks like you are looking for a recursive solution to a normalized running sum of a single signal over many time points. nope. I meant summing many signals, without knowing all of them beforehand, and needing to know all the intermediate results 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. It doesn't really matter whether the sum is accross samples of a signal signal or accross signals, you can always use error compensation when computing the sum. It's just a way of increasing the precision of an accumulator. I have watched again the wikipedia entry, yeah that makes totally sense now, yesterday night it was really late! 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. Using floating point is a non-linear operation. Your simple approach also has quite some nonlinearity (accumulated error due to recursive division and re-rounding at each step). I see. cheers alessandro Ross -- 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 -- 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
Re: [music-dsp] Precision issues when mixing a large number of signals
On 12/10/12 11:18 AM, Bjorn Roche wrote:
On Dec 10, 2012, at 4:41 AM, Alessandro Saccoia wrote:
I don't think you have been clear about what you are trying to achieve.
Are you trying to compute the sum of many signals for each time point? Or are
you trying to compute the running sum of a single signal over many time points?
Hello, thanks for helping. I want to sum prerecorded signals progressively.
Each time a new recording is added to the system, this signal is added to the
running mix and then discarded so the original source gets lost.
At each instant it should be possible to retrieve the mix run till that moment.
I see. I think you'll want to go with my first suggestion:
1
Y = * ( X+ X+ . X )
N 12 N
But only do the division when you retrieve. In other words, store NY:
NY = ( X+ X+ . X )
12 N
just a quick note, Bjorn. consider viewing your ASCII math with a
fixed-width font. we cannot all guess at what proportional-width font
you might have been using, but if everyone uses a fixed-width font (for
ASCII math or ASCII art), characters line up and you can read the
symbols. i use a combination of TeX-like constructs (like X_0, X_1, or
y^2, etc) and positioning (like i don't like to use the LaTeX construct
for a summation or integral for ASCII math). also i use uppercase for
either transformed (freq domain) signals or important constants (like
N). so i might express your first equation like:
N
y = 1/N SUM{ x_i }
i=0
or
N
y[n] = 1/N SUM{ x_i[n] }
i=0
--
r b-j r...@audioimagination.com
Imagination is more important than knowledge.
--
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
Re: [music-dsp] Precision issues when mixing a large number of signals
I dream of a time when TeX notation will be acceptable and universal
in contexts like this.
y=(1/N) \sum_{i=0}^N x_i
doesn't stay ugly for very long, and is ultimately easier to read.
And you can paste it into here:
http://www.codecogs.com/latex/eqneditor.php and then it's actually
even MORE readable than anything rendered in ASCII... and it's
completely precise.
Dave.
On Mon, Dec 10, 2012 at 5:35 PM, robert bristow-johnson
r...@audioimagination.com wrote:
On 12/10/12 11:18 AM, Bjorn Roche wrote:
On Dec 10, 2012, at 4:41 AM, Alessandro Saccoia wrote:
I don't think you have been clear about what you are trying to achieve.
Are you trying to compute the sum of many signals for each time point?
Or are you trying to compute the running sum of a single signal over many
time points?
Hello, thanks for helping. I want to sum prerecorded signals
progressively. Each time a new recording is added to the system, this signal
is added to the running mix and then discarded so the original source gets
lost.
At each instant it should be possible to retrieve the mix run till that
moment.
I see. I think you'll want to go with my first suggestion:
1
Y = * ( X+ X+ . X )
N 12 N
But only do the division when you retrieve. In other words, store NY:
NY = ( X+ X+ . X )
12 N
just a quick note, Bjorn. consider viewing your ASCII math with a
fixed-width font. we cannot all guess at what proportional-width font you
might have been using, but if everyone uses a fixed-width font (for ASCII
math or ASCII art), characters line up and you can read the symbols. i use
a combination of TeX-like constructs (like X_0, X_1, or y^2, etc) and
positioning (like i don't like to use the LaTeX construct for a summation or
integral for ASCII math). also i use uppercase for either transformed (freq
domain) signals or important constants (like N). so i might express your
first equation like:
N
y = 1/N SUM{ x_i }
i=0
or
N
y[n] = 1/N SUM{ x_i[n] }
i=0
--
r b-j r...@audioimagination.com
Imagination is more important than knowledge.
--
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
--
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
Re: [music-dsp] Precision issues when mixing a large number of signals
On Dec 10, 2012, at 12:35 PM, robert bristow-johnson wrote:
On 12/10/12 11:18 AM, Bjorn Roche wrote:
On Dec 10, 2012, at 4:41 AM, Alessandro Saccoia wrote:
I don't think you have been clear about what you are trying to achieve.
Are you trying to compute the sum of many signals for each time point? Or
are you trying to compute the running sum of a single signal over many
time points?
Hello, thanks for helping. I want to sum prerecorded signals progressively.
Each time a new recording is added to the system, this signal is added to
the running mix and then discarded so the original source gets lost.
At each instant it should be possible to retrieve the mix run till that
moment.
I see. I think you'll want to go with my first suggestion:
1
Y = * ( X+ X+ . X )
N 12 N
But only do the division when you retrieve. In other words, store NY:
NY = ( X+ X+ . X )
12 N
just a quick note, Bjorn. consider viewing your ASCII math with a
fixed-width font. we cannot all guess at what proportional-width font you
might have been using, but if everyone uses a fixed-width font (for ASCII
math or ASCII art), characters line up and you can read the symbols.
Oops.
i use a combination of TeX-like constructs (like X_0, X_1, or y^2, etc) and
positioning (like i don't like to use the LaTeX construct for a summation or
integral for ASCII math). also i use uppercase for either transformed (freq
domain) signals or important constants (like N). so i might express your
first equation like:
N
y = 1/N SUM{ x_i }
i=0
or
N
y[n] = 1/N SUM{ x_i[n] }
i=0
Sure, that's clearly better, but I was following the conventions of the OP.
bjorn
-
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
Re: [music-dsp] Precision issues when mixing a large number of signals
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. 1N - 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. When you do know N in advance, it would be better to: 1 Y = * ( X+ X+ . X ) N 12 N or 1 1 1 Y = * X+ --- X+ . + --- X N 1 N2 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. 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
Re: [music-dsp] Precision issues when mixing a large number of signals
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. 1N - 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 12 N or 1 1 1 Y = * X+ --- X+ . + --- X N 1 N2 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 -- 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
Re: [music-dsp] Precision issues when mixing a large number of signals
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. 1N - 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 12 N or 1 1 1 Y = * X+ --- X+ . + --- X N 1 N2 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 -- 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 -- 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
Re: [music-dsp] Precision issues when mixing a large number of signals
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. 1N - 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 12 N or 1 1 1 Y = * X+ --- X+ . + --- X N 1 N2 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 -- 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 -- dupswapdrop -- the music-dsp mailing list and website: subscription info, FAQ, source code archive, list archive, book
Re: [music-dsp] Precision issues when mixing a large number of signals
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 Smithrainwarr...@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. 1N - 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 ) N1 2N or 1 1 1 Y = * X+ --- X+ . + --- X N 1 N2 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
Re: [music-dsp] Precision issues when mixing a large number of signals
Hi Alessandro, A lot has been written about this. Google precision of summing floating point values and read the .pdfs on the first page for some analysis. Follow the citations for more. Somewhere there is a paper that analyses the performance of different methods and suggests the optimal approach. I think it is signal dependent. On 10/12/2012 11:32 AM, Alessandro Saccoia wrote: 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. Dividing by N only when you need to compute the sum sounds like a good good idea, that way you won't be hashing the precision of each value prior to summing it. To avoid throwing out any information you could use high-precision arithemetic. Did you say whether the signals are originally integers or floating point? If they're integers, can you keep the sum in a 64 bit int? Otherwise maybe a double. You can easily compute when you will start to loose precision in floating point based on the range of the input and the number of elements in the sum (summing 2 values requires 1 extra bit of headroom, 4 values requires 2 bits, 8 values 3 bits etc). So for 1024 32 bit values you'll need 10 more bits to avoid any loss of precision due to truncation... etc. There is also arbitrary precision arithmetic if you don't want to throw any bits away. There is something called double double which is a software 128 bit floating point type that maybe isn't too expensive. One problem with floating point is that adding a large value and a small value will truncate the small value (first it needs to be shifted so it has the same exponent as the large value). You didn't say much about your values, but assuming that you're adding values distributed around a non-zero mean, the accumulator will increase in value as you add more values. Thus later summands will be truncated more than earlier ones. One way to minimise this is to maintain multiple accumulators and only sum a certain number of values into each one (or sum into successive accumulators kind of like a ring buffer of accumulators). Then sum the accumulators together at the end. this reduces truncation effects since each accumulator has a limited range (hence higher precision of summation) and when you sum the final accumulators together (hopefully) they will all have a similar range). A variation on this, if you know your signals have different magnitudes (eg you are summing both X and X^2), is to use separate accumulators for each magnitude class - since these are obviously going to have vastly different domains. You also need to consider what form the final output will take. If the output is low precision then the best you can hope for is that each input makes an equal contribution to the output -- you need enough precision in your accumulator to ensure this. For some uses you could consider dithering the output to improve the output. Ross. -- 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
Re: [music-dsp] Precision issues when mixing a large number of signals
On Dec 9, 2012, at 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.. Brad's suggestions are good, but it makes me wonder: if you have so many inputs that the numerical error of a naive approach starts to matter, what's the result? Are you really going to hear something after adding that many signals together? If they are independent of each other, then the result of so many signals will be noise. Otherwise, the signals must have something (significant) in common, or most of them must be zero most of the time. In the latter case, these algorithms won't make much difference (although I would still not recommend your original proposal). I am a bit confused on another point: How are you getting your data: one sample at a time (one from each incoming channel) or one entire signal at a time? Or something else? If you have the whole signal stored in memory (or hard disk) you have the luxury of solving this however you like. If the data is coming in in real-time, then you know how many signals there are at any given time. If you want to add another signal to an existing sum, then just divide when you take the output. On Dec 9, 2012, at 9:28 PM, robert bristow-johnson wrote: 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? In modern C/C++, if you need a type guaranteed to hold 64 bits, include types.h (I believe) and use int64_t. On Dec 9, 2012, at 9:39 PM, Ross Bencina wrote: There is something called double double which is a software 128 bit floating point type that maybe isn't too expensive. long double, I believe - 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
Re: [music-dsp] Precision issues when mixing a large number of signals
On 10/12/2012 1:47 PM, Bjorn Roche wrote: There is something called double double which is a software 128 bit floating point type that maybe isn't too expensive. long double, I believe No. long double afaik usually means extended precision, as supported in hardware by the x86 FPU, and is 80 bits wide. It is not supported by some compilers at all (eg MSVC) since they tend to target SSE rather than x86 FPU. double double is something else: http://en.wikipedia.org/wiki/Double-double_arithmetic#Double-double_arithmetic Ross. -- 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
