WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:   || 2 | 3 | 4 | 5 |

«Л.Ф. МАРАХОВСКИЙ, Н.Л. МИХНО ОСНОВЫ ТЕОРИИ АВТОМАТОВ И СИНТЕЗА РЕКОНФИГУРИРУЕМЫХ КОМПЬЮТЕРНЫХ СИСТЕМ Киев КНЭУ 2010 УДК 519.95: 004.274 ББК 32.973 Автор: Л.Ф. Мараховский, Н. Л. Михно ...»

-- [ Страница 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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПОЧАТОК

Рис. 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).

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

Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного (при этом в реальных устройствах всегда конечного) множества внутренних состояний и свойства скачкообразного перехода из одного состояния в другое во время такта 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.

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

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

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

Информационные входные сигналы х подаются на входные каналы сложного автомата и синхронизируются сигналом j. Эти входные сигналы воздействуют на автомат в автоматное непрерывное время такта t.

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

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

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

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

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

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

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

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

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

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

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

Внешний такт Та автомата своею продолжительностью равный сумме внешних единичных тактов Т0:

Автоматное непрерывное время дает более полную возможность исследовать закон функционирования не только автоматов Мили и Мура, реализованных на триггерах, на протяжении дискретного автоматного времени 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 – конечное множество выходных сигналов;

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

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

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

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

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

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

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

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

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

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

Рис. 2.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 – множество из множества Q, называемым начальным множеством состояний автомата (Q0Q);

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

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

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

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

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

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

для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, – уравнениями:

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

у1(і)(t) = (і)(а(і)(t – 1), х(і)(t), U(і)), Смысл понятия многофункционального абстрактного автомата состоит в реализации некоторого множества отображений 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-го рода). Автоматы Мараховского реализуют свою регистровую память на схемах автоматной памяти и функционирование их рассматривается в автоматном непрерывном времени.

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

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

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

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

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

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

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

