Several methods for approximating the exact calculation of the
`magnitude of quadrature components are faster, and require smaller
`programs, than the exact methods themselves.
`
`Magnitude Approximations for
`
`Microprocessor Implementation
`
`W. Thomas Adar s* and John Brady
`
`Applied Research Laboratories
`University of Texas at Austin
`
`Many data processing systems require computation
`of the magnitude of vector quantities expressed in rec-
`tangular coordinates. All the various applications, such
`as the amplitude computation of quadrature samples of
`the magnitude portion of a rectangular-to-polar conver-
`sion, require the operation R = V 12 + Q2. Here, we will
`review several popular forms of piece-wise approxima-
`tion and will demonstrate their advantages. We will give
`examples of typical implementations.
`
`Motivation
`
`The need to compute the magnitude of vector com-
`ponents occurs repeatedly in graphics and signal process-
`ing computations. As more of this processing is done
`digitally and as system data rates increase, less time is
`available for each computation. Previously, in systems
`where the data rate permitted, excellent approximations
`to 1127+ Q2 could be achieved through Cordic routines
`and through successive approximation techniques over
`large dynamic ranges. For systems in which vector com-
`
`*Now with IBM, Entry Systems Division, Austin, Texas.
`
`ponents are expressed in eight or fewer bits, exact methods
`such as look-up tables or programmed logic arrays have
`been used. For time-constrained systems of larger
`dynamic range, the exact computation has been replaced
`by piece-wise linear approximations.
`Although the approximations typically introduce er-
`ror in the result, they reduce processing time. We will
`discuss ease of implementation, amount of error intro-
`duced,
`and
`computation
`speed
`for
`several
`approximations.
`
`Background
`
`An excellent survey of piece-wise linear methods is
`found in a letter by A. E. Filip to the editor of the IEEE
`Transactions on Audio and Electroacoustics.1 Filip ap-
`proaches the problem of error in approximating
`\ 12+ Q2 by constraining the error to an equiripple case.
`He then compares his equiripple approach to several other
`approximations (see "Rationale for magnitude approx-
`imation" on page 28). The approximations that we will ex-
`amine here consist of the ones discussed in Filip's article
`
`October 1983
`
`0272-1732/83/1000-0027$01.oo
`
`1983 IEEE
`
`27
`
`WAVES345_1013-0001
`
`Petitioner Waves Audio Ltd. 345 - Ex. 1013
`
`

`
`and some other methods. All these methods consist of
`a linear approximation to the function V 12 +Q2 and re-
`quire that the magnitude of I and Q be compared and
`that the largest and smallest of the two be defined. We
`will employ Filip's notation to avoid confusion.
`
`Therefore, we define
`
`x = max (jI',IQI)
`y = min (111,IQI).
`
`The reason for the selection of the largest and smallest
`of I and Q may not be obvious unless one considers that
`if either I or Q is much larger than the other it will tend
`to dominate the result of V I2 + Q2. By selecting the
`largest of I and Q, we can find appropriate coefficients
`or multipliers, called a and b, for x and y such that the
`amplitude-the resultant R = V 12+ Q2-is approx-
`imated by R = ax + by. In the one-line approximations,
`one set of coefficients holds for all ratios ofy/x or, alter-
`nately stated,
`
`a = a,
`b =b
`
`for e = 0 - 450, where 9 = tan-
`approximations, an angle 00 is
`< 90,
`
`- Iy/x. For the two-line
`defined such that for
`
`and for 0 >90,
`
`a =a,
`b =b
`
`a = a2
`b = b2.
`
`The values for a, b, and 00 must be chosen to minimize
`cost, size, or error and/or to maximize speed. Filip
`presents several sets of values for a and b and computes
`the mean, the standard deviation, and the peak error for
`both one-line and two-line approximations. Table I and
`2 give the values of a and b and the mean, standard, and
`peak errors for several value sets in addition to Filip's
`value sets; all computations have been verified. Region
`I is the portion of the approximation in which the coef-
`ficients (al,bl) are used. Figures 1 and 2 are plots of the
`errors introduced by the different value sets. Figure 1
`shows a comparison of the one-line methods presented
`in Table 1, while Figure 2 shows a comparison of the two-
`line methods from Table 2. Generally, the two-line
`methods require more execution time, but their errors are
`lower than those of the one-line methods. Our experience
`has been that the one-line approximations are adequate
`for many signal processing tasks but also that the two-
`line approximations are not too difficult to program.
`
`Table 1.
`One-line approximations for V
`
`with computed errors.*
`
`1
`
`2
`
`VALUE SET
`4
`
`5
`
`3
`
`6
`
`0.961
`
`1.000
`
`0.969
`1.000 (31/32) 0.948 1
`
`7
`
`1
`
`0.398
`
`0.267
`
`0.500
`
`0.375
`
`0.393 0.375
`
`0.25
`
`3.95
`
`10.4
`
`11.8
`
`4.97
`
`5.19
`
`6.8
`
`11.6
`
`COEFFICIENT
`a
`COEFFICIENT
`b
`PEAK ERROR
`lemaxl
`(percent)
`MEAN ERROR
`
`28
`
`1.30
`
`(percent)
`STANDARD
`DEVIATION OF
`THE ERROR
`Oe
`(percent)
`*Portions from Filip's
`
`2.70
`
`0.
`
`8.7
`
`1.20
`
`0
`
`4.0
`
`0.656
`
`Analysis
`
`3.87
`
`9.21
`
`2.70
`
`2.33
`
`2.56
`
`4.11
`
`Linear Approximations
`
`Of the value sets shown in Figure 1, the ones that
`minimize processing time are those for which the a and
`b coefficients can be expressed as a quotient whose
`denominator is a power of 2, such as 1/2, 3/8, or 3/4.
`With them, a shifting (truncation) process can be used
`for the division. After the division, repeated additions
`
`IEEE MICRO
`
`WAVES345_1013-0002
`
`Petitioner Waves Audio Ltd. 345 - Ex. 1013
`
`

