Code for cepstrum

Hi. I need to calculate the cepstrum of a signal. I understand that the
cepstrum of a signal is the fourier transform of the log of the fourier
transform of a signal. I can easily calculate each of these operations
individually, using the fftw3 library. However I have to unwrap the
phase of the first FT, and I don't yet know how to do this.

Can anyone either (i) point me in the direction of a freely available
cepstrum calculating library, or phase unwrapping library usable on
Linux, or (ii) convince me that phase unwrapping of a fourier transform
of a signal is easy and with a bit of study I'll have no trouble doing
it?

Cheers,

Ross-c

Ross -- it's the complex cepstrum that you need, right?

I ask because "cepstrum" is commonly used to refer to the FT of the log
of the power spectrum, which is a bit simpler to compute -- no phase
involved.

cheers,
  jerry wolf

Thanks for the answer.

(i) Hmmm..... I have to review some sources on the use of the cepstrum
in pitch detection before I can say whether I need the complex cepstrum
or not. The only source I have within arm's reach is Hess's 1983 book
on Pitch Detection. This sort of suggests that the FT of the log of the
power spectrum is what is used. However I'm confused in that the
Wikipedia article on the cepstrum says that the cepstrum is the FT of
the log of the FT, and that it is a common mistake to claim that the
cepstrum is the *INVERSE* FT of the log of the FT. Hess describes the
cepstrum as being the INVERSE FT of the power spectrum. So, I need to
look into this further. But in reality since I'm currently in an
"implement *everything*" mode, I'll probably end up implementing both.

(ii) I was presuming that unwrapping the phase of a FT was a much more
complex operation than unwrapping phase shift in FIR filters. After
running into a DSP specialist colleague in the corridor, it appears
that it's easy. I didn't realise that a discontinuity in the phase
spectrum of a FT was just a discontinuity in phase between two adjacent
FT (frequency) bins. So, I'm not sure if I need to unwrap phase or not.
But if I need to, it looks like I can with no problem.

Cheers,

Ross-c

As I suspected.  One doesn't need the complex cepstrum unless one is
going to reconstitute the signal.  For pitch estimation, you want the
real cepstrum, commonly called just the  cepstrum.  See Rabiner &
Schafer, secs. 7.1.2, 7.3.

Ross Clement (Email address invalid - do not use) wrote:
> (i) Hmmm..... I have to review some sources on the use of the cepstrum
> in pitch detection before I can say whether I need the complex cepstrum
> or not. The only source I have within arm's reach is Hess's 1983 book
> on Pitch Detection. This sort of suggests that the FT of the log of the
> power spectrum is what is used. However I'm confused in that the
> Wikipedia article on the cepstrum says that the cepstrum is the FT of
> the log of the FT, and that it is a common mistake to claim that the
> cepstrum is the *INVERSE* FT of the log of the FT. Hess describes the
> cepstrum as being the INVERSE FT of the power spectrum. So, I need to
> look into this further. But in reality since I'm currently in an
> "implement *everything*" mode, I'll probably end up implementing both.

The difference between an FFT and an IFFT after the log is only a
constant, which I think only affects where you set the thresholds when
doing pitch likelyhood estimation.

What I would like to know is if the literature recommends using
the real part of a complex FFT or a magnitude FFT (power spectrum),
both of the log of a magnitude FFT, when doing pitch estimation.


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M

Jerry Wolf wrote:
> As I suspected.  One doesn't need the complex cepstrum unless one is
> going to reconstitute the signal.

I've read about reconstituting a signal from its real cepstrum in order
to create minimum-phase filters out of the signal.  The phase of
the spectrum is lost and somehow thus minimized when reconstituted.
(Perhaps a chapter in O&S 1975 explains why.)


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M

For pitch estimation it is common to take the log of the power spectrum
which is obtained by summing the squares of the real and imaginary
outputs of the first FFT.  There is no need to square root the sum of
squares, as it is more efficient to adjust after the log.

John

