恢复余数除法器

恢复余数除法器

算法描述

恢复余数除法器是一种常用的除法器,过程与手算除法的方法很类似,过程为

  1. 将除数向左位移直到比被除数大
  2. 执行被除数减除数操作,得余数,并将商向左移位1位,空位补1
  3. 若余数大于0,除数向右移位1位。如余数小于0,余数加当前除数,商最后一位置0,除数向右移位1位
  4. 重复到2,只到除数比最初的除数小

RTL代码

RTL代码就是使用了大量的if语句完成了以上的算法描述,其中

  • 为了使移位后的除数确保大于被除数,直接将除数放到一个位宽WIDTH*3的寄存器的前WIDTH位
  • divisor_move >= '{divisor_lock}用于当移位除数小于原除数时停止
  • (divisor_move > '{remainder_r}) && (dout == 'b0)用于当出现第一个1时才开始保存结果
module restore_divider #(
    parameter WIDTH = 4
)(
    input clk,    // Clock
    input rst_n,  // Asynchronous reset active low

    input [WIDTH * 2 - 1:0]dividend,
    input [WIDTH - 1:0]divisor,

    input din_valid,

    output reg [2 * WIDTH - 1:0]dout,
    output [WIDTH - 1:0]remainder
);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH - 1:0]divisor_move;
reg [WIDTH - 1:0]divisor_lock;
always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        //初始化
        {remainder_r,divisor_lock,divisor_move,dout} <= 'b0;
    end else begin
        if(din_valid == 1'b1) begin 
            //锁存输入,3倍WIDTH的宽度用于保证移位后的除数大于被除数
            remainder_r[WIDTH * 2 - 1:0] <= dividend;
            remainder_r[2 * WIDTH] <= 'b0;
            divisor_move[3 * WIDTH - 1:2 * WIDTH] <= divisor;
            divisor_move[2 * WIDTH - 1:0] <= 'b0;
            divisor_lock <= divisor;
            dout <= 'b0;
        end else if((divisor_move > '{remainder_r}) && (dout == 'b0)) begin
            //开始条件
             remainder_r <= remainder_r;
            dout <= 'b0;
            divisor_move <= divisor_move >> 1;
            divisor_lock <= divisor_lock;
        end else if(divisor_move >= '{divisor_lock}) begin
            if(remainder_r[2 * WIDTH] == 1'b0) begin //执行减法
                remainder_r <= remainder_r - divisor_move;
                dout <= {dout[2 * WIDTH - 2:0],1'b1};
                // divisor_move <= divisor_move >> 1;
                divisor_lock <= divisor_lock;
                if(remainder_r >= divisor_move) begin
                    divisor_move <= divisor_move >> 1;
                end else begin
                    divisor_move <= divisor_move;
                end
            end else begin  //恢复余数
                remainder_r <= remainder_r + divisor_move;
                dout <= {dout[2 * WIDTH - 1:1],1'b0};
                divisor_move <= divisor_move >> 1;
                divisor_lock <= divisor_lock;
            end
        end else begin
            remainder_r <= remainder_r;
            divisor_lock <= divisor_lock;
            divisor_move <= divisor_move;
            dout <= dout;
        end
    end
end

assign remainder = remainder_r[WIDTH - 1:0];

endmodule

测试平台

测试平台复用了shiftsub除法器的平台,增加了“遇错停止”的功能

module tb_divider (
);

parameter WIDTH = 4;

logic clk;    // Clock
logic rst_n;  // Asynchronous reset active low
logic [2 * WIDTH - 1:0]dividend;
logic [WIDTH - 1:0]divisor;

logic din_valid;

logic [2 * WIDTH - 1:0]dout;
logic [WIDTH - 1:0]remainder;

restore_divider #(
    .WIDTH(WIDTH)
) dut (
    .clk(clk),    // Clock
    .rst_n(rst_n),  // Asynchronous reset active low

    .dividend(dividend),
    .divisor(divisor),

    .din_valid(din_valid),

    .dout(dout),
    .remainder(remainder)
);

initial begin
    clk = 'b0;
    forever begin
        #50 clk = ~clk;
    end
end

initial begin
    rst_n = 1'b1;
    # 5 rst_n = 'b0;
    #10 rst_n = 1'b1;
end

logic [2 * WIDTH - 1:0]dout_exp;
logic [WIDTH - 1:0]remainder_exp;
initial begin
    {dividend,divisor,din_valid} = 'b0;
    forever begin
        @(negedge clk);
        dividend = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH)));
        divisor = (WIDTH)'($urandom_range(1,2 ** WIDTH - 1));
        din_valid = 1'b1;

        remainder_exp = dividend % divisor;
        dout_exp = (dividend - remainder_exp) / divisor;

        repeat(5 * WIDTH) begin
            @(negedge clk);
            din_valid = 'b0;
        end
        if((remainder == remainder_exp) && (dout_exp == dout)) begin
            $display("successfully");
        end else begin
            $display("failed");
            $stop;
        end
    end
end

endmodule
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,561评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,218评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,162评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,470评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,550评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,806评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,951评论 3 407
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,712评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,166评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,510评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,643评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,306评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,930评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,745评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,983评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,351评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,509评论 2 348

推荐阅读更多精彩内容

  • 8086汇编 本笔记是笔者观看小甲鱼老师(鱼C论坛)《零基础入门学习汇编语言》系列视频的笔记,在此感谢他和像他一样...
    Gibbs基阅读 37,139评论 8 114
  • 移位相减除法器 基本算法 与使用移位相加实现加法一样,移位减法可以实现除法,基本算法如下描述 将除数向左移位直到比...
    月见樽阅读 3,496评论 0 0
  • 第一章数和数的运算 一概念 (一)整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候,用来表示...
    meychang阅读 2,592评论 0 5
  • 不恢复余数除法器 基本算法 不恢复余数除法器的基本算法来自于恢复余数除法器,区别在于当余数变负时不停下恢复余数而是...
    月见樽阅读 4,368评论 0 0
  • 不恢复余数除法器 基本算法 不恢复余数除法器的基本算法来自于恢复余数除法器,区别在于当余数变负时不停下恢复余数而是...
    月见樽阅读 773评论 0 0