автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Применение ранговых кодов в системах связи с ортогональным частотным уплотнением

Московский физико-технический институт (государственный университет)

На правах рукописи

СЫТНИК ДМИТРИЙ АЛЕКСАНДРОВИЧ

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

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2005 г.

Работа выполнена в Московском физико-техническом институте (Государственном университете).

Научный руководитель:

доктор технических наук, профессор,

Габидулин Эрнст Мухамедович

Официальные оппоненты: доктор технических наук,

профессор, Арепин Юрий Иович

кандидат технических наук, доцент,

Романюк Юрий Андреевич

Ведущая организация:

Тверской Государственный университет

Защита состоится 24 мая 2005 г. в 15 часов на заседании диссертационного совета К212.156.04 в Московском физико-техническом институте (Государственном университете) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., 9, ауд. 204 Нового корпуса.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).

Автореферат разослан " ^ " апреля 2005 г.

Ученый секретарь диссертационного совета К212.156.04, к.т.н., доцент

Куклев Л. П.

Общая характеристика работы

Актуальность темы исследования.

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

Многоканальная система с ортогональным частотным уплотнением (OFDM) утверждена в качестве стандарта для беспроводных локальных сетей нового типа IEEE 802.11a, High Performance LAN type 2 и мобильных систем связи одновременного доступа. В настоящее время OFDM также используется в европейских системах цифрового телерадиовещания.

В то же время, в системе передачи данных неизбежно возникают ошибки, для борьбы с которыми используется избыточное кодирование. Основные направления исследований в этой области направлены на построение кодов в хэмминговой метрике, и хорошие результаты в системах OFDM дает применение кодов Рида-Соломона с использованием перемежения.

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

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

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

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

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

1. Интеграция нового класса кодов в систему связи с OFDM.

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

3. Оценка эффективности применения ранговых кодов в OFDM системе и сравнение с другими существующими методами кодирования.

4. Метод повышения помехоустойчивости системы связи с ортогональным частотным уплотнением при использовании симметричных ранговых кодов.

5. Использование системы связи с ранговыми кодами для комбинированной защиты информации от ошибок в канале и несанкционированного доступа.

Для решения поставленной задачи в работе использовались Методы теории кодирования, алгебры, теории вероятностей, теории алгоритмов, компьютерного моделирования.

Научная новизна результатов, полученных в диссертации, заключается в следующем:

1. Реализованы программные методы рангового кодирования и декодирования.

2. Проведена оценка эффективности применения ранговых кодов в OFDM системе по сравнению с кодами Рида-Соломона в широком

спектре параметров системы, параметров канала передачи данных, параметров кодирования.

3. Разработан метод повышения помехоустойчивости систем связи с OFDM за счет использования симметричных кодов.

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

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

Научные положения, выносимые на защиту.

1. Программная реализация модели OFDM системы в среде Matlab с возможностью применения различных классов кодов.

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

3. Впервые реализована OFDM система с комбинированной защитой от ошибок канала и несанкционированного доступа.

Апробация работы. Результаты диссертации докладывались на российских и международных конференциях:

— The 9th International Workshop On Algebraic And Combinatorial Coding Theory - ACCT-DC, Kranevo, BULGARIA, 2004;

— XLV, XLVI ежегодных научных конференциях Московского физико-технического института, Москва-Долгопрудный, 2002-2003.

Основные результаты диссертации неоднократно обсуждались на научных семинарах кафедры радиотехники МФТИ.

Публикации. По теме диссертации опубликовано 5 работ, из них 3 статьи в научных журналах и сборниках научных статей, тезисы 2-х докладов на научных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы, состоящего из 34 наименований, и приложения с примерами программного кода. Объем диссертации без приложений — ПО страниц.

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

Первая глава посвящена изложению основ теории кодирования, необходимых для замкнутости изложения

В первом параграфе рассматриваются общие понятия теории кодирования. Рассматриваются блоковые и неблоковые коды, вводится понятие нормы и метрики, описываются линейные коды.

В втором параграфе кратко описываются коды Рида-Соломона (РС коды). Дается определение РС кодов, описывается алгоритм кодирования и принцип декодирования РС кодов.

В третьем параграфе приводятся известные результаты из теории ранговых кодов. Дается определение кодов с максимальным ранговым расстоянием. Описываются процедуры кодирования и декодирования. Для декодирования ранговых кодов можно использовать два метода: метод Евклида, основанный на применении линеаризованных многочленов над , и матричный метод. С увеличением ранга ошибки вычислительная трудоемкость матричного метода растет быстрее, чем при использовании метода Евклида.

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

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

релеевские замирания, частотнозависимые замирания, задержка, шум канала.

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

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

В четвертом и пятом параграфах описываются основные принципы, лежащие в основе построения систем связи с OFDM: применение преобразования Фурье и использование циклического префикса.

В шестом параграфе рассмотрены принципы модуляции, используемые в системе с OFDM.

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

Во втором параграфе дана схема программной реализации модели системы с OFDM.

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

Кроме характерных для OFDM блоков, модель содержит интерфейс, позволяющий применять ранговое и PC кодирование.

Рис. 1. Модель OFDM системы

Третий параграф содержит описание блоков модели:

1. Генератор двоичной последовательности. Выдает случайный двоичный сигнал (0,1). Сигнал представляется в виде информационной матрицы, строки которой передаются в дальнейшие блоки обработки.

2. Ранговое или PC кодирование. В работе исследовались ранговые и PC коды с различными параметрами.

3. Перемежение. Устройство предназначено для более эффективной борьбы с пакетами ошибок.

4. Модулятор. В модели применяется фазовая модуляция (Phase Shift Keying, PSK) и квадратурная амплитудная модуляция (Quadrature Amplitude Modulation, QAM).

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

6. ОДПФ. Обратное дискретное преобразование Фурье. Основной элемент OFDM системы, формирующий спектр сигнала и обеспечивающий ортогональность частот.

