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
number of bits to compute DFT
Started by ●November 10, 2014
Reply by ●November 11, 20142014-11-11
Reply by ●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 ●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 ●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 ●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 ●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
