Period mapping: Difference between revisions
simplify nowrap |
en>Enyokoyama m →Local polarized period mappings: add a link bilinear form |
||
Line 1: | Line 1: | ||
[[File:Alpha Max Beta Min approximation.png|800px|centre]] | |||
The '''alpha max plus beta min algorithm''' is a high-speed approximation of the [[square root]] of the sum of two squares. That is to say, it gives the approximate absolute magnitude of a [[vector (geometric)|vector]] given the [[Real number|real]] and [[Imaginary number|imaginary]] parts. | |||
:<math> |V| = \sqrt{ I^2 + Q^2 } </math> | |||
The algorithm avoids the necessity of performing the square and square-root operations and instead uses simple operations such as comparison, multiplication and addition. Some choices of the α and β parameters of the algorithm allow the multiplication operation to be reduced to a simple shift of binary digits that is particularly well suited to implementation in high-speed digital circuitry. | |||
The approximation is expressed as: | |||
:<math> |V| = \alpha\,\! \mathbf{Max} + \beta\,\! \mathbf{Min} </math> | |||
Where <math>\mathbf{Max}</math> is the maximum absolute value of I and Q and <math>\mathbf{Min}</math> is the minimum absolute value of I and Q. | |||
For the closest approximation, the optimum values for <math>\alpha\,\!</math> and <math>\beta\,\!</math> are <math>\alpha_0 = \frac{2 \cos \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}} = 0.96043387...</math> and <math>\beta_0 = \frac{2 \sin \frac{\pi}{8}}{1 + \cos \frac{\pi}{8}} = 0.39782473...</math>, giving a maximum error of 3.96%. | |||
{| class="wikitable" | |||
|- | |||
! <math>\alpha\,\!</math> || <math>\beta\,\!</math> || Largest error (%) || Mean error (%)<br /> | |||
|- | |||
| align="right" | 1/1 || align="right" | 1/2 || align="right" | 11.80 || align="right" | 8.68 | |||
|- | |||
| align="right" | 1/1 || align="right" | 1/4 || align="right" | 11.61 || align="right" | 0.65 | |||
|- | |||
| align="right" | 1/1 || align="right" | 3/8 || align="right" | 6.80 || align="right" | 4.01 | |||
|- | |||
| align="right" | 7/8 || align="right" | 7/16 || align="right" | 12.5 || align="right" | 4.91 | |||
|- | |||
| align="right" | 15/16 || align="right" | 15/32 || align="right" | 6.25 || align="right" | 1.88 | |||
|- | |||
| align="right" | <math>\alpha_0</math> || align="right" | <math>\beta_0</math> || align="right" | 3.96 || align="right" | 1.30 | |||
|- | |||
|} | |||
==References== | |||
*[[Richard Lyons|Lyons, Richard G]]. ''Understanding Digital Signal Processing, section 13.2.'' Prentice Hall, 2004 ISBN 0-13-108989-7. | |||
* Griffin, Grant. [http://www.dspguru.com/dsp/tricks/magnitude-estimator DSP Trick: Magnitude Estimator]. | |||
[[Category:Approximation algorithms]] | |||
[[Category:Root-finding algorithms]] |
Revision as of 12:12, 15 November 2013
The alpha max plus beta min algorithm is a high-speed approximation of the square root of the sum of two squares. That is to say, it gives the approximate absolute magnitude of a vector given the real and imaginary parts.
The algorithm avoids the necessity of performing the square and square-root operations and instead uses simple operations such as comparison, multiplication and addition. Some choices of the α and β parameters of the algorithm allow the multiplication operation to be reduced to a simple shift of binary digits that is particularly well suited to implementation in high-speed digital circuitry.
The approximation is expressed as:
Where is the maximum absolute value of I and Q and is the minimum absolute value of I and Q.
For the closest approximation, the optimum values for and are and , giving a maximum error of 3.96%.
Largest error (%) | Mean error (%) | ||
---|---|---|---|
1/1 | 1/2 | 11.80 | 8.68 |
1/1 | 1/4 | 11.61 | 0.65 |
1/1 | 3/8 | 6.80 | 4.01 |
7/8 | 7/16 | 12.5 | 4.91 |
15/16 | 15/32 | 6.25 | 1.88 |
3.96 | 1.30 |
References
- Lyons, Richard G. Understanding Digital Signal Processing, section 13.2. Prentice Hall, 2004 ISBN 0-13-108989-7.
- Griffin, Grant. DSP Trick: Magnitude Estimator.