Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

>> 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).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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]).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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.).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

>> 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

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

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)).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.