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

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

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


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

Государственный экономико-технологический университет

транспорта

Кафедра «Автоматизация и компьютерно-интегрованные технологий

транспорта»

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

ОСНОВЫ ТЕОРИИ СИНТЕЗА

ЦИФРОВЫХ УСТРОЙСТВ

НА СХЕМАХ АВТОМАТНОЙ ПАМЯТИ

Монография

Киев 2014

УДК 004.274

ББК 32.973.2-02 М25 Мараховский Л. Ф. Основы теории синтеза цифровых устройств на схемах автоматной памяти : монография.

Л. Ф. Мараховский– К.: ГЭТУТ, 2014. – 278 с.

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

© Мараховский Л. Ф., © ГЭТУТ, СОДЕРЖАНИЕ Предисловие Список сокращений Введение ЧАСТЬ І. ОСНОВЫ ТЕОРИИ АВТОМАТОВ МАРА ХОВСКОГО 1. Особенности автоматов 1.1. Развитие теории автоматов 1.2. Понятия автомата: термины и определения 1.3. Понятие об алгоритме 1.4. Понятие о дискретном автомате Заключение 2. Абстрактная теория автоматов 2.1. Понятие об абстрактном автомате 2.2. Некоторые понятия об изменениях в функционировании и самоорганизации в автоматах 2.3. Некоторые модификации абстрактных конечных автоматов 2.4. Понятие об абстрактных многофункциональных автоматах Мараховского 2.5. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний 2.6. Понятие об абстрактных вероятностных автоматах 3-го ро- да 2.7. Понятие об абстрактных нечетких автоматах 3-го рода 2.8. Классификация детерминированных абстрактных автома- тов 2.9. Классификация недетерминированных абстрактных авто- матов 2.10 Понятие об автоматах четвертого рода, контролирующих работоспособность базовых схем памяти Заключение 3. Способы задания автоматов …. 3.1. Некоторые понятия в теории абстрактных автоматов. 3.2. Табличные способы задания многофункциональных абст- рактных детерминированных автоматов 3.3. Табличные способы задания абстрактных вероятностных автоматов 3-го рода 3.4. Табличный способ задания абстрактных нечетких автома- тов 3-го рода..

3.5. Графические способы задания переходов в многофункцио- нальных абстрактных автоматах 3.6. Математическая модель иерархического абстрактного ав- томата с многофункциональной системой организации памяти 3.7. Способ задания иерархического абстрактного автомата с многофункциональной системой организации памяти с помо- щью полиграммы 3.8. Формулирование полиграммы Заключение ЧАСТЬ 2. ОСНОВЫ ПОСТРОЕНИЯ СХЕМ АВТОМАТ НОЙ ПАМЯТИ Введение 4. Основные понятия элементарных схем памяти 4.1. Основы моделирование компьютерных схем 4.2. Элементарные схемы памяти 5. Структурная организация многофункциональных схем памяти 5.1. Многофункциональные элементарные автоматы с памя- тью. Основные понятия.

