Reply by rickman November 11, 20142014-11-11
On 11/11/2014 7:14 PM, robert bristow-johnson wrote:
> On 11/11/14 4:29 PM, rickman wrote: >> On 11/11/2014 3:29 PM, robert bristow-johnson wrote: >>> On 11/11/14 1:53 PM, rickman wrote: >>>> On 11/11/2014 12:00 PM, Tim Wescott wrote: >>>>> On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote: >>>>> >>>>>> On 11/10/2014 8:37 AM, sharanbr wrote: >>>>>>> Hello All, >>>>>>> >>>>>>> I am reading DFT topic where quantization effect is described. >>>>>>> >>>>>>> One of the example in the book calculates the number of bits >>>>>>> needed to >>>>>>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>>>>>> >>>>>>> Here b = 15 bits. My question is whether the size of the sample size >>>>>>> does not matter at all for computation of the DFT? >>>>>>> >>>>>>> If input is composed of 24 bits (for example), would number of bits >>>>>>> used for DFT internally would be independent of 24-bit size? >>>>>> >>>>>> I think you are saying you wish for the output spectrum to have 30 >>>>>> dB of >>>>>> SNR. To achieve that you need to consider the size of your FFT. My >>>>>> understanding is that you add about 1/2 bit of noise from roundoff >>>>>> error >>>>>> with each pass of the FFT. So a 1024 point FFT will have 10 passes >>>>>> and >>>>>> add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with >>>>>> input data with 10 bits of significant data or 60 dB of SNR. You >>>>>> would >>>>>> need to do all calculations with at least 10 bits of precision. >>>>> >>>>> I think you're doing your computation backwards. >>>>> >>>>> Each bin of an N-point FFT acts like a bandpass filter, N points >>>>> long. So >>>>> for white noise at the input, the achievable SNR at each bin is (input >>>>> SNR) >>>>> + 3dB * N. >>>>> >>>>> So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ >>>>> SNR. >>>> >>>> You are talking about the averaging of the input noise. I am talking >>>> about the cumulative effects of round off error in each stage of the >>>> computation. >>> >>> >>> yup, but the only way doing the DFT with the simple dot-product can make >>> it better than the FFT is when your accumulator is much wider than the >>> original words (usually twice as wide) and you round (or dither and >>> round or noise-shape and round or all three) *once* at the end of the >>> summation. then the naive DFT will do better than the FFT. but i don't >>> think so otherwise. >> >> Why did you start talking about the DFT???? >> > > uhm, because those letters live in the Subject: field of this thread?? i > thought i was being on-topic with the listed subject of the conversation.
Lol, yes, I see. I don't know how quickly the error grows with the DFT calculation. Why do you say the DFT produces less noise than the FFT? I have not seen an analysis of the DFT in that regard, but off the top of my head I would expect them to be about the same. The FFT noise is 1/2 log(n) bits from some paper I read many years ago. The DFT has more calculations total, but I believe each bin has about the same number of operations involved in producing it. It would depend on whether the DFT was done as a real or complex computation. -- Rick
Reply by robert bristow-johnson November 11, 20142014-11-11
On 11/11/14 4:29 PM, rickman wrote:
> On 11/11/2014 3:29 PM, robert bristow-johnson wrote: >> On 11/11/14 1:53 PM, rickman wrote: >>> On 11/11/2014 12:00 PM, Tim Wescott wrote: >>>> On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote: >>>> >>>>> On 11/10/2014 8:37 AM, sharanbr wrote: >>>>>> Hello All, >>>>>> >>>>>> I am reading DFT topic where quantization effect is described. >>>>>> >>>>>> One of the example in the book calculates the number of bits >>>>>> needed to >>>>>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>>>>> >>>>>> Here b = 15 bits. My question is whether the size of the sample size >>>>>> does not matter at all for computation of the DFT? >>>>>> >>>>>> If input is composed of 24 bits (for example), would number of bits >>>>>> used for DFT internally would be independent of 24-bit size? >>>>> >>>>> I think you are saying you wish for the output spectrum to have 30 >>>>> dB of >>>>> SNR. To achieve that you need to consider the size of your FFT. My >>>>> understanding is that you add about 1/2 bit of noise from roundoff >>>>> error >>>>> with each pass of the FFT. So a 1024 point FFT will have 10 passes and >>>>> add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with >>>>> input data with 10 bits of significant data or 60 dB of SNR. You would >>>>> need to do all calculations with at least 10 bits of precision. >>>> >>>> I think you're doing your computation backwards. >>>> >>>> Each bin of an N-point FFT acts like a bandpass filter, N points >>>> long. So >>>> for white noise at the input, the achievable SNR at each bin is (input >>>> SNR) >>>> + 3dB * N. >>>> >>>> So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ >>>> SNR. >>> >>> You are talking about the averaging of the input noise. I am talking >>> about the cumulative effects of round off error in each stage of the >>> computation. >> >> >> yup, but the only way doing the DFT with the simple dot-product can make >> it better than the FFT is when your accumulator is much wider than the >> original words (usually twice as wide) and you round (or dither and >> round or noise-shape and round or all three) *once* at the end of the >> summation. then the naive DFT will do better than the FFT. but i don't >> think so otherwise. > > Why did you start talking about the DFT???? >
uhm, because those letters live in the Subject: field of this thread?? i thought i was being on-topic with the listed subject of the conversation. :-\ -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by rickman November 11, 20142014-11-11
On 11/11/2014 3:29 PM, robert bristow-johnson wrote:
> On 11/11/14 1:53 PM, rickman wrote: >> On 11/11/2014 12:00 PM, Tim Wescott wrote: >>> On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote: >>> >>>> On 11/10/2014 8:37 AM, sharanbr wrote: >>>>> Hello All, >>>>> >>>>> I am reading DFT topic where quantization effect is described. >>>>> >>>>> One of the example in the book calculates the number of bits needed to >>>>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>>>> >>>>> Here b = 15 bits. My question is whether the size of the sample size >>>>> does not matter at all for computation of the DFT? >>>>> >>>>> If input is composed of 24 bits (for example), would number of bits >>>>> used for DFT internally would be independent of 24-bit size? >>>> >>>> I think you are saying you wish for the output spectrum to have 30 >>>> dB of >>>> SNR. To achieve that you need to consider the size of your FFT. My >>>> understanding is that you add about 1/2 bit of noise from roundoff >>>> error >>>> with each pass of the FFT. So a 1024 point FFT will have 10 passes and >>>> add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with >>>> input data with 10 bits of significant data or 60 dB of SNR. You would >>>> need to do all calculations with at least 10 bits of precision. >>> >>> I think you're doing your computation backwards. >>> >>> Each bin of an N-point FFT acts like a bandpass filter, N points >>> long. So >>> for white noise at the input, the achievable SNR at each bin is (input >>> SNR) >>> + 3dB * N. >>> >>> So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ >>> SNR. >> >> You are talking about the averaging of the input noise. I am talking >> about the cumulative effects of round off error in each stage of the >> computation. > > > yup, but the only way doing the DFT with the simple dot-product can make > it better than the FFT is when your accumulator is much wider than the > original words (usually twice as wide) and you round (or dither and > round or noise-shape and round or all three) *once* at the end of the > summation. then the naive DFT will do better than the FFT. but i don't > think so otherwise.
Why did you start talking about the DFT???? -- Rick
Reply by Tim Wescott November 11, 20142014-11-11
On Tue, 11 Nov 2014 13:53:31 -0500, rickman wrote:

<< snip >>

> BTW, I think your math should be 3 dB * log2(N), no?
Indeed yes! -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by robert bristow-johnson November 11, 20142014-11-11
On 11/11/14 1:53 PM, rickman wrote:
> On 11/11/2014 12:00 PM, Tim Wescott wrote: >> On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote: >> >>> On 11/10/2014 8:37 AM, sharanbr wrote: >>>> Hello All, >>>> >>>> I am reading DFT topic where quantization effect is described. >>>> >>>> One of the example in the book calculates the number of bits needed to >>>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>>> >>>> Here b = 15 bits. My question is whether the size of the sample size >>>> does not matter at all for computation of the DFT? >>>> >>>> If input is composed of 24 bits (for example), would number of bits >>>> used for DFT internally would be independent of 24-bit size? >>> >>> I think you are saying you wish for the output spectrum to have 30 dB of >>> SNR. To achieve that you need to consider the size of your FFT. My >>> understanding is that you add about 1/2 bit of noise from roundoff error >>> with each pass of the FFT. So a 1024 point FFT will have 10 passes and >>> add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with >>> input data with 10 bits of significant data or 60 dB of SNR. You would >>> need to do all calculations with at least 10 bits of precision. >> >> I think you're doing your computation backwards. >> >> Each bin of an N-point FFT acts like a bandpass filter, N points long. So >> for white noise at the input, the achievable SNR at each bin is (input >> SNR) >> + 3dB * N. >> >> So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ SNR. > > You are talking about the averaging of the input noise. I am talking > about the cumulative effects of round off error in each stage of the > computation.
yup, but the only way doing the DFT with the simple dot-product can make it better than the FFT is when your accumulator is much wider than the original words (usually twice as wide) and you round (or dither and round or noise-shape and round or all three) *once* at the end of the summation. then the naive DFT will do better than the FFT. but i don't think so otherwise. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by rickman November 11, 20142014-11-11
On 11/11/2014 12:00 PM, Tim Wescott wrote:
> On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote: > >> On 11/10/2014 8:37 AM, sharanbr wrote: >>> Hello All, >>> >>> I am reading DFT topic where quantization effect is described. >>> >>> One of the example in the book calculates the number of bits needed to >>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>> >>> Here b = 15 bits. My question is whether the size of the sample size >>> does not matter at all for computation of the DFT? >>> >>> If input is composed of 24 bits (for example), would number of bits >>> used for DFT internally would be independent of 24-bit size? >> >> I think you are saying you wish for the output spectrum to have 30 dB of >> SNR. To achieve that you need to consider the size of your FFT. My >> understanding is that you add about 1/2 bit of noise from roundoff error >> with each pass of the FFT. So a 1024 point FFT will have 10 passes and >> add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with >> input data with 10 bits of significant data or 60 dB of SNR. You would >> need to do all calculations with at least 10 bits of precision. > > I think you're doing your computation backwards. > > Each bin of an N-point FFT acts like a bandpass filter, N points long. So > for white noise at the input, the achievable SNR at each bin is (input SNR) > + 3dB * N. > > So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ SNR.
You are talking about the averaging of the input noise. I am talking about the cumulative effects of round off error in each stage of the computation. I did mistakenly confuse the input data resolution with the calculation precision. The point is that relative to the resolution of the register sizes used, there will be an average of 1/2 bit of noise added with each pass of the FFT. So by using larger registers the impact on SNR can be made arbitrarily small. The averaging effect you describe depends on specific properties of the noise on the input (as you say, white) and may or may not be as effective as described. For example if the noise on the input is tonal the filtering effect will be minimal for the bin where the tone falls. BTW, I think your math should be 3 dB * log2(N), no? -- Rick
Reply by Tim Wescott November 11, 20142014-11-11
On Tue, 11 Nov 2014 12:41:01 -0500, robert bristow-johnson wrote:

> On 11/11/14 12:08 PM, Tim Wescott wrote: >> On Mon, 10 Nov 2014 07:37:13 -0600, sharanbr wrote: >> >>> Hello All, >>> >>> I am reading DFT topic where quantization effect is described. >>> >>> One of the example in the book calculates the number of bits needed to >>> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >>> >>> Here b = 15 bits. My question is whether the size of the sample size >>> does not matter at all for computation of the DFT? >>> >>> If input is composed of 24 bits (for example), would number of bits >>> used for DFT internally would be independent of 24-bit size? >> >> It's complicated. >> >> If the input is composed of 24 bits, with a signal that uses the full >> range of available values, then the bottom 19 bits are, roughly, random >> junk. (It's more like the bottom 17 bits or so, if you add guard bits >> -- >> I'm being a bit fast and loose with my math). >> >> When you finish the FFT, then if the signal were a pure tone that fell >> exactly on a bin's frequency, the SNR of the signal in that one bin >> would be roughly 60dB, meaning that the bottom 14 (OK, 12) bits are >> junk. >> >> > it appears we're talking fixed-point DFT. then, to be sufficiently slow > and tight with the math, besides being clear on the 24-bit words of the > signal (and how many guard bits are on the left) and presumably 24-bit > words for the DFT coefficients (or "twiddle factors"), we need to be > clear what is the word width of the intermediate values. > > and we need to be clear if we're doing: > > N-1 > X[k] = SUM{ x[n] e^(j 2 pi nk/N) } > n=0 > > in which the signal is growing in amplitude and we'll need log2(N) guard > bits on the left, or if we're doing > > N-1 > X[k] = (1/N) SUM{ x[n] e^(j 2 pi nk/N) } > n=0 > > > in which the signal is actually decreasing in amplitude and bits are > falling off the edge on the right, or if we're doing > > N-1 > X[k] = (1/sqrt(N)) SUM{ x[n] e^(j 2 pi nk/N) } > n=0 > > and the signal amplitude is *not* growing or shrinking (in an r.m.s. > sense), but there is still the need for 1/2 log2(N) guard bits on the > left and another 1/2 log2(N) bits are gonna fall of the edge on the > right. > > if the vanilla-flavored radix-2 FFT is used, the first case there is no > division by 2 in the butterflies. in the second case, every butterfly > has a division by 2 (a right shift by one bit) so a bit falls offa the > edge for each pass. in the final case, for every *alternate* pass, > there is a division by 2 (and a right shift by one bit) and for the > other passes, there is no divide nor shift in the butterflies. > > this is something i worried about two decades ago when i was coding this > for the good-old DSP56K (before the DSP56002 and later, which had a > special overflow-anticipation bit that was used efficiently implement a > block-floating-point FFT).
You just HAD to go and make it complicateder. Yes to all that, but within a lot of reasonable assumptions I don't think it changes the conclusions -- it just affects the details in how you implement your FFT so that the assumptions you do make remain valid. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by robert bristow-johnson November 11, 20142014-11-11
On 11/11/14 12:08 PM, Tim Wescott wrote:
> On Mon, 10 Nov 2014 07:37:13 -0600, sharanbr wrote: > >> Hello All, >> >> I am reading DFT topic where quantization effect is described. >> >> One of the example in the book calculates the number of bits needed to >> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >> >> Here b = 15 bits. My question is whether the size of the sample size >> does not matter at all for computation of the DFT? >> >> If input is composed of 24 bits (for example), would number of bits used >> for DFT internally would be independent of 24-bit size? > > It's complicated. > > If the input is composed of 24 bits, with a signal that uses the full > range of available values, then the bottom 19 bits are, roughly, random > junk. (It's more like the bottom 17 bits or so, if you add guard bits -- > I'm being a bit fast and loose with my math). > > When you finish the FFT, then if the signal were a pure tone that fell > exactly on a bin's frequency, the SNR of the signal in that one bin would > be roughly 60dB, meaning that the bottom 14 (OK, 12) bits are junk. >
it appears we're talking fixed-point DFT. then, to be sufficiently slow and tight with the math, besides being clear on the 24-bit words of the signal (and how many guard bits are on the left) and presumably 24-bit words for the DFT coefficients (or "twiddle factors"), we need to be clear what is the word width of the intermediate values. and we need to be clear if we're doing: N-1 X[k] = SUM{ x[n] e^(j 2 pi nk/N) } n=0 in which the signal is growing in amplitude and we'll need log2(N) guard bits on the left, or if we're doing N-1 X[k] = (1/N) SUM{ x[n] e^(j 2 pi nk/N) } n=0 in which the signal is actually decreasing in amplitude and bits are falling off the edge on the right, or if we're doing N-1 X[k] = (1/sqrt(N)) SUM{ x[n] e^(j 2 pi nk/N) } n=0 and the signal amplitude is *not* growing or shrinking (in an r.m.s. sense), but there is still the need for 1/2 log2(N) guard bits on the left and another 1/2 log2(N) bits are gonna fall of the edge on the right. if the vanilla-flavored radix-2 FFT is used, the first case there is no division by 2 in the butterflies. in the second case, every butterfly has a division by 2 (a right shift by one bit) so a bit falls offa the edge for each pass. in the final case, for every *alternate* pass, there is a division by 2 (and a right shift by one bit) and for the other passes, there is no divide nor shift in the butterflies. this is something i worried about two decades ago when i was coding this for the good-old DSP56K (before the DSP56002 and later, which had a special overflow-anticipation bit that was used efficiently implement a block-floating-point FFT). -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by Tim Wescott November 11, 20142014-11-11
On Mon, 10 Nov 2014 07:37:13 -0600, sharanbr wrote:

> Hello All, > > I am reading DFT topic where quantization effect is described. > > One of the example in the book calculates the number of bits needed to > compute the DFT of a 1024 point sequence with a SNR of 30 dB. > > Here b = 15 bits. My question is whether the size of the sample size > does not matter at all for computation of the DFT? > > If input is composed of 24 bits (for example), would number of bits used > for DFT internally would be independent of 24-bit size?
It's complicated. If the input is composed of 24 bits, with a signal that uses the full range of available values, then the bottom 19 bits are, roughly, random junk. (It's more like the bottom 17 bits or so, if you add guard bits -- I'm being a bit fast and loose with my math). When you finish the FFT, then if the signal were a pure tone that fell exactly on a bin's frequency, the SNR of the signal in that one bin would be roughly 60dB, meaning that the bottom 14 (OK, 12) bits are junk. If by "sample size" you mean the number of samples in the FFT (i.e. 1024), then it matters, because the SNR of that hypothetical pure tone improves by 3dB for each doubling in the sample size. If by "sample size" you mean the number of bits in the sample, then (a) you are not using the correct nomenclature ("precision" or "word width" is the word you seek), and (b), if the signal is significantly noisier than the quantization noise imposed by the word width then increasing the word width will yield no effective increase in SNR. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by Tim Wescott November 11, 20142014-11-11
On Tue, 11 Nov 2014 02:23:43 -0500, rickman wrote:

> On 11/10/2014 8:37 AM, sharanbr wrote: >> Hello All, >> >> I am reading DFT topic where quantization effect is described. >> >> One of the example in the book calculates the number of bits needed to >> compute the DFT of a 1024 point sequence with a SNR of 30 dB. >> >> Here b = 15 bits. My question is whether the size of the sample size >> does not matter at all for computation of the DFT? >> >> If input is composed of 24 bits (for example), would number of bits >> used for DFT internally would be independent of 24-bit size? > > I think you are saying you wish for the output spectrum to have 30 dB of > SNR. To achieve that you need to consider the size of your FFT. My > understanding is that you add about 1/2 bit of noise from roundoff error > with each pass of the FFT. So a 1024 point FFT will have 10 passes and > add 5 bits. To get 30 dB out (ENOB = 5) you would need to start with > input data with 10 bits of significant data or 60 dB of SNR. You would > need to do all calculations with at least 10 bits of precision.
I think you're doing your computation backwards. Each bin of an N-point FFT acts like a bandpass filter, N points long. So for white noise at the input, the achievable SNR at each bin is (input SNR) + 3dB * N. So for a 30dB _input_ SNR you could expect (at best) a 60dB _output_ SNR. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com