Бєляєв Р В, Воронцов Г М, Колесов В В, Попов А М, Рябенко В І Інститут радіотехніки й електроніки РАН, ІРЕ РАН м Москва, вул Мохова, д 11, корп 7, центр, ГСП-9, 125009, Росія Тел: +7 (495) 2021046, e-mail: kvv@mailcplireru

Анотація – Для оцінки ефективності застосування кодують алгоритмів в телекомунікаційних системах запропонований метод аналізу розподілу інтервалів між появами ідентичних кодових груп у псевдослучайной послідовності і встановлено звязок цього розподілу зі структурою формуючого послідовність кодує алгоритму

I                                       Введення

Перспективним напрямом розвитку сучасних систем звязку є застосування широкосмугових шумоподібних сигналів [1, 2] Широкосмугові системи звязку мають ряд переваг в порівнянні з традиційними вузькосмуговими системами Ці переваги повязані із зростанням числа користувачів, щільного заповнення частотного діапазону, необхідності забезпечення надійної конфіденційної передачі інформації Необхідне для роботи широкосмугових систем розширення спектру переданого сигналу досягається застосуванням псевдовипадкових послідовностей, що формуються різними спеціальними алгоритмами Ці й інші застосування подібних послідовностей (надлишкове кодування інформації в цифрових каналах звязку, криптографія, моделювання методами Монте-Карло) спонукають до пошуку нових алгоритмів, в тому числі з різними характеристиками і функціями розподілу ймовірностей Одночасно триває пошук нових методів аналізу статистичних властивостей, формованих ними послідовностей, оцінок близькості їх до ідеального випадковому процесу [3,4] Розглянуто метод оцінки статистичних властивостей цифрових багаторівневих псевдовипадкових послідовностей шляхом аналізу статистики розподілу в них кодових груп з повного коду для обраної бази псевдослучайного сигналу Розвитком цього підходу є зясування статистики інтервалів між послідовними появами ідентичних кодових груп з повного коду Очікується, що цей підхід дозволить, зокрема, аналізувати структуру невідомого алгоритму, формуючого досліджувану псевдослучайную послідовність Проведено зіставлення зазначених характеристик інтервалів для послідовностей, що формуються різними алгоритмами, в тому числі і вживаними в стандартних програмних пакетах

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

Оцінку статистичних характеристик псевдовипадкових послідовностей, що формуються деяким алгоритмом, і близькість до ідеальної випадкової послідовності можна розглядати як процес формування серії кроків, результат яких на кожному кроці повністю незалежний від результатів на попередніх кроках При цьому, якщо досліджуваний алгоритм визначений на множині цілих чисел, наприклад на інтервалі [1, М], де М-макс ціле число), то можна вважати, що відповідна цим параметрам ідеальна випадкова послідовність буде формуватися в результаті кидання М-мірного кубика, на кожній грані якого нанесено одне з цілих чисел, що входять в зазначений інтервал

Розглянуто підхід дозволяє аналізувати статистичні структурні особливості псевдовипадкових цілочисельних послідовностей Досліджувана послідовність порівнюється з кодовою групою певної довжини і структури Довжина групи – це число членів послідовності, рівне обраній базі псевдослучайного сигналу (В), а структура групи-це конкретний набір з В цілих чисел з інтервалу [1, М] Загальне число всіх різних кодів при цьому дорівнює числу елементів повного коду М [1]

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

Встановлено, що для псевдовипадкових послідовностей, що формуються поруч алгоритмів (навіть близьких до ідеальної випадкової послідовності) при аналізі інтервалів (К-довжина інтервалу) між збігами при зміщенні кодової групи уздовж псевдослучайной послідовності виявляються деякі особливості Для класу алгоритмів типу Фібоначчі [5] були отримані близькі до рівномірним розподілу щільності ймовірностей по всіх кодовою групам для даної бази Однак, при аналізі статистики появи деякої кодової групи (для В = 1) у розподілі мався провал Νκ = 0, де Νκ-число збігів Цей інтервал (К) дорівнює параметру запізнювання, що є характеристикою аналізованого алгоритму для бази В = 1 Характерний вид розподілів інтервалів (К) для 2 різних кодових груп (11 і 19) (параметри алгоритму М = 19, запізнювання Νζ = 8) при В = 1, показані на рис1 а, б Для всіх інших кодових груп при даному В ця залежність має ідентичний вигляд з рис1 а

