коды голда псевдослучайные последовательности

Коды голда псевдослучайные последовательности

10 Псевдослучайные коды(последовательности)

Максимально достижимое значение автокорреляционной функции:

Рассмотрим в качестве примера по формированию М-последовательности систему состоящую из n =4 регистров хранения сдвига и к=1 сумматоров по |2|:

Работа по генерации М- последовательности осуществляется следующим образом:

С каждым новым тактом содержимое регистра сдвигается на одну позицию вправо

Содержимое регистров Х3 и Х4 суммируются по |2|. Результат суммирования по обратной связи подается на входной регистр Х1. Итоговая последовательность –это то. Что формируется на выходе регистра Х4

Пусть в регистрах содержатся следующие двоичные значения:

Тогда на выходе регистра Х4 при каждом новом такте будем иметь:

Поскольку последнее состояние регистров Х1,Х2,Х3,Х4 идентично первоначальному, то заключаем, что длина полученной последовательности равна 15, что соответствует максимально возможной длине:

Таким образом на выходе регистра Х4 мы получим двоичную последовательность вида: 111101011001000.

Проверим данную последовательность на случайность.

А) проверка на сбалансированность

Количество «0»-7 вывод:- сбалансирована

Б) Проверка на цикличность:

При этом половина из этих циклов(т.е. 4) имеет длину =1

1/4 (т.е 2) имеет длину =2

В) Проверка на корреляцию

Сравниваем с первоначальной

Это означает, что данная последовательность коррелированна

Формируются на основе 2-х специально подобранных М-последовательностей и их посимвольного сложения по |2|.(смотри следующий рисунок)

Реализуются с помощью 3-х последовательно включенных М-последовательностей, которые так же подбираются исходя из критерия предпочтительности с различными обратными связями:

, где m ‘ и k ‘- циклические сдвиги кодов генерируемых регистрами y и z соответственно

Семейство кодов Кассами содержит последовательностей с периодом

Они считаются оптимальными в том смысле, что для любой пары кодовой последовательности Кассами обеспечиваются максимальные значения автокорреляционной функции равные:

Источник

Псевдослучайные последовательности и их применение для защиты информации

Автор: Пользователь скрыл имя, 14 Октября 2011 в 15:49, реферат

Описание работы

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

Работа содержит 1 файл

Министерство образования и науки Украины

Национальный технический университет

«Харьковский политехнический институт»

Кафедра автоматики и управления в технических системах

«Псевдослучайные последовательности и их применение для защиты информации»

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

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

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

1 ОПИСАНИЕ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

1.1 Основные аспекты псевдослучайных последовательностей (ПСП)

Последовательности случайных чисел широко используются в самых разных приложениях — от компьютерного программирования, имитационного моделирования и методов Монте-Карло до криптографии. При этом от свойств случайных последовательностей напрямую зависит качество получаемых результатов.

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

Псевдослучайная последовательность (ПСП) — это последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи. Хотя псевдослучайная последовательность в этом смысле часто, как может показаться, лишена закономерностей, однако, любой псевдослучайный генератор с конечным числом внутренних состояний повторится после очень длинной последовательности чисел.

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

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

1) Количество «1» в каждом периоде должно отличаться от количества «0» не более, чем на единицу.

2) В каждом периоде половина серий (из одинаковых символов) должна иметь длину один, одна четверть должна иметь длину два, одна восьмая должна иметь длину три и т.д. Более того, для каждой из этих длин должно быть одинаковое количество серий из «1» и «0».

Последовательность, удовлетворяющая правилам 1-3 часто именуется «ПШ-последователъностъю», где ПШ обозначает «псевдо-шумовая». К анализируемой последовательности применяется широкий спектр различных статистических тестов для исследования того, насколько хорошо она согласуется с допущением, что для генерации использовался совершенно случайный источник.

1.2 Разновидности ПСП

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

Такие последовательности обладают следующими свойствами:

1.2.2 Последовательности Голда

Последовательности Голда могут быть сгенерированы путем суммирования по модулю 2 двух М-последовательностей одинаковой длины. Результирующие Коды Голда имеют ту же самую длину как и исходные М-последовательности (рис 1.2).

В проекте WCDMA специфицированы три типа кодов Голда: первичный и вторичный ортогональные коды Голда (оба длиной 256 бит) и длинный код.

Ортогональные коды Голда создаются на основе m-последовательности длиной 255 бит с добавлением одного избыточного символа. Первичный синхрокод имеет апериодическую автокорреляционную функцию и используется для первоначального вхождения в синхронизм. Вторичный синхрокод представляет собой немодулированный ортогональный код Голда, который передается параллельно с первичным синхрокодом. Каждый вторичный синхрокод выбирается из 17 различных кодов Голда .

