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

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

I. Вступ

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

Xn = f(xn-I, Xn-2,. – Xn-Nz, Nz, М) шляхом збільшення параметра запізнювання Nz [1]. Збільшення параметра Nz призводить, як правило, і до поліпшення статистичних характеристик формованого псевдовипадкового процесу і можливості генерації довших неперіодичних сегментів, довжина яких росте в середньому пропорційно MNz [1]. Метою даної роботи була перевірка можливості підвищення “складності” алгоритму не збільшенням його розмірності, а введенням додаткового параметра запізнювання і дослідження статистичних характеристик генеруються послідовностей.

Основна частина

Розглянемо алгоритм:

хп = f(xn-i, Xn-2,.– Xn-Nz1, Nz1, Nz2, М),

1<xn^ M, Nz1> Nz2 з додатковим перетворенням зсуву хп-> Хп ± М, здійснює при одно-кратному-двократному застосуванні повернення поточного числа хп в інтервал області визначення. Введення такої додаткової зворотного зв’язку з параметром Nz2 Nz< = 729 (таблиця 1).

У алгоритму з двома запізнюваннями, як і у базового, при непарних значеннях М всі цикли одинарної кратності, а при парному значенні М цикли в фазовому просторі-короткі і багаторазові. При цьому жодної чіткої закономірності між розмірами циклів у фазових просторах тієї та іншої систем не проглядається. Спектри циклів алгоритму з двома запізнюваннями Nz1 і Nz2 не містять циклів алгоритмів з одним запізнюванням Nz = Nz1 ​​і Nz = Nz2, а швидше збігаються зі спектрами циклів алгоритму з параметром Nz = (Nz1 + Nz2) / 2 і додаванням деякого числа циклів малого періоду. При цьому незалежно від парності параметра М, як правило, спостерігалася картина істотного зменшення довжини найбільшого циклу.

Таблиця 1.

Table 1.

Nz=4

44, 29, 7, 1

Nz=5

118, 70, 22, 16, 13, 3, 1

Nz=6

457, 100, 61, 31, 28, 26, 25, 1

Nz1=4,

Nz2=3

36, 22, 12, 8, 2, 1

Nz1=5,

Nz2=3

200, 25, 12, 5, 1

Nz1=5,

Nz2=4

80, 64, 26, 23, 17, 14, 11, 7, 1

Nz1=6,

Nz2=4

347, 217, 106, 33, 13, 9, 3, 1

Чисельне моделювання показало, що породжує алгоритм при значеннях Nz, М і початкових умовах, що відповідають досить довгим циклам, формує псевдослучайную послідовність з розподілом ймовірностей, близьким до рівномірного р (х) = 1 / М. Так, при Nz1 = 16, Nz2 = 11, М = 255 і довжині аналізованого сегмента послідовності з N = 210000 чисел в експерименті отримано середнє відносне відміну по модулю від рівномірного закону Арср = 0.026, що відповідає практично рівномірному розподілу.

В експерименті рівень бічних викидів авто-і взаімокорреляціонних функцій некліпірованних і кліпіровани довільних сегментів форміруемой алгоритмом послідовності не перевищував наступних значень: (1.5h-4.0) / Vn для сегментів з N = 128 і (2.3h-4.4) / Vn для сегментів з N = 1024, що узгоджується з відповідним рівнем бічних викидів кореляційних функцій випадкових послідовностей. Таким чином, введення в алгоритм додаткового зворотного зв’язку практично не впливає на форму кореляційних залежностей сегментів генерується послідовності.

Блокова структура кпіпірованной послідовності з 270000 членів для алгоритму з тими ж параметрами продемонструвала близькість до закону p (k) = 1/2k аж до блоків розміром к = 17. Результати чисельного аналізу представлені на рис.1 в зіставленні з блокової структурою послідовності, породжуваної базовим алгоритмом (М = 255, Nz = 16). З графіка видно, що ймовірність появи блоків з однакових символів повністю збігається з залежністю 1/2до аж до блоку розміром к = 13 з невеликими відмінностями від цього закону для блоків з к = 14-І7 символів.

Відбір в систему сигналів кодових сегментів з заданими кореляційними властивостями показав, що “швидкість” такого відбору для алгоритму з двома запізнюваннями може опинитися в 1.5Н-2 рази менше, ніж у базового алгоритму. Тим не менш, одержуваний обсяг системи сигналу в тому і в іншому випадку виявляється однаковим.

III. Висновок

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

Робота виконана за фінансової підтримки РФФМ, проекти 03-07-90133 та 04-07-90161.

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

Puc. 1. Імовірність появи блоків з k однакових символів в послідовності з 270000 чисел: для базового алгоритму (1), алгоритму з двома запізнюваннями (2) і V (k) = 1 /? (3).

Fig. 1. The probability of appearance of the blocks with k-identical characters in sequence of 270000 numbers: for basic algorithm(l), algorithm with two delays (2) and for real random law V(k)=1/2* (3)

[1] Колесов В. В. Фазовий простір цифрового кодує алгоритму для телекомунікаційних систем. Матеріали 14-ї Міжнародної Кримської конференції “НВЧ-техніка і комунікаційні технології”, (КриМіКо’2004), Севастополь, Україна, вересень 12-17, 2004 р.

THE CHAOTIC ENCODING ALGORITHM WITH TWO DELAY PARAMETERS

Kolesov V. V.

Institute of Radioengineering & Electronics RAS

11    Mokhovaya St., block 7, K-9, GSP-9 Moscow -125009, Russia

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

Abstract – By numerical methods the investigation and comparison statistical properties of pseudo-random sequences forming by discrete Fibonacci-type algorithm with one and two parameters of delay for digital system of communication were carried out.

I.  Introduction

At syntheses encoding algorithms for digital telecommunication systems there is the requirement of enough high difficulty of the algorithm’s evident type reconstruction on the basis the known realization of generated code sequence. There were investigated one way to satisfy this demand by means of using Fibonacci-type algorithm with two parameters of delay.

II.  Main part

The investigated discrete algorithm was specified on limited finite interval of integers. It was added by an operation of returning in this integer-value interval in case of going out in process of calculation. This mechanism is contributed to randomization of sequences. There were investigated: spectrum of cycles in phase space of this algorithm, auto- and inter-correlation functions and the block’s structure in generated sequences. It was shown that the statistical properties of sequences formed by this algorithm are near identical to one’s of Fibonacci-type algorithm with one parameter of delay.

III.  Conclusion

Thus it was shown that generative chaotic discrete algorithm with two parameters of delay has got the high difficulty for the evident type algorithm reconstruction on the basis of the final sequence realization. The statistical characteristics of the pseudorandom sequences generated designed discrete algorithm with two parameters of delay close to statistical characteristics of random process with uniform probability distribution.

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