Якщо ймовірність появи кодової групи довжиною В для ідеальної випадкової послідовності р = 1 / М ®, а Т-число членів аналізованої послідовності, то середнє число появ кодів Т / М ® Тоді очікуване число збігів з кодовою групою довжини В через інтервал К в послідовності довжини Т одно:

Fig 1 а, Ь Function of distribution for intervals between identical code groups appearances with length У for sequence, forming by Fibonacci-type algorithm (with parameters: M = 19, delay Nz = 8 a-curve 1 for code 11 b- curve 1 for code 19 curves 2 for ideal random sequence

На рис1 а, б ця залежність Nk = F (К) представлена ​​для ідеального випадкового процесу (крива 2) Вона має характер близький до експоненті

Для В> 1 аналізоване розподіл інтервалів має більш складний вигляд: для інтервалу К, рівного параметру запізнювання Nz алгоритму є кодові групи для яких Νκ = 0 і кілька кодів для яких Νκ помітно перевищує очікуваний середній рівень, відповідний моделі ідеального випадкового процесу

III                                  Висновок

Запропонований метод аналізу статистики розподілу інтервалів появи кодових груп дозволяє дешифрувати структуру невідомого формуючого алгоритму

Робота виконана за фінансової підтримки РФФМ, проекти 04-07-08013 та 06-07-08109

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

[1] Вакін Л Є Системи звязку з шумоподібним сигналами М: Радіо і звязок, 1985

[2] Скляр Б Цифрова звязок Теоретичні основи і практичне застосування Пер з англ М – С-П-Київ, 2003

[3] Кнут Д Мистецтво програмування для ЕОМ Полу-чисельні алгоритми Т2 Пер з англ М: Світ, 1977

[4] Аграновський А В, Хаді Р Практична криптографія М: СОЛОН-Пресс, 2002

Бєляєв Р В, Воронцов Г М, Колесов В В, Рябенко В І, Попов А М Псевдовипадковий цілочисельний генератор типу Фібоначчі для кодування інформації / LVIII Наукова сесія, присвячена дню радіо Москва

2003 Праці ΡΗΤΟ РЕЗ ім А С Попова Т1 С118-120

THE ANALYSIS OF CODING PSEUDORANDOM ALGORITHMS ON BASIS OF CODING GROUP DISTRIBUTION

Рис 1 а, б Розподіл по інтервалах між появами ідентичних кодових груп при В = 1 для послідовності, формованої алгоритмом типу Фібоначчі (з параметрами: М = 19, запізнювання Nz = 8 а-крива 1 для коду 11 б – крива 1 для коду 19 криві 2 для ідеальної випадкової послідовності

Belyaev RV, Vorontzov G М, Kolesov VV, Popov A М, RyabenkovV I

Institute of Radio Engineering and Electronics, RAS

11,                    Mokhovaya Str, Block 7, Centre,

GSP-9, Moscow, 125009, Russia Ph: +7(495)2021046, e-mail: kvv@mailcplireru

Abstract – For evaluation of effectiveness of application coding algorithms in telecommunication systems the analysis method for distribution of intervals between of identical coding groups’ appearances in pseudorandom sequence and was detected a connection of this one with structure of the forming these sequence algorithm was propose

I                                         Introduction

A method of evaluation statistical properties of digital multilevel pseudorandom sequences by means of analysis the probability distribution of codes out of full code was considered As the development of this approach there was a revelation of a statistic of intervals between successive appearances of the identical code in analyzing sequence This approach allows seeing some new statistical characters of analyzing sequence

II                                        Main Part

An approach allowing analyzing statistical structure features of pseudorandom integer-number sequences was considered The analysis method consists of sequential comparison of investigated sequence with code group of definite length and definite structure The length of code group is a number of sequence’s members equal to selected basis (B) for pseudorandom signal A structure of this one is a concrete set of У integer numbers out of interval [1, M] specifying investigated sequence Then a whole number of different code groups is equal to M ® [1]

For this procedure the functions of distribution were established for the whole code group out of full code for some algorithms of pseudorandom sequences All these functions of distributions by their uniform were close to ideal random sequence But some uncommon features were observed for intervals between appearances of identical codes group for some of Fibonacci-type algorithms So, for a code group with a length B=1 function of distribution on intervals between two identical code groups in forming sequence there was an absence of such intervals for the group of codes which is equal to max value M for interval’s length K= Nz This value Nz is a parameter of delay for this algorithm

On results of this investigation you can consequently get to know a parameter of delay Nz for algorithm of this type

III                                       Conclusion

The proposed analysis of intervals between appearances in pseudorandom sequence of identical codes allows decoding a structure of some type of unknown forming algorithm

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