Длинный код для прямого канала представляет собой фрагменты кода Голда длиной 40 960 чипов. Система связи на базе WCDMA асинхронна, и соседние базовые станции используют различные коды Голда (всего их 512), повторяемые каждые 10 мс. Асинхронный принцип работы базовых станций делает их независимыми от внешних источников синхронизации. Предполагается применять длинный код и в обратном канале, однако только в тех сотах, где не задействуется режим многопользовательского детектирования.

1.2.3 Последовательности Касами

Источник

CDMA: сигналы и их свойства

Когда-то проектирование CDMA-систем было скорее искусством, чем наукой.

Инженеры выбирали сигналы, применение которых должно улучшить основные характеристики систем (качество связи, помехоустойчивость), полагаясь лишь на свою интуицию. Поворотным моментом стало создание теории формирования, обработки и передачи сигналов. Она позволяет определить эффективность использования конкретного ансамбля (множества) сигналов, базируясь лишь на знании их авто- и взаимокорреляционных характеристик.

Базовые понятия

Кодовые последовательности, используемые в CDMA-системах для передачи сигнала, состоят из N элементарных символов (чипов). Каждый информационный символ сигнала складывается с одной N-символьной последовательностью, которая называется «расширяющей» (spreading sequence), поскольку «результирующий» сигнал излучается в эфир с преднамеренно расширенным спектром. Выигрыш в качестве связи зависит как от числа символов (длины) последовательности, так и от характеристик совокупности сигналов, в первую очередь – их взаимокорреляционных свойств и способа модуляции.

Длина последовательности. В отечественной литературе сигналы, база которых существенно больше единицы (B=TF>>1, где T – длительность элемента сигнала, F – полоса частот), обычно называются сложными. По отношению к исходному (информационному) сложный сигнал представляет собой шум с практически одинаковой спектральной плотностью мощности.

Известно, что чем сильнее «растянут» спектр сигнала в эфире, тем меньше его спектральная плотность. Благодаря этому свойству сигналы с большой базой могут применяться в «чужой» (уже занятой) полосе частот «на вторичной основе», оказывая на работающую там систему сколь угодно малое воздействие.

Характеристики. Вся совокупность кодовых последовательностей, используемых в CDMA, делится на два основных класса: ортогональные (квазиортогональные) и псевдослучайные последовательности (ПСП) с малым уровнем взаимной корреляции (рис. 1).

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

Дабы получить выигрыш в качестве связи при использовании любого из способов корреляционной обработки, необходимо, чтобы ансамбль сигналов обладал «хорошими» автокорреляционными свойствами. Желательно, чтобы сигналы имели единственный автокорреляционный пик, иначе возможна ложная синхронизация по боковому лепестку автокорреляционной функции (АКФ). Заметим, что чем шире спектр излучаемых сигналов, тем уже центральный пик (основной лепесток) АКФ.

Пары кодовых последовательностей подбираются так, чтобы взаимная корреляционная функция (ВКФ) имела минимальное значение при их попарной корреляции. Это гарантирует минимальный уровень взаимных помех.

Следовательно, выбор оптимального ансамбля сигналов в CDMA сводится к поиску такой структуры кодовых последовательностей, в которой центральный пик АКФ имеет наибольший уровень, а боковые лепестки АКФ и максимальные выбросы ВКФ по возможности минимальны.

Ортогональные коды

В теории сигналов доказано, что предельно достижимое значение коэффициента взаимной корреляции определяется из условия

Минимальное значение ВКФ обеспечивает коды, у которых коэффициенты корреляции для любых пар последовательностей являются отрицательными (трансортогональные коды). Коэффициент взаимной корреляции ортогональных последовательностей, по определению, равен нулю, т.е. о?_ij=0. При больших значениях N различием между коэффициентами корреляции ортогональных и трансортогональных кодов практически можно пренебречь.

Принцип формирования этой матрицы достаточно прост; его поясняет рис. 2. Исходным является сигнал вида H₁=<1>. Подставляя его в матрицу H_2n, получаем новую матрицу большего размера:

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

Такой способ формирования сигналов реализован в стандарте IS-95, где длина последовательностей Уолша выбрана равной 64. Заметим, что различие между строками матрицы Адамара и последовательностями Уолша состоит лишь в том, что в последних используются униполяные сигналы вида <1,0>.

