《工程设计——最大公约数》由会员分享,可在线阅读,更多相关《工程设计——最大公约数(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对设计进行综合,估计芯片的性能。结果