桶形移位器与分级 MUX

先修知识：应理解 MUX^{i多路选择器 根据选择信号，把多个输入之一连接到输出的组合电路。必须规定选择位与输入编号的对应关系。了解更多}、逻辑与算术移位，以及组合电路传播延迟^{i传播延迟 从输入变化到输出稳定为正确值所需的时间。逻辑表达式等价与时间特性是两回事。了解更多}。

将可变移位转为固定连线的选择

逐位移动的移位寄存器^{i寄存器 存储多位状态的电路。本课程中的同步寄存器在时钟边沿存储指定输入。了解更多}需要与移位次数相同的时钟数。桶形移位器接收移位量，在一条组合路径中生成结果。比特并非随时间反复移动，而是通过选择连线路径，把所需位置的输入位连接到输出。

将 16 位数值移动 0~15 位时，移位量为 $s=s_0+2s_1+4s_2+8s_3$。因此串联四个阶段，分别移动 1、2、4、8 位。每级 MUX 在“原样通过”与“移动固定位置数”之间选择。

例如 11 的二进制是 1011，选择 1、2、8 位阶段，跳过 4 位阶段。将 $X=0xD2A5$ 逻辑右移，各级依次得到 0x6952、0x1A54、0x1A54、0x001A。这些是四个组合阶段的中间值，不是四个时钟周期的值。

每级有 16 个 MUX，共四组，即 64 个单比特 2:1 选择点。这是布线与常量传播优化前的结构数量。一般在 $W=2^K$ 时，数据选择结构规模与 $W\log_2W$ 成正比，深度与 $\log_2W$ 成正比。即使为每个输出分别写一个 W:1 MUX，综合后也可能变成树状结构，因此不能凭 RTL 行数断定面积或频率。

将输入 0xD2A5 逻辑右移 11 位。图中标出移位量 1011 各位选择的四个组合阶段，并不是跨四个时钟执行。

用右移电路实现左移

先反转位顺序，逻辑右移 s 位，再反转回来，就得到逻辑左移。利用这种对称性可共享四个阶段，但还需加入输入与输出方向选择 MUX，因此总成本并不止 64 个。无需动态选择的固定位反序本身只是布线。

算术右移在空出的高位填入原始输入的符号位。左移时，即使处于算术模式也补 0。在二进制补码^{i二进制补码 用固定位宽位串表示有符号整数的方法。n 位范围为 −2^(n−1) 到 2^(n−1)−1。了解更多}中，算术左移与逻辑左移产生相同位移动，并不会自动检查 signed 溢出。

移位量范围也是电路约定的一部分。下例用五位 shamt 接收 0~31。移位量不小于 16 时，逻辑移位与左移结果为 0，算术右移结果为 16 个符号位。若只使用 shamt 的低四位，就会把移位 16 误当成移位 0，因此必须单独处理。

module barrel16 (
  input  wire [15:0] x,
  input  wire [4:0] shamt,
  input  wire left,
  input  wire arithmetic,
  output wire [15:0] y
);
  wire fill;
  wire [15:0] stage [0:4];
  assign fill = (!left) && arithmetic && x[15];

  for (genvar i = 0; i < 16; i++) begin : direction
    assign stage[0][i] = left ? x[15-i] : x[i];
    assign y[i] = shamt[4] ? fill :
                  (left ? stage[4][15-i] : stage[4][i]);
  end

  for (genvar k = 0; k < 4; k++) begin : shift_stage
    localparam int D = 1 << k;
    assign stage[k+1] = shamt[k]
      ? {{D{fill}}, stage[k][15:D]}
      : stage[k];
  end
endmodule

generate 中的 k 是构建电路时确定的常数，并不是运行时把循环执行四次的装置。每级的部分选择和重复拼接长度固定，因此表现为四种固定布线与 MUX。fill 不随级数改变，所以选择多个阶段时仍按同一个符号扩展。

此 RTL 显式指定符号填充，因此也能对 unsigned^{iunsigned 将位串解释为非负整数的规则。n 位范围为 0 到 2^n−1，可能与同一位串的 signed 解释不同。了解更多} 向量实现算术移位。若改用运算符简写，算术右移需要 signed 操作数和 >>>。不要认为只写 >>>，或只把部分选择的原变量声明为 signed 就一定安全。拼接与部分选择可能失去 signed 解释，应先转为具有目标位宽的 signed 值。综合工具支持的运算符可参阅 AMD 的 Verilog 表达式文档。

分别处理延迟与信息损失

四个组合阶段之外，还要加上方向选择、范围选择和布线延迟。若时序不足，可在中间插入寄存器，但剩余移位量与方向控制也必须随数据延迟相同周期。此时输出延迟^{i延迟 从接受输入到产生对应输出的时间或周期数。它不同于单位时间处理量，即吞吐率。了解更多}发生改变，不能再将其视为与纯组合模块相同的接口。

移位无法恢复被截掉的信息。unsigned 左移时，只要移出的高位有一个为 1，就发生越界。signed 越界还需考虑原符号和被截位；本模块不输出这些标志。此外，负数算术右移相当于除以 $2^s$ 后向下取整。因此 $-3$ 右移一位为 $-2$，不同于向零截断整数除法得到的 $-1$。