CORDIC, What is it?

Question

I am reading about CORDIC (Coordinate Rotation Digital Computer) and I have t implement it. Honestly, I am reading and don't understand the difference between phase detection algorithm ( PLL, Costas loop, ...).

How can I use it to recover a phase? If I implement a transmit signal with phase shift, I know the value...so why I need to recover it? The main question is if the signal has a phase shift ( it is a signal distortion. as noise for example, isn't it?), does it mean that we need an algorithm to eliminate this shift...?

EDIT 1:

Cordic algorithm computes phases and a amplitudes of samples of a received signal.

why do we use a time recovery algorithm after cordic?

EDIT 2 Simulation

I have simulated a random BPSK sequence that was upsampled and filtered with a raised cosine filter. The length of the filter is 150 taps, sampling frequency 16, cut-off frequency 0.5 and transition bandwidth is 0.2. The noise was simulated with EbN0 = 10 with the following noise power:

SignalEnergy = (trapz(abs(filtered_signal_tx).^2))*(1/Fs);
Eb = SignalEnergy/(2*Nb);
N0 = Eb./(10.^(EbN0/10));
NoisePower = 2*N0*Fs;

The signal has a phase offset(shift): exp(1j*(2*pi*t+phase_offset));

It is the simulation a test signal. After that I define groups/blocks : 32 symbols x 16 samples and compute angels and amplitudes using CORDIC. I have found a samples with max amplitude and define sample before and after it ( max amplitude)

Answer 1

Below is an intuitive explanation to the CORDIC.

The CORDIC algorithm, published by Jack Volder in 1959 (Coordinate Rotation Digital Computer), allows rotating a phasor with only shifts and adds and can be used for phasor rotation, trigonometric calculation and computing the magnitude of of a complex phasor without the use of multipliers.

To see the significance of the CORDIC simply, first consider the general expression for rotating a phasor given by $I_1 + jQ_1$ as rotated by another phasor given by $I_r+jQ_r$ with a product as shown in the diagram below and given by these formulas:

$$I_2 = I_1I_r-Q_1Q_r \tag{1}\label{1}$$ $$Q_2 = I_1Q_r-I_rQ_1 \tag{2}\label{2}$$

This is because when we multiply phasors, the angles add, hence the result will have a product of the magnitudes and addition of the phases (rotated):

$$V_1 = I_1 + jQ_1 = K_1 e^{j\phi_1}$$ $$V_2 = I_2 + jQ_2 = K_2 e^{j\phi_2}$$ $$V_1 V_2 = K_1 K_2 e^{j\phi_1}e^{j\phi_2} = K_1K_2e^{j(\phi_1 + \phi_2)}$$

Below shows rotations that can be accomplished with no multipliers as simplifications from the general formula above. The first as a quadrature rotation of $\pm j$ requires $V_2 = 0 \pm j1$ and thus reducing $\ref{1}$ and $\ref{2}$ to a sign change and swapping $I_1$ and $Q_1$ to form the rotated $I_2$ and $Q_2$ and thus we can do this for all course rotations of 90°:

For rotations less than $\pm 90°$, what Jack Volder recognized was that if we rotate by moving on the imaginary axis alone we can achieve nearly binary weighted rotations for iteratively smaller steps. The gain will also increase, but this is an accepted side-effect known as the CORDIC gain, and ultimately through the implementation of the algorithm the gain is consistent.

We have already covered rotations by $\pm 90°$, observe that if we use $I_r=1$ and $Q_r=\pm 1$ in $\ref{1}$ and $\ref{2}$, the rotation will be $\pm 45°$ (and the gain will be $\sqrt{2}$). If we the simply divide $Q_r$ in half through a single bit shift, such that $I_r=1$ and $Q_r = \pm 0.5$, we achieve a rotation of $\pm 26.57°$ (and the gain for that rotation will be $\sqrt{1.25}$, and in general we get:

$$I_n = I_{n-1} - \frac{Q_{n-1}}{2^n} \tag{3}\label{3}$$ $$Q_n = \frac{I_{n-1}}{2^n} + Q_{n-1}\tag{4}\label{4}$$

Thus we see how an iterative approach can be used to approach a target angle in successively smaller angles, approximating a binary search. The precision of the result is improved through the use of a table look up for the accumulated angle. Below shows a simple 3 iteration example where the decision value d defines the direction of rotation (positive or negative) and the resulting accumulated phase after three iterations:

The CORDIC is typically done through iteration of a fixed number of steps, and including every stage as given by $\ref{3}$ and $\ref{4}$ such that the CORDIC gain is consistent and converges for large $n$ to approximately 1.647.

Below shows a numerical example. For precise results, a precomputed look-up table of the atan results for each of the log2(N) iteration angles is used, which removes the non-linearity from the ideal binary search (if the CORDIC resolved 90 degrees, 45 degrees, 22.5 degrees, 11.25 degrees... then the algorithm would proceed with a binary search, but since the angles are 45 degrees, 26.57 degrees, 14.04 degrees, etc....those values are stored in a look up table and used as the accumulated phase). The typical number of iterations could be 10 or more depending on actual precision desired.

And below shows the same process for starting from an arbitrary angle of 127 degrees and rotating the vector 33 degrees:

Answer 2

Notice that CORDIC operates digitally, it is more about a type of processor with a very simple instruction set that allows you to compute different functions.

The CORDIC was a great idea to make it possible to implement different arithmetic functions in early calculators. It is advantageous when you need to implement it with the least number of transistors.

You probably know how to find zeros of a function with the bisection method or some other binary search algorithm.

Coordic implements two simple transformations, the circular mode and the hyperbolic mode. With these transformations choosing the correct inputs you can perform a binary search and it will give you the desired output at a given output.

Basically CORDIC will compute a quantity like

$$ P = P_0 \prod_{k=0}^{N} \left(1 \pm \frac{1j}{2^n}\right) $$

And keep track of the angle with $$ \alpha = \sum_{k=0}^{N} \pm \tan^{-1}\left(2^{-k}\right) $$

The signal of the term in each iteration is determined by the comparison between the target value and the current value of the accumulator. And the terms $\tan^{-1}(2^{-k})$ will be precomputed.

If you choose $$ P_0 = \prod_{k=0}^{N} \frac{1}{\sqrt{1 + 2^{-2k}}}$$

And at each iteration you choose the sign to move the accumulated angle closer to $\alpha$.

You end with $P \approx \cos(\alpha) + j \sin(\alpha)$.