7. Циклическое расширение. Данный элемент OFDM системы используется для борьбы с межсимвольными взаимодействиями, обусловленными задержкой сигнала. Реализация циклического расширения заключается в том, что в начало информационного сигнала добавляются несколько последних элементов информационного сигнала.

8. Фильтр многолучевого распространения. В качестве канала рассматривался канал передачи данных с релеевскими замираниями (несколько лучей от источника сигнала, приходящих в приемное устройство). Релеевские замирания характеризуются памятью канала и глубиной (уровнем) замираний.

9. Частотно-зависимые замирания. Редкие замирания, проявляющиеся в том, что в отклике канала на какой-либо поднесущей может происходить значительное ослабление. Характеризуются вероятностью появления, количеством искаженных поднесущих и глубиной спада сигнала.

10. Импульсная помеха. Редкие замирания, проявляющиеся в том, что в какой-то момент времени возникает импульсная помеха, перекрывающая в OFDM системе весь диапазон частот, занимаемый спектром передаваемого символа. Характеризуется вероятностью появления и амплитудой импульса.

11. Гауссов шум. Аддитивный гауссов шум, уровень которого характеризуется отношением сигнал/шум в канале.

12. Устранение циклического расширения. Из информационной последовательности удаляются лишние символы, возникающие на этапе циклического расширения.

13. ДПФ. Дискретное преобразование Фурье.

14. Оценка отклика канала. На первом шаге приема данных оценивается отклик канала на переданную известную пилотную последовательность, на других шагах вносится поправка в оценку отклика на основе пилотных сигналов.

15. Восстановление после перемежения. Выполняется операция, обратная перемежению.

16. Демодулятор. При демодуляции для каждого принятого сим-

вола происходит поиск ближайшего к нему элемента созвездия.

17. Декодирование. Исправляет ранговые ошибки, если их количество не более максимальной корректирующей способности кода, в противном случае фиксирует ошибку декодирования.

18. Мягкое декодирование. Для PC кодов удаляются наиболее ненадежные столбцы, для ранговых наиболее ненадежные строки и столбцы (стирание), далее происходит проверка возможности декодирования оставшейся части полученной информационной матрицы.

В четвертом параграфе дано описание программной реализации общих конструкций ранговых кодов.

Исходя из задач работы, были сформулированы следующие требования к данному программному модулю:

• Быстрота исполнения программного кода.

• Возможность применения в различных реализациях.

Поэтому в качестве инструмента реализации был выбран язык программирования C + + (в текущей реализации использовался компилятор VC++ 6.0, VC+- 7.0) с использованием стандартной библиотеки шаблонов.

Модуль состоит из следующих классов:

• Класс bin_matrix описывает двоичные матрицы и базовые операции над ними.

• Класс gf_element описывает элементы поля GF(2N) и базовые операции над ними.

• Класс gfmatrix. Аналогичен bmmatrix, но элементами матриц являются элементы поля

• Класс poly описывает линеаризованные многочлены надСР(2^)

• Класс rank_codec описывает ранговые коды и позволяет осуществлять кодирование, два различных способа жесткого декодирования (матричный и евклидовый), и мягкое декодирование (исправление ошибок и стираний).

Диаграмма классов приведена на рис. 2.

Рис. 2. Структура классов рангового кодера / декодера.

В Четвертой главе приведены результаты сравнения эффективности применения ранговых и PC кодов в OFDM системе при различных значениях ее параметров.

В первом параграфе обосновывается выбор параметров моделирования. Моделирование осуществлялось при различных параметрах кодирования (длине и размерности кода, использовании перемежения), параметрах OFDM системы (вид модуляции и количеств несущих), параметрах канала. Исходя из практических применений, рассматривались каналы с зашумленными и зашумленными условиями.

Зашумленные условия характеризуются следующим набором параметров:

• Отсутствие прямого луча распространения сигнала.

• Пять лучей, приходящих в приемник.

• Коэффициент ослабления сигнала 0.9.

• Вероятность импульсной помехи на OFDM символ 1е-3.

• Вероятность возникновения неравномерности отклика канала на OFDM символ 1е-3.

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

Незашумленные условия характеризуются следующим набором параметров:

• Наличие прямого луча распространения сигнала.

• Два луча, приходящих в приемник.

• Вероятность импульсной помехи на OFDM символ 1е-5.

• Вероятность возникновения неравномерности отклика канала на OFDM символ 1е-5.

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

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

В третьем параграфе дано сравнение эффективности ранговых кодов с кодами Рида-Соломона. Для каждого вида модуляции сравнивалась эффективность кодирования в зашумленых и незашумленных условиях при наличии и отсутствии перемежения. При этом рассматривались коды (16,8) и OFDM система с 16 несущими.

Исходя из критериев, используемых для оценок эффективности кодирования, будем говорить, что коды сравнимы по эффективности, если разница в результате их применения не превышает 1—2 дБ. Будем говорить, что один код эффективнее другого, если его применение дает выигрыш 2—5 дБ.

Часть результатов моделирования, полученных в работе, приведена на рис. 3. На графиках приведены зависимости вероятности ошибки на бит переданного символа от отношения сигнал/шум в канале, выраженного в дБ.

На рис. 3.1, 3.2 приведены результаты моделирования для модуляции 2psk в незашумленных условиях. Перемежение практически не оказывает влияния на эффективность рангового кодирования. Значительно сказывается влияние перемежения на эффективность PC кодов: на рис. 3.1 происходит быстрый спад ошибок в диапазоне 0-8 дБ, а на рис. 3.2 спад более плавный.

на бит переданного символа от величины отношения сигнал/шум в

канале, дБ.

Ошибка декодирования РС кодов выходит практически на постоянный уровень (7е-5), который целиком определяется импульсной помехой и частотно-зависимыми замираниями. Ошибка же рангового кодирования продолжает монотонно падать.

На рис. 3.3,3.4 приведены результаты моделирования для модуляции

