跟李凡老师学FPGA之D04：有限状态机设计（20160426课堂笔记）

0932
        我们从置位开始的第一点，0,1,2,3，3以后又会回到0，1,2,3。
        如果我们给出一个置位的一个相对的时钟点，0点开始来计算，那么在时钟轴上的任意一个取样点，总会有一个数值跟它q对应。
        所以说这个时候的counter，就是引用了时钟轴上的取样点。
        如果这个counter用数学函数来描述，描述一个永远无故障、永远有电的一个counter，那么在这个时间轴上的任意一点的取样，总会有一个值跟它对应。

0933
        如果考虑到这种0123跳变的连续性，高等数学里面我们甚至认为是一个连续函数。
        输入跟一点逼近，输入也跟一点逼近。
        这个时候呢，阿兰图灵就引用了这么一个思想，无限长的时间轴上的连续的取样点，如果t的值，有一个值跟它逼近，任意逼近，总会有任意的一个数，q也会有任意的逼近，它可以是0.1，可以是0.01，可以是0.00001。
0934
        这些呢都有值，这是连续的。
        所以这个呢可以看成是无限长的时间轴上面，连续的取样点，总会有一个值跟它对应。
        所以说这是形成连续函数。
        但是阿兰图灵这个时代考虑到这样一个问题，对于一个实际的数字机器而言，在攻击德国人的密码机Enigma的时候，用机器对抗机器。
        因为Enigma是世界上第一个公开秘钥系统，公开密钥，也就是算法是公开的，每个人可以截获，盟军已经获取了德国人的这台机器，但是它是一个公开秘钥系统，它不希望落到敌人的手里。
        但是一旦这台机器落到了盟军的手里，他也不怕。
        为什么呢？
        它的算法是可以公开的，你可以打开来看，你知道它是怎么算出来的，但是你就是破解不了。
0935
        今天我们知道，我们现代的密码体系都是公开算法系统，算法都是公开的，DES，AES，谁都知道怎么算。
        但是你一旦没有秘钥，你就解不了。
        秘钥要解开它，要用大素数。
        用计算机攻击的话，都需要若干年。
        但是这个DES呢，没有多少年就已经被免费地攻击了。
        现在网上都可以免费地下载DES攻击机。
        AES的128位秘钥现在还没有攻击机。
        但是很快就会有了，这是矛和盾的一个关系。
        所以说在阿兰图灵时代，就引用这么一个想法。

0936
        他用机器攻击的时候，这个时候这个机器在时间轴上是一个离散的点，也就是说是引用时钟的，有节拍关系的。
        对于counter而言，显然是有节拍关系的。
        也就是说我们引入的这个点是踩着时钟的节拍发生的。
        我们可以是连续时间轴上的一个采样点，10ns一拍，我们只要知道采样点落在10ns的哪一拍，我们就知道它的输出是那一个值。
0937
        就是说无限长的连续的时间轴上的取样，可以离散化。
        也是现代应用数学里面的一个分支，离散数学。
        所以说，在这种情况之下呢，阿兰图灵说呢，这个q，输出的q，任意值的q，可以用无限长的离散的时间轴上的点来代入。
        仍然是无限的，但是它是离散的。
        离散化了，这个t是无限，是连续的，这个t’是无限，是离散的。
        离散的，就是10ns、20ns。
        可是阿兰图灵看到另外一件事实，尽管如此，可以用无限长时间轴上的离散点来替代。

0938
        更进一步，我还可以用有限的状态来替代。
        只有0、1、2、3，无论是10ns、20ns，因为从0起点，我们只需要把取样点的顺序号做一个模，求它的余，余几就是几。0、1、2、3，第3拍模4以后，余数是3。
        第4拍余数是0，这是余数是1。
        所以说呢，这个时候可以用有限的状态来描述，无论这个时间轴是多么的长，多么的无限，但是总可以用有限的状态来替代。
        这个时候呢，就是我们在引入无限长的离散时间轴用有限的状态来替代。
0939
        这个时候，无限长的连续的点，无限长的离散的点，是有限的状态。
        是这么来的。
        在这个例子里面，非常清晰，有限个状态，只有0、1、2、3，只有4个状态。
        无论这个时间轴多长，十万年还是一万年，总是0、1、2、3，4个状态。
        所以说你只要把无限长的时间轴，算成有限个状态，总可以得到q这个值，这是没有问题的。
        现在呢，我们就来看有限的状态，这个从无限长的时间轴，连续轴，到有限状态的这个发展的过程。
        当然其中必不可少的就是轴时间的引入，时间引入的离散化，依靠的就是时钟。
        我们用上升沿捕获嘛，就把时钟轴带来了。
        第一，无限长的时钟轴上，时间的取样点带来了；
        第二，离散化了，把时间点离散化了。

0940
        离散点的时间，就是这个t’跟s的关系。
        如何会变成有限个状态呢？
        关于这一点，也有讨论，在阿兰图灵以后，数理逻辑界曾经有反复的争论。
        它具不具有普遍的意义呢？
        就是，你是不是只在阿兰图灵说的那台机器上，具有这种可能，就是用无限长的连续时间轴上的取样点，用有限个状态来替代呢。
        是不是只在极特殊的情况下适用呢？
        这个经过了很多数理学家的推理，这里我就从略了。
        但是现代已经基本上得到非常准确的结论，可以用。
        可以用在什么方面呢？
