DFT Developement (Brandon.Price) - Revision history

Brandon.price: /* Properties of the DFT */

2008-12-02T21:32:10Z

Properties of the DFT

← Older revision		Revision as of 14:32, 2 December 2008
Line 108:		Line 108:
	<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = \frac{1-e^{j 2\pi (l-m)}}{1-e^{\frac{j 2\pi }{N}(l-m)}}</math>		<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = \frac{1-e^{j 2\pi (l-m)}}{1-e^{\frac{j 2\pi }{N}(l-m)}}</math>

	Now, for <math>l \neq m</math> this sum will always be 0 (since <math>e^{j 2\pi x} = 1 </math> for integer values of x). ~~When~~ <math>l=m</math> we find the summation is: <math>\sum_{n=0}^{N-1} e^0 = N</math>.		Now, for <math>l \neq m</math> this sum will always be 0 (since <math>e^{j 2\pi x} = 1 </math> for integer values of x).

			For <math>l=m</math> we find the summation is: <math>\sum_{n=0}^{N-1} e^0 = N</math>.

	<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>		<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>

Brandon.price: /* Properties of the DFT */

2008-12-02T21:30:44Z

Properties of the DFT

← Older revision		Revision as of 14:30, 2 December 2008
Line 104:		Line 104:
	<math> \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n }{N}}= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} e^{\frac{j 2\pi l n }{N}} = \sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} </math>		<math> \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n }{N}}= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} e^{\frac{j 2\pi l n }{N}} = \sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} </math>

	Now, using rather sneaky summation techniques from calculus ([http://www.purplemath.com/modules/series7.htm Finite Geometric Summation Formula]) with <math>r=e^{\frac{j 2\pi }{N}(l-m)}</math>, we find		Now, using rather sneaky summation techniques from calculus ([http://www.purplemath.com/modules/series7.htm Finite Geometric Summation Formula]) with <math>r=e^{\frac{j 2\pi }{N}(l-m)}</math>, we find:

			<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = \frac{1-e^{j 2\pi (l-m)}}{1-e^{\frac{j 2\pi }{N}(l-m)}}</math>

			Now, for <math>l \neq m</math> this sum will always be 0 (since <math>e^{j 2\pi x} = 1 </math> for integer values of x). When <math>l=m</math> we find the summation is: <math>\sum_{n=0}^{N-1} e^0 = N</math>.

	<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>		<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>

Brandon.price: /* Properties of the DFT */

2008-12-02T21:15:12Z

Properties of the DFT

← Older revision		Revision as of 14:15, 2 December 2008
Line 104:		Line 104:
	<math> \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n }{N}}= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} e^{\frac{j 2\pi l n }{N}} = \sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} </math>		<math> \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n }{N}}= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} e^{\frac{j 2\pi l n }{N}} = \sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} </math>

	Now, using rather sneaky summation techniques from calculus (~~see webpage~~), we find		Now, using rather sneaky summation techniques from calculus ([http://www.purplemath.com/modules/series7.htm Finite Geometric Summation Formula]) with <math>r=e^{\frac{j 2\pi }{N}(l-m)}</math>, we find

	<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>		<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>
Line 110:		Line 110:
	Applying this to our earlier equation, we have:		Applying this to our earlier equation, we have:

	<math>\sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = \sum_{m=0}^{N-1} x(m) N \delta_{m,l} = N x(l)</math>		<math>\sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n }{N}(l-m)} = \sum_{m=0}^{N-1} x(m) N \delta_{m,l} = N x(l)</math>

	Thus, since l is a dummy index just like n was, we find:		Thus, since l is a dummy index just like n was, we find:

Brandon.price: /* Properties of the DFT */

2008-12-02T21:03:31Z

Properties of the DFT

← Older revision		Revision as of 14:03, 2 December 2008
Line 54:		Line 54:

	Let us reflect on the DFT above...		Let us reflect on the DFT above...


	'''Periodicity'''		'''Periodicity'''