Другая важная разновидность ортогональных кодов – биортогональный код, который формируется из ортогонального кода и его инверсии. Главное достоинство биортогональных кодов по сравнению с ортогональными – возможность передачи сигнала во вдвое меньшей полосе частот. Скажем, биортогональный блочный код (32,6), используемый в WCDMA, позволяет передавать сигнал транспортного формата TFI.

Отметим, что ортогональным кодам присущи два принципиальных недостатка.

1. Максимальное число возможных кодов ограничено их длиной (в стандарте IS-95 число кодов равно 64), а соответственно, они имеют ограниченное адресное пространство.

Для расширения ансамбля сигналов наряду с ортогональными используются квазиортогональные последовательности. Так, в проекте стандарта cdma2000 предложен метод генерации квазиортогональных кодов путем умножения последовательностей Уолша на специальную маскирующую функцию. Этот метод позволяет с помощью одной такой функции получить набор квазиортогональных последовательностей Quasi-Orthogonal Function Set (QOFS). С помощью m маскирующих функций и ансамбля кодов Уолша длиной 2 n можно создать (m+1) 2 n QOF-последовательностей.

2. Еще один недостаток ортогональных кодов (не исключение – и применяемые в стандарте IS-95) заключается в том, что функция взаимной корреляции равна нулю лишь «в точке», т.е. при отсутствии временного сдвига между кодами. Поэтому такие сигналы используются лишь в синхронных системах и преимущественно в прямых каналах (от базовой станции к абоненту).

Возможность адаптации системы CDMA к различным скоростям передачи обеспечивается за счет использования специальных ортогональных последовательностей с переменным коэффициентом расширения спектра (OVSF, Orthogonal Variable Spreading Factor), называемых кодами переменной длины. При передаче CDMA-сигнала, который создавался с помощью такой последовательности, чиповая скорость остается постоянной, а информационная скорость изменяется кратно двум. В стандартах 3-го поколения предлагается использовать в качестве OVSF-кодов ортогональные коды Голда с кратными скоростями передачи (multirate). Принцип их образования достаточно прост; его поясняет рис. 3, где приведено кодовое дерево, позволяющее строить коды разной длины.

Кодовое дерево для генерации OVS-кодов (SF – коэффициент расширения)

Каждый уровень кодового дерева определяет длину кодовых слов (коэффициент расширения спектра, SF), причем на каждом последующем уровне возможное число кодов удваивается. Так, если на уровне 2 может быть образовано только два кода (SF=2), то на уровне 3 генерируются уже четыре кодовых слова (SF=4) и т.д. Полное кодовое дерево содержит восемь уровней, что соответствует коэффициенту SF=256 (на рисунке показаны лишь три нижних уровня).

Таким образом, ансамбль OVSF-кодов не является фиксированным: он зависит от коэффициента расширения SF, т.е. фактически – от скорости канала.

Следует отметить, что не все комбинации кодового дерева могут быть одновременно реализованы в одной и той же соте CDMA-системы. Главное условие выбора комбинации – недопустимость нарушения их ортогональности.

Псевдослучайные последовательности

Наряду с ортогональными кодами ключевую роль в CDMA-системах играют ПСП, которые хотя и генерируются детерминированным образом, обладают всеми свойствами случайных сигналов. Однако они выгодно отличаются от ортогональных последовательностей инвариантностью к временному сдвигу. Существует несколько видов ПСП, обладающих разными характеристиками. Говоря попросту, сегодня появились технические средства, способные «вывести» любой ансамбль последовательностей с заданными свойствами.

m-последовательности

Функция автокорреляции m-последовательности является периодической и двузначной:

Автокорреляционная функция для m-поседовательности: а) апериодическая, б) периодическая

Уровень побочных максимумов автокорреляционной функции (рис. 4) не превышает значения

Коды Голда и Касами

Коды Голда формируются путем посимвольного сложения по модулю 2 двух m-последовательностей (рис. 5). В проекте WCDMA специфицированы три типа кодов Голда: первичный и вторичный ортогональные коды Голда (оба длиной 256 бит) и длинный код.

Генератор кодов Голда (T – элемент регистра сдвига; & – схема совпадения; + – сумматор по модулю 2)

Ортогональные коды Голда создаются на основе m-последовательности длиной 255 бит с добавлением одного избыточного символа. Первичный синхрокод имеет апериодическую автокорреляционную функцию и используется для первоначального вхождения в синхронизм. Вторичный синхрокод представляет собой немодулированный ортогональный код Голда, который передается параллельно с первичным синхрокодом. Каждый вторичный синхрокод выбирается из 17 различных кодов Голда .

