matlab cordic算法,CORDIC算法

CORDIC算法

From Wikipedia, the free encyclopedia

CORDIC (digit-by-digit method, Volder’s algorithm) (for

COordinate Rotation DIgital Computer)

is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions. It is

commonly used when no hardware multiplier is available (e.g.,

simple microcontrollers and FPGAs) as the

only operations it requires are addition, subtraction, bitshift and table lookup.

The modern CORDIC algorithm was first described in 1959 by

Jack E. Volder. It

was developed at the aeroelectronics department of Convair

to replace the analog resolver in the B-58 bomber’s navigation computer,Henry Briggs as early as

1624. John Stephen

Walther at Hewlett-Packard further generalized the

algorithm, allowing it to calculate hyperbolic and exponential functions, logarithms, multiplications, divisions, and square roots.

Originally, CORDIC was implemented using the binary numeral system. In the 1970s,

decimal CORDIC became widely used in pocket calculators, most of which operate in binary-coded-decimal (BCD) rather than binary. CORDIC is

particularly well-suited for handheld calculators, an application

for which cost (eg, chip gate count has to be minimised) is much

more important than is speed. Also the CORDIC subroutines for trigonometric and hyperbolic

functions can share most of their code.

Application

CORDIC is generally faster than other approaches when a hardware

multiplier is unavailable (e.g., in a microcontroller based

system), or when the number of gates required to implement the

functions it supports should be minimized (e.g., in an FPGA). 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.

Mode of operation

CORDIC can be used to calculate a number of different functions.

This explanation shows how to use CORDIC in rotation mode to

calculate sine and cosine of an angle, and assumes the desired

angle is given in radians and represented in a fixed point format. To determine the

sine or cosine for an angle β, the y or x coordinate

of a point on the unit

circle corresponding to the desired angle must be found. Using

CORDIC, we would start with the vector

v0:

In the first iteration, this vector would be rotated 45°

counterclockwise to get the vector

v1. Successive iterations will

rotate the vector in one or the other direction by half the amount

of the previous iteration until the desired angle has been

achieved.

An illustration of the CORDIC algorithm in progress.

More formally, every iteration calculates a rotation, which is

performed by multiplying the vector

vi with the rotation matrix

Ri:

The rotation matrix R is given by:

the rotation matrix becomes:

The expression for the rotated vector

vi + 1 =

Rivi then

becomes:

where xi and

yi are the components of

vi. Restricting the angles

γi so that

tanγi takes on the values

the multiplication with the tangent can 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:

where

and σi can have the values of −1

or 1 and is used to determine the direction of the rotation: if the

angle βi is positive then

σi is 1, otherwise it is −1.

We can ignore Ki in the

iterative process and then apply it afterward by a scaling

factor:

which is calculated in advance and stored in a table.

Additionally it can be noted that

to allow further reduction of the algorithm’s complexity. After

a sufficient number of iterations, the vector’s angle will be close

to the wanted angle β. For most ordinary purposes, 40

iterations (n = 40) is sufficient to obtain the correct result to

the 10th decimal place.

The only task left is to determine if the rotation should be

clockwise or counterclockwise at every iteration (choosing the

value of σ). This is done by keeping track of how much

we rotated at every iteration and subtracting that from the wanted

angle, and then checking if βn + 1

is positive and we need to rotate clockwise or if it is negative we

must rotate counterclockwise in order to get closer to the wanted

angle β.

The values of γn must also be

precomputed and stored. But for small angles,

arctan(γn) = γn in

fixed point representation, reducing table size.

As can be seen in the illustration above, the sine of the angle

β is the y coordinate of the final vector

vn, while the x coordinate is

the cosine value.

Implementation in MATLAB/GNU Octave

The following is a MATLAB/GNU

Octave implementation of CORDIC that does not rely on any

transcendental functions except in the precomputation of tables. If

the number of iterations n is predetermined, then the second

table can be replaced by a single constant. The two-by-two matrix multiplication represents a pair

of simple shifts and adds. With MATLAB’s standard double-precision

arithmetic and “format long” printout, the results increase in

accuracy for n up to about 48.

function v = cordic(beta,n)

% This function computes v = [cos(beta), sin(beta)] (beta in radians)

% using n iterations. Increasing n will increase the precision.

if beta < -pi/2 || beta > pi/2

if beta < 0

v = cordic(beta + pi, n);

else

v = cordic(beta – pi, n);

end

v = -v; % flip the sign for second or third quadrant

return

end

% Initialization of tables of constants used by CORDIC

% need a table of arctangents of negative powers of two, in radians:

% angles = atan(2.^-(0:27));

angles = [ …

0.745 0.081 0.686 0.676 …

0.096 0.027 0.048 0.000 …

0.007 0.008 0.000 0.000 …

0.000 0.000 0.0000 0.0000 …

0.0000 0.00000 0.00000 0.00000 …

0.000000 0.000000 0.000000 0.000000 …

0.0000000 0.0000000 0.0000000 0.00000000 ];

% and a table of products of reciprocal lengths of vectors [1, 2^-j]:

Kvalues = [ …

0.655 0.368 0.790 0.775 …

0.617 0.130 0.353 0.889 …

0.256 0.988 0.913 0.894 …

0.140 0.701 0.591 0.314 …

0.245 0.477 0.035 0.925 …

0.897 0.890 0.889 0.888 ];

Kn = Kvalues(min(n, length(Kvalues)));

% Initialize loop variables:

v = [1;0]; % start with 2-vector cosine and sine of zero

poweroftwo = 1;

angle = angles(1);

% Iterations

for j = 0:n-1;

if beta < 0

sigma = -1;

else

sigma = 1;

end

factor = sigma * poweroftwo;

R = [1, -factor; factor, 1];

v = R * v; % 2-by-2 matrix multiply

beta = beta – sigma * angle; % update the remaining angle

poweroftwo = poweroftwo / 2;

% update the angle from table, or eventually by just dividing by two

if j+2 > length(angles)

angle = angle / 2;

else

angle = angles(j+2);

end

end

% Adjust length of output vector to be [cos(beta), sin(beta)]:

v = v * Kn;

return

Hardware implementation

The primary use of the CORDIC algorithms in a hardware

implementation is to avoid time-consuming complex multipliers. The

computation of phase for complex number can be easily implemented

in a hardware description languages using only adder and shifter

circuits bypassing the bulky complex number multipliers.

Fabrication techniques have steadily improved, and complex number

can now be handled directly without too high a cost in time, power

consumption, or excessive die space, so the use of CORDIC

techniques is not as critical in many applications as they once

were.

Related algorithms

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 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 (in radians) by computing the

exponential of 0 + ix, which is

cosx + isinx. The BKM algorithm

is slightly more complex than CORDIC, but has the advantage that it

does not need a scaling factor (K).

History

Volder was inspired by the following formula in the 1946 edition

of the CRC Handbook of

Chemistry and Physics:

with

Some of the prominent early applications of CORDIC were in the

Convair navigation computers CORDIC I to CORDIC IIIHP-9100 and HP-35

calculatorsIntel

80×87 coprocessor series until Intel 80486, and Motorola 68881

Decimal CORDIC was first suggested by Hermann Schmid and Anthony

Bogacki.