最新-基于FPGA的8位硬件乘法器设计 (1).doc

《最新-基于FPGA的8位硬件乘法器设计 (1).doc》由会员分享，可在线阅读，更多相关《最新-基于FPGA的8位硬件乘法器设计 (1).doc（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品资料-基于FPGA的8位硬件乘法器设计 (1). 本科毕业设计基于FPGA的8位硬件乘法器设计摘 要VHDL（VHSIC Hardware Description Language）是当今最流行的硬件描述语言之一，能够对最复杂的芯片和最完整的电子系统进行描述。以硬件描述语言作为设计输入，经过简单的综合与布局，快速烧录至FPGA（Field Programmable Gate Array）上进行测试，是现代IC设计验证的技术主流。 乘法器是处理器进行科学计算和数字信号处理的基本硬件结构，是现代微处理器中的重要部件。乘法器完成一次乘法操作的周期基本上决定了微处理器的主频。本文基于FPGA，采用

2、VHDL语言，结合MAX+plus这个强大的软件平台设计了8位二进制乘法器，并对其进行符号扩展，使其可以统一处理8位带符号数和无符号数。高速乘法器设计通常分为三个关键步骤：部分积产生、部分积累加和最终结果获得。本文对部分积产生过程采用改进Booth算法，有效减少部分积加法项；为了统一带符号和无符号数，对部分积进行符号扩展；而对部分积的累加则采取3-2压缩器和4-2压缩器进行压缩；最终结果的获得则以一个根据部分积累加结果到达时间的不同进行延迟优化的选择进位加法器将累加结果和累加进位相加而得。 关键词：乘法器 改进Booth算法 压缩器 选择进位加法器The Circuit Design of 8

3、-bit Hardware Multiplier Based on FPGAKe Xiuyan(College of Engineering, South China Agricultural University, Guangzhou 510642, China)Abstract: VHSIC Hardware Description Language, one of todays most popular hardware description languages, is used to describe the most complex chip and most complete e

4、lectronic systems.The multiplier is not only the basic hardware structure of the processor for scientific computing and digital signal processing but also an important component of modern microprocessors. This design for 8-bit binary multiplier is based on FPGA, using VHDL language, and proved by th

5、e MAX+plus software platform. The multiplicand has an extended sign bit so that the multiplier can unify 8-bit signed and unsigned.High-speed multiplier design is usually divided into three key steps: partial product generation circuit, accumulator and adder. In this paper, the partial product gener

6、ation process uses the modified Booth algorithm, so that the partial product addition terms can be effectively reduced. The accumulation of partial products takes 3-2 compressor and 4-2 compressor to compress. The final result is obtained with select carry adder.Key words: multiplier the modified Bo

7、oth algorithm compressor select carry adder 目 录毕业设计成绩评定表1 前言1.1 乘法器的研究背景和意义微电子技术的迅猛发展，计算机技术的不断进步，带动了集成电路工艺的不断增进，数字芯片的集成度不断提高。在经历了小规模、中规模、大规模的发展过程之后，目前集成电路已经进入超大规模和甚大规模集成电路阶段，SOC（System on Chip）时代也已经到来。数字芯片的发展一直遵循着英特尔公司的主要创始人戈登摩尔（Gordon Moore）提出的摩尔定律：芯片的集成度每三年翻两番，特征尺寸缩小倍。由于可使用的芯片面积增加，为了进一步提高运算性能，目前越来

8、越多的处理器包含多个运算单元，算术运算单元已经成为处理器结构中的一个重要组成部分。而乘法器又是运算器不可或缺的重要组成单元，所以对乘法器的研究具有一定的意义。在高速数字信号处理器、微处理器等各类芯片中，乘法器是必不可少的算术逻辑单元。乘法器往往处于关键延时路径中，它对系统的运算速度有很大影响。为实现流水线的正常工作，乘法运算往往需要在一个时钟周期内完成，另一方面，随着便携式可移动数字产品市场和芯片集成度的不断增加，要求系统在保持高速的同时，具有较低的功耗，才能保持设备的长时间可靠工作。因此，高速低功耗的乘法器的设计是运算器系统设计中的关键。目前在乘法器的实现中，制约其性能提高的因素主要有以下几

