Тема 1.2 Автомати Мілі і Мура

1.2.1 Закони функціонування автоматів Мілі і Мура

У практиці використання цифрових автоматів можна виділи­ти невелику кількість типових алгоритмів їх функціонування.

Залежно від способу організації функції виходу синхронні автомати діляться на автомати Мілі (Mealy), або автомати I роду і автомати Мура (Moore) - автомати II роду.

У автоматах Мілі - вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом q(t - 1) автомата в попередній момент часу (t - 1). Математичною моделлю таких автоматів служить система рівнянь :

У автоматах Мура вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом q(t) в даний момент часу t. Математичною моделлю таких автоматів є система:

Приведені рівняння описують функціонування автомата I роду (автомат Мілі), вихідні сигнали якого формуються у момент переходу автомата з одного стану в інший. Якщо вихідні сигнали автомата залежать тільки від станів елементів пам'яті , то такий автомат називається автоматом II роду (автомат Мура). Вихідні сигнали останнього формуються у момент фіксації чергового стану.

Цифровий автомат (першого або другого роду) називається правильним, якщо вихідний сигнал y(t) визначається одним лише його станом (q(t - 1) або q(t)) і не залежить явно від вхідного сигналу x(t).

Різниця між автоматами Мілі і Мура полягає лише в тому, що вихідний сигнал останнього залежить тільки від його внутрішньо­го стану, у той час як в автомата Мілі значення вихідного сигна­лу залежить також і від вхідного сигналу.

У ЦА Мілі вихідний сигнал є тільки тоді, коли є вхідний сигнал, а у ЦА Мура вихідний сигнал є завжди. Доцільно вважати, що вихідний сигнал у ЦА Милі носить імпульсний характер, а у ЦА Мура - потенційний характер.

1.2.2 Поєднана модель автомата (С-автомат).

Абстрактний С-автомат - математична модель дискретного пристрою, яка визначається множиною з 8 елементів: S=(Q, X, W, U, , ₁, ₂, q₁), де:

Q={q₁, q₂, .., q_m} - множина станів;

X={x₁, x₂, .., x_f} - множина вхідних сигналів;

W={w₁, w₂,.., w_g}- множина вихідних сигналів типу 1,вихідний абстрактний алфавіт автомата Мілі;

U={u₁, u₂, .., u_h}- множина вихідних сигналів типу 2, вихідний абстрактний алфавіт автомата Мура;

: Q X Q - функція переходів;

q₁  Q - початковий стан автомата;

₁: QX W - функція виходів;

₂: QX U- функція виходів.

Абстрактний С-автомат можна представити у вигляді пристрою з одним входом, на який поступають сигнали з вхідного алфавіту X, і двома виходами, на яких з'являються сигнали з алфавітів W і U (рис. 1. ). Відмінність С-автомата від моделей Мілі і Мура полягає в тому, що він одночасно реалізує дві функції виходів ₁ і ₂, кожна з яких характерна для цих моделей окремо. С-автомат можна описати наступними рівняннями:

Рисунок 1. 3 – Абстрактний С-автомат

Вихідний сигнал u_h = ₂(q_m) видається увесь час, поки автомат знаходиться в деякому стані q_m. Вихідний сигнал w_g = ₁(q_m, x_f) видається під час дії вхідного сигналу x_f при знаходженні автомата в стані q_m.