ФАЗОВОЕ ПРОСТРАНСТВО ЦИФРОВОГО КОДИРУЮЩЕГО АЛГОРИТМА ДЛЯ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

April 3, 2012 by admin Комментировать »

Колесов В. В. Институт радиотехники и электроники РАН Моховая 11, корп. 7, Москва К-9, ГСП-9, 125009, Россия Тел.: +7(095) 2021046; e-mail: kvv@mail.cplire.ru

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

I.  Введение

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

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

II.  Основная часть

Рассматривается дискретный алгоритм с запаздыванием типа генератора случайных чисел Фибоначчи, формирующий псевдослучайную последовательность с хорошими статистическими свойствами. Основным параметром алгоритма является параметр запаздывания Nz, определяющий число запоминаемых членов последовательности и размерность фазового пространства (ФП). Алгоритм определяется на конечном множестве целых чисел натурального ряда из замкнутого интервала [1, М]. Если вновь вычисленное число последовательности выходит за пределы этого интервала, то осуществляется линейное преобразование сдвига хп—>хп±М, возвращающее это число в границы области определения. Это преобразование помимо функционального действия самого алгоритма типа Фибоначчи играет существенную роль в механизме хаотизации поведения исследуемой динамической системы [1].

Число точек состояний системы в фазовом пространстве алгоритма конечно и равно MNz. Движение системы в ФП осуществляется путем перехода скачком из одного состояния в другое. Траектории движения системы занимают весь объем ФП, т.е. все возможные состояния. Каждая такая траектория движения системы происходит по своему замкнутому циклу, содержащему ограниченное число состояний системы. Структура ФП состоит из конечного набора циклов разного периода, поведение системы на которых носит псевдослучайный характер. Все циклы сложным образом располагаются во всем объеме ФП. Так, ФП алгоритма при Nz=4 и М=17 состоит из пяти циклов с периодом 73684, 3619, 2549, 2471, 529 и одной особой точки с координатами (17,17,17,17). Выбор цикла определяется заданием набора начальных условий

Псевдослучайный характер поведения системы на цикле на интервале, меньшем периода, подтверждается зависимостью изменения расстояний в ФП AR(n) между соседними точками на цикле, приведенной на рис.1 для алгоритма с Nz=3, М=13. Это расстояние на каждом шаге алгоритма изменяется случайным образом, достигая значений, близких к наибольшим геометрическим размерам ФП.

Фазовое пространство исследуемого алгоритма при Nz>2 состоит из одной особой точки с координатами (М,М,…М) и семейства циклов разного или одного и того же периода. Каждая точка ФП принадлежит только одному конкретному циклу, при этом разные циклы не имеют ни одной общей точки.

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

Показано, что в ансамбле фазовых пространств алгоритмов с различными параметрами М и Nz наблюдаются как "короткие" циклы, период которых Т много меньше по сравнению с полным числом точек фазового пространства MNz (T«MNz), так и "длинные" циклы, период которых сопоставим с последней величиной: T~MNz. При четных М в ФП алгоритма преобладают короткие циклы, а при нечетных М коротких циклов вообще не существует, либо они представлены в небольшом количестве, занимая малый объем ФП, что и обеспечивает возможность существования длинного цикла. Тем самым при нечетных М наблюдаются наиболее длинные циклы. Период таких циклов при определенных значениях параметров алгоритма может приближаться к максимально возможной величине Tmax=MNz.

Численным экспериментом зафиксирован случай, когда ФП содержит только один длинный цикл и одну изолированную точку: М=2, Nz=15, T/MNz =1.0. Близкий результат получен при М=3, Nz=9, когда период длинного цикла T/MNz=0.999, а помимо него и одной изолированной точки в ФП системы существует только один пятитактный короткий цикл. Все это подтверждает, что оценкой максимального непериодического сегмента формируемой алгоритмом последовательности может служить величина Tmax=MNz. Следует иметь в виду, что этот максимальный период Ттах может быть реализован лишь при определенных соотношениях параметров М и Nz.

Показано, что длинным циклам соответствуют распределения генерируемых чисел, близкие к равномерному. Характер изменения функций распределения генерируемых чисел при увеличении параметра Nz (для М=255) показан на рис.2. Здесь: Дрср,

Лрмакс, среднее (1) и максимальное (2) относительные по модулю, среднеквадратичное (3) отклонения распределений от равномерного (п=210000). Видно, что алгоритм формирует последовательность с практически равномерным распределением при Nz>5. В этом случае близки к равномерному распределению и все условные вероятности p(xi|xj). Это означает, что формируемая данным алгоритмом псевдослучайная последовательность по своим вероятностным свойствам мало отличается от последовательности независимых равновероятных чисел из интервала [1, М].

III.  Заключение

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

Работа выполнена при финансовой поддержке РФФИ, проекты 03-07-90133 и 04-07-90161

IV. Список литературы

Рис. 1. Расстояния в ФП между соседними точками на цикле. Nz=3, М=13.

[1]    Беляев Р.В., Воронцов Г.М., Кислое В.В., Колесов В.В., Попов А.М., Рябенков В.И. Спектр периодов псевдослучайных последовательностей, формируемых дискретным алгоритмом с запаздыванием. Радиотехника и электроника, 2004, т. 49, № 3, с.325-332.           

THE PHASE SPACE OF THE DIGITAL ENCODING ALGORITHM FOR TELECOMMUNICATION SYSTEMS

Kolesov V. V.

Institute of Radioengineering and Electronics RAS

11  Mokhovaya St., block 7, K-9, GSP-9,

Moscow -125009, Russia

phone: (095) 2021046; e-mail: kvv@maii.cplire.ru

Abstract – There were investigated the phase space’s structure of discrete algorithm with delay determined on integer number interval. The Fibonacci-type mechanism of chaotization was added by a mixing transformation at bound violation of the definite region of value. It was founded the phase space of the system consisted of finite number of different cycles and the system’s behavior has pseudo-random character. It was shown that under the condition of proper choice of value the algorithm allows to form nonperiodic pseudorandom sequence of the prescribed length for coding of information in telecommunication system.

I.   Introduction

For providing the effective coding of digital information there are required of pseudo-random sequences with arbitrarily match period. Syntheses and investigation of an algorithm for forming of sequences with properties of such kind is an object of this report.

II.   Main part

There were investigated Fibonacci-type discrete algorithms with delay forming pseudorandom sequences with good statistical properties. The algorithm is specified on finite set of integers [1, М]. If in process of calculation a new received number is out of borders of this interval the special transformation is used. This operation returns it back to interval in accordance with law xn—>xn±M. This transformation additionally assists to mechanism chaotization at forming sequences. There were examined properties of the algorithm’s phase space and spectrum of cycles in it.

III.   Conclusion

It was shown that the investigated algorithm with proper matching value of parameters forms long non-periodic segments of pseudo-random sequences with uniform function of probability distribution. This algorithm can be effectively used at coding of information in telecommunication system and computer networks.

Fig. 1. Distance in phase space between neighbor points on cycle: Nz=3, M=13

Puc. 2. Отличие распределения от равномерного в зависимости от Nz (М=255).

1  – \Рср, 2 -Армакс, 3 — 0.

Fig. 2. The difference on uniform function of numbers distribution in dependence of Nz (M=255)

1    – Apcp, 2 -Армакс, 3 — 0.

Источник: Материалы Международной Крымской конференции «СВЧ-техника и телекоммуникационные технологии»

Оставить комментарий

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