[转论坛的帖子]发个今天的面试题,拿出来和大家探讨

上一篇 / 下一篇 2008-08-11 16:08:16 / 个人分类：IC/EDA

一个黑匣子，输入一位，输出一位，还有clk输入，设计黑匣子里面的电路：
输入的数字序列能被5整除的话，输出1，不能被5整除，输出0，比如输入0101，输出就是1001。
大家把思路说出来就行，不用写代码了。

a simple state machine with five states.
whatever mod by 5, there are five results, 0,1,2,3,4..based on these five results, you can easily draw a state machine diagram.
BTW: assuming it's a infinite width shift register and MSB first...

Looks like most people don't understand the problem. It's not a practical problem, just a conceptual problem!!

A small example:

current input bit       current input sequence       current output bit          current output sequence
1                                                 1                                              0                                                 0
0                                                 10                                              0                                                 00
1                                                 101                                           1                                                 001
0                                                 1010                                        1                                                 0011
1                                                 10101                                     0                                                 00110
1                                                 101011                                     0                                                 001100
1                                                 1010111                                  0                                                 0011000
......                                              ......                                           ............                                        .............

回答上面一些朋友的问题：

1.确实输入的是无穷序列；
2.最后考我这个问题的考官好像确实是在考察我的arithmetic方面的知识，问的问题都是一些和数学还有算法相关的，比如如何用硬件实现递归的算法等等；
3.不能认同状态机不重要的观点。状态机还是在设计中经常用到的，如何最有效地实现状态机是一个挺有挑战的问题。这就好像算法和编程之间的关系一样。

写个答案吧，看看能不能写清楚：
首先一些基本事实：输入一位就是右移一位，如果输入数为0那么就是乘2，如果输入数为1就是乘2加1。
假设原数我们设为M，那么输入为0就是2M,输入1就是2M+1。
任何数字都能表示成 5i+r 的形式 i取正整数，r取0，1，2，3，4。那么M=5i+r
考虑输入数字mod5的情况:如果是0就是2*(5i+r) mod 5=(5i+r) mod 5,如是1就是(2*(5i+r)+1) mod 5 = (5i+ (2r+1))mod 5.
前面2#已经说了，除以5得到的余数可能答案只有{0,1,2,3,4}那么这就是状态机的状态。只有当0状态的时候输出为1，所以下面分析就不说输出是什么了:
首先从0开始，0状态表示现在的输入数字是0，在输入0的时候就是0x2 mod 5=0,那么0状态，输入是0的时候，还是停留0状态; 输入是1就是 (0+1) mod 5=1，跳转状态1；
1状态，输入0, 1*2 mod 5 = 2, 输入1， (1*2+1) mod 5= 3;
2状态....
3状态....
4状态....
状态图完成。