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

I've run across a few web pages describing how to convert an arbitrary
FIR filter to a minimum phase variant by the use of cepstral methods:
e.g.
> wn = [ones(1,m); 2*ones((n+odd)/2-1,m) ; ones(1-rem(n,2),m);
>       zeros((n+od d)/2-1,m)];
> y = real(ifft(exp(fft(wn.*real(ifft(log(abs(fft(x)))))))));
etc.

I've tried this algorithm on a few windowed-sinc filters and it seems
to work...  much more straight-forward than trying to find the zeros
of a z-transform and move them inside.

Why does this technique work?  How does a cepstrum help generate a
minimum phase filter?


Thanks.
-- 
Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/ 
#include <canonical.disclaimer>        // only my own opinions, etc.

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

Hi Ron!

To your question, see below.

"Ronald H. Nicholson Jr." <r...@mauve.rahul.net> skrev i meddelandet
news:c3ahbu$5cp$1...@blue.rahul.net...
> I've run across a few web pages describing how to convert an arbitrary
> FIR filter to a minimum phase variant by the use of cepstral methods:
> e.g.
> > wn = [ones(1,m); 2*ones((n+odd)/2-1,m) ; ones(1-rem(n,2),m);
> >       zeros((n+od d)/2-1,m)];
> > y = real(ifft(exp(fft(wn.*real(ifft(log(abs(fft(x)))))))));
> etc.
>
> I've tried this algorithm on a few windowed-sinc filters and it seems
> to work...  much more straight-forward than trying to find the zeros
> of a z-transform and move them inside.
>
> Why does this technique work?  How does a cepstrum help generate a
> minimum phase filter?
>
I don't remember exactly becous it was so long time ago now. But the reason
why it works depends on that the cepstrum is a logarithmic function. And, if
I remember correctly the cepstrum has a properity of minimum phase. You have
to search in the theory
of Analytical Functions or Theory of Complex Functions, here you can find
correct answear.

Best regards,

Michael Numminen, M.Sc.E.E.

> Thanks.
> -- 
> Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/
> #include <canonical.disclaimer>        // only my own opinions, etc.

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

Michael Numminen wrote:

> Hi Ron!
> 

>>Why does this technique work?  How does a cepstrum help generate a
>>minimum phase filter?
>>
> 
> I don't remember exactly becous it was so long time ago now. But the reason
> why it works depends on that the cepstrum is a logarithmic function. And, if
> I remember correctly the cepstrum has a properity of minimum phase. You have
> to search in the theory
> of Analytical Functions or Theory of Complex Functions, here you can find
> correct answear.

Yeah, you can find a lot of recipes for its use on the net 
but nothing about the theory that justifies it.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

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

In article c...@enews2.newsguy.com, Bob Cain at
a...@arcanemethods.com wrote on 03/19/2004 00:03:

> Michael Numminen wrote:
> 
>>> Why does this technique work?  How does a cepstrum help generate a
>>> minimum phase filter?
>> 
>> I don't remember exactly becous it was so long time ago now. But the reason
>> why it works depends on that the cepstrum is a logarithmic function. And, if
>> I remember correctly the cepstrum has a properity of minimum phase. You have
>> to search in the theory
>> of Analytical Functions or Theory of Complex Functions, here you can find
>> correct answear.
> 
> Yeah, you can find a lot of recipes for its use on the net
> but nothing about the theory that justifies it.