9、个方面：部分积生成速度与面积的冲突、部分积的相加延迟过大、版图实现的规则性和紧凑性难以提高。乘法器的设计思想，就是在乘法器设计的结构复杂度，以及乘法器最终的运算速度，电路完成后的占用芯片的面积这几个因素之间进行均衡。1.2 乘法器的研究发展状况迄今为止，关于乘法器实现研究的著作和论文已经有很多。乘法器作为处理器最主要的模块之一，在大量文献中均有研究。过去的十年，修正Booth算法进一步扩展了 Booth编码算法的空间，以传输管逻辑、多路选择器和动态技术为基础的各种电路实现方法持续刷新着高性能乘法器的实现记录。与此同时，与物理实现紧密相关的乘法器拓扑结构的研究也硕果累累。乘法器研究上的里程碑应该

10、从A.D.Booth在1951年提出的Booth编码方法和Wallace的树型压缩开始。其中Wallace介绍了著名的用于压缩部分积的Wallace树结构。随后在1961年O.L.Mcsorley把Booth算法中的每次交叠检验乘法的两位推广到每次交叠检验三位，即著名的修正Booth算法，或称Booth2算法，这种方法使得部分积数目减少一半。1965年Dadda提出的计数器的概念，可将3:2计数器推广到4:2，5:2和9:2等，进一步减少Wallace树所需计数器个数。进入上世纪九十年代之后，Bewick提出了冗余Booth3算法，使得Booth 3可以在略多于Booth 2的时间内完成。进一

11、步扩展到基16、基32、乃至基256的Booth算法也被提出和研究。拓扑结构方面，进位保留加法器被广泛使用，双阵列、高阶阵列用于提高阵列拓扑结构的速度。Shen和Weinberger提出了4:2压缩器用于构成较Wallace树更规整的二进制树，延迟平衡树Zuras和McAllister首先提出，倒阶梯树也可用于改善树型结构的规整性。乘法器算法方面已经日趋完善。与此相应的，可用于乘法器最后求和运算的各种加法器结构层出不穷。在电路实现方面，1981年，Weinberger提出了具有更高压缩比和对称性的4:2压缩单元以代替全加器和半加器完成部分积的求和工作。此举不仅降低了布局困难，而且可以缩短关键路

12、径，平衡端口延迟，极大的提高了运算速度。1995年Ohkubo基于传输管逻辑实现了4.4ns的54位乘法器，同时提出了新的4:2压缩单元结构和进位选择加法器结构。1996年，Hanawa实现了4.3ns的54位乘法器，同一年，Makino实现了8.8ns的54位冗余二进制编码乘法器。1997年Inoue提出了符号选择Booth解码和改进的4:2压缩单元结构，实现了4.lns的54位乘法器。1998年Hagihara基于动态技术和传输管逻辑实现了2.7ns的54位乘法器，同年Carlson介绍了6.0ns的64位乘法器实现方法。2001年Itoh实现了一个600MHz的两级流水线的54位乘法器。

13、2003年，Cho基于标准单元库实现了一个3.25ns的54位乘法器，并提出了改进的进位选择加法器结构。除了提高乘法器的速度以外，各种结构的编码单元，改进的规整的树型压缩结构，以及乘法器的低功耗设计等也得到了广泛而深入的研究。2 总体方案确定2.1 乘法器设计方案本文采用了一种改进Booth编码算法，实现8位带/无符号并行乘法器，并选择3-2压缩器和4-2压缩器组成的部分积累加器及选择进位加法器为最终加法器结构实现乘法器的设计（王定，等，2007）。高速乘法器的关键就是要提高并行计算量，减少后续的计算量。Booth编码算法是广泛采用的算法，它可以减少一半的乘法乘积项，大大提高运算速度。而部分积