где суммирование предполагается распространенным на всю область определения данной случайной величины [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 имеют те же значения и тот же смысл, что и при описании вектора (2.2);

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

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

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

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

Рис. 2.5. Обобщенная структура автомата А В реальных устройствах на входные узлы поступает последовательная пара входных сигналов х(t) и е(), которые определяют элементарное входное слово р(Т) = х(t), е(). При использовании в качестве схем памяти триггеров, все состояния элементов памяти которых сохраняются только при одном сохраняющем е() входном сигнале. Этот сохраняющий е() входной сигнал не в состоянии изменить состояние автомата.

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

Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою подмножества µi( ( i Q) ) состояний автомата, а строки – подj i множества j ( j Q) состояний автомата (табл.. 2.1) Триггеры и многостабильные схемы памяти (МСП) можно представить как строку 0 автоматной матрицы (табл. 2.1) в связи с тем, что все его ai состояния сохраняются при одном сохраняющем е() входном сигнале в одном множестве всех его состояний. Эти схемы обладают полнотой функций переходов, когда из каждого ai состояния можно под воздействием определенного входного х(t) сигнала перейти в любое, наперед заданное, ai состояние схемы памяти; а также полнотой системы выходов, когда каждое ai состояние отождествляется с выходным уi сигналом, который отличный от всех других.

В схемах автоматной памяти [14] переходы в момент t под воздействием входных х(t) сигналов могут происходить из одного состояния в другое в определенном подмножестве i, а в моменты автоматного непрерывного времени Т под воздействием входного е() сигнала могут происходить переходы из одного состояния в другое в определенном подмножестве µi состояний автомата. Таким образом, в матричной схеме автоматной памяти возможны переходы по двум переменным х(t) и е() в автоматном непрерывном времени Т.

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

А = (Х, Е, YI, YII, YIII, Q,, e0, a0, o, e, y, 1, 2, 3), (2.14) у которого:

Х = {x0, x1,…, xN-1} – множество информационных входных сигналов (входной информационный алфавит);

Е = {е0, е0,…, еR-1} – множество сохраняющих входных сигналов (входной сохраняющий алфавит);

YI = { Y01, Y11,...,YK1 1 } – множество выходных сигналов типа 1( выходной алфавит типа 1):

YII = { Y02, Y12,...,YK2 1 } – множество выходных сигналов типа 2 ( выходной алфавит типа 2);

YIII = { Y03, Y13,...,YK3 1 } – множество выходных сигналов типа 3 ( выходной алфавит типа 3);

Q = {a0, a1,…, am1} – произвольное множество состояний (алфавит состояний);

= { 0, 1,…, R-1} –множество блоков j состояний (алфавит блоков состояний);

е0Е –начальный сохраняющий входной сигнал;

a0 0 ( j Q) – начальное состояние автомата;

o: Q X Q – однозначная функция переходов, реализующая отображение D Q X в Q. Другими словами, функция o: некоторым парам „состояние – информационный входной сигнал” (а(-1), х(t)) ставит в соответствие состояние автомата а(t)= o(а(-1), х(t)), где а e: функция сохранения состояний блока j при а j, реализующая отображение D Q e j в j. Другими словами, функция е: некоторым парам „состояние – сохраняющий входной сигнал” (а(t), е()) ставит в соответствие состояние автомата а()= е(а(t), е()), где а y: Q E j – функция укрупненных переходов, реализующая отображение D Q e j в j. Другими словаy ми, функция у некоторым парам „состояние – сохраняющий входной сигнал” (а(t), е()) ставит в соответствие состояние автомата а()= у(а(t), е()), где а(t) p, а() j, а(t) а() (а(t), а() Q);

1: Q X YI – функция выходов типа 1, реализующая отображение D Q X в YI. Другими словами, функция 1: некоторым парам „состояние – информационный входной сигнал” (а(-1), х(t)) ставит в соответствие выходной сигнал автомата у(t)= 1(а(-1), х(t)), где у YI;

2: Q YII – функция выходов типа 2, реализующая отображение D Q в YII. Другими словами, функция 2:

некоторым парам „состояние – состояние” (а(t), а()), которые равны друг другу а(t)= а(), ставит в соответствие выходной сигнал автомата у(Т)= 2(а(t), а()), где у 3: Q E YIII – функция выходов типа 3, реализующая отображение D Q Е в YIII. Другими словами, функция 3: некоторым парам „состояние – сохраняющий входной сигнал” (а(), е()) ставит в соответствие выходной сигнал автомата у()= 3(а(), е()), где у YIII;

Абстрактные автоматы М представляют собою объединение автоматов 1-го, 2-го и 3-го рода, функционируют в автоматное непрерывное время Тi, которое состоит из двух отрезков ti и i (Тi= ti+i), описанных ранее.

В каждый момент i автомат способен воспринимать входной е() сохраняющий сигнал – произвольную букву входного сохраняющего алфавита Е и находится в определенном состоянии а() подмножества j из множества Q (j Q) состояний автомата, причем в начальный момент времени = автомат всегда находится в своем начальном состоянии а0, то есть а(0)=а0.

В каждый момент ti автомат 1-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), которое принадлежит определенному подмножеству состояний j, сохраняющегося при входном сигнале еj() и входящего в множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у(t) – некоторую букву выходного алфавита YI.

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

В каждый момент ti автомат 2-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), которое принадлежит определенному подмножеству состояний j, сохраняющегося при входном сигнале еj() и входящего в множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у(t) – некоторую букву выходного алфавита YII.

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

В каждый момент ti автомат 3-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое состояние а(t), а также способен воспринимать сохраняющийся входной сигнал еj()– произвольную букву входного сохраняющего алфавита Е и осуществлять в каждый момент i переход в новое состояние а() входящего в подмножество µi множество состояний Q (µi Q), а также выдавать соответствующий выходной сигнал у(t) – некоторую букву выходного алфавита YIII.

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