"Jerry Wolf" <sl_jerry1@hotmail.com> wrote in message
news:1134570017.351854.16430@g49g2000cwa.googlegroups.com...
> Ross -- it's the complex cepstrum that you need, right?
>
> I ask because "cepstrum" is commonly used to refer to the FT of the log
> of the power spectrum, which is a bit simpler to compute -- no phase
> involved.
>
> cheers,
>   jerry wolf
>
Watch out for a bias which  esists after you take logs. This only involves
the first Cepstrum coefficient C0 and I believe the bias is Eulers number
downwards (negative). You have to add Eulers number to unbias.

Ing

I don't know if this helps at all.  Here is an older message I wrote to Rune 
Allnor:

Fred

***************************

I made some diagrams out of the O&S first ed. book and substituted "s" for 
the "square" operator.

The "Convolutional System" is what you're dealing with.  What interests me 
below is that the Z Transforms go forward/inverse (in that order) in both 
Figures 5 and 6.  It's because in the input case the first transformation is 
from convolutional to multiplicative and in the output case the second 
transformation is from multiplicative to convolutional.

Of course an L linear stage is implied between Figures 5 and 6.

I guess this simply says that a multiplicative system can directly be dealt 
with using complex log and complex exponential but a convolutional system 
needs to be:
1) transformed first so that it becomes a multiplicative system.  Then we 
can do the log operation.
2) transformed back so that it becomes an additive/linear system. Then we 
can apply a linear filter.
3) transformed next so that it becomes a multiplicative system again.  Then 
we can apply the exponent operation.
4) transformed back so that it becomes a convolutional system once more - in 
other words getting back to the domain of interest.

I'm used to doing linear filtering in the frequency domain using 
multiplication just as well as doing it in the time domain with convolution. 
So, it appears that the middle transform operation pair is unnecessary if 
you do the filtering in the frequency domain.  Why bother computing the 
complex cepstrum at all?  Am I missing something here.  Oh, they probably 
call that a "trick" later on!  I just haven't read enough.  Note in Fig 1 
that they are applying a linear filter in the time domain and are using the 
operational symbols "+" for input and output even though it's a 
convolutional process in the time domain.  The "+"s mean that the inputs add 
and the outputs add as in superposition.

I'm sure you've already gone through all this and that's why you're looking 
at phase unwrapping programs.

       s           +      +       +      +           o
       +-----------+      +-------+      +-----------+
 x(n)  |           | x^(n)|       | y^(n)|           | y(n)
 ----->|    Ds     |----->|   L   |----->|  Ds^-1    |----->
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

      Fig 1 Canonic Representation of homomorphic systems


       x           +      +       +      +           x
       +-----------+      +-------+      +-----------+
 x(n)  |  complex  |      |       |      |  complex  | y(n)
 ----->|    log    |----->|   L   |----->|exponential|----->
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

      Fig 2 Multiplicative System with Ds = Complex Log


       *           +      +       +      +           *
       +-----------+      +-------+      +-----------+
 x(n)  |           | x^(n)|       |y^(n) |           | y(n)
 ----->|    D*     |----->|   L   |----->|    D*^-1  |----->
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

       Fig 3 Convolutional System Abstract Representation


       *           +      +       +      +           *
       +-----------+      +-------+      +-----------+
 X(z)  |  complex  | X^(z)|       |Y^(z) |  complex  | Y(z)
 ----->|    log    |----->|   L   |----->|    exp    |----->
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

      Fig 4 Convolutional System Z Transform Domain Representation
            as a Canonic Homomorphic System

       *           x      x       +      +           +
       +-----------+      +-------+      +-----------+
 x(n)  |           | X(z) |complex|X^(z) |           | x^(n)
 ----->|   z[]     |----->|  log  |----->|    z^-1[] |-----> complex 
cepstrum > to "L"
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

      Fig 5 Convolutional System Representation for D* as in Fig 3

       +           +      +       x      x           *
       +-----------+      +-------+      +-----------+
 y^(n) |           | Y^(z)|complex| Y(z) |           | y(n)
 ----->|   z[]     |----->|  exp  |----->|   z^-1[]  |----->
       |           |      |       |      |           |
       +-----------+      +-------+      +-----------+

      Fig 6 Convolutional System Representation for D*^-1 as in Fig 3 

Thanks to everyone who replied on this thread. Given the time being
just before 5pm on a Friday, I won't be trying to write any cepstrum
code until Monday. But your postings will be very helpful when I get
around to doing it.

Cheers,

Ross-c