РАДИОТЕХНИКА И ЭЛЕКТРОНИКА, 2004, том 49, № 3, с. 325-332
= СТАТИСТИЧЕСКАЯ РАДИОФИЗИКА
УДК 621.396
СПЕКТР ПЕРИОДОВ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ФОРМИРУЕМЫХ ДИСКРЕТНЫМ АЛГОРИТМОМ С ЗАПАЗДЫВАНИЕМ
© 2004 г. Р. В. Беляев, Г. М. Воронцов, В. В. Кислов, В. В. Колесов, А. М. Попов, В. И. Рябенков
Поступила в редакцию 03.06.2003 г.
Для разработки информационных технологий и задач помехоустойчивого кодирования исследованы закономерности формирования псевдослучайных последовательностей дискретными алгоритмами с запаздыванием типа Фибоначчи, определенными на замкнутом интервале целых чисел, в которых используется возврат генерируемых чисел в заданный интервал, обеспечивающий механизм перемешивания. Для различных значений параметров найдены спектры периодов последовательностей для произвольного набора начальных значений, однозначно определяющих состояние системы в ее фазовом пространстве. Получены соотношения, позволяющие сократить время поиска максимального периода псевдослучайной последовательности, формируемой рекуррентным алгоритмом типа Фибоначчи.
ВВЕДЕНИЕ
Поиск информационных носителей (процессов и сигналов), имеющих повышенную информационную емкость, и математических алгоритмов, порождающих такие процессы, является наиболее актуальной задачей при разработке новых информационных технологий. Основным термином в области информационных технологий служит "кодирование информации", трактуемое обычно как синоним способа "представления информации". Носителями информации могут быть графика (рисунки), тексты, нотные записи, числа, последовательности электромагнитных, оптических или других сигналов.
Под словом "код" в самом общем смысле понимают конкретный способ представления информации. Часто под словом "кодирование" понимают также не только способ представления информации, но еще и сам процесс преобразования из одного представления информации в другое. Процесс обратного преобразования в таком случае обычно называют декодированием.
Прикладное применение информационных технологий предполагает физическую реализацию конкретного кодирующего процесса при передаче, обработке и хранении информации в телекоммуникационных системах и компьютерных сетях. Прогресс в данной области связан с увеличением быстродействия и повышением помехозащищенности информационных каналов. Это в первую очередь обусловлено потребностью разработки эффективных каналов информационного обмена и управления распределенными сетями и автоматическими системами с дистанционным управлением, где цена ошибки или частичная потеря ин-
формации может иметь катастрофические последствия, вплоть до потери всей системы.
Наблюдаемая в последние годы тенденция глобального распространения разнообразных открытых телекоммуникационных систем и резкий рост числа абонентов приводят к необходимости защиты информации не только на уровне государственных органов, специальных служб или деловых кругов, но и на уровне практически каждого индивидуального пользователя. В информационных сетях постановка данной проблемы обусловлена в большей степени потерями информации из-за низкой помехоустойчивости различных каналов связи, а не вопросами сохранения конфиденциальности. Проблема повышения помехоустойчивости каналов связи особенно актуальна в радиолинейных линиях. Насыщенность частотного диапазона, традиционными средствами связи, основанными на принципе частотного разделения каналов, привела к разработке методов кодирования для так называемого кодового разделения каналов, в которых в качестве кодов применяются потоки случайных (псевдослучайных) чисел. При передаче информации потоковое кодирование обеспечивает наибольшую помехоустойчивость (а значит, и криптостойкость) при использовании непрерывных случайных ключевых потоков с равномерной функцией распределения. Естественно, что в таких системах для обеспечения кодового разделения ключевые потоки абонентов, участвующих в информационном обмене, должны быть когерентны.
Для формирования случайных числовых последовательностей применяют два основных метода: первый основан на использовании оцифров-
ки аналоговых случайных физических процессов, а второй использует детерминированные вычислительные алгоритмы, генерирующие потоки чисел, обладающие статистическими свойствами случайного процесса, вследствие чего они были названы псевдослучайными. Примером истинно случайных физических явлений могут быть, например, дробовой и тепловой шумы. В последние годы в связи с развитием возможностей цифровой техники при обработке потоковой информации в режиме реального времени наблюдается тенденция постепенного вытеснения аналоговых методов представления и обработки информации. Эффективное кодирование информации осуществляется псевдослучайными последовательностями (ПСП), сформированными при помощи специально разработанных программных алгоритмов.
Следует отметить, что при генерации ПСП одна из основных проблем заключается в необходимости формирования длинных реализаций при использовании короткого задающего ключа, определяющего начальные условия.
При программной реализации алгоритмов генерации псевдослучайных процессов ЭВМ оперирует с дискретными числами в бинарном представлении с конечным числом разрядов. Из-за этого ограничения на конечную разрядность чисел в ЭВМ полный объем фазового пространства (ФП), любая точка которого соответствует однозначному состоянию системы, ограничен. Соответственно, любой алгоритмический метод формирования должен выйти на периодическое повторение одних и тех же сегментов формируемой последовательности, т.е. выйти на цикл, хотя его период и может быть очень большим и даже бесконечным с точки зрения ряда практических применений.
Требования, предъявляемые к свойствам последовательностей псевдослучайных чисел, зависят от конкретных применений. Как правило, один алгоритм не может удовлетворить всем этим требованиям. В общем случае можно сформулировать основные требования, предъявляемые к ПСП [1]:
1) высокое качество - ПСП по статистическим критериям должна быть близка к случайному процессу и иметь возможно более длинный период;
2) эффективность - алгоритм должен быть быстрым и занимать возможно меньший объем памяти;
3) воспроизводимость - при точном воспроизведении начальных условий алгоритма должна формироваться одна и та же ПСП на реализациях любой длительности, а незначительные изменения в начальной процедуре должны приводить к генерации качественно различных последовательностей;
4) простота - формула алгоритма должна быть проста в реализации и использовании.
Все сказанное подчеркивает актуальность поиска новых детерминированных алгоритмов, обеспечивающих формирование потоков псевдослучайных чисел, удовлетворяющих различным системам требований.
В общедоступной литературе практически нет сведений о методах разработки алгоритмов генерации псевдослучайных чисел. Однако следует отметить работу [2], в которой в основном рассмотрено понятие случайности конечного ряда чисел, формируемых детерминированным алгоритмом, тесты проверки статистических свойств этих чисел и их применения в разнообразных вычислительных задачах. Разработка новых алгоритмов требует понимания закономерностей формирования ПСП чисел с определенными заданными статистическими свойствами.
С точки зрения практического применения в цифровых информационных технологиях интерес представляют алгоритмы, определенные на замкнутом интервале целых чисел. В этом случае в процессе вычисления членов последовательности устраняется (исключается) операция округления. Соответственно, результаты вычисления в этом случае не будут зависеть от разрядности шины данных в конкретной ЭВМ и числа значащих цифр в представлении чисел с фиксированной запятой, что является несомненным достоинством таких алгоритмов.
Достигнутые в последние годы успехи в понимании механизмов возникновения хаоса в динамических системах широкого класса, позволил по новому взглянуть на пути разработки алгоритмов формирования псевдослучайных числовых последовательностей [1-5]. В частности, более ясной стала роль механизма перемешивания в обеспечении процесса стохастизации, что особенно важно в случае использования алгоритмов, определенных на ограниченном числовом интервале. Наиболее известными из описанных в литературе алгоритмов формирования ПСП являются целочисленный конгруэнтный алгоритм, предложенный математиком Лемером [1] и семейство алгоритмов типа алгоритмов Фибоначчи [6]. Конгруэнтный алгоритм имеет вид
Хп = (аХп -1 + С)( modM),
где Х0, а, С - заданные целые числа (при этом Х0, а, С < М, а в качестве М взято некоторое большое целое число).
Алгоритмы Фибоначчи относятся к классу алгоритмов с запаздыванием. Обобщенная формула их линейного варианта имеет вид
Nz
Хп = 1
Г N1
а:Хп _ ¡А
1 ЬХ - ,
V = 1
; л
где а, Ь равны нулю или единице, N _ параметр
запаздывания, А (■) - некоторый оператор, учитывающий фазовые соотношения между запаздывающими членами. Случай А (■) = 1 соответствует обобщенному генератору Фибоначчи:
Nz
Хп
= X
ап — 1ХП
1 = 1
Параметр запаздывания N1 определяет число заданных (или вычисленных ранее) членов последовательности, которые надо хранить в памяти вычислительного устройства, чтобы иметь возможность найти новый член последовательности на каждом следующем шаге алгоритма, ап _ 1 _ коэффициенты, которые обычно считают равными единице или нулю. В ряде работ используются не суммы, а разности этих элементов или их произведения. Классический алгоритм Фибоначчи учитывает только два члена ряда: вычисленный на предыдущем шаге (п _ 1) и вычисленный на шаге (п _ N1).
Размерность ФП динамической системы определяется числом величин, которые надо задать, чтобы однозначно описать ее состояние и иметь возможность найти состояние системы на следующем шаге вычисления. Очевидно, что размерность ФП динамической системы, описываемой алгоритмом с запаздыванием, определяется параметром запаздывания N1.
В силу ограниченности ФП алгоритма, заданного на конечном интервале целых чисел, общее число всех состояний системы счетно и конечно. И начиная с некоторого шага результаты вычисл
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.