CN119512501A - 一种基于基-4Booth编码和改进Wallace压缩树的乘法器 - Google Patents
一种基于基-4Booth编码和改进Wallace压缩树的乘法器 Download PDFInfo
- Publication number
- CN119512501A CN119512501A CN202411550163.7A CN202411550163A CN119512501A CN 119512501 A CN119512501 A CN 119512501A CN 202411550163 A CN202411550163 A CN 202411550163A CN 119512501 A CN119512501 A CN 119512501A
- Authority
- CN
- China
- Prior art keywords
- carry
- compression
- partial product
- partial
- multiplier
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000007906 compression Methods 0.000 title claims abstract description 40
- 230000006835 compression Effects 0.000 title claims abstract description 36
- 230000001934 delay Effects 0.000 claims description 2
- 238000004364 calculation method Methods 0.000 abstract description 3
- 241001442055 Vipera berus Species 0.000 description 32
- 238000010586 diagram Methods 0.000 description 6
- 238000000034 method Methods 0.000 description 3
- 230000007547 defect Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000006978 adaptation Effects 0.000 description 1
- 239000011159 matrix material Substances 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
本发明涉及一种基于基‑4Booth编码和改进Wallace压缩树的乘法器，包括部分积生成模块：通过采用Radix‑4Booth算法将输入乘数重新编码为多个部分积，形成紧凑的部分积阵列；部分积压缩模块：通过利用改进的Wallace树压缩结构，通过两种压缩器对部分积进行快速压缩，降低计算路径延迟；最终求和模块：使用高速加法器对压缩后的部分积进行求和，得到最终的乘法结果。本发明采用基‑4Booth编码算法，使部分积阵列排列规则，减少了电路面积，采用新的3‑2与4‑2压缩器相混合的树型压缩结构来实现Wallace树，提高了压缩效率并降低关键延迟。
Description
技术领域
本发明涉及电子器件领域，尤其涉及一种基于基-4Booth编码和改进Wallace压缩树的乘法器。
背景技术
乘法器被广泛应用于数字系统中，通常存在功耗高和延迟长的问题；目前的高效和低功耗乘法器算法和架构主要有Booth和Wallace树结构两种。Booth算法通过对乘数的连续位进行编码，生成加减操作以减少部分积的数量，从而提升乘法速度。常见的有基于Radix-4和Radix-8的Booth算法，适用于处理带有较多连续相同位的数。Wallace树形结构采用并行处理和多级压缩来提高乘法运行速度，通过生成部分积矩阵，然后采用树形结构的多级加法器压缩部分积，最终使用高速乘法器求和得到乘法结果。但是，现有乘法器的加法器数量多，结构复杂，部分积生成和压缩过程中依然存在较大的资源消耗和延迟问题。
发明内容
本发明的目的在于克服现有技术的缺点，提供了一种基于基-4Booth编码和改进Wallace压缩树的乘法器，解决了现有技术存在的不足。
本发明的目的通过以下技术方案来实现：一种基于基-4Booth编码和改进Wallace压缩树的乘法器，所述乘法器包括部分积生成模块、部分积压缩模块和最终求和模块；
所述部分积生成模块：通过采用Radix-4 Booth算法将输入乘数重新编码为多个部分积，形成紧凑的部分积阵列；
所述部分积压缩模块：通过利用改进的Wallace树压缩结构，通过两种压缩器对部分积进行快速压缩，降低计算路径延迟；
所述最终求和模块：使用高速加法器对压缩后的部分积进行求和，得到最终的乘法结果。
所述Radix-4 Booth算法对乘数重新编码，并且产生相应的控制信号，根据乘数的数量按照每三位乘数作为一组，每两组重叠一位的方式进行分组，每组按照B＝Bn-1×(-2)n-1+Bn-2×2n-2+…+B1×21+B0×20+B-1的方式进行编码，其中，B表示乘数。
所述两种压缩器包括进位保留加法器和带进位的一位全加器，两种压缩器的关键路径上都有2个XOR门的延时。
所述改进的Wallace树压缩结构由两个进位保留加法器和两个带进位的一位全加器组成；部分积生成模块产生P0-P8一共8个部分积，P0和P1部分积加1后输入到第一进位保留加法器，P1部分积直接输入到第一进位保留加法器，P3-P5部分积输入到第二进位保留加法器，两个进位保留加法器均输入到第一带进位的一位全加器，第一带进位的一位全加器和P6和P7部分积输入到第二带进位的一位全加器。
本发明具有以下优点：一种基于基-4Booth编码和改进Wallace压缩树的乘法器，采用基-4Booth编码算法，使部分积阵列排列规则，减少了电路面积，采用新的3-2与4-2压缩器相混合的树型压缩结构来实现Wallace树，提高了压缩效率并降低关键延迟。
附图说明
图1为本发明的结构示意图；
图2为部分积求和结构示意图；
图3为优化后的异或门逻辑电路图；
图4为优化后的3-2压缩器逻辑电路图；
图5为改进的Wallace树压缩结构示意图；
图6为加法树的压缩过程示意图。
具体实施方式
为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。因此，以下结合附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的保护范围，而是仅仅表示本申请的选定实施例。基于本申请的实施例，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本申请保护的范围。下面结合附图对本发明做进一步的描述。
如图1所示，本发明具体涉及一种基于基-4Booth编码和改进Wallace压缩树的乘法器，用作两个16位符号数的乘法运算，其包括部分积的产生、部分积的压缩、以及最后的两组部分积的快速求和；为了得到良好的树结构压缩的部分积阵列，部分积产生模块中采用了基-4Booth编码，由两个16位的二进制数产生一个由8个部分积组成的排列紧凑规则的阵列。部分积压缩模块中采用改进的Wallace树结构对部分积阵列进行快速压缩，该结构根据部分积的数量，将经过优化后的3-2压缩器和4-2压缩器重新排列，所形成的压缩结构关键路径时延小且资源消耗少。
本发明采用基-4Booth乘法，然后利用Booth编码进行one hot编码，进行部分积四选一。相比于传统乘法运算(或基-2Booth)，基-4Booth乘法只需要n/2-1次加法，n为位宽，极大加快了速度。
基4的Booth编码算法通过公式
B＝Bn-1×(-2)n-1+Bn-2×2n-2+…+B1×21+B0×20+B-1对乘数重新编码，并且产生相应的控制信号，如表1所示。对于16位的乘数，在最低位补一个0后变为17位数，按照每三位作为一组，每两组重叠一位的方式进行分组，将乘数分成了8组。对每组按表1的方式重新编码，表中B表示乘数，A表示被乘数，Bi-1，Bi，Bi+1均为1位数，因此部分积一共只有8种可能性。
表1、Booth编码表
| Bi+1 | Bi | Bi-1 | -2Bi-1+Bi+Bi-1 | PP |
| 0 | 0 | 0 | +0 | 0 |
| 0 | 0 | 1 | +1 | +A |
| 0 | 1 | 0 | +1 | +A |
| 0 | 1 | 1 | +2 | +2A |
| 1 | 0 | 0 | -2 | -2A |
| 1 | 0 | 1 | -1 | -A |
| 1 | 1 | 0 | -1 | -A |
| 1 | 1 | 1 | -0 | 0 |
因此，对于任意位数的乘法，最多只需要w+1+3＝w+4位即可确定每一个部分积(其余位数全为0)，w表示乘数(被乘数)的位宽，即操作数的位数。如图2所示，其中h为尾数，s代表最终产生的部分积的符号位，由原始被乘数符号位和对被乘数的+/-(1为+，0为-)的同或运算得到。
3-2压缩器即进位保留加法器，4-2压缩器即带进位的一位全加器，其关键路径上有2个XOR门(异或门)的延时，其逻辑表达式为：和Sum表示求和，Cout表示输出进位，Cin表示输入借位，如图3和图4所示，可以将部分与项和输出至下一级。
如图5所示，P0～P7为部分积产生模块产生的8个部分积，该结构经过使用全加器与半加器的组合，通过并行运算，8个部分积的压缩只用到了2个CSA(经线路优化后的3-2压缩器)与2个4-2压缩器，缩短了加法运算的路径长度。此外还具有相应的扩展性，可以方便的运用到更高的位宽计算当中。
基于上述改进压缩结构的加法树压缩过程如图6所示，整体分为5个部分：add1_7、32A、32B、42A、42B，其中空白圆代表数据0，h代表pp_generate中在部分积后添加的加一信号，实心圆和C以及S代表有数据或者是生成的数据，HA表示所使用的是半加器，FA代表所使用的是全加器，黑框用42压缩器标明的代表使用的是4-2压缩器进行加法的运算。
add1_7部分中，pp0，pp1为21位输入信号，将第八个部分积的加一信号放至第15位处，HA处使用了6个半加器，生成了S1-S6和C1-C6，其中信号C的权重为2，需要左移一位，因此第15位的pp0_1会空出来，将加一信号h填入，输出新的21位pp0_1和pp1_1。
32A压缩过程中，在第3位和第4位用到了add1_7的方法来使用2个半加器填入加一信号，在第5位到第21位使用17个全加器来实现3缩2的过程，同时全加器会生成C和S信号。32B模块压缩过程中，低位只有两个信号的数据，进行直接输出，第9位和第10位使用了2个半加器，第11到第25位使用了15个全加器，第26位和第27位使用半加器，并且使用上述的进位左移，然后往空白处填入数据的方式，实现了32B的3缩2操作。
42A模块部分，第5位和第6位的数据进行进位左移，Cout作为第24位全加器的进位来实现4-2压缩，使用进位左移，空白填半加器的进位，这种方式来实现4缩2，在第29位的4-2压缩器会生成三个信号Cout、C、S，其中C左移一位，S本位保留，Cout作为第30位全加器的进位来实现4-2压缩，第31位使用半加器来实现3缩2。
以上所述仅是本发明的优选实施方式，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实施例的排除，而可用于各种其他组合、修改和完善，并能够在本文所述构想范围内，通过上述教导或相关领域的技术或知识进行改动。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。
Claims (4)
1.一种基于基-4Booth编码和改进Wallace压缩树的乘法器，其特征在于：所述乘法器包括部分积生成模块、部分积压缩模块和最终求和模块；
所述部分积生成模块：通过采用Radix-4 Booth算法将输入乘数重新编码为多个部分积，形成紧凑的部分积阵列；
所述部分积压缩模块：通过利用改进的Wallace树压缩结构，通过两种压缩器对部分积进行快速压缩，降低计算路径延迟；
所述最终求和模块：使用高速加法器对压缩后的部分积进行求和，得到最终的乘法结果。
2.根据权利要求1所述的一种基于基-4Booth编码和改进Wallace压缩树的乘法器，其特征在于：所述Radix-4 Booth算法对乘数重新编码，并且产生相应的控制信号，根据乘数的数量按照每三位乘数作为一组，每两组重叠一位的方式进行分组，每组按照B＝Bn-1×(-2)n-1+Bn-2×2n-2+…+B1×21+B0×20+B-1的方式进行编码，其中，B表示乘数。
3.根据权利要求1所述的一种基于基-4Booth编码和改进Wallace压缩树的乘法器，其特征在于：所述两种压缩器包括进位保留加法器和带进位的一位全加器，两种压缩器的关键路径上都有2个XOR门的延时。
4.根据权利要求3所述的一种基于基-4Booth编码和改进Wallace压缩树的乘法器，其特征在于：所述改进的Wallace树压缩结构由两个进位保留加法器和两个带进位的一位全加器组成；部分积生成模块产生P0-P8一共8个部分积，P0和P1部分积加1后输入到第一进位保留加法器，P1部分积直接输入到第一进位保留加法器，P3-P5部分积输入到第二进位保留加法器，两个进位保留加法器均输入到第一带进位的一位全加器，第一带进位的一位全加器和P6和P7部分积输入到第二带进位的一位全加器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411550163.7A CN119512501A (zh) | 2024-11-01 | 2024-11-01 | 一种基于基-4Booth编码和改进Wallace压缩树的乘法器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411550163.7A CN119512501A (zh) | 2024-11-01 | 2024-11-01 | 一种基于基-4Booth编码和改进Wallace压缩树的乘法器 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN119512501A true CN119512501A (zh) | 2025-02-25 |
Family
ID=94658787
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411550163.7A Pending CN119512501A (zh) | 2024-11-01 | 2024-11-01 | 一种基于基-4Booth编码和改进Wallace压缩树的乘法器 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN119512501A (zh) |
-
2024
- 2024-11-01 CN CN202411550163.7A patent/CN119512501A/zh active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| TWI783295B (zh) | 乘法器及乘法運算方法 | |
| CN111488133B (zh) | 高基数近似布斯编码方法和混合基数布斯编码近似乘法器 | |
| CN101739231A (zh) | 布斯-华莱士树型乘法器 | |
| CN110955403A (zh) | 近似基-8布斯编码器及混合布斯编码的近似二进制乘法器 | |
| Thomas | Design and simulation of radix-8 booth encoder multiplier for signed and unsigned numbers | |
| Nair et al. | A review paper on comparison of multipliers based on performance parameters | |
| US5944776A (en) | Fast carry-sum form booth encoder | |
| Ahmed et al. | Improved designs of digit-by-digit decimal multiplier | |
| Basha et al. | Design and Implementation of Radix-4 Based High Speed Multiplier for ALU's Using Minimal Partial Products | |
| CN110825346B (zh) | 一种低逻辑复杂度的无符号近似乘法器 | |
| Sharma et al. | Modified booth multiplier using wallace structure and efficient carry select adder | |
| CN119512501A (zh) | 一种基于基-4Booth编码和改进Wallace压缩树的乘法器 | |
| CN115658007A (zh) | 一种高带宽可配流水级的并行乘法器运算方法 | |
| Song et al. | Design of Multiplier Circuit Based on Signed-Digit Hybrid Stochastic Computing | |
| Kumar et al. | A design of low power modified Booth multiplier | |
| CN112860219B (zh) | 并行乘法器及其工作方法 | |
| Sahoo et al. | Delay optimized array multiplier for signal and image processing | |
| Jeevan et al. | Implementation of parallel multiplier based on Booth computing method using FPGA | |
| Kumar et al. | Design and Implementation of Low Power, High-Speed Configurable Approximation 8-Bit Booth Multiplier | |
| Bawaskar et al. | High performance redundant binary multiplier | |
| Sharanya et al. | A MODIFIED PARTIAL PRODUCT GENERATOR FOR REDUNDANT BINARY MULTIPLIERS | |
| Issa et al. | Design and implementation of sign-digit floating point multiplier unit | |
| SUREKHA et al. | Pre Encoded Multipliers Based on Non Redundant Radix-4 Design Using Modified Wallace Scheme | |
| Prathibha et al. | Design and Implementation of Signed Radix-8 Booth Encoded Multiplier Using 5-3 Compressor | |
| Rathore et al. | Implementation and Design of Xilinx based Booth multiplier |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |