Convert to higher sample rate

Randy Yates <yates@digitalsignallabs.com> wrote:

(snip, I wrote, regarding large FFTs)

>> log2(77*60*44100) is about 28. Worst case is one additional bit
>> per stage, so 53 bit floating point should be plenty.
 
> I don't think that addresses the cos(2*pi/268435456) issue. The
> "quantization bits per stage" is another issue.
> 
> The cos(2*pi/268435456) (and corresponding sin()) issue may cause
> problems when there is cancellation
 
>  http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems
 
> but it would be data-dependent. For example, the input 
 
>  [-1 +1 -1 +1 .... -1 +1] 
 
> would aggravate the cancellation issue since 
 
>  cos[n * (2 * pi / 268435456)]
 
> and 
 
>  cos[(n + 1) * (2 * pi / 268435456)]
 
> are going to be very close.
 
> Don't you think?

There are some things you should be careful with. 

As I wrote before, I believe that the FFT rounding is better than
the DCT rounding. For small n, cos(n*2*pi/(large number)) will 
round to 1, which I don't believe is a problem.

One that I am not sure about, though, is that there won't be any
small rounding effects in the result. If you take 16 bit input,
convert to floating point, FFT then iFFT, it is possible that
some samples will be slightly larger than before. If one sample
was at 32767, it might come out 32768, which is bad in 16 bits.

And as we well know, if you do filter, some samples can come
out significantly larger. 

As for the cos() case, yes some will cancel, but the interesting
part is in the sin() terms in that case. 

When you get to the point where sin(2*pi/(large number)) is less
than epsilon, then you do have to be careful. We are not so close
to that with IEEE double.

-- glen

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:

> Randy Yates <yates@digitalsignallabs.com> wrote:
>
> (snip, I wrote, regarding large FFTs)
>
>>> log2(77*60*44100) is about 28. Worst case is one additional bit
>>> per stage, so 53 bit floating point should be plenty.
>  
>> I don't think that addresses the cos(2*pi/268435456) issue. The
>> "quantization bits per stage" is another issue.
>> 
>> The cos(2*pi/268435456) (and corresponding sin()) issue may cause
>> problems when there is cancellation
>  
>>  http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems
>  
>> but it would be data-dependent. For example, the input 
>  
>>  [-1 +1 -1 +1 .... -1 +1] 
>  
>> would aggravate the cancellation issue since 
>  
>>  cos[n * (2 * pi / 268435456)]
>  
>> and 
>  
>>  cos[(n + 1) * (2 * pi / 268435456)]
>  
>> are going to be very close.
>  
>> Don't you think?
>
> There are some things you should be careful with. 
>
> As I wrote before, I believe that the FFT rounding is better than
> the DCT rounding. For small n, cos(n*2*pi/(large number)) will 
> round to 1, which I don't believe is a problem.
>
> One that I am not sure about, though, is that there won't be any
> small rounding effects in the result. If you take 16 bit input,
> convert to floating point, FFT then iFFT, it is possible that
> some samples will be slightly larger than before. If one sample
> was at 32767, it might come out 32768, which is bad in 16 bits.
>
> And as we well know, if you do filter, some samples can come
> out significantly larger. 
>
> As for the cos() case, yes some will cancel, but the interesting
> part is in the sin() terms in that case. 
>
> When you get to the point where sin(2*pi/(large number)) is less
> than epsilon, then you do have to be careful. We are not so close
> to that with IEEE double.

Seem's like you'd be in trouble at some point when sin(blah) is 
anywhere near epsilon.

sin(blah)is about 4E-10 on my calc. Isn't epsilon around 1E-15 for
doubles?
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

>> If you decide to fft an entire song as is proposed by some, and then
apply a
filter with a very steep rolloff, the length of the impulse response could
be,
literally, minutes long. This would obviously be a disaster. 

well, it's a natural consequence from using filter with a transition
bandwidth of 1/length (which is absurdly narrow). Whatever implementation I
use, the closer it gets to ideal, the more pronounced the ringing will be.

Solution, don't try to implement an ideal filter. Simply taper the
frequency response magnitude and the ringing disappears. For example,
general raised cosine with non-zero alpha.

In reality, there is no problem as long as it is guaranteed that the input
signal contains no energy near the cutoff frequency. Which holds for
digitized audio data that's meant to be played through a non-ideal
reconstruction filter.	 

_____________________________		
Posted through www.DSPRelated.com

How can you prevent the input from having energy near the cutoff? If you can gaurantee this then you wouldn't need the filter. I think the aliasing problem is worse in an fft filterbank because the alias components can be reflected to low frequencies so they are not masked. 

That being said, if you obey the rules then aliasing should disappear, but a casual approach to drawing a response curve will not work. This assumes that you are using an STFT filterbank with a certain overlap. If you swallow an entire song with one giant fft then probably things are better from an aliasing point of view. 
I forsee a day when all bands will write songs that are 2^n samples long.

On 4/16/14 4:50 AM, radams2000@gmail.com wrote:
> How can you prevent the input from having energy near the cutoff? If you can gaurantee this then you wouldn't need the filter. I think the aliasing problem is worse in an fft filterbank because the alias components can be reflected to low frequencies so they are not masked.
>
> That being said, if you obey the rules then aliasing should disappear, but a casual approach to drawing a response curve will not work. This assumes that you are using an STFT filterbank with a certain overlap. If you swallow an entire song with one giant fft then probably things are better from an aliasing point of view.
> I forsee a day when all bands will write songs that are 2^n samples long.

:-)

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