14、的相加采用3-2压缩器和4-2压缩器，它可以将乘法的时间复杂度降低。最终加法器则用选择进位加法器实现。算法运算可分为3部分来实现：Booth编码和译码；压缩器；最终加法器（李磊，等，2008）。 2.2 硬件描述语言VHDL2.2.1 硬件描述语言 所谓硬件描述语言，就是利用该语言可以描述硬件电路的逻辑功能、电路结构和连接形式。硬件描述语言是一种用于设计硬件电子系统的计算机语言，适合大规模电路系统的设计。例如一个32位的加法器，利用传统的图形输入软件需要输入500至1000个门，而利用VHDL语言只需要书写一行代码A=B+C即可。而且VHDL语言可读性强，易于发现错误和修改。硬件描述语言可以在

15、不同的层次上描述数字系统。比如，描述电阻、晶体管及其之间相互连线关系的，称为开关级描述；描述基本逻辑门、触发器及其之间相互连线关系的，称为门级描述；在更高层面上描述寄存器及其之间数据传递的，称为寄存器传输级描述。目前得到广泛认可的硬件描述语言有VHDL 和 Verilog两种。2.2.2 VHDL语言简介 VHDL的英文全名是 VHSIC(Very High Speed Integrated Circuit) Hardware Description Language，于1983年由美国国防部正式推出，1986年VHDL被建议作为IEEE 标准，经过多次更改后，直到1987年12月，它才被IE

16、EE接纳为硬件描述语言标准(IEEE STD 1076)，该标准经过不断完善和更新，最近的标准为 IEEE 1164标准，己经被IC生产厂家和 EDA工具提供商所接受。当前几乎所有的 EDA软件，比如SYNOPSYS,MENTOR GRAPHICS,COMPASS,CADANCE等都支持该项标准。VHDL已经成为硬件描述语言的业界标准之一。 VHDL是一种全方位的硬件描述语言，包括系统行为级、寄存器传输级和逻辑门级多个设计层次,支持结构、数据流、行为三种描述形式的混合描述，因此VHDL几乎覆盖了以往各种硬件描述语言的功能，整个自顶向下或自底向上的电路设计过程都可以用VHDL来完成。VHDL主要

17、用于描述的结构、行为、功能和接口。除了含有许多具有硬件特征的语句外，VHDL的语言形式和描述风格与句法是十分类似于一般的。VHDL的程序结构特点是将一项工程设计，或者称作设计实体（可以是一个元件，一个电路模块或一个系统）分成外部（或者称可视部分,及端口)和内部（或者称不可视部分），既涉及实体的内部功能和算法完成部分。在对一个设计实体定义了外部界面后，一旦其内部开发完成后，其他的设计就可以直接调用这个实体。这种将设计实体分成内外部分的概念是VHDL系统设计的基本点。2.2.3 VHDL的基本结构一个VHDL设计系统是由若干个VHDL文件构成，每个文件主要包含如下三个部分中的一个或全部，分别是程序

18、包（Package）、实体（Entity）和结构体（Architecture）。已在设计实体中定义过的数据类型、子程序或数据对象对于其他设计实体是不可用的，或者说是不可见的。为了使已定义的常数、数据类型、元件调用说明以及子程序等能被更多其他设计实体方便地访问和共享，可以将它们收集在一起作为一个程序包。多个程序包可以并入一个VHDL库中，使之适用于更一般的访问和调用范围。程序包主要是用来定义结构体和实体中要用到的数据类型、元件和子程序等。VHDL实体作为一个设计实体（独立的电路功能结构）的组成部分，其功能是对这个设计实体与外部电路进行接口描述，即定义了一个设计模块的外部输入和输出端口。实体是设计

19、实体的表层设计单元，实体说明部分规定了设计单元的输入输出接口信号或引脚，描述了一个元件或一个模块与其他部分之间的连接关系，它是设计实体对外的一个通信界面。一个设计可以包含有多个实体，只有处于最高层的实体称为顶层实体，EDA工具的编译和仿真都是对顶层实体进行的。处于低层的各个实体可作为单个元件，被高层实体调用。 结构体是实体所定义的设计实体中的一个组成部分。结构体描述设计实体的内部结构和外部设计实体端口间的逻辑关系。结构体通常包括对数据类型、元件等元素的说明部分、描述实体逻辑行为的功能描述语句和外部元件端口的连接。每个实体可以有多个结构体，每个结构体对应着实体的不同结构和算法实现方案，其间的各结