4psk в незашумленных условиях. Качественно результаты аналогичны результатам для 2psk. Перемежение оказывает лишь незначительное количественное влияние на эффективность рангового кодирования. Хорошо видно влияние перемежения на эффективность PC кодов: на рис. 3.3 происходит быстрый скачкообразный спад ошибок в диапазоне 0-10 дБ, а на рис. 3.4 спад более плавный.

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

На рис. 3.5, 3.6 приведены результаты для модуляции 16qam в незашумленных условиях. Так же, как и в предыдущем случае (модуляция 4psk), перемежение оказывает лишь незначительное количественное влияние на эффективность рангового кодирования в незашумленных условиях. Перемежение оказывает значительное влияние на результаты для PC кодов.

Ошибка декодирования PC кодов выходит практически на постоянный уровень ( 1е-4). Уровень ошибки PC кодов целиком определяется импульсной помехой и частотно-зависимыми замираниями. Ошибка же рангового кодирования продолжает монотонно падать.

В четвертом параграфе исследуется зависимость эффективности применения ранговых и PC кодов от длины кода и числа несущих. При рассмотренных параметрах ранговый код показывает лучшие результаты при отношении сигнал/шум (signal to noise ratio, snr) snr>12 дБ.

Пятая глава посвящена применению симметричных ранговых кодов в OFDM системах.

В первом параграфе описываются матричное и векторное представление ранговых кодов, а также отображения для переходов от матричного представления к векторному и наоборот.

Во втором параграфе описываются симметричные матрицы, представляющие поле, и конструкция для построения таких матриц.

В третьем параграфе описывается построение симметричного рангового кода с помощью симметричных матриц, представляющих поле.

В четвертом параграфе представлена программная реализация симметричного рангового кодера, построенная на базе описанного в Гла-

ве 3 объектно-ориентированного модуля рангового кодирования. Такой подход позволил воспользоваться всеми достоинствами разработанного модуля рангового кодера и сократить время на реализацию.

Для реализации методов, необходимых для построения симметричных кодов, к программному коду были добавлены следующие классы:

• Класс bin_poly описывает многочлены с коэффициентами из GF(2) и действия над ними.

• Класс sym_matrix_generator реализует подготовительные функции для симметричных матриц, представляющих поле.

• Класс sym_matrix_codec реализует операции кодирования и декодирования симметричных ранговых кодов.

В четвертом параграфе рассматривается применение симметричных ранговых кодов в OFDM системе. Для повышения эффективности исправления ошибок передачи по сравнению с общими конструкциями ранговых кодов исследованы два метода.

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

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

На рис. 4.1 показаны результаты моделирования при 8 несущих и незашумленных условиях. Видно, что в интервале 1-5 дБ применение симметричного кода дает несколько лучшие результаты, чем общей конструкции рангового кода. Однако для общей конструкции рангового кода ошибка продолжает монотонно падать с уменьшением шума канала от 5 до 10 дБ, а для симметричного она выходит на практически постоянный уровень 1.5е - 5, вокруг которого происходят колебания. Таким образом, при небольших значениях шума, когда влияние шума менее значительно, чем влияние импульсных помех и частотно-зависимых

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

На рис. 4.2 показаны результаты моделирования при 8 несущих и зашумленных условиях. Видно, что эффективность кодов сравнима в интервале 0-10 дБ, далее ранговый код лучше. В целом наблюдается практически линейное падение уровня ошибок во всем исследуемом интервале для обеих кривых. Как и на предыдущем рисунке, при больших значениях шума, когда больший вес вносят нелинейные импульсные ошибки, эффективность симметричного кода меньше.

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

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

пытка декодирования полученной матрицы. В случае, если происходит отказ от декодирования, выполняется симметризация матрицы и повторная попытка декодирования. Примеры результатов моделирования при использовании метода приведены на рис. 4.3,4.4.

Как видно из рис. 4.3, происходит быстрый, близкий к линейному, спад ошибок в интервале отношения сигнал/шум 0-6 дБ и затем более медленный. Во всем интервале значений симметричный код эффективнее. Сходную картину с большим уровнем ошибки можно наблюдать на рис. 4.4. Во всем интервале значений отношения сигнал/шум симметричный код эффективнее.

Анализ результатов показывает, что предложенный метод позволяет повысить эффективность декодирования на 2-6 дБ в зависимости от параметров канала передачи данных.

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

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

Во втором параграфе кратко описывается система ГПТ (Габидулина, Парамонова и Третьякова) и основные атаки на данную систему.

В третьем параграфе рассматриваются приводимые ранговые коды, и процедуры кодирования и декодирования.

В четвертом параграфе представлена система на основе приводимых ранговых кодов и проанализированы ее свойства.

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

Для реализации рассматриваемой системы в исходный текст рангового кодера были добавлены следующие классы:

• Класс reducible_codec, реализует функциональность приводимых ранговых кодов.

• Класс crypto_system, реализует непосредственно систему.

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

^90 13 3 /ч 200

криптостойкость 2 , 2 , 2 операций в gf(2) соответственно.

Таблица 1. Тараметры используемых систем.

Параметры Система 1 Система 2 Система 3

N ■ 29 41 53

п 58 82 106

к 30 50 62

Ь 7 8 11

Длина ключа, Кбит 50 168 348

Скорость передачи 0.52 0.61 0.58

данных

Стойкость к прямым 2» 2Ш 2200

