Структурна схема на основі регістра зсуву

Перейдемо до опису схем, блок пам'яті в якій і функції переходів виконані на регістрі зсуву. Розглянемо спочатку можливість побудови такої схеми для автомата з одним входом і двійковим вхідним алфавітом. Припустимо, що автомат заданий повним розміченим деревом вхідних послідовностей. Закодуємо стан цього автомата в такий спосіб. Початковому стану припишемо код 00...01. Стани інших ярусів дерева кодуються послідовно, в порядку збільшення номера ярусу. Якщо стану q_i вже приписаний код a₁, a₂, ..., a_h–1 , a_h, і якщо під дією вхідного сигналу х із цього стану автомат переходить у стан q_j, то стану q_j припишемо код a₂, ..., a_h–1 , a_h. Відповідно до цього правила, код кожного наступного стану виходить із коду попереднього стану шляхом зсуву останнього ліворуч на один розряд і запису вхідного сигналу в останній розряд, що звільнився. При такому способі кодування необхідне число двійкових розрядів h визначається числом ярусів дерева вхідних послідовностей. Як ілюстрація описаного способу, на рис. 7.10 показане кодування графа автомата, отриманого з дерева вхідних послідовностей додаванням дуг, що ведуть із вузлів останнього ярусу в початковий вузол.

Рис7.10. Кодування з використанням операції зсуву

Структурна схема, що реалізує розглянутий спосіб кодування, зображена на рис.7.11.

Рис.7.11. Структурна схема автомата на основі регістра зсуву

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

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

Розглянутий спосіб кодування може бути застосований також з невеликими змінами до автоматів, у яких букви вхідного алфавіту представлені за допомогою k двійкових символів. У цьому випадку код кожного наступного стану повинен формуватися шляхом зсуву коду попереднього стану на k двійкових розрядів і запису вхідного сигналу на вільне місце. Для реалізації автомата, що обробляє слова довжиною n, при цьому потрібен регістр ємністю n×k двійкових розрядів.

Ще один спосіб кодування, що дозволяє використовувати стандартні блоки, називається двокоординатне кодування. Розіб'ємо вузли заданого графа автомата на яруси і пронумеруємо їх. Потім пронумеруємо вузли в кожному ярусі. При цьому кожен вузол графа однозначно визначається двома числами: номером ярусу і номером вузла в ярусі. Замінюючи номера двійковими кодами, одержуємо закодований граф автомата. Якщо при нумерації ярусів графа використати послідовність чисел, що відрізняються на одиницю, то для одержання такої послідовності в схемі може бути застосований двійковий лічильник. У деяких випадках вдається одержати спрощення комбінаційної частини схеми за рахунок використання сусідніх наборів для кодування вузлів у кожному ярусі. Приклад такого кодування наведений на рис.7.12.

Рис.7.12. Двокоординатний спосіб кодування