FixedPoint Designer 

This example shows how to compute square root using a CORDIC kernel algorithm in MATLAB®. CORDICbased algorithms are critical to many embedded applications, including motor controls, navigation, signal processing, and wireless communications.
On this page… 

CORDIC Kernel Algorithms Using Hyperbolic Computation Modes MATLAB Implementation of a CORDIC Hyperbolic Vectoring Algorithm CORDICBased Square Root Computation 
CORDIC is an acronym for COordinate Rotation DIgital Computer. The Givens rotationbased CORDIC algorithm (see [1,2]) is one of the most hardware efficient algorithms because it only requires iterative shiftadd operations. The CORDIC algorithm eliminates the need for explicit multipliers, and is suitable for calculating a variety of functions, such as sine, cosine, arcsine, arccosine, arctangent, vector magnitude, divide, square root, hyperbolic and logarithmic functions.
The fixedpoint CORDIC algorithm requires the following operations:
1 table lookup per iteration
2 shifts per iteration
3 additions per iteration
Note that for hyperbolic CORDICbased algorithms, such as square root, certain iterations (i = 4, 13, 40, 121, ..., k, 3k+1, ...) are repeated to achieve result convergence.
CORDIC Kernel Algorithms Using Hyperbolic Computation Modes
You can use a CORDIC computing mode algorithm to calculate hyperbolic functions, such as hyperbolic trigonometric, square root, log, exp, etc.
CORDIC EQUATIONS IN HYPERBOLIC VECTORING MODE
The hyperbolic vectoring mode is used for computing square root.
For the vectoring mode, the CORDIC equations are as follows:
where
if , and otherwise.
This mode provides the following result as approaches :
where
.
Typically is chosen to be a largeenough constant value. Thus, may be precomputed.
Note also that for square root we will use only the result.
MATLAB Implementation of a CORDIC Hyperbolic Vectoring Algorithm
A MATLAB code implementation example of the CORDIC Hyperbolic Vectoring Kernel algorithm follows (for the case of scalar x, y, and z). This same code can be used for both fixedpoint and floatingpoint data types.
CORDIC Hyperbolic Vectoring Kernel
k = 4; % Used for the repeated (3*k + 1) iteration steps
for idx = 1:n xtmp = bitsra(x, idx); % multiply by 2^(idx) ytmp = bitsra(y, idx); % multiply by 2^(idx) if y < 0 x(:) = x + ytmp; y(:) = y + xtmp; z(:) = z  atanhLookupTable(idx); else x(:) = x  ytmp; y(:) = y  xtmp; z(:) = z + atanhLookupTable(idx); end
if idx==k xtmp = bitsra(x, idx); % multiply by 2^(idx) ytmp = bitsra(y, idx); % multiply by 2^(idx) if y < 0 x(:) = x + ytmp; y(:) = y + xtmp; z(:) = z  atanhLookupTable(idx); else x(:) = x  ytmp; y(:) = y  xtmp; z(:) = z + atanhLookupTable(idx); end k = 3*k + 1; end end % idx loop
CORDICBased Square Root Computation
Square Root Computation Using the CORDIC Hyperbolic Vectoring Kernel
The judicious choice of initial values allows the CORDIC kernel hyperbolic vectoring mode algorithm to compute square root.
First, the following initialization steps are performed:
is set to .
is set to .
After iterations, these initial values lead to the following output as approaches :
This may be further simplified as follows:
where is the CORDIC gain as defined above.
Note: for square root, and atanhLookupTable have no impact on the result. Hence, and atanhLookupTable are not used.
MATLAB Implementation of a CORDIC Square Root Kernel
A MATLAB code implementation example of the CORDIC Square Root Kernel algorithm follows (for the case of scalar x and y). This same code can be used for both fixedpoint and floatingpoint data types.
CORDIC Square Root Kernel
k = 4; % Used for the repeated (3*k + 1) iteration steps
for idx = 1:n xtmp = bitsra(x, idx); % multiply by 2^(idx) ytmp = bitsra(y, idx); % multiply by 2^(idx) if y < 0 x(:) = x + ytmp; y(:) = y + xtmp; else x(:) = x  ytmp; y(:) = y  xtmp; end
if idx==k xtmp = bitsra(x, idx); % multiply by 2^(idx) ytmp = bitsra(y, idx); % multiply by 2^(idx) if y < 0 x(:) = x + ytmp; y(:) = y + xtmp; else x(:) = x  ytmp; y(:) = y  xtmp; end k = 3*k + 1; end end % idx loop
This code is identical to the CORDIC Hyperbolic Vectoring Kernel implementation above, except that z and atanhLookupTable are not used. This is a cost savings of 1 table lookup and 1 addition per iteration.
Example
Use the CORDICSQRT function to compute the approximate square root of v_fix using ten CORDIC kernel iterations:
step = 2^7; v_fix = fi(0.5:step:(2step), 1, 20); % fixedpoint inputs in range [.5, 2) niter = 10; % number of CORDIC iterations x_sqr = cordicsqrt(v_fix, niter); % Get the Real World Value (RWV) of the CORDIC outputs for comparison % and plot the error between the MATLAB reference and CORDIC sqrt values x_cdc = double(x_sqr); % CORDIC results (scaled by An_hp) v_ref = double(v_fix); % Reference floatingpoint input values x_ref = sqrt(v_ref); % MATLAB reference floatingpoint results figure; subplot(211); plot(v_ref, x_cdc, 'r.', v_ref, x_ref, 'b'); legend('CORDIC', 'Reference', 'Location', 'SouthEast'); title('CORDIC Square Root (InRange) and MATLAB Reference Results'); subplot(212); absErr = abs(x_ref  x_cdc); plot(v_ref, absErr); title('Absolute Error (vs. MATLAB SQRT Reference Results)');
Overcoming Algorithm Input Range Limitations
Many square root algorithms normalize the input value, , to within the range of [0.5, 2) range. This preprocessing is typically done using a fixed word length normalization, and can be used to support small as well as large input value ranges.
The CORDICbased square root algorithm implementation is particularly sensitive to inputs outside of this range. The function CORDICSQRT overcomes this algorithm range limitation through a normalization approach based on the following mathematical relationships:
, for some and some even integer .
Thus:
In the CORDICSQRT function, the values for and , described above, are found during normalization of the input . is the number of leading zero most significant bits (MSBs) in the binary representation of the input . These values are found through a series of bitwise logic and shifts. Note: because must be even, if the number of leading zero MSBs is odd, one additional bit shift is made to make even. The resulting value after these shifts is the value .
becomes the input to the CORDICbased square root kernel, where an approximation to is calculated. The result is then scaled by so that it is back in the correct output range. This is achieved through a simple bit shift by bits. The (left or right) shift direction dependends on the sign of .
Example
Compute the square root of 10bit fixedpoint input data with a small nonnegative range using CORDIC. Compare the CORDICbased algorithm results to the floatingpoint MATLAB reference results over the same input range.
step = 2^8; u_ref = 0:step:(0.5step); % Input array (small range of values) u_in_arb = fi(u_ref,0,10); % 10bit unsigned fixedpoint input data values u_len = numel(u_ref); sqrt_ref = sqrt(double(u_in_arb)); % MATLAB sqrt reference results niter = 10; results = zeros(u_len, 2); results(:,2) = sqrt_ref(:); % Compute the equivalent Real World Value result for plotting. % Plot the Real World Value (RWV) of CORDIC and MATLAB reference results. x_out = cordicsqrt(u_in_arb, niter); results(:,1) = double(x_out); figure; subplot(211); plot(u_ref, results(:,1), 'r.', u_ref, results(:,2), 'b'); legend('CORDIC', 'Reference', 'Location', 'SouthEast'); title('CORDIC Square Root (Small Input Range) and MATLAB Reference Results'); axis([0 0.5 0 0.75]); subplot(212); absErr = abs(results(:,2)  results(:,1)); plot(u_ref, absErr); title('Absolute Error (vs. MATLAB SQRT Reference Results)');
Example
Compute the square root of 16bit fixedpoint input data with a large positive range using CORDIC. Compare the CORDICbased algorithm results to the floatingpoint MATLAB reference results over the same input range.
u_ref = 0:5:2500; % Input array (larger range of values) u_in_arb = fi(u_ref,0,16); % 16bit unsigned fixedpoint input data values u_len = numel(u_ref); sqrt_ref = sqrt(double(u_in_arb)); % MATLAB sqrt reference results niter = 16; results = zeros(u_len, 2); results(:,2) = sqrt_ref(:); % Compute the equivalent Real World Value result for plotting. % Plot the Real World Value (RWV) of CORDIC and MATLAB reference results. x_out = cordicsqrt(u_in_arb, niter); results(:,1) = double(x_out); figure; subplot(211); plot(u_ref, results(:,1), 'r.', u_ref, results(:,2), 'b'); legend('CORDIC', 'Reference', 'Location', 'SouthEast'); title('CORDIC Square Root (Large Input Range) and MATLAB Reference Results'); axis([0 2500 0 55]); subplot(212); absErr = abs(results(:,2)  results(:,1)); plot(u_ref, absErr); title('Absolute Error (vs. MATLAB SQRT Reference Results)');
Jack E. Volder, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, Volume EC8, September 1959, pp330334.
Ray Andraka, A survey of CORDIC algorithm for FPGA based computers, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, Feb. 2224, 1998, pp191200