атакам в (?Р(2)

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

В шестом параграфе предлагается метод выбора параметров системы для достижения требуемых значений стойкости и помехоустойчивости.

Рис. 5. Система 3, зашумленные условия.

В заключении перечислены основные результаты диссертационной работы:

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

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

• Исследованы сравнительные возможности ранговых кодов и кодов Рида-Соломона в OFDM системах. Выявлен диапазон физических условий передачи данных и параметров системы, при которых ранговые коды обладают значительно лучшими характеристиками. В частности, ранговые коды значительно эффективнее PC кодов при

использовании модуляции 2psk и 4psk при наличии (даже достаточно редких) импульсных помех и частотно-зависимых замираний. На основе результатов сравнения сформированы рекомендации по применению таких кодов в OFDM системе.

• Предложен метод применения симметричных ранговых кодов в OFDM системе, позволяющий повысить эффективность декодирования на 2-6 дБ по сравнению с ранговыми кодами.

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

В приложении приводятся участки программного кода модели и рангового кодера/декодера.

Рекомендации. Кратко сравнение эффективности ранговых кодов и PC кодов можно отобразить в виде таблицы (snr — отношение сигнал/шум в канале):

Таблица 2. Сравнительная эффективность ранговых и PC кодов

Тип модуляции Сравнительная эффективность кодов

2psk Ранговые коды значительно эффективнее практически во всех случаях

4psk Ранговые коды значительно эффективнее, если не используется перемежение. При использовании переме-жения эффективность сравнима в диапазоне впг=0-7 дБ, при большем эпт ранговые коды эффективнее.

16qam Ранговые коды сравнимы по эффективности либо знаг чительно эффективнее, если не используется перемежение. При использовании перемежения ранговые коды сравнимы по эффективности при впг<15 дБ, при большем 8пг ранговые коды эффективнее.

64<}ат Ранговые коды сравнимы по эффективности при впг<20 дБ либо эффективнее, если не используется перемежение. При использовании перемежения ранговые коды эффективнее при впг>20дБ.

256qam Качественно ранговые коды эффективнее, если не используется перемежение и зпг>30дБ.

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

Эффективность ранговых кодов по сравнению с PC кодами снижается по мере усложнения применяемой модуляции, поэтому наиболее эффективно применение ранговых кодов при использовании простых видов модуляции (2 psk, 4psk). При сложных видах модуляции и использовании перемежения ранговые коды эффективнее при достаточно больших отношениях сигнал-шум (snr>20 дБ).

Дополнительное повышение помехоустойчивости систем с OFDM достигнуто за счет применения симметричных ранговых кодов. Использование метода симметризации матрицы в случае отказа от декодирования позволяет повысить эффективность на 2-6 дБ.

Программное обеспечение крпитозащиты, основанной на приводимых ранговых кодах, позволяет решать комбинированную задачу обеспечения конфиденциальности и помехозащищенности передаваемых данных. Криптосистема обеспечивает криптостойкость до 2250 операций в GF(2) при снижении помехоустойчивости на 2-5 дБ.

Результаты диссертации изложены в следующих работах

1. Э.М. Габидулин, Д.А. Сытник. Ранговые коды в системе связи с ортогональным частотным уплотнением// Электронный журнал "Исследовано в России", 155, стр. 1673-1690, 2004 г. http://zhumal.ape.relarn.ru/articles/2004/155.pdf

2. Э.М. Габидулин, Д.А. Сытник, А.А. Вакуленко, В.Н. Тикме-нов. Повышение помехоустойчивости систем связи с ортогональ-

ным частотным уплотнением за счет применения рангового кодирования. // Радиотехника (журнал в журнале), 2004, 5.

3. D.A. Sytnik, A.M. Bibikov. Applications ofthe cryptographic system based on reducible rank codes in OFDM. // The 9th International Workshop On Algebraic And Combinatorial Coding Theory — ACCT-IX, Kranevo, BULGARIA, 2004.

4. Д.А. Сытник. Преимущества применения ранговых кодов в системах многоканальной связи с ортогональным частотным уплотнением. // XLVI научная конференция МФТИ (2003 год).

5. Д.А. Сытник. Характеристики системы OFDM, использующей ранговые коды. // XLV научная конференция МФТИ (2002 год).

Сытник Дмитрий Александрович

ПРИМЕНЕНИЕ РАНГОВЫХ КОДОВ В СИСТЕМАХ СВЯЗИ С ОРТОГОНАЛЬНЫМ ЧАСТОТНЫМ УПЛОТНЕНИЕМ Изд. лиц. ИД .№ от Подписано в печать.

Формат 60 х 84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1.3. Тираж 70 экз. Заказ №152

Московский физико-технический институт (государственный университет) Отдел автоматизированных издательских систем "ФИЗТЕХ-ПОЛИГРАФ" 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Où./я7--0SJ3

. ■ i ч

i ?ч?!

V !¿ i /

X „ -

19 ;лди 2005

Введение

I 1 Необходимые сведения из теории кодирования

1.1 Основные понятия.

1.2 Коды Рида-Соломона.

1.2.1 Кодирование.

1.2.2 Декодирование.

1.3 Ранговые коды

1.3.1 Основные понятия и определения.

1.3.2 Линеаризованные многочлены.

1.3.3 Алгоритмы кодирования и декодирования.

1.3.4 Введение ранговых стираний.

2 Принципы построения систем связи с ортогональным частотным уплотнением

0 2.1 Особенности беспроводной передачи данных.

2.1.1 Ослабление сигнала.

2.1.2 Релеевское замирание.

2.1.3 Частотно-зависимые замирания

2.1.4 Задержка.

2.1.5 Доплеровский сдвиг.

2.2 Многоканальная передача данных.

2.3 Спектр OFDM сигнала.

2.4 Применение преобразования Фурье.

2.5 Защитный временной интервал и циклический префикс.

2.6 Фазовая и амплитудная модуляция.

3 Построение модели системы связи с ортогональным частотным уплотнением

3.1 Особенности канала передачи.

3.1.1 Модель канала с замираниями.

3.1.2 Использование пилотных сигналов.

3.1.3 Перемежение.

3.2 Построение модели системы передачи данных.

3.3 Основные блоки модели.

4 Сравнительная оценка эффективности ранговых и PC кодов

4.1 Влияние порога ненадежности символов при мягком декодировании

4.2 Декодирование при различных видах фазовой и амплитудной модуляции

4.2.1 Модуляция 2PSK

4.2.2 Модуляция 4PSK

4.2.3 Модуляция 16 QAM.

4.2.4 Модуляция 64 QAM.

4.2.5 Модуляция 256 QAM.

4.2.6 Сравнение по эффективности ранговых и PC кодов.

4.3 Эффективность декодирования при различных параметрах передачи

