基于Sklansky结构的24位并行前缀加法器的设计与实现

姚若河++马廷俊++苏少妍

摘 要： 针对串行进位加法器存在的延时问题，采用一种基于Sklansky结构的并行前缀加法器，通过对并行前缀加法器各个模块进行优化，设计实现了一个24位并行前缀加法器。通过与24位串行进位加法器进行延时比较，结果表明，Sklansky并行前缀结构的加法器，能有效提高运算速度。

关键词： 并行前缀加法器； Sklansky结构； 优化延时； 并行思想

中图分类号： TN402?34； TP332.2 文献标识码： A 文章编号： 1004?373X（2015）21?0145?04

Design and implementation of 24?bit parallel prefix adder based on Sklansky structure

YAO Ruohe， MA Tingjun， SU Shaoyan

（School of Electronic and Information Engineering， South China University of Technology， Guangzhou 510640， China）

Abstract： Aiming at the delay problem of serial carry adder （SCA）， a parallel prefix adder （PPA） based on Sklansky was adopted. A 24?bit PPA was designed and realized on the basis of optimizing the various modules of PPA. By comparing the delay of 24?bit PPA with that of 24?bit SCA， the results show that the parallel prefix adder based on Sklansky can increase the computing speed effectively.

Keywords： parallel prefix adder； Sklansky structure； optimization delay； parallel thinking

0 引 言

在数字信号处理电路中，离不开最基础的加法器部件，而形式最简单的加法器是串行进位加法器（Serial Carry Adder，SCA）。但SCA因其自身逻辑的缺陷造成了极大的延时，无法满足各种高速处理器所要求具有的高运算速度。随着集成电路工艺的快速提升，集成电路的集成度已经越来越高，但运算速度一直制约着VLSI技术的发展，设计与实现各种高速加法器是一个研究热点。随着集成电路的发展，大规模的并行处理技术将代替串行处理技术。

本文采用一种有效且快捷的加法器设计，即并行前缀加法器（Parallel Prefix Adder，PPA）。由于PPA内部具有规整的运算结构单元，因而非常适合基于VLSI技术的高性能微处理器、专用DSP芯片、现场可编程门阵列芯片等的实现。一方面，当比特数大于4位时，PPA的延时情况要短于SCA的延时情况[1]；另一方面，根据实际需求与设计指标，PPA有多种可实现的并行前缀结构。本文基于Sklansky结构设计实现了一个24位的PPA。

1 理论基础

1.1 算法原理

假设有两个24 b的二进制数[A23A22A21…A2A1A0]与[B23B22B21…B2B1B0，]记[Gi]为两二进制数各自的第[i]比特相与的结果，[Pi]为两二进制数各自的第[i]比特相异或的结果，即：

图2 24位基于Sklansky结构PPA核心部分的构成

另一方面，运用上述原理求出了每一位的进位信息，因而求和结果中的各个位的情况由式（4）求得，如[S8=G7：0P8。]

3 24位PPA主要模块设计

3.1 数据预处理模块

24位二进制数中的每一位相与信息以及相异或信息在后续处理步骤中都需要使用，因而24位PPA需要首先对两个输入的加数进行数据预处理，其实现的方法为：对两个数中对应的每一比特数使用一个与门以及一个异或门处理。该模块共分别需要与门和异或门24个。与门的输出为[Gi，]异或门的输出为[Pi，]将这些预处理信息传送到下一模块进行处理。

3.2 4位PPA模块

该模块在24位PPA中共有6个，且这6个4位PPA的组成均相同。现在以处理第0～3位的4位PPA为例。4位PPA中仍然体现着并行的思想，即先同时求得[G1：0]和[G3：2，]再同时求得[G2：0]和[G3：0。]根据式（3），求解[G1：0=G1：1+G0：0P1：1=G1+G0P1，]其中G1，G0和P1是在数据预处理模块后得到的。以同样的方法可以求解[G3：2。]下一步求解[G2：0=G2：2+G1：0P2：2=G2+G1：0P2]以及[G3：0=G3：2+][G1：0P3：2=G3：2+G1：0P3P2，]其中[G1：0]和[G3：2]从上一步中获得。这样，4位PPA中所有位的进位情况均已求出，且上述四个步骤均分别使用一个与门和一个或门，外加求[P3：2]的一个与门共5个与门和4个或门。4位PPA的电路结构如图3所示。6个4位PPA则需要30个与门和24个或门。

3.3 8位PPA与16位PPA模块

8位PPA由2个4位PPA构成，并通过进一步的连接实现。以处理第0～7位的8位PPA为例，由第一个4位PPA得出的[G3：0，]以及第二个4位PPA得出的[G4：4，][G5：4，][G6：4]和[G7：4，]根据式（3），可求得[G4：0，][G5：0，][G6：0]和[G7：0。]同样地，这四个步骤均分别使用一个与门和一个或门，外加求[P4P5P6P7]的三个与门共7个与门和4个或门。8位PPA的电路结构如图4所示。6个4位PPA连接成3个8位PPA则需要额外的21个与门和12个或门。

