面试题分析--独热码检测

今天老李带大家分析一道数字电路面试题，这道题也是老李面试别人的时候喜欢问的一道问题。欢迎大家一起讨论。

题干很简单：给定一个4bit的信号A，设计逻辑来判断A是不是独热码，设输出为Y，如果A是独热码，则Y输出1，如果不是，则输出0.

首先我们来看什么是独热码(one-hot)。独热码是一种二进制编码方式，它的特点是，用来编码这个数的N位bit中，有且只有一位是1，其余位全部为0。因为只有1位是1，所以叫做one-hot （对应的，还有一种编码方式是只有1位是0，其余位都是1，叫做one-cold)

下面的表格是用独热码来表示0到7这8个数。

其实one-hot编码在电路设计中很常见。举个最常见的例子，给定一个SRAM的地址，要读出SRAM中的一行，SRAM内部就是利用address的某几位来转换为one-hot的select从而选中对应的word line和bit line。还有一些场合，利用one-hot来编码状态机，好处就是一个flop就表示一个状态，用来判断状态机在哪一个状态的时候就只需要看第几个flop为1即可，而不需要像binary编码那样是所有flop在一起参与比较。这样可以省下一点点逻辑的比较电路的延时，代价显而易见，用one-hot编码状态机需要的寄存器比binary编码要多，这就是一个典型的利用面积换性能的trade off。

回到这个问题本身，其实直接回答上这个问题难度不大，相信所有学过数字逻辑的同学都能够立刻想到解决办法--利用真值表和卡诺图。这也是面试官要考察你的第一个层次，对于学校课程的基础知识掌握是不是扎实。

真值表咱们略过，直接上卡诺图

很明显，在这个例子中，卡诺图并不能帮我们简化逻辑（为什么？），最后的表达式其实都可以直接想到

Y = (A[0] & (!A[1]) & (!A[2]) & (!A[3])) 
   |((!A[0]) & A[1] & (!A[2]) & (!A[3]))
   |((!A[0]) & (!A[1]) & A[2] & (!A[3]))
   |((!A[0]) & (!A[1]) & (!A[2]) & A[3]);

这个时候面试官可能会问你，需要多少个逻辑门。关于上面的表达式，假设我们有四输入的与门和四输入的或门，而且假设输入可以取反，那么我们就需要4个与门，1个或门，如下图所示：

回答至此，面试官可以认为你在数字电路的课没有完全睡觉，至少最基本的知识你是掌握的。能够回答出这个答案不一定会给你offer，但是如果回答不上那肯定是对不起谢谢了。

那么接下来老李会怎么问呢？如果输入变成了16bit，甚至32bit或者更多，你要怎么设计电路呢？如何用verilog来表示你的电路呢？

你当然可以回答继续用卡诺图和真值表，直接写表达式，16个最小项，再把它们或起来。可是你知道这不是我想要的答案。因为面试官想要你设计的，是一个参数化的表达，参数化的设计是数字逻辑设计中很重要的一个点，它体现了你的设计是不是可以复用，而且能够匹配各种应用需求。以这个为例，面试官想要你设计的其实是下面这个function

parameter WIDTH = 16;
function is_onehot (input[WIDTH-1:0] sig)
//put  your code here
endfunction

那么让我们想想该如何解决这个问题。其实有个很简单的思路，就是从独热码的定义出发：只有一位是1，其余位都是0。那么不管我输入信号有多少位，有一个性质是不变的 -- 把这些位各自相加，最后的结果肯定得是1。那么我们就可以利用一个for循环，把每一位相加，最后再把最终的结果和1比较一下，如果是1，那就是独热码，如果不是1，那就是其他的数，非常直观吧？

当然，如果你告诉我这个思路，我会很乐于让你写一下RTL code，code不长，只要你能写出来，没有语法错误，那你在面试官里的心里又加了一分。下面是一个上面思路的参考版本

function automatic logic is_onehot(input [WIDTH-1:0] sig);
  localparam SUM_WIDHT = $clog2(WIDTH) + 1;
  logic [SUM_WIDTH-1:0] sum;
  sum = '0;
  for(int i = 0; i < WIDHT; i++)
     sum = sum + sig[i];
  is_onehot = (sum == 1);
endfunction

如果你能写出上面的代码，特别是能够注意用到automatic, $clog2等等，说明你对SystemVerilog掌握得还不错，是写过几行代码的人。如果你是一个应届毕业生，能够写出这样的code，并且能够回答出我针对这几行code的follow up问题，老李对你已经很感兴趣了。这里面有个小点需要大家注意，SUM\_WIDTH要用$clog2之后再加1，为什么需要这样留给大家思考。