5 Симметричные ранговые коды в OFDM системе

5.1 Введение

5.2 Симметричные матрицы, представляющие конечное поле.

5.3 Коды в ранговой метрике на основе симметричных матриц.

5.4 Программная реализация.

5.5 Применение симметричных ранговых кодов.

5.5.1 Выбор параметров моделирования

5.5.2 Декодирование с принудительной симметризацией матрицы

5.5.3 Декодирование с симметризацией при отказе от декодирования

6 Программная реализация криптосистемы на основе приводимых ранговых кодов

6.1 Введение.

6.2 Криптосистема Габидулина, Парамонова и Третьякова.

6.3 Конструкции приводимых ранговых кодов.

6.4 Криптосистема на основе приводимых кодов.

6.5 Программная реализация криптосистемы

6.6 Применение криптосистемы.

6.6.1 Параметры моделирования.

6.6.2 Результаты моделирования.

6.7 Методика выбора параметров криптосистемы на основе приводимых ранговых кодов.

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

Этим требованиям отвечает система многоканальной связи с ортогональным частотным уплотнением (OFDM). OFDM утверждена в качестве стандарта для беспроводных локальных сетей нового типа IEEE 802.11а, High Performance LAN type 2 (HIPERLAN/2) и мобильных систем связи одновременного доступа. В настоящее время OFDM также используется в европейских системах цифрового телерадиовещания [28].

Как известно, при передаче данных по каналам с шумами неизбежно возникают ошибки, для борьбы с которыми обычно используется избыточное кодирование. Основные направления исследований в этой области направлены на построение кодов в хемминговой метрике, и хорошие результаты в системах OFDM дает применение кодов Рида-Соломона, с использованием перемежения.

Однако, хэммингова метрика не всегда хорошо согласуется с реальным каналом связи. Использование кодов в других метриках часто позволяет более полно использовать пропускную способность конкретного канала. С многоканальной системой хорошо согласуется ранговая метрика, исследованная в работах Э.М. Габидулина [2],[3],[17].

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

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

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

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

ЦЕЛЬЮ диссертационной работы является повышение помехозащищенности и обеспечение конфиденциальности передаваемых данных в системе с OFDM.

Для достижения поставленной цели в работе решены следующие ЗАДАЧИ.

1. Интеграция в систему связи с OFDM нового класса кодов, а именно ранговых кодов Габидулина.

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

3. Оценка эффективности ранговых кодов в OFDM системе и сравнение с существующими методами кодирования.

4. Метод повышения помехоустойчивости системы связи с ортогональным частотным уплотнением при использовании симметричных ранговых кодов.

5. Использование системы связи с ранговыми кодами для комбинированной защиты информации от ошибок в канале и несанкционированного доступа.

Для решения поставленной задачи в работе использовались МЕТОДЫ теории кодирования, линейной алгебры, теории вероятностей, теории алгоритмов, компьютерного моделирования.

Научная новизна результатов, полученных в диссертации, заключается в следующем:

1. Впервые реализованы программные методы рангового кодирования и декодирования.

2. Проведена оценка эффективности ранговых кодов в OFDM системе по сравнению с кодами Рида-Соломона в широком спектре параметров системы, параметров канала передачи данных, параметров кодирования.

3. Разработан метод повышения помехоустойчивости систем связи с OFDM за счет использования симметричных кодов.

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

ТЕОРЕТИЧЕСКАЯ И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ.

На основе разработанной модели OFDM системы передачи данных и программной реализации методов рангового кодирования выполнено сравнение эффективности различных методов кодирования. Показано, что ранговые коды в широком диапазоне параметров системы передачи данных, канала передачи и параметров кодирования более эффективны по сравнению с кодами РидагСоломона. Дополнительное увеличение помехоустойчивости достигнуто при применении нового класса ранговых кодов - симметричных ранговых кодов. Программно реализованная криптосистема на основе приводимых ранговых кодов позволяет обеспечить помехозащищенность и конфиденциальность передаваемой информации.

АПРОБАЦИЯ РАБОТЫ. Результаты диссертации докладывались на российских и международных конференциях: the 9th International Workshop On Algebraic And Combinatorial Coding Theory — ACCT-IX, Kranevo, BULGARIA, 2004;

XLIV, XLV, XLVI ежегодных научных конференциях Московского физико-технического института, Москва-Долгопрудный, 2000-2003.

Результаты диссертации обсуждались на научных семинарах кафедры радиотехники МФТИ.

ПУБЛИКАЦИИ. По теме работы опубликовано 5 работ, из них 3 статьи в журналах и сборниках научных статей, 2 работы в виде тезисов докладов на научных конференциях МФТИ.

НАУЧНЫЕ ПОЛОЖЕНИЯ, выносимые на защиту

1. Программная реализация модели OFDM системы в среде Matlab с возможностью применения ранговых и PC кодов.

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

3. Впервые реализованная система OFDM с комбинированной защитой от ошибок канала и несанционированного доступа.

Работа построена следующим образом.

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

Вторая глава посвящена описанию систем связи с OFDM. Рассматриваются физические процессы, возникающие при беспроводной передаче данных, которые необходимо учитывать при построении систем связи. Описывается основной принцип многоканальной связи и принцип построения OFDM системы на базе многоканальной передачи данных. Указываются особенности реализации OFDM системы, которые позволяют использовать достоинства системы многоканальной связи и избежать характерных для таких систем недостатков.

Третья глава подробно описывает реализацию модели системы связи с ортогональным уплотнением с возможностью применения ранговых и PC кодов. Описывается модель канала передачи данных, а также понятие перемежения. Представлен принцип построения имитационной модели OFDM системы, позволяющей сравнивать эффективность кодирования при использовании различных блоковых кодов. Приведена блок-схема построенной модели системы связи и описание особенностей реализации отдельных блоков модели с учетом физических параметров системы. Дано описание программной реализации методов рангового кодирования и декодирования.

