Forums

How to obtain X(z^1/2) from X(z)

Started by Jérôme September 20, 2011
Dear all,

I have a question linked to the decimation of a signal.

Let's have a signal x(n), and X(z) its Z-transform. If we decimate this
signal, i.e. xe(n) = x(2n), we obtain the following Z-transform :
Xe(z) = 1/2 [X(z^1/2) + X(-z^1/2)]

My question is : is there a way to obtain a signal with X(z^1/2) as
Z-transform.

I find one theoretical way of doing it, but not exact in practice. If we
create two signals containing respectively the even and odd samples of x(n)
(even samples are obtained by decimation by two, odd samples are obtained
by delaying the signal of one sample and then decimating by two), they have
the following Z-transform :
Xe(z) = 1/2        [X(z^1/2) + X(-z^1/2)]
Xo(z) = 1/2 z^-1/2 [X(z^1/2) - X(-z^1/2)]

Now, we can get the the wanted signal like this :
X(z^1/2) = z^-1 Xe(z) + z^-1/2 Xo(z)

The problem here is that we need to perform a delay of half a sample
(z^-1/2), which can be approximated through FIR or IIR filters, but cannot
be obtained exactly.

I would like to know if anybody has an idea about this problem, or can help
to show if there is a solution or not with a practical implementation (I
doubt that there is a solution since to have Y(z) = X(z^1/2) through
decimation, half of the samples of x(n) should be zero. But I didn't arrive
to prove it).

Thank you in advance

Jérôme


On 9/20/2011 12:55 PM, J�r�me wrote:
> Dear all, > > I have a question linked to the decimation of a signal. > > Let's have a signal x(n), and X(z) its Z-transform. If we decimate this > signal, i.e. xe(n) = x(2n), we obtain the following Z-transform : > Xe(z) = 1/2 [X(z^1/2) + X(-z^1/2)] > > My question is : is there a way to obtain a signal with X(z^1/2) as > Z-transform. > > I find one theoretical way of doing it, but not exact in practice. If we > create two signals containing respectively the even and odd samples of x(n) > (even samples are obtained by decimation by two, odd samples are obtained > by delaying the signal of one sample and then decimating by two), they have > the following Z-transform : > Xe(z) = 1/2 [X(z^1/2) + X(-z^1/2)] > Xo(z) = 1/2 z^-1/2 [X(z^1/2) - X(-z^1/2)] > > Now, we can get the the wanted signal like this : > X(z^1/2) = z^-1 Xe(z) + z^-1/2 Xo(z) > > The problem here is that we need to perform a delay of half a sample > (z^-1/2), which can be approximated through FIR or IIR filters, but cannot > be obtained exactly. > > I would like to know if anybody has an idea about this problem, or can help > to show if there is a solution or not with a practical implementation (I > doubt that there is a solution since to have Y(z) = X(z^1/2) through > decimation, half of the samples of x(n) should be zero. But I didn't arrive > to prove it). > > Thank you in advance
There's a traditional engineering approach to difficult problems: If you can't solve the problem you have, construct a similar one that you _can_ solve. Perhaps it will help. If you can arrange to sample twice as fast (or upsample by 2) then a one-sample delay at the higher rate is a half-sample delay at the original rate. Will decimating everything by two after the delay id performed put you where you want to be? Jerry -- Engineering is the art of making what you want from things you can get.
>> I doubt that there is a solution since to have Y(z) = X(z^1/2) through
decimation, half of the samples of x(n) should be zero Let me say this in other words: To have exactly the same signal at twice the sampling rate, I insert every second sample zero. That's it. The original samples remain, zeros are placed in-between. The catch lies in "exactly the same signal": - The spectrum of the original signal is periodic in multiples of the initial sampling rate. - The spectrum of the second signal contains one alias zone and is periodic in multiples of the high rate. They are indeed identical - I "added" zero samples, in other words, I added nothing. It may be that the original question boils down to "there is no perfect lowpass" (which is required to -suppress- the newly created alias zone at the high rate, and / or to implement delay by half a sample).
On Tue, 20 Sep 2011 11:55:26 -0500, Jérôme wrote:

> Dear all, > > I have a question linked to the decimation of a signal. > > Let's have a signal x(n), and X(z) its Z-transform. If we decimate this > signal, i.e. xe(n) = x(2n), we obtain the following Z-transform : Xe(z) > = 1/2 [X(z^1/2) + X(-z^1/2)] > > My question is : is there a way to obtain a signal with X(z^1/2) as > Z-transform. > > I find one theoretical way of doing it, but not exact in practice. If we > create two signals containing respectively the even and odd samples of > x(n) (even samples are obtained by decimation by two, odd samples are > obtained by delaying the signal of one sample and then decimating by > two), they have the following Z-transform : > Xe(z) = 1/2 [X(z^1/2) + X(-z^1/2)] Xo(z) = 1/2 z^-1/2 [X(z^1/2) - > X(-z^1/2)] > > Now, we can get the the wanted signal like this : X(z^1/2) = z^-1 Xe(z) > + z^-1/2 Xo(z) > > The problem here is that we need to perform a delay of half a sample > (z^-1/2), which can be approximated through FIR or IIR filters, but > cannot be obtained exactly. > > I would like to know if anybody has an idea about this problem, or can > help to show if there is a solution or not with a practical > implementation (I doubt that there is a solution since to have Y(z) = > X(z^1/2) through decimation, half of the samples of x(n) should be zero. > But I didn't arrive to prove it). > > Thank you in advance > > Jérôme
I'm not sure what math you believe that you're using to arrive at your Xe (z), but you're violating one of the ground rules of using the z transform to analyze systems. First, yes, you _are_ analyzing a system. If you had any one particular signal and you wanted to find the z transform of its decimated version, you would just find the time-domain version of the signal, decimate it, and then find the z transform of that. But you want to have a 'magic box' that you run any arbitrary signal through, and get a decimated version out -- that magic box is a system. But the system that you want to analyze is time (well, shift) varying. And you can't use the z transform to analyze shift varying systems, any more than you can use the Laplace transform to analyze time varying ones. So you can't get there from here, at least not by using the z transform. You _could_ use the discrete-time Fourier transform for at least part of this, by modeling the sampling process as a multiplication by the sequence 1,0,1,0,... and then a compaction of the spectrum. But you'd have to mind your P's and Q's very carefully to make sure that such easy- to-understand time domain phenomenon as a signal that is zero for even samples and non-zero for odd samples gets transformed correctly. Dunno if that helps -- tell us what you're really doing, and perhaps more help will be forthcoming. -- www.wescottdesign.com
On 09/20/2011 12:55 PM, J�r�me wrote:
> [...] > The problem here is that we need to perform a delay of half a sample > (z^-1/2), which can be approximated through FIR or IIR filters, but cannot > be obtained exactly.
Why do you say that? I disagree. At least, it can be approximated to any arbitrary accuracy.
> I would like to know if anybody has an idea about this problem, or can help > to show if there is a solution or not with a practical implementation (I > doubt that there is a solution since to have Y(z) = X(z^1/2) through > decimation, half of the samples of x(n) should be zero.
That's not true.
> But I didn't arrive to prove it).
Well, that's good, cause it's not true. Here's a trivial counter-example: sample a DC signal, x(t) = A, at any arbitrary sample rate. The output is xs(nT) = A. Delay the sampling by 1/2 sample: the output is still xs(nT) = A! A DC signal isn't just a one-off, either. Just think what the sampling theorem means - you can reconstruct any continuous signal (within the usual constraints) from its samples. That means that any signal that is non-zero at (n + 1/2)T will have a non-zero half-sample delay. --Randy
Thank you all for your answers. I response to each one in the order of
arrival.
I just put two references I use after :
[1] Multirate Digital Filters..., Vaidyanathan.
http://www.systems.caltech.edu/dsp/ppv/papers/ProcIEEEmultirateTUTExtra.pdf
[2] Principles of fractinal delay filters, Välimäki.
http://www.acoustics.hut.fi/~vpv/publications/icassp00-fd.pdf

>> Jerry : "If you can arrange to sample twice as fast (or upsample by 2)
then a one-sample delay at the higher rate is a half-sample delay at the original rate.". It's a good idea, but it's cheating. I cannot play on the initial sampling frequency.
>> mnentwig : "It may be that the original question boils down to "there is
no perfect lowpass" (which is required to -suppress- the newly created alias zone at the high rate, and / or to implement delay by half a sample)." In the multirate systems, the "good thing" is that you permit aliasing after the analysis bank because you can further remove it by choosing the corresponding synthesis filters. cf [1] Fig. 13 and Eqs. 27 to 30. "Let me say this in other words: To have exactly the same signal at twice the sampling rate, I insert every second sample zero." This way of telling it conforts me to think that it is not possible.
>> Tim : "I'm not sure what math you believe that you're using to arrive at
your Xe(z), but you're violating one of the ground rules of using the z transform to analyze systems." "you can't use the z transform to analyze shift varying systems" I don't know why you are shocked by such equations, it's not because decimator and expander are LTV systems that you cannot use the z-transform, all papers and books about multirate systems use it. Cf [1] Eqs. 3a and 3b, which give the z transform of the expander output and of the decimator output.
>> Randy : "Why do you say that? I disagree. At least, it can be
approximated to any arbitrary accuracy." I was not saying that this is the delay which is approximated, I wanted to say there is no FIR or IIR filters which the transfer function is z^-1/2 (and in general z^-M/N), but they are filters that can approximate this transfer function, cf [2]. I am not really convinced by your example, you talk about delaying of 1/2 sample but no decimation. Indeed you can reconstruct value between samples with sinc function, but we return to the previous problem of the realization. The ideal fractional delay filter is nonrealizable because its impulse response is infinite (cf [2]).
Jerry, I come back on your point.
>> If you can arrange to sample twice as fast (or upsample by 2) then a
one-sample delay at the higher rate is a half-sample delay at the original rate. In fact it's not even cheating, it could not work. We have an input X(z), we decimate it by two and obtain Y(z). Now we want to delay Y(z) by half a sample, so we perform these operations : X(z) -> [Decimation by 2] -> Y(z) -> [z^-1/2] -> V(z) which gives the following equations : Y(z) = 1/2 [X(z^1/2) + X(-z^1/2)] V(z) = z^-1/2 Y(z) = 1/2 z^-1/2 [X(z^1/2) + X(-z^1/2)] Now if we delay by one sample before the decimation, we have this system : X(z) -> [z^-1] -> U(z) -> [Decimation by 2] -> V(z) which gives the following equations : U(z) = z^-1 X(z) V(z) = 1/2 [U(z^1/2) + U(-z^1/2)] = 1/2 [z^-1/2 X(z^1/2) - z^-1/2 X(z^1/2)] = 1/2 z^-1/2 [X(z^1/2) - X(z^1/2)] The results are different. This is because the noble identities may not work if the transfer function of the filter (here H(z) = z^-1/2) after the decimator or before the expander is irrationnal (which is the case here). cf [1] of previous post.
On 09/21/2011 08:34 AM, J�r�me wrote:
> [...] > I am not really convinced by your example, you talk about delaying > of 1/2 sample but no decimation.
Who said anything about decimation? You stated: The problem here is that we need to perform a delay of half a sample (z-1/2), which can be approximated through FIR or IIR filters, but cannot be obtained exactly.
> Indeed you can reconstruct value between samples with sinc function, > but we return to the previous problem of the realization. The ideal > fractional delay filter is nonrealizable because its impulse > response is infinite (cf [2]).
Well make up your mind. You seem to be vascillating between "no exact representation" and "no exact realization." There are no exact realizations of filters of any kind in the real world since you have all kinds of nasty practical matters to contend with (round-off noise, accuracy, quantized coefficients, etc.).
>> z^-M/N
Hello, yes, it boils down to ideal lowpass filtering. Conceptually, delaying a signal by any sub-sample length means reconstructing the continuous-time waveform and resampling it. The former needs an ideal lowpass filter. In other words, I convolve every past and future sample with a sinc pulse, as was stated. BTW, this may be of interest (as general background): http://signal.hut.fi/spit/publications/1996j5.pdf
Hello,

>> Who said anything about decimation?
You said "That's not true." after "I doubt that there is a solution since to have Y(z) = X(z^1/2) through decimation, half of the samples of x(n) should be zero." This is why I said that you didn't talk about decimation.
>> There are no exact realizations of filters of any kind in the real world
since you have all kinds of nasty practical matters to contend with (round-off noise, accuracy, quantized coefficients, etc.)." For the moment, I don't care about the errors due to quantization, I just would like a schematic that gives me the exact solution and that I can realize. For example, 1+z^-1 is a function that I can implement without approximate it, for z^-1/2 is not the case. More I think about the subject, more I am troubled. I have some problem in understanding the meaning of a delay of z^-1/2. Here is an example that I don't understand. Imagine the following system : X(z) -> [Decimation by 2] -> X0(z) -> [z^-1/2] -> V0(z) X(z) -> [z^-1] -> X1(z) -> [Decimation by 2] -> V1(z) W(z) = V0(z)+V1(z) -> [Expander by 2] -> Y(z) which gives the following equations : X0(z) = 1/2 [X(z^1/2) + X(-z^1/2)] V0(z) = z^-1/2 X0(z) = 1/2 z^-1/2 [X(z^1/2) + X(-z^1/2)] X1(z) = z^-1 X(z) V1(z) = 1/2 [X1(z^1/2) + X1(-z^1/2)] = 1/2 z^-1/2 [X(z^1/2) - X(-z^1/2)] W(z) = V0(z) + V1(z) = z^-1/2 X(z^1/2) Y(z) = W(z^2) = z^-1 X(z) We find that y(n) is a delayed version of x(n). But y(n) is the output of an expander, which means that half of its samples are 0, so it cannot be a delayed version of x(n) (except the particular case where half of the sample of x(n) are 0 but no such hypothesis is made). So I don't understant what is wrong in this system ? Is it the z^-1/2 delay block that we cannot modelized like this ? I have implemented this system under Matlab using a FIR (sampling of delayed sinc) and Thiran filter. y(n) and x(n) are indeed correlated but it is not as good as the autocorrelation of x(n) (the peak is wider and lower than the one of the autocorrelation of x(n)).