авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ И НАУКИ

УКРАИНЫ

КИЕВСКИЙ НАЦИОНАЛЬНЫЙ

ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

Л.Ф. МАРАХОВСКИЙ, Н.Л. МИХНО

ОСНОВЫ

ТЕОРИИ АВТОМАТОВ

И

СИНТЕЗА РЕКОНФИГУРИРУЕМЫХ

КОМПЬЮТЕРНЫХ СИСТЕМ

Киев КНЭУ 2010

УДК 519.95: 004.274

ББК 32.973

Автор: Л.Ф. Мараховский, Н. Л. Михно

Рецензенты:

А. П. Будя, кандидат технических наук, доцент, заведующий ка федры математики та информационных технологий, Киевского уни верситету туризму, экономики и права.

А. И. Безверхий, доктор физ.-мат. наук, наук, профессор, старший научный сотрудник института механики НАН Украины В. В. Гавриленко, доктор фіз.-мат. наук, заведующий кафедры информационные системы и технологии Национального транспортно го университета.

Мараховский Л.Ф., Михно Н. Л.

Основы теории автоматов и синтеза реконфигурируемых компьютерных систем: монография. – К.: КНЭУ, 2010. – 276 с.

"Основы теории автоматов и синтеза реконфигурируемых компьютерных систем: мо нография. – К.: КНЭУ, 2010. – 276 с.

Книга рассматривает теорию автоматов 1-го и 2-го рода, а также автоматов 3-го рода, которые совместно представляют собою основу современной теории автоматов. В ней изложены основы синтеза и анализа элементарных схем памяти: двоичных, много стабильных, многофункциональных (МФСП) и многоуровневых (МУСП), составляю щих основу элементной базы современных компьютерных систем и сетей.

В книге также рассмотрена теория синтеза реконфигурируемых компьютерных систем с памятью на триггерах на «автоматном» уровне, а также дана теория синтеза реконфигурируемых компьютерных систем с памятью на многоуровневых схемах па мяти на «элементном» уровне, что позволяет комплексно подойти к проектированию современных компьютерных систем и сетей.

В книге дано новое направление построения компьютеров на основе МФСП и МУСП, что способствует прогрессу вычислительной техники. Компьютер может быть реализован на современных логических элементах, используемых в СБИС, ПЛИС, ОЗУ, что может положительно повлиять на развитие реконфигурируемых устройств, компьютеров, компьютерных систем и сетей, в которых необходима адаптация к клас сам решаемых задач, повышение отказоустойчивости аппаратуры, самозащита компь ютеров от несанкционированного доступа.

Книга рассчитана на студентов и преподавателей высших учебных заведений, а также на разработчиков, которые занимаются проектированием реконфигурируемых современных компьютерных систем и сетей".

Мараховский Л.Ф.

Михно Н.Л.

© КНЭУ, СОДЕРЖАНИЕ УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ..………… ВВЕДЕНИЕ…….…………………………………………..….... ГЛАВА ПОНЯТИЯ АВТОМАТА: ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ... § 1.1. Алфавитный способ преобразования информации …. § 1.2. Понятие об алгоритме…………….…………………… § 1.3. Понятие о дискретном автомате………………......….. ГЛАВА АБСТРАКТНАЯ ТЕОРИЯ АВТОМАТОВ...………….…..... § 2.1. Понятие об абстрактном автомате …………….…....... § 2.2. Понятие об абстрактных автоматах Мили и Мура....... § 2.3. Понятие об многофункциональных абстрактных авто матах Мили и Мура………………………………..………..... § 2.4. Некоторые понятия о изменениях в функционировании и самоорганизации в автоматах…..……………...…………... § 2.5. Некоторые модификации абстрактных конечных авто матов………………………………………….…………...….. § 2.6. Понятие об абстрактных многофункциональных авто матах Мараховского……………………………....……….… § 2.7. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний………………………... § 2.8. Понятие об абстрактных вероятностных автоматах 3-го рода………………….………………………….…………..….. § 2.9. Понятие об абстрактных нечетких автоматах 3-го ро да……………………………………………………..…..….... § 2.10. Классификация детерминированных абстрактных ав томатов……………...………………………………………… § 2.11. Классификация недетерминированных абстрактных автоматов……………...…………………...........................

.... ГЛАВА СПОСОБЫ ЗАДАНИЯ АВТОМАТОВ……………….…...… § 3.1. Некоторые понятия в теории абстрактных автоматов…………………………………..………………… § 3.2. Табличные и графические способы задания классиче ских автоматов Мили и Мура……………………………….. § 3.3. Табличные способы задания многофункциональных аб страктных детерминированных автоматов…..…………..… § 3.4. Табличные способы задания абстрактных вероятност ных автоматов 3-го рода……………..……..…..……….….. § 3.5. Табличный способ задания абстрактных нечетких ав томатов 3-го рода…………………………….………………. § 3.6. Графические способы задания переходов в многофункциональных абстрактных автоматах……....... § 3.7. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти…………………..……….… § 3.8. Способ задания иерархического абстрактного автомата с многофункциональной системой организации памяти с по мощью полиграммы…………….………….……..….….…. ГЛАВА АНАЛИТИЧЕСКИЙ ОБЗОР РАБОТ В ОБЛАСТИ ПРОЕК ТИРОВАНИЯ КОМПОНЕНТОВ КОМПЬЮТЕРНЫХ СИС ТЕМ НА «АВТОМАТНОМ» УРОВНЕ...... § 4.1. Введение в проектирование реконфигурируемых сис тем на «автоматном» уровне…………....……………….… § 4.2. Развитие реконфигурируемых систем на «автоматном»

уровне …………………………….. § 4.2.1. Архитектура процессоров фирмы MIPS ……… § 4.2.2. Кэш-память команд …………………………... § 4.2.3. Обработка команд перехода § 4.2.4. Архитектура процессоров фирмы Intel …….. § 4.2.5. Повышение производительности процессоров Intel путем увеличения производительности устройств про граммным путем…………………...…………….…... § 4.2.6. Обзор расширения набора команд SSE4 для архи тектуры Intel……………………………….................... § 4.3. ринципы мультиконвейерной вычислительной структу ры в реконфигурируемых вычислительных системах….. § 4.4. Построение процессоров для компьютеров на основе ПЛИС.………………………………………………...…….… §4.5. Использование ПЛИС для построения мультипроцес сорных реконфигурируемых систем.……………..….….… § 4.5.1. Заказные СБИС.……………………………....… § Программируемые логические интегральные схемы.…………………………………………….…..…. § 4.5.3. Принципы построения базовых модулей реконфи гурируемых вычислительных структур на основе ПЛИС……………………………………..………..…..… § 4.6. Основные направления развития высокопроизводи тельных реконфигурируемых систем..…………….….…... ГЛАВА МЕТОДЫ СИНТЕЗА ЭЛЕМЕНТАРНЫХ МНОГОФУНК ЦИОНАЛЬНЫХ СХЕМ ПАМЯТИ КОМПЬЮТЕРНЫХ СИС ТЕМ……………………….…………………………………. § 5.1. Символьный язык описания элементарных многофунк циональных схем памяти…………….……………………... § 5.2 Исследование возможных вариантов многофункцио нальных схем памяти в символьном числе……….……….. § Синтез многофункциональных схем памяти по символь ному описанию…………………………………………. § 5.4. Определение входных слов многофункциональных схем памяти……………………………………….................. § 5.4.1.Определение однозначных элементарных входных слов ……….………………………..……………….. § 5.4.2. Определение укрупненных элементарных вход ных слов…….………………….………………..…..…… § 5.4.3. Анализ работы многофункциональных схем памя ти с помощью имитационного моделирования…….…. § 5.5. Характеристики параметров многофункциональных схем памяти…………….………….………..……………….. ГЛАВА МЕТОДЫ СИНТЕЗА ЭЛЕМЕНТАРНЫХ МНОГОУРОВНЕ ВЫХ СХЕМ ПАМЯТИ КОМПЬЮТЕРНЫХ СИСТЕМ.… § 6.1. Символьный язык описания многоуровневых схем па мяти …………………….………………….…….……...…… § 6.2. Определение параметров многоуровневых схем памяти по символьному описанию………….…….…...……..…..… § 6.3. многоуровневых схем памяти по символьному описа нию с учетом ограничений элементов…… § 6.4. Принцип структурной организации элементарных мно гоуровневых схем памяти ………………………...…...…… § 5. Метод проектирования общего автомата стратегии для всей многоуровневой схемы памяти ……………………..... § 6.6. Метод логического проектирования многоуровневой схемы памяти класса с общим автоматом стратегии…..…. § 6.7. Метод логического проектирования многоуровневой схемы памяти класса с автоматами стратегии для каждой группы многоуровневых схем памяти ………...……….….. § 6.8. Анализ работы многоуровневой схемы памяти с помо щью имитационного моделирования ………...…….……… ГЛАВА СРАВНЕНИЕ ПАКРАМЕТРОВ БАЗОВЫХ ЭЛЕМЕНТАР НЫХ СХЕМ ПАМЯТИ..……………………...............…….. § 7.1. Классификация базовых схем памяти ……..…..….... § 7.2. Сравнение параметров схем памяти ………………... § 1 Определение количества логических элементов необ ходимых для построения схемы памяти § 2 Определение максимально возможной нагрузки по выходам схем памяти § 3 Определение количества внутренних связей схем па мяти …………………………………………………... § 4 Определение количества внешних связей схем памяти ………………………………….……………..… § Определение количества элементов на одно состояние схемы памяти….. § Сравнение рабочей частоты переключения и функцио нальных возможностей схем памяти… ГЛАВА МЕТОДЫ ПОСТРОЕНИЯ РЕКОНФИГУРИРУЕМЫХ УСТ РОЙСТВ КОМПЬЮТЕРНЫХ СИСТЕМ НА ЭЛЕМЕНТАХ МНОГОУРОВНЕВОЙ ПАМЯТИ § Методы построения реконфигурируемых регистров на мно гоуровневых схемах памяти § Анализ параметров реконфигурируемых параллельных ре гистров на многоуровневых схемах памяти……………..

