Is there such thing as a shift-theorem* for filterbanks other than the discrete fourier transform? For example the discrete cosine transform, the cosine modulated filterbank, the discrete wavelet transform? * The shift theorem for the DFT states that if Y(m) is the m-th DFT coefficient of y(n) then DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) (This assumes that y(n) is periodic)
shift theorem
Started by ●March 26, 2005
Reply by ●March 26, 20052005-03-26
"porterboy" <porterboy76@yahoo.com> wrote in message news:c4b57fd0.0503260544.64cd3e9@posting.google.com...> Is there such thing as a shift-theorem* for filterbanks other than the > discrete fourier transform? For example the discrete cosine transform, > the cosine modulated filterbank, the discrete wavelet transform? > > * The shift theorem for the DFT states that if Y(m) is the m-th DFT > coefficient of y(n) then > > DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) > > (This assumes that y(n) is periodic)Hello Porterboy, A few transforms enjoy the duality of shifting <--> modulation. You already gave an example. The technical name is the Heaviside shifting theorem. I'm not quite sure what you are asking though. What do you mean by a shift theorem for filterbanks? Clay
Reply by ●March 26, 20052005-03-26
in article c4b57fd0.0503260544.64cd3e9@posting.google.com, porterboy at porterboy76@yahoo.com wrote on 03/26/2005 08:44:> Is there such thing as a shift-theorem* for filterbanks other than the > discrete fourier transform? For example the discrete cosine transform, > the cosine modulated filterbank, the discrete wavelet transform? > > * The shift theorem for the DFT states that if Y(m) is the m-th DFT > coefficient of y(n) then > > DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) > > (This assumes that y(n) is periodic)such an assumption should be implicit with DFT, although there are deniers. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 26, 20052005-03-26
robert bristow-johnson wrote:> > in article c4b57fd0.0503260544.64cd3e9@posting.google.com, porterboy at > porterboy76@yahoo.com wrote on 03/26/2005 08:44: > > > Is there such thing as a shift-theorem* for filterbanks other than the > > discrete fourier transform? For example the discrete cosine transform, > > the cosine modulated filterbank, the discrete wavelet transform? > > > > * The shift theorem for the DFT states that if Y(m) is the m-th DFT > > coefficient of y(n) then > > > > DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) > > > > (This assumes that y(n) is periodic) > > such an assumption should be implicit with DFT, although there are deniers.First of all, the assumption that y(n) is periodic was not needed in the firat place. Secondly, the above equation actually demonstrates why the DFT need not be periodic. Consider when k is a non-rational number. It is only *your* assumption that k is an integer that makes the DFT periodic. -jim ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Reply by ●March 26, 20052005-03-26
in article 42461c77$1_1@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on 03/26/2005 21:37:> > > robert bristow-johnson wrote: >> >> in article c4b57fd0.0503260544.64cd3e9@posting.google.com, porterboy at >> porterboy76@yahoo.com wrote on 03/26/2005 08:44: >> >>> Is there such thing as a shift-theorem* for filterbanks other than the >>> discrete fourier transform? For example the discrete cosine transform, >>> the cosine modulated filterbank, the discrete wavelet transform? >>> >>> * The shift theorem for the DFT states that if Y(m) is the m-th DFT >>> coefficient of y(n) then >>> >>> DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) >>> >>> (This assumes that y(n) is periodic) >> >> such an assumption should be implicit with DFT, although there are deniers. > > First of all, the assumption that y(n) is periodic was not needed in the > firat place. Secondly, the above equation actually demonstrates why the > DFT need not be periodic. Consider when k is a non-rational number. It > is only *your* assumption that k is an integer that makes the DFT > periodic.well, probably we need to ask the OP what he means by "y(n)". even though he used parenths instead of square brackets (as in y[n]) it seems to me to be outside the realm of reasonableness to assume that, when the question is in the context of DFT (or DCT), that the argument of "y(n)" is anything other than an integer. if any non-integer "n" is implied, we are talking about continuous-time (or continuous-something-else, say if it's image processing) and the DFT has no definition to that. now, getting specifically to what the OP said, but giving it a slightly different notation to eliminate ambiguity (need mono-spaced font): N-1 let Y[m] =def DFT{ y[n] } =def SUM{ y[n] * exp(-j*2*pi*n*m/N) } n=0 then if it is true that DFT{ y[n-k] } = exp(j*2*pi*k*m/N) * Y[m] which (except for a missing "m" which i presume is a typo of the OP's), then i ask you, jim, what must y[n] be for n<0 , (which must have *some* definition if k>0) ? in order for that statement to be true for an arbitrary y[n] and k and m, what must y[n] be for n<0? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 27, 20052005-03-27
robert bristow-johnson wrote:> > in article 42461c77$1_1@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on > 03/26/2005 21:37: > > > > > > > robert bristow-johnson wrote: > >> > >> in article c4b57fd0.0503260544.64cd3e9@posting.google.com, porterboy at > >> porterboy76@yahoo.com wrote on 03/26/2005 08:44: > >> > >>> Is there such thing as a shift-theorem* for filterbanks other than the > >>> discrete fourier transform? For example the discrete cosine transform, > >>> the cosine modulated filterbank, the discrete wavelet transform? > >>> > >>> * The shift theorem for the DFT states that if Y(m) is the m-th DFT > >>> coefficient of y(n) then > >>> > >>> DFT[y(n-k)]_m = exp(j.2pi.k/N).Y(m) > >>> > >>> (This assumes that y(n) is periodic) > >> > >> such an assumption should be implicit with DFT, although there are deniers. > > > > First of all, the assumption that y(n) is periodic was not needed in the > > firat place. Secondly, the above equation actually demonstrates why the > > DFT need not be periodic. Consider when k is a non-rational number. It > > is only *your* assumption that k is an integer that makes the DFT > > periodic. > > well, probably we need to ask the OP what he means by "y(n)". even though > he used parenths instead of square brackets (as in y[n]) it seems to me to > be outside the realm of reasonableness to assume that, when the question is > in the context of DFT (or DCT), that the argument of "y(n)" is anything > other than an integer. if any non-integer "n" is implied, we are talking > about continuous-time (or continuous-something-else, say if it's image > processing) and the DFT has no definition to that. > > now, getting specifically to what the OP said, but giving it a slightly > different notation to eliminate ambiguity (need mono-spaced font): > > N-1 > let Y[m] =def DFT{ y[n] } =def SUM{ y[n] * exp(-j*2*pi*n*m/N) } > n=0 > > then if it is true that > > DFT{ y[n-k] } = exp(j*2*pi*k*m/N) * Y[m] > > which (except for a missing "m" which i presume is a typo of the OP's), then > i ask you, jim, what must y[n] be for n<0 , (which must have *some* > definition if k>0) ? in order for that statement to be true for an > arbitrary y[n] and k and m, what must y[n] be for n<0?We can assume (if you wish) that n is an integer. But if one is willing to entertain the possibility that k is not an integer then it becomes obvious that its rather pointless to assume that n is an integer - which I guess is the meandering point your question is trying to make. Regardless, its your assumptions about how time is referenced that makes the DFT periodic not anything implicit in the DFT. -jim ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Reply by ●March 27, 20052005-03-27
in article 424631fc$1_1@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on 03/26/2005 23:09:> robert bristow-johnson wrote:(small revision...)>> well, probably we need to ask the OP what he means by "y(n)". even though >> he used parenths instead of square brackets (as in y[n]) it seems to me to >> be outside the realm of reasonableness to assume that, when the question is >> in the context of DFT (or DCT), that the argument of "y(n)" is anything >> other than an integer. if any non-integer "n" is implied, we are talking >> about continuous-time (or continuous-something-else, say if it's image >> processing) and the DFT has no definition for that. >> >> now, getting specifically to what the OP said, but giving it a slightly >> different notation to eliminate ambiguity (need mono-spaced font): >> >> N-1 >> let Y[m] =def DFT{ y[n] } =def SUM{ y[n] * exp(-j*2*pi*n*m/N) } >> n=0 >> >> then, if it is true that >> >> DFT{ y[n-k] } = exp(-j*2*pi*k*m/N) * Y[m] >> >> which (except for a missing "-m" which i presume is a typo of the OP's) is >> what the OP postulated, then i ask you, jim, what must y[n] be for n<0 , >> (which must have *some* definition if k>0) ? in order for that statement >> to be true for an arbitrary y[n] and k and m, what must y[n] be for n<0? > > We can assume (if you wish) that n is an integer. But if one is willing > to entertain the possibility that k is not an integer then it becomes > obvious that its rather pointless to assume that n is an integer - which > I guess is the meandering point your question is trying to make. > Regardless, its your assumptions about how time is referenced that makes > the DFT periodic not anything implicit in the DFT.it gets down to a semantic issue, but an important semantic issue. (what is it that we mean when we use terms like DFT?) in the discussion of interpolation of discrete-time (or discrete-whatever) sequences, i am willing to entertain a k that is not an integer. but in simply the discussion of discrete-time sequences, and particularly with the DFT, i am not. the argument of y[..], whatever you call it, is an integer and y[n] has no meaning for n (or whatever lives between the square brackets) that is not an integer. the notation of square brackets for discrete-time sequences was adopted as an alternative to the subscripted "n" for a discrete sequence. that adaptation of notation was made to more compactly express a family of discrete-time sequences (with another integer *subscript* as is done for continuous-time "x(t)"), say, with a multiple-input and/or multiple-output system. it looks better, but has no mathematical meaning other than what it would have if the "[n]" was moved to a subscript. so to focus in on what it is we are debating, jim, is it the DFT (as conventionally defined in all the literature) or is it interpolation? "interpolation of the DFT" is also fine topic to discuss, but let's call it what it is. if we can settle the semantics i will ask the question again that you have evaded answering. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 27, 20052005-03-27
robert bristow-johnson wrote:> > in the discussion of interpolation of discrete-time (or discrete-whatever) > sequences, i am willing to entertain a k that is not an integer. but in > simply the discussion of discrete-time sequences, and particularly with the > DFT, i am not.And that was my point exactly. And no need to go on and on about "n is an integer" that was already agreed. Now why is it inconceivable to shift the frame of reference for a DFT by some non-integer amount? Why would the introduction of a linear phase term make any difference to the DFT? And its really got nothing to do with whether the shift is integer amount or not. The fact is your opposed to a shift of any amount when it comes to the DFT. -jim ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Reply by ●March 28, 20052005-03-28
> A few transforms enjoy the duality of shifting <--> modulation. Youalready> gave an example. The technical name is the Heaviside shiftingtheorem. I'm> not quite sure what you are asking though. What do you mean by ashift> theorem for filterbanks?Well, the DFT is a block transform, as is the DCT. However a cosine modulated filterbank implements a lapped transform. However, it is still a "transform". I guess what I'm asking is: Suppose I time shift the input to a transform by k samples... In the case of the DFT, the mth output coefficient is scaled by by exp(j.2.pi.k.m/N). I was wondering what happens if the transform is a DCT or a DWT or even a lapped transform like a CMFB. Thanks for your reference to the Heaviside shift theorem, it has given me some leads...
Reply by ●March 28, 20052005-03-28
in article 424766d4$1_2@127.0.0.1, jim at "N0sp"@m.sjedging@mwt.net wrote on 03/27/2005 21:06:> robert bristow-johnson wrote: > >> >> in the discussion of interpolation of discrete-time (or discrete-whatever) >> sequences, i am willing to entertain a k that is not an integer. but in >> simply the discussion of discrete-time sequences, and particularly with the >> DFT, i am not. > > And that was my point exactly. And no need to go on and on about "n is > an integer" that was already agreed."n" is a symbol. i don't give much of a rat's ass about the symbol. so, to remove it from the discussion, do you agree or not, that in a discrete-time sequence, that whatever the stuff that goes in between the little square brackets of y[..] is an integer? if i refer to some discrete-time sequence "y[n]", then "n" is an integer. if we're talking about y[n-k], then n-k is an integer. if n is already restricted to be an integer (for some reason), what does that say about k?> Now why is it inconceivable to shift the frame of reference for a DFT > by some non-integer amount?not inconceivable, but for a discrete-time or discrete-frequency sequence, there is no definition of a non-integer shift because there is no definition of what either y[..] or Y[..] for non-integer indices. jim, i'm being very careful to not get sucked into a dispute of contradiction that happens here when we're not extremely careful about terminology and notation. if you want to talk about the subject of interpolation, fine, but let's call it what it is (a definition of a continous-whatever function from discrete-whatever samples). if you want to talk about issues regarding the Discrete-Time Fourier Transform (DCFT), fine, but let's call it what it is (not the DFT). in the meantime, would you please commit to an answer, without evasion, that i asked you from the outset. here it is again:>> >> N-1 >> let Y[m] =def DFT{ y[n] } =def SUM{ y[n] * exp(-j*2*pi*n*m/N) } >> n=0 >> >> then, if it is true that >> >> DFT{ y[n-k] } = exp(-j*2*pi*k*m/N) * Y[m] >> >> which (except for a missing "-m" which i presume is a typo of the OP's) is >> what the OP postulated, then i ask you, jim, what must y[n] be for n<0 , >> (which must have *some* definition if k>0) ? in order for that statement >> to be true for an arbitrary y[n] and k and m, what must y[n] be for n<0?thank you. (i'll get back to this tommorrow.) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