5.2. Метод микроструктурного синтеза элементарных МФСП 5.3. Символьный язык описания элементарных многофунк- циональных схем памяти 5.4. Исследование возможных вариантов многофункциональ- ных схем памяти в символьном числе 5.5. Синтез многофункциональных схем памяти по символь- ному описанию 5.6. Определение входных слов схем автоматной памяти 5.6.1. Определение однозначных элементарных входных слов 5.6.2. Определение укрупненных элементарных входных слов 5.6.3. Вопросы контроля работоспособности базовых схем памяти Заключение 6. Структурная организация многоуровневых схем памяти 6.1. Основные понятия 6.2. Разработка символьного языка описания многоуровневых схем памяти 6.3. Определение параметров многоуровневых схем памяти посимвольному описанию 6.4. Разработка метода синтеза многоуровневых схем памяти по символьному описанию 6.5. Разработка принципа структурной организации элемен- тарных многоуровневых схем памяти 6.6. Разработка метода проектирования общего автомата стра- тегии для всей многоуровневой схемы памяти 6.7. Метод логического проектирования многоуровневой схе- M L с одним автоматом стратегии мы памяти класса 6.8. Метод логического проектирования многоуровневой схе B мы памяти класса LN с автоматом стратегии для каждой группы многоуровневых схем памяти 6.9. Классификация базовых элементарных схем памяти Заключение ЧАСТЬ 3. СИСТЕМНЫЙ ПОДХОД К ПОСТРОЕНИЮ РЕКОНФИГУРИРУЕМЫХ КОМПЬЮТЕРНЫХ УСТ РОЙСТВ Введение 7.1. Развитие реконфигурированных систем с памятью на триггерах 7.2. Разработка методов построения реконфигурированных регистров на многоуровневых схемах памяти 7.3. Методы построения реконфигурированных счетчиков на многоуровневых схемах памяти 7.3.1. Основные понятия 7.3.2. Методы построения реконфигурировананых счетчи- ков на многоуровневых схемах памяти 7.4. Методы построения реконфигурированного устройства управления на многоуровневых схемах памяти 7.5. Методы построения реконфигурированных процессоров и компьютеров на схемах автоматной памяти 7.5.1. Введение 7.5.2. Методы построения реконфигурированной архитек- туры структуры процессоров на МФСП и МУСП 7.5.3. Исследование последовательной и параллельной об- работки иерархической информации в современных процессо рах 8. Способов задания иерархических автоматов на многоуров- невых схемах памяти 9. Принципы построения реконфигурированных процессоров и компьютеров, одновременно обрабатывающих общую и ча- стную информацию 10. Методы построения реконфигурированного компьютера с учетом «элементного» уровня.

11. Ускорения выполнения алгоритмов в реконфигурирован- ных компьютерных системах на многоуровневых схемах па мяти Заключение ЧАСТЬ 4. МОДЕЛЬ ЦИФРОВОГО ИСКУССТВЕННОГО НЕЙРОНА НА СХЕМАХ АВТОМАТНОЙ ПАМЯТИ.

Введение 12.1. Предварительные понятия о модели нейрона 12.2. Свойства человеческого мышления 12.3. Основы кратковременной памяти человеческого мозга 12.4. Проблемы создания модели человеческого мозга 12.5. Информационные характеристики нейрона человече- ского мозга 12.6. Принципы построения системы искусственного интеллекта 12.7. Методы проектирования модели искусственного ней- рона на схемах автоматной памяти 12.8. Структурная модель цифрового искусственного ней- рона Заключение ВЫВОДЫ Литература ПРЕДИСЛОВИЕ В последнее время многие ученые выражают обеспокоенность по поводу низкой информационной надежностью современных микро процессоров с памятью на триггерах, используемых в системах управ ления. Иногда достаточно сбоя одного электронного элемента в мик ропроцессоре, чтобы система начала выполнять ложную команду, ко торая может стать причиной аварии.

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

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

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

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

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

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

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

Автор будут благодарен за замечания данные читателями.

Контактные данные: Леонид Федорович Мараховский, д.т.н., профессор, основатель научной школы, член-корреспондент РАЕ, академик Междисципланорной академии наук: (044) 525-77-39, e-mail:

marachovsky@ukr.net, СПИСОК СОКРАЩЕНИЙ ВТ – вычислительная техника;

ИИ – искусственный интеллект;

МСП – многостабильная схема памяти;

МФСП – многофункциональные схемы памяти;

МУСП – многоуровневые схемы памяти;

ЭА – элементарный автомат;

x(t) – устанавливающий входной сигнал;

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

р (Т) – входное слово;

М – число устойчивых запоминаемых состояний схемы памяти;

rх – число устанавливающих x(t) входных сигналов в схеме памяти;

rе – число сохраняющих e() входных сигналов в схеме памяти;

Fp – предельная рабочая частота переключения;

РQ – нагрузочная способность по выходам;

Scв – число внутренних связей;

Sвc – число внешних связей;

