Hello, Wild guess... I think what Greg mentioned is known as "Noble Identities". Maybe that helps with your "riddle". I didn't find any good links on the web, but it's covered for example in Fred Harris' Multirate book. Cheers Markus
A DSP Decimation Riddle
Started by ●August 24, 2007
Reply by ●August 27, 20072007-08-27
Reply by ●August 27, 20072007-08-27
On Fri, 24 Aug 2007 12:15:34 -0400, Randy Yates <yates@ieee.org> wrote:>Just for fun! > >When is decimating by N not equivalent to decimating by 2*N followed >by interpolating by 2? > >This is not a trick question and is an actual real-life application. >-- >% Randy Yates % "Maybe one day I'll feel her cold embrace,Hi, Oh shoot. I think I'm "muddying up the water" here. Randy, when you wrote "interpolation" for some reason I thought of strictly "stuffing zeros with no filtering." If by "interpolation" you mean "stuffing zeros followed by filtering", then I vote for Greg Berchin's reply. [-Rick-]
Reply by ●August 28, 20072007-08-28
Rick Lyons wrote:> On Fri, 24 Aug 2007 12:15:34 -0400, Randy Yates <ya...@ieee.org> > wrote: > > >Just for fun! > > >When is decimating by N not equivalent to decimating by 2*N followed > >by interpolating by 2? > > >This is not a trick question and is an actual real-life application. > >-- > >% Randy Yates % "Maybe one day I'll feel her cold embrace, > > Hi, > Oh shoot. I think I'm "muddying up > the water" here. Randy, when you wrote > "interpolation" for some reason I thought of > strictly "stuffing zeros with no filtering." > > If by "interpolation" you mean > "stuffing zeros followed by filtering", > then I vote for Greg Berchin's reply.Well, this _is_ a trick question, and you all fell for it :-). The trick lies in the reconstruction step. "Interpolating by 2" must be assumed to mean the following: 1. Insert a zero every other sample (expanding by a factor of 2). 2. Apply an (as yet unspecified) interpolation filter. Consider the simple case N=1 (decimating by 2, expanding by 2 and filtering). As other posters have stated, if the signal is limited to the band [0, Fs/4], then the original signal, and the signal we get after applying the above steps 1 and 2 will be equal if the interpolation filter is h=1/2 sinc(n/2), n=0, +/-1, +/-2, ... On the other hand, if the original signal is limited to [Fs/4, Fs/2], and the interpolation filter is h=1/2 sinc(n/2) cos(pi n), n=0, +/-1, +/-2, ..., then the original signal will also be equal to the decimated and interpolated signal. Why? Decimating by 2 aliases the band [Fs/4,Fs/2] to [0,Fs/4] (after decimation, the signal is sampled at Fs/2). Expanding by 2 generates an image of the band [0,Fs/4] at [Fs/4,Fs/2]. This image is the original signal (the spectral inversion of the alias is undone in the image). Now one can simply apply a highpass to remove the content from [0,Fs/4] to retrieve the original signal. To generalize, I post a new DSP riddle: Assume a signal x_k[n] is limited to the band [(k-1) Fs/(2 N), k Fs/(2 N)] for k=1,2,...,2 N. Let y[n] = x_k[2 N n] (decimation by a factor of 2 N), y2[n] = y[n/2] (expanded by factor of 2 with zero-stuffing) and z[n] = x_k[N n] (decimation by a factor of N). Specify the filter h_k[n], such that z[n] = y2[n] * h_k[n] (* denotes convolution). :-) Regards, Andor
Reply by ●August 30, 20072007-08-30
On 28 Aug., 17:20, Andor <andor.bari...@gmail.com> wrote:> Rick Lyons wrote: > > On Fri, 24 Aug 2007 12:15:34 -0400, Randy Yates <ya...@ieee.org> > > wrote: > > > >Just for fun! > > > >When is decimating by N not equivalent to decimating by 2*N followed > > >by interpolating by 2? > > > >This is not a trick question and is an actual real-life application. > > >-- > > >% Randy Yates % "Maybe one day I'll feel her cold embrace, > > > Hi, > > Oh shoot. I think I'm "muddying up > > the water" here. Randy, when you wrote > > "interpolation" for some reason I thought of > > strictly "stuffing zeros with no filtering." > > > If by "interpolation" you mean > > "stuffing zeros followed by filtering", > > then I vote for Greg Berchin's reply. > > Well, this _is_ a trick question, and you all fell for it :-). The > trick lies in the reconstruction step. "Interpolating by 2" must be > assumed to mean the following: > > 1. Insert a zero every other sample (expanding by a factor of 2). > 2. Apply an (as yet unspecified) interpolation filter. > > Consider the simple case N=1 (decimating by 2, expanding by 2 and > filtering). As other posters have stated, if the signal is limited to > the band > > [0, Fs/4], > > then the original signal, and the signal we get after applying the > above steps 1 and 2 will be equal if the interpolation filter is > > h=1/2 sinc(n/2), n=0, +/-1, +/-2, ... > > On the other hand, if the original signal is limited to > > [Fs/4, Fs/2], > > and the interpolation filter is > > h=1/2 sinc(n/2) cos(pi n), n=0, +/-1, +/-2, ..., > > then the original signal will also be equal to the decimated and > interpolated signal. Why? Decimating by 2 aliases the band [Fs/4,Fs/2] > to [0,Fs/4] (after decimation, the signal is sampled at Fs/2). > Expanding by 2 generates an image of the band [0,Fs/4] at [Fs/4,Fs/2]. > This image is the original signal (the spectral inversion of the alias > is undone in the image). Now one can simply apply a highpass to remove > the content from [0,Fs/4] to retrieve the original signal. > > To generalize, I post a new DSP riddle: Assume a signal x_k[n] is > limited to the band [(k-1) Fs/(2 N), k Fs/(2 N)] for k=1,2,...,2 N.Typo! The signal should be limited to [(k-1) Fs/(4 N), k Fs/(4 N)].> Let > > y[n] = x_k[2 N n] (decimation by a factor of 2 N), > y2[n] = y[n/2] (expanded by factor of 2 with zero-stuffing) > > and > > z[n] = x_k[N n] (decimation by a factor of N). > > Specify the filter h_k[n], such that z[n] = y2[n] * h_k[n] (* denotes > convolution).Hint: I've specified all of the filters needed above already. The answer is of the form "If k has this property, use this filter, and if k has that property, use that filter." Common guys! Regards, Andor
Reply by ●August 31, 20072007-08-31
On 30 Aug., 09:31, Andor wrote:> On 28 Aug., 17:20, Andor wrote: > > > > > > > Rick Lyons wrote: > > > On Fri, 24 Aug 2007 12:15:34 -0400, Randy Yates <ya...@ieee.org> > > > wrote: > > > > >Just for fun! > > > > >When is decimating by N not equivalent to decimating by 2*N followed > > > >by interpolating by 2? > > > > >This is not a trick question and is an actual real-life application. > > > >-- > > > >% Randy Yates % "Maybe one day I'll feel her cold embrace, > > > > Hi, > > > Oh shoot. I think I'm "muddying up > > > the water" here. Randy, when you wrote > > > "interpolation" for some reason I thought of > > > strictly "stuffing zeros with no filtering." > > > > If by "interpolation" you mean > > > "stuffing zeros followed by filtering", > > > then I vote for Greg Berchin's reply. > > > Well, this _is_ a trick question, and you all fell for it :-). The > > trick lies in the reconstruction step. "Interpolating by 2" must be > > assumed to mean the following: > > > 1. Insert a zero every other sample (expanding by a factor of 2). > > 2. Apply an (as yet unspecified) interpolation filter. > > > Consider the simple case N=1 (decimating by 2, expanding by 2 and > > filtering). As other posters have stated, if the signal is limited to > > the band > > > [0, Fs/4], > > > then the original signal, and the signal we get after applying the > > above steps 1 and 2 will be equal if the interpolation filter is > > > h=1/2 sinc(n/2), n=0, +/-1, +/-2, ... > > > On the other hand, if the original signal is limited to > > > [Fs/4, Fs/2], > > > and the interpolation filter is > > > h=1/2 sinc(n/2) cos(pi n), n=0, +/-1, +/-2, ..., > > > then the original signal will also be equal to the decimated and > > interpolated signal. Why? Decimating by 2 aliases the band [Fs/4,Fs/2] > > to [0,Fs/4] (after decimation, the signal is sampled at Fs/2). > > Expanding by 2 generates an image of the band [0,Fs/4] at [Fs/4,Fs/2]. > > This image is the original signal (the spectral inversion of the alias > > is undone in the image). Now one can simply apply a highpass to remove > > the content from [0,Fs/4] to retrieve the original signal. > > > To generalize, I post a new DSP riddle: Assume a signal x_k[n] is > > limited to the band [(k-1) Fs/(2 N), k Fs/(2 N)] for k=1,2,...,2 N. > > Typo! The signal should be limited to [(k-1) Fs/(4 N), k Fs/(4 N)]. > > > Let > > > y[n] = x_k[2 N n] (decimation by a factor of 2 N), > > y2[n] = y[n/2] (expanded by factor of 2 with zero-stuffing) > > > and > > > z[n] = x_k[N n] (decimation by a factor of N). > > > Specify the filter h_k[n], such that z[n] = y2[n] * h_k[n] (* denotes > > convolution).Here is my solution: Let B = Fs/(4N) and x_k[n] be sampled at Fs and limited to the band [(k-1) B, k B], for some k = 1, 2, ..., 2 N. |X_k(f)| ^ | /| | / | | / | | / | | / | | / | | / | -+-------+-------+--- ... ---+-------+-- ... --+--> f 0 B 2 B (k-1) B k B 2 N B Decimation of x_k[n] by N gives z[n]. There are 4 different cases of how the spectrum X_k(f) gets aliased into the new baseband [0, 2 B]: - floor((k-1)/2) even, k odd: |Z(f)| ^ | /| | / | | / | | / | | / | | / | |/ | -+-------+-------+--> f 0 B 2 B - floor((k-1)/2) even, k even: |Z(f)| ^ | /| | / | | / | | / | | / | | / | | / | -+-------+-------+--> f 0 B 2 B - floor((k-1)/2) odd, k even: |Z(f)| ^ |\ | \ | \ | \ | \ | \ | \ -+-------+-------+--> f 0 B 2 B - floor((k-1)/2) odd, k odd: |Z(f)| ^ | |\ | | \ | | \ | | \ | | \ | | \ | | \ -+-------+-------+--> f 0 B 2 B Decimation of x_k[n] by 2 N followed by expansion with 2 gives y2[n]. This time there are only 2 different possible outcomes: - k odd: |Y2(f)| ^ | / \ | / \ | / \ | / \ | / \ | / \ |/ \ -+-------+-------+--> f 0 B 2 B - k even: |Y2(f)| ^ |\ /| | \ / | | \ / | | \ / | | \ / | | \ / | | \ / | -+-------+-------+--> f 0 B 2 B So we see what the required filter h_k[n] to make y2[n] equal to z[n] must be: if (floor((k-1)/2) odd && k even) || (floor((k-1)/2) even && k odd) h_k[n] = 1/2 sinc(n/2) else h_k[n] = 1/2 sinc(n/2) cos(pi n) Regards, Andor
