极客工场

Appearance

共 2,781 字预计阅读约 9 分钟

乘法器与桶形移位：移位加，与一拍移任意位 ​

更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」入门层（beginner）数字逻辑基础第十九篇。加法器 讲了两数相加，这一篇把数据通路里另一类最吃硬件、也最影响时序的运算讲清楚——乘法，以及和乘法形影不离的移位。

本文要回答的问题 ​

  • 二进制乘法为什么能化成「移位 + 相加」？部分积是什么？
  • 无符号阵列乘法器怎么用与门和全加器搭出来？为什么乘法又大又慢？
  • 有符号补码乘法难在哪，Booth 编码凭什么又处理符号又减少部分积？
  • 华莱士树/Dadda 树用什么办法把很多排部分积快速压成两排？
  • 逐拍移位的移位寄存器和一拍移任意位的桶形移位器差在哪，各用在哪？

一、二进制乘法就是小学竖式 ​

先看无符号数。回忆十进制竖式：乘数的每一位去乘被乘数，得到一行行部分积（partial product），低位行左移对齐，最后全部加起来。二进制更简单——乘数位只有 0 和 1：

bash
        1101   (13)
      × 1011   (11)
      ------
        1101   ← 乘数 b0=1：被乘数左移 0 位
       1101·   ← b1=1：被乘数左移 1 位
      0000··   ← b2=0：全 0 行
     1101···   ← b3=1：被乘数左移 3 位
      ------
    10001111   (143)

规则可以一句话概括：乘数位 bi 为 1，就把被乘数 A 左移 i 位作为第 i 行部分积；为 0，该行就是全 0。而「左移 i 位」在硬件里不过是连线错位、不花门，「bi 为 1 才放行」正好用一个与门 Ai·bi 实现。于是 n×n 乘法需要 n² 个与门产生 n 排部分积，再用加法器把这 n 排数加起来。

还有一个必须记住的尺寸事实：两个 n 位数相乘，结果最多 2n 位。Verilog 里写 y = a*b 若把 y 也声明成 n 位，高位会被静默截断——这是 定点数设计里最高频的位宽错误之一，乘法结果寄存器务必按 2n（或按定标分析后的宽度）声明。

二、阵列乘法器：与门矩阵 + 全加器阵列 ​

把上面的竖式直接「固化」成电路，就是阵列乘法器（array multiplier）：

  1. 顶部一片 n×n 的与门阵列，按位产生全部部分积；
  2. 下方用一排排全加器逐行累加：每来一排部分积，和上一排的累加和、进位对齐相加；
  3. 最末一排可用一个行波进位或超前进位加法器收成最终结果。

它的优点是结构规整、容易布局，在早期和小位宽里很常见；缺点也明显：部分积有 n 排，进位要穿过很多级全加器，延迟随操作数位宽增长很快，面积约按 n² 膨胀。这就是为什么在时序报告里乘法常常出现在关键路径上——它本质是「一片加法器阵列」，比单个加法器重得多。理解这一点，你就明白为什么 AI 加速器要把成千上万个乘法做成规整的 MAC 阵列、为什么 FPGA 干脆准备专用硬块。

三、有符号乘法与 Booth 编码 ​

无符号的「是 1 就加」对补码不成立——最高位是负权（权重为 −2ⁿ⁻¹），不能照正数那样直接产生部分积。早期做法要先对负数取绝对值、乘完再恢复符号，既慢又费逻辑。更聪明的办法是 Booth 编码，它的直觉来自一个改写：

bash
连一串 1 不必逐个加，例如 0111 = 8 − 1：
  与其「+4 +2 +1」做三次加法，
  不如「+8 −1」只做一次加、一次减。

Booth 算法扫描乘数位，看相邻两位 (bᵢ, bᵢ₋₁) 的组合决定本行动作：00/11 不加不减、01 加被乘数、10 减被乘数（减用补码加法实现）。这样一串连续的 1 被合并成「串尾加一次、串头减一次」，既自动正确处理了补码符号（减操作天然兼容负数），又常常减少了非零部分积的排数。改进的 Radix-4 Booth 一次看三位、把乘数两两分组，直接把部分积排数减半，是现代乘法器的标准第一步。

Booth 之后还剩大约 n/2 排部分积要相加。若一排排串行加，延迟仍大；于是有了下一步的压缩优化。

四、华莱士树与 Dadda：用压缩器并行求和 ​

关键洞察：把多排数加起来，不必关心进位在哪一排，只要尽快减少「数的排数」。**华莱士树（Wallace tree）**和 Dadda 树大量使用 3:2 压缩器（compressor）——它就是一个全加器：把同一列上的 3 个输入比特压成 1 个本位（sum）和 1 个进到高位的进位（carry），3 进 2 出，列上的待加数从 3 个变 2 个。

