工程设计——最大公约数

1、百度文库1课程设计报告题目：用硬件设计一个最大公约数计算的算法电路班级：姓名：学号：合作者：百度文库2摘要：本文论述的是采用二元的最大公约数算法，即欧基理德算法(Eucldean GCDAlgorithm)设计一个计算两个32位整数最大公约数 (GCD的处理器。首先给出了欧几里 得算法的描述，阐述了欧几里得算法原理；接着阐述了基本功能单元的选取和实现；随后详细的描述了设计过程和软硬件代码并对设计结果进行了分析、验证以及用QUARTU歎件对该程序进行仿真综合得出电路图。要求设计一种的VLSI实现方案，该方案须使用Altera公司的FPGA设计流程实现，技术和功能上总体要求低功耗优先。具体指标取下

2、：DCAstro工艺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%百度文库3一、设计要求1、 目标：设计一个计算两个32位整数最大公约数(GCD的处理器。2、 输入：OPA 32-bit，操作数一；OPB 32-bit，操作数二；START启动信号；RESET复位信号；CLK系统时钟。3、 输出：DONE指示输出

3、。RESULT 32-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，假设ab，求其最大公约数(gcd),使用欧几里得算法，先计 算a mod b得到c,百度文库4再计算b mod c得到d,再计算c mod d得到e,.直到模的结果为0,那么0之

4、前的那个数就是所求的最大公约数。例如，求174和136的最大公约数，1741136T38T22宀 16 宀 6T4 宀 2 宀 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就是最大公约数。我们的方案使用一个基本单元， 在控制电路控制下， 反复计算，经过几个周期得到一个计算结果。 /2、基本功能单元的实现百度文库5前面已经介绍了基本功能单元实现的功能，即“贪婪减法并排序”。这可以通过组合逻辑实现。百度文库6消耗的硬件资源将很大。和b比较进行排序。也就是说，还要做a-bk-b的运算。数据流如图4。长度，把可能需要的结果提前运

6、算，然后根据需要选择相应的数据。也就是，提前计算a-balign、a-balign_sub、a-balign-b、a-balign_sub-b。这样改进后，组合逻辑的延时缩短了，代价是使用了更多的减法器。最终的结构就是图3的形式。最直观的想法a和b、2b、4b、8b、（即b左移0位、1位、2位、3位、后的结果）分别比较，找到满足b*2kavb*2P的b*2k，然后将a减去b*2k，结果和b排序，送到下一级。但是，如果采用32个比较器并行地比较,为了节省硬件，可以先检测a和b前导0的数目，相减得到需要左移的位数，然后移位b到和a对齐的位置。比较一次，就能找到需要的b*2k（记为= oooooi

7、louoooooi= 0000001001H1000a，这时bk=balign_sub。基本功能单元编码和对数移位器用于找出和bk（=b*2k），做减法得到a-bka第一个1对齐，这个结果还需要SLL为了缩短流水线的bk） 。的baiign，这个值和a比较，找到需要的b.alignbt;set百度文库7图3基本功能单元（贪婪减法并排序）的硬件结构百度文库8四、设计过程描述1、总体结构使用一个“贪婪减法并排序”的基本功能单元，加上附加的控制，构建出我们的方案（图5）。更加具体的内部结构如图6，图中的“预处理”是对OPA和OPB排序，保证进入寄存 器a、b的值满足ab，通过简单的比较和选择逻辑就能

8、实现。图5方案模块图百度文库9图6方案的具体内部结构图百度文库102、工作流程直到b=0，运算完成，输出结果。该方案的操作时序如图MASTER的控制，START信号拉高后，GCD模块读取操作数OPA和OPB并开始运算，经过多次迭代运算，到b=0后，运算完成，DONE言号被置1，MASTER读取结果，然后撤销五、软硬件代码描述1、求最大公约数的C语言算法首先编写程序，用以描述所要实现的计算任务。图9所示为求最大公因数(GreatestCommonDivisor，GCD的系统框图，其输入为go_i、x_i和y_i，输出为d_o。 /其中go_i为控制信号，x_i和y_i为两个输入的正整数，d_o为

9、两个输入正整数的公因数。在该方案中，完成一次运算需要多个周期。运算数a和b被基本功能单元反复运算,7，GCD模块作为一个对象受到START接着GCD模块撤销DONE信号。IWaster卜1酸CIsr.unGCB:|K?i_/readCBlIi匚口i i呂/Icrxifilpt*百度文库11图9最大公因数系统框图求最大公约数的C语言算法如下：int x，y，r；while(1)while(!go_i);if(x_iy_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简单：求两个输

10、入数的最大公因数，并输出。如果输入是12和9,则输出应该是3;如果输入是13和3,则输出应该为1。可以利用C语言的集成开发环境(如VC+6.0)验证算法的正确性。程序中，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; II用于定义输入数的范围，最大为2*N-1in pu

11、tN-1:0 x_i,y_i;in put clk,go_i;output regN-1:0d_o;parameter s0=3b111,s1=3b001,s2=3b010,s3=3b011,s4=3b100,s5=3b101,s6=3b110;reg2:0curre nt_state ,n ext_state;regN-1:0 x,y,r;always(posedge clk)II状态寄存器curre nt_state=n ext_state;always(curre nt_state,x_i,y_i,go_i,x,y,r)产生下一个状态的组合逻辑case(curre nt_state)s0

12、:if(go_i) n ext_state=s1;else n ext_state=s0;s1:if(x_i=y_i) next_state=s2;else n ext_state=s3;s2: n ext_state=s4;s3: n ext_state=s4;百度文库13s4:if(y0) n ext_state=s5;else n ext_state=s6;s5: n ext_state=s4;s6: n ext_state=s0;default:n ext_state=s0;endcasealways( negedge elk) /产生输出和中间变量的组合逻辑case (eurre n

13、t_state)s2:begi nx=x_i;y=y_i;ends3:begi nx=y_i;y=x_i;endr=x%y; x=y;y=r; ends6:d_o=x;defaultendeaseen dmodules5:百度文库ii程序说明：(1)部分注释见程序的旁注。(2)本程序中的状态与图13(b)(见八、设计过程中遇到的问题与解决办法)中的状态对应关系如下：sO2, si3, s24, si6,si8,si9,sii2。对照状态图阅读程序，一目了然。六、设计结果的分析、验证及设计电路图i、仿真波形图如图iO所示。图iO QUARTUS仿真波形图(1)从仿真波形可以看出，33和55的最大

14、公约数为ii,33和9的最大公约数为3,9和iO的最大公约数为i,i8和32的最大公约数为2,i8和i7的最大公约数为i,结果均正 确。(2)从仿真波形可以看出，得出最大公约数有一个延迟时间，这个延迟时间跟状态机有关， 因为一个时钟周期状态机转换一次状态，而得到最大公约数需要完成一个完整的状态 图，所以需要若干个时钟周期。可以分析得出最大公约数与延迟两者之间的关系，并从 仿真波形中得到验证。(3)在仿真波形中，也将程序中用到的一些信号(比如状态机、中间信号x和y等)加了进去，这些信号用于分析状态机的运行过程非常有效。(4)这里采用多进程的方式来描述状态机，每个进程功能明确。另外，需要特别说明的

15、是，在程序中既用到elk的上升沿，又用到了elk的下降沿，这样是为了使状态转换及输出 的时序关系更清晰。2、设计电路图通过QUARTU欧件对该程序compile编译成功后，进行该程序的仿真综合，得到该算法的电路图如图ii所示：百度文库15.1 :-J_蔓*g-1 T匚Tc1paflTETZ- dft哇图11系统总体电路图由于图片过大，不便于在word中显示，系统总体电路图和各模块电路图以附件的形式发过去。七、性能估计使用DC对设计进行综合，估计芯片的性能。结果列于表1中。表1方案的性能估计DCAstro工艺SMIC.13 tt 1.2VSMIC.13 tt 1.2V单元库SIMIC13IO_l

16、i ne_02_ttSMIC13STDLIBM6关键路径、2.79ns（约358MHz）4.32 ns（约230MHz）静态功耗1.86uwJ动态功耗3.99mwarea239087 um2236um*236um=55696 um利用率N/A82% /可以分析得出，操作数是2537720636和4106118243将产生最坏情况，需要46次迭代才能得出运算结果。 在modelsim中仿真，随机产生10000组数，利用我们的模块求最大公约 /数，测试结果显示，共用了290656个周期，平均每次运算花费29个周期。结合频率的估计值，运算速率约8M op/s。可见，该方案在技术和功能上总体满足低功耗

17、优先的要求。百度文库16八、课程设计过程中遇到的问题与解决办法一如何将C语言算法转换成Verilog硬件描述语言？这个问题还是第一次接触， 一点没有思路。于是我在网上搜了一些资料， 了解它的思路, 参考了它的写法。其中贺敬凯，王瑞春等人写的将C算法转换为Verilog实现的一种方法对我的帮助很大，下面给出将C语言算法转换成Verilog的实现方法。1、C算法转换为Verilog实现的转换原理将C语言算法转换成Verilog硬件实现，应该从C语言的特征着手。C语言有三种基本 的程序结构：顺序结构、选择结构、循环结构；而且使用这三种基本结构可以实现任何复杂的算法。因此，如果能够将这三种基本结构转换

18、成可综合的Verilog表述，那么任何复杂的算法都可以用Verilog硬件来实现。三种基本程序结构向状态图转换，如图12所示。图12三种基本程序结构向状态图转换的模板在以上转换模板的基础上，用硬件来实现程序算法，则需要以下4个步骤：(1)首先将解决问题的算法用C语言程序或程序流程图表示。(2)使用三种基本程序结构向状态图转换的模板，将C语言算法转换成一个复杂的状态图, 图中的状态和边可包含算术表达式，表达式中可使用外部输入、输出以及变量。这一 步又分为如下两个子步骤：A.先将所有语句分为赋值语句、循环语句或分支语句。B.对于赋值语句、循环语句和分支语句，分别套用图2所示的转换模板将相应的程序语

19、 句转换为状态图。（3） 对于上一步得到的状态图进行化简。这一步需要对以下状态化简：没有做任何事情a=b下一条语旬while tco nd： 循环体语句F一条语句下一条黔句；日培旬else if c2Jt 他语切Ci甬区丘2讲取淇飯呼砂下一亲语诃( (C) )分支语句百度文库17的状态，可以删除；两个状态间没有循环运算的或者是两个状态没有先后逻辑顺序 关系的，可以合并。（4） 对于化简后的状态图，采用状态机实现。对于这一步，建议采用3进程状态机实现。2、下面具体说明由上面介绍的转换步骤将C语言描述的最大公约数算法转化为Verilog硬件描述语言实现。（1）将程序算法转换成一个复杂的状态图采用图

20、12的模板，将C语言描述的最大公约数算法可以方便转换成状态图，如图13（a）所示。（2）状态图化简在图13（a）所示的状态图中，可以看出，该状态图中有几个状态根本没有做任何事情，因此可以将其删除；另外有一些状态可以合并。下面对图13（a）的状态图进行化简。显然，状态1没有做任何事情，没有必要存在；状态2和状态2-J可以合并为一个状态，因为在两者之间没有循环运算；状态4和状态5也可以合并，因为它们所执行的赋值运算彼此无关，同理，状态6和状态7也可以合并，状态9、状态10和状态11也可以合 并；状态3-J和状态8可以合并；状态1-J可以去掉。化简后的状态图如图13（b）。百度文库18图13(a)求最大公约数的状态图(3)使用VerilogHDL语言实现状态图。得到化简的状态图后，下一步骤就是使用Ve