Another DSP puzzle

Hi Rick (and Jitendra),


I hope Jitendra doesn't mind me stepping in to clarify a few things
here.

>>w_jk(t) = 2^(j/2)w(2^j t - k)<<

This is the standard notation in wavelet theory. However, to avoid
confusion, I am going to replace j with n so that no one mistakes it as
sqrt(-1):

W_nk(t) = 2^(n/2) * W(2^n * t - k)

W_nk(t) is the nth "daughter wavelet" at step k. W(t) is the mother
wavelet. (A mother wavelet can be any time-limited function such as a
rectangle function.) This equation relates a daughter function to its
mother. You can see a wavelet example here:
http://mathworld.wolfram.com/HaarFunction.html

2^(n/2) is the normalizing factor to make every daughter eual in total
energy. nth and (n+1)th daughter wavelets differ in frequency by a
factor of 2. Therefore, DFT of (n+1)th daugher has the same shape as
DFT of the nth daughter decimated by 2. Nomalization will make the DFTs
equal in magnitude as well.

This property of "2" successive daughter wavelet functions, though
similar to what we are talking about here, is not the property we are
looking for in "a" time sequence.



Back to the puzzle proper, my answer is that any sequence with
alternate zeros is a solution and nothing else. A sequence with freq of
Fs/4 is neither necessary nor sufficient condition in this problem. (I
tested this with white noise inserted with alternate zeros. Isn't this
like a zero padding?) Again, I tried to solve this DSP problem by dumb
brute force, i.e. mathematical derivation: (I am not going to show by
dirty work here.)

Essentially, we are looking for something to satisfy:

abs{ SUM[ a(n)*exp(-j*Pi*k*n/N) ] }
= abs{ SUM[ ( a(n)+b(n)*exp(-j*Pi*k/N) )*exp(-j*Pi*k*n/N) ] }
for all non-negative integer k.

The a(n) are even terms and b(n) are odd terms in the input sequence.
(n starts from 0) The obvious general solution is b(n)=0. i.e. all
alternate samples are zero.

Another possibility is for the inner term on the left hand side to be
equal to the conjugate of the inner term on the right hand side, but I
can't find any sequence that can possibly do so "for all k".



BTW, Rick, I am a DSP newbie and I love your book! I am about to finish
reading every single page! Where can I get an errata sheet of your 2nd
edition? THANK YOU!


Best Regards.

KD

Hi Rick (and Jitendra),


I hope Jitendra doesn't mind me stepping in to clarify a few things
here.

>>w_jk(t) = 2^(j/2)w(2^j t - k)<<

This is the standard notation in wavelet theory. However, to avoid
confusion, I am going to replace j with n so that no one mistakes it as
sqrt(-1):

W_nk(t) = 2^(n/2) * W(2^n * t - k)

W_nk(t) is the nth "daughter wavelet" at step k. W(t) is the mother
wavelet. (A mother wavelet can be any time-limited function such as a
rectangle function.) This equation relates a daughter function to its
mother. You can see a wavelet example here:
http://mathworld.wolfram.com/HaarFunction.html

2^(n/2) is the normalizing factor to make every daughter eual in total
energy. nth and (n+1)th daughter wavelets differ in frequency by a
factor of 2. Therefore, DFT of (n+1)th daugher has the same shape as
DFT of the nth daughter decimated by 2. Nomalization will make the DFTs
equal in magnitude as well.

This property of "2" successive daughter wavelet functions, though
similar to what we are talking about here, is not the property we are
looking for in "a" time sequence.



Back to the puzzle proper, my answer is that any sequence with
alternate zeros is a solution and nothing else. A sequence with freq of
Fs/4 is neither necessary nor sufficient condition in this problem. (I
tested this with white noise inserted with alternate zeros. Isn't this
like a zero padding?) Again, I tried to solve this DSP problem by dumb
brute force, i.e. mathematical derivation: (I am not going to show by
dirty work here.)

