米利型有限状态机

一个简单Mealy机的状态图

在计算理论中，米利型有限状态机（英語：Mealy machine）是基于它的当前状态和输入生成输出的有限状态自动机（更精确的叫有限状态变换器）。这意味着它的状态图将为每个转移边包括输入和输出二者。与输出只依赖于机器当前状态的摩尔有限状态机不同，它的输出与当前状态和输入都有关。但是对于每个米利机都有一个等价的摩尔机，该等价的摩尔机的状态数量上限是所对应米利机状态数量和输出数量的乘积加1（|S'|=|S|*|Λ|+1）。

名源

米利机的名字来自这个概念的提出者，在1951年写了《A Method for Synthesizing Sequential Circuits》的状态机的先驱喬治·H·米利。

運作機制

米利机提供了密码机的一个根本的数学模型。例如考虑拉丁字母表的输入和输出，一个米利机可以被设计用来把给定字母的字符串（一序列输入）处理成密码字符串（一序列输出）。但是，尽管你可能使用米利模型来描述恩尼格玛密码机，状态图对于提供设计复杂密码机的灵活方式而言太复杂了。

米利状态机与摩尔有限状态机不同，米利有限状态机的输出不单与当前状态有关，而且与输入信号的当前值有关。米利有限状态机的输出直接受输入信号的当前值影响，而输入信号可能在一个时钟周期内任意时刻变化，这使得米利有限状态机对输入的响应发生在当前时钟周期，比Moore有限状态机对输入信号的响应要早一个周期。因此，输入信号的噪声可能影响在输出的信号。

形式定义

米利机是6-元组（S, S₀, Σ, Λ, T, G），构成自：

• 状态的有限集合（S）
• 开始状态（也叫做初始状态）S₀，它是（S）的元素
• 叫做输入字母表的有限集合（Σ）
• 叫做输出字母表的有限集合（Λ）
• 将状态和输入符号的对映射到对应的下一个状态 的转移函数（T : S×Σ → S）
• 将状态和输入符号的对映射到对应的输出符号 的输出函数（G : S×Σ → Λ）

在某些表述中，转移函数和输出函数被合并为一个单一函数 $T:S\times \Sigma \rightarrow S\times \Lambda$.

“随时间演化”的概念在此抽象中通过状态机在离散的“计时器滴答”时刻查询随时间变化的输入符号得以实现，这些时刻记为 $t_{0},t_{1},t_{2},...$ ，状态机根据这些理想化瞬间的内部配置作出响应，或者等待下一个输入符号（如先进先出队列）并在其到达时作出反应。

与摩尔有限状态机的比较

1. 米利机通常具有更少的状态数：
   • 其输出变化体现在转移弧上（n²种可能），而非状态节点上（仅需n种状态）。
2. 当作为电子电路实现时（而非数学抽象或代码形式）：
   • 摩尔机比米利机使用更安全：
     • 输出变化始终发生在时钟边沿（总是延迟一个周期）。
     • 米利机中，输入变化会立即通过逻辑电路影响输出——当多台机器互联时可能引发严重问题，若不谨慎设计会导致异步反馈。
   • 米利机对输入响应更快：
     • 同一时钟周期内即可响应——无需等待时钟触发。
     • 摩尔机可能需要更多逻辑电路将状态解码为输出——时钟边沿后需经历更多门延迟。

参见

• 有限状态机
• 摩尔型有限状态机

引用

參考文獻

• Mealy, GH. A Method to Synthesizing Sequential Circuits. Bell System Technical J. 1955: 1045–1079. 

• Roth, Charles H., Jr. Fundamentals of Logic Design. Thomson-Engineering. 2004: 364-367. ISBN 0534378048.