图4 8位PPA电路结构

同样地，16位PPA由2个8位PPA构成，可由第1个8位PPA的[G7：0]与第2个8位PPA的[Gt：8]（t=8，9，…，15）求得[Gt：0]（t=8，9，…，15）。这些步骤加上求P8P9…P15共使用的门电路数目为15个与门和8个或门，这也是16位PPA所需的额外门电路。

由图2可以看出，结合求解0～15位的16位PPA与16～23位的8位PPA就可以得出24位PPA的核心模块，不过这两部分的结合也需要像上述的2个8位PPA构成16位PPA那样需要额外的门电路，这部分同样需要15个与门和8个或门。

3.4 求和模块

根据式（4），通过数据预处理模块得出了每一位的异或信息，结合各个PPA模块得出进位信息。对于每一位和的情况，可以通过求这两部分相应位上的信息的异或得到。所以，求解第1～23位各个位的和需要23个异或门，而求解第0位的和只需将数据预处理后的第0位的异或信息直接输出即可。

3.5 级联拓展模块

在上面的设计中，没有考虑第0位之前是否有从其他加法器传进来的进位，也就是说，上面的24位PPA设计并不适宜级联从而计算48位甚至更多位的加法。但是，为了提高24位PPA的普适性，增加计算从上一个加法器传进来的进位功能模块是很有必要的，而且无论是从原理上讲还是将其实现，都不复杂。经过分析，综合考虑延时性质与门电路数目，最终决定在PPA处理第0位之前加入该级联拓展模块。

现将传进来的进位信息定为[c，]从数据预处理模块得出的第0位的[P0]与[G0]没有改变，但此时[G0]并不直接连接到0～3位的4位PPA的“[G0]”引脚，而是先计算[G′0=G0+cP0，]而得到的[G′0] 才连接到“[G0]”引脚。另一方面，[S0]也会受到[c]的影响，其计算式为[S0=][cP0。]此时就完成了级联拓展模块的设计，只需增加1个与门、1个或门和1个异或门即可实现，而且不需要改变其他的任何模块。

如果需要级联24位PPA，则将低24位PPA的[G23：0]连接到高24位PPA的[c]即可，而对于最低的24位PPA，[c]需要置0。

4 延时与面积的分析和对比

4.1 Sklansky结构与Kogge?Stone结构、Brent?Kung结构的比较

根据文献[6]，本文的Sklansky结构设计的24位PPA与文献[4]Kogge?Stone结构设计的24位PPA，以及使用Brent?Kung结构之间的性能对比见表1。

4.2 PPA与SCA的比较

在实际应用中，更多使用的是带有级联拓展模块，即允许从上一个加法器传入进位的加法器组合，因此本节将以带有级联拓展模块的24位PPA进行延时和面积的分析，同时也对24位SCA与24位PPA的延时与面积做一对比。

这里将不同种的门所占用的面积与延时设为相等，且所有的门均为两输入门电路。则对于24位PPA，其延时与面积的分析如表2所示。

从表3可以看出，虽然24位SCA所使用的门电路数目为24位PPA的58.0%，但24位PPA的总延时仅为24位SCA的28.6%，也就是说24位PPA的运算速度是24位SCA的3.5倍。

5 结 语

本文通过分解24位基于Sklansky结构的PPA的每一个模块来实现24位PPA，并对24位PPA的面积及延时做了细节分析，最后为表明Sklansky结构的PPA的优越性，将其与不同并行前缀结构的PPA还有24位SCA在面积及延时上做了对比。数据表明， PPA在延时方面上远短于SCA；采用Sklansky并行前缀结构的PPA能有效地提高运算速度。

注：本文通讯作者为姚若河。

参考文献

[1] 徐向民.数字系统设计及VHDL实践[M].北京：机械工业出版社，2007.

[2] 胡剑浩，马上.余数系统原理与在高速数字信号处理中的应用[M].北京：科学出版社，2012.

[3] SMITH A B， LIM C C. Parallel prefix adder design [C]// Proceedings of the 15th International Symposium on Computer Arithmetic. [S.l.]： IEEE， 2001： 218?225.

[4] 赵翠华，娄冕，张洵颖，等.一种改进的基于Kogge?Stone结构的并行前缀加法器[J].微电子学与计算机，2011，28（2）：47?50.

[5] ZAMHARI N， VOON P， KIPLI K， et al. Comparison of parallel prefix adder （PPA）： 2078?0958 [R]. London： the World Congress on Engineering， 2012.

[6] ZIMMERMANN R. Binary adder architecture for cell?based VLSI and their synthesis [D]. Zurich： Swiss Federal Institute of Technology， 1997.

[7] FLOYD T L. Digital fundamentals [M]. 10th ed. Upper Saddle River： Prentice Hall， 2008.