§ Методы построения реконфигурируемых регистров сдвига на многоуровневых схемах памяти………… § Методы построения реконфигурируемых счетчиков на многоуровневых схемах памяти § 8.4.1. Основные понятия §.4.2. Методов построения реконфигурируемых счетчи ков на многоуровневых схемах памяти § 8.5. построения реконфигурируемых устройств управления на многоуровневых схемах ГЛАВА МЕТОДЫ ПОСТРОЕНИЯ РЕКОНФИГУРИРУЕМЫХ ПРО ЦЕССОРОВ И КОМПЬЮТЕРОВ, ОСУЩЕСТВЛЯЮЩИХ ОДНОВРЕМЕННО ОБРАБОТКУ ОБЩЕЙ И ЧАСТНОЙ ИНФОРМАЦИИ ………………...……………..……………. § 1. Разработка принципов построения реконфигурируемых архитектур и структур процессоров на многоуровневых схе мах памяти………..……………………….…………………. § 9.2. Последовательная и параллельная обработка иерархи ческой информации в современных процессорах § 9.3.Способы задания иерархических автоматов на много уровневых схемах памяти...…… § 9.4. Разработка принципов построения реконфигурируемых процессоров и компьютеров, одновременно обрабатывающих общую и частную информацию. § 9.5. Методы построения реконфигурируемых компьютеров на «элементному» уровне................ § 6. Ускорение выполнения алгоритмов в реконфигурируе мых компьютерных системах на многоуровневых схемах па мяти ЗАКЛЮЧЕНИЕ ЛИТЕРАТУРА……………………………………………….. УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ ВТ – вычислительная техника ЭА – элементарный автомат ЭВМ – электронные вычислительные машины БА – базовые автоматы (логические элементы И-ИЛИ-НЕ, ИЛИ НЕ, И-НЕ) многоустойчивая схема памяти многофункциональная схема памяти многоуровневая схема памяти схема автоматной памяти многофункциональный элементарный автомат иерархический автомат операционный прибор устройство управления микропроцессор регистр интегральная схема сверхоперативная память арифметико-логическое устройство большая интегральная схема СБИС сверхбольшая интегральная схема ПЛИСпрограммируемые логические интегральные схемы реконфигурируемые устройства мультиконвейерная вычислительная структура IOB – блоки ввода/вывода CLB – конфигурируемые логические блоки DSP – блоки встроенных модулей цифровой обработки сигналов DCM – цифровые модули управления синхронизацией LUT – таблицы преобразования look-up tables CMT (Clock Manager Tile) – модуль формирования тактичного сигнала ВВЕДЕНИЕ Теория конечных автоматов характеризуется широким ис пользованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на ба зе булевой алгебры и модели дискретного устройства в виде так называемого конечного автомата. На ней основано разви тие методов логического проектирования дискретных уст ройств и методов построения тестов для проверки последних, обеспечение надежности и устойчивости их работы, решения задач «конструирования» дискретных устройств. Возникли отдельные ответвления теории конечных автоматов в виде теории вероятностных и нечетких автоматов, коллективного поведения автоматов, экспериментов и т. д. [1;

3–4;

6;

8;

13– 14;

20;

25–27;

40–41;

49;

55–56;

66;

69;

86;

104;

110;

122;

126], Теория автоматов представляет собой раздел теории управляющих машин, изучающий математические модели преобразователей дискретной информации, называемые авто матами (от греч. аutmatos – самодействующий). С теоретиче ской точки зрения, такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т. п.), так и абстрактные системы (матема тические машины, аксиоматические теории и т. д.). Характер ной особенностью этих преобразователей является дискрет ность функционирования и конечность областей значений па раметров, описывающих их.

В Библии сказано, что в начале было слово… Когда-то язык был слабым преобразованием вещей в сознании челове ка, прозрачной зыбкой моделью, отделяющий человека от не живой материи. За прошедшие тысячелетия язык развился до такой степени, что сам проявляет тенденцию к независимому движению и управляет развитием разума. Он сконцентрировал в себе все тайны Вселенной, в нем, возможно, скрыты ответы на извечные вопросы бытия.

Одна и та же модель одного и того же явления разными людьми воспринимается по-разному: формула может оста ваться неизменной, но интерпретация ее может быть разной.

Мир человеком воспринимается с помощью моделей, совер шенствующих друг друга и увязываемых между собой до тех пор, пока не происходит революция в идеях, прекращающая такое объединение моделей.

Наши модели вначале нечеткие. Это наглядно видно на примере изучения счетом младенца. Ему необходимо повто рить от 6-ти до 10 раз, чтобы он мог различать один палец от двух. Наши мысли, сформированные на основе независимых моделей тоже нечеткие. Этим мы существенно отличаемся от компьютера!

Человек, помимо способности рассуждать и логически мыслить, обладает, как все живые существа, способностью принимать в расчет параллельно соображения, как общего, так и сопутствующего характера. Не рискуя сильно ошибиться, как писал французский профессор Арнольд Кофман, – «можно предсказать, что технология будет развиваться по пути, сбли жающем идеи компьютерного и обычного человеческого мышления в ожидании того дня, когда компьютеры начнут обрабатывать общую информацию принципиально параллель но, без предварительной последовательной обработки» [49].

Понятие вероятности развивалось с XVII века. Идея веро ятности появилась в процессе развития квантовых представ лений в физике в начале ХХ столетия. Возник вопрос о соот ношения динамических и статических законов. Известна дис куссия между Нильсом Бором и Альбертом Энштейном, в ко торой Бор отстаивал вероятностный характер микропроцессов, а Энштейн отстаивал классическое представление, утверждая, что «Бог не играет в кости». К сожалению, эта дискуссия не завершилась и до сих пор.

Нобелевский лауреат, философ Игорь Пригожин внес один новый и истинно важный момент в эту центральную для нас проблему, который позволяет решить вопрос о соотноше нии причиной детерминированности и многовариантности решений в сложных системах. Почему случайность реализует ся именно так, как это происходит, а не иначе. Только ответ на данный вопрос позволяет понять, что такое условие и в чем специфика их влияния [127].

Теория автоматов возникла в середине ХХ столетия в свя зи с изучением свойств конечных автоматов. Исторически наиболее рано начала развиваться теория комбинационного синтеза релейно-контактных схем с использованием булевой алгебры [25;

125–126].

В период появления электронных цифровых машин эта теория пополнилась теорией структурного и блочного синтеза автоматов. Возникновению абстрактной теории автоматов бы ло положено в работах Клини и Мура. В работах Неймана бы ло положено начало теории синтеза надежных схем из нена дежных элементов.

В работах В.М. Глушкова и его школы была решена зада ча сопряжения этапов абстрактного и структурного синтеза и представление всей структурной теории автоматов в виде, пригодном для решения проблем синтеза цифровых автоматов с запоминающими двоичными элементами любой природы.

Эта единая математическая теория цифровых автоматов была доведена до практического применения при разработке авто матизированной системы логического проектирования дис кретных устройств [27]. В основу этой теории были положены автоматы Мили (автоматы 1-го рода) и Мура (автоматы 2-го рода) с памятью на двоичных триггерах [25].

В настоящее время вся теория автоматов делится на тео рию абстрактных и структурных автоматов Мили и Мура, функционирующие в дискретные моменты времени ti(i =1, 2, …,n,…).

