为了账号安全,请及时绑定邮箱和手机立即绑定

如何仅在一个时钟周期内获得32位输入的平方根?

/ 猿问

如何仅在一个时钟周期内获得32位输入的平方根?

我想在Verilog中设计一个可综合的模块,在计算32位给定输入的平方根时仅需一个周期。



查看完整描述

3 回答

?
largeQ

最近发现即使测试确定一切正常,结果仍然不正确,因此我进行了更深入的研究,发现我的方程式中有一个愚蠢的错误,并且由于与pgm环境的名称冲突,测试得到了误报,因此我之前忽略了它。现在,它可以在所有情况下正常工作。


我能想到的最好的事情(近似值或大的LUT除外)是没有乘法的二进制搜索,这里是C ++代码:


//---------------------------------------------------------------------------

WORD u32_sqrt(DWORD xx) // 16 T

    {

    DWORD x,m,a0,a1,i;

    const DWORD lut[16]=

        {

        //     m*m

        0x40000000,

        0x10000000,

        0x04000000,

        0x01000000,

        0x00400000,

        0x00100000,

        0x00040000,

        0x00010000,

        0x00004000,

        0x00001000,

        0x00000400,

        0x00000100,

        0x00000040,

        0x00000010,

        0x00000004,

        0x00000001,

        };

    for (x=0,a0=0,m=0x8000,i=0;m;m>>=1,i++)

        {

        a1=a0+lut[i]+(x<<(16-i));

        if (a1<=xx) { a0=a1; x|=m; }

        }

    return x;

    }

//---------------------------------------------------------------------------

标准的二进制搜索sqrt(xx)是将的位x从MSB设置为LSB,以使结果为x*x <= xx。幸运的是,我们可以通过简单地将事物重写为递增乘数来避免乘法...在每次迭代中,x*x可以像这样使用较旧的结果:


x1 = x0+m

x1*x1 = (x0+m)*(x0+m) = (x0*x0) + (2*m*x0) + (m*m)

其中,x0是x上次迭代的x1值,是实际值。的m是重量实际经处理的位的。的(2*m)和(m*m)是恒定的,并且可以被用作LUT和位移所以无需乘法。仅需要添加。可悲的是,迭代受限于顺序计算,禁止并行化,因此结果16T充其量是最好的。


在代码中a0代表最后x*x,a1代表实际的迭代x*x


如您所见sqrt,16 x (BitShiftLeft,BitShiftRight,OR,Plus,Compare)在可以对位移位和LUT进行硬连线的情况下完成了操作。


如果您为此提供了超快速门,您可以将输入时钟乘以该时钟16并将其用作SQRT模块的内部时序。类似于过去在旧的Intel CPU / MCU中使用MC时钟作为源CPU时钟的分频的情况...这样可以获得计时(或计时的倍数取决于乘法比)。1T


查看完整回答
反对 回复 2019-12-06
?
慕容708150

有转换为对数,减半并转换回去。

有关如何实现“组合” 日志和反日志的想法,请参阅Michael Dunn的EDN文章,其中显示了优先级编码器,桶形移位器和查找表,以及在System Verilog中用于下载的三种日志变体。

(优先级编码器,桶形移位器和查找表对于“单步Babylonian / Heron / Newton / -Raphson看起来很有希望。但是,它可能仍需要128K x 9位查找表。)


尽管没有提供“ verilog”功能,但

Tole Sutikno:“在FPGA硬件中实现的优化平方根算法”展示了一种修改后的(二进制)逐位算法的组合实现。


查看完整回答
反对 回复 2019-12-06
?
胡说叔叔

我的代码在这里


    module sqrt(

input[31:0]a,

output[15:0]out

    );

reg [31:0]temp;

reg[14:0]x;


always@(a)

begin

if(a<257)x=4;

if(a>256 && a<65537)x=80;

if(a>65536 && a<16777217)x=1000;

if(a>16777216 && a<=4294967295)x=20000;

temp=(x+(a/x))/2;

temp=(temp+(a/temp))/2;

temp=(temp+(a/temp))/2;

temp=(temp+(a/temp))/2;

temp=(temp+(a/temp))/2;

temp=(temp+(a/temp))/2;

temp=(temp+(a/temp))/2;

end


assign out=temp;

endmodule

分享编辑


查看完整回答
反对 回复 2019-12-06

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信