工程设计——最大公约数

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

2、CAstro工艺SMIC.13 tt 1.2VSMIC.13 tt 1.2V,单元库SIMIC13IO_line_02_ttSMIC13STDLIBM6关键路径2.79ns （约 358MHz）4.32ns （约 230MHz）静态功耗1.86uw动态功耗3.99mwarea239087 um 2236um*236um=55696 um利用率N/A82%一、设计要求1、目标：设计一个计算两个 32位整数最大公约数(GCD的处理器。2、输入：OPA 32-bit ,操作数一；OPB 32-bit ,操作数二；START启动信号；RESET复位信号；CLK:系统时钟。3、输出：DONE指示输出。R

3、ESULT 32-bit ,最大公约数(GCD；4、要求： 采用二元的最大公约数算法，即欧基理德算法( 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

4、,那么0之前的那个数就是所求的最大公约数。例如，求174和136的最大公约数，174 136 一 38 - 22- 16一 6一 4一 2一 0最大公约数是2。在实现上，求模的方法就是做除法，保留余数。如果细看一般求余数的方法，就是做减法，比如求a mod b的过程（假设a>=b ）,从a中减去b的尽量大的倍数就得到模的结 果。但是，在实际中，这个“尽量大的倍数”（就是商）比较难找，所以，一般拿b的（8 倍、4倍、2倍、1倍）去试，每次减掉尽量大的一个 ，这样从大到小试，试完一遍就可以 得到结果。三、基本功能单元1、基本功能单元的选取基于这个理解，我们选取的基本单元完成的功能是：从大数中

5、减去小数尽量大的倍数（1倍、2倍、4倍、8倍）。我们不妨把这个操作叫做“贪婪减法”。除此之外，对减法的结果，如果小于b,要和b交换位置，以保证每次运算都在 a>b前提下开始。 运算数a和 b被模块读取后，先排序，使得a>=b ,然后，a和b被基本功能单元反复运算，直到b变为0。这时的a就是最大公约数。abfind <a <b*2 );图1 基本功能单元我们的方案使用一个基本单元， 在控制电路控制下， 反复计算，经过几个周期得到一个计算结果。 /2、基本功能单元的实现/前面已经介绍了基本功能单元实现的功能，即“贪婪减法并排序”。这可以通过组合逻辑实现。最直观的想法是，a和

6、b、2b、4b、8b、（即b左移0位、1位、2位、3位、后的结果）分别比较，找到满足b*2&a<b*2T 的 b*2k,然后将 a减去b*2k,结果和b排序，送到下一级。但是，如果采用32个比较器并行地比较,消耗的硬件资源将很大。为了节省硬件，可以先检测a和b前导0的数目，相减得到需要左移的位数，然后移位b到和a对齐的位置。比较一次，就能找到需要的b*2k （记为= oooooi louooooo ib k)。=M10Q0 OOHllf)GOO?.iT如果 balign< a，则 bk = balign；=txmiooi ii oooor)>df寻找尽量大的bk的ba

7、lign,这个值和a比较，找到需要的0则)balign >a)寸 bk=balign_subo基本功能单元的结构图 （图3）,头0编码和对数移位器用于找出和bk (=b*2k),做减法得到 a-bka第一个1对齐,这个结果还需要和b比较进行排序。也就是说，还要做 a-bk-b的运算。数据流如图4。为了缩短流水线的长度，把可能需要的结果提前运算，然后根据需要选择相应的数据。也就是，提前计算a-b align 、ab align_sub 、 a-b align -b、 a-b align_sub -b 。这样改进后，组合逻辑的延时缩短了，代价是使用了更多的减法器。最终的结构就是图3的形式。图

8、3 基本功能单元（贪婪减法并排序）的硬件结构四、设计过程描述1、总体结构使用一个“贪婪减法并排序”的基本功能单元，加上附加的控制，构建出我们的方案（图5）。更加具体的内部结构如图 6 ,图中的“预处理”是对 OPA和OPB排序，保证进入寄存器a、b的值满足a>b ,通过简单的比较和选择逻辑就能实现。STAKTCLKRFSFT过或TdT.图5方案模块图图6方案的具体内部结构图2、工作流程在该方案中，完成一次运算需要多个周期。运算数 a和b被基本功能单元反复运算，直到b=0,运算完成，输出结果。该方案的操作时序如图7 , GCD模块作为一个对象受到/ MASTER勺控制，START信号拉高后

