数字IC秋招手撕代码（十）计算最小公倍数与最大公约数

---

题目

---

分析

• 题目要求计算最小公倍数和最大公约数，其中最大公约数可以利用辗转相除法计算得到；

• 而最小公倍数可以先将两数相乘再除最大公约数得到；

• 具体原理在本文就不赘述，需要了解的同学可以移步：辗转相除法的原理

• 此外，因为辗转相除法中用了取模和除法的运算，目前高版本的DC虽然已经支持了‘%’和‘/’的综合，但是在实际工程中还是建议使用IP来完成计算，例如蒙哥马利算法取模、移位减法的除法器；

• 需要注意的是，不论是取模、除法或是辗转相除法本身都有可能需要多时钟周期才能完成，所以如果vld_in信号过快的有效，将影响模块的计算，本方案中使用了busy信号来屏蔽多余的vld_in。
  
  

---

代码

module example(
clk,
rst_n,
A,
B,
vld_in,
lcm_out,
mcd_out,
vld_out
);

parameter       DATA_W      =       8;

input                   clk;
input                   rst_n;
input   [DATA_W-1:0]    A;
input   [DATA_W-1:0]    B;
input                   vld_in;

output  [DATA_W-1:0]    lcm_out;
output  [DATA_W-1:0]    mcd_out;
output                  vld_out;

reg     [DATA_W-1:0]    a;
reg     [DATA_W-1:0]    b;
reg                     busy;
reg                     busy_dly;
reg     [DATA_W-1:0]    mod;

reg     [DATA_W-1:0]    mcd_out;
reg     [DATA_W*2-1:0]  lcm_out_tmp;
reg                     vld_out;


//sample A B
always @(posedge clk or negedge rst_n)begin
    if(!rst_n)begin
        a[DATA_W-1:0] <= {(DATA_W){1'b0}};
        b[DATA_W-1:0] <= {(DATA_W){1'b0}};
    end
    else if(vld_in & !busy)begin
        a[DATA_W-1:0] <= A[DATA_W-1:0]>B[DATA_W-1:0] ? A[DATA_W-1:0] : B[DATA_W-1:0];
        b[DATA_W-1:0] <= A[DATA_W-1:0]>B[DATA_W-1:0] ? B[DATA_W-1:0] : A[DATA_W-1:0];
    end
    else if(busy_dly & busy)begin
        a[DATA_W-1:0] <= b[DATA_W-1:0];
        b[DATA_W-1:0] <= mod[DATA_W-1:0];
    end
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        busy <= 1'b0;
    else if(busy & !(|b[DATA_W-1:0]))
        busy <= 1'b0;
    else if(vld_in & !busy)
        busy <= 1'b1;
end

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

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        mod[DATA_W-1:0] <= {(DATA_W){1'b0}};
    else if(busy & (|b[DATA_W-1:0]))
        mod[DATA_W-1:0] <= a % b;
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        mcd_out[DATA_W-1:0] <= {(DATA_W){1'b0}};
    else if(busy & !(|b[DATA_W-1:0]))
        mcd_out[DATA_W-1:0] <= a[DATA_W-1:0];
end

assign lcm_out[DATA_W-1:0] = lcm_out_tmp[DATA_W-1:0];

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        lcm_out_tmp[DATA_W*2-1:0] <= {(DATA_W*2){1'b0}};
    else if(vld_in)
        lcm_out_tmp[DATA_W*2-1:0] <= A[DATA_W-1:0] * B[DATA_W-1:0];
    else if(!busy & busy_dly)
        lcm_out_tmp[DATA_W*2-1:0] <= lcm_out_tmp[DATA_W*2-1:0] / mcd_out[DATA_W-1:0];
end

always @(posedge clk or negedge rst_n)begin
    if(!rst_n)
        vld_out <= 1'b0;
    else if(!busy & busy_dly)
        vld_out <= 1'b1;
    else
        vld_out <= 1'b0;
end

endmodule

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

---

  仿真结果如下：

---