Algoritme alfa max mes beta min

El lloc geomètric dels punts que donen el mateix valor en l'algoritme, per a diferents valors d'alfa i beta

L'algoritme Alfa max més Beta min és una aproximació llineal d'alta velocitat de la raïl quadrada de la suma de dos quadrats. La raïl quadrada de la suma de dos quadrats, també coneguda com suma pitagórico, és una funció útil perque troba l'hipotenusa d'un triàngul rectàngul donades les llongituts dels dos costats, la norma d'un vector 2-D o la magnitut $|z|=\sqrt{a^2+b^2}$ d'un número complex z = a + bi donades les parts real i imaginària .

L'algoritme evita realisar les operacions de raïl quadrada i cúbica, i en el seu lloc utilisa operacions simples com a comparació, multiplicació i suma. Algunes eleccions dels paràmetros α i β de l'algoritme permeten que l'operació de multiplicació es reduïxca a un simple canvi de dígits binaris que és particularment adequat per a l'implementació en circuits digitals d'alta velocitat.

L'aproximació s'expressa com

$|z|=\alpha 𝐌𝐚𝐱+\beta 𝐌𝐢𝐧,$

on $𝐌𝐚𝐱$ és el valor absolut màxim de a i b, i $𝐌𝐢𝐧$ és el valor absolut mínim de a i b.

Per a l'aproximació més propenca, els valors òptims per a $\alpha$ i $\beta$ són ${\alpha }_0=\frac{2\cos \frac{\pi }{8}}{1+\cos \frac{\pi }{8}}=\mathrm{0.960433870103...}$ i ${\beta }_0=\frac{2\sin \frac{\pi }{8}}{1+\cos \frac{\pi }{8}}=\mathrm{0.397824734759...}$, donant un error màxim de 3,96%.

$\alpha$	$\beta$	Error màxim(%)	Error mig (%)
1/1	1/2	11.80	8.68
1/1	1/4	11.61	3.20
1/1	3/8	6.80	4.25
7/8	7/16	12.50	4.91
15/16	15/32	6.25	3.08
${\alpha }_0$	${\beta }_0$	3.96	2.41

Millores

Quan $\alpha <1$, $|z|$ es torna més chicotet que $𝐌𝐚𝐱$ (la qual cosa és geomètricament impossible) prop dels eixos a on $𝐌𝐢𝐧$ està prop de 0. Açò es pot remediar reemplaçant el resultat en $𝐌𝐚𝐱$ sempre que siga major, essencialment dividint la llínea en dos segments diferents.

$|z|=\max (𝐌𝐚𝐱,\alpha 𝐌𝐚𝐱+\beta 𝐌𝐢𝐧).$

L'us d'esta millora canvia quins valors de paràmetros són òptims, perque ya no necessiten una coincidència propenca per a tot l'interval. Una baixa $\alpha$ i més alt $\beta$ per lo tant, pot aumentar encara més la precisió. En dividir la llínea en dos com esta, es podria millorar la precisió encara més reemplaçant el primer segment per una millor estimació que $𝐌𝐚𝐱$ i ajustar $\alpha$ i $\beta$ respectivament.

$|z|=\max (|z_0|,|z_1|),$

$|z_0|={\alpha }_0𝐌𝐚𝐱+{\beta }_0𝐌𝐢𝐧,$

$|z_1|={\alpha }_1𝐌𝐚𝐱+{\beta }_1𝐌𝐢𝐧.$

${\alpha }_0$	${\beta }_0$	${\alpha }_1$	${\beta }_1$	Error màxim(%)
1	0	7/8	17/32	−2,65%
1	0	29/32	61/128	+2,4%
1	0	0.898204193266868	0.485968200201465	±2,12%
1	1/8	7/8	33/64	−1,7%
1	5/32	27/32	71/128	1,22%
127/128	3/16	27/32	71/128	−1,13%

No obstant, es deu tindre en conte que un valor distint de zero ${\beta }_0$ requeriria a lo manco una adició adicional i alguns canvis de bits (o una multiplicació), provablement casi duplicant el cost i, depenent del hardware, frustrant el propòsit d'usar una aproximació en primer lloc.

Referències

• Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7.
• Griffin, Grant. DSP Trick: Magnitude Estimator.