如何用Verilog实现最小公倍数和最大公约数的计算

题目

描述

设计一个时序电路，输入2个无符号数，位宽可以通过参数DATA_W确定，输出两个数的最小公倍数和最大公约数。模块的接口信号图如下：

要求使用Verilog HDL语言实现，并编写testbench验证模块的功能。

输入描述

clk：时钟信号

rst_n：复位信号，低电平有效

A：输入信号，位宽可以通过DATA_W指定

B：输入信号，位宽可以通过DATA_W指定

vid_in：输入数据有效的指示信号

输出描述

icm_out：输出最小公倍数

mcd_out：输出最大公约数

vid_out：输出数据有效的指示信号

分析

• 题目要求计算最小公倍数和最大公约数，其中最大公约数可以利用辗转相除法计算得到；
• 而最小公倍数可以先将两数相乘再除最大公约数得到；
• 此外，因为辗转相除法中用了取模和除法的运算，目前高版本的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           

仿真结果