那么老李接下来就会问你，这段code综合出来的电路是什么样的呢？这里老李其实想考察你对for loop在RTL中实际理解。对于许多RTL的初学者，通常会搞不清楚for loop的作用，错误地把程序设计中的for循环的想法滥用在RTL设计中，从而很容易写出看起来好像正确，但是实际无法综合出电路的RTL code。老李一再要和大家强调，RTL是硬件描述语言，你写的每一行code都是在描述一个电路，大家一定要做到心中有电路，手下才有code。

上面的电路以WIDTH=4为例，综合出的电路（优化前）其实是

很明显，这样的电路可以达到设计的目的，但是并不是最优的，大家可以计算一下每个2bit full adder需要多少门，comparator需要多少门，再和之前利用卡诺图方法得出的最简电路比较一下。

那么有什么办法可以优化呢？当然如果你继续对上面的思路进行优化，比如第一级，第二级其实不需要一个2bit的adder, 而是可以将a[0]，a[1]送到一个half adder里面，这样就可以替换掉前面两个2bit adder，还有half adder本质其实就是一个XOR gate等等... 这些都是我很乐于和你探讨的，你探讨的越细，在老李心中的加分越多。老李说句掏心窝子的话，你在面试的过程中是不是给出最优解并不关键，重要的是给面试官展现出你思考的过程，展现出你利用你现有的知识去一点一点解决未知问题的能力。一般来说，如果这道题你经过这么一个思考过程，包括写代码画电路图还有和面试官讨论，你在这个问题上的表现已经在面试官心里有谱了。

那么这个问题再上一个层次要怎么回答呢？其实思路来自一个稍微冷门但其实又非常常用的知识点：对一个binary number进行奇偶校验。

举例来说，对于一个4位的二进制数，我们对这4位奇偶校验，利用XOR门依次进行每一位，最后的结果如果是奇数个1那么4位XOR之后结果就是1，如果偶数个1那么结果就是0。看到了吗，我们要找的独热码其实是奇数个1的特殊情况，即只有1位是1。所以更加巧妙的方法就来自于这个按位XOR。

我们再来看几个例子，看能不能找出独热码按位XOR的特点。还是以4位为例，我们定义如下运算，把A相应按位XOR的结果记为P，其中P[0] = A[0]， P[i] = A[i] ^ P[i-1]。

我们可以看到一个什么规律？即对于独热码，我们得到的P会是这样一个数：如果独热码A的第i位为1，那么P的第i-1到第0位都是0，而第i位和更高位都是1。注意，这个规律只对独热码适用，大家可以试验一下其他任何数，只要多于1位是1，那么就不会出现高位连续的都是1，高位必然会出现0。（思考，什么时候P的高位会出现0？）

那么我们就可以继续观察，如果我们将A按位取反，然后再和P按位OR起来会得到什么？A既然是独热码，那么除了为1的那一位（假设是第i位），取反之后都会变成1，只有第i位会是0。而P的第i位是1，那么最后按位OR的结果是什么？全部每一位都是1。

那么如果A不是独热码，而是有两个1或者更多1，假设第i位和第k位是1(k是i之后第一个1），我们进行上面的操作会得到什么？P[k]会得到0。A反和P按位OR之后第k位也是0.

至此，我们距离我们的最终答案只有一步之遥，A反和P按位OR之后的结果我们再对每一位进行按位AND，得到的结果如果是0，那么一定不是独热码！

为什么是一步之遥呢？我们这里漏了一个特殊情况，即A为全0。当A为全0的时候，P也是全0，但是A取反之后是全1，所以A反和P按位OR之后也会得到全1。幸好，特殊情况就只有这一种，我们只需要对A进行一下全0判断就可以了。

至此，我们更加高效的通用解法就出来了

function automatic logic is_onehot(input [WIDTH-1:0] sig);
  logic [WIDTH-1:0] parity;
  parity[0] = sig[0];
  for(int i = 1; i < WIDTH; i++)
     parity[i] = parity[i-1] ^ sig[i];
  is_onehot = parity[i-1] & (&(parity | ~sig));
endfunction

终于至此，这道面试题算是讲差不多了，说实话能够回答出最后一种解法的人寥寥无几，所以作为一道面试题，这道题的区分度其实并不怎么样。老李还是更看重面试者是否能够顺利地利用前面基本思路来给出一个可以work的解法。至于如果哪天遇到一个求职者给出了最后的解法，老李肯定对他是十分佩服的，肯定会给strong hire。当然，老李在这里写这篇文章不是希望大家去背答案，而是去思考这么一道看似简单题的解题思路，还是那句话，你给出的答案其实不那么重要，重要的是你的思考过程。

作者：硅谷老李
来源：https://mp.weixin.qq.com/s/xnK43oIpeshy66Sri58Kqg
作者微信公众号

相关文章推荐

• MUX变身大法
• 聊一聊Lockup Latch

更多IC设计技术干货请关注IC设计技术专栏。