Misplaced Pages

#12987

56-423: BKM is similar to CORDIC , but uses a table of logarithms rather than a table of arctangents . On each iteration, a choice of coefficient is made from a set of nine complex numbers, 1, 0, −1, i, −i, 1+i, 1−i, −1+i, −1−i, rather than only −1 or +1 as used by CORDIC. BKM provides a simpler method of computing some elementary functions, and unlike CORDIC, BKM needs no result scaling factor. The convergence rate of BKM

112-430: A k = 1 + 2 − k {\displaystyle a_{k}=1+2^{-k}} , allowing the product to approach any value between 1 and ~4.768, depending on which subset of a k {\displaystyle a_{k}} we use in the final product. At this point, the above equation looks like this: This choice of a k {\displaystyle a_{k}} reduces

168-468: A colleague of Volder at Convair, developed conversion algorithms between binary and binary-coded decimal (BCD). In 1958, Convair finally started to build a demonstration system to solve radar fix –taking problems named CORDIC I , completed in 1960 without Volder, who had left the company already. More universal CORDIC II models A (stationary) and B (airborne) were built and tested by Daggett and Harry Schuss in 1962. Volder's CORDIC algorithm

224-416: A complex vector with a vector on the unit circle actually amounts to a rotation). CORDICs are often used in circuits for telecommunications such as digital down converters . In two of the publications by Vladimir Baykov, it was proposed to use the double iterations method for the implementation of the functions: arcsine, arccosine, natural logarithm, exponential function, as well as for the calculation of

280-505: A consequence, CORDIC has been used for applications in diverse areas such as signal and image processing , communication systems , robotics and 3D graphics apart from general scientific and technical computation. The algorithm was used in the navigational system of the Apollo program 's Lunar Roving Vehicle to compute bearing and range, or distance from the Lunar module . CORDIC

336-421: A fixed-point format. To determine the sine or cosine for an angle β {\displaystyle \beta } , the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, one would start with the vector v 0 {\displaystyle v_{0}} : In the first iteration, this vector is rotated 45° counterclockwise to get

392-667: A four-function, floating-point desktop calculator he had completed in DTL logic in December 1964. This project resulted in the public demonstration of Hewlett-Packard's first desktop calculator with scientific functions, the HP ;9100A in March 1968, with series production starting later that year. When Wang Laboratories found that the HP ;9100A used an approach similar to