Line 64:		Line 65:

	<math> x(nT)=x[(n+N)T]</math>		<math> x(nT)=x[(n+N)T]</math>


			'''Negative Frequencies'''

			Since we work with positive indices, how can we determine the negative frequency components?

			We must note that <math> X(m) </math> for <math> m > \frac{N}{2} </math> corresponds to <math> X(m-N) </math>

			In words, the last half of our sequence should really be shifted back one entire period (our disguised negative frequency components).


Line 105:		Line 115:

	<math>IDFT(X(m))=\frac{1}{N} \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n}{N}} = x(l) </math>		<math>IDFT(X(m))=\frac{1}{N} \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n}{N}} = x(l) </math>

Brandon.price: /* Properties of the DFT */

2008-12-02T20:58:46Z

Properties of the DFT

← Older revision		Revision as of 13:58, 2 December 2008
Line 57:		Line 57:
	'''Periodicity'''		'''Periodicity'''

	We notice that X(m) is periodic with period N since:		We notice that the frequency sequence X(m) is periodic with period N since:

	<math>X(m+N)= \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n (m+N) / N} = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} e^{- j 2\pi n } = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} = X(m)</math>		<math>X(m+N)= \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n (m+N) / N} = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} e^{- j 2\pi n } = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} = X(m)</math>

			Similarly, the time sequence x(nT) is periodic with period NT:

			<math> x(nT)=x[(n+N)T]</math>

Brandon.price: /* Properties of the DFT */

2008-12-02T20:54:49Z

Properties of the DFT

← Older revision		Revision as of 13:54, 2 December 2008
Line 75:		Line 75:

	<math>DFT(x(nT)) = \sum_{n=0}^{N-1} x(nT)\ e^{\frac{- j 2\pi n m }{N}} = \frac{1}{T} \sum_{n=-N/2}^{N/2-1} x(nT)\ e^{- j 2\pi n T (\frac{m}{N T})}T \approx \frac{1}{T}\int_{-NT/2}^{NT/2} x(t)\ e^{- j 2\pi t f}\,dt</math>		<math>DFT(x(nT)) = \sum_{n=0}^{N-1} x(nT)\ e^{\frac{- j 2\pi n m }{N}} = \frac{1}{T} \sum_{n=-N/2}^{N/2-1} x(nT)\ e^{- j 2\pi n T (\frac{m}{N T})}T \approx \frac{1}{T}\int_{-NT/2}^{NT/2} x(t)\ e^{- j 2\pi t f}\,dt</math>


	The only real differences are limits on the integral and the 1/T scaling factor. So, the DFT may not be such a bad approximation after all!		The only real differences are limits on the integral and the 1/T scaling factor. So, the DFT may not be such a bad approximation after all!


			'''Inverse DFT (IDFT)'''

			Suppose we know X(n) for integer values of n. Can we extract x(m)? By definition,

			<math> X(n) = \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} </math> for <math> n \in \{0,1,2,\dots,N-1\} </math>

			Now, we start manipulating X(m), and hopefully arrive back at x(n):

			<math> \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n }{N}}= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x(m) e^{\frac{- j 2\pi n m }{N}} e^{\frac{j 2\pi l n }{N}} = \sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} </math>

			Now, using rather sneaky summation techniques from calculus (see webpage), we find

			<math>\sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = N \delta_{m,l} </math>

			Applying this to our earlier equation, we have:

			<math>\sum_{m=0}^{N-1} x(m) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(l-m)} = \sum_{m=0}^{N-1} x(m) N \delta_{m,l} = N x(l)</math>

			Thus, since l is a dummy index just like n was, we find:

			<math>IDFT(X(m))=\frac{1}{N} \sum_{n=0}^{N-1} X(n) e^{\frac{j 2\pi l n}{N}} = x(l) </math>



			'''Multiplication'''

			We saw earlier (for the Fourier Integral) that multiplying functions in the frequency domain corresponded to convolving the functions in the time domain (and vice versa). What happens in the discrete world with the DFT?

			Let's take the IDFT of two frequency sequences:

			<math>IDFT(X(n)H(n))= \sum_{n=0}^{N-1} \frac{1}{N} X(n)H(n) e^{\frac{- j 2\pi k n }{N}}=\sum_{n=0}^{N-1} \frac{1}{N} \sum_{m=0}^{N-1}x(m) e^{\frac{- j 2\pi n m }{N}} \sum_{l=0}^{N-1} h(l) e^{\frac{- j 2\pi n l }{N}} e^{\frac{j 2\pi k n }{N}}</math>

			<math>=\frac{1}{N} \sum_{m=0}^{N-1} x(m) \sum_{l=0}^{N-1} h(l) \sum_{n=0}^{N-1} e^{\frac{j 2\pi n}{N}(k-l-m)} = \frac{1}{N} \sum_{m=0}^{N-1}x(m) \sum_{l=0}^{N-1} h(l) N \delta_{l,k-m} = \sum_{m=0}^{N-1}x(m) h(k-m) </math>

			This looks very similar to a convolution, and we call it a "Circular Convolution" since it only works when the sequences are periodic.