Установлением законов функционирования абстрактных автоматов 1-го, 2-го и 3-го рода обобщенного абстрактного автомата М заканчивается определение абстрактного автомата.

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

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

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

Каждое элементарное входное слово р (р=х, е), последовательно подается на вход данного абстрактного автомата М, установленного предварительно в начальное состояние. В момент такта t под воздействием входной х(t) буквы входного информационного алфавита Х автомат М способен перейти в новое состояние подмножества состояний j, сохраняющегося при входной букве еj() входного сохраняющего алфавита Е автомат М, и входящего в множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у(Т) – некоторую букву выходного алфавита YII.

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

Каждое элементарное входное слово р (р=х, е), последовательно подается на вход данного абстрактного автомата М, установленного предварительно в начальное состояние. В момент такта t под воздействием входной х(t) буквы входного информационного алфавита Х автомат М способен перейти в новое состояние подмножества состояний j, сохраняющегося при входной букве еj() входного сохраняющего алфавита Е автомат М, и входящего в множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у(Т) – некоторую букву выходного алфавита YIII.

Возникающие таким образом конечные последовательности входных элементарных слов р(Т) = х(t), е() на основании законов функционирования автомата в автоматном непрерывном времени Т вызывает соответственно определенные конечные последовательности qi= i(p) выходных букв из соответствующих входных алфавитов YI, YII, YIII. Эту последовательность qi называют выходным словом автомата 1-го, 2-го или 3го рода обобщенного автомата М.

Таким образом, отнесся каждой последовательности входных элементарных слов р соответствующую ему последовательность выходного слова qi, получаем искомое отображение i, которое называют отображением, индуцированным абстрактным автоматом М, который в состоянии работать как автомат 1-го, 2-го и 3-го рода.

Абстрактный М-автомат А, который описывается вектором (2.14), имеет два входа Х и Е та три виходи Y1, Y2, Y (рис. 2.6). Функционирование автомата исследуется в автоматном непрерывном времени Т [11–12].

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

Примером использования линии задержки в схемах памяти могут быть двухступенчатые регистры на САП. Каждая ступень в регистре тактируются синхроимпульсами i (i=1, 2) только одной серии, или отдельные группы САП, каждая из которых имеет информационные х(t) входные сигналы, которые тактируются синхроимпульсами i (i=1, 2) только одной серии. При использовании нескольких групп САП для создания обратных связей можно использовать выходные сигналы других групп, которые в данный момент t имеют устойчивые выходные сигналы.



Pages:   || 2 | 3 | 4 | 5 |
 
Похожие работы:

«В.Н. КРАСНОВ КРОСС КАНТРИ: СПОРТИВНАЯ ПОДГОТОВКА ВЕЛОСИПЕДИСТОВ Москва • Теория и практика физической культуры и спорта • 2006 УДК 796.61 К78 Рецензенты: д р пед. наук, профессор О. А. Маркиянов; д р пед. наук, профессор А. И. Пьянзин; заслуженный тренер СССР, заслуженный мастер спорта А. М. Гусятников. Научный редактор: д р пед. наук, профессор Г. Л. Драндров Краснов В.Н. К78. Кросс кантри: спортивная подготовка велосипеди стов. [Текст]: Монография / В.Н. Краснов. – М.: Научно издательский...»

«Ж. Ван Мигем ЭН ЕРГЕТИКА АТМОСФЕРЫ Перевод с английского под редакцией и с предисловием Л. Т. МАТВЕЕВА Ленинградский Гидрометеорологический ин-т БИБЛИОТЕКА Л-К 195196 Малоохтинский пр., SS | ГИДРОМЕТЕОИЗДАТ ЛЕНИНГРАД 1977 УДК 551_.5,1 Перевод с английского Ю. JI. Матвеева В монографии последовательно излагаются основы и современное состояние одного из наиболее важных разделов динамики атмосферы — учения об источниках и преобразовании энергии атмосферных процессов. В первой части монографии...»

