FPGA Implementation of Sine and Cosine Value

Generators using Cordic Algorithm for Satellite

Attitude Determination and Calculators
Shoaib Bhuria, Student Member, IEEE, and P.Muralidhar, Member, IEEE

very important in attitude determination and control process

Abstract-- The trigonometric functions sine and cosine have [8].
found numerous applications in various areas. For Satellites, the For systems such as Calculator, keeping the size of
smallest category envisioned is the “femptosat” which would calculator very small is of prime importance. For these
weigh less than one-tenth of a kilogram, a satellite that would
systems the cost (eg. chip gate count has to be minimized) is
handle very simple missions and would be implemented on a
single chip. One of the elementary things required in these more important than speed. Also it is very important to
satellites is the Satellite Attitude Determination System. The calculate the values with good accuracy and precision.
Satellite Attitude Determination system requires the calculation Though sometimes by increasing the bit length we can
of sine and cosine values with good accuracy. Normally these obtain better precision, but it is more important to select a
values are calculated using a software. In this paper using method which gives more accurate results.
Coordinate Rotation Digital Computer (CORDIC) algorithm we
This paper presents an architecture which is very suitable
propose an architecture for the calculation of sine and cosine
values which is much faster than the software counterpart and for systems such as Satellite Attitude Determination and
also occupies very small area on the chip. This architecture is also Calculators with an eye towards implementation in Field
suitable for systems like calculator where the chip count has to be Programmable Gate Arrays (FPGAs).
reduced. Also this approach uses a very small lookup table In the next section we have described various methods used
resulting into very small memory requirement. for the calculation of sine and cosine. Then in the third section
we explain the mathematical basis of Cordic Algorithm. In the
Index Terms— Cordic, Cosine, FPGA, Sine.
fourth section we present our approach, in the fifth section we
present the Architecture and finally in the sixth and seventh
section we present our results and conclusions respectively.
I. INTRODUCTION

T HE Trigonometric functions sine and cosine have found

applications in various places such as Navigation systems
[1], digital signal processing [2], robot control [3], software
II. COMPUTATION OF SINE AND COSINE
The Computation of sine and cosine values can be done by
various methods. They are:
radio [4], math processors [5] etc.
1. Taylor Series
Satellites are generally classified by weight with standard
2. Lookup Table Method
ones weighing a ton or more, small satellites coming in
3. Cordic Algorithm
between 100 kilograms and a ton, and microsats that fall
between 10 and 100 kilograms. The upcoming new wave of A. Taylor Series
smaller satellites currently in the pipeline are nanosatellites The Taylor series expansion for sine is:
ranging from 10 kilograms down to 1 kilogram and
x3 x 5 x 7
picosatellites that weigh less than 1 kilogram. The smallest sin( x ) = x − + − + ..... (1)
category envisioned is the “femptosat” which would weigh 3! 5! 7!
less than one-tenth of a kilogram, a satellite that would handle This method is one of the oldest and most widely, but the
very simple missions and would be implemented on as single problem associated with this method is, to get values of higher
chip and hence known as Satellite on a Chip [6]. accuracies, higher order factorial and power has to be
The Earth's Magnetic Field is a very computationally calculated [9]. Moreover to implement this we would at least
intensive procedure in satellite attitude determination and is require a multiplier, divider, adder and a subtractor. For good
usually implemented in software [7]. Satellite Attitude accuracy it would be required to take each term in calculation
determination systems require good accuracy and speed as till they become insignificant. Thus this approach has a lot of
Attitude accuracy, which is also known as pointing accuracy is hardware requirements as well as it is slow.
B. Look up Table
Authors are with the Department of Electronics and Communication
Engineering, National Institute of Technology, Warangal-506004, India (e- The Lookup table approach involves storing values of sine
mail: [email protected], [email protected]) and cosine at different angles. Based on the number of values

978-1-4244-8542-0/10/$26.00 ©2010 IEEE

 2

