基于FPGA的快速并行平方器

liyf

介绍了一种二进制补码快速并行平方器的设计方法，并给出了一个6位二进制补码平方器的例子及在MAX+PLUS II 10.0环境下的仿真结果。
关键词：FPGA，二进制补码，平方器


1 引言
平方器在科学技术的许多领域被广泛应用，例如图像压缩及通信技术。在实际FPGA设计中，比较常用的方法是直接将乘法器用作平方器，即将相同数据直接送至两输入乘法器的输入端，从而完成平方运算。但用此方法实现平方器存在两个主要缺点：一是速度慢；二是浪费资源。如果使用查表法实现平方器，虽然能够提高运算速度，但当输入数据位数比较长时，所用资源是非常巨大的。本文所介绍的设计方法可以有效克服速度与资源的矛盾，从而设计出既节省资源又快速的平方器。
2 平方器的实现原理
对于输入为n位的二进制补码，无论其是正数还是负数，经平方运算后都为正数，所以平方器的输出结果只需要2n-1位就可以表示了，默认的符号位为零可以省略。假设输入数据为长度为6位的二进制补码，则平方器输出为11位。根据参考文献[1]，可推得平方运算的具体过程如图1（a）所示。图中数字符号即代表输入数据的对应位，横杠表示取反，“1”表示二进制数1。图1（a）的原理对于二进制补码的正、负数均适用。从图中可以看出，由于乘数与被乘数相同，乘积项是沿对角线对称分布的。这样，根据二进制加法的特点，可以将对角线以上的乘积项左移一位，从而将对角线以下的乘积项消去，如图1（b）所示。观察图1（b）可发现，由于输出平方值的P0等于输入X0与自身相与，所以就等于X0，而P1则总等于零。运用上述观察到的特点，可以大大简化电路设计并提高运算速度。下面的设计就是依据图1（b）进行的。




　




3 平方器的FPGA实现
由图1（b）可以看出，用FPGA实现平方运算，可以分两步：第一步，产生乘积项；第二步，用串行进位加法器将乘积项逐行相加，最后得出结果。这样做虽然思路简单清晰，但有一个缺点，就是在使用串行进位加法器时，因为加法器存在进位传送延迟，使得在对每一行乘积项相加时都存在进位延迟，从而降低了运算速度。为减少进位延迟的影响，可以分三步来实现平方运算：第一步，产生乘积项；第二步，运用全加器及半加器将第一列的乘积项压缩为只有两项，原理如图2所示。其中，A、B是加法器的两个加数输入端，Ci是进位输入端，Co、Su分别是进位输出端与本位和输出端，并假设该列有5个乘积项（加上前一列的进位项），分别用a、b、c、d、e来表示。这样，只需一个全加器和一个半加器就可将乘积项压缩为两项，同时产生两个进位项。用此方法对每一列进行压缩，这样经压缩后的乘积项就只有两行；第三步，将第二步产生的两行乘积项送至进位传送加法器相加，得到平方值。可以看出，用第二种方法实现平方器，在对乘积项进行压缩时不存在进位传送延迟，而只在第三步存在加法器的进位延迟，因此可以大大提高运算速度。下面就举一个6位平方器的便子来说明如何用第二种方法实现平方器。原理如图3所示（图中，correct项对应于二进制数1，“0”表示二进制数0）。第一步，产生乘积项。因为每个乘积项是由输入数据的对应比特相与产生的，所以，对于产生电路用语言描述比用图形描述更为方便，此处使用VHDL语言来描述乘积项产生电路；第二步，通过全加器及半加器组成的网络，将乘积项压缩为两行。从图1（b）可以看出，按列进行乘积项压缩，由于每一列的乘积项缺乏规律性，不便于用语言来描述，所以此处使用图形输入法来描述乘积项压缩电路，图3中虚线框内的部分就是乘积项压缩电路；第三步，将压缩得到的两行乘积项送至串行进位加法器相加，得到平方值。图3中虚线框以外的部分就是最后的串行进位加法器。





图4（a）是用MAX+PLUS II 10.0仿真得到的结果。通过观察图4（a）的仿真结果可以发现，由于组合电路的竞争与冒险，使得输出结果有毛刺。这个问题可以通过加流水线的方法来解决。图4（b）是经流水线处理后的输出波形，毛刺被完全消除。





4 性能分析与比较
此处，我们使用的FPGA器件是Altera公司的EPM7064LC44-7，用于比较的乘法器是MAX+PLUS II的LPM库中的乘法器LPM_MULT。对于本文的平方器，共使用了15个逻辑单元，占资源的23%；对于LPM_MULT，共使用了35个逻辑单元，占资源的54%。在资源的使用上节省了一半多。为比较两种平方器的工作速度，我们使用了MAX+PLUS II中时序逻辑电路性能分析功能，即在输入、输出端口加上D触发器，然后进行定时分析。结果显示，本文的平方器可以工作的最高频率是76.92MHz，而LPM_MULT工作的最高频率是35.71MHz。由此可见，无论是资源的使用还是工作速度，本文所介绍的平方器都具有很大的优越性。

参考文献

1 L.Dadda. Fast Multipliers for Tow’s-Complement Num-bers in Serial Form. IEEE Symp. Computer Arithmetic. Urbana,I11,June 1985
2 侯伯亨，顾新.VHDL硬件描述语言数字逻辑电路设计.西安：西安电子科技大学出版社，1999，9
3 宋万杰，罗丰，吴顺君.CPLD技术及其应用.西安：西安电子科技大学出版社，1999，9