В четвертой главе произведено сравнение эффективности ранговых и PC кодов в OFDM системе. Сравнивались результаты прохождения сигнала через модель системы с OFDM при использовании ранговых кодов и кодов Рида-Соломона. Моделирование проводилось при различных параметрах канала передачи, параметрах кодирования и OFDM системы. Приведен анализ полученных результатов.

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

Пятая глава посвящена применению симметричных ранговых кодов в OFDM системах. Дано общее описание симметричных ранговых кодов (/г, 1, п) над GF(qN), и приведены конструкции симметричных ранговых кодов. Приведена программная реализация симметричных ранговых кодов. Скорость реализованного алгоритма декодирования для симметричных ранговых кодов практически совпадает со скоростью алгоритма декодирования ранговых кодов.

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

Предлагаются два метода повышения помехоустойчивости систем связи с OFDM за счет применения симметричных ранговых кодов. Для проверки методов проведено моделирование и сравнение результатов. Первый метод, основанный на принудительной симметризации полученной матрицы, не позволяет добиться существенного увеличения помехоустойчивости. Второй метод основан на симметризации полученной матрицы в случае отказа от декодирования. По сравнению с применением обычного рангового кода применение данного метода позволяет повысить эффективность декодирования на 2-6 дБ. Скорость выполнения алгоритма незначительно падает при этом на 5% по сравнению с алгоритмом декодирования общих конструкций ранговых кодов.

В шестой главе предлагается программная реализация и методика применения криптосистемы на основе приводимых ранговых кодов в системе связи с OFDM.

Во введении этой главы описана общая классификация криптосистем, а также преимущества и недостатки криптосистем на основе линейных кодов. Рассмотрена система ГПТ на базе ранговых кодов. Дан краткий анализ системы ГПТ, преимущества и недостатки системы по сравнению с другими криптосистемами с открытым ключом.

Рассмотрено семейство приводимых кодов в ранговой метрике, алгоритмы кодирования и декодирования. Описано построение и анализ криптосистемы на основе приводимых ранговых кодов. Осуществлена программная реализация криптосистемы на основе приводимых ранговых кодов с использованием объектно-ориентированных технологий программирования на языке С++. Предложен метод применения криптосистемы в системе связи с OFDM. Приведен анализ помехоустойчивости криптосистем при заданной криптостойкости. На основе анализа дана методика выбора параметров криптосистемы для обеспечения требуемой стойкости и помехоустойчивости.

1 Необходимые сведения из теории кодирования

В данной главе приводятся сведения из теории кодирования, необходимые в работе для полноты изложения. Содержание главы основано на материалах [1],[4],[7], [2], [3], [17].

1.1 Основные понятия

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

Блоковое и неблоковое кодирование

Блоковое кодирование состоит в том, что последовательность символов источника сообщений (аь а2,.) разбивается на блоки, например по к символов в каждом: <21 = (аь о2,., ак), а2 — (ак+1,ак+2,., а2к). Кодер преобразует каждый входной к -блок в выходной п -блок хг = х(аг) = (х^сц),., хп(аг)) таким образом, чтобы различным входным блокам соответствовали различные выходные. Ясно, что п> к, так как иначе нашлись бы два различных блока, которым соответствует один и тот же выходной.

Блоковое кодирование можно интерпретировать следующим образом. Будем рассматривать входные к-блоки а = (а1,а2,.--,а0 как буквы укрупненного алфавита Ак. Мощность этого алфавита = дк. Аналогично выходные п-блоки х = (хг, х2, . ■ ■, хп) будем считать буквами укрупненного алфавита Ап. Мощность этого алфавита \Ап\ — г/п. Кодирование ставит в соответствие каждой входной букве а некоторую выходную букву х(а). Совокупность всех таких различных букв х(а) называется блоковым кодом длины п и мощности (или объема) М = дк. Скорость

R= [\ogqM] =к/п. (1.1.1)

Нормы, метрики и кодовые расстояния

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

Определим операции над буквами конечного алфавита А. Будем считать, что алфавит А наделен структурой конечного поля. Над буквами алфавита определены две операции: сложение и умножение.

Рассмотрим произвольный вектор х = ., хп). Нормой или весом Хемминга вектора х называется число его ненулевых координат. Норма вектора х обозначается |£|. Расстоянием Хемминга du(x, у) между векторами хну называется норма их разности: dH(x,y) = \x-y\ (1.1.2)

Рассмотрим код С с векторами жь х2,., хм- Кодовым расстоянием в метрике Хемминга «¿я(С) кода С называют минимальное из попарных расстояний между его векторами:

С1н{С) - min dN(xi, $j) = min \хг - yj\ (1.1.3)

Кодовое расстояние определяет способность кода исправлять ошибки. Пусть, например, d//(C) = d и пусть при передаче некоторого кодового слова х3 по каналу произошли ошибки точно в t позициях этого слова. Тогда существует декодер, который позволяет правильно определить переданное кодовое слово при условии, что

2t < d — 1. (1.1.4)

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

Линейные коды

Совокупность всех векторов длины п с координатами из конечного поля GF(q) называют векторным пространством V над GF(q), если определены операции суммирования любых двух векторов и умножение вектора на любой элемент из GF(q). В общем случае кодом называется любое подмножество векторов. Среди этих подмножеств важную роль играют линейные подпространства.

Любое линейное подпространство С можно задать с помощью базиса из к линейно независимых векторов (1 < к < п ):

9\ = (01ь • • -,9in),92 = (521, • • • ,52п), • • •, <7fc = (9къ ■ ■ ■ ,9кп)

Число к называется размерностью подпространства. Число различных векторов в fc-мерном подпространстве равно qk. Линейным (п, к)-кодом называют к-мерное линейное подпространство. Линейные коды играют важную роль, прежде всего потому, что для них проста процедура кодирования. Для нелинейного кода объемом М = qk необходимо помнить все qk кодовых последовательностей. Для линейного кода можно ограничиться хранением лишь к векторов g\,g-2, ■ ■ ■ ,9к или эквивалентной порождающей матрицы кода т \ / дп

921

G =