Настоящая книга посвящена изложению существующей классической теории автоматов Мили и Мура с памятью на двоичных триггерах и функционирующих в дискретные мо менты времени ti, выявлению их ограничений. А также в книге предлагается более общая теория многофункциональных ав томатов 1-го и 2-го рода, частным случаем которой являются автоматы Мили и Мура [25;

66;

91], и теория автоматов 3-го рода, предложенная впервые доктором технических наук, профессором Л. Ф. Мараховским [31;

55;

60;

69;

86–87].

Вошедший в пособие материал неоднократно излагался автором, профессором Л. Ф. Мараховским и его учениками в ряде работ [55–60] и при чтении обязательного раздела по тео рии автоматов в курсе «Компьютерная схемотехника» [56].

Новизна этого материала изложена в ряде патентов [72;

77– 80].

В настоящее время широко используется теория построе ния реконфигурируемых систем, использующих память на триггерах, на «автоматном» уровне [97].

Расширенная Мараховским теория автоматов позволила создать теорию проектирования реконфигурируемых уст ройств с учетом «элементного» уровня с памятью на элемен тарных многофункциональных схемах [57–60].

ГЛАВА ПОНЯТИЯ АВТОМАТА:

ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ § 1.1. Алфавитный способ преобразования информа ции Философы и математики, заметив одинаковые законы раз вития разнообразных объектов, предложили общее понятие – сложная система. Система – это структурно организованный объект, в котором выделяются состояния, переходы, под структуры и взаимодействия частей. С появлением таких ис кусственных сложных систем, как электронных вычислитель ных машин для их проектирования с системных позиций ро дилась наука теория автоматов, которые воспринимают ин формацию, изменяя свои состояния, сохраняют эти состояния в памяти (если память присутствует в автомате) и могут выда вать информацию о состоянии автомата. Системный подход дает возможность анализировать многие сложные объекты, в том числе и реальные устройства вычислительной техники, с позиции единой общей методологии.

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

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

Существуют два различных подхода с информационной точки зрения: изучение явлений в непрерывном или дискрет ном времени. Характерным для непрерывного подхода явля ются вещественные числа, которые могут изменяться непре рывно. При дискретном подходе временные координаты при нимают дискретные ряды значений. Обычно нулевой момент времени считается начальным, а остальные моменты времени в соответствии с их номерами: 1, 2, …, n,… Чаще всего огра ничиваются рассмотрением конечных временных интервалов, начиная с нулевого или с первого момента времени.

Реальные устройства обладают рядом ограничений при приеме информации:

чувствительность воспринимающего устройства дает ему возможность различать лишь конечное число градаций значений величин, характеризующих процесс;

разрешающая способность устройства приводит к то му, что достаточно малые участки пространства восприни маются как отдельные точки;

полосы пропускания воспринимающего информацию устройства не позволяют ему различать очень близкие момен ты времени.

С точки зрения воспринимающего устройства можно ог раничиться дискретным временем, деля реальное непрерывное время на столь малые интервалы, чтобы концы этих интерва лов воспринимались объектом как один момент времени.

С учетом ограничений устройства, воспринимающего ин формацию, любая непрерывная информация сводится, факти чески, в дискретную информацию. Отсюда следует универ сальность алфавитного способа задания информации.

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

Абстрактным алфавитом называют любую конечную со вокупность объектов (букв) данного алфавита. Природа этих объектов в данном случае не существенна. Важно лишь то, чтобы рассматриваемый алфавит был конечным, то есть со стоял из конечного числа букв [5]. В абстрактном алфавите можно считать целые слова конкретного языка отдельными буквами, если это необходимо при удобстве преобразования информации.

Различие между словами алфавитов разговорных языков и словами абстрактного алфавита состоит в том, что слово в аб страктном алфавите может содержать и простое сочетание букв, которое в обычном языке не имеет аналогов и считается бессмысленным (например, сочетание букв «ккллммнн»). Ко личество букв в конкретном слове называют обычно длиною этого слова. Наряду со словами положительной длины (со стоящими не менее чем из одной буквы) в абстрактном алфа вите рассматривается также пустое слово, не содержащее ни одной буквы.

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

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

При рассмотрении цифровых автоматов Мараховского (многофункциональных автоматах 1-го, 2-го рода и автоматов 3-го рода) с памятью, которые в процессе функционирования под влиянием пустого слова е могут изменять структуру запо минания в схеме памяти, дискретное автоматное время не подходит. В этом случае вводиться непрерывное автоматное время, в котором слову е выделяется длина, как букве абст рактного алфавита [55].

Поскольку целью настоящей книги является изучение цифровых автоматов (дискретных преобразователей информа ции) с системных позиций, в дальнейшем под словом инфор мация всегда будем понимать, если специально не оговорено противное, информацию, заданную в дискретной алфавитной форме.

Рассмотрим понятие преобразование информации, которая представлена в алфавитной форме. С абстрактной точки зре ния преобразование информации есть отображение одного класса явлений в другой класс явлений в соответствии с опре деленным законом. Например, явление из некоторого класса А явлений влечет за собою некоторое определенное явление из того же самого или из другого класса явлений В, то говорят, что задано преобразование информации f( )1, = (1.1) где стрелка «» – знак преобразования информации, то есть отображение явления в явление.

Если подобное отображение осуществляется определен ным объектом, то такой объект называется преобразователем информации.

Алфавитным отображением (оператором) называется всякое соответствие (функция), сопоставляющее слово в том или ином алфавите слова в том же самом или в некотором другом фиксированном алфавите.

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

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

Под термином алфавитный оператор понимают одно значное, вообще говоря, частично определенное отображение множества слов во входном алфавите оператора в множество слов в его выходном алфавите. Чтобы входной и выходной алфавиты оператора совпадали, достаточно их объединить в один алфавит.

С каждым алфавитным оператором связывается интуитив ное представление о его сложности. Наиболее простыми яв ляются операторы, осуществляющие побуквенное отображе ние. В автоматах без памяти используется побуквенное ото бражение, в которых каждая буква х входного слова р заменя ется некоторой буквой у выходного оператора q, зависящей только от буквы х, но не от выбора входного слова р. Побук венное отображение определяется заданием соответствия меж ду буквами входного и выходного алфавита.

Большое значение имеет кодирующее отображение, кото рое называют просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а алфавита А некоторой конечной последовательности bi bi...bi в 1 2 k алфавите B, называемой кодом соответствующей буквы. Раз личным буквам алфавита А сопоставляются различные коды.

Кодирующее отображение должно быть обратимым, то есть взаимная однозначность соответствующего кодирующего ото бражения. Обратимость кодирования будет всегда выполнять ся, если соблюдаются следующие два условия:

1. коды различных букв исходного алфавита А различны;

2. код любой буквы алфавита А не может совпадать ни с каким из отрезков кодов других букв алфавита В.

С помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в стандартном двоичном алфавите, содержащим две цифры (буквы) 0 и 1. Двоичное кодирование должно соблю даться при выполнении следующего соотношения:

2m n, (1.2) где n – число различных букв исходного алфавита А;

m – количество цифр двоичного алфавита, необходимых для кодирования букв алфавита А.

Кодирование информации в двоичном алфавите неодно значно. Для любого исходного алфавита существует беско нечное множество таких преобразований. Такие преобразова ния называются двоичным кодированием исходной информа ции.

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

Это утверждение очень важно, потому что в реальных дискретных устройствах обычно значение сигнала разбивается на два типа: высокое давление – низкое давление, высокий по тенциал – низкий потенциал и т. д., которые условно прини маются в двоичном алфавите за 1 или 0.

Подводя итоги можно сказать, что алфавитный способ преобразования информации является универсальным для описания входных воздействий на произвольный автомат и получения выходных результатов этих воздействий, которые представляются в виде соответственно двух алфавитов (вход ного и выходного) или одного объединенного алфавита.

§ 1.2. Понятие об алгоритме Понятие алгоритма является одним из фундаментальных понятий современной математики. Известно, что слово алго ритм пришло из Персии. Предложил его автор книги c мате матики Abu Jafer Mohammed ibn Musa al Khowarizmi. Он оп ределил его как определенный специальный метод разреше ния поставленной проблемы.

Любое целенаправленное действие сложной системы свя зано с понятием алгоритма. Он определяет последователь ность действий объекта для достижения цели. Так первобыт ные люди придумывали алгоритмы охоты и изобретали алго ритмы первых кулинарных рецептов. Алгоритмы повседнев ной жизни человека отличаются неоднозначностью и рас плывчивостью выбора принятия решений, не всегда опти мальным исполнением. Это соответствует действию системы в ситуации с неполной информациею. Когда, как говорят, «кар тина» для человека ясна, то он старается действовать наиболее оптимальным или известным ему способом.

Человечество всегда искало способы описания найденных правил для решения своих задач в виде алгоритмов. Сохрани лись древние магические рецепты, математические тексты, книги боевого искусства, где описывались приемы действий в тех или иных ситуациях. Сохранились и переиздаются книги духовного содержания, такие как: Библия, Талмуд, Коран, где раскрываются расплывчатые алгоритмы духовного воспита ния человека.

Потребности человечества в обобщении многочисленных подходов к решению разнообразных задач привели к созда нию теории алгоритмов.

Понятие алгоритма является одним из фундаментальных понятий современной математики. В математической теории алгоритмов существует большое разнообразие определений алгоритма, которые ориентированы на различные способы вычислительной реализации: арифметическое исчисление предикатов (К. Гедель, 1931), -определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936 и А. Тьюринг, 1937), алго ритмы Маркова (А. А. Марков, 1951) и многих других видных ученых. Попытку описать общую теорию алгоритмов пред принял В. М. Глушков в книге «Теория алгоритмов» [5], в ко торой он с системных позиций описал абстрактную теорию алгоритмов и связал ее с ЭВМ, автоматами и самосовершенст вующимися системами.

В соответствии с дискретной точки зрения произвольное преобразование информации можно рассматривать как ото бражение (вообще говоря, частичное) множества слов в неко тором конечном алфавите в множество слов в том же самом или любом другом конечном алфавите. Такие отображения принято называть алфавитными операторами.

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

Алгоритмы могут быть однозначные, вероятностные, не четкие, самосовершенствующиеся и т. д.

Примером однозначного алгоритма может быть система правил сложения целых чисел в произвольной позиционной системе счисления (двоичной, восьмеричной, десятичной и т.

д.), которая состоит из правил поразрядного сложения и опре деления поразрядного переноса в старший разряд. Этот алго ритм сложения чисел С = А + В можно задать в формульном виде так:

a b, при ai bi q;

0, при ai bi q, сi i i pi 1 (1.3) ai bi q, при ai bi q, 1, при ai bi q.

де сі — цифра і-го розряду результату;

рі+1 — перенос в і+1 розряд;

q – основание системы счисления.

Этот алгоритм перерабатывает слова вида а+b в алфавите, состоящим из q цифр и знака сложения, в слова в том же ал фавите, но без знака сумы (+).

Примером вероятностного алгоритма могут быть различ ные игры (в кости, в шашки, в шахматы и т. д.). Применитель но к вероятностным алгоритмам выбор «лучшего» хода опре деляется не однозначно, а случайно, в соответствии с какими либо вероятностными критериями.

Игру в шахматы можно трактовать как преобразование слов в конечном алфавите. В качестве алфавита здесь приме няются символы шахматной нотации. Словами считают ко нечные последовательности букв алфавита. Одни последова тельности представляют собою шахматные позиции, а другие – бессмысленные наборы символов, как например, 3КЛad. Ал горитм задается лишь для слов, представляющих осмыслен ные позиции в позицию, возникающую из нее после выполне ния очередного хода. Опыт игры в шахматы показывает, что можно составить конечную систему стратегических правил, позволяющих в каждой конкретной ситуации выбрать единст венный наилучший (в некотором смысле) ход. Присоединяя эту систему стратегических правил к правилам движения фи гур, получаем алгоритм, который, несмотря на свою неодно значность, можно назвать алгоритмом шахматной игры. Раз работанный машинный алгоритм шахматной игры позволил ЭВМ выиграть у чемпиона мира Каспаров.

Нечеткие (размытые, расплывчатые или неопределенные) алгоритмы, допускающие использования нечетких инструк ций, широко распространены в различных сферах человечес кой деятельности, позволяют описывать приближенные рас суждения и, следовательно, являются полезным инструментом для приближенного анализа таких систем и процессов приня тия решений, которые слишком сложны для применения об щепринятых количественных методов [49;

127].

Интересными типами алгоритмов являются самосовер шенствующиеся (обучающие), которые обычно задаются в виде специальным образом организованной системы алго ритмов.

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

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

Одно из важнейших фундаментальных понятий теории алгоритмов является рекурсия. Под рекурсией в общем смысле понимают такой способ организации системы, при котором она в отдельные моменты своего развития, определяемые ее правилами, может создавать (вызывать) собственные измене ния копий, взаимодействовать с ними и включать их в свою структуру. Законы изменения копий при вызове также вклю чаются в правила системы и могут зависеть от многих пара метров: от состояния системы и других подсистем в момент вызова копии, от информационного наполнения заданных па раметров, от правил самой системы. Частным случаем являет ся чистая рекурсия, в которой отсутствуют изменения при вы зове копии. Существует многообразие вариантов поведений копий. Они могут существовать и развиваться параллельно с главной системой, исчезать после своего этапа функциониро вания, по-разному взаимодействовать между собой. Все опре деляется правилами системы. В теории алгоритмов доказано, что, используя рекурсию, можно из ограниченного количества функциональных единиц получить все многообразие вычис лительных функций.

При организации цикличных процессов используются ре курсивные выражения, которые описывают любой член по следовательности чисел. Таким примером могут быть числа Фибоначчи, где первые два члена равны 1, а остальные вы числяются с помощью формулы ai = ai-2 + ai-1. Такая формула называется рекурсивною. Входными данными для каждого последующего шага являются результаты предыдущего.

Структурная блок схема алгоритма определения ряду чи сел Фибоначчи, чтобы последнее число не превышало 100, представляет вычислительный рекурсивный процесс с неиз вестным числом повторений (рис. 1.1).

ПОЧАТОК A(1) = 1 : A(2) = 1 : I = так A(I) 100 КІНЕЦЬ ні A(I) = A(I - 2) + A(I - 1) A(I - 2) = A(I - 1) : A(I -1) =A(I) Рис. 1.1. Определение чисел Фибоначчи Многочисленные попытки уточнения понятия алгоритма привели к установлению способов точного задания произ вольных алгоритмов. В.М.Глушков приводит один из таких способов, принадлежащий А.А. Маркову [26].

Алгоритмы А.А. Маркова, называемые также нормаль ными алгоритмами, преобразуют слова, заданные в любом конечном алфавите А = А(а1, …, an), в слова в том же самом алфавите, причем, как правило, алгоритм оказывается опреде ленным лишь для части слов и задает, следовательно, частич ное отображение.

С достаточной убедительностью В.М. Глушков показал, что любой алгоритм эквивалентен некоторому нормальному алгоритму. Поэтому, не нарушая общности, говоря о произ вольном алгоритме, иметь в виду только нормальные алго ритмы.

Сложность и большой объем вычислений способствовали созданию специализированных вычислительных устройств.

Они прошли сложный путь развития. Среди них можно выде лить класс универсальных устройств обработки информации – это электронные вычислительные машины (ЭВМ). Проник новение ЭВМ в разные сферы практической деятельности людей значительно повлияло на эволюцию теории алгорит мов, на выбор новых направлений их использования. Появи лись новые направления разработки алгоритмов, такие, как:

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

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

В данной работе основное внимание будет уделяться цифровым автоматам (устройствам ЭВМ), которые функцио нируют в автоматном времени. Начиная с 40-х годов ХХ сто летия, вся цифровая вычислительная техника проектирова лась в целом с использованием классической теории автома тов Мили и Мура, память в которых использовалась в основ ном на триггерах (элементарных монофункциональных схе мах памяти). Все существующие машинные алгоритмы в той или другой мере использовали только один однозначный тип перехода в автоматах Мили и Мура – детерминированный пе реход за один машинный такт из одного состояния в другое, который зависел от предыдущего состояния автомата а и входного сигнала х в дискретный момент времени ti. Это об стоятельство определило последовательность работы машин ных алгоритмов. Для параллельных алгоритмов необходимо было использовать аналогичную дополнительную аппаратуру.

Примером может служить использования не менее двух со процессоров, ЭВМ и т. д.

С появлением автоматов Мараховского на схемах авто матной памяти [55;

56–60], возможности теории алгоритмов расширились в связи с качественно новыми дополнительными переходами в устройствах ЭВМ (hardware) [60]. Автоматная схема памяти, используя меньшее количество аппаратуры на одно запоминаемое состояние по сравнению с триггерами, в тоже время, оказалась в состоянии осуществлять качественно новые переходы в автоматах.

Автоматная схема памяти способна еще выполнять каче ственно новые переходы, такие как:

1. детерминированный переход за счет входного «пус того» сигнала е, то есть осуществлять переход за один машинный такт по двум переменным х и е;

2. вероятностный переход в одно из подмножеств ав томата, которые сохраняются под влиянием вход ных сигналов е;

3. нечеткий переход в одно из четких подмножеств ав томата, которое входит в нечеткое множество.