448-422: A multiplier-based or CORDIC-based implementation will depend on the context. The multiplication of two complex numbers represented by their real and imaginary components (rectangular coordinates), for example, requires 4 multiplications, but could be realized by a single CORDIC operating on complex numbers represented by their polar coordinates, especially if the magnitude of the numbers is not relevant (multiplying

504-460: A power series implementation is not due to the specificity of such an IP, i.e. CORDIC can compute many different functions (general purpose) while a hardware multiplier configured to execute power series implementations can only compute the function it was designed for. On the other hand, when a hardware multiplier is available ( e.g. , in a DSP microprocessor), table-lookup methods and power series are generally faster than CORDIC. In recent years,

560-651: A rotation, which is performed by multiplying the vector v i {\displaystyle v_{i}} with the rotation matrix R i {\displaystyle R_{i}} : The rotation matrix is given by Using the trigonometric identity : the cosine factor can be taken out to give: The expression for the rotated vector v i + 1 = R i v i {\displaystyle v_{i+1}=R_{i}v_{i}} then becomes: where x i {\displaystyle x_{i}} and y i {\displaystyle y_{i}} are

616-423: A scaling factor K ( n ) {\displaystyle K(n)} : which is calculated in advance and stored in a table or as a single constant, if the number of iterations is fixed. This correction could also be made in advance, by scaling v 0 {\displaystyle v_{0}} and hence saving a multiplication. Additionally, it can be noted that to allow further reduction of

SECTION 10

#1732775492013

672-506: A similar approach John E. Meggitt (IBM ) had proposed as pseudo-multiplication and pseudo-division in 1961. Meggitt's method also suggested the use of base 10 rather than base 2 , as used by Volder's CORDIC so far. These efforts led to the ROMable logic implementation of a decimal CORDIC prototype machine inside of Hewlett-Packard in 1966, built by and conceptually derived from Thomas E. Osborne 's prototypical Green Machine ,

728-464: A way to reduce the gate counts (and complexity) of the FPU sub-system. CORDIC uses simple shift-add operations for several computing tasks such as the calculation of trigonometric, hyperbolic and logarithmic functions, real and complex multiplications, division, square-root calculation, solution of linear systems, eigenvalue estimation, singular value decomposition , QR factorization and many others. As

784-494: Is a simple and efficient algorithm to calculate trigonometric functions , hyperbolic functions , square roots , multiplications , divisions , and exponentials and logarithms with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC is therefore also an example of digit-by-digit algorithms . CORDIC and closely related methods known as pseudo-multiplication and pseudo-division or factor combining are commonly used when no hardware multiplier

840-448: Is approximately one bit per iteration, like CORDIC, but BKM requires more precomputed table elements for the same precision because the table stores logarithms of complex operands. As with other algorithms in the shift-and-add class, BKM is particularly well-suited to hardware implementation. The relative performance of software BKM implementation in comparison to other methods such as polynomial or rational approximations will depend on

896-554: Is available (e.g. in simple microcontrollers and field-programmable gate arrays or FPGAs), as the only operations they require are additions , subtractions , bitshift and lookup tables . As such, they all belong to the class of shift-and-add algorithms . In computer science, CORDIC is often used to implement floating-point arithmetic when the target platform lacks hardware multiply for cost or space reasons. Similar mathematical techniques were published by Henry Briggs as early as 1624 and Robert Flower in 1771, but CORDIC

952-468: Is better optimized for low-complexity finite-state CPUs. CORDIC was conceived in 1956 by Jack E. Volder at the aeroelectronics department of Convair out of necessity to replace the analog resolver in the B-58 bomber 's navigation computer with a more accurate and faster real-time digital solution. Therefore, CORDIC is sometimes referred to as a digital resolver . In his research Volder

1008-688: Is indeed faster than interpolating table based implementations such as the ones provided by the ARM CMSIS and C standard libraries. Though the results may be slightly less accurate as the CORDIC modules provided only achieve 20 bits of precision in the result. For example, most of the performance difference compared to the ARM implementation is due to the overhead of the interpolation algorithm, which achieves full floating point precision (24 bits) and can likely achieve relative error to that precision. Another benefit

1064-404: Is positive, then σ i {\displaystyle \sigma _{i}} is +1, otherwise it is −1. The following trigonometric identity can be used to replace the cosine: giving this multiplier for each iteration: The K i {\displaystyle K_{i}} factors can then be taken out of the iterative process and applied all at once afterwards with

1120-842: Is strictly increasing, it can be shown by induction and convergence that for any 1 ≤ x ≲ 4.768 {\displaystyle 1\leq x\lesssim 4.768} . For calculating the output, we first create the reference table Then the output is computed iteratively by the definition y k = { 0 if  k = 0 y k − 1 + A k if  x k  would be ≤ x y k − 1 otherwise {\displaystyle y_{k}={\begin{cases}0&{\text{if }}k=0\\y_{k-1}+A_{k}&{\text{if }}x_{k}{\text{ would be}}\leq x\\y_{k-1}&{\text{otherwise}}\end{cases}}} The conditions in this iteration are

1176-667: Is that the CORDIC module is a coprocessor and can be run in parallel with other CPU tasks. The issue with using Taylor series is that while they do provide small absolute error, they do not exhibit well behaved relative error. Other means of polynomial approximation, such as minimax optimization, may be used to control both kinds of error. Many older systems with integer-only CPUs have implemented CORDIC to varying extents as part of their IEEE floating-point libraries. As most modern general-purpose CPUs have floating-point registers with common operations such as add, subtract, multiply, divide, sine, cosine, square root, log 10 , natural log,

SECTION 20

#1732775492013

1232-627: Is the BKM algorithm , which is a generalization of the logarithm and exponential algorithms to the complex plane. For instance, BKM can be used to compute the sine and cosine of a real angle x {\displaystyle x} (in radians) by computing the exponential of 0 + i x {\displaystyle 0+ix} , which is cis ⁡ ( x ) = cos ⁡ ( x ) + i sin ⁡ ( x ) {\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)} . The BKM algorithm

1288-736: Is the known value and x {\displaystyle x} is the value we want to calculate, thereby calculating the exponential instead of the logarithm. Since x becomes an unknown in this case, the conditional changes from to To calculate the logarithm function (L-mode), the algorithm in each iteration tests if x n ⋅ ( 1 + 2 − n ) ≤ x {\displaystyle x_{n}\cdot (1+2^{-n})\leq x} . If so, it calculates x n + 1 {\displaystyle x_{n+1}} and y n + 1 {\displaystyle y_{n+1}} . After N {\displaystyle N} iterations

1344-569: Is the number of digits), i.e. for each digit of the result. For the natural logarithm, exponential, hyperbolic sine, cosine and arctangent, R {\displaystyle R} iterations should be performed for each value i {\displaystyle i} . For the functions arcsine and arccosine, two R − 1 {\displaystyle R-1} iterations should be performed for each number digit, i.e. for each value of i {\displaystyle i} . For inverse hyperbolic sine and arcosine functions,