L –·число элементов на одно состояние;

МЭА – многофункциональный элементарный автомат;

БА – базовый автомат;

у1(t) – выходной сигнал автомата 1-го рода;

у2(Т) – выходной сигнал автомата 2-го рода;

у3() – выходной сигнал автомата 3-го рода;

р0(Т) – однозначное входное слово;

ру(Т) – укрупненное входное слово;

СБИС – сверхбольшие интегральные схемы;

ЦИН – цифровой искусственный нейрон.

ВВЕДЕНИЕ Парадигма основы новой информационной технологии на схе мах автоматной памяти – новое междисциплинарное направление, объединяющее теорию автоматов, теорию построения схем памяти, принципы анализа базовых схем памяти при их катастрофических от казах, методы логического проектирования реконфигурируемых уст ройств компьютерной техники и принципы построения цифрового ис кусственного нейрона. Автор надеется, что основы новой информаци онной технологии на схемах автоматной памяти будут способствовать построению конкурентоспособных устройств. Она позволит расши рить функциональные возможности, повысить надежность и живу честь, позволит выявлению катастрофических отказов в базовых схе мах памяти реконфигурируемых устройств вычислительной техники (ВТ), реализованных с памятью на триггерах, с начала их промыш ленного использования [3–53;

86–95;

97–122;

124–138;

140–143].

Исторически работы по ВТ пошли сразу по двум направления [109]:

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

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

В 1981 году Япония предложила программу создания ЭВМ пято го поколения, которая позволила бы компьютерам частично владеть искусственным интеллектом (ИИ), т. е. самостоятельно составлять программы для решения конкретных задач, принимать самостоятель ные решения и т.д. [99]. В 1983 году в США была принята стратегиче ская компьютерная программа, предусматривающая опережение японских разработок по машинам пятого поколения. Соответствую щие программы были приняты в Англии, Франции, ФРГ, а также в странах членов СЭВ до 2000 года [109]. К сожалению и эти проекты не дали ожидаемых результатов по ИИ [100–102].

Формально, в 70-80 гг. прошлого века было окончательно уста новлено, что уровень развития вычислительной техники не позволяет говорить даже о возможности приближения к Искусственному Разу му. «Разумность» автоматических систем была снята с рассмотрения [101].

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

Рис.1. Динамика развития цифровых технологий Прогнозирование эволюционного развития цифровых микросхем и технологий с использованием математических формул, предложен ных В. И. Акуновым, продемонстрировало совпадение прогнозов с реальными достижениями в этой области: линейная зависимость (за кон Мура) по данным всемирно известной фирмы Интел (рис. 1) пере станет действовать к 2010 – 2015 г.г. [139].

В ноябре 2011 г. в Портленде (штат Орегон) Supercomputing Conferen-ce'09 фирма IBM заявила о существенном прогрессе в созда нии вычислительной системы, которая симулирует и эмулирует спо собность мозга чувствовать, воспринимать, действовать, взаимодейст вовать, познавать, и при этом сравнима с мозгом по низкому энерго потреблению и размерам.

Рис. 2. Суперкомпьютер BlueGene/Р, на котором симулировалась кора головного мозга BlueMatter – новый алгоритм, созданный IBM Research в сотруд ничестве со Стэнфордским университетом, использует суперкомпью терную архитектуру BlueGene/Р (рис. 2) для измерения и отображения связей между всеми локусами коры и подкорки в мозге человека с по мощью диффузной спектральной томографии [1–2;

96].

Специалисты компании IBM разработали передовой процессор, имитирующий работу человеческого мозга. «Это наше первое когнитивное компьютерное ядро, которое сочетает в себе вычисления в виде нейронов, память в виде синапсов, а связи - в виде аксонов», рассказал в интервью CNET руководитель исследования Дхармендра Модха.

«Биологический» процессор основывается на алгоритме BlueMatter, который был разработан 2009 г. при попытке выявить связь между корковыми и подкорковыми структурами головного мозга. Разработка этого алгоритма была необходима для того, чтобы понять, как этот орган обрабатывает и обменивается информацией, отметил Модха [1–2].

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

