集线逻辑和分线逻辑数字电路一个电路向另一个电路传递信号时通常不是一根导线而是多根导线组合成一根多维序组的导线即总线bus它通常也不直接不变地传递给另一个电路而是有集线和分线的变化后再输入到另一根导线。比如两个总线A(1,0)和总线B(1,1,0)集线成一根总线后变成总线C(1,0,1,1,0)。集线逻辑和分线逻辑的的序组变化在某个数学系统下集线分线后元素的顺序怎么排列两个逻辑运算在什么样的代数结构下本作者将在后续创作中讨论。分线逻辑和集线逻辑有一点不同导线在流出方向上具有复制性也就是说单一根导线D(1)也可以分线成(1,1)例如总线C(1,0,1,1,0)可以分线(1,0,1)和(1,1,0)也可以分线为(1,0,1,1)和(0,1,1,0)参照系统互联中的串联和并联。一根总线可以看成一个列向量或者数组。作为第一小节本文章以下的所有导线都看成由多根单独的导线组合而成的一根总线。电路封装与函数:多个逻辑门组合在一起没有回路结构如同有向无环图叫做组合电路(主要是结构上定义尽管一些电路有向有环真值表的形式和组合电路一致也不能是组合电路)。可以证明任何有限映射都能用组合电路实现哪怕无限映射也可以用无限的组合电路实现。多个逻辑门组合在一起成组合电路把它看成一个整体黑盒只看输入端和输出端就是封装。按照程序的思维每一根导线或者总线就是一个变量输入端就是形参而只在电路内部的导线就是实参。传播延迟模型假设一个非门的门延迟是30纳秒输入端起始为0因此输出端为1输入端产生了一个2纳秒的010的脉冲有两种情况1输出端会产生延迟30纳秒的101的脉冲2没有时间识别这个脉冲而不变化。前者是传播延迟模型后者是实际电路中会发生的惯性延迟模型。前者能更好兼容数学框架为构建模拟机的基础。真实的电路中为了适应后者会采用边沿触发即通过检测“信号的变化”而不是“信号”来改变时序电路的状态触发分为两种边沿触发和电平触发电平触发就是只检测“信号”而处理“信号的变化”要比处理“信号”更快避免了逻辑门没有识别到极短的脉冲信号。构建虚拟机一般只考虑传播延迟模型因此边沿触发在数学模型中是不必要的可以将极短时间的电平触发代替边沿触发。构建人列计算机中我们假设逻辑门是传播延迟模型后者模型是没必要的假设。动态系统dynamical system一个动态系统是一个三元组(状态集合时间集合演化映射演化映射是状态集合×时间集合→状态集合的映射。也叫状态转移函数递推函数下文统称递推函数。意味着一个状态经过了某个时间后变成下一个状态。其实就是一个函数的输出在递归到自己的输入时间意味着递归了多少次。本文章探讨的是离散时间离散无序关系状态的动力系统。考拉兹猜想就是典型的离散动力系统猜想它的递推函数如果是偶数就除以二。如果是奇数就乘以三1。猜想认为所有正整数都会收敛到1_2_4循环中。稳态给一个递推函数输入一个初始值再把输出的值再投进去输入反复操作无穷次产生的数列轨道只有两种结果收敛或者发散数学上发散的定义就是不收敛。但在学术圈中稳态没有严谨定义。本文章探讨的是离散时间离散状态的动力系统也不用考虑”收敛但一直变化“的情况因此本文章定义在某个时间t系统进入稳态意味着状态转移函数在时间t下的输出不动点。不动点就是输入进状态转移函数后的输出保持不变。研究数列通常还伴随对差分的研究。差分有三种前向差分Δx_nx_n1-x_n如果论文只说差分默认就是这个差分后向差分∇x_nx_n-x_n-1中心差分δx_nx_n1-x_n-1。差分方程就是含差分的方程F(n,x_n​,Δx-n​,Δ^2 x_n​,…,Δ^k x_n​)0可以证明和F(n,x_n,x_n1​,…,x_nk​)0等价其中k是差分方程的阶数例如x_n1​2x_n​3就是一个一阶差分方程。带反馈的电路的动态系统以上探讨的都是没有和外部连接与外界隔离的动力系统实际计算机是有输入和输出的。接下来探究一个组合电路的输出的其中一个分量也就是输出总线中拿出几根导线进行分线反过来接入自己的输入的组合电路。在系统控制论中这也叫开环控制即系统的输出不决定系统的输入一般的组合电路只是闭环控制即系统的输出决定系统的输入。当电路产生反馈后会产生这样的问题例如一个与非门的输出分线两根其中一根连接自己的其中一个输入另一个输入作为封装后的形参输入形参初始默认为0改为输入1后输出会产生的010101一样的振荡难以控制它的变化。假设逻辑门处理一个信号需要一个传播延迟的时间那么非门在这种情况下就是每经过一次传播延迟时间更新一次自己的输出因此可以把该模型下看成是一个自动控制领域中的离散时间动态系统。与之对应有连续时间系统但本文章不讨论。其中一次传播延迟可以看作一个离散时间系统中的一个离散单位时间。把这个与非门替换成一般的组合电路输入的形参反馈电路的实参以及输出都看作多根组合而成的总线这些总线可以编码成更多的值而不是单根导线的一个值。带反馈的电路的结构带反馈的电路可以看成一个连接了三根导线的每经历一个单位时间就允许一次的函数第一根导线来自外部的多个输入组合成一个有序组可以看成一个整体的输入端例如c语言int add(int a, int b) {return a b;}a和b看成一个整体有序组的输入端所以是一根导线。第二根是反馈电路它是由函数的输出再连接会自己的输入的一根导线可以看成内部的不能连接外部的实参。第三根是输出端。三根导线说明是三个变量输入x内部实参s也就是states内部状态这种电路可以看成是一个有限状态机下文会讲输出y。在离散时间系统中输入x是随着时间变化的量输入序列是x_0,x_1,x_2......x_t-1,x_t,x_t1......同样y和s也是如此只是y和s是输入x在经过一个时间单位后变化的量比如x_0x_1x_2x_3发生变化那么y_0为空值也可能是设置过的初始值或者在时间是双向无限序列的假设下的值y_1变为非空值是一个根据s_0和x_0根据函数变化的值假设系统初始状态就是稳态s_0因为x_0x_1s_0s_1所以y_2y_1。带反馈的电路的数学描述因此得出一个递推函数y_t1G(s_t,x_t)。由于s也受上一个单位时间的x和自己上一个单位时间的s的影响也有一个递推函数s_t1F(s_t,x_t)。这两个递推函数共同构造了离散时间动态系统的数学描述。因此可以判断在用组合电路构建离散时间动态系统最起码要用到两个单独的组合电路。前者就是输出函数后者是状态函数。状态函数方程和输出函数方程足以描述时序电路的所有逻辑与FSM(Finite State Machine)等价。这种电路也叫mealy电路如果大学学过数字电路还会学到moore电路但是mealy电路可以证明是比moore电路更强的数学表达只需要把mealy电路的输出函数中对x_t进行空运算。事实上我们只需要学习mealy电路所谓教育和学术共同体只是一群循规蹈矩者动态系统和数字电路学是20世纪中叶的新产物对于新事物所有教育体系为了更低成本的教学设计就会照搬所谓old school形容的就是这些人。因此可以想象时序电路的结构输入总线会进行分线分别输入主要的两个部分两个组合电路F和G它们的输入端都是能接受两根总线分别是x和s输出只有一根总线F输出sG输出y。F输出的s会分线其中一根连接自己的其中一个输入端另一根连接G。因此G接受了两根总线一根来自总体外部的输入总线的分线一根来自F输出s的分线。时钟由于F的总线s产生了自我反馈会产生以下问题1.由这个反馈电路产生的传播延迟是不是固定的所以不同的时序电路作为离散时间动态系统有着不同的离散时间那么不同的动态系统交互就存在难以协调2.组合电路本身刚接受到一个信号输出时本身会输出一些稳定的毛刺信号这些信号是因为不同信号经过的逻辑门数量路径不同产生的如果这些毛刺信号被反馈就会进一步加剧不稳定的信号产生。3.带反馈电路天然有信号振荡的风险为了解决这些问题就要引入状态寄存器接入到F的输出端后也就s导线s导线分线前的位置寄存器前的原来s导线为s_t1寄存器后的原来s导线为s_t它的作用是只有通过某种触发边沿触发或者电平触发前s导线才会因为后s导线的值而更新否则不会一直更新下去产生振荡寄存器还外接一个新的输入导线CLK作为接受时钟信号用时钟信号作为动态系统的新的离散时间单位代替传播延迟。状态寄存器的CLK的值决定了它是否“透明”当他被激活时可以无视它的存在没有激活时只会保留上一次透明时的值。传统的mealy电路是输入导线x直接绕过状态寄存器连接G电路但要符合以上的动态系统假设应该要接入寄存器由时钟信号决定是否透明穿过寄存器连接G电路。状态寄存器属于存储电路存储电路也是一种时序电路。