1400-437: Is the same for both examples (1 ≤  Argument  ≤ 4.768462058…). In the case of the base-2 logarithm the exponent can be split off in advance (to get the integer part) so that the algorithm can be applied to the remainder (between 1 and 2). Since the argument is smaller than 2.384231…, the iteration of k can start with 1. Working in either base, the multiplication by s can be replaced with direct modification of

1456-722: The factor combining method in their earlier LOCI-1 (September 1964) and LOCI-2 (January 1965) Logarithmic Computing Instrument desktop calculators, they unsuccessfully accused Hewlett-Packard of infringement of one of An Wang 's patents in 1968. John Stephen Walther at Hewlett-Packard generalized the algorithm into the Unified CORDIC algorithm in 1971, allowing it to calculate hyperbolic functions , natural exponentials , natural logarithms , multiplications , divisions , and square roots . The CORDIC subroutines for trigonometric and hyperbolic functions could share most of their code. This development resulted in

1512-412: The x axis) by an angle between −90° and +90°. Decisions on the direction of the rotation depend on β i {\displaystyle \beta _{i}} being positive or negative. The vectoring-mode of operation requires a slight modification of the algorithm. It starts with a vector whose x coordinate is positive whereas the y coordinate is arbitrary. Successive rotations have

1568-521: The CORDIC algorithm has been used extensively for various biomedical applications, especially in FPGA implementations. The STM32G4 series and certain STM32H7 series of MCUs implement a CORDIC module to accelerate computations in various mixed signal applications such as graphics for human-machine interface and field oriented control of motors. While not as fast as a power series approximation, CORDIC

1624-413: The CORDIC algorithm to solve sine and cosine functions and a prototypical computer implementing it. The report also discussed the possibility to compute hyperbolic coordinate rotation , logarithms and exponential functions with modified CORDIC algorithms. Utilizing CORDIC for multiplication and division was also conceived at this time. Based on the CORDIC principle, Dan H. Daggett,

1680-451: The algorithm's complexity. Some applications may avoid correcting for K {\displaystyle K} altogether, resulting in a processing gain A {\displaystyle A} : After a sufficient number of iterations, the vector's angle will be close to the wanted angle β {\displaystyle \beta } . For most ordinary purposes, 40 iterations ( n  = 40) are sufficient to obtain

1736-497: The availability of fast multi-bit shifts (i.e. a barrel shifter ) or hardware floating point arithmetic. In order to solve the equation the BKM algorithm takes advantage of a basic property of logarithms Using Pi notation , this identity generalizes to Because any number can be represented by a product, this allows us to choose any set of values a k {\displaystyle a_{k}} which multiply to give

BKM algorithm - Misplaced Pages Continue

1792-471: The components of v i {\displaystyle v_{i}} . Setting the angle γ i {\displaystyle \gamma _{i}} for each iteration such that tan ⁡ ( γ i ) = ± 2 − i {\displaystyle \tan(\gamma _{i})=\pm 2^{-i}} still yields a series that converges to every possible output value. The multiplication with

1848-444: The computational complexity of the product from repeated multiplication to simple addition and bit-shifting depending on the implementation. Finally, by storing the values ln ⁡ ( 1 + 2 − k ) {\displaystyle \ln(1+2^{-k})} in a table, calculating the solution is also a simple matter of addition. Iteratively, this gives us two separate sequences. One sequence approaches