stored, the lookup table can be big or small, but clearly, the Therefore, the angle for which we want to know the sine and
smaller the lookup table, more is the error involved. The cosine value can be obtained by simply rotating the point to
problem with a bigger lookup table is that it requires more the target angle. The rotation can be in a single step or a series
memory and memory is expensive. Moreover the size of the of small steps which may be either clock wise or anti-
Lookup table increases exponentially with the increase in the clockwise.
precision of the angle. Though this approach provides fast The rotation of a point in two dimensional space can be
results it is very expensive to implement. given by the rotation matrix which is:

C. Cordic Algorithm
 x '   x  cos θ − sin θ 
CORDIC is an acronym for Coordinate Rotation Digital   =    (2)
Computer introduced by Jack E. Volder [1]. It is an iterative  y '   y  sin θ cos θ 
algorithm capable of calculating trigonometric and various
other functions. In this algorithm with the help of an This matrix operation can be expressed by mathematical
adder/subtractor, a small look up table and a shifter the operations as follows:
trigonometric functions can be calculated very easily. The x ' = x cos θ − y sin θ (3)
advantage that Cordic offers over other algorithms is that it y ' = y cos θ + x sin θ (4)
does not require multiplication or division blocks, instead it
works only with a shifter, adder/subtractor and a small lookup
Therefore, in each iteration the coordinates are rotated and in
table. This reduces the hardware requirement drastically and
the i+1th rotation coordinates are given by:
provides reasonably good speed.
xi +1 = xi cos θ i +1 − yi sin θ i +1 (5)
The main constraint in System on chip design is the amount yi +1 = yi cos θ i +1 + xi sin θ i +1 (6)
of on chip memory and this constraint is equally valid in
System on chip prototyping using programmable logic [6]. Now if we divide by cos θ i +1 we get:
Hence using Cordic Algorithm we can minimize the memory xi +1
requirements. = xi − yi tan θ i +1 (7)
cos θi +1
III. MATHEMATICAL BASIS OF CORDIC ALGORITHM yi +1
= yi + xi tan θ i +1 (8)
There are two forms of the Cordic Algorithm - Vectoring cos θi +1
and Rotation mode. In vectoring mode, the coordinates (x0,y0)
are rotated until y0 converges to zero. In the rotation mode the Therefore,
coordinates (x0,y0) are initially aligned with the x- axis and
xi +1 = cos θ i +1 ( xi − yi tan θ i +1 ) (9)
they are rotated by an angle of θ i every cycle until it reaches
the target angle or close to the target angle. yi +1 = cos θ i +1 ( yi + xi tan θ i +1 ) (10)
For the Architecture proposed we have used the rotation
mode to calculate sine and cosine values. Now if tan θi +1 is restricted to ±2− i , then the
Suppose that we have a point on a unit circle then by Fig 1.
multiplication is converted into an arithmetic right shift.
we can conclude that the coordinates can be given
by (cos θ ,sin θ ) where θ is the angle made by the line Therefore we have:
joining the point and the center with the x-axis.
tan θ i +1 = ±2− i (11)
y - axis
θi +1 = tan −1 (±2 − i )
(cos θ ,sin θ )
Now taking Cosine of θi +1 we get:
cos(θi +1 ) = cos(tan −1 (±2− i )) (12)
−1 1
As cos(tan ( x )) =
x - axis 1 + x2
We have,
1
cos(tan −1 (±2−1 )) = = Ki
1 + 2 −2i (13)
Now we can write (9) and (10) as:
Fig 1. A point on unit circle rotated by an angle θ xi +1 = K i ( xi − yi d i 2 − i ) (14)
−i
yi +1 = K i ( yi + xi di 2 ) (15)
 3

d i gives the direction of rotation and d i = ±1 . If d i is clock cycle. Also a control unit is used for coordinating the
activities and finally a lookup table is used for storing the
positive it means direction of rotation is anti clockwise and if values.
it is negative it means direction of rotation is clockwise.
Multiplication with Ki can be avoided by considering it as
a multiplication factor for all the iterations. Therefore, for n
iterations K is given by the product of every Ki .
K = K 0 * K1 * K 2 *.....* K15 = 0.6073
Hence, it is possible to break our rotations into many steps,
each of decreasing size and have each step such that tan θ is
1
a power of . This would allow us the multiplication by
2
tan θ operation to be substituted by a simple bit shift
operation.