«Б.Д. Цыбенов ИСТОРИЯ И КУЛЬТУРА ДАУРОВ КИТАЯ Историко-этнографические очерки Улан-Удэ 2012 Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Восточно-Сибирский государственный университет технологий и управления (ФГБОУ ВПО ВСГУТУ) Б.Д. Цыбенов ИСТОРИЯ И КУЛЬТУРА ДАУРОВ КИТАЯ Историко-этнографические очерки Улан-Удэ Издательство ВСГУТУ 2012 1 УДК 39 (518) ББК 65.5 (5 Кит) Ц Утверждено к...»

«А.В. Дементьев К О Н Т Р АК ТНА Я Л О Г ИС ТИ К А А. В. Дементьев КОНТРАКТНАЯ ЛОГИСТИКА Санкт-Петербург 2013 УДК 334 ББК 65.290 Д 30 СОДЕРЖАНИЕ Рецензенты: Н. Г. Плетнева — доктор экономических наук, профессор, профессор Введение................................................................... 4 кафедры логистики и организации перевозок ФГБОУ ВПО СанктПетербургский государственный экономический университет; Потребность в...»

«Ю. В. КУЛИКОВА ГАЛЛЬСКАЯ ИМП Е Р И Я ОТ ПОСТУМА ДО ТЕТРИКОВ Санкт-Петербург АЛЕТЕЙЯ 2012 У ДК 9 4 ( 3 7 ).0 7 ББК 6 3.3 (0 )3 2 К 90 Р ец ен зен ты : профессор, д.и.н. В.И.К узищ ин профессор, д.и.н. И.С.Ф илиппов Куликова Ю. В. К90 Галльская империя от П остума до Тетриков : м онография / Ю. В. Куликова. — С П б.: Алетейя, 2012. — 272 с. — (Серия Античная библиотека. И сследования). ISBN 978-5-91419-722-0 Монография посвящена одной из дискуссионных и почти не затронутой отечественной...»

«Балтийский государственный технический университет Военмех им. Д. Ф. Устинова УДК 530.16 + 536-34.3:[535.2/.4 + 535.521.3] + 536.7+ 536.8 ББК 22.317 Редакция от 13.06.2004 была депонирована в ВИНИТИ: 16.07.2004, № 1249 - B2004 В. В. Савуков Уточнение аксиоматических принципов статистической физики (теоретическое обоснование поискового проекта “Euler”) Copyright © 1986 – 2006. The project “Euler” by Vladimir V. Savukov. Настоящие материалы являются объектом авторского права, регламентируемого...»

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Рязанский государственный университет имени С.А. Есенина Н.В. Мартишина СТАНОВЛЕНИЕ И РАЗВИТИЕ ТВОРЧЕСКОГО ПОТЕНЦИАЛА ПЕДАГОГА В СИСТЕМЕ НЕПРЕРЫВНОГО ПЕДАГОГИЧЕСКОГО ОБРАЗОВАНИЯ Монография Рязань 2009 ББК 74.00 М29 Рецензенты: Л.К. Гребенкина, д-р пед. наук, проф., В.А. Беляева, д-р пед. наук, проф. Мартишина Н.В. М29 Становление и развитие творческого потенциала педагога в...»

«www.webbl.ru - электронная бесплатная библиотека РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт психологии ПРОБЛЕМА СУБЪЕКТА В ПСИХОЛОГИЧЕСКОЙ НАУКЕ Отв. ред.: А.В. Брушлинский М.И. Воловикова В.Н. Дружинин МОСКВА Издательство Академический Проект 2000, ББК 159.9 УДК 88 П78 Проблема субъекта в психологической науке. Отв ред член-корреспондент РАН, профессор А В Бруш-линский, канд психол наук М И Воловикова, профессор В Н Дружинин — М Издательство Академический проект, 2000 - 320 с ISBN 5-8291.0064-9 ISBN...»

