Reference no: EM132948306

Greatest Common Divisor (GCD) Calculator

The greatest common divisor or the highest common factor is the largest natural number that divides two numbers without leaving a remainder. Hope you remember GCD calculations used in algebra and solving fractions in your secondary classes. In addition to that GCD is used in various other applications such as cryptography etc. One of the GCD estimation method is known as Euclid's GCD method, which is described using C language-style syntax below.

a <= ain;
b <= bin;
while (a b){ if (a > b)
a = a - b;
else
b = b - a;

G C D a ;

A dry-run for the GCD algorithm is given in Table 1. You may try it with other number combinations to familiarise the algorithm better.

7. 5 5 a b . . GCD a

Table 1: Euclid's GCD Algorithm Example

Since System Verilog is quite rich in programming constructs the above algorithm can easily be im- plemented as shown in Code . There is one to one relationship between the algorithm and the SystemVerilog code except the additional inputs and some control signals. We have two 8-bit inputs (Air and 6/u) and one 8-bit output (GUDout). Apart from the inputs and the output, there are two control signals s/ r/ and done. The start is a 1-bit input signal to inform the module that the data is ready and the module can start calculating the GCD, while done is a 1-bit output signal to signal that the GCD calculation is complete. Also, we first copy the data into two temporary variables named A and B, which is not essential, but advisable since the data is manipulated and copied onto the same variable during the process.

The GCD SystemVerilog implementation in Example is working accurately (See Figure 1), but this is not a hardware model implemented in System Verilog . In addition to that the model will not synthesis to a hardware which can be implemented on a FPGA specially because the while loop is not finite - it is data dependant. A hardware system should always be finite.

Now think like a hardware designer - how would one implement an algorithm with conditional state- ments in hardware? You do not have a luxury of using infinite amount to functional units or storage.

Therefore, it is better to reuse hardware components. Now, in order to execute the algorithm you might have to use one functional unit several times and data is written again and again to registers. We call them as register transfer operations. Every register-transfer operation must complete within one clock cycle (which is equivalent to one state of the FSM, since the FSM changes state at ev- ery clock cycle).Furthermore, in a single register-transfer operation, a functional unit cannot be used more than once. However, the same functional unit can be used more than once if it is used by different register-transfer operations. In other words, a functional unit can be used only once in the same clock cycle, but can be used again in a different clock cycle.

The datapath requires a comparator and a subtractor in order to carry out the operations in the algorithm. Let us assume that we have two registers to store the values for A and B, known as RegA and RegB. First we can compare the numbers - that means we require a comparator. Therefore the output of RegA and RegB (RegAout and RegBout) are the inputs to the comparator. At the same time, these outputs are connected to a subtractor. To make things simple, lets use two substractors: one subtractor to calculate A-B, and the other for B-A. The result of A-B should be fed back to RegA (and B-A to RegB). The input to RegA (or RegB) has two paths, one is the initial data which the user need to enter and other is, the subtractor output. Now we have to determine which input to select depending on the comparator decision. Therefore we are going to use a multiplexor at the input of RegA (and RegB). The datapath we require is shown in Figure 2. The functional units in the datapath required to be controlled based on the current and/or the next statement the datapath should carry out.

The multiplexors (muxA and muxB) has a select signal controlled by the control unit: when the data is loaded into registers select signals for the multiplexors will be 0; when the subtractor output is to be loaded sel signal will be 1. To load any data available at the input of registers, the load (loadA or loadB) should be asserted. Once the data is loaded to the registers, the comparator and the subtract units will compute the results. The comparison results will be fed into the control unit which will either stop the operation or load necessary results (A-B or B-A) to RegA or RegB. This will continue until A is equal to B.

Design and implement the GCD Calculator as shown Figure 2.

Deliverables for Submission

You are required to submit a logbook style document not more than 10 pages long containing the following details:

1. State Diagram for the controller and control-word table

2. SystemVerilog Codes for the Datapath including sub modules, Controller and the overall system Give explanations for the code with reference to the block diagram. Marks will be awarded for the mastery of HDL programming methods used.

3. Functional Simulation Results for at least five non-zero value pairs Give reasons for your value selection. A sample testbench code is given in the Appendix

4. What happens if one or both values for ain and bin are zero? Where do you think the issue is?
Propose a fix for this.

5. How would you improve the performance of this GCD Calculator? Clearly explain the exten- sion/improvement introduced to the circuit and its effect.

Attachment:- CourseWork.rar