`
`COEFFICIENTS
`b= 0.2(
`67
`b= 0.2!
`b=0.3S
`93
`b = 0.31
`75
`98
`b = 0.3'
`75
`b=0.3.
`b=0.5
`
`a= 1.0
`a= 1.0
`a= 0.948
`a = 0.969
`a = 0.961
`a=1.0
`a= 1.0
`
`5 ,
`
`VALUE SET
`
`2
`7
`5
`4
`1
`6
`3
`
`10
`l
`
`1
`1
`
`DEGREES
`25
`20
`
`+15
`
`+10 -
`
`N
`
`o+5
`
`cc°0
`
`-10
`
`-15
`Figure 1. Comparison of one-line approximations to R = V/ 12+ OR
`
`BREAKPOINT
`26.5650
`22.50
`14.036240
`14.036240
`
`COEFFICIENTS
`a1 = 0.986 b1 = 0.233 a2= 0.817 b2= 0.586
`b1 = 0.197 a2= 0.84
`a, = 0.99
`b2= 0.561
`a, = 0.996 b1 = 0.123 a2= 0.886 b2= 0.502
`a1,=1.0
`b1= 0.0
`a2=0.875 b2=0.5
`
`DEGREES
`
`VALUE SET
`
`2 3 4
`
`+15F
`+10 _
`
`'o +5-
`
`cc 5
`- r.
`
`x 0
`
`uw
`
`Figure 2. Comparison of two-line approximations to R =
`
`can be used to accomplish the multiplication. Of the one-
`line approximations, the value sets which fit the power-
`of-2 quotient criterion are sets 3, 4, 6, and 7, which are
`plotted in Figure 3. It is easy to see that value set 3
`(x+y/2) provides the simplest and fastest implementa-
`tion, since only one shift operation and one addition are
`required in addition to the comparison. Value set 4 is
`much more difficult to implement due to the 31/32 coef-
`ficient, and value sets 6 and 7 lie between value sets 3
`and 4 in difficulty, with value set 7 having the smallest
`mean error. Notice that the coefficients for value set 7
`(x+y/4) are nearly the same as those for value set 2
`(x +0.267y) and that the coefficients for value set 6 are
`very close to those for value sets 1, 4, and 5. It may be
`concluded that value sets 3, 6, and 7 are the easiest to
`implement and that all have less than 3/4-dB mean error
`and less than 1-dB peak error. These errors are entirely
`acceptable for many systems.
`If peak errors of less than 1/2 dB are required, then
`a two-line method will be needed. Two-line methods re-
`quire more execution time and are slightly more difficult
`to implement. In order to implement a two-line method,
`one must separate the regions by measuring the magnitude
`of the difference between the quadrature components to
`determine whether one component is larger than the other
`by some preset amount. The magnitude of the difference
`determines which of the regions is chosen for the approx-
`imation. The implementation is made simpler if this dif-
`ference is a power of 2. Table 2 shows all the two-line
`methods we examined. The methods with coefficients that
`are powers of 2 and whose difference magnitude is 2 are
`value sets 4-9. Figure 4 is a plot of value set 4 and Figure
`5 is a plot of value set 7; value sets 4 and 7 were chosen
`since they have the lowest errors of value sets 4-9. The
`peak errors are less than 0.26 dB and the mean errors are
`0.05 dB and 0.012 dB, respectively. This reduction in er-
`ror from the one-line methods may be significant enough
`in some applications to justify the more extensive soft-
`ware needed for two-line methods.
`If there is a criterion other than ease of implementa-
`
`Table 2.
`Two-line approximations for V j2 + Q2, with computed errors.*
`VALUE SET
`5
`6
`7
`60=tan'1(1/4) 80=tan1l(1/4) eo=tan-(1/2) 0
`1.0
`1.0
`1.0
`0.875
`1.0
`0.875
`
`4
`90=tan'1(1/4)
`1.0
`0.875
`
`1
`2
`3
`BREAKPOINT 80=n/8 e0=tan'1(1/2) 80=tan-1(1/4)
`0.990
`REGION
`0.986
`0.996
`REGION II
`0.840
`0.817
`0.886
`
`8
`9
`=tan-1(1/2) 08=tan-1(1/2
`1.0
`1.0
`0.875
`1.0
`
`0.197
`0.561
`0.970
`
`0.970
`
`0.323
`
`0.644
`
`0.233
`0.586
`1.36
`
`0.650
`
`0.354
`
`0.123
`0.502
`0.376
`
`1.84
`
`0.461
`
`0.765
`
`1.05
`
`0
`0.5
`2.98
`
`2.98
`
`0.617
`
`1.23
`
`0.125
`0.5
`0.778
`
`2.95
`
`0.143
`
`0.021
`
`0
`0.5
`2.97
`
`11.8
`
`6.76
`
`0.125
`0.5
`4.92
`
`2.77
`
`0.499
`
`5.4
`
`1.45
`
`0
`0.5
`10.5
`
`2.77
`
`2.17
`
`2.99
`
`0
`0.5
`10.5
`
`11.8
`
`1.96
`
`7.11
`
`COEFFICIENT
`a
`
`COEFFICIENT
`b
`
`REGION
`REGION II
`REGION
`
`REGION II
`
`PEAK ERROR
`Iemax
`(percent)
`MEAN ERROR
`e
`(percent)
`STANDARD
`DEVIATION
`Oe
`(percent)
`*Portions from Filip's "Linear Approximations
`
`October 1983
`
`29
`
`WAVES345_1013-0003
`
`Petitioner Waves Audio Ltd. 345 - Ex. 1013
`
`

`
`tion, then peak error, mean error, or standard deviation
`may be considered. The tables give the values of the er-
`rors so that reasonable design selections can be made. In
`general, a random distribution of the input values is
`assumed.
`
`Implementations
`
`The software realization for one one-line method and
`one two-line method will be described here in order to
`illustrate the relative complexity of the various methods.
`
`One-line method. The one-line method chosen for im-
`plementation is a = 1, B = 1/4, since it produces a low
`mean error (0.656 dB). Figure 6 is a flowchart of this
`method. Since a comparison of the magnitude of these
`components is needed, the absolute value of the
`quadrature components is computed first. Then the
`magnitudes are compared, and the larger of the
`quadrature components is placed in a register called X.
`The smaller of the two is placed in a register called Y.
`The contents of the Y register are shifted two times to
`the right, which approximates division by 4. There is some
`error involved in this method of division, but the average
`error for a 12-bit number is less than 0.5 percent. The
`resulting contents of the Y register are added to the con-
`tents of the X register to obtain the final result. Note that
`if an approximation such as x + 3y/8 were to be im-
`plemented, the Y register would be shifted three times
`for division by 8, and the resulting contents of Y would
`be added to the X register three times to implement the
`multiplication.
`
`Two-line method. The two-line method chosen for im-
`plementation is Region I, a = 1.0, b = 0, and Region
`II, a = 7/8, b = 1/2, Oo = tan-1(b/a). This method
`was chosen because it has a low mean error (0.61 per-
`cent) and is representative of all two-line methods. Figure
`7 is a flowchart of this method. As in the one-line method,
`the absolute values of the I and Q components are com-
`puted first. Then these absolute values are compared. The
`comparison must determine whether either the x or y com-
`ponent is four times as large as the other. Depending on
`the outcome of this comparison, one of two methods is
`chosen. If one component is at least four times larger than
`the other, the angle is in Region I and the largest number
`is chosen. The approximation is then complete. If one
`component is not four times larger than the other, the
`angle is in Region II and the approximation must be com-
`puted with a = 7/8 and b = 1/2. The X and Y registers
`holding the absolute values of the coefficient must be
`shifted the appropriate number of places in order to ap-
`proximate divisions by 8 and by 2. The registeirs must be
`summed to an accumulator and the X register must be
`added to itself seven times; the Y register must be added
`to the total once. The operation is then complete.
`These one- and two-line approximation methods are
`not difficult to implement, result in faster operation, and
`require less processing time than exact methods.
`
`IEEE MICRO
`
`VALUE SET
`
`7
`
`4
`
`6
`
`3
`
`10
`
`15
`
`COEFFICIENTS
`an 1.0
`bu0.250
`
`la 0.
`
`b a 0.375
`
`a
`
`1.0
`
`ba0.375
`
`s 1.0
`ba0.5
`DEGREES
`20
`25
`
`3Q
`
`+15r
`
`+10
`
`O +5
`
`x c
`
`c
`
`0
`
`le
`
`-10
`
`-15
`
`0 c
`
`c:
`LLJ
`
`Figure 3. One-line methods wih power.of-2 coefficients.
`
`+15
`
`+10
`
`CN
`
`'0 +5°vS
`
`): 14.03
`al a 1.0
`b, - 0.0
`a2' 0.875
`0.5
`b2
`
`5
`
`10
`
`15
`
`25
`20
`DEGREES
`
`-O
`
`35
`
`40
`
`45
`
`X 0 :
`
`Figure 4. Plot of the "fast" two-line method.
`
`+15r
`
`+10 F
`
`+5 F
`
`v.~ .. _-A .
`5
`10
`15
`
`): 14.O3
`a, s 1.0
`b, - 0.125
`- 0.875
`0.5
`
`b2
`
`.! _i
`25
`20
`DEGREES
`
`30
`
`35
`
`40
`
`45
`
`N
`
`0 wc
`
`c0c
`
`c
`:r
`
`Figure 5. Plot of the two-line pproximation, value set 7.
`
`30
`
`WAVES345_1013-0004
`
`Petitioner Waves Audio Ltd. 345 - Ex. 1013
`
`

`
`Several methods can be used to approximate the ex-
`act calculation of the magnitude of quadrature com-
`ponents. A number of one-line methods give faster com-
`putation, with less software, than exact methods. For even
`lower errors, two-line approximations can be easily im-
`plemented, with even higher-speed results. -
`
`Acknowledgment
`
`The authors wish to thank Patti Hall for the genera-
`tion of the computer plots. This work was sponsored
`under Naval Sea Systems Command Contract
`N00024-76-C-6022.
`
`Reference
`1. A. E. Filip, "Linear Approximations to '.72+_y1Having
`Equiripple Characteristics," IEEE Trans. Audio and Elec-
`troacoustics, Vol. AU-21, No. 3, 1973, pp. 554-556.
`
`W. Thomas Adams has been an engineer
`with IBM Corporation, Entry Systems
`Division, Austin, Texas, since 1978. His
`responsibilities
`include new product
`development. He was a research engineer
`with the Applied Research Laboratories of
`the University of Texas at Austin from 1969
`until 1977. A member of the IEEE, Adams
`was chairman of the Central Texas Chapter
`YNu0 s00204zi50of the Cornputer Society for 1982-83. He
`received a BS in electrical engineering in 1969 and an MS in elec-
`trical engineering in 1974, both from the University of Texas
`at Austin.
`Adams' address is IBM Corporation, F25/045, 11400 Burnet
`Rd., Austin, TX 78758.
`
`John Brady is an engineer at the Applied
`Research Laboratories of the University of
`Texas at Austin, where he is involved in
`sonar signal processing applications. He
`received a BS in 1972 and an MS in 1978,
`both in electrical engineering and both from
`the University of Texas at Austin.
`Brady's address is Applied Research
`C, V l Laboratories, The University of Texas at
`m Austin, PO Box 8029, Austin, TX 78712.
`
`October 1983
`
`Figure 6. Flowchart for the one-line approximation, value
`set 7: a + (1/4) b.
`
`Figure 7. Flowchart for the two-line approximation, value set 8: region
`I, a = 1.0, b = 0; region 11, a = 7/8, b = 1/2, tan-18 = 1/4.
`
`31
`
`WAVES345_1013-0005
`
`Petitioner Waves Audio Ltd. 345 - Ex. 1013