20、构体的地位是同等（王志功，等，2010）。 2.2.4 VHDL的优点与其他硬件描述语言相比，使用VHDL进行工程设计有以下优点：VHDL支持自上向下和基于库的设计方法，而且支持同步电路、异步电路、现场可编程门阵列器件(FPGA)以及其他随即电路的设计。VHDL具有比其他硬件描述语言更强大的行为描述能力，基于抽象的行为描述风格避开了具体的器件结构，使设计人员能从逻辑行为上描述和设计大规模电子系统。目前流行的EDA工具和VHDL综合器大都能实现行为描述到RTL描述的转换。VHDL具有强大的系统硬件描述能力。VHDL具有多层次的设计描述功能，既可以描述系统级电路，又可以描述门级电路。而描述既可以采

21、用行为描述、寄存器传输描述或结构描述，也可以采用三者混合的混合级描述。另外，VHDL支持惯性延迟和传输延迟，还可以准确地建立硬件电路模型。VHDL支持预定义的和自定义的数据类型，给硬件描述带来较大的自由度，使设计人员能够方便地创建高层次的系统模型。VHDL对设计的描述具有相对独立性。设计人员用VHDL进行设计时，不需要首先考虑选择完成设计的器件，就可以集中精力进行设计的优化。当设计描述完成后，可以用多种不同的器件结构来实现其功能。设计者可以不懂硬件的结构，也可以不管最终设计的目的器件是什么，而进行独立的设计。VHDL支持广泛、易于修改。由于VHDL已经成为IEEE标准所规范的硬件描述语言，目前

22、大多数EDA工具都支持VHDL，这为VHDL的进一步推广和广泛应用奠定了基础。在硬件电路设计过程中，主要的设计文件是用VHDL编写的源代码，因为VHDL易读和结构化，所以易于修改设计。VHDL具有强大的移植能力，易于共享和调用。VHDL是一种标准化的硬件描述语言，同一个设计描述可以被不同的工具所支持，使得设计描述的移植成为可能。采用基于库(Library)的设计方法，可以建立各种可再次利用的模块。这些模块可以预先设计或使用以前设计中的存档模块，将这些模块存放到库中，就可以在以后的设计中进行调用，可以使设计成果在设计人员之间进行交流和共享，减少硬件电路设计。由于VHDL具有类属描述语句和子程序调

23、用等功能，对于完成的设计，在不改变源程序的条件下，只需改变类属参量或函数，就能轻易地改变设计的规模和结构。VHDL语句的行为描述能力和程序结构，也决定它对具有支持大规模设计的分解和已有设计的再利用功能。VHDL具有丰富的仿真语句和库函数，使得门电路级的功能仿真、检查成为可能，可随时对系统进行仿真模拟，使设计者在任何大系统的设计早期就能对整个工程设计的结构和功能的可行性做出判断。VHDL作为一种IEEE的工业标准，使VHDL的设计成果便于重复利用和交流。这就更进一步推动了VHDL语言的推广和完善。另外,由于其语法严格,给阅读和使用带来极大的便利。2.3 实验工具MAX+plus2.3.1 MAX

24、+plus简介MAX+plus(或写成Maxplus2,或MP2)是Altera公司推出的第三代PLD开发系统。 MAX+plus界面友好，使用便捷，容易上手，使用MAX+plus的设计者不需精通器件内部的复杂结构。设计者在MAX+plus上可以用自己熟悉的设计工具（如原理图输入或者是硬件描述语言）完成设计输入、元件适配、时序和功能仿真、编程下载整个流程。MAX+plus提供了一种与结构无关的设计环境，方便设计者进行设计输入、快速处理和器件编程，同时其设计速度非常快，对于一般几千门的电路设计，使用MAX+plus，从设计输入到器件编程完毕，到用户拿到设计好的逻辑电路，大约只需要几小时，而设计处