i think it's in O&S.  do you want me to read and relearn it and try to post
a synopsis?  (i don't really want to but curiosity might get me.)

i s'pose it has something to do with the iFT(log(minphase filter)) being a
one-sided or "causal" function.

r b-j

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

In article <BC7FF47B.997D%r...@surfglobal.net>,
robert bristow-johnson  <r...@surfglobal.net> wrote:
>i think it's in O&S.

The book "Digital Signal Processing" by A.V. Oppenheim & R.W. Schafer ?
Is it worth buying a copy?  Any particular edition?


IMHO. YMMV.
-- 
Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/ 
#include <canonical.disclaimer>        // only my own opinions, etc.

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

"Michael Numminen" <m...@comhem.se> wrote in message
news:<ZTs6c.86740$d...@newsc.telia.net>...
> Hi Ron!
> 
> To your question, see below.
> 
> "Ronald H. Nicholson Jr." <r...@mauve.rahul.net> skrev i meddelandet
> news:c3ahbu$5cp$1...@blue.rahul.net...
> > I've run across a few web pages describing how to convert an arbitrary
> > FIR filter to a minimum phase variant by the use of cepstral methods:
> > e.g.
> > > wn = [ones(1,m); 2*ones((n+odd)/2-1,m) ; ones(1-rem(n,2),m);
> > >       zeros((n+od d)/2-1,m)];
> > > y = real(ifft(exp(fft(wn.*real(ifft(log(abs(fft(x)))))))));
> > etc.
> >
> > I've tried this algorithm on a few windowed-sinc filters and it seems
> > to work...  much more straight-forward than trying to find the zeros
> > of a z-transform and move them inside.
> >
> > Why does this technique work?  How does a cepstrum help generate a
> > minimum phase filter?
> >
> I don't remember exactly becous it was so long time ago now. But the reason
> why it works depends on that the cepstrum is a logarithmic function. And, if
> I remember correctly the cepstrum has a properity of minimum phase. 

I read some stuff not long ago about the cepstrum. Most of it was based 
on chapter 7 in Oppenheim and Schafer (the 1975 book), but also some 
of the journal literature (search for J. Tribolet on IEEExplore). 
Some of the articles I read are listed at the end of this post.

The problem with the cepstrum is that the complex logarithm is ambiguous. 
Write a complex number z on polar form as 

   z = r*exp(i*phi+ n*2pi), r=|z|, n=...,-2,-1,0,1,2,...

and define the complex logaritm as 

  Log (z) = log(r)+ i(phi + n*2pi).

Computing the cepstrum involves computing Log(X(w)), and there are 
two problems with that:

- How does one unwrap the phase of X(w)?
- How does one deal with stop-bands in X(w) where |X(w)| -> 0?

The answer of these questions are not obvious, and it appears that 
considerable effort has gone into resolving them. 

Some references I have seen impose assumptions on the cepstrum, 
the sequence to be produced by this computation. If one requires the 
cepstrum to be real-valued, it follows that log|X(w)| and 
phase(X(w)) are a Hilbert transform pair. That, in turn, requires 
Log(X(w)) to be an analytic function in z domain. 

This requirement does, if I have understood things correctly, wreck 
all sorts of havoc woth the signal. To get an analytic Log(X(w)), 
the phase of (X(w)) continuous, which means it must be periodic
around the unit circle in Z domain. This is a self-imposed restriction 
that is caised by us wanting a real-valued cepstrum. But the consequence 
is that any time sequence that is re-generated from the cepstrum
is noncausal. For my intended applicaytion, pulse deconvolution, 
this meant that the reflection serquence which is represented as 
a set of time-shifted delta pulses, can not be represented accurately, 
and the method does not appear to be worth the considerable effort 
needed to get the cepstrum processing to work. 

[DISCLAIMER: I never tested the cepstrum processing with my application. 
I only got as far as reckognizing all the issues listed here, and decided 
that there was too much uncertainty and too much work involved, and thus 
decided to leave the cepstrum as a curiosity and little more than that.]

>You have
> to search in the theory
> of Analytical Functions or Theory of Complex Functions, here you can find
> correct answear.

That's right. I lost interest in these things when I had to look up 
"Poisson's Kernel", which seems to be intimately related to the 
Hilbert transform, and found that it was just barely mentioned 
on the latest pages of the standard book on complex function theory by 
Churchil and Brown. 

For what it's worth, 

Rune

[1] Oppenheim, Kopec and Tribolet: "Signal Analysis by Homomorphic
    Prediction". IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-24(4)
    August 1976, p 327.
 
[2] Tribolet: "A New Phase Unwrapping Algorithm".
    IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-25(2)
    April 1977, p 170.
 
[3] Bonzanigo: "An Improvement to Tribolet's Phase Unwrapping Algorithm".
    IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-26(1)
    February 1978, p 104.
 
[4] Tribolet: "Applications of Short-Time Homomorphic Signal Analysis 
    to Seismic Wavelet Estimation". IEEE Trans. Acoust. Sp. Sig. Proc., 
    Vol ASSP-26(4) August 1978, p 343.
 
[5] Schroeder: "Direct (Nonrecursive) Relations Between Cepstrum and
    Predictor Coefficients". IEEE Trans. Acoust. Sp. Sig. Proc., 
    Vol ASSP-29(2) April 1981, p 297.
 
[6] Bednar and Watt: "Calculating the Complex Cepstrum Without 
    Phase Unwrapping or Integration". IEEE Trans. Acoust. Sp. Sig. Proc., 
    Vol ASSP-33(4) August 1985, p 1014.

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

In article c3ea5c$lb6$1...@blue.rahul.net, Ronald H. Nicholson Jr. at
r...@mauve.rahul.net wrote on 03/19/2004 03:14:

> In article <BC7FF47B.997D%r...@surfglobal.net>,
> robert bristow-johnson  <r...@surfglobal.net> wrote:
>> i think it's in O&S.
> 
> The book "Digital Signal Processing" by A.V. Oppenheim & R.W. Schafer ?

the 1975 version has that title.  the 1989 version is titled "Discrete-Time
Signal Processing", *and* i've seen a newer version with an additional
author:

http://www.amazon.com/exec/obidos/ISBN%3D0137549202/

> Is it worth buying a copy?  Any particular edition?

*everyone* doing DSP and wanting to deal with and understand algorithms
should have a copy of *some* O&S, in my opinion.

r b-j

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

robert bristow-johnson wrote:

>>Yeah, you can find a lot of recipes for its use on the net
>>but nothing about the theory that justifies it.
> 
> 
> i think it's in O&S.  do you want me to read and relearn it and try to post
> a synopsis?  (i don't really want to but curiosity might get me.)

That would be cool.  I may not be able to understand it but 
it would be nice to try and would be a good thing to have in 
our FAQ.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

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

robert bristow-johnson <r...@surfglobal.net> wrote in message
news:<BC808AC0.99B3%r...@surfglobal.net>...
> In article c3ea5c$lb6$1...@blue.rahul.net, Ronald H. Nicholson Jr. at
> r...@mauve.rahul.net wrote on 03/19/2004 03:14:
> 
> > In article <BC7FF47B.997D%r...@surfglobal.net>,
> > robert bristow-johnson  <r...@surfglobal.net> wrote:
> >> i think it's in O&S.
> > 
> > The book "Digital Signal Processing" by A.V. Oppenheim & R.W. Schafer ?
> 
> the 1975 version has that title.  the 1989 version is titled "Discrete-Time
> Signal Processing", *and* i've seen a newer version with an additional
> author:
> 
> http://www.amazon.com/exec/obidos/ISBN%3D0137549202/
> 
> > Is it worth buying a copy?  Any particular edition?
> 
> *everyone* doing DSP and wanting to deal with and understand algorithms
> should have a copy of *some* O&S, in my opinion.
> 
> r b-j

Yes and no... The one O&S book that really stands out among all the other 
books on DSP, is the 1975 book. I've seen the 1989 book, and it isn't 
very different from, say, Proakis and Manolakis. Given the choise between 
O&S 1989 and P&M, I choose P&M since that's the book I already know,
and O&S 1989 is almost similar. I guess there must be some sort of 
"formula" for DSP textbook authors, that everybody seem to conform to. 
With some notable exceptions. 

[ Hey Rick, if you have the time to read comp.dsp these days: When is 
your 2nd edition out? ]

O&S 1975 is a completely different story. It was an early book, and the 
"book formula" was not yet established at the time. That's the reason why 
the book has more than historical interest. It presents standard material 
from what we who learned DSP from later books, would call non-standard 
viewpoints. And it contains material other books don't contain. Like 
the formal approach to the inverse FT, and the cepstrum.

Rune

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

Rune:

I didn't completely understand it while in DSP at MIT, but I got the gist
that Cepstrum analysis is the core of homomorphic deconvolution, which has
many real-world benefits such as recovering original data from scratched
LPs, etc. Thus, though I have never used it in my work as an EE, I think it
*may* be an important part of signal processing that ought not lightly be
dismissed as "a curiostity". Others could comment much better than I--my
career is a hardware designer and DSP coder, not a DSP theorist
(unfortunately).

Jim

"Rune Allnor" <a...@tele.ntnu.no> wrote in message
news:f...@posting.google.com...
> "Michael Numminen" <m...@comhem.se> wrote in message
news:<ZTs6c.86740$d...@newsc.telia.net>...
> > Hi Ron!
> >
> > To your question, see below.
> >
> > "Ronald H. Nicholson Jr." <r...@mauve.rahul.net> skrev i meddelandet
> > news:c3ahbu$5cp$1...@blue.rahul.net...
> > > I've run across a few web pages describing how to convert an arbitrary
> > > FIR filter to a minimum phase variant by the use of cepstral methods:
> > > e.g.
> > > > wn = [ones(1,m); 2*ones((n+odd)/2-1,m) ; ones(1-rem(n,2),m);
> > > >       zeros((n+od d)/2-1,m)];
> > > > y = real(ifft(exp(fft(wn.*real(ifft(log(abs(fft(x)))))))));
> > > etc.
> > >
> > > I've tried this algorithm on a few windowed-sinc filters and it seems
> > > to work...  much more straight-forward than trying to find the zeros
> > > of a z-transform and move them inside.
> > >
> > > Why does this technique work?  How does a cepstrum help generate a
> > > minimum phase filter?
> > >
> > I don't remember exactly becous it was so long time ago now. But the
reason
> > why it works depends on that the cepstrum is a logarithmic function.
And, if
> > I remember correctly the cepstrum has a properity of minimum phase.
>
> I read some stuff not long ago about the cepstrum. Most of it was based
> on chapter 7 in Oppenheim and Schafer (the 1975 book), but also some
> of the journal literature (search for J. Tribolet on IEEExplore).
> Some of the articles I read are listed at the end of this post.
>
> The problem with the cepstrum is that the complex logarithm is ambiguous.
> Write a complex number z on polar form as
>
>    z = r*exp(i*phi+ n*2pi), r=|z|, n=...,-2,-1,0,1,2,...
>
> and define the complex logaritm as
>
>   Log (z) = log(r)+ i(phi + n*2pi).
>
> Computing the cepstrum involves computing Log(X(w)), and there are
> two problems with that:
>
> - How does one unwrap the phase of X(w)?
> - How does one deal with stop-bands in X(w) where |X(w)| -> 0?
>
> The answer of these questions are not obvious, and it appears that
> considerable effort has gone into resolving them.
>
> Some references I have seen impose assumptions on the cepstrum,
> the sequence to be produced by this computation. If one requires the
> cepstrum to be real-valued, it follows that log|X(w)| and
> phase(X(w)) are a Hilbert transform pair. That, in turn, requires
> Log(X(w)) to be an analytic function in z domain.
>
> This requirement does, if I have understood things correctly, wreck
> all sorts of havoc woth the signal. To get an analytic Log(X(w)),
> the phase of (X(w)) continuous, which means it must be periodic
> around the unit circle in Z domain. This is a self-imposed restriction
> that is caised by us wanting a real-valued cepstrum. But the consequence
> is that any time sequence that is re-generated from the cepstrum
> is noncausal. For my intended applicaytion, pulse deconvolution,
> this meant that the reflection serquence which is represented as
> a set of time-shifted delta pulses, can not be represented accurately,
> and the method does not appear to be worth the considerable effort
> needed to get the cepstrum processing to work.
>
> [DISCLAIMER: I never tested the cepstrum processing with my application.
> I only got as far as reckognizing all the issues listed here, and decided
> that there was too much uncertainty and too much work involved, and thus
> decided to leave the cepstrum as a curiosity and little more than that.]
>
> >You have
> > to search in the theory
> > of Analytical Functions or Theory of Complex Functions, here you can
find
> > correct answear.
>
> That's right. I lost interest in these things when I had to look up
> "Poisson's Kernel", which seems to be intimately related to the
> Hilbert transform, and found that it was just barely mentioned
> on the latest pages of the standard book on complex function theory by
> Churchil and Brown.
>
> For what it's worth,
>
> Rune
>
> [1] Oppenheim, Kopec and Tribolet: "Signal Analysis by Homomorphic
>     Prediction". IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-24(4)
>     August 1976, p 327.
>
> [2] Tribolet: "A New Phase Unwrapping Algorithm".
>     IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-25(2)
>     April 1977, p 170.
>
> [3] Bonzanigo: "An Improvement to Tribolet's Phase Unwrapping Algorithm".
>     IEEE Trans. Acoust. Sp. Sig. Proc., Vol ASSP-26(1)
>     February 1978, p 104.
>
> [4] Tribolet: "Applications of Short-Time Homomorphic Signal Analysis
>     to Seismic Wavelet Estimation". IEEE Trans. Acoust. Sp. Sig. Proc.,
>     Vol ASSP-26(4) August 1978, p 343.
>
> [5] Schroeder: "Direct (Nonrecursive) Relations Between Cepstrum and
>     Predictor Coefficients". IEEE Trans. Acoust. Sp. Sig. Proc.,
>     Vol ASSP-29(2) April 1981, p 297.
>
> [6] Bednar and Watt: "Calculating the Complex Cepstrum Without
>     Phase Unwrapping or Integration". IEEE Trans. Acoust. Sp. Sig. Proc.,
>     Vol ASSP-33(4) August 1985, p 1014.

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