«Министерство образования и науки Российской Федерации Казанский государственный технический университет им.А.Н.Туполева ООО Управляющая компания КЭР–Холдинг ТЕПЛООБМЕНА ИНТЕНСИФИКАЦИЯ ТЕПЛООБМЕНА И.А. ПОПОВ Х.М. МАХЯНОВ В.М. ГУРЕЕВ ФИЗИЧЕСКИЕ ОСНОВЫ И ПРОМЫШЛЕННОЕ ПРИМЕНЕНИЕ ПРОМЫШЛЕННОЕ ПРИМЕНЕНИЕ ТЕПЛООБМЕНА ИНТЕНСИФИКАЦИИ ТЕПЛООБМЕНА Под общей редакцией Ю.Ф.Гортышова Казань Центр инновационных технологий УДК 536. ББК 31. П Под общей редакцией проф. Ю.Ф.Гортышова Рецензенты: докт.техн.наук,...»

«УДК 882-1 ББК 84(2Рос-Рус)5 в 93 Редакционная коллегия : Н. В. Высоцкий,С. В. /'Кильцов,А. В. Максимов,В. Б. Назаров, Е. А. Трофимов Составление и комментарии П. Е. Фокина Подготовка текста. научное консультирование и текстологические комментарии С. В. /'Кильцова При составлении комментариев учтены воспоминания современников В. С. Высоцкого и наблюдения исследователей его творчества, зафиксированные в монографиях и научных публикациях, в частности в книгах: /'Кивая 1Кизнь. Штрихи к...»

«Е.М.Григорьева Ю.А.Тарасова ФИНАНСОВЫЕ ПРЕДПРИНИМАТЕЛЬСКИЕ СТРУКТУРЫ: ТРАНСФОРМАЦИЯ ПОД ВЛИЯНИЕМ РЫНОЧНОЙ КОНЪЮНКТУРЫ Монография Санкт-Петербург 2010 УДК 336 ББК 65 Ф 59 Рецензенты: д-р экон. наук, проф. Е.М.Рогова, заведующая кафедрой Финансовый менеджмент и финансовые рынки Санкт-Петербургского филиала ГУ-ВШЭ; к.э.н, доцент Козлова Ю.А., ГУАП. Григорьева Е. М., Тарасова Ю. А. Финансовые предпринимательские структуры: трансформация под влиянием рыночной конъюнктуры. Монография. – СПб.: ИД...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РФ ФГБОУ ВПО КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГАРНЫЙ УНИВЕРСИТЕТ В.А. Попов Н.В. Островский МЕТОДИКА ПОЛЕВЫХ МЕЛИОРАТИВНЫХ ОПЫТОВ В РИСОВОДСТВЕ Монография Краснодар 2012 1 УДК 631.6:001.891.55]:633.18 ББК 40.6 П 58 Рецензенты: А.Ч. Уджуху, доктор сельскохозяйственных наук (ГНУ Всероссийский научно-исследовательский институт риса); Т.И.Сафронова, доктор технических наук, профессор (Кубанский государственный аграрный университет) П 58 В.А. Попов Методика полевых...»

«О.С. СУБАНОВА Фонды целевых капиталов некоммерческих организаций: формирование, управление, использование Монография подготовлена по результатам исследования, выполненного за счёт бюджетных средств по Тематическому плану НИР Финуниверситета 2011 года Москва КУРС 2011 УДК 330.142.211 ББК 65.9(2Рос)-56 С89 Рецензенты: В.Н. Сумароков — д-р экон. наук, профессор, заслуженный работник высшей школы, исполнительный директор Фонда управления целевым капиталом Финансового университета при Правительстве...»

«Федеральное агентство по образованию ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ С. Э. Желаева В.Е. Сактоев Е.Д. Цыренова ИНСТИТУЦИОНАЛЬНЫЕ АСПЕКТЫ УСТОЙЧИВОГО РАЗВИТИЯ СОЦИОЭКОЛОГО-ЭКОНОМИЧЕСКИХ СИСТЕМ РАЗЛИЧНЫХ ТИПОВ Издательство ВСГТУ Улан-Удэ 2005 УДК 330.8:332.1(571.54) ББК 65.01(2Р-:Бу) Ж 50 Ответственный редактор д.э.н., профессор Цыренова Е.Д. Желаева С.Э., Сактоев В.Е., Цыренова Е.Д. Ж 50 Институциональные аспекты устойчивого развития социо-эколого-экономических...»