Появление возможности осуществлять качественно новые переходы в схемах памяти позволило Мараховскому Л.Ф. и его ученикам расширить теорию автоматов [55;

60]. Авторы надеются, что это обогатить в дальнейшем и теорию компью терных алгоритмов, и теорию построения устройств ЭВМ.

Подводя итоги можно сказать, что рассмотрение автома тов Мараховского, функционирование которых рассматрива ется в непрерывное автоматное время, расширяет теорию классических автоматов Мили и Мура и создает в ней новое направление, позволяющее описывать устройства на схемах автоматной памяти, а также создавать качественно новые вы числительные алгоритмы [55].

§ 1.3. Понятие о дискретном автомате Дискретными автоматами Мили и Мура называют уст ройства, которые преобразуют информацию в дискретные моменты времени, которые в математике отождествляются как точка на числовой оси ti (i = 0, 1, 2, …, n, …), а в реальном устройстве как такт t (рис. 1.2).

ti-1 ti ti+ Рис. 1.2, а. Точки на числовой оси Uв t акт t Такт машинный Рис. 1.2, б. Машинний такт Дискретную информацию считают алфавитной, заданной в том или другом алфавите. В современных дискретных авто матах принято отождествлять буквы используемого стандарт ного алфавита с цифрами той или одной системы счисления (чаще всего двоичной или десятичной). Поэтому дискретные автоматы принято называть цифровыми автоматами.

Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного (при этом в реальных устройствах все гда конечного) множества внутренних состояний и свойства скачкообразного перехода из одного состояния в другое во время такта t (рис. 1.2), который занимает не более двух-трех задержек э элемента. Скачкообразный переход означает воз можность трактовать его как мгновенный (на определенной степени абстракции), который совершается непосредственно, минуя какие-либо состояния. Такая абстракция, достаточно хорошо описывает основные свойства реальных цифровых автоматических устройств (прежде всего устройств ЭВМ и самих ЭВМ) и поэтому может быть принята для построения теории цифровых автоматов.

Второе допущение состоит в том, что переход в следую щее состояние оказывается возможным после переходного процесса в схемах памяти автомата, которые имеют разброс параметров, но для данного автомата составляет некоторый фиксированный промежуток времени, который обычно выби рается равным четырем задержкам э элемента. Такой интер вал дискретности автомата обычно выбирается как такт t ма шинного такта (рис. 1.2.). Такое допущение дает возможность рассматривать при функционировании цифрового автомата Мили или Мура в дискретное автоматное время ti (рис. 1.2, а). При построении такого дискретного автоматного времени различают два основных случая:

1. синхронные автоматы, в которых машинный такт определяется генератором синхронизирующих им пульсов, и, обычно, имеет одинаковые промежутки такта t, во время которого поступают входные сиг налы х(t) на входы автомата, и промежутка между тактами, на которые поступают пустые входные сло ва е, которые в работе автоматов Мили и Мура не принимаются во внимание, потому что не способны участвовать в переходах в памяти автоматов на триг герах;

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

Теория асинхронных автоматов существенно отличается от теории синхронных автоматов тем, что в ней рассматрива ются не только моменты фактически имевших место перехо дов, но также и такие переходы, которые в данный момент возможны, но не произошли. К числу таких моментов при числяют моменты прихода входных сигналов х(t) импульсно го типа (мгновенных) и изменения уровня напряжения сигна лов потенциального типа, действующих во временном интер вале такта t (рис. 1.2, б). При этом считают, что интервал дис кретности автомата ограничивает минимально возможное расстояние между дополнительно вводимыми моментами ав томатного времени. При таком допущении теория асинхрон ных автоматов в ряде случаев может быть сведена к синхрон ному случаю, поскольку фактически длины интервалов между последовательными моментами дискретного автоматного времени в идеализированной теории автоматов (без учета пе реходных процессов) не имеет никакого значения, так как на автомат в этот момент поступает пустое слово е нулевой дли ны. Имея в виду такое обстоятельство, в автоматах Мили и Мура рассматривается абстрактное дискретное автоматное время, принимающее целые неотрицательные значения: t = 0, 1, 2, …, n, …, и строится теория, как теория синхронных ав томатов, хотя в действительности она охватывает в значи тельной мере и теорию асинхронных автоматов.

Переходы из одного аi состояния автомата в другое ak вы зываются входными сигналами x(t), возникающими вне авто мата и передающимися в автомат по конечному числу вход ных каналов. В отношении входных сигналов х(t) цифровых автоматов принимаются два допущения: во-первых, для лю бого цифрового автомата число различных входных сигналов х(t) обязательно конечно, а, во-вторых, входные сигналы х(t) рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, опреде ляемым соответствующими им переходами. Особо следует подчеркнуть, что реальный физический входной сигнал, вы зывающий изменения состояния автомата в момент времени ti, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к моменту времени ti, а не ti-1.

Результатом работы цифрового автомата является выдача выходных сигналов у, передаваемых из автомата во внешние цепи по конечному числу выходных каналов. В отношении выходных сигналов у вводятся допущения, аналогичные тем, которые были сделаны для случая входных сигналов х. Во первых, для любого цифрового автомата число различных выходных сигналов у обязательно конечно, а, во-вторых, каж дому отличному от нуля моменту автоматного времени отно сится соответствующий ему выходной сигнал у.

В автоматах Мараховского вводится и используется авто матное непрерывное время, в котором кроме такта ti исполь зуется еще промежуток между тактами ti, интервал которого обозначим символом « ». Это объясняется тем, что в интер вале используется сохраняющий входной сигнал е( ), кото рый в автоматах Мили и Мура называется пустым словом ну левой длины и не учитывается в работе автоматов, а в автома тах Мараховского может использоваться для осуществления переходов в автоматной памяти автомата.

Рассмотрим автоматное непрерывное время с учетом син хронных сигналов j и дадим ряд определений.

Определение 1.1. Тактом t назовем промежуток времени, i на протяжении которого на автомат можно подавать произ вольный синхронизирующий сигнал i.

Определение 1.2. Внутренним тактом назовем мень j ший открытый промежуток времени между появлениями син хронизирующих сигналов i.

Определение 1.3. Внешним тактом T назовем меньший j открытый справа промежуток времени, который соответству ет периоду синхронизированного сигнала i.

Такты, что определены, можно выразить такой формулой:

T j t j j ;

j 0,1, 2,..., n,.... (1.4) Информационные входные сигналы х подаются на вход ные каналы сложного автомата и синхронизируются сигналом j. Эти входные сигналы воздействуют на автомат в автомат ное непрерывное время такта t.

j Определение 1.4. Внутренним единичным тактом 0 авто матного непрерывного времени назовем меньший открытый промежуток времени между появлением двух произвольных и последовательных синхронизированных сигналов р и р + 1.

Определение 1.5. Внешним единичным тактом Т0 назвемо меньший открытый справа промежуток времени, который со ответствует периоду времени между появлением двух произ вольных и последовательных синхронизирующих сигналов р и р + 1.

. Внешний единичный такт Т0 в соответствии со временем равен сумме продолжительности такта t и внутреннего еди j ничного такту 0. Эта зависимость рассматривается таким ра венством:

Т0= t + 0. (1.5) j Продолжительность внешнего такта T равна продолжи j тельности внешнего такта Та автомата. За один внешний такт Та на автомат воздействуют все синхронизирующие сигналы j по одному разу.

Определение 1.6. Внешним тактом Та автомата назовем меньший открытый справа промежуток времени, который со ответствует периоду воздействия всех синхронизирующих сигналов j (j = 1, 2,…, C) на входных каналах автомата.

Автомат, что описывает реальное устройство ЭВМ, может удовлетворять простейшим требованиям надежности и ста бильности состояний аі и выходных сигналов уі.

Необходимо учитывать, что на входные каналы элемен тарных автоматов поступают сигналы определенной продол жительности j.

Под влиянием входного сигнала х во время такта t эле j ментарный автомат с памятью может переходить в опреде ленное состояние при реализации однозначного переходу.

Под воздействием входного сигнала е во время внутреннего единичного такта 0 элементарный многофункциональный автомат с памятью может переходить в новое состояние при реализации функции укрупненного или вероятностного пере хода.

Новое установленное состояние элементарного автомата может сохраняться после окончания такта t при однознач j ном переходе или после внутреннего единичного такта 0 при реализации функций укрупненного или вероятностного пере хода.

Временные соотношения синхронизирующих и входных сигналов иллюстрирует рис. 1.3.

U t e1() х1(t) U t t t1 Т Т Рис. 1.3. Временные соотношения синхронизирующих и входных сигналов Выходной сигнал уj элементарного автомата фиксирует новое устойчивое состояние в автомате и сохраняет неизмен ным свое состояние на всем временном отрезке T. Отрезок j T j определяется в соответствии с такой формулою:

T j = – 0. (1.6) j Внешний такт Та автомата своею продолжительностью равный сумме внешних единичных тактов Т0:

C (T Ta ) j. (1.7) j Автоматное непрерывное время дает более полную воз можность исследовать закон функционирования не только ав томатов Мили и Мура, реализованных на триггерах, на про тяжении дискретного автоматного времени tі. Однако, иссле довать многофункциональные 1-го и 2-го рода автоматы Ма раховского, реализованные на схемах автоматной памяти, на протяжении внутреннего такта і, можно только в автоматное непрерывное время. Рассмотрение автоматного непрерывного времени помогает более полному исследованию законов функционирования автомата на абстрактном уровне [9–13].


В автоматах Мили, рассматриваемых в автоматном дис кретном времени, выходной сигнал у(t) определяется парой (х(t), а(t-1)), а сам автомат называется автоматом первого рода.

В автоматах Мура, рассматриваемых в автоматном дис кретном времени, выходной сигнал у(t) определяется только состоянием автомата а(t), а сам автомат называется автома том второго рода.

В автоматах Мараховского, реализованных на схемах ав томатной памяти и рассматриваемых в автоматном непрерыв ном времени, выходной сигнал исследуется как для много функционального автомата 1-го и 2-го рода с использование входных сигналов х(t) и е(). Автоматы Мараховского явля ются более общим типом цифровых автоматом, а автоматы Мили и Мура являются их частным случаем. Кроме этого в автоматах Мараховского рассматривается и автомат 3-го рода, который дополняет теорию автоматов 1-го и 2-го рода.

Схемы автоматной памяти представляют собою матрицу запоминаемых состояний [60], состоящую из блоков j, пред ставляющих строки матрицы, в которых сохраняются под множества определенных состояний автоматной схемы памя ти под влиянием входного сигнала е(), и блоков µі, пред ставляющие столбцы матрицы с определенными подмножест вами состояний автоматной схемы памяти, устанавливаемых входным сигналом х(t).

Обратим внимание, что в триггерах сохраняется только одно подмножество состояний автомата, которое сохраняется под воздействием только одного сохраняющего входного сиг нала е(), которое в работе автоматов Мили и Мура не учи тывается, и, как говорилось ранее, называется пустым словом нулевой длины [26].

В детерминированных автоматах Мараховского дополни тельно рассматривается функция сохранения состояний а(Т), которая определяется парой (а(t), е()). Входной сигнал е() сохраняет состояние а(t) автоматов 1-го и 2-го рода после его установки на всем протяжении машинного такта Т в опреде ленном подмножестве j (рис.1.3). Функции переходов из од ного состояния а(-1) в другое состояние а(t) определяется парой (а(-1), х(t)), а сохранение состояния во время проме жутка определяется парой (а(t), е()).

В автоматах 3-го рода функция укрупненного перехода из состояния а(t) в состояние а() осуществляется под воздейст вием входного сигнала е() в определенном подмножестве µi и определяется парою (а(t), е()).

Выходные сигналы у определяют тип рода автомата. Вы ходной сигнал у1 автомата первого рода определяется парой (а(-1), х(t)), выходной сигнал у2 автомата второго рода оп ределяется парой (а(t), а()), а выходной сигнал у3 автомата третьего рода определяется парой (а(t), е()).

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

Абстрактная теория автоматов, таким образом, близка к теории алгоритмов, являясь по существу ее дальнейшей де тализацией.

Структурная теория автоматов, прежде всего, интере суется структурой, как самого автомата, так и его входных и выходных сигналов. В структурной теории рассматриваются, прежде всего, способы построения автоматов из элементар ных автоматов, способы кодирования входных и выходных сигналов элементарными сигналами, передаваемыми по ре альным входным и выходным каналам и т. п.

Таким образом, структурная теория автоматов является продолжением и дальнейшим развитием абстрактной теории.

В частности задача идеализированного (без учета переходных процессов) цифрового автомата естественным образом под разделяется на этапы абстрактного и структурного синтеза.

Частным случаем дискретных автоматов являются авто маты, обладающие одним внутренним состоянием, которые называют комбинационными схемами или автоматами без памяти. Работа таких автоматов состоит в том, что они со поставляют каждому входному сигналу х(t) выходной сигнал у(t).

Основная идея методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основ ные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза к задаче синтеза комбинационных схем Теории автоматов Мараховского, кроме детерминирован ных однозначных и укрупненных переходов, рассматривают ся вероятностные и нечеткие переходы.

Одним типом вероятностных переходов определяют пе реходы из вполне определенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Р1 под влиянием пары (хр(t).

ek()), в которой входной сигнал хр(t) устанавливает в схеме памяти не запоминаемое состояние ар(t) ни при одном вход ном сигнале e(). Другим типом вероятностных переходов определяют переходы из вполне определенного состояния ав томата а(-1) подмножества i в состояние а() подмножест ва k (i k) под влиянием пары (х (t). ев()), в которой вход ной сигнал ев() с определенной вероятностью Р2 определяет подмножество сохраняемых состояний k. Вероятностный пе реход второго типа возможен при рассмотрении трех уровней автоматной схемы памяти в цифровом автомате.

Нечеткие переходы в нечеткие подмножества Qн, состоя щие из определенного числа четких подмножеств i, опреде ляют переходы из вполне определенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Рн под влиянием пары (хр(t).

ев()).

Вероятностные и нечеткие переходы являются расплыв чатыми и в большой степени зависят от физических свойств реальных автоматов.

Теория классических автоматов Мили и Мура, которая развивалась более 50 лет и является законченной разработкой, внедрена на сегодняшний день почти во все автоматические дискретные устройства современных ЭВМ. Теория же авто матов Мараховского внедрена только при разработках экспе риментальных устройств. В связи с этим авторы решили по знакомить начинающих специалистов в начале с классиче ской теорией автоматов Мили и Мура, а потом более опытных специалистов по теории автоматов Мили и Мура с более об щей теорией многофункциональных автоматов Мараховского, которая возможно найдет свое достойное применение при разработках перспективных и конкурентоспособных цифро вых устройств.

ГЛАВА АБСТРАКТНАЯ ТЕОРИЯ АВТОМАТОВ § 2.1. Понятие об абстрактном автомате Объектом изучения в абстрактной теории автоматов с точ ки зрения системного подхода вплоть до 90-х годов ХХ столе тия являлись абстрактные автоматы Мили и Мура, функцио нирующие в дискретном автоматном времени. В последующие годы, в связи с бурным развитием больших интегральных схем, которые представляют собою целые функциональные блоки ЭВМ (процессоры, оперативную память и т. д.), интерес к теории автоматов упал, хотя все они реализуются автомата ми Мили и Мура. Даже некоторыми ученными в конце ХХ века высказывалась мысль, что теория автоматов себя изжила.

Однако, это совсем не так! Лучшим подтверждением явля ется создание теории многофункциональных автоматов (в том числе и автоматов Мараховского), которые дали толчок для развития новых направлений в таких областях вычислитель ной техники, как:

1. теории построения схем автоматной памяти, которая в состоянии изменять свои состояния по двум пере менным с реконфигурацией структуры запоминания состояний;

2. теории построения многоуровневых схем памяти, ко торые в состоянии обрабатывать одновременно об щую информацию (в автомате стратегии) и частную информацию (в схемах автоматной памяти) без пред варительной обработки;

3. построение ЭВМ на предложенных схемах памяти, способных реконфигурировать структуру обработки информации и одновременно обрабатывать частную и общую информацию без предварительной обработ ки.

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

В начале абстрактной теории автоматов рассмотрим поня тие об абстрактном автомате Мили, Мура и Мараховского.

§ 2.2. Понятие об абстрактных автоматах Мили и Мура В теории абстрактных автоматов часто отвлекаются от его структуры. Понятие абстрактного автомата в теории дискрет ных устройств воплотило в себе системный подход, при кото ром предмет или явление рассматриваются как нечто целост ное, и основной акцент в исследованиях делается на выявле нии многообразии связей и отношений с внешней средой. По нятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании систем, выходы которых зависят не только от состояния входов в дан ный момент, но и от некоторой предыстории, то есть от сигна лов, которые поступали на входы системы ранее и изменяли ее функционирование. Состояния, рассматриваемые в данный момент, и соответствуют некоторой памяти о прошлом, по зволяя устранять время как явную переменную и выразить выходной сигнал как функцию только с аргументами состоя ния и входного сигнала в данный отрезок времени.

С точки зрения последовательных монофункциональных автоматов Мили и Мура общая характеристика автомата дос таточно полно описана в работе [27], в которой комбинацион ные схемы названы формерами. Каноническая схема автома тов Мили и Мура или в общем случае последовательного С автомата представляет собой устройство, состоящее из взаи модействующих регистра на триггерах и комбинационных схем.

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


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