chip-design/beginner/23-multiplier-shifter.md D2 示意图

每经过一层 3:2 压缩，待加的排数约降为原来的 2/3，log 级几层之后，几十排部分积就被压成两排（sum 与 carry），最后只需一个快速的超前进位加法器（CLA）把这两排收成最终乘积。Wallace 追求尽快压缩（延迟小、用的压缩器多），Dadda 则在每一层「只压到下一层刚好够用」，省器件、末端加法器稍长——两者是面积/速度的折中。现代高性能乘法器还会用 4:2 压缩器等进一步缩短树高。

这套「产生部分积（与门/Booth）→ 压缩树减排 → 末端加法」的三段结构，是所有乘法器的通用骨架。在 FPGA 上，位宽和级联关系合适的乘法会被推断（infer）进 DSP48 硬核（内含乘法器和加法器，见 FPGA DSP48 初认识），既省大量 LUT 又快；写得不规整（位宽截断、加法插在乘法中间打断级联）则会退回用通用逻辑拼阵列，又大又慢。

五、移位：移位寄存器 vs 桶形移位器 ​

移位和乘法、定点定标、串并转换天然绑定：左移一位在二进制里等于 ×2，右移等于 ÷2，浮点对阶、定点 Q 格式定标都靠它。但「移位」有两种实现哲学，别混为一谈。

第一种：移位寄存器（时序，逐拍移）。在 寄存器、计数器与移位寄存器 里见过——每个时钟沿把所有 bit 向相邻触发器挪一位，要移 k 位就得花 k 个周期。它省硬件（就是一排 FF 接线）、能配合串行数据流逐位吞吐，用于串并转换、线性反馈移位寄存器（LFSR）、UART 串并收发。

第二种：桶形移位器（barrel shifter，组合，一拍移任意位）。它是一块纯组合逻辑，输入「数据 + 移位量 shamt」，一个周期内就能移任意指定位数。经典实现是一排多级 MUX 交叉开关：移位量按二进制逐位控制每一级——最低位控制「移不移 1 位」，下一位控制「移不移 2 位」，再下一位「移不移 4 位」……log₂(n) 级 MUX 就能在 n 路里任选移位量（和 MUX 树、CLA 一个数量级的对数思想）。

对比移位寄存器桶形移位器
类型时序（用时序元件 FF）纯组合（MUX 阵列）
移 k 位耗时k 个时钟周期1 个周期（穿过几级 MUX）
硬件一排 FF，很省n 位宽要一片 MUX 矩阵，较大
典型用途串并转换、LFSR、逐位协议浮点对阶、ALU 移位指令、即时定标

CPU 的 ALU 里的移位/循环指令用的就是桶形移位器（配合 加法器与 ALU），因为指令要求这一拍给出结果；而与慢外设打交道、逐位收发时，移位寄存器更自然。右移还要注意算术与逻辑之分：无符号数右移左端补 0（逻辑移位），补码有符号数右移要复制符号位（算术右移）才能保持除以 2 的语义，这和 数制与编码里的符号扩展是同一回事，写错会把负数右移成大正数。

与现有篇目的衔接 ​

总结 ​

一句话总结：二进制乘法回到小学竖式——乘数位为 1 就把被乘数左移相应位、为 0 就是全 0，「左移」只是连线错位、「为 1 放行」用一个与门，故无符号阵列乘法器由 n² 个与门产生部分积再用全加器阵列累加，结构规整但面积约 n²、进位穿多排而又大又慢，且 n×n 乘积达 2n 位、结果寄存器必须留足位宽；有符号补码因最高位是负权不能照搬，Booth 编码按相邻位决定本行加、减或不加，把连续的 1 合并成「串尾加、串头减」，既自动处理符号又常减少部分积，Radix-4 Booth 再把排数减半；华莱士树/Dadda 树用 3:2 压缩器（全加器）层层把多排部分积压到只剩 sum、carry 两排再交末端 CLA，是「产生部分积→压缩树→末端加法」通用乘法骨架，FPGA 上规整乘法会被推断进 DSP48 硬块；移位则分两种哲学——移位寄存器靠一排触发器逐拍挪一位、省硬件适合串并转换和 LFSR，桶形移位器用 log₂(n) 级 MUX 交叉开关在一拍内移任意位、面积较大但供 ALU 移位指令和浮点对阶使用，有符号数右移还须复制符号位做算术右移才能保持除以 2 的语义。