问题描述

给定位宽为 N 的向量，检测其从 高位到低位（MSB） 第一个 1 出现的位置，向量为 0 时输出 0。示例如下

输入向量 输出向量
8’b0010_1101 8’b0010_0000
8’b0100_0000 8’b0100_0000
8’b0000_0000 8’b0000_0000

下述模块均采用 组合逻辑 实现，例化参数如下

参数 描述
VECTOR_WIDTH 向量位宽

端口定义如下

端口 方向 类型 说明
seq IN [VECTOR_WIDTH-1:0] 输入向量
pos OUT [VECTOR_WIDTH-1:0] 输出位置

仿真验证

由于不同方法所设计的模块端口完全相同，此处通过修改 VECTOR_DETECT_MODE 参数完成对不同模块的仿真测试，仿真文件如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
`timescale 1ns / 1ns

`define VECTOR_WIDTH 16
`define VECTOR_DETECT_MODE `VECTOR_DETECT_COMPL
`define VECTOR_DETECT_CASEZ 0
`define VECTOR_DETECT_DIVDE 1
`define VECTOR_DETECT_COMPL 2
`define VECTOR_DETECT_SHIFT_XOR 3

module vector_detect_tb;

    reg  [`VECTOR_WIDTH-1:0] seq;
    wire [`VECTOR_WIDTH-1:0] pos;

    generate
        if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_CASEZ) begin
            vector_detect_casez vector_detect_casez_inst (
                .seq(seq),
                .pos(pos)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_DIVDE) begin
            vector_detect_divide #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_divde_inst (
                .seq(seq),
                .pos(pos)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_COMPL) begin
            vector_detect_compl #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_compl_inst (
                .seq(seq),
                .pos(pos)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_SHIFT_XOR) begin
            vector_detect_shift_xor #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_shift_xor_inst (
                .seq(seq),
                .pos(pos)
            );
        end
    endgenerate

    initial begin
        for (seq = 0; seq < ~0; seq = seq + 1'b1) begin
            #1;
        end
        #10 $stop;
    end

endmodule

注意：暴力破解法（VECTOR_DETECT_CASEZ）不支持参数化，因此修改 VECTOR_WIDTH 参数无效

性能测试

为对比不同模块的 资源占用 和 时序性能，此处在所有模块上对位宽 16 的向量进行综合测试，所有模块均在 Artix-7 系列 XC7A100TFTG256-1 平台综合实现（采用 默认综合策略），顶层模块和约束如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
`define VECTOR_WIDTH 16
`define VECTOR_DETECT_MODE `VECTOR_DETECT_COMPL
`define VECTOR_DETECT_CASEZ 0
`define VECTOR_DETECT_DIVDE 1
`define VECTOR_DETECT_COMPL 2
`define VECTOR_DETECT_SHIFT_XOR 3

module vector_detect_top (
    input                          clk,
    input                          rst_n,
    output reg [`VECTOR_WIDTH-1:0] pos
);

    reg  [`VECTOR_WIDTH-1:0] seq;
    wire [`VECTOR_WIDTH-1:0] pos_w;

    generate
        if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_CASEZ) begin
            vector_detect_casez vector_detect_casez_inst (
                .seq(seq),
                .pos(pos_w)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_DIVDE) begin
            vector_detect_divide #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_divde_inst (
                .seq(seq),
                .pos(pos_w)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_COMPL) begin
            vector_detect_compl #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_compl_inst (
                .seq(seq),
                .pos(pos_w)
            );
        end else if (`VECTOR_DETECT_MODE == `VECTOR_DETECT_SHIFT_XOR) begin
            vector_detect_shift_xor #(
                .VECTOR_WIDTH(`VECTOR_WIDTH)
            ) vector_detect_shift_xor_inst (
                .seq(seq),
                .pos(pos_w)
            );
        end
    endgenerate

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            seq <= 'b0;
        end else begin
            seq <= seq + 1'b1;
        end
    end

    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            pos <= 'b0;
        end else begin
            pos <= pos_w;
        end
    end
    
endmodule
1
create_clock -period 3.000 -name clk [get_ports clk]

不同模块的综合结果如下，综合考虑灵活性、资源占用和时序性能，推荐使用 二分法

FMAX LUT WNS TNS 参数化 资源占用 工作频率
穷举法 435 MHz 20 0.057 ns 0.156 ns ❌ ⭐⭐ ⭐⭐
二分法 455 MHz 19 0.006 ns 0.203 ns ✅ ⭐⭐⭐ ⭐⭐⭐
独热加法 345 MHz 33 0.007 ns 0.193 ns ✅ ⭐ ⭐
错位相或法 435 MHz 19 0.045 ns 0.216 ns ✅ ⭐⭐⭐ ⭐⭐
  1. FMAX 即最大工作频率，由满足 WNS 和 TNS 均大于 0 条件的最小时钟周期换算而来
  2. 为了满足时序要求，综合工具往往会通过插入寄存器等方法对模块进行优化，因此同一模块不同工作频率下的资源占用不尽相同。此处资源数据为 FMAX 工作频率下 顶层文件 的资源占用，仅供参考
  3. 不同模块 FMAX 相同时 不能 通过 WNS 和 TNS 比较性能，因为 Vivado 采用 尽力而为 的综合策略，即以满足时序要求为目标，不追求宽裕的 WNS 和 TNS

模块实现

本文提供了常用的 穷举法、二分法、独热加法 和 错位相减法 四种向量 1 检测思路和具体实现，实际上向量 1 检测的思路还有很多，比如遍历向量所有比特位

1
2
3
4
5
6
7
generate
    for (genvar i = 0; i < VECTOR_WIDTH - 1; i = i + 1) begin
        assign pos[i] = seq[VECTOR_WIDTH-1:i+1] ? 1'b0 : seq[i];
    end
endgenerate

assign pos[VECTOR_WIDTH-1] = seq[VECTOR_WIDTH-1];

或者使用 if-else

1
2
3
4
5
6
7
if (seq[15]) begin
	pos = 16'b1000_0000_0000_0000;
end
else if (seq[14]) begin
	pos = 16'b0100_0000_0000_0000;
end
else if ...

上述方法或与本文所提方法 思路相似，或 性能和资源占用 没有优势，因此没有列出

穷举法

简洁明了，无需多言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
module vector_detect_casez (
    input      [15:0] seq,
    output reg [15:0] pos
);

    always @(*) begin
        casex (seq)
            16'b1xxx_xxxx_xxxx_xxxx: pos = 16'b1000_0000_0000_0000;
            16'bx1xx_xxxx_xxxx_xxxx: pos = 16'b0100_0000_0000_0000;
            16'bxx1x_xxxx_xxxx_xxxx: pos = 16'b0010_0000_0000_0000;
            16'bxxx1_xxxx_xxxx_xxxx: pos = 16'b0001_0000_0000_0000;
            16'bxxxx_1xxx_xxxx_xxxx: pos = 16'b0000_1000_0000_0000;
            16'bxxxx_x1xx_xxxx_xxxx: pos = 16'b0000_0100_0000_0000;
            16'bxxxx_xx1x_xxxx_xxxx: pos = 16'b0000_0010_0000_0000;
            16'bxxxx_xxx1_xxxx_xxxx: pos = 16'b0000_0001_0000_0000;
            16'bxxxx_xxxx_1xxx_xxxx: pos = 16'b0000_0000_1000_0000;
            16'bxxxx_xxxx_x1xx_xxxx: pos = 16'b0000_0000_0100_0000;
            16'bxxxx_xxxx_xx1x_xxxx: pos = 16'b0000_0000_0010_0000;
            16'bxxxx_xxxx_xxx1_xxxx: pos = 16'b0000_0000_0001_0000;
            16'bxxxx_xxxx_xxxx_1xxx: pos = 16'b0000_0000_0000_1000;
            16'bxxxx_xxxx_xxxx_x1xx: pos = 16'b0000_0000_0000_0100;
            16'bxxxx_xxxx_xxxx_xx1x: pos = 16'b0000_0000_0000_0010;
            16'bxxxx_xxxx_xxxx_xxx1: pos = 16'b0000_0000_0000_0001;
            default:      pos = 8'b0000_0000;
        endcase
    end

endmodule

穷举法性能和资源占用中规中矩，主要缺点是 无法参数化

二分法

将向量 V 分为两个 位宽相等 的子向量 A 和 B，即 V={A,B}V=\left\{A,B\right\}，分别在 A 和 B 中寻找第一个 1 的位置（此处采用 递归 算法实现）

  • 如果 A 不为 0，则第一个 1 在 A 中
  • 如果 A 为 0，则第一个 1 可能在 B 中（也可能为 0）

该模块递归向量阈值为 2，因此 向量位宽必须为偶数。如果向量位宽为奇数，可将其分为 1bit + 偶数位宽向量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
module vector_detect_divide #(
    parameter  VECTOR_WIDTH     = 16,
    localparam VECTOR_SUB_WIDTH = VECTOR_WIDTH >> 1
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    wire [1:0][VECTOR_SUB_WIDTH-1:0] sub_pos;

    generate
        if (VECTOR_WIDTH == 2) begin
            assign pos = { seq[1], seq[1] ? 1'b0 : seq[0] };
        end else begin
            vector_detect_divide #(
                .VECTOR_WIDTH(VECTOR_SUB_WIDTH)
            ) vector_detect_0 (
                .seq(seq[0+:VECTOR_SUB_WIDTH]),
                .pos(sub_pos[0])
            );

            vector_detect_divide #(
                .VECTOR_WIDTH(VECTOR_SUB_WIDTH)
            ) vector_detect_1 (
                .seq(seq[VECTOR_WIDTH-1-:VECTOR_SUB_WIDTH]),
                .pos(sub_pos[1])
            );

            assign pos[VECTOR_WIDTH-1-:VECTOR_SUB_WIDTH] = sub_pos[1];
            assign pos[0+:VECTOR_SUB_WIDTH] = sub_pos[1] ? 'b0 : sub_pos[0];
        end
    endgenerate

endmodule

二分法资源占用和时序性能都比较优秀，且可以参数化，推荐使用

独热加法

非常巧妙的方法，但由于引入了加法器，资源占用和时序性能均比较差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
module vector_detect_compl #(
    parameter VECTOR_WIDTH = 16
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    wire [VECTOR_WIDTH-1:0] seq_trans;
    wire [VECTOR_WIDTH-1:0] pos_trans = (~seq_trans + 1'b1) & seq_trans;

    generate
        for (genvar i = 0; i < VECTOR_WIDTH; i = i + 1) begin
            assign seq_trans[i] = seq[VECTOR_WIDTH-1-i];
        end
    endgenerate

    generate
        for (genvar i = 0; i < VECTOR_WIDTH; i = i + 1) begin
            assign pos[i] = pos_trans[VECTOR_WIDTH-1-i];
        end
    endgenerate

endmodule

错位相或法

考虑向量

V=8′b01001010V=8'b01001010

如果能通过某种方法构造出如下向量

  • A=8′b01000000A=8'b01000000（或 B=8′b10111111B=8'b10111111）
  • C=8′b11000000C=8'b11000000（或 D=8′b00111111D=8'b00111111）

那么通过简单运算（与、非等）即可得到向量中的第一个 1，下面将介绍如何构造向量 D=8′b00111111D=8'b00111111（向量中第一个 1 及之前的位置均为 0，之后的位置均为 1）

  1. 由向量 DD 定义可知 D[7]=0D[7]=0
  2. D[6]=V[7] ∣ D[7]=0 ∣ 0=0D[6]=V[7]\ |\ D[7]=0\ |\ 0=0
  3. D[5]=V[6] ∣ D[6]=1 ∣ 0=1D[5]=V[6]\ |\ D[6]=1\ |\ 0=1
  4. ......
  5. D[n−1]=V[n] ∣ D[n]D[n-1]=V[n]\ |\ D[n]

上述计算方法看起来可能有点突兀，我们不妨代入所有递推公式

D[n]=V[n+1] ∣ D[n+1]=V[n+1] ∣ V[n+2] ∣ D[n+2]=...=V[n+1] ∣ V[n+2] ∣ ...V[N−1]D[n]=V[n+1]\ |\ D[n+1]=V[n+1]\ |\ V[n+2]\ |\ D[n+2]=...=V[n+1]\ |\ V[n+2]\ |\ ...V[N-1]

显然，向量 DD 中的每个比特位，实际上就是 向量 VV 在该位置前所有比特的或值。某种程度上说，这也是一种“遍历”算法，用 Verilog 描述可能更为直观

1
2
3
4
5
6
7
8
9
wire [VECTOR_WIDTH-1:0] D;

assign D[VECTOR_WIDTH-1] = 1'b0;

generate
    for (genvar i = 0; i < VECTOR_WIDTH-1; i = i + 1) begin
        assign D[i] = |[VECTOR_WIDTH-1:i+1];
    end
endgenerate

上述代码稍加改造其实可以直接求出向量 VV 中的第一个 1 的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module vector_detect_shift_ergodic #(
    parameter VECTOR_WIDTH = 16
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    assign pos[VECTOR_WIDTH-1] = seq[VECTOR_WIDTH-1:0];

    generate
        for (genvar i = 0; i < VECTOR_WIDTH-1; i = i + 1) begin
            assign pos[i] = [VECTOR_WIDTH-1:i+1] ? 1'b0 : seq[i];
        end
    endgenerate

endmodule

然而经过综合测试，上述模块的资源占用和时序性能都比较差，因此没有单独列出。下面给出 错位相或法 的具体实现，其中 seq_pre 即构建出的向量 DD

1
2
3
4
5
6
7
8
9
10
11
12
13
module vector_detect_shift_xor #(
    parameter VECTOR_WIDTH = 16
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    wire [VECTOR_WIDTH-1:0] seq_pre;

    assign seq_pre = { 1'b0, seq[VECTOR_WIDTH-1:1] | seq_pre[VECTOR_WIDTH-1:1] };
    assign pos = seq & (~seq_pre);

endmodule

错位相或法在 时序要求不高时资源占用最少，可结合实际应用选择

拓展应用

向量 1 检测属于比较基础的模块，下面将介绍一些拓展应用

LSB

从向量的低位到高位，寻找第一个 1 出现的位置。这个实现其实非常简单，只要将输入输出的高低位顺序调换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
module vector_detect_r2l #(
    parameter VECTOR_WIDTH	= 16
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    wire [VECTOR_WIDTH-1:0] seq_trans;
    wire [VECTOR_WIDTH-1:0] pos_trans;

    generate
        for (genvar i = 0; i < VECTOR_WIDTH; i = i + 1) begin
            assign seq_trans[i] = seq[VECTOR_WIDTH-1-i];
            assign pos[i] = pos_trans[VECTOR_WIDTH-1-i];
        end
    endgenerate

    vector_detect_l2r #(
        .VECTOR_WIDTH(VECTOR_WIDTH)
    ) vector_detect_l2r_inst (
        .seq(seq_trans),
        .pos(pos_trans)
    );

endmodule

双向 1 检测

分别从高位到低位、从低位到高位寻找第一个 1 出现的位置，示例如下

输入向量 输出向量
8’b0010_1101 8’b0010_0001
8’b0100_0000 8’b0100_0000
8’b0000_0000 8’b0000_0000

该模块的实现也比较简单，将 MSB 和 LSB 输出相或即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
module vector_detect_both_side #(
    parameter VECTOR_WIDTH	= 16
) (
    input  [VECTOR_WIDTH-1:0] seq,
    output [VECTOR_WIDTH-1:0] pos
);

    wire [VECTOR_WIDTH-1:0] pos_l2r;
    wire [VECTOR_WIDTH-1:0] pos_r2l;
    
    assign pos = pos_l2r | pos_r2l;

    vector_detect_l2r #(
        .VECTOR_WIDTH(VECTOR_WIDTH)
    ) vector_detect_l2r_inst (
        .seq(seq),
        .pos(pos_l2r)
    );
    
    vector_detect_r2l #(
        .VECTOR_WIDTH(VECTOR_WIDTH)
    ) vector_detect_r2l_inst (
        .seq(seq),
        .pos(pos_r2l)
    );

endmodule

参考资料

  1. 关于“1”的verilig相关手撕代码
  2. Verilog找向量中的第一个1位置-一些想法