А = (Х, Y, ), (2.1) у которого:

Х – конечное множество входных сигналов;

Y – конечное множество выходных сигналов;

: Х Y – функция выходов, реализующая отображение Х на Y.

Комбинационные схемы иногда называют функциональ ными преобразователями и изображают следующим образом (рис. 2.1):

Х Y Рис. 2.1. Функциональные преобразователи Определение 2.1. Абстрактный автомат А Мили или Му ра задается как совокупность шести объектов:

А = (Х, Y, Q,,, а0), (2.2) где Х – конечное множество входных сигналов, называемых входным алфавитом;

Y – конечное множество выходных сигналов, называемых выходным алфавитом;

Q – произвольное множество, называемое множеством состояний автомата;

а0 – элемент из множества Q, называемым начальным состоянием автомата;

двух функций (а, х) и (а, х), задающих однозначные отображения множества пар (а, х), где а Q и хХ, в множества Q и Х.

Функция (а, х) называется функцией перехода автомата, а функция (а, х) – функцией выходов (для автомата Мили) или сдвинутой (а) функцией выходов (для автомата Мура).

Автомат, заданный функцией выходов, называется автома том первого рода;

автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.

Абстрактный автомат Мили или Мура функционирует в дискретном времени, принимая целые неотрицательные зна чения t = 0, 1, 2, …. В каждый момент времени t этого време ни он находится в определенном состоянии а(t) из множества Q состояний автомата, причем в в начальный момент времени t=0 автомат всегда находится в своем начальном состоянии а0, то есть а(0) = а0. В каждый момент времени t, отличный от на чального, автомат способен воспринимать входной сигнал х(t) – произвольную букву входного алфавита Х и выдавать соот ветствующий выходной сигнал у(t) – некоторую букву выход ного алфавита Y.

Процедура, устанавливающая соответствие между после довательностями входных, состояний и выходных сигналов, называют функционированием модели абстрактного автомата.

Автомат с начальным состоянием а0 называют инициаль ным абстрактным конечным автоматом.

Закон функционирования абстрактного автомата в случае автомата первого рода (автомата Мили) задается уравнениями в автоматном дискретном времени:

а(t) = (а(t – 1), х(t)), у(t) = (а(t – 1), х(t)), (t = 1, 2. …), (2.3) для автомата второго рода (автомата Мура), функционирую щего в автоматном дискретном времени, – уравнениями:

а(t) = (а(t – 1), х(t)), у(t) = (а(t)), (t = 1, 2. …), (2.4), а в случае объединенного С-автомата, в котором реализова лись функции выходов автоматов Мили и Мура – уравнения ми:

а(t) = (а(t – 1), х(t)), у1(t) = 1(а(t – 1), х(t)), у2(t) = 2(а(t)), (t = 1, 2. …), (2.5) Установлением закона функционирования заканчивается определение абстрактного автомата. Смысл понятия абстракт ного автомата состоит в реализации некоторого отображения множества слов входного алфавита в множество слов вы ходного алфавита. Отображение в автоматах Мили и Мура реализуется так: каждое слово р хi1, xi2,..., xik входного ал фавита Х = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предвари тельно в начальное состояние а0. Возникающая таким образом конечная последовательность входных сигналов, автомата А x(1) х,..., x(k ) x, на основании закона функционирования i1 ik автомата вызывает появление однозначно определенной ко нечной последовательности q= y(1), y(2), …, y(k) выходных сигналов. Эту последовательность называют выходным сло вом, соответствующим входному слову р. Допустимыми вход ными словами называются те и только те входные слова р, на которых с помощью функций и (описанным выше спосо бом) определяются соответствующие выходные слова q=(р).

Построенное указанным способом искомое отображение, а именно: q = (р), называют отображением, индуцирован ным абстрактным автоматом А.

Автомат называется конечным, если конечны все три оп ределяющие его множества Х, Y, Q. Автомат называется впол не определенным, если его функции переходов и выходов заданы на всех парах (а, х), и частичным автоматом – в про тивном случае.

По количеству выполняемых преобразований все множе ство автоматов Мили и Мура делятся на два класса: моно функциональные и многофункциональные.

Каноническая схема автомата Мили (рис. 2.2, а), автомата Мура (рис. 2.2, б) или С-автомата в обобщенном виде (рис. 2. 2, в) состоят из связанных между собою регистра и комбинацион ных схем.

Входные сигналы автомата Мили Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы а Входные сигналы автомата Мура Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы б Входные сигналы Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.2. Структурные схемы монофункциональных автоматов 1-го и 2-го рода Монофункциональный автомат имеет жесткую структуру и всегда реализует одно и то же преобразование {X} в {Y}.

Для такого автомата величина функциональности f равна (L=1).

§ 2.3. Понятие об многофункциональных абстрактных автоматах Мили и Мура С конца 60-х и начала 70-х годов ХХ века начались иссле дования последовательных многофункциональных логических устройств [5;

33–34;

88–89;

121]. Эти работы положили начало общей теории многофункциональных автоматов. В этих рабо тах использовались триггеры с коммутируемыми функциями входных и выходных сигналов, управляемые автоматами стра тегии (настройки). Вначале в автоматах стратегии обрабаты валась общая информация, которая потом своими выходными сигналами настраивала многофункциональный автомат на реализацию одного монофункционального автомата Мили, Мура или С-автомата, в которых обрабатывалась частная ин формация.

В общем случае автомат может характеризоваться не од ной парой функций и, а несколькими. Тогда он реализует при каждой i-ой настройке различные отображения i (не ме нее двух) автомата, которые определяются парой функций пе реходов (i) и выходов (i).

Определение 2.2. Абстрактный многофункциональный автомат А Мили или Мура задается как совокупность восьми объектов:

А = (Х, Y, Q,,, Q0, U, f), (2.6) где Х – конечное множество входных сигналов, называемых входным алфавитом;

Y – конечное множество выходных сигналов, называемых выходным алфавитом;

Q – произвольное множество, называемое множеством состояний автомата;

Q0 – множество из множества Q, называемым началь ным множеством состояний автомата (Q0Q);

– множество функций переходов (i)(а, х) и (а, х), за дающих однозначные отображения множества пар (а, х), где а Q и хХ, в множества Q и Х;

– множество функций выходов (i)(а, х), задающих од нозначные отображения множества пар (а, х), где аQ и хХ, в множества Q и Х;

U – множество настроек функций переходов и выходов (U={U, U});

f – функциональность автомата, которая описывается как: ( f i. :U U i i, i 1, L, L Q).

i i Некоторый i-й монофункциональный автомат Аі задается как шестикомпонентный кортеж или вектор:

Аі = (Хі, Yі, Qі, (і), (і), а(і)0), (2.7) в котором компоненты не отличаются от компонентов, опи санных в (2.2) Исходя из уравнений (2.3) и (2.4) функционирования мо нофункциональных автоматов 1-го и 2-го рода, получим урав нения законов функционирования детерминированных мно гофункциональных абстрактных автоматов таких же типов 1 го и 2-го рода.:

Для многофункциональных автоматов 1-го рода (автома тов Мили) задается уравнениями в автоматном дискретном времени:

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), 2.8) (t = 1, 2. …, i = 1, 2, …L), для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, – уравнениями:

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t), U(і)), (2.9), (t = 1, 2. …, i = 1, 2, …L), а, в случае, объединенного С-автомата, в котором реализова лись функции выходов автоматов Мили и Мура – уравнения ми:

