郑州网站建设喝彩科技,濮阳团购网站建设,做网站工作的怎么填职务,住房与城乡建设部网站打不开国庆假期不小心扭伤了脚踝#xff0c;在家没事看到一篇文章挺有意思#xff0c;于是写出来分享给大家。
这是一道数字电路面试题#xff0c;也是很多面试官很喜欢考察面试者的一道题目#xff0c;题干很简单#xff1a;给定一个4bit的信号A#xff0c;设计逻辑来判断A是…国庆假期不小心扭伤了脚踝在家没事看到一篇文章挺有意思于是写出来分享给大家。
这是一道数字电路面试题也是很多面试官很喜欢考察面试者的一道题目题干很简单给定一个4bit的信号A设计逻辑来判断A是不是独热码设输出为Y如果A是独热码则输出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]);
【卡诺图中的1/0是怎么来的其实是根据真值表来的为1的项表示真值表可能存在的值以1000为例这一项就是这个one-hot可能存在的一个值因此在卡诺图中该项为1】 这个时候面试官可能会问你需要多少个逻辑门关于上面的表达式假设我们有四输入的与门和四输入的或门而且假设输入可以取反那么我们就需要4个与门1个或门如下图所示 回答到这里面试官可以认为你在数字电路的课没有完全睡觉至少最基本的只是你是掌握的能够回答出这个答案不一定会给你offer但是回答不出来那肯定是对不起谢谢了。
那么接下来面试官会进一步问如果输入变成了16bit甚至32bit或者更多呢你要怎么设计电路如果用verilog来表示你的电路呢
当然你可以继续使用卡诺图和真值表直接写表达式16个最小项再把他们或起来可是你知道这不是面试官想要的答案因为面试官想要你设计的是一个参数化的表达参数化的设计是数字逻辑设计中很重要的一个点它体现了你的设计是不是可以复用而且能够匹配各种应用需求以这个为例面试官想要你设计的其实是下面这个function。
parameter WIDTH 16;
function is_one_hotinput[WIDTH-1:0] signal
// code your rtl
endfunction 那么让我们想一想该如何解决这个问题其实有个很简单的思路就是从独热码的定义出发只有一位是1其余位都是0那么不管我们输入信号有多少位有一个性质是不变的--把这些位加起来最后的结果肯定是1那么我们就可以利用一个for循环把每一位相加最后把最终的和1比较一下如果是1那就是独热码如果不是1那就是其他的数非常的直观。
当然如果你告诉面试官这个思路面试官会很乐于让你写以下RTL codecode不长只要你能写出来没有语法错误那你在面试官心里又加了一分下面是一个上述思路的RTL参考code。
function automatic logic is_one_hot(input [WIDTH-1:0] signal)
parameter SUM_WIDTH $clog2(WIDTH)1;
logic [SUM_WIDTH-1:0] sum;
sum d0;
for (int i 0; i WIDTH; i)sum sum sig[i];is_one_hot (sum 1);
endfunction
如果你能写出上面的代码特别是能注意到automatic $clog2等说明你对systemverilog掌握的不错是写过几行代码的人如果你是一个应届生能够写出这样的code并且能够回答出面试官针对这几行code的问题面试官已经对你很感兴趣了这里面有几个小点需要大家注意SUM_WIDTH要用$clog2之后再加1为什么要这样大家自己思考一下。
那么面试官下来就会问你这段code综合出来的电路是什么样子的呢这里面试官想考察你对for loop在RTL中实际理解对于许多RTL的初学者通常搞不清楚for loop的作用错误的把程序设计中的for循环的想法滥用在RTL设计中这里我们一直在强调RTL的每一行代码都是在面熟电路大家一定要做到心中有电路手下才有code。
上面的电路以WIDTH4为例综合处的电路优化前其实是 很明显这样的电路可以达到设计的目的但是并不是最优的大家可以计算以下每个2bit full adder需要多少门comarator需要多少门再和之前利用卡诺图方法得出的最简电路比较一下。
那么有什么办法可以优化呢当然如果你继续对上面的思路进行优化比如第一级第二级其实不需要一个2bit的adder而是可以将a[0]a[1]送到一个half adder里面这样就可以替换掉前面两个2bit adder还有half adder本质其实就是一个XOR gate等等这些都是面试官很乐意和你探讨的你探讨的越细在面试官心里的加分就越多其实在面试过程中你是不是给出最优解并不关键重要的是给面试官展现出来你的思考过程展现出你利用现在有的只是去一点点解决未知问题的能力一般来说如果这道题目你经过这么一个思考过程包括写代码画电路和面试官讨论你在这个问题上的表现已经在面试官心里有谱了。
那么这个问题再上一个层次要怎么回答呢其实思路来自一个稍微冷门但其实又非常常用的知识点对一个binary number进行奇偶校验。
举例来说对于一个4位的二进制数我们对这4位奇偶校验利用XOR门依次进行每一位运算最后的结果如果4位binary有奇数个1那么4位XOR之后的结果就是1如果有偶数个1那么结果就是0看到了吗我们要找的独热码其实就是奇数个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
那么我们就可以继续观察如果我们将A按位取反然后再和P按位OR起来会得到什么A既然是独热码那么除了为1的那一位假设是第i位取反之后都会变成1只有第i位会是0而P的第i位是1那么最后按位OR的结果是什么——全部每一位都是1。
那么如果A不是独热码而是有两个1或者更多1假设第i位和第k位是1k是i之后第一个1我们进行上面的操作会得到什么P[k]会得到0A反和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_one_hot(input [WIDTH-1:0] signal)logic [WIDTH-1:0] parity;parity[0] signal[0];for (int i1; i WIDTH ; i)parity[i] signal[i] ^ parity[i-1];is_one_hot parity[i-1] ((parity | ~sig));
endfunction
至此这个问题就讲的差不多了说实话能够回答出最后一种解法的人寥寥无几作为一道面试题这道题的区分度其实并不怎么样面试官更看重面试者是否能够顺利的利用前面基本思路来给出一个可以work的解法。
转载面试题分析--独热码检测
