Теория алгоритмов и вычислительных процессов

 

 

 

 

 

Пояснительная записка

 к курсовому проекту

 по курсу «Теория  алгоритмов и вычислительных  процессов»

 

 

 

 

 

 

Выполнил:

Студент группы

__________/./

“____”______________201г.

Руководитель проекта:

__________/./

“____”______________201г.

 

 

 

 

 

 

 

Оглавление

 

 

1. Вступление.

Данный курсовой проект является разработкой и исследованием алгоритма и прикладной программы моделирования автономной матричной линейной последовательностной машины (АМЛПМ) над полем GF(р).

Данная тема является актуальной, так как линейные последовательностные машины (ЛПМ) широко применяются в автоматике и вычислительной технике в качестве генераторов последовательностей, счетчиков, кодирующих и декодирующих устройств, устройств обнаружения а исправления ошибок, при моделировании нейронных сетей и т. д.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Краткие теоретические сведения

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

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

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

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

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

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

Псевдослучайная двоичная последовательность — частный случай ПСП, в которой элементы принимают два возможных значения 0 и 1 (или -1 и +1 ).

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

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

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

3) Предположим, у нас есть две копии одной и той же последовательности периода p, сдвинутые относительно друг друга на некоторое значение d. Тогда для каждого d, 0 <= d <= p-l, мы можем подсчитать количество согласованностей между этими двумя последовательностями Ad, и количество несогласованностей Dd. Коэффициент автокорреляции для каждого d определяется соотношением (Ad - Dd)/p и эта функция автокорреляции принимает различные значения по мере того, как d проходит все допустимые значения. Тогда для любой последовательности, удовлетворяющей правилу 3, автокорреляционная функция (АКФ) должна принимать лишь два значения.

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

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

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

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

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

М-последовательности или последовательности максимальной длины (англ. Maximum length sequence, MLS) — псевдослучайные последовательности, нашедшие широкое применение в широкополосных системах связи. Как правило, используются двоичные М-последовательности, члены которых состоят из чисел 1 и 0.

Одно из наиболее простых  и чрезвычайно эффективных средств  генерации двоичных детерминированных последовательностей – использование регистра сдвига (РС). Последовательность на выходе n-разрядного РС с обратной связью всегда периодична, причем ее период n (число тактов, через которое схема возвращается в исходное состояние) не превышает 2ⁿ.

Теоретически, используя n-разрядный регистр и соответствующим  образом подобранную логику обратной связи, можно получить последовательность любой длины N в пределах от 1 до 2ⁿ включительно. Последовательность максимальной длины, или m-последовательность, будет иметь период 2ⁿ-1.

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

1. М-последовательности являются периодическими с периодом N = 2ⁿ − 1;
2. количество символов, принимающих значение единица, на длине одного периода М-последовательности на единицу больше, чем количество символов, принимающих значение нуль;
3. любые комбинации символов длины n на длине одного периода М-последовательности за исключением комбинации из n нулей встречаются не более одного раза. Комбинация из n нулей является запрещённой: на её основе может генерироваться только последовательность из одних нулей;
4. сумма по mod 2 любой М-последовательности с её произвольным циклическим сдвигом также является М-последовательностью;
5. периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный (− 1 / N).

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

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

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

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

В CDMA-системах чаще всего применяются  псевдослучайные последовательности Голда и, обеспечивающие малый уровень  выбросов ВКФ. Коды Голда с периодом 2ⁿ-1 формируются на основе двух m-последовательностей с отбором так называемых «предпочтительных пар» (preferred pairs), имеющих трехзначную функцию автокорреляции (-1,-о?(t), о? (t)-2), где

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

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

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

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

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

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

Коды Касами — тип псевдослучайных последовательностей. Применяются в CDMA. Значимость этих последовательностей происходит из-за их очень низкой взаимной корреляции. Код Касами длины N = 2^m − 1, где m — четное целое число, может быть получен, беря периодические выборки из М-последовательности и выполняя суммирование по модулю 2 на циклически сдвигаемых последовательностях. Выборки берутся через каждые s = 2^{m / 2} + 1 элементов М-последовательности, чтобы сформировать периодическую последовательность и затем прибавляя эту последовательность постепенно к первоначальной М-последовательности по модулю 2, чтобы сформировать s = 2^{m / 2} последовательностей Касами. Взаимная корреляционная функция двух последовательностей Касами принимает значения [-1, -s, s-2].

Семейство кодов Касами содержит 2^к последовательностей с периодом 2^n-1. Они считаются оптимальными в том смысле, что для любой «предпочтительной» пары обеспечивается максимальное значение автокорреляционной функции, равное (1+2^к).

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

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

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

к рис. 1.2)

 

 

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

Последовательность Баркера — это числовая последовательность a₁, a₂, …, a_N, где каждый элемент равен +1 или -1, причём, , для всех .

Последовательности Баркера  имеют минимальный уровень боковых  лепестков автокорреляционной функции 1/N.

Последовательность Баркера  с 11 членами используется в цифровых системах передачи данных.

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

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

Таблица 2.2.1. – Структура последовательности Баркера (N = 7, 11, 13)

Длина	Вид последовательности	Показатель качества
7	+1 +1 +1 −1 −1 +1 −1	9,85
11	+1 +1 +1 −1 −1 −1 +1 −1 −1 +1 −1	12.1
13	+1 +1 +1 +1 +1 −1 −1 +1 +1 −1 +1 −1 +1	14.08