radams2000@gmail.com writes:
> [...]
> I forsee a day when all bands will write songs that are 2^n samples long.

And they will all have a time signature of 2^l / 2^m...
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

robert bristow-johnson <rbj@audioimagination.com> writes:
> [...]
> the real problem is with the cosine of teeny values.  because then
> it's only in the *difference* between cos(theta) and 1 that tells you
> anything about what theta is.  and that hidden 1 bit you get in floats
> doesn't save your ass as it does with sin(theta).  

Why doesn't it? The "hidden 1" bit is about normalization, right? It
allows you to use one more bit for the mantissa than you otherwise would
have, and that's useful for values whether they're close to one or not.
It allows one more significant digit, whether close to one or not, does
it not?

> at least sin(theta) is well represented in floats, even for
> super-small theta. but not cos().

Well that's just a restatement of what you're contending. 

> and with cos(theta), that difference from 1 approaches (1/2 theta^2),

Where did you get (1/2 theta^2) from?

> so your significant bits really fall off the edge fast with
> cos(theta).
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

On 4/17/14 12:38 AM, Randy Yates wrote:
> robert bristow-johnson<rbj@audioimagination.com>  writes:
>> [...]
>> the real problem is with the cosine of teeny values.  because then
>> it's only in the *difference* between cos(theta) and 1 that tells you
>> anything about what theta is.  and that hidden 1 bit you get in floats
>> doesn't save your ass as it does with sin(theta).
>
> Why doesn't it? The "hidden 1" bit is about normalization, right? It
> allows you to use one more bit for the mantissa than you otherwise would
> have,

no, all of those bits are set to 1.  only the MSB which is 1 gets to be 
hidden.

Randy, this is the well-known "cosine problem" that affects both 
coefficient calculation of IIRs at very, very low resonant frequency. 
it also is a problem in displaying frequency response (magnitude) of a 
filter for very low frequencies.  this is a real problem for folks doing 
it in single-precision float.

> and that's useful for values whether they're close to one or not.
> It allows one more significant digit, whether close to one or not, does
> it not?
>
>> at least sin(theta) is well represented in floats, even for
>> super-small theta. but not cos().
>
> Well that's just a restatement of what you're contending.

no, i'm saying it's different with cosine.  with sin(theta) you still 
have all of your significant bits.

>> and with cos(theta), that difference from 1 approaches (1/2 theta^2),
>
> Where did you get (1/2 theta^2) from?

second term of the taylor series for cosine.  (first term is 1.)


here's an identity:

    cos(omega)  =  1 - 2*( sin(omega/2) )^2

now, no matter what theta is, all of the information is in the latter 
term on the right.  when theta gets very tiny, then the latter term is 
tiny compared to the first term and most of the significant bits of the 
latter term have to fall off the edge when it gets shifted right and 
added to 1.

the solution to this cosine problem is to replace cos(omega) with the 
identity above and rework/simplify your equations and collect all of 
those "1s" (along with the coefficients that multiply them) together.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On 4/16/14 12:37 AM, mnentwig wrote:
>>> If you decide to fft an entire song as is proposed by some, and then
> apply a
> filter with a very steep rolloff, the length of the impulse response could
> be,
> literally, minutes long. This would obviously be a disaster.
>
> well, it's a natural consequence from using filter with a transition
> bandwidth of 1/length (which is absurdly narrow). Whatever implementation I
> use, the closer it gets to ideal, the more pronounced the ringing will be.
>
> Solution, don't try to implement an ideal filter. Simply taper the
> frequency response magnitude and the ringing disappears. For example,
> general raised cosine with non-zero alpha.

dunno what "alpha" is.  an exponent?

anyway, to sorta clarify what Bob says:

On 4/16/14 4:50 AM, radams2000@gmail.com wrote:
>  ... a casual approach to drawing a response curve will not work.


> In reality, there is no problem as long as it is guaranteed that the input
> signal contains no energy near the cutoff frequency.

no, there's more to worry about.  the FFT is the DFT (just done 
efficiently) and the DFT is inherently periodic and that means to 
prevent time aliasing, the spectrum that you multiply by has to be the 
DFT of an impulse response that is as short as the zero-padding done to 
your long soundfile. *that* is the primary restriction you have to worry 
about when you "simply taper the frequency response magnitude".


so draw the frequency response you want at a much lower resolution (so 
the DFT is operating on a much shorter array of data), inverse DFT, take 
that response (with the right half swapped to the left because it 
represents "negative" time) and zero-pad it to the entire big DFT 
length.  then DFT it.  *that* is the frequency response you get.  now 
just make sure your big DFT is as long as your soundfile plus the little 
DFT length.

then whack away with all the MIPS you have at your disposal.  you're golden.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson <rbj@audioimagination.com> writes:

> On 4/17/14 12:38 AM, Randy Yates wrote:
>> robert bristow-johnson<rbj@audioimagination.com>  writes:
>>> [...]
>>> the real problem is with the cosine of teeny values.  because then
>>> it's only in the *difference* between cos(theta) and 1 that tells you
>>> anything about what theta is.  and that hidden 1 bit you get in floats
>>> doesn't save your ass as it does with sin(theta).
>>
>> Why doesn't it? The "hidden 1" bit is about normalization, right? It
>> allows you to use one more bit for the mantissa than you otherwise would
>> have,
>
> no, 

Yes. See the table under the "Internal Representation" section here:

  http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems

The point I was making is exactly why the "Bits Precision" column is one
greater than the "Significand" column for Single and Double in that
table.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com