По мнению Модха, такие процессоры могут прийти на смену ар хитектуре фон Неймана, на которой построено большинство совре менных компьютеров. Когда появятся первые коммерческие прило жения для «биологических» чипов, Модха не сообщил. Как считает аналитик Рик Доэрти, глава Envisioneering Group, такие программы могут быть готовы к 2015 или 2016 году [1–2;

96].

Для создания подобных чипов в IBM объединили достижения в области нанотехнологий, нейробиологии и суперкомпьютеров. На чальный этап исследований в области нейросинаптических чипов профинансировало американское агентство передовых научных раз работок DARPA, выделив на проект 21 млн. долларов. Исследования велись в рамках научного проекта Systems of Neuromorphic Adaptive Plastic Scalable Electronics (SyNAPSE). Сейчас исследователи говорят, что созданные чипы пока способны анализировать данные, но не спо собны самоперестраиваться, а также память еще находится не в нейронах. Данные способности, как надеются исследователи, у них появятся в будущем.

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

Исследуя неудачи и трудности создания ИИ на современном этапе автор приходит к выводу, что фундаментальные исследования в области человеческого мозга, его нейрона еще не привели к созданию соот- ветствующей модели клетки нейрона, его модели связей, характеризующих реальный объект. В связи с этим и используются супер-компьютеры (рис.2), которые по внешним характеристикам создают пока только модель «действия кошки».

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

В данной монографии рассматривается фундаментальные основы реконфигурируемых устройств компьютеров, которые являються новым научным направлением, объединяющее теорию автоматов, схемы памяти, реконфигурируемые устройства компьютеров и искусственного нейрона на схемах автоматной памяти [54–55;

60–64;

66–68;

70–85].

Доктор технических наук, профессор Стахов А.П. пишет в статье [129], что недавно пришло сообщение об очередном аварийном запус ке космического аппарата связи «Меридиан». Считается, что потери от аварийного запуска этого космического аппарата могут составить до 2 млрд. рублей. До этого подобные аварийные запуски происходи ли и ранее (при запуске спутников «Глобалстар»). Одной из возмож ных причин такого «сбоя» могут быть «сбои» в цифровой системе управления двигателями. По странному совпадению, аварии начались после усовершенствования системы управления и ее переводе на циф ровую технику. И вот в этом, возможно, и «зарыта собака». Дело в том, что цифровые системы управления, основанные на современных микропроцессорах, обладают очень низкой информационной надеж ностью по сравнению с аналоговыми системами. Иногда достаточно сбоя одного электронного элемента (триггера) в микропроцессоре системы управления для того, чтобы система начала выполнять лож ную команду, что может стать причиной аварии. Сбой цифровой сис темы управления вызывается как внутренними, так и внешними фак торами. Сбой может возникнуть, например, в результате мощного внешнего электромагнитного воздействия на ракету-носитель в пери од запуска (электромагнитный терроризм).

На низкую информационную надежность современных микро процессоров (особенно иностранного производства) обращает внима ние выдающийся российский ученый академик Ярослав Хетагуров, который пишет, что применение микропроцессоров, контроллеров и программного обеспечения вычислительных средств (ВС) иностран ного производства для решения задач в системах реального времени (СРВ) военного, административного и финансового назначения таит в себе большие проблемы. Это своего рода «троянский конь», роль ко торого только стала проявляться. Потери и вред от их использования могут существенно повлиять на национальную безопасность России, Украины и многих других стран [137].

Стахов А.П. в своих работах [128–130], развивая мысли академи ка Хетагурова Я.А., сделал следующее, на первый взгляд парадок сальное утверждение: «Таким образом, человечество становится за ложником классической двоичной системы счисления, которая лежит в основе современных микропроцессоров и информационных техно логий. Поэтому дальнейшее развитие микропроцессорной техники и основанной на ней информационной технологии и классической дво ичной системы счисления следует признать тупиковым направлением.

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

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

