Hi there. Just a little status update how that integerization is coming along. I am trying to limit myself to 32 bit arithmetics. That means not using any __int64 or long long datatypes at any point. I have now replaced all steps up to including the estimation of the LPC filter coefficients with integer code. That is about a quarter of the total work completed, I would say. One problem that i encountered is the high dynamic range of the results of the autocorrelation function. Think 96db squared. -> 192 dB ;) That is not very desirable when used as input for further processing. I have most precision issues pretty well under control until before I enter the Levinson Durbin algorithm. The Levinson Durbin routine is where things go bad. I am currently losing 2 dB of SNR when I apply the integerized version. The algorithm seems very sensitive to rounding and precision issues. Is there a way to alter the algorithm or to condition the input values and intermediate results such that the outcome is not quite as sensitive to computation with integer arithmetics? Do we have some of the maths/signal processing gurus here who could provide some clues? I may decide to postpone "fixing" this routine and proceed with my integeization quest. Just like most politicians do: Leave a mess and quietly return to business. ;) Christian --- >8 ---- List archives: http://www.xiph.org/archives/ Ogg project homepage: http://www.xiph.org/ogg/ To unsubscribe from this list, send a message to 'speex-dev-request@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
Hey.
The problems with Levinson -type algorithms and integrization are
well known. Older codecs have usually solved the problem by using Schur
decomposition for inversion of the autocorrelation matrix instead of
Levinson. Another solution sometimes used is to use double precision -
in this case you probably could code some pseudo-64bit implementation
(using only 32bit commands), but that can become quite complex. I would
recommend Schur. Both solutions require naturally more computations than
Levinson, but that's what you get :)
If you're unfamiliar with Schur I'd be glad to help, or you can
check out any standard matrix computation manual, e.g. Golub, "Matrix
comuptations".
cheers,
Tom Bäckström
Laboratory of Acoustics and Audio Signal Processing
Helsinki University of Technology
http://www.acoustics.hut.fi/~tbackstr/
Christian Buchner wrote:> Hi there.
>
> Just a little status update how that integerization is coming along.
> I am trying to limit myself to 32 bit arithmetics. That means
> not using any __int64 or long long datatypes at any point.
>
> I have now replaced all steps up to including the estimation of
> the LPC filter coefficients with integer code. That is about a
> quarter of the total work completed, I would say.
>
> One problem that i encountered is the high dynamic range of the
> results of the autocorrelation function. Think 96db squared.
> -> 192 dB ;) That is not very desirable when used as input for
> further processing.
>
> I have most precision issues pretty well under control until before
> I enter the Levinson Durbin algorithm. The Levinson Durbin routine
> is where things go bad. I am currently losing 2 dB of SNR when I
> apply the integerized version. The algorithm seems very sensitive
> to rounding and precision issues.
>
> Is there a way to alter the algorithm or to condition the input
> values and intermediate results such that the outcome is not quite
> as sensitive to computation with integer arithmetics?
> Do we have some of the maths/signal processing gurus here who
> could provide some clues?
>
> I may decide to postpone "fixing" this routine and proceed
> with my integeization quest. Just like most politicians do:
> Leave a mess and quietly return to business. ;)
>
> Christian
>
> --- >8 ----
> List archives: http://www.xiph.org/archives/
> Ogg project homepage: http://www.xiph.org/ogg/
> To unsubscribe from this list, send a message to
'speex-dev-request@xiph.org'
> containing only the word 'unsubscribe' in the body. No subject is
needed.
> Unsubscribe messages sent to the list will be ignored/filtered.
>
--- >8 ----
List archives: http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to
'speex-dev-request@xiph.org'
containing only the word 'unsubscribe' in the body. No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.
Tom Bäckström wrote:> Hey. > > The problems with Levinson -type algorithms and integrization are > well known. Older codecs have usually solved the problem by using > Schur decomposition for inversion of the autocorrelation matrix > instead of Levinson. Another solution sometimes used is to use double > precision - in this case you probably could code some pseudo-64bit > implementation (using only 32bit commands), but that can become quite > complex. I would recommend Schur. Both solutions require naturally > more computations than Levinson, but that's what you get :) > If you're unfamiliar with Schur I'd be glad to help, or you can > check out any standard matrix computation manual, e.g. Golub, "Matrix > comuptations".As you said, the Schur recursion is the standard trick in most vocoders, so you can find an implementation in most vocoder source code. Take care not to copy an implementation that has restrictions, though. Regards, Steve <p><p>--- >8 ---- List archives: http://www.xiph.org/archives/ Ogg project homepage: http://www.xiph.org/ogg/ To unsubscribe from this list, send a message to 'speex-dev-request@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.
Le ven 27/06/2003 à 05:10, Christian Buchner a écrit :> Hi there. > > Just a little status update how that integerization is coming along. > I am trying to limit myself to 32 bit arithmetics. That means > not using any __int64 or long long datatypes at any point.If possible, it would be nice to restrict ourselves to 32x32->64 multiplies, so the code could run on almost any architecture.> One problem that i encountered is the high dynamic range of the > results of the autocorrelation function. Think 96db squared. > -> 192 dB ;) That is not very desirable when used as input for > further processing.One thing to note here is that it is only the "relative values" that count for the auto-correlation. That is, you can normalize it by autocor[0] and get the same results. That should greatly reduct the dynamic range. BTW, once normalized by autocor[0], all the auto-correlation coef. are in the [0,1] range. Jean-Marc -- Jean-Marc Valin, M.Sc.A. LABORIUS (http://www.gel.usherb.ca/laborius) Université de Sherbrooke, Québec, Canada <p> -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 190 bytes Desc: Ceci est une partie de message numériquement signée Url : http://lists.xiph.org/pipermail/speex-dev/attachments/20030627/d934f823/signature-0001.pgp
>> Just a little status update how that integerization is coming along. >> I am trying to limit myself to 32 bit arithmetics. That means >> not using any __int64 or long long datatypes at any point.> If possible, it would be nice to restrict ourselves to 32x32->64 > multiplies, so the code could run on almost any architecture.Right now I can choose from 2 implementations (with a #define). a) one that uses 64 bit intermediate results b) one that restricts itself to 32 bit precision on intermediates. However the two factors going into the multiplications will be normalized (with right shifts) such that the intermediate cannot overflow. Interestingly enough, there is no significant difference in performance (SNR) when switching between a) and b).> One thing to note here is that it is only the "relative values" that > count for the auto-correlation. That is, you can normalize it by > autocor[0] and get the same results.Thanks, that might be very helpful. --- >8 ---- List archives: http://www.xiph.org/archives/ Ogg project homepage: http://www.xiph.org/ogg/ To unsubscribe from this list, send a message to 'speex-dev-request@xiph.org' containing only the word 'unsubscribe' in the body. No subject is needed. Unsubscribe messages sent to the list will be ignored/filtered.