Длинный код для прямого канала представляет собой фрагменты кода Голда длиной 40 960 чипов. Система связи на базе WCDMA асинхронна, и соседние базовые станции используют различные коды Голда (всего их 512), повторяемые каждые 10 мс. Асинхронный принцип работы базовых станций делает их независимыми от внешних источников синхронизации. Предполагается применять длинный код и в обратном канале, однако только в тех сотах, где не задействуется режим многопользовательского детектирования.

Кодовые последовательности Касами реализуются с помощью трех последовательно включенных регистров сдвига (u, v и w) с различными обратными связями (рис. 6), каждый из которых формирует свою m-последовательность. Чтобы получить кодовые последовательности Касами с заданными свойствами, последовательности v и w должны иметь различные сдвиги.

Генератор кодов Касами типа kas (6, m, k), где m и k – циклические сдвиги v- и w-кодов соответственно (см. условные обозначения к рис. 5)

Коды Касами длиной 256 бит используются в качестве коротких последовательностей в обратном канале (проект WCDMA) в тех сотах, в которых применяется многопользовательское детектирование.

Последовательности Баркера

Псевдослучайные последовательности с малым значением апериодической АКФ способны обеспечить синхронизацию передаваемых и принимаемых сигналов за достаточно короткий промежуток времени, обычно равный длине самой последовательности. Наибольшую известность получили последовательности Баркера (см. таблицу).

Эффективность последовательностей с апериодической АКФ принято оценивать показателем качества F, который определяется как отношение квадратов синфазных составляющих сигнала к сумме квадратов его расфазированных составляющих. Таким образом, мерой эффективности апериодической корреляции двоичной последовательности является показатель качества.

Поделитесь материалом с коллегами и друзьями

Источник

Коды Голда

Коды Голда — тип псевдослучайных последовательностей. Значимость этих последовательностей происходит из-за их очень низкой взаимной корреляции. Применяются в CDMA и GPS.

Оптимальные автокорреляционные свойства могут быть получены и для М-последовательностей, однако, для реализации принципа коллективного доступа необходим большой набор кодов одинаковой длины с хорошими взаимокорреляционными свойствами. Поэтому используется особый класс ПШ-последовательностей, который называют последовательностями Голда. Коды Голда не только позволяют получить большой набор последовательностей, но также и однородные и ограниченные значения взаимокорреляционной функции. Коды Голда хорошо подходят для использования в качестве длинных скремблирующих кодов для беспроводного множественного доступа с кодовым разделением каналов ( кодов Голда для передачи информации от базовой станции к подвижному объекту, и кодов усеченной последовательности для обратного направления).

Последовательности Голда могут быть сгенерированы путем суммирования по модулю 2 двух М-последовательностей одинаковой длины. Результирующие Коды Голда имеют ту же самую длину как и исходные М-последовательности.

Ниже приведены предпочтительные пары М-последовательностей для генерации кодов Голда, число сгенерированных кодов Голда равно , где m — длина сдвигового регистра, длина кода равна . Нормализованная ВКФ принимает одно из трех значений в зависимости от m.

Полезное

Смотреть что такое «Коды Голда» в других словарях:

Псевдослучайная двоичная последовательность — частный случай ПСП, в которой элементы принимают два возможных значения 0 и 1 (или 1 и +1 ). Постулаты Голомба Одна из первых формулировок некоторых основополагающих правил для статистических свойств периодических псевдослучайных… … Википедия

Проект «Венона» — (англ. Project Venona) кодовое название секретной программы контрразведки США по расшифровке советских шифрованных донесений, начатой 1 февраля 1943 года и закрытой 1 октября 1980 года. Проект позволил оценить масштаб советского… … Википедия

Израиль — У этого термина существуют и другие значения, см. Израиль (значения). Государство Израиль מדינת ישראל Мединат Исраэль دولة إسرائيل‎ Даулат Исра’иль … Википедия

Список серий мультсериала «Новый Капитан Скарлет» — Основная статья: Новый Капитан Скарлет Содержание 1 1 сезон 1.1 Орудие Уничтожения Часть. 1 1.2 … Википедия

Тракайский диалект караимского языка — Самоназвание: Karaj tili Страны … Википедия

Список эпизодов мультсериала «Лига справедливости» — Лига справедливости (англ. Justice League), позже Лига справедливости: Без границ (англ. Justice League Unlimited) американский сериал по мотивам комиксов компании DC Comics о команде супергероев, борющихся со злом в мире. Оригинальный… … Википедия

Источник