Start > Misc. > CORDIC Simulation to estimate effective bits

CORDIC Simulation to estimate effective bits

Overview

Author	Dominik Auras
Type	Matlab Simulation Code
State	Done
Features	Fast simulation of bit arithmetic using integer arithmetic Evaluation of effective bits

Introduction

See CORDIC on Wikipedia (en)

The CORDIC algorithm is widely used, especially in places where we cannot do multiplications. One example working area for this algorithm are implementations on hardware, for example on FPGAs. These implementation involve by force the use of finite-length arithmetic. If we are area constraint, the decision on the bitwidth is a crucial part as this increases the size of both arithmetic units and storage elements.

The chosen bitwidth of our data paths additionally controls the precision of the implementation. Several authors revealed the different error sources, as there are to be mentioned the approximation error due to the approximation of the rotation angle and the quantization error caused by finite length arithmetic.

The following simulation provides a tool to estimate the effective bits for different parameter settings. This allows to choose an optimal parameter set depending on your application demands.

Implementation

First the input values are generated. We generate sets of uniformly distributed random values in the range [-1,1]. There are 50 angle steps in the range of [0,pi*49/50] with a stepsize of 1/50*pi. Every angle together with one set of X/Y input values is used as input to the simulation.

Next the simulation converts all values to their representation in the desired finite length bitvectors. Then we start applying the algorithm with first doing an initial rotation of 180° (scale-free first iteration) if our angle falls outside the range we can reach (+- ~99° -> +-90°). For every stage, one iteration of the CORDIC is performed. For emulation of the shift operator, the matlab function idivide is used. This functions performs integer division with rounding towards zero. That is, it discards the fractional bits.

The final results are converted into floating point numbers. We compute the reference values using floating point numbers. These are assumed to be "precise". The reference and the result are compared and the squared error is computed. These squared error values are collected in the main program. After one complete simulation run, we calculate the SNR. For the signal power, we use the theoretic formula for uniformly distributed random values, while for the error power, we select the highest squared error value.

Under the assumption that our input and the error is uniformly distributed, the SNR is a function of the effective bits. The theoretic formula reveals that the SNR increases by ~6dB per additional bit. Therefore, we estimate the effective bits by dividing the SNR with 6dB.

The main script iterates over an area of parameters, varying both the input X/Y bitwidth and the number of stages. The Z width is set to be constant. But of course, this can be modified too. The final results are presented with a mesh plot and overlayed contours.

I hope this code is useful to someone and might be a good starting point if you want to do further investigations on this topic. Feel free to experiment. If you find any error, please let me know!

Results

References

Uwe Meyer-Baese, "Digital Signal Processing with Field Programmable Gate Arrays", Third Edition, Springer-Verlag

Yu Hen Hu, "The Quantization Effects of the CORDIC Algorithm", IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 40, NO. 4, APRIL 1992

Sang Yoon Park and Nam Ik Cho, "Fixed-Point Error Analysis of CORDIC Processor Based on the Variance Propagation Formula",IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-I: REGULAR PAPERS, VOL. 51, NO. 3, MARCH 2004

Herbert Dawid and Heinrich Meyr, "CORDIC Algorithms and Architectures"

License

This work is licensed under the terms of the GPL.

Sourcecode

Archive with Matlab code	TAR-Archive 2008-06-12 14.1kb