onehot编码检测

　　‘’16bits位宽寄存器，用五（六也行）级逻辑判断其中有15个0和1个1‘’，这么道题目，面试无数，几乎没有人能答出来，连给我衍生‘’14个0和2个1‘’的机会都没有。

　　今天的问题来源于知乎，某大牛说的面试题，据说很少有人给出正确答案。正确答案究竟是什么我也不清楚，我的目标是实现一个FPGA的版本，特记录于此。

　　说明一下问题，一个16bits的数输入，检查其中1的个数，如果为独热码，即16位中只有1位为1，则输出为1。题目乍看起来很简单，使用Verilog，可以很轻松实现，实现方法不在赘述。出此面试题的人应该也不是考察HDL编码能力，而是考察面试者对底层逻辑的理解，出题人的本意应该是希望使用逻辑门来实现此功能，但本人是个FPGA工程师，就应该遵循FPGA的设计理念，所以决定使用LUT实现该功能。LUT为xilinx FPGA的原语，LUT是基于SRAM的查找表，使用查找表可以完成逻辑门的功能。如4输入LUT,则是一个4输入，1输出的查找表，查找表的深度为2^4=16，查找表的内容则是逻辑函数的真值表。作为FPGA工程师时刻都要清楚，FPGA的组合逻辑几乎都是用LUT完成的。

　　言归正传，Xilinx 7系列的查找表为6输入，少于6输入可以只覆盖查找表的低位地址，多余6输入需要级联组合，这也就是FPGA中的逻辑层数，级联了几级便是几层逻辑层数。分析题目，16个输入，有一个输入为1则结果为True,多余1个或是全为0则False。这里引入另一个FPGA的设计理念，即并行二字，FPGA中的电路可以并行运行，不同功能模块只要没有先后依赖关系就可以并行处理。个人以为这个是FPGA和GPU的最大差别，GPU为单指令多数据SIMD,FPGA则为MIMD。GPU应该还是串行执行指令的，而FPGA的不能功能模块则为不同指令，这些不同指令可以同时执行。关于GPU与FPGA的差别，仅是个人思路整理，没有深刻研究过GPU。再继续说检测onehot，检测主要分成三部分，第一输入中只有一位为1则输出1，如0x001,0x002,0x004...2^n等,使用2个6输入LUT,1个4输入LUT,2*6+4=16个输入。6输入LUT真值表为64‘h0000_0001_0001_0116,4输入LUT真值表为16'h0116，每个真值表都能够检出仅存一个1的输入，每个LUT此时能得出的结果是，输出true表示仅有一个1存在，输出Flase表示输入可能有1个以上的1或是全为0，此时三个LUT输出求结果无解。所以还需要引入第二功能，检测全为0的输入，仍然是2个6输入LUT,1个4输入LUT，真值表值为64’d1,16'd1，表示只有0x0地址输出true，即全为0输入，同样有3个输出，此结果可以确定输入全为0，补充了第一步的条件。这两个功能为并行执行，为第一级组合逻辑，共6个输出，这6个输出可以作为函数输入求解。第二级功能使用一个6输入LUT，假设为全为0检测的输出是dout0[2:0],仅有独个1的输出是dout1[2:0],求结果result=dout1[0]&dout0[1]&dout0[2] | dout1[1]&dout0[0]&dout0[2] | dout1[2]&dout0[1]&dout0[0]，这个函数正好是个6输入lut。前文已述，4输入lut实际使用6输入lut，所以该项目一共用了7个lut，共两层逻辑。代码改天再贴。

巴特西

onehot编码检测

最新文章

热门文章