Hello

Welcome lekule blog

Hi, I`m Sostenes, Electrical Technician and PLC`S Programmer.
Everyday I`m exploring the world of Electrical to find better solution for Automation.
together in the world. #lekule86
Join us on

An Introduction to the CORDIC Algorithm

CORDIC (coordinate rotation digital computer) is a hardware-efficient iterative method which uses rotations to calculate a wide range of elementary functions.
This article reviews the basics of this algorithm and later demonstrates how we can use CORDIC to calculate the sine and cosine of a given angle.

Rotate to Perform a Wide Range of Operations

For the time being, let's forget about electronics and go back to high-school mathematics to see which operations can be achieved by simply rotating a vector.
Suppose that we have an efficient system that receives a vector and rotates it by an arbitrary angle

. Choosing the origin as the center of rotation, we will get to the point (
) by rotating the point (
) by




Equation 1.

Figure 1 illustrates this rotation below.


Figure 1. Rotating the input vector by
. Image courtesy of UCLA (PDF).

If we choose

 and
, after rotation we will have



Equation 2.

Therefore, we can simply calculate sine and cosine of an arbitrary angle through rotation.
For another example of the functions that can be calculated from rotation, consider the vector magnitude, 

. To achieve this, we only need to rotate the input vector so that it is aligned with the x-axis. In this way,
and the x component will give the vector magnitude.
Interestingly, the list of the functions that can be calculated from rotation is relatively long. Inverse trigonometric functions such as arctan, arcsin, arccos, hyperbolic and logarithmic functions, polar to rectangular transform, Cartesian to polar transform, multiplication, and division are some of the most important operations that can be obtained from variants of rotation.
The CORDIC algorithm attempts to provide a hardware-efficient method for calculating these functions. “Hardware-efficient” means that the algorithm avoids the use of multipliers and relies on only shifts and additions/subtractions. Note that other methods of implementing these functions, such as utilizing power series, usually need dedicated multipliers.

The Basics of CORDIC

Equation 1 can be simplified to:


Equation 3.

The above equation shows that for one rotation, we need to perform 4 multiplications (plus some additions/subtractions). The question that remains is, How can we avoid these multiplications?
The CORDIC algorithm resorts to two fundamental ideas to achieve rotation without multiplication. The first fundamental idea is that rotating the input vector by an arbitrary angle

is equal to rotating the vector by several smaller angles,
,
, provided
. For example, a rotation of
is the same as three successive rotations by
,
, and
(note that we can use negative angles too).
The second fundamental idea is that we can choose the small elementary angles in a way that

for
. In this way, multiplication by
can be achieved by a bitwise shift which is a much faster operation compared to multiplication. You may wonder if, for a given
, we can satisfy the conditions of these two fundamental ideas simultaneously, i.e.
 while
.
Note that, in practice, we face a limited accuracy and the convergence of these equations is important. Fortunately, the equations converge and by increasing

, we can increase the accuracy of calculations.
Choosing angles such that

is an inverse power of two will allow us to perform these multiplications using bit shifts, but we still need to perform two other multiplications by
. Note that the multiplications by
 act as a system gain (because both the x and y components need to be multiplied by the same scaling factor). If we ignore this scaling factor, the rotation angle will be correct but we still have to scale down both the x and y components to arrive at the final values of
and
. This is illustrated in Figure 2 where multiplications by
are not applied and, as a result,
and
 are achieved which are
times larger than
and
, respectively.


Figure 2. Multiplication by cos(θ) acts as a scaling factor.

Now let's examine the effect of this scaling factor when applying the successive elementary rotations of the CORDIC algorithm. Suppose that we want to rotate the input vector by

which is
. The first rotation by
will give us:


Equation 4.

For the second rotation, we obtain:


Equation 5.

Substituting Equation 4 into Equation 5 gives us:


Equation 6.

For the third rotation, we will have:


Equation 7.

Finally, we obtain:


Equation 8.

Equation 8 has two implications. First, each rotation mandates a scaling factor which appears in the final calculations. This means that it is possible to ignore the

term of equation (3) and take the scaling factor into account at the end of the algorithm. Second, as we proceed with the algorithm, the angle of rotation rapidly becomes smaller and smaller. Hence,
tends toward unity.
For example, with

,
becomes
which leads to a scaling factor of
. As a result, if the algorithm is designed to have more than six iterations, looking at the four significant figures, we obtain the following scaling factor:



In summary, we can ignore the

term of Equation 3 and apply a scaling factor of approximately
at the end of the process regardless of the desired rotation angle. For a more demanding application where higher accuracy is required, you can consider more significant figures for the scaling factor. This generally comes at no cost because, as explained in the example at the end of the article, the scaling factor is usually stored as an initial value in the system.
We can use a constant scaling factor because the algorithm uses some predefined angles in each elementary rotation. You may wonder if we still need a multiplier to take the scaling factor into account. As discussed later, we will see that we can sometimes apply the scaling factor somewhere else in the system without using a multiplier.
Therefore, omitting the scaling factor term from Equation 3, we obtain the following equations for the CORDIC algorithm:



Equation 9.

where

 determines the sign of the elementary angle and will be discussed in the next section of the article. The above equation shows that the algorithm will always perform a certain number of rotations with the predefined angles (for example, 12 rotations), and the only thing that the algorithm determines is whether each rotation will go clockwise or counter-clockwise during each iteration (choose
equal to +1 or -1).

Negative Feedback Mechanism of CORDIC

Equation 9 allows us to rotate a vector by some predefined angles without multiplication but how can we rotate the vector by an arbitrary angle? In other words, how should we choose the value of

for each iteration of the algorithm? This is accomplished by simply recording the angle of previous rotations and comparing the overall achieved rotation with the desired angle.
If the desired rotation is larger (smaller) than previously achieved rotation, then we need to rotate counter-clockwise (clockwise) in the next iteration. For example, assume we want a rotation of

. At the beginning of the algorithm, we have achieved zero rotation and
, so
. This will bring about a rotation of
. In the second iteration, we see that the achieved rotation is still smaller than the target angle (
), so
.
This will lead to a

rotation in this iteration. Since
, the next iteration will choose
which means that a rotation of
will be applied clockwise and the overall rotation will be
. This process will go on until all the
iterations of the algorithm are performed.
The described procedure is actually a negative feedback mechanism which computes the overall rotation and compares that to a reference value and chooses the new rotations in a way that minimizes the error signal (

).
The above mechanism is taken into account by adding another equation to the set of expressions in Equation 9 as follows:




Equation 10.

This equation accumulates the angle of all the previous rotations and compares that with an initial value

. For example, in the rotation by
, we must choose
 and consider the sign of
 to decide about the direction of the next rotation.
There are two points that need to be further clarified here: first, as you may have noticed, we have to know the angle of each iteration,

. For example, if we design a twelve-iteration algorithm, the value of the first twelve angles which satisfy
 should be stored in a lookup table (you can see this lookup table in Figure 3).
Second, the algorithm will perform the same number of iterations for any given

. For example, although
is exactly equal to
, the algorithm will not stop with three iterations because this will require a different scaling factor (with three iterations
will not be
!). In this case, three iterations will lead to
but the algorithm will continue until all the iterations are performed so that
is
and
is within the acceptable range.
The following figure shows the implementation of a single iteration in the CORDIC algorithm:


Figure 3. Implementation of Equation 9 for one iteration. Image courtesy of UCLA (PDF).

A Numerical Example

As an example, we will apply the CORDIC algorithm to calculate the sine and cosine of

with
iterations. As previously mentioned, to calculate the sine and cosine with rotation, we have to choose
and
. The following table shows how the set of expressions in Equation 10 are evaluated for this example:

Iteration (
)
- -

Now we can take the scaling factor into account:

which is pretty close to the
. The y component gives the sine of
equal to
 which is a very good approximation of
.
As mentioned previously, we can sometimes avoid multiplication by the scaling factor. This is possible in the above example. To this end, we can apply the scaling factor to the initial values and start from

and
so that the final multiplication is omitted. In other words, since the initial values are constants, the application of the scaling factor merely changes the constants that are used.

Share this:

ABOUTME

Hi all. This is deepak from Bthemez. We're providing content for Bold site and we’ve been in internet, social media and affiliate for too long time and its my profession. We are web designer & developer living India! What can I say, we are the best..

Post a Comment
My photo

Hi, I`m Sostenes, Electrical Technician and PLC`S Programmer.
Everyday I`m exploring the world of Electrical to find better solution for Automation. I believe everyday can become a Electrician with the right learning materials.
My goal with BLOG is to help you learn Electrical.

