Algoritmo alfa max mas beta min

El lugar geométrico de los puntos que dan el mismo valor en el algoritmo, para diferentes valores de alfa y beta

El algoritmo Alfa max más Beta min es una aproximación lineal de alta velocidad de la raíz cuadrada de la suma de dos cuadrados. La raíz cuadrada de la suma de dos cuadrados, también conocida como suma pitagórica, es una función útil porque encuentra la hipotenusa de un triángulo rectángulo dadas las longitudes de los dos lados, la norma de un vector 2-D o la magnitud $|z|=\sqrt{a^2+b^2}$ de un número complejo z = a + bi dadas las partes real e imaginaria .

El algoritmo evita realizar las operaciones de raíz cuadrada y cúbica, y en su lugar utiliza operaciones simples como comparación, multiplicación y suma. Algunas elecciones de los parámetros α y β del algoritmo permiten que la operación de multiplicación se reduzca a un simple cambio de dígitos binarios que es particularmente adecuado para la implementación en circuitos digitales de alta velocidad.

La aproximación se expresa como

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

dónde $𝐌𝐚𝐱$ es el valor absoluto máximo de a y b, y $𝐌𝐢𝐧$ es el valor absoluto mínimo de a y b.

Para la aproximación más cercana, los valores óptimos para $\alpha$ y $\beta$ son ${\alpha }_0=\frac{2\cos \frac{\pi }{8}}{1+\cos \frac{\pi }{8}}=0.960433870103...$ y ${\beta }_0=\frac{2\sin \frac{\pi }{8}}{1+\cos \frac{\pi }{8}}=0.397824734759...$, dando un error máximo de 3,96%.

$\alpha$	$\beta$	Error máximo(%)	Error medio (%)
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

Mejoras

Cuando $\alpha <1$, $|z|$ se vuelve más pequeño que $𝐌𝐚𝐱$ (lo cual es geométricamente imposible) cerca de los ejes donde $𝐌𝐢𝐧$ está cerca de 0. Esto se puede remediar reemplazando el resultado con $𝐌𝐚𝐱$ siempre que sea mayor, esencialmente dividiendo la línea en dos segmentos diferentes.

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

El uso de esta mejora cambia qué valores de parámetros son óptimos, porque ya no necesitan una coincidencia cercana para todo el intervalo. Una baja $\alpha$ y más alto $\beta$ por lo tanto, puede aumentar aún más la precisión. Al dividir la línea en dos como esta, se podría mejorar la precisión aún más reemplazando el primer segmento por una mejor estimación que $𝐌𝐚𝐱$ y ajustar $\alpha$ y $\beta$ respectivamente.

$|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áximo(%)
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%

Sin embargo, se debe tener en cuenta que un valor distinto de cero ${\beta }_0$ requeriría al menos una adición adicional y algunos cambios de bits (o una multiplicación), probablemente casi duplicando el costo y, dependiendo del hardware, frustrando el propósito de usar una aproximación en primer lugar.

Referencias

• Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 Plantilla:ISBN.
• Griffin, Grant. DSP Trick: Magnitude Estimator.

Enlaces externos

• Plantilla:Cita web