9、，GCD模块读取操作数 OPA和OP所开始运算，经过多次迭代运算，到 b=0后，运算完成，DONE言号被置1 , MASTER卖取结果，然后撤销 J*START接着GCD模块撤销DONE信号。、/ X f, , -GCD;nn.: aLir)/IJcrwrletf图7 方案的操作时序醒工一conputim图8 方案的状态转换图五、软硬件代码描述1、求最大公约数的 C语言算法首先编写程序，用以描述所要实现的计算任务。(GreatestCommonDivisor , GCD 的系统框图，其输入为 go_i /其中go_i为控制彳言号，x_i和y_i为两个输入的正整数，d_o /=0/图9所示为求最

10、大公因数、x_i和y_i ,输出为d_o。为两个输入正整数的公因数。/J OPA'Master(口PB图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)

11、验证算法的正确性。'、(2)程序中，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-1inputN-1:0x_i,y_i;input clk,go_i;output regN-1:0d_o;parameter S0=3&

12、#39;b111,s1=3'b001,s2=3'b010,s3=3'b011,s4=3'b100,s5=3'b101,s6=3'b110;reg2:0current_state,next_state;regN-1:0x,y,r;always(posedge clk)状态寄存器current_state=next_state;always(current_state,x_i,yj,go_i,x,y,r)产生下一个状态的组合逻辑case(current_state)s0:if(go_i) next_state=s1;else next_state=s

13、0;s1 : if(x_i>=y_i) next_state=s2;else next_state=s3;百度文库ii52: next_state=s4;53: next_state=s4;s4:if(y>0) next_state=s5;else next_state=s6;55: next_state=s4;56: next_state=s0;default:next_state=s0; endcase/always(negedge clk) /case (current_state) s2: beginx=x_i;y=y_i;end53: beginx=y_i;y=x_i;e

14、nd55: beginr=x%y;x=y;y=r;end56: d_o=x;defaultendcase产生输出和中间变量的组合逻辑endmodule程序说明:(1) 部分注释见程序的旁注。(2) 本程序中的状态与图13(b)(见八、设计过程中遇到的问题与解决办法)中的状态一一对应关系如下：s0>2, si >3, s2 >4, si>6, si >8, si >9, si>12。对照状态图阅读程序，一目了然。六、设计结果的分析、验证及设计电路图i、仿真波形图如图i0所示。图i0 QUARTU防真波形图(i)从仿真波形可以看出，33和55的最大公约数为

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

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

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

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

19、的Verilog表述，那么任何复杂的a=b下一条讲句whi：C co nd ： 1V环体语句卜一条吊句蹴值语句算法都可以用 Verilog硬件来实现。三种基本程序结构向状态图转换，如图12所示。C 语旬else if c2语句句下j 一语句£语句：应责位艾其旭舟硕下一条语句Cc)分支语句图12三种基本程序结构向状态图转换的模板在以上转换模板的基础上，用硬件来实现程序算法，则需要以下4个步骤：(1)首先将解决问题的算法用 C语言程序或程序流程图表示。/(2)使用三种基本程序结构向状态图转换的模板，将C语言算法转换成一个复杂的状态图,图中的状态和边可包含算术表达式，表达式中可使用外部输入

20、、输出以及变量。这一 步又分为如下两个子步骤：A.先将所有语句分为赋值语句、循环语句或分支语句。B.对于赋值语句、循环语句和分支语句，分别套用图2所示的转换模板将相应的程序语句转换为状态图。(3)对于上一步得到的状态图进行化简。这一步需要对以下状态化简：没有做任何事情的状态，可以删除；两个状态间没有循环运算的或者是两个状态没有先后逻辑顺序 关系的，可以合并。(4)对于化简后的状态图，采用状态机实现。对于这一步，建议采用3进程状态机实现。2、下面具体说明由上面介绍的转换步骤将C语言描述的最大公约数算法转化为Verilog硬件描述语言实现。(1)将程序算法转换成一个复杂的状态图采用图12的模板，将

21、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)。19图13 (a)求最大公约专