Колесов В. В. Інститут радіотехніки й електроніки РАН Мохова 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) відхилення розподілів від рівномірного (п = 210 000). Видно, що алгоритм формує послідовність з практично рівномірним розподілом при 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.

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