《工程设计——最大公约数》由会员分享，可在线阅读，更多相关《工程设计——最大公约数（10页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告题目：用硬件设计一个最大公约数计算的算法电路班级：姓名：学号：合作者：摘要：本文论述的是采用二元的最大公约数算法，即欧基理德算法(Eucldean GCDAlgorithm )设计一个计算两个 32位整数最大公约数 (GCD的处理器。首先给出了欧几里 得算法的描述，阐述了欧几里得算法原理； 接着阐述了基本功能单元的选取和实现；随后详细的描述了设计过程和软硬件代码并对设计结果进行了分析、验证以及用QUARTU歎件对该程序进行仿真综合得出电路图。要求设计一种的VLSI实现方案，该方案须使用 Altera公司的FPGA设计流程实现，技术和功能上总体要求低功耗优先。具体指标取下：DCAst
2、ro工艺SMIC.13 tt 1.2VSMIC.13 tt 1.2V单元库SIMIC13IO_li ne_02_ttSMIC13STDLIBM6关键路径2.79ns （约 358MHz）4.32 ns （约 230MHz）静态功耗1.86uw动态功耗3.99mwarea239087 um2236um*236um=55696 um利用率N/A82%一、设计要求1、目标：设计一个计算两个 32位整数最大公约数(GCD的处理器。2、输入:OPA 32-bit，操作数一；OPB 32-bit，操作数二；START启动信号；RESET复位信号；CLK系统时钟。3、输出：DONE指示输出。RESULT 3
3、2-bit，最大公约数（GCD；4、要求：（1）采用二元的最大公约数算法，即欧基理德算法（ Eucldean GCD Algorithm ；（2）设计一种的VLSI实现方案，该方案须使用 Altera 公司的FPGA设计流程实现。二、欧几里得算法描述欧几里得算法的基础是下面这个定理：设a,b,c为3个正整数，且a=bq+c,其中q为整数，则（a,b）=（b,c）。另外，（b,0）=b。给定两个正整数 a,b，假设a b，求其最大公约数（gcd）,使用欧几里得算法，先计 算a mod b得到c,再计算b mod c得到d,再计算c mod d得到e,直到模的结果为 0,那么0之前的那个数就是所求
4、的最大公约数。例如，求174和136的最大公约数，1741136t 38 t 22宀 16宀 6 t 4宀0最大公约数是2。在实现上，求模的方法就是做除法，保留余数。如果细看一般求余数的方法，就是做减法，比如求a mod b的过程（假设a=b ）,从a中减去b的尽量大的倍数就得到模的结 果。但是，在实际中，这个“尽量大的倍数”（就是商）比较难找，所以，一般拿b的（8 倍、4倍、2倍、1倍）去试，每次减掉尽量大的一个，这样从大到小试，试完一遍就可以 得到结果。三、基本功能单元1、 基本功能单元的选取基于这个理解， 我们选取的基本单元完成的功能是： 从大数中减去小数尽量大的倍数 （ 1 倍、2倍、
5、4倍、8倍）。我们不妨把这个操作叫做“贪婪减法”。除此之外，对减法的结果，如果小于b，要和b交换位置，以保证每次运算都在 ab前提下开始。 运算数a和 b 被模块读取后， 先排序， 使得 a=b ，然后， a 和 b 被基本功能单元反复运算， 直到 b 变 为0。这时的 a 就是最大公约数。图 1 基本功能单元我们的方案使用一个基本单元， 在控制电路控制下， 反复计算， 经过几个周期得到一个 计算结果。2、 基本功能单元的实现前面已经介绍了基本功能单元实现的功能，即“贪婪减法并排序”。这可以通过组合逻辑实现。最直观的想法是，a和b、2b、4b、8b、（即b左移0位、1位、2位、3位、 后的结果
6、）分别比较，找到满足 b*2k aa ，这时 bk=balign_sub 。基本功能单元的结构图 （图 3），头 0 编码和对数移位器用于找出和 a 第一个 1 对齐 的balign ，这个值和a比较，找到需要的 bk （=b*2,做减法得到a-bk，这个结果还需要 和 b 比较进行排序。也就是说，还要做a-bk-b 的运算。数据流如图 4 。为了缩短流水线的长度，把可能需要的结果提前运算，然后根据需要选择相应的数据。也就是，提前计算 a-b align 、a-b align_sub 、 a-b align -b 、a-b align_sub -b 。 这样改进后，组合逻辑的延时缩短了，代价
7、是使用了更多的减法器。最终的结构就是图 3 的形式。图 3 基本功能单元（贪婪减法并排序）的硬件结构图 4 初始的设计，太长的延时四、设计过程描述1、 总体结构使用一个 “贪婪减法并排序” 的基本功能单元， 加上附加的控制， 构建出我们的方案 （图 5）。更加具体的内部结构如图 6 ，图中的“预处理”是对 OPA 和 OPB 排序，保证进入寄存 器a、b的值满足a b，通过简单的比较和选择逻辑就能实现。图5 方案模块图图6 方案的具体内部结构图2、 工作流程在该方案中，完成一次运算需要多个周期。运算数 a 和 b 被基本功能单元反复运算， 直到b=0，运算完成，输出结果。该方案的操作时序如图7
8、，GCD模块作为一个对象受到MASTER勺控制，START信号拉高后，GCD模块读取操作数 OPA和OPB并开始运算，经过多次迭代运算，到 b=0后，运算完成，DONE言号被置1 , MASTER卖取结果，然后撤销 START接着GCD模块撤销DONE信号。图 7 方案的操作时序图 8 方案的状态转换图五、软硬件代码描述1、求最大公约数的 C语言算法首先编写程序，用以描述所要实现的计算任务。 图9所示为求最大公因数（GreatestCommonDivisor , GCD 的系统框图， 其输入为 go_i、x_i 和 y_i ,输出为 d_o。 其中 go_i 为控制信号， x_i 和 y_i
9、为两个输入的正整数， d_o 为两个输入正整数的公因数。图 9 最大公因数系统框图求最大公约数的 C语言算法如下： int x ， y， r； while ( 1)while ( !go_i )；if (x_i y_i ) x=x_i ；y=y_i ；elsex=y_i ；y=x_i ；while ( y!= 0 ) r=x%y；x=y；y=r；d_o=x；程序说明：(1) 该算法的功能很简单：求两个输入数的最大公因数，并输出。如果输入是12 和9，则输出应该是 3；如果输入是 13和3，则输出应该为 1。可以利用 C 语言的集成开发环境(如 VC+6.0)验证算法的正确性。(2) 程序中，
10、go_i 、x_i 、y_i 均为输入， d_o 为输出，与图 9框图中的输入输出一致。 go_ 为控制信号，只有该信号为有效电平(即高电平)时，才启动求最大公约数的进程，若 为无效电平，则程序暂停直到该信号有效。2、求最大公约数的 Verilog 代码(简稿，更加详细优化的 Verilog 代码见附件)module gcd(clk,x_i,y_i,go_i,d_o);parameter N=6; / 用于定义输入数的范围， 最大为 2*N-1 inputN-1:0x_i,y_i;input clk,go_i;output regN-1:0d_o;parameter s0=3b111,s1=3
11、b001,s2=3b010,s3=3b011,s4=3b100,s5=3b101, s6=3b110;reg2:0current_state,next_state;regN-1:0x,y,r;always(posedge clk)/ 状态寄存器 current_state=next_state;always(current_state,x_i,y_i,go_i,x,y,r)/ 产生下一个状态的组合逻辑 case(current_state)s0:if(go_i) next_state=s1;else next_state=s0;s1： if(x_i=y_i) next_state=s2;els
12、e next_state=s3;s2: next_state=s4;s3: next_state=s4;s4:if(y0) next_state=s5;else next_state=s6;s5: next_state=s4;s6: next_state=s0;default:next_state=s0;endcasealways(negedge clk) / 产生输出和中间变量的组合逻辑case (current_state)s2 ： beginx=x_i;y=y_i;ends3 ： beginx=y_i;y=x_i;ends5 ： beginr=x%y;x=y;y=r;ends6 ： d_
13、o=x;defaultendcaseendmodule程序说明：( 1) 部分注释见程序的旁注。( 2) 本程序中的状态与图 13(b) (见八、 设计过程中遇到的问题与解决办法) 中的状 态一一对应关系如下： s02，s13，s24，s16，s18，s19， s1 12。对照状态图阅读程序，一目了然。六、设计结果的分析、验证及设计电路图1、仿真波形图如图 10 所示。图10 QUARTUS仿真波形图(1) 从仿真波形可以看出， 33和 55的最大公约数为 1 1，33和9的最大公约数为 3，9和 10 的最大公约数为 1 ， 1 8和32的最大公约数为 2，18和 1 7的最大公约数为 1
14、，结果均正 确。(2) 从仿真波形可以看出，得出最大公约数有一个延迟时间，这个延迟时间跟状态机有关， 因为一个时钟周期状态机转换一次状态，而得到最大公约数需要完成一个完整的状态 图，所以需要若干个时钟周期。可以分析得出最大公约数与延迟两者之间的关系，并从 仿真波形中得到验证。(3) 在仿真波形中，也将程序中用到的一些信号(比如状态机、中间信号x和y等)加了进去，这些信号用于分析状态机的运行过程非常有效。(4) 这里采用多进程的方式来描述状态机，每个进程功能明确。另外，需要特别说明的是，在程序中既用到 elk的上升沿，又用到了 elk的下降沿，这样是为了使状态转换及输出 的时序关系更清晰。2、设计电路图通过QUARTU欧件对该程序compile编译成功后，进行该程序的仿真综合，得到该算法的电路图如图11所示：图11系统总体电路图由于图片过大，不便于在word中显示，系统总体电路图和各模块电路图以附件的形式发过去。七、性能估计使用DC对设计进行综合，估计芯片的性能。结果
