Verilog | 公约数与公倍数

最小公倍数可以通过两个数的乘积除以两个数的最小公约数得到。乘法是容易计算的，所以问题变成如何求解最大公约数。可以采用辗转相减法求解，例如 ：两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7。

Verilog代码：

`timescale 1ns/1ns
 
module lcm#(
parameter DATA_W = 8)
(
input [DATA_W-1:0] A,
input [DATA_W-1:0] B,
input          vld_in,
input           rst_n,
input          clk,
output  wire    [DATA_W*2-1:0]     lcm_out,
output  wire   [DATA_W-1:0]    mcd_out,
output  reg                 vld_out
);
reg [DATA_W*2-1:0]  mcd,a_buf,b_buf;
reg [DATA_W*2-1:0] mul_buf;
reg                 mcd_vld;
reg [1:0]           cur_st,nxt_st;
parameter IDLE= 2'b00,S0 = 2'b01, S1 = 2'b10, S2 = 2'b11;
//两段式状态机
always @(posedge clk or negedge rst_n)
    if (!rst_n)
        cur_st <= IDLE;
    else
        cur_st <= nxt_st;
always @(posedge clk or negedge rst_n)
    if (!rst_n) begin
        nxt_st <= IDLE;
        mcd   <= 0;
        mcd_vld <= 0;
        a_buf <= 0;
        b_buf <= 0;
        mul_buf <= 0;
        vld_out <= 1'b0;
    end
    else begin
        case (cur_st)
        IDLE:if(vld_in) begin 
                a_buf <= A;
                b_buf <= B;
                nxt_st <= S0;
                mul_buf <= A*B;
                mcd_vld <= 0;
                vld_out <= 1'b0;
                end
                else begin
                nxt_st <= IDLE;
                mcd_vld <= 0;
                vld_out <= 1'b0;
                end
        S0:if(a_buf!=b_buf)begin
                if(a_buf>b_buf)begin
                    a_buf<=a_buf-b_buf;
                    b_buf<=b_buf;
                end
                else begin 
                    b_buf <= b_buf - a_buf;
                    a_buf <= a_buf;
                    vld_out <= 1'b0;
                end
                nxt_st <= S0;
                end
                else begin
                    nxt_st <=S1;
                    vld_out <= 1'b0;
                    end
        S1:begin   
            mcd <= b_buf;
            mcd_vld <= 1'b1;
            nxt_st  <= IDLE;
            vld_out <= 1'b1;
            end
        default:begin  
            nxt_st<=IDLE;
            vld_out <= 1'b0;
            end
        endcase
    end
     
assign mcd_out = mcd;
assign lcm_out = mul_buf/mcd;
endmodule

`timescale 1ns/1ns
 
module lcm#(
parameter DATA_W = 8)
(
input [DATA_W-1:0] A,
input [DATA_W-1:0] B,
input           vld_in,
input           rst_n,
input           clk,
output  wire    [DATA_W*2-1:0]  lcm_out,
output  wire    [DATA_W-1:0]    mcd_out,
output                   vld_out
);
     
    reg [DATA_W-1:0] a_r;
    reg [DATA_W-1:0] b_r;
    wire [DATA_W-1:0] a_w;
    wire [DATA_W-1:0] b_w;
    wire [DATA_W-1:0] res_w;
    reg flag_r;
    reg [DATA_W*2-1:0] lcm_out_r;
     
    assign vld_out = flag_r && (a_r == b_r);
    assign res_w = a_r - b_r;
    assign {a_w, b_w} = res_w > b_r ? {res_w, b_r} : {b_r, res_w};
    assign mcd_out = vld_out ? a_r : 'd0;
    assign lcm_out = lcm_out_r/ mcd_out;
     
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            a_r <= 'd0;
            b_r <= 'd0;
            flag_r <= 'd0;
        end
        else if (vld_in) begin
            {a_r, b_r} <= A > B ? {A, B} : {B, A};
            lcm_out_r <= A * B;
            flag_r <= 'd1;
        end
        else if (vld_out) begin
            flag_r <= 'd0;
        end
        else if (flag_r) begin
            a_r <= a_w;
            b_r <= b_w;
        end
    end
endmodule