1904-438: The convergence of the method throughout the valid range of argument changes. The generalization of the CORDIC convergence problems for the arbitrary positional number system with radix R {\displaystyle R} showed that for the functions sine, cosine, arctangent, it is enough to perform R − 1 {\displaystyle R-1} iterations for each value of i (i = 0 or 1 to n, where n

1960-403: The correct result to the 10th decimal place. The only task left is to determine whether the rotation should be clockwise or counterclockwise at each iteration (choosing the value of σ {\displaystyle \sigma } ). This is done by keeping track of how much the angle was rotated at each iteration and subtracting that from the wanted angle; then in order to get closer to

2016-498: The first scientific handheld calculator , the HP-35 in 1972. Based on hyperbolic CORDIC, Yuanyong Luo et al. further proposed a Generalized Hyperbolic CORDIC (GH CORDIC) to directly compute logarithms and exponentials with an arbitrary fixed base in 2019. Theoretically, Hyperbolic CORDIC is a special case of GH CORDIC. Originally, CORDIC was implemented only using the binary numeral system and despite Meggitt suggesting

2072-653: The floating point exponent, subtracting 1 from it during each iteration. This results in the algorithm using only addition and no multiplication. To calculate the exponential function (E-mode), the algorithm in each iteration tests if y n + ln ⁡ ( 1 + 2 − n ) ≤ y {\displaystyle y_{n}+\ln(1+2^{-n})\leq y} . If so, it calculates x n + 1 {\displaystyle x_{n+1}} and y n + 1 {\displaystyle y_{n+1}} . After N {\displaystyle N} iterations

2128-411: The goal of rotating the vector to the x axis (and therefore reducing the y coordinate to zero). At each step, the value of y determines the direction of the rotation. The final value of β i {\displaystyle \beta _{i}} contains the total angle of rotation. The final value of x will be the magnitude of the original vector scaled by K . So, an obvious use of

2184-696: The hyperbolic functions. Double iterations method consists in the fact that unlike the classical CORDIC method, where the iteration step value changes every time, i.e. on each iteration, in the double iteration method, the iteration step value is repeated twice and changes only through one iteration. Hence the designation for the degree indicator for double iterations appeared: i = 0 , 0 , 1 , 1 , 2 , 2 … {\displaystyle i=0,0,1,1,2,2\dots } . Whereas with ordinary iterations: i = 0 , 1 , 2 … {\displaystyle i=0,1,2\dots } . The double iteration method guarantees

2240-592: The input and output format did not alter CORDIC's core calculation algorithms. CORDIC is particularly well-suited for handheld calculators, in which low cost – and thus low chip gate count – is much more important than speed. CORDIC has been implemented in the ARM-based STM32G4 , Intel 8087 , 80287 , 80387 up to the 80486 coprocessor series as well as in the Motorola 68881 and 68882 for some kinds of floating-point instructions, mainly as

2296-840: The input value x {\displaystyle x} while the other approaches the output value ln ⁡ ( x ) = y {\displaystyle \ln(x)=y} : x k = { 1 if  k = 0 x k − 1 ⋅ ( 1 + 2 − k ) if  x k  would be ≤ x x k − 1 otherwise {\displaystyle x_{k}={\begin{cases}1&{\text{if }}k=0\\x_{k-1}\cdot (1+2^{-k})&{\text{if }}x_{k}{\text{ would be}}\leq x\\x_{k-1}&{\text{otherwise}}\end{cases}}} Given this recursive definition and because x k {\displaystyle x_{k}}

BKM algorithm - Misplaced Pages Continue

2352-439: The need to implement CORDIC in them with software is nearly non-existent. Only microcontroller or special safety and time-constrained software applications would need to consider using CORDIC. CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in rotation mode to calculate the sine and cosine of an angle, assuming that the desired angle is given in radians and represented in

2408-407: The number of iterations will be 2 R {\displaystyle 2R} for each i {\displaystyle i} , that is, for each result digit. CORDIC is part of the class of "shift-and-add" algorithms , as are the logarithm and exponential algorithms derived from Henry Briggs' work. Another shift-and-add algorithm which can be used for computing many elementary functions

2464-412: The same as the conditions for the input. Similar to the input, this sequence is also strictly increasing, so it can be shown that for any 0 ≤ y ≲ 1.562 {\displaystyle 0\leq y\lesssim 1.562} . Because the algorithm above calculates both the input and output simultaneously, it's possible to modify it slightly so that y {\displaystyle y}

2520-403: The table size. As can be seen in the illustration above, the sine of the angle β {\displaystyle \beta } is the y coordinate of the final vector v n , {\displaystyle v_{n},} while the x coordinate is the cosine value. The rotation-mode algorithm described above can rotate any vector (not only a unit vector aligned along

2576-392: The tangent can therefore be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a bit shift . The expression then becomes: and σ i {\displaystyle \sigma _{i}} is used to determine the direction of the rotation: if the angle γ i {\displaystyle \gamma _{i}}

2632-482: The use of the decimal system for his pseudo-multiplication approach, decimal CORDIC continued to remain mostly unheard of for several more years, so that Hermann Schmid and Anthony Bogacki still suggested it as a novelty as late as 1973 and it was found only later that Hewlett-Packard had implemented it in 1966 already. Decimal CORDIC became widely used in pocket calculators , most of which operate in binary-coded decimal (BCD) rather than binary. This change in

2688-604: The value of the function is known with an error of Δ exp ⁡ ( x ) ≤ 2 − N {\displaystyle \Delta \exp(x)\leq 2^{-N}} . Example program in C++ (see A_e for table): CORDIC CORDIC ( coordinate rotation digital computer ), Volder's algorithm , Digit-by-digit method , Circular CORDIC ( Jack E. Volder ), Linear CORDIC , Hyperbolic CORDIC (John Stephen Walther), and Generalized Hyperbolic CORDIC ( GH CORDIC ) (Yuanyong Luo et al.),

2744-460: The value of the function is known with an error of Δ ln ⁡ ( x ) ≤ 2 − N {\displaystyle \Delta \ln(x)\leq 2^{-N}} . Example program for natural logarithm in C++ (see A_e for table): Logarithms for bases other than e can be calculated with similar effort. Example program for binary logarithm in C++ (see A_2 for table): The allowed argument range

2800-559: The value we started with. In computer systems, it's much faster to multiply and divide by multiples of 2, but because not every number is a multiple of 2, using a k = 1 + 2 m {\displaystyle a_{k}=1+2^{m}} is a better option than a more simple choice of a k = 2 m {\displaystyle a_{k}=2^{m}} . Since we want to start with large changes and get more accurate as k {\displaystyle k} increases, we can more specifically use

2856-557: The vector v 1 {\displaystyle v_{1}} . Successive iterations rotate the vector in one or the other direction by size-decreasing steps, until the desired angle has been achieved. Each step angle is γ i = arctan ⁡ ( 2 − i ) {\displaystyle \gamma _{i}=\arctan {(2^{-i})}} for i = 0 , 1 , 2 , … {\displaystyle i=0,1,2,\dots } . More formally, every iteration calculates

SECTION 50

#1732775492013

2912-528: The vectoring mode is the transformation from rectangular to polar coordinates. In Java the Math class has a scalb(double x,int scale) method to perform such a shift, C has the ldexp function, and the x86 class of processors have the fscale floating point operation. The number of logic gates for the implementation of a CORDIC is roughly comparable to the number required for a multiplier as both require combinations of shifts and additions. The choice for

2968-632: The wanted angle β {\displaystyle \beta } , if β n + 1 {\displaystyle \beta _{n+1}} is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise: The values of γ n {\displaystyle \gamma _{n}} must also be precomputed and stored. For small angles it can be approximated with arctan ⁡ ( γ n ) ≈ γ n {\displaystyle \arctan(\gamma _{n})\approx \gamma _{n}} to reduce

3024-642: Was first described in public in 1959, which caused it to be incorporated into navigation computers by companies including Martin-Orlando , Computer Control , Litton , Kearfott , Lear-Siegler , Sperry , Raytheon , and Collins Radio . Volder teamed up with Malcolm McMillan to build Athena , a fixed-point desktop calculator utilizing his binary CORDIC algorithm. The design was introduced to Hewlett-Packard in June 1965, but not accepted. Still, McMillan introduced David S. Cochran (HP) to Volder's algorithm and when Cochran later met Volder he referred him to

3080-588: Was inspired by a formula in the 1946 edition of the CRC Handbook of Chemistry and Physics : where φ {\displaystyle \varphi } is such that tan ⁡ ( φ ) = 2 − n {\displaystyle \tan(\varphi )=2^{-n}} , and K n := 1 + 2 − 2 n {\displaystyle K_{n}:={\sqrt {1+2^{-2n}}}} . His research led to an internal technical report proposing

3136-576: Was used to implement the Intel 8087 math coprocessor in 1980, avoiding the need to implement hardware multiplication. CORDIC is generally faster than other approaches when a hardware multiplier is not available (e.g., a microcontroller), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA or ASIC ). In fact, CORDIC is a standard drop-in IP in FPGA development applications such as Vivado for Xilinx, while

#12987