22111

Структурная схема конечного автомата

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

Комбинационная схема строится из логических элементов образующих функционально полную систему а память на элементарных автоматах обладающих полной системой переходов и выходов. Каждое состояние абстрактного автомата ai i=0n кодируется в структурных автоматах набором состояний элементов памяти Q2 R=1R. Здесь Q состояние автомата а ai = {0 1} Как и прежде Q Общее число необходимых элементов памяти можно определить из следующего неравенства 2R n 1.

Русский

2013-08-04

26.5 KB

3 чел.

Лекция 14

Структурная схема конечного автомата.

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

Каждое состояние абстрактного автомата ai, i=0,n, кодируется в структурных автоматах набором состояний элементов памяти Q2, R=1,R. Поскольку в качестве элементов памяти используются обычные двоичные триггера, то каждое состояние можно закодировать двоичным числом ai=Q1Q2….Qr. Здесь Q – состояние автомата, а ai = {0, 1}/ Как и прежде Q 

Общее число необходимых элементов памяти можно определить из следующего неравенства 2R > n + 1. Здесь (n+1) – число состояний. Логарифмируя неравенство получим R > ]log2 (n+1)[. Здесь ]с[ - означает, что необходимо взять ближайшее целое число, большее или равное C.

В отличии от абстрактного автомата, имеющего один входной и один выходной канала, на которые поступают сигналы во входном X={x1, x2,…..,xm} и выходном Y={y1,y2,….,yk} алфавитах, структурный автомат имеет L входных и N выходных каналов. Каждый входной xj и выходной yj сигналы абстрактного автомата могут быть закодированы двоичным набором состояний входных и выходных каналов структурного автомата.

Очевидно число каналов L и N можно определить по формулам

L ]log m[;

N ]log k[,

аналогичным формуле для определения a3 под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния ai в состояние as под действием сигнала xj с выдачей сигнала yg соответствует переход структурного автомата из состояния () в состояние (), под действием входного сигнала ()  с выдачей выходного сигнала (). Для того, чтобы структурный автомата перешел из одного состояния в другое, необходимо изменить состояние элементов памяти Qr.

Изменение же состояния элементов памяти происходит под действием сигналов U=(U1,U2,…,Ur) поступающих на их входы. Эти сигналы формируются комбинационной схемой II и называются функций возбуждения элементов памяти (элементарных автоматов). На вход комбинационной схемы II, кроме входного сигнала xj, по цепи обратной связи поступают сигналы Q=(Q1, Q2, …, QR), называемые функцией обратной связи от памяти автомата к комбинационной схеме. Комбинационная схема I служит для формирования выходного сигнала yg, причем в случае автомата Мили на вход этой схемы поступает входной сигнал xj, а в случае автомата Мура – сигнал xj не поступает, т.к. yg не зависит от xj.


 

А также другие работы, которые могут Вас заинтересовать

67963. Микробиологическая диагностика риккетсиозов 97 KB
  Актуальность темы: Заболевания, вызываемые риккетсиями, называются риккетсиозами, они распространены во всех странах мира. До недавнего времени семейство риккетсий включало роды Rickettsia, Orienta, Erlichia, Coxiella. По современной класификации семейство Rickettsiaceae включает два рода...
67965. Санитарная микробиология 94.5 KB
  Цель: Освоение практических навыков определения санитарных показателей воды. Основными задачами санитарной микробиологии являются: Разработка и совершенствование микробиологических методов исследования объектов окружающей среды воды воздуха почвы пищевых продуктов предметов обихода...
67968. Клиническая микробиология. Госпитальные инфекции 67 KB
  Клиническая микробиология – это раздел частной медицинской микробиологии, посвященный изучению заболеваний, вызванных условно-патогенными микроорганизмами. Развитие подобных заболеваний связано со снижением иммунного статуса человека, развитием иммунодефицитных состояний, интенсивной антибиотикотерапией...
67969. Система управления базами данных Microsoft Access 2007. Создание базы данных 393.5 KB
  Перед созданием таблиц в СУБД необходимо для каждого поля столбца таблиц определить некоторые характеристики полужирным шрифтом выделены ключевые поля: Тематика Характеристики поля Поле Тип поля Списочный характер Возможные ограничения Индексируемость Обязательность заполнения Код тематики...
67970. Система управления базами данных Microsoft Access 2007. Анализ и изменение данных с помощью запросов. Создание запросов с параметрами 302.5 KB
  Авиапассажиры код авиапредприятия код города назначения код страны города назначения номер рейса дата вылета фамилия адрес Авиапредприятия код наименование адрес телефон Города код наименование Страны код наименование страны. Выпуск изделий код изделия код предприятия количество выпускаемых...
67971. Програмні засоби розробки і відладки програм на мові С++ 5.19 MB
  Схематичне зображення вікна середовища розробки програм 2 Відкрити проект Виконайте послідовність дій зображених на малюнку. 2 Відкрити файл проекту FRNMS5.mdp Виберіть проект FRNMS5. 3 Конвертувати файл проекту до формату Microsoft Visul Studio 2005 тільки при першому...