25、理一般在几分钟内完成。MAXplus开发工具在国内使用很普遍，同时拥有完备的在线帮助，被公认为是最易使用、人机界面最友善的PLD开发软件。初学者可以很快学习掌握该工具的使用，完成高性能的设计。2.3.2 MAX+plus的设计流程MAXplus的设计流程包括设计输入编辑、编译网表提取、数据库建立、逻辑综合、逻辑分割、适配、延时网表提取、编程文件汇编（装配）及编程下载9个步骤。具体可分为五大步骤，如图1所示。设计输入综合或编译适配器件下载仿真图1 MAXplus设计流程2.3.3 MAX+plus的特点（1）开放的界面。MAX+plus支持与Cadence，Exemplarlogic，Mento

26、r Graphics，Synplicty，Viewlogic和其它公司所提供的EDA工具接口。（2）与结构无关。MAX+plus系统的核心Complier支持Altera公司的FLEX10K、FLEX8000、FLEX6000、MAX9000、MAX7000、MAX5000和Classic可编程逻辑器件，提供了世界上唯一真正与结构无关的可编程逻辑设计环境。 （3）完全集成化。MAX+plus的设计输入、处理与较验功能全部集成在统一的开发环境下，这样可以加快动态调试、缩短开发周期。 （4）丰富设计库。MAX+plus提供丰富的库单元供设计者调用，其中包括74系列的全部器件和多种特殊的逻辑功能（M

27、acro-Function）以及新型的参数化的兆功能（Mage-Function）。 （5）模块化工具。设计人员可以从各种设计输入、处理和较验选项中进行选择从而使设计环境用户化。 （6）MAX+plus软件支持各种HDL设计输入选项，包括VHDL、Verilog HDL和Altera自己的硬件描述语言AHDL。（7）MAX+plus软件具有开放核的特点，允许设计人员添加自己认为有价值的宏函数。2.4 现场可编辑门阵列（FPGA）2.4.1 FPGA简介FPGA的英文全名是 Field Programmable Gate Array。现场可编程门阵列，是一个含有可编辑元件的半导体设备，是一个可供

28、使用者程式化的逻辑门元件。 以硬件描述语言（Verilog 或 VHDL）作为设计输入，经过简单的综合与布局，快速的烧录至 FPGA 上进行测试，是现代 IC 设计验证的技术主流。这些可编辑元件可以被用来实现一些基本的逻辑门（比如AND、OR、XOR、NOT）或者更复杂一些的组合功能比如解码器或数学方程式。在大多数的FPGA里面，这些可编辑的元件里也包含记忆元件例如触发器或者其他更加完整的记忆块。系统设计师可以根据需要通过可编辑的连接把FPGA内部的逻辑块连接起来。一个出厂后的成品FPGA的逻辑块和连接可以按照用户的设计而改变，这样可以实现满足用户要求的专用集成电路，真正达到了用户自行设计、自

29、行研制和自行生产集成电路的目的。2.4.2 FPGA的基本结构FPGA一般由三种可编程电路和一个用于存放编程数据的静态存储器SRAM组成。这三种可编程电路是：可编程逻辑块CLB (Configurable Logic Block)、输入/输出模块IOB (I/O Block)和可编程内部连线PI（Programmable Interconnect）。FPGA的基本结构如图2所示，可编程逻辑块(CLB)是实现逻辑功能的基本单元，它们通常规则地排列成一个阵列，散布于整个芯片；可编程输入/输出模块(IOB)主要完成芯片上的逻辑与外部封装脚的接口，它通常排列在芯片的四周；可编程内部连线包括各种长度的连

30、线线段和一些可编程连接开关，它们将各个CLB之间或CLB、IOB之间以及IOB之间连接起来，构成特定功能的电路（潘松，等，2005）。FPGA的功能由逻辑结构的配置数据决定。工作时，这些配置数据存放在片内的SRAM或熔丝图上。基于SRAM的FPGA器件，在工作前需要从芯片外部加载配置数据，配置数据可以存储在片外的EPROM或其他存储体上。用户可以控制加载过程，在现场修改器件的逻辑功能，即所谓的现场编程。可编程内部连线PI输入输出块IOB可编程逻辑块CLB图2 FPGA的结构原理2.4.3 FPGA的特点总的来说，FPGA器件具有下列优点：高密度、高速率、系列化、标准化、小型化、多功能、低功耗、