Зг \

92

9к)

9ы \

92п 9ki

1.1.5)

9кп /

Для кодирования достаточно задать блок информационных символов а — («х, ., ак). Тогда кодовый вектор получается путем умножения этого вектора на порождающую матрицу С д = аб (1.1.6)

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

GHT = 0.

1.1.7)

Тогда любое кодовое слово удовлетворяет уравнению дЙт = 0.

1.1.8)

Матрица Н называется проверочной матрицей кода. Оба способа задания линейного кода - с помощью порождающей матрицы С и с помощью проверочной матрицы Я эквивалентны. Для любых (п, к) кодов <1 < п—к+1, а коды, для которых достигается равенство, называются разделимыми с максимальным расстоянием (МДР - кодами).

Заключение

Работа посвящена исследованию повышения помехоустойчивости и обеспечения конфиденциальности передаваемых данных в системах связи с ортогональным частотным уплотнением. Широкий спектр практических применений таких систем требует построения кодов, позволяющих исправлять сложные конфигурации ошибок, и обеспечить возможность построения криптосистем на базе таких кодов. Для исследования эффективности методов кодирования была создана модель связи с ортогональным частотным уплотнением. Выполнена программная реализация методов рангового кодирования и декодирования, включая симметричные ранговые коды. Разработана и применена методика сравнения эффективности применения ранговых кодов и кодов Рида-Соломона. Предложен метод применения симметричных ранговых кодов в OFDM системе. На основе приводимых ранговых кодов была создана криптосистема с открытым ключом и интегрирована в систему передачи данных.

Сформулируем основные результаты, полученные в работе.

