Computing Line Spectrum Pairs

Line spectrum pairs are a technique used in compression of speech and other audio signals. The two papers listed below describe an algorithm I developed for computing the LSF's with a fairly simple program. In brief, we start with an all-pole model of the signal spectrum [A(z)]. We the form even and odd polynomials P_e(z) and P_o(z). These polynomials have roots on the unit circle, so the angles of the roots completely characterize them. The general procedure for computing the LSF's is as follows:

Compute P_e(z) and P_o(z), and divide out extraneous roots at +1 and -1.
Project the roots onto the real axis, resulting in real polynomials whose roots are real, distinct, and lie in the range -1 to +1.
Find the roots of these polynomials.
Take the inverse cosine of each root, to get the angle of the corresponding LSF.

The two papers describe efficient ways to perform steps 2 and 3 of this process. In the first paper, I show that the following subroutine implements the reduction of step 2. It is based on recursive application of the properties of the Chebyshev polynomials. Compared to other published methods, it eliminates multiplications (except for a trivial multiplication by 2), and obvously allows a very simple implementation.
static void cheby2(double *g, int ord) {
int i, j;

        for(i=2; i<= ord; i++) {
                for(j=ord; j > i; j--) {
                        g[j-2] -= g[j];           add++;
                }
                g[j-2] -= 2.0*g[j];           mpy++; add++;
        }
}

The second paper looks at algorithms for computing the roots of the real polynomials. Historically, people have avoided the use of traditional rootfinding algorithms, because of concerns about convergence. This primary contribution of this paper is to point out that these polynomials have very nice properties that make rootfinding algorithms work very well. Specifically, it shows that
A conventional Newton's method iteration is guaranteed to converge monotonically to the most positive or most negative root if the starting point is properly chosen.
An accelerated variant of Newton's method will converge with fewer iterations, and still offers guaranteed convergence.

Copyright information.
The publisher, IEEE, requires the following copyright notice to be posted. This copyright applies to both papers listed below. For more information, check the IEEE policy (6.2.10).

"© 1999 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE."

J. Rothweiler, "On Polynomial Reduction in the Computation of LSP Frequencies," to be published in IEEE Transactions on Speech and Audio Processing, September, 1999. lsf.ps (79k)
J. Rothweiler, "A Rootfinding Algorithm for Line Spectral Frequencies," Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP-99), March 15-19, 1999, Phoenix, AZ, USA, pp. II-661 - II-664. Available as PDF: ic992022.pdf (76k)

A test program is available here:a2lsp.c(8k) Depending on your browser, you may need to shift-click or right-click the link to download the file.