如何实现一个求对数电路逻辑

最近遇到一个对输入以2为底求对数向下取整的逻辑需求。正好可以研究下如何去实现以2为底求对数向上取整及向下取整的实现。

设计思路

所有的数字均以二进制的形式进行存储。在计算机中均是二进制，对于对数的求取具有天然的优势。对于任意一个数字，均可以表示成一系列2的n次幂的和。以6为例：

6=2^2+2^1

在进行以2为底的求对数运算中，当其拆解为2的n次幂的和那么最高次幂的次数决定了结果的整数部分。像上面的6最高次幂为2，故其结果整数部分即为2。而这正和数字以二进制存储时的结构相对应:

图片.png

读到这里，想必你心中已经有了一个大概的思路了！

对于向向下取整，只需找出数据的为1的最高bit的位置即可。
对于向上取整，在找到数据的为1的bit位置之外，还需考虑是否有其他bit存在为1的情况。若存在，则需再加1，否则，即输出。
无论是求对数向上取整还是向下取整，整个逻辑设计关键为找到数据中为1的最高bit的位置。而再进一步拆分，可以分为两步：

将数据转换为独热码，独热码中1出现的位置即为原数据中为1的最高bit的位置。
将读热码中1出现的位置转换成普通的二进制表示形式。

二进制转独热码

对于上面的第一步，想要实现独热码中1出现的位置即为原数据中为1的最高bit的位置，不知小伙伴是否有合适的Idea？千万可别是一堆if else 或者casez……
如果暂且没有思路，不妨换个想法。如何找到一个数据中最低位为 1的位置并转换成独热码。只需要做一次减法和按位与：

oneHotCode=symbol& ~(symbol-1)

原理并不复杂。对于任何一个数据：

图片.png

其减一之后将会变成：

图片.png

取反：

图片.png

做按位与后即可得到对应的独热码：

图片.png

有了找到一个数据中最低位为 1的位置并转换成独热码的方式，那么实现独热码中1出现的位置即为原数据中为1的最高bit的位置也就不难了。

symbolResvered=symbol.reversed  
oneHotCode=symbolResvered& ~(symbolResvered-1)  
oneHotCode.reversed

独热码的二进制表示

而针对独热码转换成为二进制，一开始或许也要思索一番。其实也不难，只要发现了其中的规律，实现起来也就没有那么难了。以8位数为例，其转换为二进制则需要3个比特(0~7)。先看下其规律:

图片.png

其中可以认为:

UInt(2)=bit(4)||bit(5)||bit(6)||bit(7)
UInt(1)=bit(2)||bit(3)||bit(6)||bit(7)
UInt(0)=bit(1)||bit(3)||bit(5)||bit(7)

其中假定OneHot的编码序号为index，则有

UInt(2)=OneHot.filter((index>>2)&0x1==1).xor 
UInt(1)=OneHot.filter((index>>1)&0x1==1).xor 
UInt(0)=OneHot.filter((index>>0)&0x1==1).xor

以此类推，可得到OneHot转UInt的方式为：

UInt(N)=OneHot.filter((index>>N)&0x1==1).xor

最终实现

有了上面的总结，想必你就知道怎么实现了。其实上面的两个小的方法在SpinalHDL lib中均有提供。这里给出完整的实现(不考虑输入为0)：

/**
  * 求2的对数，向上取整
  * @param x ：待求对数的数字
  */
case class Log2Ceil(x: UInt) extends ImplicitArea[UInt] {
  val oneHotSymol = OHMasking.last(x)
  val symbolMasked = (~oneHotSymol) & x
  val oneHotCeil = (symbolMasked === 0) ? (U(0, 1 bits) @@ oneHotSymol) | (oneHotSymol << 1)
  val result = OHToUInt(oneHotCeil)

  override def implicitValue: UInt = result
}
/**
  * 求2的对数，向下取整
  * @param x ：待求对数的数字
  */
case class Log2Floor(x: UInt) extends ImplicitArea[UInt] {
  val oneHotSymol = OHMasking.last(x)
  val result = OHToUInt(oneHotSymol)

  override def implicitValue: UInt = result
}

SpinalHDL这种丰富的组件对于日常的开发工作来讲无疑是十分好用的，深入之后你会发现，自己曾经是多么无聊的一遍遍造轮子～

☆ END ☆

作者：玉骐
原文链接：https://mp.weixin.qq.com/s/qaZW14sAGWsLuh80er62mw
微信公众号：

推荐阅读

更多SpinalHDL技术干货请关注Spinal FPGA专栏。

设计思路

二进制转独热码

独热码的二进制表示

最终实现

推荐阅读

目录