31、低成本，设计灵活方便，可无限次反复编程，并可现场模拟调试验证。使用FPGA器件，一般可以在几天到几周内完成一个电子系统的设计和制作，缩短研制周期，达到快速上市和进一步降低成本的要求。其基本特点有：一是采用FPGA设计ASIC电路，用户不需要投片生产，就能得到合用的芯片。 二是FPGA可做其它全定制或半定制ASIC电路的中试样片。 三是FPGA内部有丰富的触发器和I/O引脚。 四是FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。 五是FPGA采用高速CHMOS工艺，功耗低，可以与CMOS、TTL电平兼容。 FPGA是由存放在片内RAM中的程序来设置其工作状态的，因此，工作

32、时需要对片内的RAM进行编程。用户可以根据不同的配置模式，采用不同的编程方式。 加电时，FPGA芯片将EPROM中数据读入片内编程RAM中，配置完成后，FPGA进入工作状态。掉电后，FPGA恢复成白片，内部逻辑关系消失，因此，FPGA能够反复使用。FPGA的编程无须专用的FPGA编程器，只须用通用的EPROM、PROM编程器即可。当需要修改FPGA功能时，只需换一片EPROM即可。这样，同一片FPGA，不同的编程数据，可以实现不同的电路功能，使用非常灵活。FPGA有多种配置模式：并行主模式为一片FPGA加一片EPROM的方式；主从模式可以支持一片PROM编程多片FPGA；串行模式可以采用串行P

33、ROM编程FPGA；外设模式可以将FPGA作为微处理器的外设，由微处理器对其编程。3 理论分析及设计3.1 乘法器的数据格式3.1.1 二进制的表示二进制数用0和1两个数码来表示数，而且分为无符号数和带符号数。无符号数的所有位都可以表示数值的大小，带符号数的最高有效位表示数值的正负，其余位表示数值大小。带符号数可以采用原码、反码和补码三种表示法，实际上，任何正数的反码和补码都和原码表示相同，但负数的原码、反码、补码则各自有不同的表达方式。正负在计算机中只能用0和1表示，正数的符号位用0表示，负数的符号位用1表示。符号位用0和1表示正负，数值部分用二进制绝对值表示数值大小，这种表示法称为原码。正

34、数的反码与原码相同，符号位为0，其余为数值位。而负数的反码是将负数的原码符号位保持不变，而数值部分按位取反。负数的补码是在数值原码在不改变符号位的基础上，将其余数据位取反并在最低位加 1。3.1.2 无符号数的运算与十进制一样，二进制也可以进行加减乘除四则运算，加法的规则是逢二进一，减法的规则是借一当二，乘法的规则是1与1乘为1，其他为0。3.1.3 带符号数的运算带符号数用其补码表示后，其运算方法与二进制的运算相同，但也会出现其特有的问题。带符号数的符号占用了1个二进制数的最高有效位，当运算结果数值超过二进制数所能表达的范围时，其值就进入符号位，因而可能改变其运算结果的符号，得到错误的结果，

35、运算结果超出了数值范围，故称为“溢出”。在带符号数的运算中，判别其运算结果是否溢出可以归结为，若运算结果的数值向前进位（称为CP），其符号运算向前进位（称为CF），则溢出的判别为CPCF。这种逻辑“异或”操作结果为1，则运算结果有溢出。3.1.4 带符号数的符号扩展表示在补码数相加的过程中，由于数据宽度不同，所以在进行某些运算时需要将数据进行符号扩展，否则运算过程中可能结果会出错。无符号数扩展，仅在其数据扩展位加上若干位0即可；而带符号数的扩展实际是扩展其符号，即正数前补0，负数前补1。例如-1+1=0，图3显示了不使用符号扩展和使用符号扩展进行计算的过程。 图3 有符号数相加由上图可知，左边

36、的运算没有使用符号扩展，-1的数据宽度为4，而1的数据宽度为8，两个数相加得到的和为16，这明显是错误的。而右边的运算使用了符号扩展，将-1的数据宽度扩展到8位，两个8位数-1和1相加，结果溢出，得到了正确的结果0。3.2 乘法器算法乘法器的实现可以采用多种算法，比较常用的有移位相加算法、Booth算法、改进型 Booth算法等，各个算法都有自己的特点，下面对这些算法进行简单的比较和分析。3.2.1 移位相加算法移位相加算法是一种简单且容易理解的算法。这个算法将n位带符号数分成一位符号位和n-1位数码位，处理过程包括对符号位和对数码位处理的两个过程。对于符号位，可以用异或门处理，如果符号位相同