Essentially, we are looking for something to satisfy:

abs{ SUM[ a(n)*exp(-j*Pi*k*n/N) ] }
= abs{ SUM[ ( a(n)+b(n)*exp(-j*Pi*k/N) )*exp(-j*Pi*k*n/N) ] }
for all non-negative integer k.

The a(n) are even terms and b(n) are odd terms in the input sequence.
(n starts from 0) The obvious general solution is b(n)=0. i.e. all
alternate samples are zero.

Another possibility is for the inner term on the left hand side to be
equal to the conjugate of the inner term on the right hand side, but I
can't find any sequence that can possibly do so "for all k".



BTW, Rick, I am a DSP newbie and I love your book! I am about to finish
reading every single page! Where can I get an errata sheet of your 2nd
edition? THANK YOU!


Best Regards.

KD

On Tue, 14 Dec 2004 15:49:46 GMT, r.lyons@_BOGUS_ieee.org (Rick Lyons)
wrote:

>On Mon, 13 Dec 2004 15:09:36 GMT, r.lyons@_BOGUS_ieee.org (Rick Lyons)
>wrote:
>
>Hi,
>
>  you guys "came through" again.
>I 'm not surprised.
>
>My answer to my puzzle is a 
>time sequence where every other sample 
>is a zero.

I believe that the posited answer is incorrect. 

Here is a simple counterexample: The sequence [1 1 1 , ...] Has a
component only at DC. The result of the transform is unchanged at any
decimation level. It has no zeroes. In general if a time series is a
solution to the problem, then the same time series with a mean shift
is also.

Randy
>
>I ran across this little puzzle while trying 
>to understand why it is that we can 
>interchange (swap) upsampling by integer U 
>with downsampling by integer D if, and 
>only if, U & D are "relatively prime".
>
>[-Rick-]

R Potter <rpotter1@socal.rr.com> writes:

> On Tue, 14 Dec 2004 15:49:46 GMT, r.lyons@_BOGUS_ieee.org (Rick Lyons)
> wrote:
>
>>On Mon, 13 Dec 2004 15:09:36 GMT, r.lyons@_BOGUS_ieee.org (Rick Lyons)
>>wrote:
>>
>>Hi,
>>
>>  you guys "came through" again.
>>I 'm not surprised.
>>
>>My answer to my puzzle is a 
>>time sequence where every other sample 
>>is a zero.
>
> I believe that the posited answer is incorrect. 
>
> Here is a simple counterexample: The sequence [1 1 1 , ...] Has a
> component only at DC. The result of the transform is unchanged at any
> decimation level. 

Not true. Here's a counterexample: The 4-point DFT of [1 1 1 1] is
4. The 2-point DFT of [1 1 1 1 ] decimated by two, which is [1 1], is
2.
-- 
%  Randy Yates                  % "She's sweet on Wagner-I think she'd die for Beethoven.
%% Fuquay-Varina, NC            %  She love the way Puccini lays down a tune, and
%%% 919-577-9882                %  Verdi's always creepin' from her room." 
%%%% <yates@ieee.org>           % "Rockaria", *A New World Record*, ELO   
http://home.earthlink.net/~yatescr

David Kirkland wrote:

> I believe another way to think of this is is to have tonals in the
> original signal. The second tonal is placed such that when the sequence
> is decimated it is aliased down onto the first tonal - making up for the
> factor of 1/2. The phases would also have to be taken into account so
> that they add coherently.


Hi David,

OK. That would be another way of thinking of it. But to continue with
the puzzle:

If you construct a sequence that meets your above described criteria, is
it possible to end up with any other form than the solution Rick
provided (a sequence in the form of [x 0 x 0 x 0 x 0 ....] and if not,
why not?

-jim


----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= East/West-Coast Server Farms - Total Privacy via Encryption =---


-----------== Posted via Newsfeed.Com - Uncensored Usenet News ==----------
   http://www.newsfeed.com       The #1 Newsgroup Service in the World!
-----= Over 100,000 Newsgroups - Unlimited Fast Downloads - 19 Servers =-----

Hi Rick,

(I wonder, in my previous post, if I did a "reply to Rick" or "reply to
the thread". I can't see my earlier post in this thread. Anyone else
saw it?)

My copy of your book is a first printing. You can e-mail it to
kd20128@yahoo.com.

Again, thank you very much. I enjoy reading your posts (and others') in
this newsgroup. You guys have certainly made great contributions to the
DSP community.


Best Regards.

KD

John Monro wrote:
> Rune Allnor wrote:
>
> >Rick Lyons wrote:
> >
> >
> >>Hi Guys,
> >>
> >>In the past I've posted what I thought
> >>were interesting little DSP puzzles only to
> >>find that ten of you reply with the
> >>correct answer within 24 hours!  So I've
> >>failed, thus far, to come up with any
> >>"puzzles" that turn out to puzzle anyone.
> >>But I'm not going to stop trying to puzzle you.
> >>
> >>OK, here goes.  While not often stated
> >>in the DSP literature, when we decimate
> >>a signal sequence the spectrum of the
> >>decimated sequence experiences an
> >>amplitude loss.  That makes sense because
> >>DFT amplitudes are proportional to the
> >>length of the sequence applied to the
> >>DFT.  If we decimate a sequence by two, the
> >>decimated sequence is half the length of
> >>the undecimated sequence.  So the DFT
> >>amplitudes of the decimated sequence will be
> >>half the DFT amplitudes of the undecimated
> >>sequence.
> >>
> >>The only place I've seen this "spectral amplitude
> >>loss from decimation" issue discussed is
> >>in Vaidyanathan's Multirate Systems book.
> >>
> >>Yesterday, I ran across a time sequence x(n)
> >>that when decimated by two, the DFT amplitudes
> >>of the decimated sequence were *equal* to
> >>the DFT amplitudes of the undecimated x(n)!
> >>
> >>Can you guess what x(n) is?
> >>
> >>
> >
> >My *guess* is that x(n) is such that every other sample
> >is 0, and you decimate so as to remove the 0 samples:
> >
> >...,x(-4),0,x(-2),0,x(0),0,x(2),0,x(4),...
> >
> >|  Decimation by 2
> >V
> >
> >...,x(-4),x(-2),x(0),x(2),x(4),...
> >
> >Continuing along these lines, I agree with Randy in
> >that one (the only?) sequence that meets the criteria
> >of the puzzle and where the decimated sequence also
> >meets he Nyquist sampling criterion (although just
> >barely...) is
> >
> >x(n) = cos(2*pi*fs/4*n)
> >where fs is the sampling frequency before decimation.
> >
> >Rune
> >
> >
> >
> Rune,
> I don't agree that the decimated signal even 'barely' meets the
Nyquist
> Criterion.  The problem is, after decimation the signal becomes a
> sequence of constant-amplitude samples, having been aliased down to
D.C.

I can't see what you mean. A cosine with frequency fs/4 gives
the undecimated sequence

... 0 1 0 -1 0 1 0 -1 0 ...

Decimating this by 2 gives either

... 0 0 0 0 0 0 ...

or

... -1 1 -1 1 -1 1 -1 ...

The all zeros sequence is aliased dow to DC. The other one has
one spectrum line at fsd/2, where fsd is the sampling frequency
after decimation. For this sequence, the Nyquist criterion is
violated for all sequences exept the cosine. Formally, a cosine
can be reconstructed when sampled at the Nyquist frequency, since
the cosine is sampled at the maximum amplitudes. This is, of course,
only of theoretical interest since one in any practical situation
would not know whether or not a sinusoidal is sampled at the
maximum.

> This, by the way,  shows that the often-used version of the Nyquist
> Criterion: that "f  must be less than oe equal to fs,"  is not quite
> correct,
> and should be:  " f must be less than fs"  (Where f is the frequency
of
> the highest-frequency component and fs is the sampling frequency.)

Agreed.

> As to Rick's puzzle, he does refer to the "DFT amplitudes" (plural)
so
> he may have given away a hint there, suggesting maybe that there is
more
> than one frequency component involved.  Unfortunately,  I can't think
of
> any multiple-component signal that has zero-crossings in the right
place
> and does not have the aliasing problem.  It will be interesting to
see
> the answer!

When I read Rick's post I never took it to be a a very practical
question. I read it more like one of those chess puzzles we see here
and there. These puzzles can be almost insane from a chess game point
of view, but what matters is to use the rule of the game to solve a
stated problem. It might not be practical per se, but it's nice
training to think in terms of the rules you have to use in practice.
Rune

On 15 Dec 2004 09:43:06 -0800, "KEDI" <kd20128@yahoo.com> wrote:

>Hi Rick,
>
>(I wonder, in my previous post, if I did a "reply to Rick" or "reply to
>the thread". I can't see my earlier post in this thread. Anyone else
>saw it?)
>
>My copy of your book is a first printing. You can e-mail it to
>kd20128@yahoo.com.
>
>Again, thank you very much. I enjoy reading your posts (and others') in
>this newsgroup. You guys have certainly made great contributions to the
>DSP community.
>
>
>Best Regards.
>
>KD

Hi KD,

  The errata is "on its way".

[-Rick-]

Rune, you wrote:
(snip)

>I can't see what you mean. A cosine with frequency fs/4 gives
>the undecorated sequence
>
>... 0 1 0 -1 0 1 0 -1 0 ...
>
>Decimating this by 2 gives either
>
>... 0 0 0 0 0 0 ...
>
>or
>
>... -1 1 -1 1 -1 1 -1 ...
>
>The all zeros sequence is aliased down to DC. The other one has
>one spectrum line at fsd/2, where fsd is the sampling frequency
>after decimation. For this sequence, the Nyquist criterion is
>violated for all sequences except the cosine. Formally, a cosine
>can be reconstructed when sampled at the Nyquist frequency, since
>the cosine is sampled at the maximum amplitudes. This is, of course,
>only of theoretical interest since one in any practical situation
>would not know whether or not a sinusoidal is sampled at the
>maximum.
>  
>

You are quite right of course. Thanks for pointing that out.
 In my rush to find a function that had zeroes in the right places I 
overlooked the fact that the signs were alternating.


>
>When I read Rick's post I never took it to be a a very practical
>question. I read it more like one of those chess puzzles we see here
>and there. These puzzles can be almost insane from a chess game point
>of view, but what matters is to use the rule of the game to solve a
>stated problem. It might not be practical per se, but it's nice
>training to think in terms of the rules you have to use in practice.
>Rune
>  
>
Yes, and I note that Rick did say it was a "time sequence" and did not 
infer that the samples came from some practical application.
An interesting exercise.

Regards,
John

jim wrote:

> 
> Jerry Avins wrote:
> 
> 
>>If that's the answer, it's cooked. If you take alternate samples of
>>[1 0 1 0 1 0], you could also get [0 0 0]. The average of those
>>amplitudes is right in the money! 8-) The real cook is that you need to
>>remove Fs/4 (Fs is the original rate) and above before decimating, so
>>you will get [0 0 0] whether you pick the odd samples or the even ones.
> 
> 
> I don't think that's correct. First your ignoring the DC content of the
> original, which should under no circumstance disappear. Second I think
> the basis of the puzzle was that the sequence would be resampled only so
> removing the fs/4 would eliminate the aliasing of fs/4 which is what
> makes the puzzle puzzling:} 
> 
> -jim

You're right: I overlooked DC. After the needed low-pass filter,
[1 0 1 0 1 0] should become [.5 .5 .5 .5 .5 .5], so is doesn't matter
whether even samples are chosen, or odd.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������