На взгляд авторов, одной из проблем в создании нового класса перестраиваемых компьютеров и создания модели исскуственного нейрона лежит широко используемая двоичная память, которая представляет собой закрытую структуру, «нулевую» избыточность и обладает жестким алгоритмом работы, не надежна при работе компьютерных систем и, как пишут авторитетные ученые: Я.А. Хета гуров [137], А.П. Стахов [128–130], не способна к перестройки структуры своих запоминаемых состояний.

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

60;

64;

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

Часть І.

ОСНОВЫ ТЕОРИИ АВТОМАТОВ МАРАХОВСКОГО 1. Особенности автоматов 1.1. Развитие теории автоматов Теория конечных автоматов характеризуется широким использо ванием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе булевой алгебры и модели дискретного устройства в виде так называемого конечного ав томата. На ней основано развитие методов логического проектиро вания дискретных устройств и методов построения тестов для провер ки последних, обеспечение надежности и устойчивости их работы, решения задач «конструирования» дискретных устройств. Возникли отдельные ответвления теории конечных автоматов в виде теории ве роятностных и нечетких автоматов, коллективного поведения автома тов, экспериментов и т. д. [14;

18–21;

24–26;

34–35;

90;

119;

125;

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

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

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

Наши модели вначале нечеткие. Это наглядно видно на примере изучения счета ребенком с 2 до 5 лет [65]. Ему необходимо повторить от 6-ти до 10 раз, чтобы он мог вначале различать один палец от двух.

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

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

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

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

Только ответ на данный вопрос позволяет понять, что такое условие и в чем специфика его влияния [133].

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

15;

21;

36;

87;

93].

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

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

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

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

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

59;

64].

Этот материал неоднократно излагался автором и его последова телями в ряде работ [70–71;

79;

83–84], в учебных пособиях при чте нии обязательного раздела по теории автоматов в курсе «Компьютер ная схемотехника» [54–55;

66;

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

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

39;

42;

91;

104–106;

138;

143].

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

1.2. Понятия автомата: термины и определения Философы и математики, заметив одинаковые законы развития разнообразных объектов, предложили общее понятие – сложная сис тема.

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

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

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

Существуют два различных подхода с информационной точки зрения: изучение явлений в непрерывном или дискретном времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Большое значение имеет кодирующее отображение, которое на зывают просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а1 алфавита А некоторой конечной последовательности b b... b в алфавите B, называемой ко i1 i2 ik дом соответствующей буквы. Различным буквам алфавита А сопос тавляются различные коды. Кодирующее отображение должно быть обратимым, то есть взаимная однозначность соответствующего коди рующего отображения. Обратимость кодирования будет всегда вы полняться, если соблюдаются следующие два условия:

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

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

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

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

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

Кодирование информации в двоичном алфавите неоднозначно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примером однозначного алгоритма может быть система правил сложения целых чисел в произвольной позиционной системе счисле ния (двоичной, восьмеричной, десятичной и т. д.), которая состоит из правил поразрядного сложения и определения поразрядного переноса в старший разряд. Этот алгоритм сложения чисел С = А + В можно за дать в формульном виде так [65]:

ai bi, при ai bi q;

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

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

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

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

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

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

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

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

49].

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

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

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

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

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

130].

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

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

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

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


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

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

1.4. Понятие о дискретном автомате В данной работе основное внимание будет уделяться цифровым автоматам (компьютерам), которые функционируют в автоматном времени. Начиная с 40-х годов ХХ столетия, вся цифровая вычисли тельная техника проектировалась в целом с использованием класси ческой теории автоматов Мили и Мура, память в которых использо валась в основном на триггерах (элементарных монофункциональных схемах памяти с закрытой структурой и с «нулевой» избыточностью).

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

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

58–64;

66–67;

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

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

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

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

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

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