37、，则最后的符号为 0，如果符号位不同，则为 1。对数码位的处理是通过逐项移位相加原理来实现，首先从乘数的最低位开始，每次取一位，判断该位乘数是1还是0，若是1，则该位乘数与被乘数相乘产生的部分积是被乘数本身，若是0，则产生的部分积为0。然后将产生的部分积与上次部分积相加后逻辑右移一位。接着取乘数的高一位，继续重复上述步骤，直至乘数移到的最高位，则移位相加的操作结束。最后还需要将符号位与数码位的处理结果统一，才能得到最终乘积。移位相加算法在处理带符号数乘法运算上非常简单明了，但它对带符号数的处理只是单纯将符号位与数码位分开，这样存在两个明显的缺点。首先，符号位是单独处理的，这使得最终乘积的符号还

38、需根据符号位的运算结果进行修正，增加了控制部件的难度；其次，数码位运算中存在着许多不必要的运算，这样的运算不仅没有减少乘数数目，也没有减少部分积数目，将导致运算速度的降低。总之，移位相加算法是建立在无符号数运算基础上的一种间接补码乘法算法。它对数码位的处理类似于无符号数的操作，因而该算法延时比较长，运算速度较慢（傅志晖，等，2003）。3.2.2 Booth算法A.D.Booth 在 1951 年提出了Booth算法，主要是为了解决带符号位乘法运算中出现的符号修正问题。下面简单介绍这种算法。设带符号乘数 ，同时设置一个附加位用于辅助运算，并规定。此时对乘数B进行一些变换如下公式所示 则可以推出

39、乘积补码，如下式所示。 由上式可知，该算法通过取乘数的和的差来产生对应的部分积，和的取值可以有表1所示的四种组合，当和的差值为0时，部分积的对应值为0左移j位；当和的差值为-1时，部分积的对应值为被乘数的补码且左移j位；当和的差值为1时，部分积的对应值为被乘数左移j位。如表1所示。表1 Booth算法的编码结果0000110110该算法对于用补码表示的两位数相乘不需要进行符号位修正，但是对于带符号数乘法来说，该算法会产生n个编码项和n个部分积，需要 n 次移位。由表1可知，一个部分积为0的概率为1/2，由于部分积为0实际上不需要相加，所以平均需要 n/2 次加法。相对于传统的移位加算法，所以它

40、并不能很好的减少完成一次乘法所需要的时钟周期数。该算法并没有提高乘法器的速度，并且部分积编码和产生逻辑更复杂，使得硬件面积增加。3.2.3 改进型Booth算法1961 年 O.L.Macsorley 将Booth 算法中的乘数每次两位交叠检验推广到每次三位交叠检验，这种算法即著名的 Booth-MacSorley 算法也叫改进 Booth 算法。改进 Booth 算法使编码数减少一半，即使部分积的个数减少一半，从而提高了乘法器的运算速度并降低了硬件复杂度。同样设带符号乘数B，对 B 的补码进行变换，如下公式所示，假设 n 为偶数（Booth A D，1951）。 则可以推出乘积补码，如下式所

41、示。 由上式可知，该算法通过重叠扫描乘数的3位，取乘数的和的和减去2倍来产生对应的部分积。上式是适用于n为偶数的情况下，当乘数为奇数为时，乘数需要通过符号扩展使位数变成偶数个，即将最高符号位向高一位扩展作为辅助位，这个扩展的辅助位不会影响编码结果（应征，等，2003）。根据位数奇偶把辅助位补上之后，便可以开始对乘数进行编码，从最低辅助位向高位选择连续的三位，然后保留选取的最高位，继续向高位选取连续的两位组成新的三位，以此类推，相应的取值可以有表2所示的八种组合，而实际上对被乘数进行的处理产生的部分积只有5种，如表2所示。表2 改进Booth算法的编码结果00000010100112100101

