"Компьютерра" № 47, 1998. тема номера - Хаос
cover page (10 Kb) "На кромке хАоса и хаОса" Л. Левкович-Маслюк
"Хаос. Тупики, парадоксы, надежды" Г. Малинецкий
"Детерминированный хаос и информационные технологии" А. Дмитриев
"Нелинейная динамика, теория динамического хаоса и синергетика (перспективы и приложения)" А. Лоскутов
"Что такое хаос?"

Детерминированный хаос и информационные технологии

А.С. ДМИТРИЕВ (3.6 Kb)

АЛЕКСАНДР ДМИТРИЕВ
Ведущий научный сотрудник Института радиотехники и электроники РАН, доктор физико-математических наук, профессор, дважды лауреат Премии Совета министров СССР
chaos@mail.cplire.ru

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

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

Управление хаосом

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

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

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

Кооперативное поведение и хаотическая синхронизация

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

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

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

Игра "Жизнь" в клеточных автоматах

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

Биологическая эволюция

Со времен Дарвина биологи рассматривали эволюцию как процесс естественного отбора. Однако возможно, что биологический порядок отчасти отражает спонтанную упорядоченность, на фоне которой действовал механизм естественного отбора. Другими словами, в процессе эволюции в пространстве морфологических признаков могут быть реализованы не все комбинации, а только некоторое избранное множество "аттракторов". То есть трудно ожидать, что любые уродства возможны. Кроме того, такой механизм значительно ускоряет процесс эволюции. Он резко сужает множество допустимых траекторий движения и, тем самым, необходимое число "итераций" для появления того или иного биологического вида. Здесь уместна аналогия между скоростью сходимости случайного и градиентного методов поиска экстремума: в первом случае поиск ведется по всей области изменения переменных, а во втором - только вдоль определенной траектории.

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

Самоорганизованная критичность

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

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

Как можно себе представить механизм адаптации в связанных динамических системах? Заманчиво выглядит модель эволюционного равновесия (кромки хаоса) как некоего вида хаотической синхронизации. Действительно, процесс синхронизации резко упрощает динамику системы, снижая размерность ее аттрактора. Он напрямую определяется степенью связности системы - "адаптивный механизм" движения к кромке хаоса включается только при наличии достаточно сильных связей.

Порождение информации хаотическими системами

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

Запись, хранение и поиск информации с помощью хаоса

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

Одна из двух картинок, записаных на отображении Функция отображения

Рис. 1.Пример, иллюстрирующий запись информации на циклах одномерного отображения отрезка в себя xn+1 = f(xn).
Фиолетовым цветом показана синтезированная функция y = f(x).
В примере на отображении записано два образа, один из которых - котенок размером 32х48 пиксела. Желтым цветом изображена траектория - предельный цикл, соответствующая изображению котенка. Любая точка цикла является "входом", позволяющим воспроизвести весь образ путем итерирования отображения. При старте с произвольных начальных условий траектория после переходного процесса притягивается к одному из двух циклов и воспроизводит соответствующий образ.

Эта идея возникла и получила развитие при попытках понять, чем может быть полезен хаос в обработке информации живыми системами. Были построены математические модели, которые демонстрировали принципиальную возможность записи, хранения и извлечения информации с помощью траекторий динамических систем с хаосом. Эти модели казались очень простыми, и эксперт одного уважаемого международного журнала написал в своей рецензии: "Это просто игрушечные модели, и на их основе не может быть создана никакая технология ни на Востоке, ни на Западе". Однако вскоре за исследования в этом направлении был присужден Главный приз на конкурсе компании "Хьюлетт-Паккард" по распознаванию образов. Развитие "игрушек" привело к тому, что их потенциальная информационная емкость значительно превысила объем всей информации, имеющейся в Интернете (патент РФ 2050072, патент США US 5774587). И даже на скромных "писишках" стало возможным синтезировать динамические системы с объемом записанной информации, эквивалентной среднему собранию сочинений.

Поиск информации на географических картах

Рис. 2. Пример применения ассоциативной памяти на основе хаотической динамики для целей ориентирования и навигации. Область для ориентирования общей площадью 576 км2 задается географической картой в масштабе М 1:20000. Она разбита на 16 фрагментов, каждый из которых представляет собой цветной графический образ размером 200х200 пикселов в 256-цветном алфавите. Каждый из образов представлен как предельный цикл в одном и том же двумерном кусочно-линейном отображении.

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

Программа демонстрирует также возможность идентификации по искаженным кусочкам. В нашем примере уровень искажений в кусочке, предъявляемом для идентификации, может составлять 70-80%.

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

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

Ассоциативный доступ к тексту

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

Дополнительную информацию по системе FacsData Wizard, а также демонстрационную версию программы можно получить по адресам http://www.aha.ru/~pbc и http://neurosoftdata.com.

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

Передача и защита информации

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

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

Структура источника хаотических колебаний Электронная схема и фазовый портрет

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

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

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

Связь с использованием хаоса

Рис. 5. Пример схемы связи с использованием хаоса. Передатчик и приемник включают в себя такие же нелинейные и линейные системы, как источник. Дополнительно в передатчик включен сумматор, а в приемник - вычитатель. В сумматоре производится сложение хаотического сигнала источника и информационного сигнала, а вычитатель приемника предназначен для выделения информационного сигнала. Сигнал в канале хаосоподобный и не содержит видимых признаков передаваемой информации, что позволяет передавать конфиденциальную информацию. Сигналы в точках A и A', B и B' попарно равны. Поэтому при наличии входного информационного сигнала S на входе сумматора передатчика такой же сигнал будет выделяться на выходе вычитателя приемника.

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

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

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

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

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

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

Литература

[1] Дмитриев А. С., Панас А. И., Старков С. О. Динамический хаос как парадигма современных систем связи, Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. 1997. № 10, стр. 4-26.

[2] Андреев Ю. В., Дмитриев А. С., Куминов Д. А. Хаотические процессоры, Успехи современной радиоэлектроники (Зарубежная радиоэлектроника), 1997, No. 10, с.50-79.

[3] Дмитриев А. С., Старков С. О. Передача сообщений с использованием хаоса и классическая теория информации. Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. 1998. №11, стр. 4-32.




Материалы "Компьютерры" №47, 1998, посвященные теме номера Хаос:
Л. Левкович-Маслюк, На кромке хАоса и хаОса
Г. Малинецкий, Хаос. Тупики, парадоксы, надежды
А. Дмитриев, Детерминированный хаос и информационные технологии
А. Лоскутов, Нелинейная динамика, теория динамического хаоса и синергетика (перспективы и приложения)

а также мнения "простых людей" о хаосе.


InformChaosLab. InformChaos Lab Home Page

Учебные и методические материалы по хаосу