Heisenberg's microscope

2013-11-18T13:45:50Z

31.19.223.83: Added "2" to the equation for :<math>\Delta p_x arccording to the source [5].

'''Line spectral pairs''' ('''LSP''') or '''line spectral frequencies''' ('''LSF''') are used to represent [[linear predictive coding|linear prediction coefficients]] (LPC) for transmission over a channel. LSPs have several properties (e.g. smaller sensitivity to quantization noise) that make them superior to direct quantization of LPCs. For this reason, LSPs are very useful in [[speech coding]]. LSP representation was developed by [[Fumitada Itakura]] in the 1970s.<ref>See e.g. http://www.work.caltech.edu/~ling/pub/icslp98lsp.pdf</ref>

== Mathematical foundation ==
The LP [[polynomial]] <math>A(z) = 1- \sum_{k=1}^p a_k z^{-k}</math> can be expressed as <math>A(z) = 0.5[P(z) + Q(z)]</math>, where:
* <math>P(z) = A(z) + z^{-(p+1)}A(z^{-1})</math>
* <math>Q(z) = A(z) - z^{-(p+1)}A(z^{-1})</math>

By construction, ''P'' is a '''[[palindromic polynomial]]''' and ''Q'' an '''antipalindromic polynomial'''; physically ''P''(''z'') corresponds to the vocal tract with the [[glottis]] closed and ''Q''(''z'') with the [[glottis]] open.<ref>http://svr-www.eng.cam.ac.uk/~ajr/SpeechAnalysis/node51.html#SECTION000713000000000000000 Tony Robinson: Speech Analysis</ref> It can be shown that:
* The [[zero of a function|roots]] of ''P'' and ''Q'' lie on the [[unit circle]] in the complex plane.
* The roots of ''P'' alternate with those of ''Q'' as we travel around the circle.
* As the coefficients of ''P'' and ''Q'' are real, the roots occur in [[Complex conjugate root theorem|conjugate pairs]]

The Line Spectral Pair representation of the LP polynomial consists simply of the location of the roots of ''P'' and ''Q'' (i.e. <math>\omega</math> such that <math>z = e^{i\omega}, P(z) = 0</math>). As they occur in pairs, only half of the actual roots (conventionally between 0 and <math>\pi</math>) need be transmitted. The total number of coefficients for both ''P'' and ''Q'' is therefore equal to ''p'', the number of original LP coefficients (not counting <math>a_0=1</math>).

A common algorithm for finding these<ref>e.g. lsf.c in http://www.ietf.org/rfc/rfc3951.txt</ref> is to evaluate the polynomial at a sequence of closely spaced around the unit circle, observing when the result changes sign; when it does a root must lie between the points tested. Because the roots of ''P'' are interspersed with those of ''Q'' a single pass is sufficient to find the roots of both polynomials.

To convert back to LPCs, we need to evaluate
<math>A(z) = 0.5[P(z)+ Q(z)]</math>
by "clocking" an impulse through it ''N'' times (order of the filter), yielding the original filter, ''A''(''z'').

== Properties ==

Line spectral pairs have several interesting and useful properties. When the roots of ''P''(''z'') and ''Q''(''z'') are interleaved, stability of the filter is ensured if and only if the roots are monotonically increasing. Moreover, the closer two roots are, the more resonant the filter is at the corresponding frequency. Because LSPs are not overly sensitive to quantization noise and stability is easily ensured, LSP are widely used for quantizing LPC filters. Line spectral frequencies can be interpolated.

==See also==
* [[Log Area Ratios]]

== Sources ==
* [http://speex.org/docs/ Speex manual] and source code (lsp.c)
* [http://www.ece.mcgill.ca/~pkabal/papers/1986/Kabal1986.pdf "The Computation of Line Spectral Frequencies Using Chebyshev Polynomials"]/ P. Kabal and R. P. Ramachandran. IEEE Trans. Acoustics, Speech, Signal Processing, vol. 34, no. 6, pp. 1419–1426, Dec. 1986.
Includes an overview in relation to LPC.
* [http://www.dspcsp.com/pdf/lsp.pdf "Line Spectral Pairs" chapter] as an online excerpt (pdf) / "Digital Signal Processing - A Computer Science Perspective" (ISBN 0-471-29546-9) [[Jonathan Stein]].

== References ==
{{Reflist}}

{{Compression Methods}}

[[Category:Lossy compression algorithms]]
[[Category:Digital signal processing]]

formulasearchengine - User contributions [en]

Heisenberg's microscope