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.
Minimum phase filter design using cepstrum methods?
Started by ●March 17, 2004
Reply by ●March 18, 20042004-03-18
Hi Ron! To your question, see below. "Ronald H. Nicholson Jr." <rhn@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.
Reply by ●March 19, 20042004-03-19
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
Reply by ●March 19, 20042004-03-19
In article c3duuq22sje@enews2.newsguy.com, Bob Cain at arcane@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
Reply by ●March 19, 20042004-03-19
In article <BC7FF47B.997D%rbj@surfglobal.net>, robert bristow-johnson <rbj@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.
Reply by ●March 19, 20042004-03-19
"Michael Numminen" <michael.numminen@comhem.se> wrote in message news:<ZTs6c.86740$dP1.248790@newsc.telia.net>...> Hi Ron! > > To your question, see below. > > "Ronald H. Nicholson Jr." <rhn@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.
Reply by ●March 19, 20042004-03-19
In article c3ea5c$lb6$1@blue.rahul.net, Ronald H. Nicholson Jr. at rhn@mauve.rahul.net wrote on 03/19/2004 03:14:> In article <BC7FF47B.997D%rbj@surfglobal.net>, > robert bristow-johnson <rbj@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
Reply by ●March 19, 20042004-03-19
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
Reply by ●March 20, 20042004-03-20
robert bristow-johnson <rbj@surfglobal.net> wrote in message news:<BC808AC0.99B3%rbj@surfglobal.net>...> In article c3ea5c$lb6$1@blue.rahul.net, Ronald H. Nicholson Jr. at > rhn@mauve.rahul.net wrote on 03/19/2004 03:14: > > > In article <BC7FF47B.997D%rbj@surfglobal.net>, > > robert bristow-johnson <rbj@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-jYes 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
Reply by ●March 22, 20042004-03-22
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" <allnor@tele.ntnu.no> wrote in message news:f56893ae.0403190133.6b99bebb@posting.google.com...> "Michael Numminen" <michael.numminen@comhem.se> wrote in messagenews:<ZTs6c.86740$dP1.248790@newsc.telia.net>...> > Hi Ron! > > > > To your question, see below. > > > > "Ronald H. Nicholson Jr." <rhn@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 thereason> > 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 canfind> > 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.
