Description
PURPOSE – In this lab you will design and implement a 16-bit CORDIC computer. The design to be implemented is based on a bit-serial configuration. It will take as input a 16-bit signed binary fixed point number, corresponding to an angle in the range 0 to π/2, and use the CORDIC method to find the sine and cosine of this angle. This will be coded in Verilog and implemented on the Basys 3 board.
Introduction
Coordinate Rotation Digital Computer was invented by Jack Volder in 1956 [1] as a replacement for the analog resolver used in the navigation systems of the B-58 bomber. At this time digital hardware was limited and it was a significant challenge to do this in real-time. The CORDIC method was a scheme that replaced the multiplications with shifts and adds. Two shift registers and two serial adder-subtractor were used. A third shift register and serial adder-subtractor was used with a ROM to complete the implementation.
There are two modes in which CORDIC can operated. ROTATION and VECTORING modes. For the calculation of sine and cosine we will operate the CORDIC computer in ROTATION mode for which the equations of interest are
|
xi+1 |
= xi−di yi 2−i |
||||||||||||||||||
|
yi+1 |
= |
yi +di xi 2−i |
di= |
di=+1 |
for zi≥0 |
||||||||||||||
|
{di=−1 |
for zi<0 |
||||||||||||||||||
|
zi+1 |
= |
zi−di tan−1 (2−i) |
|||||||||||||||||
|
After n iterations the above equations produce |
|||||||||||||||||||
|
1 |
[ x0 cos(z0 )− y0 sin(z0 )] |
||||||||||||||||||
|
xn= |
|||||||||||||||||||
|
K n |
|||||||||||||||||||
|
y n= |
1 |
[ x0 sin (z0)+ y0 cos (z0)] |
|||||||||||||||||
|
K n |
|||||||||||||||||||
|
zn=0 |
|||||||||||||||||||
|
n |
1 |
||||||||||||||||||
|
where K n=k0 k1 ⋯kn =∏ |
is a constant that, for a given n, can be computed offline. For |
||||||||||||||||||
|
−2i |
|||||||||||||||||||
|
i=0 |
√1+2 |
||||||||||||||||||
large n the constant Kn will converge to 0.607253.
1
For an angle θ in the range 0 to π/2 the CORDIC method can be used to compute cos(θ ) and sin(θ ). If we set the initial values as x0 = Kn, y0 =0, and z0 = θ, when the computation is complete we have xn = cos(θ), yn = sin(θ), and zn=0. (For n=16 we have K16 = 0.607253 )
FPGA Implementation
The implementation in of CORDIC in an FPGA is discussed in [2]. There are a number of possibilities, the first would be to implement the three equations for x, y, and z directly, this is a bit-parallel implementation. However the bit-parallel implementation requires large shift registers which typically do not map well into an FPGA. A better way is a bit-serial implementation which can be clocked near the maximim possible on an FPGA and avoids the problem with a large shift register. The bit-serial design is typically much more compact and better performing than the bit-parallel design. In this lab be implement a bit-serial design.
Note that your computations in this lab will use signed binary fixed point fractions. These are discussed on pages 242 – 243 of the text [4].
CORDIC Datapath
A bit-serial implementation of CORDIC is shown in the following datapath. This implementation is for 16-bits. The bit-serial implementation corresponds to the original implementation developed by Volder. It consists of 3 sets of shift registers, serial adder-subtractors, and two input multiplexers. Two of the shift registers, x and y, are coupled via 13 input multiplexers to the serial adder-subtractor in the other registers datapath. The third register, z, is input to the third serial adder-subtractor along with an inverse tangent value stored in a table in a serial ROM.
Figure 1. Datapath of the 16-bit CORDIC computer
This hardware is based on three, 16-bit shift registers. Each register is clocked into a 1-bit adder-subtractor. The x and y values for each iteration are contained in these registers. These registers are interconnected. The z register is used with a serial ROM which contains a table of inverse tangent values used in updating the z register each iteration. You will need to compute the values to put in the
2
ROM (easily done with something like MATLAB.) The values are all represented as signed two’s complement fixed point fractions. Use the format 2.14 (2 bits to the left of the binary point and the remaining 14-bit, the fractional part, to the right of the binary point.)
A Verilog model of this can be built from several components. With reference to the figure 1 for the datapath we need three 16-bit parallel in/ parallel out shift registers, three 1-bit adder-subtractor units, three 2-input and two 13-input multiplexers, and a ROM with thirteen, 16-bit words.
Controller
In operation we require a total of n times k clocks where n is the number of iterations and k-bits is the word size (16-bits for the hardware shown in figure 1. The initial values of x0, y0, and z0 are loaded into the corresponding registers through the multiplexers. Each iteration the values in the x and y registers are added or subtracted to the appropriately shifted values of the y and x registers. The sign of the msb of the y register is used to determine if we should add or subtract. For the z registers the value is added or subtracted to the appropriate arc tangent value contained in the ROM. A simple state machine or counters are needed to keep track of the iterations, amount of shift, and ROM address. On completion the results are read directly from the x and y registers.
You should list the inputs and outputs to the controller and construct a state diagram or state table.
Input and Output
Once you have the CORDIC Verilog code debugged you should add input and output modules.
For this lab initial values will be loaded into the x, y, and z registers. Initially x will be loaded with the value of Kn and y will be loaded with 0. These can be hardwired into your design. The initial value in the z register will correspond to the angle θ, in radians. You should use the 16 switches on the Basys 3 board to select the value of θ to be entered. A pushbutton should be used to enter the z value.
After the initial values are loaded into the x, y, and z registers a second push button should be used to start each iteration. Each iteration will consist of 16 shift operations at the end of which each of the x, y, and z registers will have been updated. You should display the value in the x register using the four 7-segment displays.
To implement this in the Basys 3 you need to create a constraints file.
Verifying the design
To verify your design is working your TA will give you an initial angle to load in the z register and will then ask you to step through each iteration to verify you get the correct intermediate and final results.
3
SUMMARY – In this lab you designed a Verilog of a CORDIC computer, implemented it on a Digilent Basys 3 board, and verified its correctness.
REFERENCES
-
J. E. Volder, “The CORDIC Trigonometric Computing Technique,” IRE Transactions on Electronic Computers, EC-8 (3), 330 – 334.
-
R. Andraka, “A Survey of CORDIC Algorithms for FPGAs,”, in Proceedings of rthe 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays (FPGA ’98), Monterrey, Feb 22-24, 1998, pp. 191-200.
-
A. P. Taylor, “How to use the CORDIC algorithm in your FPGA design,” Xilinx Xcell Journal, issue 79 (second quarter 2012), 50-55
-
C. H. Roth, L. K. John, B. K. Lee, Digital Systems Design Using Verilog, Cengage, 2016
4