66–85]. Авторы надеются, что это обогатить в дальнейшем и теорию компьютерных алгоритмов, и тео рию построения устройств компьютеров, а также сможет явиться элементной базой для построения реконфигурируемых устройств, ко торой недостает в современных работах по когнитивному направле нию при создании модели человеческого мозга [1–2;

101].

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

92;

96;

101].

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

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

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

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

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

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

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

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

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

(1.4) T j t j j ;

j 0,1, 2,..., n,....

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

U t e1() х1(t) U t t t1 Т Т Рис. 1.3. Временные соотношения синхронизирующих и входных сигналов В автоматах Мараховского рассматривается и автомат 3-го рода, который дополняет теорию автоматов 1-го и 2-го рода.

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

В детерминированных автоматах Мараховского дополнительно рассматривается функция е сохранения состояний а(), которая оп ределяется парой (а(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). ев()).

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

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

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

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

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

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

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

4. методов построение цифровых искусственных нейронов.

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

2.2. Некоторые понятия об изменениях в функционировании и самоорганизации в автоматах При решении различных задач теории автоматов часто возникают дополнительные условия на рассматриваемые автоматы, определяю щие те или иные подклассы класса всех конечных автоматов [59;

93].

Одним из таких условий является понятие многофункциональных ав томатов совместно с автоматами настройки (автоматами стратегии).

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

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

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

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

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

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

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

асинхронного, вероятностного, нечеткого и т. д.

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

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

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

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

55;

64].

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

Однако, на взгляд автора, это не совсем верное утверждение.

Математика предлагает куда более простое объяснение. В 1928 году Фрэнк Пламптон Рамсей, английский математик, философ и экономист, доказал, что такие упорядоченные конфигурации неиз бежно присутствуют в любой большой структуре, будь то группа звёзд, совокупность случайно разбросанных камешков или последова тельность чисел, полученных бросанием игральной кости. Если речь идёт о достаточно большом количестве звёзд, то всегда можно найти группу, которая с очень большой точностью образует какую-нибудь заданную конфигурацию: прямую линию, прямоугольник или, если уж мы заговорили о звёздах, большой ковш. Фактически теория Рам сея утверждает, что любая структура обязательно содержит упорядо ченную подструктуру. Как впервые провозгласил около четверти века назад американский математик Теодор С. Моцкин, из теории Рамсея следует, что полный беспорядок невозможен [144].

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

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

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

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

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

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

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

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

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

64].

Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою подмножества µi ( Q) состояний автомата, j а строки – подмножества i j i Q) состояний автомата (табл. 2.1).

( j j Таблица 2. Матрица состояний схемы автоматной памяти µ1 µ2 ….. µn 0 a10 a20 … an 1 a11 a21 … an 2 a12 a22 … an …… … … … m a1m a2m … anm Триггеры и многостабильные схемы памяти (МСП) можно пред ставить как строку 0 автоматной матрице (табл. 2.1) в связи с тем, что все ее ai состояния сохраняются при одном сохраняющем е() вход ном сигнале в одном множестве всех его состояний. Эти схемы обла дают полнотой функций переходов, когда из каждого ak состояния можно под воздействием определенного входного х(t) сигнала перей ти в любое, наперед заданное, ai состояние схемы памяти;

а также полнотой системы выходов, когда каждое ai состояние отождествля ется с выходным уi сигналом, который отличный от всех других.

В многофункциональной схеме автоматной памяти (МФСП) [63] переходы в момент t под воздействием входных х(t) сигналов могут происходить из одного состояния в другое в определенном подмноже стве i, а в моменты автоматного непрерывного времени Т под воз действием входного е() сигнала могут происходить переходы из од ного состояния в другое в определенном подмножестве µi состояний автомата. Таким образом, в матричной схеме автоматной памяти воз можны переходы по двум переменным х(t) и е() в одном машинном такте Т автоматного непрерывного времени [64].

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

А = (Х, Е, 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,...,YK 1 } – множество выходных сигналов типа (выходной алфавит типа 1):

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

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

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

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

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

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

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

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

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;



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





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

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