42、1101110 图4通过以下几个步骤详细说明两个9 位的带符号数采用了改进Booth算法相乘的过程。从图4可知，9个实心圆表示9位带符号数，乘数是奇数位，所以向高一位扩展一位符号数，用空心圆表示，同时补上一位辅助位，用三角符号表示。首先对乘数进行改进 Booth 编码，产生的5个编码用实心三角符号表示。每个编码对应产生一个部分积，5个编码对应产生6个部分积。因为该算法采用的是补码运算，所以当编码结果为负数时，要把被乘数逐位取反并在最低位加上1。如果将最低位要加的数用s表示，那么s的取值刚好跟编码结果的正负一样，若编码结果为正，则s为0，若为负，则s为1。 图4 8位数相乘过程 每次产生的部分积

43、最后都需要和其他的部分积进行相加，但是每次产生的部分积数据宽度不用，正如上文提到，在补码数相加的过程中，如果补码数的数据宽度不同，需要将数据进行符号扩展，否则运算过程中可能结果会出错。所以每个部分积都需要扩展成18位数，扩展位用E表示。E的取值由编码结果的符号和被乘数的符号共同决定，并且规定编码得到的部分积为0，则E为0。用表3来简单说明，其中正用0表示，负用1表示。表3 Booth编码中的有关符号位Booth2 编码符号 最低位要加的数s被乘数的符号部分积的符号 E0000001111011110 部分积扩展符号位后增加了部分积的位数，明显影响到乘法器的速度。 因此，可以采用符号扩展简化技术

44、对部分积进行处理，即将连续的n个E用连续的n个1乘以表示。假设一个扩展数EEEEXXXXX，则会有这样的等价关系1111XXXXX =EEEEXXXXX。对部分积进行简化处理之后，扩展符号位出现了固定的连续的数 1，而且相加会得到固定的结果，所以在部分积压缩中利用这种关系可以简化符号扩展。 3.3 加法器3.3.1 半加器半加器和全加器是算术运算电路中的基本单元，它们完成的是1位二进制数相加的一种组合逻辑电路（康华光，2006）。如果只考虑两个加数本身，而没有考虑低位进位的加分运算，称为半加。实现半加运算的逻辑电路称为半加器。两个1位二进制数的半加运算的逻辑真值表可用表4所示。其中A、B是两个

45、加数，S表示和，C表示进位数。表4 半加器的真值表ABCS0000010110011110 用逻辑表达式来表示输出为S =AB C = AB 从上述表达式可知，半加器有异或门和与门组成。半加器也可以作为压缩器使用，它把和值信号传到同权值的下级，进位信号传到高一位权值的下级，不进行级联。 3.3.2 全加器全加器能进行加数、被加数和低位来的进位信号相加，并根据求和结果给出该位的进位信号，即全加器能实现两个二进制数和一个进位信号相加的功能，逻辑真值表如表 5所示，其中A和B分别是被加数和加数，Cin是低位进位数，S为本位和，Cout为向高位的进位数。表5 全加器的真值表ABCinCoutS0000

46、000101010010111010001101101101011111用逻辑表达式来表示输出为S = ABCin Cout=AB+（AB）Cin 从上述表达式可知，全加器是有两个半加器和一个或门构成的。3.3.3 串行进位加法器若有多位数相加，则可采用并行相加串行进位的方式来完成。如果有两个n位二进制数相加，可以采用n-1个全加器和一个半加器，如图5所示。FA 代表全加器，HA 代表半加器。图5 串行进位加法器每个加法器的低位进位输出作为下一个加法器的进位输入，最低位由于没有进位输入只需要半加器。任意1位的加法运算必须在低1位的运算完成之后才能进行，这种进位方式成为串行进位，此种加法器称为串行进位加法器。这种加法器的逻辑电路比较简单，面积小，易于理解，但是运算速度不高，延时大。其关键路径是所有加法器的进位链路径，延时正比于相加位数，为O(n)。3.3.4 超前进位加法器在串行进位加法器中，每个加法器要等到上一级加法器产生进位输出才能产生有效的