Математична модель цифрового автомата

1. Q={q₁, q₂,.., q_m} - алфавіт станів - множина станів, в яких може знаходитися цифровий автомат. Кількість станів відіграє важливу роль при реалізації ЦА. Чим більше станів, тим більше вимагається елементів(тригерів) пам'яті, для побудови ЦА.

2. X = {x₁, x₂,.., x_f} - алфавіт вхідних значень - множина значень, які можуть поступати на вхід ЦА. Наприклад, якщо у автомата двохрозрядний двійковий вхід, то елементами алфавіту можуть бути 00, 01, 10 і 11.

3. Y={y₁, y₂,.., y_g} - алфавіт вихідних значень - множина значень, які можуть бути встановлені на виході ЦА.

4. d: Q´ X® Q - функція переходів q(t)=d(x(t), q(t-1)). Функція переходів визначає, в який стан q(t) перейде автомат під впливом вхідного сигналу x(t), якщо у даний момент часу автомат знаходиться у стані q(t-1).

5. l: Q´X® Y - функція виходів y(t)= l(q(t-1), x(t)). Функція виходів визначає яке вихідне значення y(t) буде встановлено на виході автомата залежно від вхідного значення x(t) і поточного стану q(t-1).

6. q₁ Î Q - початковий стан автомата - стан в який встановлюється ЦА після подачі живлення або після скидання

Під алфавітом тут розуміється не порожня множина попарно різних символів. Елементи алфавіту називаються буквами, а кінцева впорядкована послідовність букв - словом в цьому алфавіті.

Поняття стану у визначенні автомата введене у зв'язку з тим, що часто виникає необхідність в описі поведінки систем, виходи яких залежать не лише від стану входів в даний момент часу, але і від деякої передісторії, тобто від сигналів, які поступали на входи системи раніше. Стани якраз і відповідають деякій пам'яті про минуле, дозволяючи усунути час як явну змінну та виразити вихідний сигнал як функцію стану і входу в даний момент часу.

Абстрактний автомат (рис. 1.2) має один вхід і один вихід. В кожен момент t дискретного часу автомат знаходиться в деякому стані q(t-1) з множини станів автомата, причому в початковий момент t = 0 він завжди знаходиться в початковому стані q(0)=q₁. Автомат, який завжди починає працювати з початкового стану, називається ініціальним.

У момент t, будучи в стані q(t-1), автомат здатний сприйняти на вході букву вхідного алфавіту х(t)Î Х. Відповідно до функції виходів він видасть в той же момент часу t букву вихідного алфавіту y(t)= l(q(t-1), x(t)) і відповідно до функції переходів перейде в наступний стан q(t)=d(x(t), q(t-1)), q (t-1)Î Q, y(t) Î Y.

Зміни стану цифрового автомата викликаються вхідними сигналами, які виникають поза автоматом і передаються в автомат по кінцевому числу вхідних каналів. Відносно вхідних сигналів цифрових автоматів приймаються два допущення:

- для будь-якого цифрового автомата число різних вхідних сигналів обов'язкове скінченне;

- вхідні сигнали розглядаються як причина переходу автомата з одного стану в інший і відносяться до моментів часу, які визначені відповідними ним переходами.

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

Результатом роботи цифрового автомата є видача вихідних сигналів, що передаються з автомата в зовнішні кола по кінцевому числу вихідних каналів. Відносно вихідних сигналів вводяться допущення, аналогічні допущенням для вхідних сигналів. По-перше, число різних вихідних сигналів для будь-якого цифрового автомата завжди скінченне. По-друге, кожному відмінному від нуля моменту автоматного часу відноситься відповідний йому вхідний сигнал. Реальний фізичний вихідний сигнал y(t), віднесений до моменту часу t, з'являється завжди після відповідного цьому ж моменту часу вхідного сигналу x(t). Що ж стосується моменту часу t переходу автомата із стану q(t - l) в стан q(t), то сигнал y(t) може фактично з'явиться або раніше, або пізніше за цей момент.

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

У практиці роботи автоматів часто мають місце випадки, коли деякі комбінації значень вхідних символів подавати неприпусти­мо. Такі комбінації є за­бороненими для автомата. Автомати, що мають заборонені вхідні слова, називаються частковими. Наприклад, деякий абстрактний автомат має вхідний алфавіт X, що складається із двох символів x₀ і x₁, кожен з яких може набувати значення 0 або 1. Слова є дозволеними, а слово x₁x₀ - забороненим.

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

Функція задає значення виходів автомата з ал­фавіту Y. Кількість символів алфавіту Y може не збігатися із кількістю символів алфавіту X. За аналогією з перетворювачами кодів, автомат забезпечує відображення слів вхідного алфавіту у слова вихідного алфавіту. Якщо взяти можливу кількість слів вхідного алфавіту за Р_х, вихідного алфавіту - за К_у, то залежно від спів­відношення між Р_х та К автомати можуть за функціональним призначенням поділятися на три групи.

Якщо К_y < Р_х, маємо автомати, які призначені для розв'язання задач керування, стиснення інформації, розпізнавання повідомлень. Наприклад, цифровий кодовий замок може мати 3...5 вхідних символів і лише один вихідний. Інший приклад - розпізнавання введеного пароля під час отримання доступу до комп'ютера.

Якщо К_у > Р_x то маємо ситуацію, коли довжина вихідних слів буде більшою, ніж вхідних, оскільки кількість слів повинна бути однаковою. Вихідні слова будуть містити надмірну інформацію, що використовується, як було зазначено у попередніх розділах, для синтезу завадостійких кодів.

Якщо К_у = Р_х, кількість і довжина вхідних та вихідних слів од­накові. Такі автомати використовуються для деяких кодових пе­ретворень (наприклад, перетворення двійкового коду на код Грея тощо), для реалізації деяких методів захисту даних від несанкці­онованого доступу (метод підстановок) і т. д.

Контрольні питання і завдання

1. Дайте означення автомата.

2. Які підходи застосовують до визначення і вивчення автоматів та в чому їх сутність?

3. Сформулюйте визначення абстрактного автомату

4. Сформулюйте визначення кінцевого автомату

5. Порівняйте між собою синхронні і асинхронні цифрові автомати

6. Сформулюйте визначення комбінаційного цифрового автомата.

7. Подати узагальнену структурну схему автомата.

8. В чому різниця між детермінованими і імовірнісними автоматами?

9. У чому зміст головних параметрів цифрового автомата?

10. Що є узагальненою математичною моделлю ЦА? Які компоненти включає і які між ними встановлені зв'язки?

11. Прокоментуйте поняття «внутрішній стан» ЦА?

12. Що означає частково визначений абстрактний автомат?