Labels

LEKULE TV EDITORIALS ARTICLES DC ROBOTICS DIGITAL SEMICONDUCTORS GENERATOR AC EXPERIMENTS MANUFACTURING-ENGINEERING REFERENCE FUNDAMENTAL OF ELECTRICITY ELECTRONICS ELECTRICAL ENGINEER MEASUREMENT TRANSDUCER & SENSOR VIDEO ARDUINO RENEWABLE ENERGY AUTOMOBILE TEARDOWN SYNCHRONOUS GENERATOR DIGITAL ELECTRONICS ELECTRICAL DISTRIBUTION CABLES AUTOMOTIVE MICROCONTROLLER SOLAR PROTECTION DIODE AND CIRCUITS BASIC ELECTRICAL ELECTRONICS MOTOR SWITCHES CIRCUIT BREAKERS CIRCUITS THEORY PANEL BUILDING ELECTRONICS DEVICES MIRACLES SWITCHGEAR ANALOG MOBILE DEVICES WEARABLES CAMERA TECHNOLOGY COMMUNICATION GENERATION BATTERIES FREE CIRCUITS INDUSTRIAL AUTOMATION SPECIAL MACHINES ELECTRICAL SAFETY ENERGY EFFIDIENCY-BUILDING DRONE CONTROL SYSTEM NUCLEAR ENERGY SMATRPHONE FILTER`S POWER BIOGAS BELT CONVEYOR MATERIAL HANDLING RELAY ELECTRICAL INSTRUMENTS ENERGY SOURCE PLC`S TRANSFORMER AC CIRCUITS CIRCUIT SCHEMATIC SYMBOLS DDISCRETE SEMICONDUCTOR CIRCUITS WIND POWER C.B DEVICES DC CIRCUITS DIODES AND RECTIFIERS FUSE SPECIAL TRANSFORMER THERMAL POWER PLANT CELL CHEMISTRY EARTHING SYSTEM ELECTRIC LAMP FUNDAMENTAL OF ELECTRICITY 2 BIPOLAR JUNCTION TRANSISTOR 555 TIMER CIRCUITS AUTOCAD BLUETOOTH C PROGRAMMING HOME AUTOMATION HYDRO POWER LOGIC GATES OPERATIONAL AMPLIFIER`S SOLID-STATE DEVICE THEORRY COMPUTER DEFECE & MILITARY FLUORESCENT LAMP INDUSTRIAL ROBOTICS ANDROID ELECTRICAL DRIVES GROUNDING SYSTEM CALCULUS REFERENCE DC METERING CIRCUITS DC NETWORK ANALYSIS ELECTRICAL SAFETY TIPS ELECTRICIAN SCHOOL ELECTRON TUBES FUNDAMENTAL OF ELECTRICITY 1 INDUCTION MACHINES INSULATIONS USB ALGEBRA REFERENCE HMI[Human Interface Machines] INDUCTION MOTOR KARNAUGH MAPPING USEUL EQUIATIONS AND CONVERSION FACTOR ANALOG INTEGRATED CIRCUITS BASIC CONCEPTS AND TEST EQUIPMENTS DIGITAL COMMUNICATION DIGITAL-ANALOG CONVERSION ELECTRICAL SOFTWARE GAS TURBINE ILLUMINATION OHM`S LAW POWER ELECTRONICS THYRISTOR BOOLEAN ALGEBRA DIGITAL INTEGRATED CIRCUITS FUNDAMENTAL OF ELECTRICITY 3 PHYSICS OF CONDUCTORS AND INSULATORS SPECIAL MOTOR STEAM POWER PLANTS TESTING TRANSMISION LINE C-BISCUIT CAPACITORS COMBINATION LOGIC FUNCTION COMPLEX NUMBERS CONTROL MOTION ELECTRICAL LAWS INVERTER LADDER DIAGRAM MULTIVIBRATORS RC AND L/R TIME CONSTANTS SCADA SERIES AND PARALLEL CIRCUITS USING THE SPICE CIRCUIT SIMULATION PROGRAM AMPLIFIERS AND ACTIVE DEVICES APPS & SOFTWARE BASIC CONCEPTS OF ELECTRICITY CONDUCTOR AND INSULATORS TABLES CONDUITS FITTING AND SUPPORTS ELECTRICAL INSTRUMENTATION SIGNALS ELECTRICAL TOOLS INDUCTORS LiDAR MAGNETISM AND ELECTROMAGNETISM PLYPHASE AC CIRCUITS RECLOSER SAFE LIVING WITH GAS AND LPG SAFETY CLOTHING STEPPER MOTOR SYNCHRONOUS MOTOR AC METRING CIRCUITS BECOME AN ELECTRICIAN BINARY ARITHMETIC BUSHING DIGITAL STORAGE MEMROY ELECTRICIAN JOBS HEAT ENGINES HOME THEATER INPECTIONS LIGHT SABER MOSFET NUMERATION SYSTEM POWER FACTORS REACTANCE AND IMPEDANCE INDUCTIVE RECTIFIER AND CONVERTERS RESONANCE SCIENTIFIC NOTATION AND METRIC PREFIXES SULFURIC ACID TROUBLESHOOTING TROUBLESHOOTING-THEORY & PRACTICE 12C BUS APPLE BATTERIES AND POWER SYSTEMS DC MOTOR DRIVES ELECTROMECHANICAL RELAYS ENERGY EFFICIENCY-LIGHT INDUSTRIAL SAFETY EQUIPMENTS MEGGER MXED-FREQUENCY AC SIGNALS PRINCIPLE OF DIGITAL COMPUTING QUESTIONS REACTANCE AND IMPEDANCE-CAPATIVE SEQUENTIAL CIRCUITS SERRIES-PARALLEL COMBINATION CIRCUITS SHIFT REGISTERS WIRELESS BUILDING SERVICES COMPRESSOR CRANES DIVIDER CIRCUIT AND KIRCHHOFF`S LAW ELECTRICAL DISTRIBUTION EQUIPMENTS 1 ELECTRICAL DISTRIBUTION EQUIPMENTS B ELECTRICAL TOOL KIT ELECTRICIAN JOB DESCRIPTION INDUSTRIAL DRIVES LAPTOP SCIENCE THERMOCOUPLE TRIGONOMENTRY REFERENCE UART oscilloscope BIOMASS CONTACTOR ELECTRIC ILLUMINATION ELECTRICAL SAFETY TRAINING ELECTROMECHANICAL FEATURED FILTER DESIGN HARDWARE JUNCTION FIELD-EFFECT TRANSISTORS NASA NUCLEAR POWER VALVE COLOR CODES ELECTRIC TRACTION FLEXIBLE ELECTRONICS FLUKE GEARMOTORS INTRODUCTION LASSER PID PUMP SEAL ELECTRICIAN CAREER ELECTRICITY SUPPLY AND DISTRIBUTION MUSIC NEUTRAL PERIODIC TABLES OF THE ELEMENTS POLYPHASE AC CIRCUITS PROJECTS REATORS SATELLITE STAR DELTA VIBRATION WATERPROOF