Brandon.price: /* Properties of the DFT */

2008-12-02T09:07:05Z

Properties of the DFT

← Older revision		Revision as of 02:07, 2 December 2008
Line 64:		Line 64:
	'''Fourier Integral Resemblance'''		'''Fourier Integral Resemblance'''

	We ~~also~~ notice that with the following approximations, we can see a resemblance between the DFT and the Fourier Integral:		We notice that with the following approximations, we can see a resemblance between the DFT and the Fourier Integral:

	<math>f \approx \frac{m}{NT}</math>		<math>f \approx \frac{m}{NT}</math>

Brandon.price: /* Properties of the DFT */

2008-12-02T09:06:48Z

Properties of the DFT

← Older revision		Revision as of 02:06, 2 December 2008
Line 56:		Line 56:

	'''Periodicity'''		'''Periodicity'''

	We notice that X(m) is periodic with period N since:		We notice that X(m) is periodic with period N since:

Brandon.price: /* Properties of the DFT */

2008-12-02T09:06:39Z

Properties of the DFT

← Older revision		Revision as of 02:06, 2 December 2008
Line 55:		Line 55:
	Let us reflect on the DFT above...		Let us reflect on the DFT above...

			'''Periodicity'''
	We notice that X(m) is periodic with period N since:		We notice that X(m) is periodic with period N since:

	<math>X(m+N)= \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n (m+N) / N} = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} e^{- j 2\pi n } = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} = X(m)</math>		<math>X(m+N)= \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n (m+N) / N} = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} e^{- j 2\pi n } = \sum_{n=0}^{N-1} x(nT)\ e^{- j 2\pi n m / N} = X(m)</math>


			'''Fourier Integral Resemblance'''

	We also notice that with the following approximations, we can see a resemblance between the DFT and the Fourier Integral:		We also notice that with the following approximations, we can see a resemblance between the DFT and the Fourier Integral:

Brandon.price: /* Extracting the DFT */

2008-12-02T09:04:53Z

Extracting the DFT

← Older revision		Revision as of 02:04, 2 December 2008
Line 40:		Line 40:


	3) We want to work with discrete frequency data too, in the computer, so we multiply the frequency domain by a sequence of impulse functions. The corresponding convolution in time makes our discrete sample periodic.		3) We want to work with discrete frequency data too, in the computer, so we multiply in the frequency domain by a sequence of impulse functions. The corresponding convolution in time makes our discrete sample periodic.

	[[Image:DFTDev3(brandon.price).jpg\|600px]]		[[Image:DFTDev3(brandon.price).jpg\|600px]]