> 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
Reply by Andor●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 Andor●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 Rick Lyons●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 mnentwig●August 27, 20072007-08-27
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
Reply by Rick Lyons●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,
OK. I think I have one correct answer.
As far as I can tell, decimating by two is not
equivalent to decimating by four followed by
interpolation by two.
[-Rick-]
Reply by Greg Berchin●August 27, 20072007-08-27
On Aug 27, 10:07 am, R.Lyons@_BOGUS_ieee.org (Rick Lyons) wrote:
> ... isn't there some restriction
> about decimation followed by interpolation
> only works "as expected" when the decimation and
> interpolation factors are mutually prime?
Rick,
Could you be referring to polyphase filtering, where the order of
downsampling and upsampling can only be reversed if the downsampling
and upsampling factors are relatively prime?
Greg
Reply by Scott Seidman●August 27, 20072007-08-27
Randy Yates <yates@ieee.org> wrote in news:m37inkdi3d.fsf@ieee.org:
> 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.
When the highest frequency content is bigger than Fs/4, with Fs being the
original sampling rate.
--
Scott
Reverse name to reply
Reply by Rick Lyons●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 Randy,
I don't have solid answer for ya'
right now, but isn't there some restriction
about decimation followed by interpolation
only works "as expected" when the decimation and
interpolation factors are mutually prime?
[-Rick-]
Reply by G Iveco●August 25, 20072007-08-25
frequency related issue is it?
when you decimate, you lose some signal in the high range of the bandwidth.
and you can't recover the lost signal by interpolation.
Am I right?
"Randy Yates" <yates@ieee.org> wrote in message
news:m37inkdi3d.fsf@ieee.org...
> 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,
> %% Fuquay-Varina, NC % and kiss her
> interface,
> %%% 919-577-9882 % til then, I'll leave her
> alone."
> %%%% <yates@ieee.org> % 'Yours Truly, 2095', *Time*, ELO
> http://home.earthlink.net/~yatescr