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

February 15, 2013 by admin Комментировать »

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

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

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 R. V., Vorontzov G. М., Kolesov V. V., 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@mail.cplire.ru

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г. 

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

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