0941
        可以用在我们所认知的时空领域，时空领域特别大的情况之下，特别小的情况之下，量子力学的情况之下不适用，爱因斯坦的相对论的空间，时空范围不适用。
        其他的范围，就是我们正常处理的时空领域，这个有限的状态是适用的。
        就是大多数，位于我们实际所处理的问题，都可以用有限的状态来描述。
        总可以用，前提是只要能够离散化。
        如果我们做全模拟量，它可能不适用，一定要离散化。
        离散变成数字，变成时钟了以后，那么阿兰图灵的这个理论，从离散层面，连续的时间轴上的取样点，到有限的状态，这种变迁是适用的。
        现在我们就来说怎么变迁过来。
        怎么从离散的点上，离散的时间轴，就是clk，怎么从clk上变成有限的状态的？
0942
        这个呢，就是涉及到有限状态机的经典的理论。
        虽然我们今天是第一天的课程，但是如果这个基础的理论我们做得好，后面的工作就轻松，我们的编码就准确，我们就能写出一个状态机，在一个正确的道路上，而不是走到一个可能会犯错误的道路上。
        我们现在就来说这么个关系，就是无限长的时间轴上的离散的点，如何会变成有限的状态？

0943
        这个发展的过程，就从略了。
        我们就说，现在的有限状态机的基础理论，从离散的这个轴，这个离散的时间轴上的取样点，引入clk，时钟。
        时钟使得时间轴离散化了，它带来了时钟，并且把时间轴离散化了。
        也就是说我需要有一个设备，如果我们有一个设备，引入的时钟，我们就知道，这个时钟的引入，就是引入了时间，并且离散化了。
        输出状态，有限个状态，那么这台机器就是一个状态的发展序列，就实现了这个函数，就是阿兰图灵所描述的函数。
        我们已经解释了，现代的数理逻辑的认知是，在我们所处的时空范围之内，大多数的事物是适用的，是可以用的。

0944
        那么这部分呢，就称之为SM，Sequential Machine。
        本来它的含义是序列机，现在呢也把这个SM解释成State Machine。
        这个时候，SM的这个架构，能够把时间轴变成有限的状态，但是光这个模块是不够的。
        也就是说，对于函数的修正，还要引入输入变量，对于实际的状态机的模型，我们换一个名字，更通用一点，是状态机的模型。
        状态机的模型，不仅和时间有关，还与当前的输入有关，它是当前的输入的函数，它的输出不仅是时间的函数，还是输入的函数。

0945
        我们在前两天的课程里面讨论了时序逻辑和组合逻辑，时序逻辑是有记忆的，它引入了时间以后，当然它和输入是有关系的。
        复杂的情况，象状态机，它的输入就是一个复位，更复杂的情况，我们会来讨论。
        各种各样现实的处理，都跟输入有关系，所以说输入仍然是它的函数指引。
        也就是说输入轴会变迁，会从无限长的连续点，无限长的离散点，变成有限的状态。
        但是总跟输入是有关的。
        所以说，是跟输入有关的，一个状态发展的序列。

0946
        这个状态该如何发展，显然不仅仅是时间的关系。
        如果仅仅是时间的关系，跟输入没有关系，那么任何人都一模一样，整个世界都绝对的雷同了。
        所以说，一定跟现场发生了什么情况有关，现场发生的情况来决定在时钟轴的作用下面，来决定它何时转到不同的状态，状态的转移何时发生变迁。
        所以说状态的这个过程之中，从时钟的引入，状态到时钟离散点的变化上，那么这个状态是从s0，到s1，到s2，到一系列的变化。
        那么究竟在s1上是到s2呢，还是到s3呢？
        这个时候肯定要跟输入有关。
        所以说这个状态的变迁，引入的时钟，并且是跟输入是有关联的。

0947
        也就是说，这个架构要决定两个问题。
        第一个问题，这个状态的变迁，指向何处？转向何处？
        当前如果是s0，下面一个状态转向何处呢？
        s1是转向s2，还是转向s3呢？
        称之为何处的问题。
        另外一个问题，何时。
        何处要解决，何时转呢？
        现在是引入了时钟，离散的点上的，离散的时钟轴上的取样点，当然根据时钟进行转移。
        根据时钟转移是没有问题，但什么时候转仍然是个问题。
        我是第一拍转，第二拍转，第三拍转呢，仍然是SM的事情。
        所以说SM要解决两件事情，第一，转向何处，第二，何时转移。
        它是怎么做到的呢？
0948
        这两个，转向何处，和何时转移，分别用两个功能模块，两个电路单元来实现。
        首先我把时钟这根线先忽略掉，肯定有时钟。
        首先称之为ST的一个部分，State Transition，状态转移，一个部件，一个组件，一个功能模块，一个决策库，一个数据系统，一个专家系统。
        它知道状态转到什么地方。你只要告诉它，现场是什么，当前的输入是什么情况，当前什么情况，当前的状态是什么。