IV. APPROACH Fig 2. Architecture for our design

We use the two's Complement for the representation of the
data. Now since the sine and cosine values are in decimal it is ANGLE is the input for which we are calculating the sine
not possible to represent them accurately with the fixed point and cosine values.
approach. Therefore we represent the data in the form of
integers. For example Sin(45)=0.7071, now it is not possible
to represent this value accurately using the fixed point format. RESC
Instead represent it by 7071. But now the number of bits
required to represent the data would increase with greater EC COUNTER COUNT
precision.
Since we use two’s complement representation of data we CLOCK
will be using the most significant bit of the angle to determine
the direction of the next rotation over. If the most significant Fig 3. Counter
bit is zero then it means the angle is positive and therefore the
next rotation will be in anti-clockwise direction. If the most RESET is used for resetting the system. RESC is used for
significant bit is one then the angle is negative and hence the resetting the counter. EC is used to enable the counter. ASX,
direction of the next rotation will be clockwise. ASA, ASY decide whether the arithmetic operation will be
Also we have to multiply the multiplication factor to get the addition or subtraction. SEL is used for controlling the
coordinates, but to multiply it would require a multiplier, in multiplexer. If SEL is zero then the registers are loaded with
order to avoid that, we multiply the multiplication factor the initial values, else if it is one then they are loaded with the
before we start the rotation of coordinates, hence we multiply value obtained after arithmetic operations. COUNT indicates
0.6073 with (1,0) to obtain (0.6073,0). So now the rotation the number of iterations that are over. AMSB is used to decide
starts from (0.6073,0). that whether the next rotation has to be clockwise or anti
The Architecture is presented in the next section and we use clockwise.
two's complement representation to represent the data.

V. ARCHITECTURE RESET RESC

The Architecture proposed consists of three Registers, three
CLOCK EC
Adders/Subtractors, three 2X1 MUX, two Barrel Shifters, a
Lookup Table, a Counter, a Clock and a Control Unit.
CONTROL
COUNT ASX
It is a sequential design and hence we have used a clock and
a control unit. This architecture presents the implementation of UNIT
AMSB ASA
Iterative Cordic and it can be extended to any number of
iterations without a considerable increase in the size of the
ASY
components used.
A Multiplexer is used for selecting either the initial value or
SEL
the value obtained after subsequent steps of calculation. Three
registers are used for storing the value of x, y and θ . Each
adder/subtractor is related to either x, y or θ . Fig 4. Control unit
Also a Counter is used for counting the no of iterations. The
Barrel shifter is used to achieve the required no of shifts in one
 4

VI. RESULTS
TABLE II
All of the modules were written in VHDL and the simulation XILINX FPGA IMPLEMENTATION RESULTS
was done on Altera's Quartus II 9.0 as well as Xilinx ISE 12.1
for 16 iterations, 16 bit system. Finally the design was Parameter Used Percentage
implemented on Altera's FPGA EP2C35F672C6 of Cyclone II
No. of Slices 157 8
family and Xilinx's xc3s200-5ft256. The implementation
results on Altera's FPGA are given in the table below: No. of Slice Flip Flops 110 2
No. of 4 input Lookup Tables 299 7
TABLE I
ALTERA FPGA IMPLEMENTATION RESULTS
No. of GCLKS 2 25

The Device utilization summary for the work done in [10] for
Parameter Used Available
the Area optimization is:
Logic Elements 417 33216
TABLE III
Dedicated Logic Registers 55 33216 RESULTS FOR WORK DONE IN [10]
Total Memory Bits 272 483840
Parameter Used Percentage
The time taken for the Computation of Sine and Cosine No. of Slices 1075 55
values was 400ns. No. of Slice Flip Flops 570 14
A program was written in C++ for the calculation of sine No. of 4 input Lookup Tables 1737 44
and cosine for the same no of iterations. On executing the No. of GCLKS 1 12
program on a 2GHZ T7300 processor, it was found that the
time taken to compute the sine and cosine value was 11ms. Though the work done in [10] offers much higher speed but
Therefore our approach is 27500 times faster than the software at the same time it also takes up much more area, but for
approach. systems such as calculator where the chip count has to be
Also a graph was plotted using Matlab for the error in sine reduced we have to go for an approach which takes least
and cosine values obtained for different angles. The graph is amount of area. Moreover for calculators, it is not an issue
given below : even if the time taken to compute these values is in
microseconds since human beings do not respond that fast.

