工程设计——最大公约数.doc

课程设计报告 题目：用硬件设计一个最大公约数计算的算法电路 班级： 姓名： 学号： 合作者： 摘 要：本文论述的是采用二元的最大公约数算法，即欧基理德算法（Eucldean GCD Algorithm）设计一个计算两个 32位整数最大公约数（GCD）的处理器。 首先给出了欧几里得算法的描述，阐述了欧几里得算法原理；接着阐述了基本功能单元的选取和实现；随后详细的描述了设计过程和软硬件代码并对设计结果进行了分析、验证以及用QUARTUS 软件对该程序进行仿真综合得出电路图。要求设计一种的 VLSI实现方案，该方案须使用 Altera公司的FPGA 设计流程实现，技术和功能上总体要求低功耗优先。具体指标取下： DC Astro 工艺 SMIC.13 tt 1.2V SMIC.13 tt 1.2V 单元库 SIMIC13IO_line_02_tt SMIC13STDLIBM6 关键路径 2.79ns（约 358MHz） 4.32ns（约 230MHz） 静态功耗 1.86uw 动态功耗 3.99mw area 39087 um2 236um*236um=55696 um2 利用率 N/A 82% 一、设计要求 1、目标： 设计一个计算两个 32位整数最大公约数（GCD）的处理器。 2、输入： OPA：32-bit，操作数一； OPB：32-bit，操作数二； START：启动信号； RESET：复位信号； CLK：系统时钟。 3、输出： DONE：指示输出。 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,假设a≥b ，求其最大公约数（gcd），使用欧几里得算法，先计算a mod b得到 c,再计算b mod c 得到d，再计算c mod d 得到e，……直到模的结果为0，那么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、 基本功能单元的选取 基于这个理解，我们选取的基本单元完成的功能是：从大数中减去小数尽量大的倍数（1 倍、2 倍、4 倍、8 倍……）。我们不妨把这个操作叫做“贪婪减法”。除此之外，对减法的结果，如果小于 b，要和 b 交换位置，以保证每次运算都在a≥b 前提下开始。 运算数a 和b 被模块读取后，先排序，使得 a>=b，然后，a 和b 被基本功能单元反复运算，直到 b 变为0。这时的a 就是最大公约数。 图 1 基本功能单元 我们的方案使用一个基本单元，在控制电路控制下，反复计算，经过几个周期得到一个计算结果。 2、 基本功能单元的实现 前面已经介绍了基本功能单元实现的功能，即“贪婪减法并排序” 。这可以通过组合逻辑实现。 最直观的想法是，a 和b、2b、4b、8b、……（即 b 左移0 位、1 位、2 位、3 位、……后的结果）分别比较，找到满足b*2k≤a<b*2k+1的b*2k，然后将 a 减去b*2k，结果和b 排序，送到下一级。但是，如果采用 32 个比较器并行地比较， 消耗的硬件资源将很大。 为了节省硬件，可以先检测 a 和b 前导 0 的数目，相减得到b 需要左移的位数，然后移位b 到和 a对齐的位置。比较一次，就能找到需要的b*2k（记为 bk）。 图 2 寻找尽量大的bk 如果balign ≤a ，则bk=balign ； 否则，balign >a，这时bk=balign_sub 。 基本功能单元的结构图（图 3），头 0 编码和对数移位器用于找出和 a 第一个 1 对齐的balign ，这个值和 a 比较，找到需要的bk（=b*2k），做减法得到a-bk ，这个结果还需要和 b 比较进行排序。也就是说，还要做a-bk-b