MicroZed Chronicles: The CORDIC Algorithm
In final weeks weblog, we checked out probably the most vital algorithms ever developed: the FFT. On this week’s weblog, we’ll be discussing the CORDIC algorithm, which is analogous in significance to the FFT.
Brief for COordinate Rotation DIgital Laptop, the CORDIC algorithm, invented by Jack Volder for the B58 program in 1959, is without doubt one of the most vital algorithms in an FPGA engineer’s instrument field and one which few are conscious of. Engineers have nearly actually used outcomes calculated by a scientific calculator just like the HP35, and this observe continues with present-day calculators, which use the algorithm for trigonometric and exponential features. Nonetheless, it’s critically vital to grasp the CORDIC algorithm as effectively. The true great thing about the CORDIC algorithm is that it may be carried out with a really small FPGA footprint and requires solely a small lookup desk together with logic to carry out shifts and additions. Equally vital is that the algorithm requires no devoted multipliers or dividers to implement.
This algorithm is without doubt one of the most helpful for DSP and industrial management purposes and may also implement some very helpful mathematical features relying on its mode and configuration. The CORDIC algorithm can function in certainly one of three configurations: linear, round or hyperbolic. Inside every of those configurations, the algorithm features in certainly one of two modes: rotation or vectoring. In rotation mode, the enter vector is rotated by a specified angle. In vector mode, the algorithm rotates the enter vector to the x axis whereas recording the angle of rotation required.
The unified CORDIC algorithm may be seen under and covers all three configurations. It has three inputs (X, Y and Z) and the way these are initialized at begin up is determined by the mode of operation (vectoring or rotation)
The place m defines the configuration for both hyperbolic (m = -1), linear (m = 0) or round (m = 1), the worth of ei, which notes the angle of rotation, modifications relying upon the configuration. The worth of ei is generally carried out as a small lookup desk throughout the FPGA.
di is the course of rotation which relies upon upon the mode of operation for rotation mode di = -1 if Zi < 0 else +1, whereas in vectoring mode di = +1 if Yi < 0 else -1.
When configured in both round or hyperbolic and utilizing rotation mode, the output outcomes may have acquire which may be pre calculated utilizing the variety of rotations outlined utilizing the next equation.
This acquire is often fed again into the preliminary setting of the algorithm to take away the necessity for put up scaling of the outcome.
Whereas the algorithm offered above is essential to the design engineer, it must be famous that the CORDIC algorithm solely operates inside a strict convergence zone, which can require the engineer to carry out some pre-scaling to make sure the algorithm performs as anticipated. It’s price noting that the algorithm will get extra correct with each iteration (serial) or stage (parallel) the engineer decides to implement. A common rule of thumb is that for n bits of precision, n iterations or levels are required.
The CORDIC algorithm will solely converge (work) throughout a restricted vary of enter worth. For round configurations of CORDIC algorithms, convergence is assured for the angles under the sum of the angles within the lookup desk (i.e. between -99.7 and 99.7 levels). For angles exterior of this, the engineer should use a trigonometric identification to translate one inside. That is additionally true for convergence throughout the linear configuration. In hyperbolic mode, nevertheless, sure iterations should be repeated (4, 13, 40, Ok… 3K+1) to realize convergence. On this case, the utmost enter of Ɵ is roughly 1.118 radians.
Like beforehand acknowledged, CORDICs are utilized in a variety of purposes from DSP and picture processing to industrial management methods. Probably the most primary methodology of utilizing a CORDIC is to generate sine and cosine waves when coupled with a part accumulator. The usage of the algorithm to generate these waveforms can, if executed appropriately, lead to a excessive spurious free dynamic vary (SFDR). It’s vital to notice that good SFDR efficiency is required for many sign processing purposes. Throughout the subject of robotics, CORDICs are utilized in kinematics the place the addition of coordinate values with new coordinate values may be simply completed by means of a round CORDIC in vectoring mode. Throughout the subject of picture processing, three dimensional operations resembling lighting and vector rotation are excellent candidates for algorithm implementation. Nonetheless, maybe the most typical use of the algorithm is within the implementation of conventional mathematical features as proven in desk one. Right here we see that multipliers, dividers, or extra attention-grabbing mathematical features are required in units the place there aren’t any devoted multipliers or DSP blocks. Which means CORDICs are utilized in many small industrial controllers to implement mathematical switch features. True RMS measurement is one such instance.
Implementation inside an FPGA
Relating to implementing a CORDIC inside our AMD FPGA, we are able to implement the CORDIC IP block that comes with Vivado. This module offers a variety of configurations to implement vectoring, rotation, and sine and cosine technology together with assist for hyperbolic and sq. root operations.
To conclude this text, we’re going to configure the module to generate sine and cosine vectors and simulate it to grasp extra about its operation. We’ll lengthen the take a look at bench to take a look at different options in a future weblog.
When working within the sine and cosine mode, we have to guarantee the choice for coarse rotation is checked if we would like to have the ability to cowl the complete circle. If this isn’t checked, we’re restricted to the -Pi/4 to Pi/. With it chosen, we’re in a position to full a full circle.
The block diagram appears as under.
With the easy design created, I made a easy take a look at bench which inputs values utilizing the AXIS. The enter format of this vector is 3 signed integer bits with the rest fractional. This permits values between +/- Pi to be enter.
Whereas the output vector is formatted as a 1 bits signed integer bit with the rest fractional, this permits values between -1 and 1 to be output and the sine and cosine outputs are shared on the output vector.
The take a look at bench may be very straight ahead and makes use of a counter to rely frequently between -pi and pi and is utilized because the part enter to the CORDIC IP core.
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
use UNISIM.VComponents.all;
structure Behavioral of cordic_tb is
fixed clk_period : time := 10 ns;
fixed increment : actual := 0.01256637;
sign M_AXIS_DOUT_0_tdata : STD_LOGIC_VECTOR ( 31 downto 0 );
sign M_AXIS_DOUT_0_tvalid : STD_LOGIC;
sign S_AXIS_PHASE_0_tdata : STD_LOGIC_VECTOR ( 15 downto 0 );
sign S_AXIS_PHASE_0_tvalid : STD_LOGIC := '0';
sign clk : STD_LOGIC := '0';
sign phase_wheel : actual vary -MATH_PI to MATH_PI ;
sign course : std_logic := '0';
clk <= not clk after (clk_period/2);
M_AXIS_DOUT_0_tdata => M_AXIS_DOUT_0_tdata,
M_AXIS_DOUT_0_tvalid => M_AXIS_DOUT_0_tvalid,
S_AXIS_PHASE_0_tdata => S_AXIS_PHASE_0_tdata,
S_AXIS_PHASE_0_tvalid => S_AXIS_PHASE_0_tvalid,
S_AXIS_PHASE_0_tvalid <= '1';
S_AXIS_PHASE_0_tdata <= std_logic_vector(to_sfixed(phase_wheel, 2,-13 )) ;
if phase_wheel >= MATH_PI and course = '0' then
elsif phase_wheel <= -MATH_PI and course = '1' then
phase_wheel <= phase_wheel - increment;
phase_wheel <= phase_wheel + increment;
Operating this within the take a look at bench offers the next output in Vivado simulator.
In a future weblog, we are going to look deeper at exploiting this for numerous purposes, however till then, we now know extra in regards to the CORDIC algorithm!
If you happen to loved the weblog why not check out the free webinars, workshops and coaching programs we have now created over time. Highlights embrace
Embedded System Guide
Do you need to know extra about designing embedded methods from scratch? Try our e book on creating embedded methods. This e book will stroll you thru all of the levels of necessities, structure, element choice, schematics, structure, and FPGA / software program design. We designed and manufactured the board on the coronary heart of the e book! The schematics and structure can be found in Altium here Study extra in regards to the board (see earlier blogs on Bring up, DDR validation, USB, Sensors) and think about the schematics here.