CORDIC sine/cosine

[hamster_nz]

I've been learning how CORDIC algorithms work to calculate SIN() and COS(), once you have the precomputed table it just uses bitshifts, additions and subtractions.

It's so I can make a 24-bit DDS for experimenting with my CS4434 I2S DAC board with an FPGA. Yes, I know I can do it easier, but it is a hobby learning project...

I must say, it is pretty nifty! What I really like is that you don't have to have the input angle in radians or degrees, you can have it in anything you like. It will tie up really nice with a binary phase accumulator.

Code is for calculating a sin() or cos() for the first quadrant (0 -> PI/2), just to make sure I understand the algorithm and checking the number of repetitions and bits required:

Code: [Select]

#include <stdio.h>
#include <math.h>
#include <stdint.h>

#define PI            (3.14159265358979323846)
#define FULL_CIRCLE   (2.0*PI)
#define EIGHTH_CIRCLE (FULL_CIRCLE/8)
#define CORDIC_REPS   (27)
#define BITS          (30)

int64_t initial;
double angles[CORDIC_REPS];
/****************************************************************
 * Calculate the values required for CORDIC sin()/cos() function
 ***************************************************************/
void setup(void) {
   int i;
   double scale = 1.0;
   for(i = 0; i < CORDIC_REPS; i++ ) {
     angles[i]  = atan(1.0/pow(2,i+1));
     scale     *= cos(angles[i]);
   }
   initial = (int64_t)(pow(0.5,0.5)*scale*pow(2.0,BITS)+0.5);
}

/***************************************************************
 * Cordic routine to calculate Sine and Cosine for angles
 * from 0.0 to a little over PI/2
 **************************************************************/
void cordic_sine_cosine(double z, int64_t *s, int64_t *c) {
   int i;
   int64_t x = initial,y = initial;
   z -= EIGHTH_CIRCLE;
   for(i = 0; i < CORDIC_REPS; i++ ) {
     int64_t tx = (x + (1<<i)) >> (i+1);
     int64_t ty = (y + (1<<i)) >> (i+1);
     x -= (z > 0 ?        ty :        -ty);
     y += (z > 0 ?        tx :        -tx);
     z -= (z > 0 ? angles[i] : -angles[i]);
   }
   *c = x;
   *s = y;
}

/**************************************************************/
int main(int argc, char *argv[]) {
  double a = 0.8;
  int64_t sll, cll;

  setup();
  for(a = 0; a <= PI/2; a += PI/40) {
    double s,c;
    cordic_sine_cosine(a, &sll, &cll);
    s = sll / pow(2,BITS);
    c = cll / pow(2,BITS);
    printf("Computed sin(%11.8f), cos(%11.8f), ", s, c);
    printf("error %11.8f & %11.8f\n",s-sin(a), c-cos(a));
  }
  return 0;
}
/**************************************************************/


[legacy]

Code: [Select]

cplx_fx32_t cordic_fx_trig
(
    fx32_t theta
)
{
    cplx_fx32_t ans;
    uint32_t    i;
    fx32_t      ds;
    fx32_t      dx;
    fx32_t      dy;
    fx32_t      dz;
    fx32_t      x;
    fx32_t      y;
    fx32_t      z;

    ds = 0;
    dx = 0;
    dy = 0;
    dz = 0;

    x = fixedpoint_get(cordic_fx_1K);
    y = 0;
    z = theta;

    for (i = 0; i < cordic_fx_data_size; i++)
    {
        ds = fixedpoint_get_sign(z);

        if (z > 0)
        {
            dx = x - (y shiftRight i);
            dy = y + (x shiftRight i);
            dz = z - (cordic_fx_lut_0[i]);
        }
        else
        {
            dx = x + (y shiftRight i);
            dy = y - (x shiftRight i);
            dz = z + (cordic_fx_lut_0[i]);
        }

        x = dx;
        y = dy;
        z = dz;
    }

    ans.re = x;
    ans.im = y;

    return ans;
}

This is mine at my first step before hw-re-implementation. LUTs & stuff got pre-computed.
I have also tried to implement in hw a sort of modified BKM-algorithm, and it's stable, but it's not as neat as Coordic.

[iMo]

I did the cordic on Spartan6 LX6 in past - the library cordic code, connected to microblaze. One gpio port issued the argument and the second/third one read the sine and cosine (both calculated at once) back. It was in direct mode (there is a pipelined mode as well) and I got the sine&cosine result within 100ns.

Edit: The result here got in a single clock.. The max sine/cosine width and speed depends on the device used..

[legacy]

fixed-point-32bit usually takes 34 clock's ticks to compute

[hamster_nz]

fixed-point-32bit usually takes 34 clock's ticks to compute

...if you pipeline every operation. The Xilinx IP generator allows you to select the level of pipelining you want. It is very crude though - The options should be "none, some, lots".

[iMo]

As I edited above the IP cordic I tried was "none" - both sine and cosine I got in 1 clock..
The ~100ns came as max estimated clock for the given design then..

[legacy]

Look at the above code in C. It's neat and simple, and I used it to design my own HDL serial implementation that takes the C-code as guidance.

Depending upon the application, CORDIC Processor is implemented in a number of ways. The simplest architecture is serial architecture consist of three adders and ROM containing the lookup table. Serial architecture performs one micro rotation for every clock cycle. The output is obtained after n clock cycle. Since serial architecture uses n clock- cycles for every rotation.

In my case one clock cycle per bit of precision, plus 3 clock cycles to set up the initial value and miscellanea. It takes the complexity very low, and it doesn't waste too much area on the FPGA.

Pro: simpler, doesn't take too many resources, you can implement it using the C code as the reference
Con: slower than the pipeline version, but faster than any software implementation

The pipelined architecture converts iterations in to pipeline phrases, but it consists of n cascaded blocks, hence it consumes n-times more area and it adds a lot of complexities since the first output of n stage CORDIC is after every clock cycle and tricks need to be used to store the angle for a particular micro rotation along a machine that is not synchronous. A lot of problems can happen here.



The reason why I wrote *usually*, meaning it's acceptable and suggesting you to implement the serial version 

[hamster_nz]

I finally got around to finishing this today, testing it in hardware with an I2S DAC, and adding it to my Wiki.

(Of course the audio DAC is skipping 2047 in every 2048 samples, because it is at running at ~50kS/s, but the CORDIC module can can run at 160MHz+).




http://hamsterworks.co.nz/mediawiki/index.php/CORDIC

[legacy]

Rather than generating one n-bit value every n+2 cycles (which is the usual way to minimize resource usage) I've decided to generate one value every cycle, as might be done in a high performance SDR environment.

so, you did the pipelined version 

[babysitter]

Got CORDIC explained sitting next a campfire while I was slightly intoxicated by someone much more intoxicated, what a fun.

Efficient, low weight algorithms from the ~60s rule!
(Also, learning drunk at the campfire rules. Ham radio lifestyle.)