基于FPGA的阵列乘法器的设计与实现
基于FPGA 的阵列乘法器的设计与实现
本文先对乘法器进行了分析,然后用现场可编程门阵列(FPGA)实现了阵列乘法器,并分析了设计原理。 0 引言
乘法是运算中的基本算法,应用也最为广泛。在计算机中乘法最基本的操作就是移位相加,各类乘法最终都要归结为这一点。早期计算机中为了简化硬件结构,采用串行的移位乘法方案,即多次执行“加法-移位”操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢,自从大规模集成电路问世以来,出现了各种形式的并行乘法器,一部分即为流水式阵列乘法器。
1 二进制乘法器
设有两个不带符号的M×N位二进制整数:
点击图片查看大图
点击图片查看大图
它们的乘积用X 和表示,按“手工计算”的方法给出就是:
点击图片查看大图
从中可以看出,只要a k ≠0,输入量X 就随着k 的位置连续地变化,然后累加X2。如果a k =0,就可以忽略相应的转换相加。
以201×9为例,可以知道N=8,X=9,A=11001001。当k 由0开始递增时,对A 的a k 位进行分析,a 0=1,则X2=9;a 1=0,则X2=0;„a7=1,则X2=9×128=1152。同时,将计算结果X2:9,0,0,72,0,0,576,1152进行累加。最终各部分结果之和即为201×9的乘积1809。
1.1 移位乘法器
移位乘法器计算过程为:将A 依次向右移一位,并检查其最低位a 0,如果不为零,则将X 与部分和相加,然后将X 向左移一位;如果为零,则仅仅将X 向左移一位。移位时,X 的低端和A 的高端均补零。
可以看出由于第一个操作数X 是并行形式的,而第二个操作数A 是逐位形式的,所以刚才描述的乘法器也称为串行/并行乘法器。如果两个操作数都是串行的,那么这一结构称为串行/串行乘法器。这样的乘法器只需要一个全加器,但是计算乘积所需的时间更长。
1.2 阵列乘法器
移位乘法器是通过牺牲时间来降低复杂性,还有一种方法通过增加复杂性来换取速度,称之为“阵列”,或者叫并行/并行乘法器。
在M×N位不带符号整数的阵列乘法中,每一个部分乘积项(位积)a k x j 叫做一个被加数。这M×N个被加数{ak x j |0≤k≤N-1,0≤j≤M-1}可以用M×N个与门并行地产生,并且并行提交给N2个加法器单元的加法器阵列。图1给出了一个4×4位阵列乘法器逻辑电路。
点击图片查看大图 k 017k
图1 4位阵列乘法器
该乘法器的总的乘法时间可以估算如下:令T a 为与门的传输延迟时间,T f 为全加器(FA)的进位传输延迟时间,假定用2级“与非”逻辑来实现FA 的进位链功能,那么我们就有:
点击图片查看大图
因而得M×N位不带符号的阵列乘法器总的乘法时间T s 为:
点击图片查看大图
这种乘法器要实现N×N位时,需要N (N-1)个全加器和N 个与门。故可以看出,阵列乘法器相对于移位乘法器大大增加了复杂性,但却缩短了时间。 2
2 FPGA技术
FPGA是一类称为现场可编程逻辑(field-programmable logic ,FPL) 器件中的一员。50多年前,匈牙利数学家Neumann 提出了电脑的设计构想,通过中央处理器从存储器中存取数据,并逐一处理各项任务。现在,通过采用可编程芯片FPGA 取代微处理器,电脑可并行处理多项任务。尽管FPGA 芯片的时钟频率要低于奔腾处理器,但是由于FPGA 芯片可并行处理各种不同的运算,所以可完成许多复杂的任务。例如网页显示,全球天气建摸及基因组合核对等,而且处理速度比奔腾处理器或数字信号处理器快得多。
2.1 VHDL
VHDL(VHSIC hardware description language,超高速集成电路硬件描述语言) ,由美国国防部(DOD)制定,是以文本形式来描述数字系统硬件结构和行为,是一种用形式化方法来描述数字电路和系统的语言。
本文通过www.huisheliren.com VHDL语言来描述,使图1所示的4位阵列乘法器的逻辑电路在FPGA 芯片中实现。其代码如下:
点击图片查看大图
需要注意的是,如果完成进位与和累加所需要的时间相同,这一方法就是可行的。 对于现在的FPGA 来讲,进位计算执行的速度要比和累加的速度快,因此产生了另一种结构。这一结构在第一步就将两个相邻的部分乘积结合起来的结果再加到最终输出乘积上。这是一个“手工计算”思想的直接阵列形式。这种阵列乘法器为实现(并行)二叉树乘法器提供了机会,还可以使得引入流水线级更为容易。
3 结束语
由前面的分析,可以看出在实现计算机算法中,结构的复杂程度与执行周期是成反比的。所以各种乘法器的优劣无法一概而论,应根据实际需求和条件选取不同结构的乘法器。