如何解决这个数学问题？求帮助！

amabag

版上高手们，大家好，LZ有一个数学问题，没想到好的实现方法，困扰很久，特发帖求助。
劳烦各高手们花费几分钟看看，也帮我想想更好的办法，十分感谢！

reg [13:0] m;
reg [3:0] n,k;

m和n均从上一步计算中求得，n<9。
求解k，使得k是满足 15*（2^k）< m 的最大整数，且k<n。

要求用verilog或VHDL实现且代码可综合。

LZ想了一个最笨的办法，但是耗费时钟周期太长，办法如下：

1. 求解m的比特深度bd，就是非0的比特位宽（如m是14'b00_0110_0011_1110，求得比特位宽为11）。这一步耗费4个时钟周期。
2. 将m非0最高4位与4'b1111比较，如等于4'b1111，k取bd-4，如小于，k取bd-5（如m是14'b00_0110_0011_1110，高4位为4'b1100，比4'b1111小，故k取11-5=6）。这一步耗费5个时钟周期。

版上高手们，LZ这个最笨的办法耗费周期太长，严重影响计算速度。大家能有更好的办法吗？
期盼回复，感激不尽！

layueliuhuo

用ROM表怎么样 m,n作为地址，K输出。地址线总共18位，这样的话ROM表挺大的，如果用2个9位的并行处理不知道能实现不，感觉应该可以。比如m[8:0]为一个ROM的地址，{n[3:0],m[13:9]}为另一个ROM地址，两者的输出经过一个逻辑组合或判断得到最终结果。2个ROM具体还得想想

patrick007

*2^k等于左移。
最多11次比较。
00000000001111 <? m
00000000011110 <? m
00000000111100 <? m
...
11110000000000 <? m
剩下的就是比较或者排序算法了。

可以用分治法，相当于看m在这11个数组成的11个区间的哪个部分。
先比较m是不是大于中间的点，比如
000000111100000 <? m
对结果判断后继续2分。
大概可以把比较器的个数降到4到5个。

对这4到5次比较，可以用串行的方式实现，也可以用并行的方式实现。

wgej1987

不怕资源浪费的话，k就16种情况。。。

jxk304

1. 计算出m中第一个1的位置， 比如第M位: 0...01x...x
2. 然后有四种可能:
        1) 0...010xxx...x : k = min((M-1), n)
        2) 0...011xxx...x : k = min((M-2), n)
        3) 0...0111xx...x : k = min((M-3), n)
        4) 0...01111x...x : k = min(M         , n)
如果timing够就1拍，如果不够就2拍

jxk304

第4个case好像有点问题，因为要求15*（2^k）< m, 没有等于
那么m=0...01111x...x还有两种情况：
1）x...x 不全为0， 那么k = min(M, n)
2）x...x 全部为0， 那么k = min((M-1), n)

jxk304

晕，有四种情况又写错了:
         1) 0...010xxx...x
         2) 0...0110xx...x
         3) 0...01110x...x
         4) 0...01111x...x

suifeng_lll

求指导，学习了

amabag

回复 5# jxk304
第一步求解第一个1的位置，也就是我说的求解该数的比特深度。我想的解决办法是用LZC(Leading zero counter)算法，求出来最少都要4个周期了。如果想很好的满足时序，个人觉得一个周期求不出来。

amabag

回复 3# patrick007

谢谢您的回复，感激不尽！