反復ユニットベースのリカバリ残高開方器

4497 ワード

反復ユニットベースのリカバリ残高開方器
きほんアルゴリズム
この開方器のアルゴリズムは「手計算」(開方にこの手計算の方法があることを知らなかった)アルゴリズムと似ており、反復解を用いて、文字は以下のように記述されている.
  • は、0を剰余の初値a、0を結果初値b
  • とする.
  • 被開方数の上位2桁の{I(2m + 1),I(2m)}を取り出し、01と比較する.上位2桁が大きいと、{I(2m + 1),I(2m)} - 01が出力剰余(a(m))となり、出力結果1(b(m))、そうでないと{I(2m + 1),I(2m)}が出力剰余(a(m))となり、出力結果0(b(m))
  • となる.
  • 被開方数の3位から4位の{I(2m - 1),I(2m - 2)}を取り出し、{a(m),I(2m - 1),I(2m - 2)}{b(m),2'b01}の大きさを比較し、前項が大きければ出力残数a(m - 1)は前項減後項であり、出力結果b(m - 1){b(m),1}である.そうでない場合、出力残数は前項(直接出力)である、出力結果b(m - 1){b(m),0}
  • である.
  • ...
  • 被開方数の算出が終了するまで
  • .
    反復ユニット
    アルゴリズム#アルゴリズム#
    反復ユニットのアルゴリズムは比較的簡単で、以下のように説明されています.
  • 入力剰余と現在の開方数の2ビット{b,I(i),I(i - 1)}を組み合わせ、組み合わせ入力結果と01は{a,2'b01}
  • である.
  • はサイズを比較し、組合せ残数が大きいと出力残数が組合せ残数から組合せ結果を減算し、出力結果{a,1}である.そうでない場合の剰余は組合せ剰余を出力し、結果は{a,0}
  • を出力する.
    RTLコード
    module square_cell #(
        parameter WIDTH = 4,
        parameter STEP = 0
    )(
        input clk,    // Clock
        input rst_n,  // Asynchronous reset active low
    
        input [2 * WIDTH - 1:0]radicand,
        input [WIDTH - 1:0]last_dout,
        input [2 * WIDTH - 1:0]remainder_din,
    
        output reg [WIDTH - 1:0]this_dout,
        output reg [2 * WIDTH - 1:0]remainder_dout
    );
    
    wire [2 * WIDTH - 1:0]target_data = {remainder_din[2 * WIDTH - 3:0],radicand[2 * STEP +:2]};
    wire [2 * WIDTH - 1:0]try_data = {last_dout,2'b01};
    
    always @(posedge clk or negedge rst_n) begin
        if(~rst_n) begin
            {this_dout,remainder_dout} <= 'b0;
        end else begin
            if(target_data >= try_data) begin
                this_dout <= {last_dout[WIDTH - 2:0],1'b1};
                remainder_dout <= target_data - try_data;
            end else begin
                this_dout <= {last_dout[WIDTH - 2:0],1'b0};
                remainder_dout <= target_data;
            end
        end
    end
    endmodule
    

    最上位レベルとTestbench
    最上位ユニット
    module square_extractor #(
        parameter WIDTH = 4
    )(
        input clk,    // Clock
        input rst_n,  // Asynchronous reset active low
    
        input [2 * WIDTH - 1:0]radicand,
    
        output [WIDTH - 1:0]dout,
        output [2 * WIDTH - 1:0]remainder
    );
    
    genvar i;
    generate
        for (i = WIDTH - 1; i >= 0; i = i - 1) begin:square
            wire [2 * WIDTH - 1:0]remainder_dout,remainder_din;
            wire [WIDTH - 1:0]this_dout,last_dout;
            if(i == WIDTH - 1) begin
                assign remainder_din = 'b0;
                assign last_dout = 'b0;
            end else begin
                assign remainder_din = square[i + 1].remainder_dout;
                assign last_dout = square[i + 1].this_dout;
            end
            square_cell #(
                .WIDTH(WIDTH),
                .STEP(i)
            ) u_square_cell (
                .clk(clk),    // Clock
                .rst_n(rst_n),  // Asynchronous reset active low
    
                .radicand(radicand),
                .last_dout(last_dout),
                .remainder_din(remainder_din),
    
                .this_dout(this_dout),
                .remainder_dout(remainder_dout)
            );
        end
    endgenerate
    
    assign dout = square[0].this_dout;
    assign remainder = square[0].remainder_dout;
    
    endmodule
    

    TestBench
    Testbenchランダムな入力を入力した後、完了を待って、完了後に結果と残数を取って正しい入力を回復できるかどうかを見ます
    module tb_square (
    );
    
    parameter WIDTH = 4;
    
    logic clk;    // Clock
    logic rst_n;  // Asynchronous reset active low
    
    logic [2 * WIDTH - 1:0]radicand;
    
    logic [WIDTH - 1:0]dout;
    logic [2 * WIDTH - 1:0]remainder;
    
    square_extractor #(
        .WIDTH(WIDTH)
    ) dut (
        .clk(clk),    // Clock
        .rst_n(rst_n),  // Asynchronous reset active low
    
        .radicand(radicand),
    
        .dout(dout),
        .remainder(remainder)
    );
    
    initial begin
        clk = 0;
        forever begin
            #50 clk = ~clk;
        end
    end
    
    initial begin
        rst_n = 1'b1;
        #5 rst_n = 1'b0;
        #10 rst_n = 1'b1;
    end
    
    logic [2 * WIDTH - 1:0]act;
    logic [2 * WIDTH - 1:0]dout_ex;
    initial begin
        radicand = 'b0;
        forever begin
            @(negedge clk);
            radicand = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH)));
            repeat(4 * WIDTH) begin
                @(negedge clk);
            end
            dout_ex = '{dout};
            act = dout_ex * dout_ex + remainder;
            if(act != radicand) begin
                $stop;
            end
        end
    end
    
    endmodule