а(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у1(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), у(і)(t) = (і)(а(і)(t), U(і)), (2.10) (t = 1, 2. …? i = 1, 2, …L), Смысл понятия многофункционального абстрактного ав томата состоит в реализации некоторого множества отображе ний i множества слов входного i-го алфавита в множество слов выходного i-го алфавита. Отображение i в автоматах Мили и Мура реализуется так: каждое слово рi хi1, xi2,..., xik входного i-го алфавита Хi = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, по дается на вход данного абстрактного автомата Аi из множества многофункционального автомата А, установленного предвари тельно в начальное состояние а(i)0. Возникающая таким обра зом конечная последовательность входных сигналов, автомата Аi x x(1), х(2),..., x(k ), на основании закона функционирова ik ния автомата вызывает появление однозначно определенной i-й конечной последовательности qi= y(1), y(2), …, y(k) выход ных сигналов. Эту последовательность называют выходным i м словом, соответствующим входному слову рi. Допустимыми входными словами называются те и только те входные слова рi, на которых с помощью функций (і) и (і) (описанным выше способом) определяются соответствующие выходные слова qi=(рi).

Каноническая схема многофункционального абстрактного автомата с настройкой функций переходов и выходов пред ставлена на рис. 2.3.

Монофункциональные и многофункциональные автоматы 1-го и 2-го рода и их объединение С-автомат [6;

8;

21–24], реа лизующие свою регистровую память на триггерах и функцио нирование которых рассматривается в автоматном дискретном времени, являются частным случаем автоматов Мараховского (многофункциональных автоматов 1-го и 2-го рода). Автоматы Мараховского реализуют свою регистровую память на схемах автоматной памяти и функционирование их рассматривается в автоматном непрерывном времени.

U Входные сигналы автомата Мили U Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы а U Входные сигналы автомата Мура U Комбинационная Комбинационная Регистр на схема 1 (КС1) схема 2 (КС2) вы триггерах входных сигналов ходных сигналов Выходные сигналы б Входные сигналы U U Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.3. Структурные схемы многофункциональных автоматов 1-го и 2-го рода с настройками § 2.4. Некоторые понятия об изменениях в функциони ровании и самоорганизации в автоматах При решении различных задач теории автоматов часто возникают дополнительные условия на рассматриваемые ав томаты, определяющие те или иные подклассы класса всех конечных автоматов [26]. Одним из таких условий является понятие многофункциональных автоматов совместно с авто матами настройки (автоматами стратегии).

При проникновении в структуру процессов самоизменения и самоорганизации делается целесообразным рассмотрение не отдельного автомата (алгоритмов), а системы автоматов (ал горитмов). В простейшем случае такая система состоит из двух автоматов (алгоритмов). Первый из этих двух является многофункциональным и называется рабочим автоматом (ал горитмом), осуществляет непосредственную переработку по даваемой на его вход частной информации. Второй может быть монофункциональным или тоже многофункциональным автоматом (алгоритмом). Он предназначенный для обработки общей информации, оценки функционирования рабочего ав томата (алгоритма), внесения соответствующих изменений в функционирование рабочего автомата и называется контроли рующим или обучающим, а иногда и автоматом стратегии.

В случае, когда рассматриваются автоматы Мили и Мура, то эти изменения вносятся в функции переходов и выходов рабо чего автомата (рис. 2.4).

Если контролирующий автомат первой ступени много функциональный, то над ним можно поместить контроли рующий автомат второй ступени, в задачу которого входит оценивать действия автомата первой ступени и вносить в него необходимые изменения. По аналогии можно вводить контро лирующие автоматы третьей, четвертой и какой-угодно более высокой ступени. Построенную подобным образом иерархия автоматов (алгоритмов) называют многоступенчатой или системой автоматов, применительно к понятиям самоизме нения, самоорганизации и самосовершенствования. Подобная многоступенчатая организация системы самосовершенствую щихся автоматов (алгоритмов) позволяет моделировать высо кие формы самосовершенствования и самоорганизации.

Входные сигналы автомата настройки Автомат Настройки U U U Входные сигналы U U Обобщенная Регистр на комбинационная триггерах схема Выходные сигналы в Рис. 2.4. Обобщенная структурная схема многофунк ционального автомата с автоматом настройкии При рассмотрении теории самоорганизующих систем (ав томатов, алгоритмов) весьма существенным являются понятия одномерной и многомерной случайной величины, значениями которых являются конечные упорядоченные наборы вещест венных чисел или, иначе говоря, вещественные векторы той или иной (конечной) размерности.

Различают непрерывные и дискретные случайные величи ны. Непрерывная случайная величина может принимать про извольные значения в той или иной области (открытом мно жестве) соответствующего векторного пространства. Сово купность возможных значений дискретной случайной величи ны могут служить лишь дискретные множества точек, каждая точка которого может быть заключена в сферу, не содержа щую других точек того же самого множества. Свойство слу чайности, рассматриваемых величин, распространяется и при испытаниях. В каждом испытании случайная величина при нимает значение из области ее определения.

Области определения дискретных случайных величин мо гут быть конечными либо счетными бесконечными. В обоих случаях выполняется условие нормировки:

f ( xi )1, (2.11) i где суммирование предполагается распространенным на всю область определения данной случайной величины [27].

§ 2.5. Некоторые модификации абстрактных конечных автоматов Содержательная модель абстрактного конечного автомата основывается на ряде предположений относительно работы исследуемого реального устройства. Обобщая некоторые из этих предположений, получаем различные модификации по нятия абстрактного автомата: асинхронного, вероятностного, нечеткого и т. д.

Работа реального устройства, которое исследуется в моде лях автоматов Мили и Мура, наблюдается лишь в выделенные моменты времени t1, t2, …. Причем изменения, происходящие с устройством между наблюдаемыми моментами, с точностью до несущественных деталей, определяются информацией, по лучаемой в моменты t1, t2, …. Одно из возможных обобщений этого допущения заключается в рассмотрении двух независи мых последовательностей времени t1, t2, …и 1, 2, …, таких, что в моменты t1, t2, …наблюдаются поступающие на входные узлы внешние сигналы, а в моменты 1, 2, … – наблюдаются выходные сигналы устройства. При этом предполагается, что устройство имеет функцию перехода, которая однозначно оп ределяются по входному сигналу и состоянию устройства и описываемую уравнением (2.3) во времена t1, t2, …. Выходные сигналы устройства определяются во времени 1, 2, …, кото рые определятся соотношениями: tn s s+1…s+l tn+1, и однозначно определяются по входному сигналу и состоянию устройства в момент времени tn.

Возникающая в результате модель представляет собою со держательную модель абстрактного конечного асинхронного автомата.

Абстрактный конечный асинхронный автомат определяет ся как автоматы Мили и Мура, но без начального состояния.

Асинхронные автоматы реализуют преобразования слов их входного алфавита Х* в выходной алфавит Y*, при которых длина слова может изменяться, а также быть пустыми. В част ности, асинхронный автомат может заменять каждый символ а(i) слова p = а(1), а(2)… а(m) на кодирующий этот символ слово в алфавите Y* и выполнять ряд других преобразований слов, встречающихся в теории кодирования.

Успехи развития теории алгоритмов и теории детермини рованных автоматов поставили на повестку дня задачу выяв ления новых принципиальных возможностей, которые таит в себе использование случайных актов в процессе дискретной обработки информации. Смысл теории вероятностных автома тов состоит в получении позитивного значения случайности в дискретных преобразователях информации. Вероятностный автомат по существу появляется только тогда, когда вероятно сти не постулируются вычислимыми. Вероятностный автомат определен как неконструктивный элемент из-за предположе ния об отсутствии вычислимости вероятностных переходов, кроме специального случая, когда рассматривается рацио нальный вероятностный автомат[13].

Рассматривается еще одна модификация конечного авто мата – нечеткие автоматы. Теория нечетких подмножеств наилучшим образом позволяет структурировать все то, что разделено не очень точными границами, например, мысль язык, восприятия людей. Заслуга Л.А. Заде состоит в введении понятия взвешенной принадлежности, которая дает понятие нечеткого (размытого) подмножества [40].

Нечеткие автоматы получаются в результате замены функций переходов и выходов нечеткими отношениями. Не четкое подмножество М задается функцией, отображающейся в отрезке [0, 1]. Таким образом, роль функции переходов и выходов в нечетком автомате осуществляют функции, ото бражающие множества Q X Q и Q X Y в отрезке [0, 1], где Q – множество состояний, X – входной алфавит, Y – выходной алфавит. Для нечетких автоматов естественно обобщаются основные понятия и задачи, характерные для не четких автоматов[19].

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

§ 2.6. Понятие об абстрактных многофункциональных автоматах Мараховского Функционирование абстрактных многофункциональных автоматов Мараховского, построенных на схемах автоматной памяти [57–58], рассматривается в автоматное непрерывное время (рис. 1.3).

Для более лучшего понимания использования автоматного непрерывного времени рассмотрим в нем работу последова тельных монофункциональных автоматов Мили и Мура.

Монофункциональный абстрактный автомат, включаю щий в виде компонентов пустое слово е и функцию е сохра нения состояний, описывается восьмикомпонентным векто ром:

А = (Х, Y, Q,,, е, a0, e), (2.12) у которого:

- компоненты Х, Y, Q,, и a0 имеют те же значения и тот же смысл, что и при описании вектора (2.2);

- е (е Х) – сохраняющий входной сигнал;

- е: Q е Q – функция сохранения состояния, реа лизующее отображение De Qe на Q, при котором произвольное состояние aі(aі Q) сохраняет свое зна чение.

Пустое слово е(), названное сохраняющим входным сиг налом, воздействует в автомате А на его входные узлы во вре мя отсутствия входных сигналов х(t), где хХ. При одновре менном воздействии входных сигналов х(t) и е(t) сигнал е(t) поглощается сигналом х(t):

х(t) е(t)= х(t) (2.13) Структуру восьмикомпонентного монофункционального абстрактного автомата А в обобщенном виде представлена на рис. 2.5.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.