«Межрегиональные исследования в общественных науках Министерство образования и науки Российской Федерации ИНОЦЕНТР (Информация. Наука. Образование) Институт имени Кеннана Центра Вудро Вильсона (США) Корпорация Карнеги в Нью-Йорке (США) Фонд Джона Д. и Кэтрин Т. МакАртуров (США) Данное издание осуществлено в рамках программы Межрегиональные исследования в общественных науках, реализуемой совместно Министерством образования и науки РФ, ИНОЦЕНТРом (Информация. Наука. Образование) и Институтом имени...»

«Светлана Замлелова Трансгрессия мифа об Иуде Искариоте в XX-XXI вв. Москва – 2014 УДК 1:2 ББК 87:86.2 З-26 Рецензенты: В.С. Глаголев - д. филос. н., профессор; К.И. Никонов - д. филос. н., профессор. Замлелова С.Г. З-26 Приблизился предающий. : Трансгрессия мифа об Иуде Искариоте в XX-XXI вв. : моногр. / С.Г. Замлелова. – М., 2014. – 272 с. ISBN 978-5-4465-0327-8 Монография Замлеловой Светланы Георгиевны, посвящена философскому осмыслению трансгрессии христианского мифа об Иуде Искариоте в...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ им. В.П. Астафьева В.А. Мальцев Гуманистическая этика: ИСТОРИЯ И ПРОБлЕМЫ Монография Электронное издание КРАСНОЯРСК 2013 ББК 87.7 М 215 Рецензенты: А.И. Таюрский, академик РАО, председатель Сибирского отделения Российской академии образования; А.И. Шилов, доктор медицинских наук,...»

«ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ИМЕНИ М.Е. ЕВСЕВЬЕВА В.В. Будилов, П.В. Будилов Пространственно-временное распределение карабидофауны (Coleoptera, Carabidae) в агроценозах Среднего Поволжья МОНОГРАФИЯ САРАНСК МОРДОВСКОЕ КНИЖНОЕ ИЗДАТЕЛЬСТВО 2007 1 УДК 595.762.12:591.553(470.40/43) ББК 28.691 Ш 903 Рецензенты: И.Х.Шарова, докт. биолог. наук, Почетный профессор Московского педагогического государственного университета; Н.Б.Никитский, докт....»

«Министерство образования Российской Федерации Московский государственный университет леса И.С. Мелехов ЛЕСОВОДСТВО Учебник Издание второе, дополненное и исправленное Допущено Министерством образования Российской Федерации в качестве учеб­ ника для студентов высших учебных за­ ведений, обучающихся по специально­ сти Лесное хозяйство направления подготовки дипломированных специали­ стов Лесное хозяйство и ландшафтное строительство Издательство Московского государственного университета леса Москва...»

«Л. П. ДРОЗДОВСКАЯ Ю. В. РОЖКОВ МЕХАНИЗМ ИНФОРМАЦИОННО-ФИНАНСОВОЙ ИНТЕРМЕДИАЦИИ Хабаровск 2013 УДК 336.717:330.47 ББК 65.262.1 Д75 Дроздовская Л.П., Рожков Ю.В. Д75 Банковская сфера: механизм информационно-финансовой интермедиации: монография / под научной ред. проф. Ю.В. Рожкова. — Хабаровск : РИЦ ХГАЭП, 2013. — 320 с. Рецензенты: д-р экон. наук, профессор Богомолов С. М. (Саратов, СГСЭУ); д-р экон. наук, профессор Останин В.А. (Владивосток, ДВГУ) ISBN 978-5-7823-0588- В монографии...»






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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