基于牛顿迭代法的32位无符号数平方根计算逻辑

创作时间:

作者:

@小白创作中心

基于牛顿迭代法的32位无符号数平方根计算逻辑

引用

CSDN

https://blog.csdn.net/LionelZhao/article/details/145285403

基于牛顿迭代法的32位无符号数平方根计算逻辑

1.设计功能与要求

2.算法原理

本设计采用牛顿迭代法算法，是一种通过迭代近似求解方程的方法。

牛顿迭代公式

设r为方程f(x) = 0的根，设x0为r的初始近似值。过点(x0, f(x0))做函数y = f(x)的切线L1：

y = f(x0) + f'(x0)(x - x0)

L1与x轴交点横坐标为x1 = x0 - f(x0) / f'(x0)，称x1为r的一次近似值。过点(x1, f(x1))做函数y = f(x)的切线L2：

y = f(x1) + f'(x1)(x - x1)

L2与x轴交点横坐标为x2 = x1 - f(x1) / f'(x1)，称x2为r的二次近似值。

反复迭代以上过程能够得到r的近似值序列，其规律为：xn+1 = xn - f(xn) / f'(xn)，xn+1为r的n+1次近似值。

对于开平方根运算而言，设f(x) = x^2 - a，其中a为待开平方的输入数据，由牛顿迭代公式得xn+1 = xn - (xn^2 - a) / (2xn) = 1/2 * (xn + a / xn)，本设计就是反复迭代直到xn+1收敛。收敛的标志为第n+1次迭代所得的数值与第n次迭代相同，即xn+1 = xn

更加详细的举例和说明请参考参考与致谢第一篇博客。

综上所述，我们明确了基于牛顿迭代法的平方根计算逻辑的原理与步骤，下面将进行RTL实现。

3.RTL实现

根据第2小节中的描述和题目要求，本设计采用三段式状态机实现，其状态转移图如下所示，状态机共有三个状态，IDLE空闲状态检测输入有效信号vld_in，若为高电平则进入计算状态CALC，在CALC状态进行迭代计算直到上一个周期和当前周期计算数值相同或相差1拉高结束标志calc_finished进入DONE状态，然后DONE状态下一个时钟周期返回空闲状态IDLE。

3.1 控制通路

标志信号calc_ena控制计算的开始与否，当进入计算状态CALC时拉高。calc_finished控制状态转移到DONE状态标志计算结束，当上一周期的结果y_tmp与本周期计算结果y相等或相差1时拉高。calc_ena由三段式状态机控制。

// parameter define
localparam IDLE = 3'b001;
localparam CALC = 3'b010;
localparam DONE = 3'b100;
// signal define
reg [2:0] cstate, nstate;
reg calc_ena;
wire calc_finished;//end calculate
// FSM1
always @(posedge clk or negedge rst_n) begin
    if(!rst_n)begin
        cstate <= IDLE;
    end
    else begin
        cstate <= nstate;
    end
end
// FSM2
always @(*) begin
    case(cstate)
        IDLE: begin
            if(vld_in) nstate = CALC;
            else nstate = IDLE;
        end
        CALC: begin
            if(calc_finished) nstate = DONE;
            else nstate = CALC;
        end
        DONE: begin
            nstate = IDLE;
        end
        default: nstate = IDLE;
    endcase
end
// FSM3
always @(posedge clk or negedge rst_n) begin
    if(!rst_n)begin
        vld_out <= 1'b0;
        calc_ena <= 1'b0;
    end
    else begin
        case (nstate)
            IDLE: begin
                vld_out <= 1'b0;
                calc_ena <= 1'b0;
            end
            CALC: begin
                vld_out <= 1'b0;
                calc_ena <= 1'b1;
            end
            DONE: begin
                vld_out <= 1'b1;
                calc_ena <= 1'b0;
            end
            default: begin
                vld_out <= 1'b0;
                calc_ena <= 1'b0;
            end
        endcase
    end
end
assign calc_finished = (y_tmp==y) || ((y_tmp+1'b1)==y);

3.2 数据通路

使用32位寄存器x_r在输入有效信号vld_in为高电平的时候寄存输入信号x并进入CALC状态进行计算，防止后续计算过程中输入x发生变化导致结果错误。

reg [31:0] x_r;
// get input data x
always @(posedge clk or negedge rst_n) begin
    if(!rst_n)begin
        x_r <= 32'd0;
    end
    else if(vld_in)begin
        x_r <= x;
    end
    else begin
        x_r <= x_r;
    end
end

使用div_tmp计算a / xn，其中a为待开方的输入数据。使用addey_tmp计算xn + a / xn，使用y_tmp通过右移1位替代×1/2的计算。

wire [15:0] div_tmp;//temp divide data
wire [16:0] addey_tmp;//output from adder
wire [15:0] y_tmp;//temp y

assign div_tmp = x_r/y;
assign addey_tmp = {1'b0, div_tmp} + {1'b0, y};
assign y_tmp = addey_tmp[16:1];
always@(posedge clk,negedge rst_n) begin
    if(!rst_n) begin
        y <= 8'd1;
    end
    else if(calc_ena) begin
        y <= y_tmp;
    end
end

3.3 完整代码

完整代码如下

module SqrtCal(
    input clk,
    input rst_n,
    input vld_in,
    input [31:0] x,
    output reg vld_out,
    output reg [15:0] y
    );
    // parameter define
    localparam IDLE = 3'b001;
    localparam CALC = 3'b010;
    localparam DONE = 3'b100;
    // signal define
    reg [31:0] x_r;
    reg [2:0] cstate, nstate;
    reg calc_ena;
    wire calc_finished;//end calculate
    wire [15:0] div_tmp;//temp divide data
    wire [16:0] addey_tmp;//output from adder
    wire [15:0] y_tmp;//temp y
    // FSM1
    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            cstate <= IDLE;
        end
        else begin
            cstate <= nstate;
        end
    end
    // FSM2
    always @(*) begin
        case(cstate)
            IDLE: begin
                if(vld_in) nstate = CALC;
                else nstate = IDLE;
            end
            CALC: begin
                if(calc_finished) nstate = DONE;
                else nstate = CALC;
            end
            DONE: begin
                nstate = IDLE;
            end
            default: nstate = IDLE;
        endcase
    end
    // FSM3
    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            vld_out <= 1'b0;
            calc_ena <= 1'b0;
        end
        else begin
            case (nstate)
                IDLE: begin
                    vld_out <= 1'b0;
                    calc_ena <= 1'b0;
                end
                CALC: begin
                    vld_out <= 1'b0;
                    calc_ena <= 1'b1;
                end
                DONE: begin
                    vld_out <= 1'b1;
                    calc_ena <= 1'b0;
                end
                default: begin
                    vld_out <= 1'b0;
                    calc_ena <= 1'b0;
                end
            endcase
        end
    end
    // get input data x
    always @(posedge clk or negedge rst_n) begin
        if(!rst_n)begin
            x_r <= 32'd0;
        end
        else if(vld_in)begin
            x_r <= x;
        end
        else begin
            x_r <= x_r;
        end
    end
    assign calc_finished = (y_tmp==y) || ((y_tmp+1'b1)==y);
    assign div_tmp = x_r/y;
    assign addey_tmp = {1'b0, div_tmp} + {1'b0, y};
    assign y_tmp = addey_tmp[16:1];
    always@(posedge clk,negedge rst_n) begin
        if(!rst_n) begin
            y <= 8'd1;
        end
        else if(calc_ena) begin
            y <= y_tmp;
        end
    end
endmodule

Vivado RTL analysis结果如下图所示，符合设计预期。