英伟达的面试题，求解

77881919 · 发表于 2018-3-30 22:51:24

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

英伟达的实习面试题，设计一个8bit模3取余电路，要求一个cycle完成。看上去很简单，但是实际一脸懵逼。能想到的就是列真值表求布尔表达式，但是发现布尔表达式毫无规律，不知大家有没有其他设计思路或算法

himingway · 发表于 2018-3-31 10:44:53

剩下的自己看着办吧~

77881919 · 发表于 2018-3-31 11:43:27

回复 2# himingway
6666后面变成4位、3位、2位，但是路径还是很长，中间还需要多路选择器和加法器

hychuchen · 发表于 2018-3-31 17:49:22

(2*(A7+A5+A3+A1)+(A6+A4+A2+A0)) mod3 = ( (A6+A4+A2+A0) - (A7+A5+A3+A1) ) mod3

Emersondjp · 发表于 2018-4-1 20:01:13

本帖最后由 Emersondjp 于 2018-4-2 06:43 编辑

回复 3# 77881919 一下是我个人思路哈~
上面的思路差不多，下面分奇数部分A1,A3,A5,A7；和偶数部分A0,A2,A4,A6两部分分析：奇数部分：
   余1的情况有5种，A1*A3*A5*A7和只有一个为0其他三个为1的四种情况，逻辑之后取或得到even_1（0表示非余1,1表示余1）
   余2的情况有6种，取逻辑或得到even_2
   余0的情况有四种，取逻辑或得到even_0；
偶数部分同样得到odd_0,odd_1,odd_2三个标志位；
然后根据even_0,even_1,even_2,odd_0,odd_1,odd_2得到下一步的结果：
余0 ： even_0*odd_0 + even_1*odd_2 + even_2*odd_1
余1 ： even_0*odd_1 + even_1*odd_0 + even_2*odd_2
余2 ： even_0*odd_2 + even_1*odd_1 + even_2*odd_1
这样得到了三个标志位，再做一个3选1的MUX,选择2'b00, 2'b01, 2'b10输出就可以了。。
也可以直接余2，余1组成结果输出，省去mux.
如果能够使用四输入逻辑门的话，算下来总的逻辑技术应该在8级以内，应该能够满足一个cycle内完成的目标。。
如果需要更快，可以采用动态电路完成里面大扇入逻辑。
我想这个问题目的在于进行一步步划分，从而使计算复杂度降低，看起来很庞大的逻辑可以不断划分为小问题一一解决。