• Выполнена программная реализация методов рангового кодирования и декодирования. Для реализации использовалась объектно-ориентированна модель программирования, основной упор делался на оптимизации алгоритма для быстрого исполнения под существующие операционные системы и аппаратные платформы. Быстрота декодирования для ранговых кодов 0(п3) операций в GF(2") для кодов длины п.

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

• Исследованы сравнительные способности ранговых кодов и кодов Рида-Соломона в OFDM системах. Выявлен широкий диапазон физических условий передачи данных и параметров системы, при которых ранговые коды показывают значительно лучшие характеристики. В частности, ранговые коды значительно эффективнее PC кодов при использовании модуляции 2PSK и 4PSK при наличии (даже достаточно редких) импульсных помех и частотно-зависимых замираний. На основе результатов сравнения даются рекомендации по применению таких кодов в OFDM системе.

• Выполнена программная реализация методов симметричного рангового кодирования. Предложен метод применения симметричных ранговых кодов в OFDM системе, позволяющий повысить эффективность декодирования на 2-6 дБ по сравнению с ранговыми кодами.

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

1. Берлекэмп <9., Алгебраическая теория кодирования М.: Мир, 1971.

2. Габидулин Э.М., Теория кодов с максимальным ранговым расстоянием // Проблемы передачи информации, 1985. Т. XXI, вып.1, - С. 3-16.

3. Габидулин Э.М., Оптимальные коды, исправляющие ошибки решетчатой конфигурации // Проблемы передачи информации, 1985. Т. XXI, вып.2.

4. Габидулин Э.М., Афанасьев В.Б., Кодирование в радиоэлектронике. М.: Радио и связь, 1986.

5. Гантмахер Ф. Р., Теория матриц. М.: Наука, 1988.

6. Дж. Кларк, мл., Дж. Кейн, Кодирование с исправлением ошибок в системах цифровой связи.- М.: Радио и связь, 1987.

7. Прокис Дж., Цифровая связь. М.: Радио и связь, 2000.

8. Д.А. Ситник, Э.М. Габидулин, Ранговые коды в системе связи с ортогональным частотным уплотнением. // Электронный журнал "Исследовано в России", 155, стр. 1673-1690, 2004 г., // http://zhurnal.ape.relarn.ru/articles/2004/155.pdf

9. Э.М. Габидулин, Д.А. Сытник, A.A. Вакуленко, В.Н. Тикменов, Повышение помехоустойчивости систем связи с ортогональным частотным уплотнением за счет применения рангового кодирования. // Радиотехника (журнал в журнале), 2004, 5.

10. Д.А. Сытник, Преимущества применения ранговых кодов в системах многоканальной связи с ортогональным частотным уплотнением. // XLVI научная конференция МФТИ (2003 год).

11. Д.А. Сытник, A.C. Дементьев, Н.И. Пилипчук, Ранговые коды в системе многоканальной связи с ортогональным частотным уплотнением. // XLIV научная конференция МФТИ (2001 год).

12. Уривский A.B., Система шифрования с открытым ключом на основе расширенных ранговых кодов // тезисы докладов XLII научной конференции МФТИ, Часть IL- Москва Долгопрудный, 1999. - С. 6.

13. Уривский A.B., Декодирование линейных кодов в ранговой метрике // Труды XLIV научной конференции МФТИ. Часть I. Москва - Долгопрудный, 2001. -С.4.

14. А. Barg, Complexity Issues In Coding Theory // Handbook of coding theory. Chapter 7, Amsterdam: Elsevier, 1998. P 649-754.

15. W. E. Diffie, M.E. Helman, New directions in Cryptography // IEEE Trans. Inform Theory, 1976. Vol. 22, еб.- P. 644-645.

16. E. M. Gabidulin, A Fast Matrix Decoding Algorithm for Rank-Error-Correcting Codes. In: Algebraic Coding / Ed. By G.Cohen, S. Litsyn, A. Lobstein, G. Zemor, LNCS 573, 1992. P. 126-133.

17. E. M. Gabidulin Public Key Cryptocsystem Based on Linear Codes Over Large Alphabets: Efficiency and Weakness.- In: Codes and Chipers: Cryptology and coding IV / Ed. By P.G. Farrell.- Formara Limited, Southend-on-Sea, Essex, 1995.- P. 17-32.

18. E.M. Gabidulin, A. Ourivski, V. Pablouchkov, On the Modified Niederreiter Cryptosystem. In: Proceedings of the Information Theory and Networking Workshop - Metsovo, Greece, 1999 - P. 50.

19. E.M. Gabidulin, A. Ourivski, Improved GPT Public Key Cryptosystems.- In: Proceedings of the 5th International Symposium on Communication Theory and Applications.- Ambleside, UK, 1999.- P. 232.

20. E.M. Gabidulin, A. Ourivski, Improved GPT Public Key Cryptosystems.- In: Coding, Communications and Broadcasting / Ed. By P. Farrell, M. Darnell, B. Honary. -London: Research Studies Press, England, 2000. P. 73-102.

21. E.M. Gabidulin, A. Ourivski, B. Honary, B. Ammar, Reducible Rank Codes and Application to Cryptography. In: Information, Coding and Mathematics / Ed. By M. Blaum, P.G. Farrell, H.C.A. van Tilborg. - Boston: Kluwer Academic Publishers, 2002.

22. E.M. Gabidulin, M. Bossert, P. Lusina, "Space-Time Codes Based on Rank Codes, "Proceedings of the 2000 IEEE International Symposium on Information Theory, 25 30 June, 2000, p. 283, Sorrento, Italy.

23. E.M. Gabidulin, N.I. Pilipchuk, Symmetric rank codes and applicatons, "Problems of Information Transmission, 2003.

24. J.K. Gibson, The Security of the Gabidulin Public Key Cryptosystem. In: Advances in Cryptology - EUROCRYPT' 96 / Ed. By U.M. Maurer, LNCS 1070,1996.- P. 212223.

25. E. P. LAWREY,Adaptive Techniques for Multiuser OFDM, Thesis for the degree of Doctor of Philosophy in Electrical and Computer Engineering School of Engineering, James Cook University

26. G. DesBrisay, Basics of Orthogonal Frequency Division Multiplexing (OFDM), 2000, Cisco.com,http: / / www.cisco.com/univercd/cc/td/doc / product / wireless /

27. R. J. McEliece, A public Key Cryptosystem Based on Algebraic Coding Theory // JPL DSL Progress Report 42-44, Jan-Feb. 1978. P. 114^116.

28. A. J. Menezes, Application Of Finite Fields. Boston: Kluwer Academic Publishers , 1993.

29. A. Ourivski, T. Johanson, Decoding Arbitrary Codes In Rank Metric. In: Proceedings of the 8th International Workshop on Algebraic and Combinatorial Coding Theory - ACCT - VIII. - St. Petersburg, Russia, 2002.

30. C.S. Park, Improving Code Rate of McEliece's Public Key Cryptosystem // Electronic Letters 25(21), October 1989.- P-1466-1467.

31. J.R. Riek, Observations on the Application of Error Correcting Codes to Public Key Encryption. In: Proceedings of IEEE International Carnahan Conference on Crime Countermeasures, 1990. - P. 15-18.

32. D.A. Sytnik, A.M. Bibikov, Applications of the cryptographic system based on reducible rank codes in OFDM. // The 9th International Workshop On Algebraic And Combinatorial Coding Theory — ACCT-IX, Kranevo, BULGARIA, 2004.

33. У. Этот сигнал используется при первой передаче для определения отклика У. канала; при этом передаваемый сигнал совпадает с пилотным initialpilotsignal=zeros(N,l); initialpilotsignal(:)=star(l);

34. У. вектор используемый для оценки отклика каналаfading.vectort=zeros(N,l);

35. У. вектор используемый для оценки отклика каналаtinputsignal=zeros(N,1); out=zeros(1,numpoints);outl=zeros(l»num.points); const3=l/(sqrt(2)); impulsecounter=0; •/,-----------------f or pointcoimter=pointco\mter 1: numpoints

36. У. выполняем кодирование, просто накладывая дополнительныеслучайные матрицыrankaddition=randint(n*dim,n-k);rsaddition=randint(m*dim,n-k);ранговое кодированиеrankcodedsignal(:,l:k)=ranksignal;rankcodedsignal(:,k+l:n)=rankaddition;

37. У. кодирование Рида-Соломонаrscodedsignal(:,l:k)=rssignal;rscodedsignal(:,k+l:n)=rsaddition;модуляция полученных кодированных сигналовstarrssignal=sigstar(rscodedsignal,s,0);starranksignal=sigstar(rankcodedsignal,s,0);

38. У, полученные матрицы передаем по строкам

39. У. из-за разного количества строк в rs и rank матрицах идем в два '/, этапа

40. У, аналогичный блок для кода Рида-Соломона У.end

41. Функция осуществляет модуляцию двоичного сигнала.

42. G1.entries.row*n+col.=G.entries.[row*n+col]; for(row = k; row < n-l; row++)for (col = 0; col < n; col++) {tpower=k-row-1;

43. Gl.entries.row*n+col.=(G.entries.[col]).xpower(tpower);gf.matrix res=Gl.solve(false);take first column, ~-k+l. and fill first rowfor (i=0;i<n;i++) {

44. H.entries.1.=res.entries.res.columns*i.;for (row = 1; row < n-k; row++) for (col = 0; col < n; col++)

45. H.entries.row * n + col. = H.entries.[(row i) * n + col]*H.entries.[(row - 1) 'int rank.codec::rowserasedecode(vector<gfelement> & code, vector<gfelement> & info, vector<int> & rows) { int t2 = static.cast<int>(rows.sizeO) ;int i,col,row;

46. Code vector contains error but we can't fix it. return 1;now lets solve key equationinitial conditions

47. F 0. . coef f [d 1] =one;1. F0.fixnorm();1. Fl. = syndrome;1. B 1. . coef f 0. =one;1. Bl.fixnorm();

48. E2 poly Gi; int m; int i = 0;while (1) {

49. F1.symbolicdiv(Fi + 1., Gi, F[i + 2]); B[i + 2] = Gi * B [i + 1] + B [i];if (F1.norm >= (<L 1) / 2 tt Fi + 1.norm. < (d - 1) / 2) {m = i; break;