VII. CONCLUSION
Therefore an architecture of iterative Cordic is presented for
systems such as calculator and Satellite Attitude
determination. For Calculators it provides a very area efficient
system as well as accurate results and for the Satellite Attitude
determination systems it gives results as fast as 27500 times
than the traditional software approach. Implementation results
on Altera's EP2C35F672C6 of Cyclone II family and Xilinx's
xc3s200-5ft256 are presented. Finally our work has been
compared with the work done in [9] and [10].

VIII. REFERENCES

[1] J.E.Volder, “The CORDIC Trigonometric Computing Technique,”IRE

Trans. Electronic Computers, vol. EC-8, pp. 330-334, Sept. 1959
[2] Y.H. Hu, “CORDIC-based VLSI architectures for digital signal
processing,” IEEE Signal Processing Magazine, vol. 9, no.3, pp.16-35,
July 1992.
Fig 5. Error in sine and cosine values for different angles
[3] R. G. Harber, X.Hu, J. Li, and S.C. Bass, “The application of bit-serial
CORDIC computational units to the design of inverse kinematics
processors,” in Proc. 1988 IEEE Int. Conf. Robot. Automat., vol.2 ,
The memory utilization in our design is only 34 bytes. pp.1152-1157.
Though a special algorithm has been developed in [9] for the [4] J. Valls, T. Sansaloni, A. Perez-Pascual, V.Torres, V. Almenar, “The
software approach, it uses 4K memory which cannot be Use of CORDIC in Software Defined Radios: A Tutorial,” IEEE
Communications Magazine, vol. 44, no.9, pp.46-50, Sept. 2006
suitable for on-chip implementation. [5] J. Duprat and J. M. Muler, “The CORDIC Algorithm : New Results for
Moreover sine and cosine calculation is just a basic Fast VLSI Implementation,” IEEE Transactions on Computers, Vol. 42,
requirement for satellite attitude determination, therefore it is pp.168-178,1993.
very important that it does not take up most of the resources [6] Hans Tiggeler, Tanya Vladimirova, Daixun Zheng, Jiri Gaisler,
“Experiences Designing a System-on-a-Chip for Small Satellite Data
on the chip. Hence our architecture is perfect for Satellite Processing and Control,” Surrey Space Center, University of Surrey,
Attitude Determination. Guildford, Surrey, GU2 7XH. [Online]. Available:
The Device Utilization Summary on Xilinx's FPGA is:
 5

http://klabs.org/richcontent/MAPLDCon00/Papers/Session_P/P20_Tigg [Online]. Available: http://stellarforce.com/SF%20webINFO%20SPS

eler_P.pdf. M5000TP.doc
[7] Tanya Vladimirova and Hans Tiggeler, “FPGA Implementation of Sine [9] Sahabaz Kathewadi, “FSCA: Fast Sine calculating Algorithm,” in Proc.
and Cosine Value Generators using the Cordic Algorithm,” Surrey 2009 IEEE International Advance Computing Conf., pp. 165 -170
Space Center, University of Surrey, Guildford, Surrey. [Online]. [10] Esteban O.Garcia, Rene Cumplido, Miguel Arias, “ Pipelined CORDIC
Available: Design on FPGA for a Digital Sine and Cosine Waves Generator,” in
http://klabs.org/richcontent/MAPLDCon99/Papers/A2_Vladimirova_P.p Proc. 2006 IEEE 3rd International Conference on Electrical and
df. Electronics Engineering, pp 1-4
[8] Joseph A. DiPentino, “Spacecraft Attitude Determination and Control
Systems,” Webster University Space Systems Operations Management.