Введение 5 1 Обработка информации на физическом уровне цифровых систем связи 8
1.1 Каналы передачи информации 8
1.1.1 Двоичный канал со стираниями 9
1.1.2 Двоичный симметричный канал 10
1.1.3 Аддитивный Гауссовский канал 10
1.1.4 Линейный Гауссовский канал с межсимвольной интерференцией . . 13
1.1.5 Релеевский канал 15
1.2 Модуляция 16
1.2.1 Одноканальная M-ичная модуляция 16
1.2.2 Ортогональное разделение частот 18
1.3 Многопользовательские системы связи 20
1.3.1 Временное разделение 21
1.3.2 Частотное разделение 22
1.3.3 Пространственное и поляризационное разделение 22
1.3.4 Кодовое разделение 22
1.4 Помехоустойчивое кодирование 26
1.4.1 Основные понятия 26
1.4.2 Коды Рида-Соломона 27
1.4.3 Вычислительные алгоритмы алгебраического декодирования 32
1.4.4 Низкоплотностные коды 37
1.4.5 Фактор-графы 40
1.4.6 Кодированная модуляция 43
1.5 Методы адаптивной передачи 46
1.5.1 Однопользовательские одноканальные системы 46
1.5.2 Однопользовательские многочастотные системы 48
1.5.3 Многопользовательские многочастотные системы 52
1.6 Выводы. Задачи диссертационной работы 56
2 Адаптивные методы передачи 58
2.1 Адаптивное многоуровневое кодирование 58
2.1.1 Постановка задачи 58
2.1.2 Семейство многоуровневых кодов 58
2.1.3 Адаптивное кодирование в многочастотных системах 61
2.1.4 Анализ эффективности 65
2.2 Адаптивное разделение каналов в многопользовательских многочастотных
системах 66
2.2.1 Постановка задачи 67
2
2.2.2 Оптимизационный алгоритм 70
2.2.3 Анализ эффективности 71
2.2.4 Частотно-временное расширение 72
2.2.5 Сжатие служебной информации 73
2.2.6 Чувствительность к изменениям состояния канала 76
2.3 Выводы 79
3 Вычислительные процедуры декодирования 81
3.1 Ускоренный поиск корней многочленов над конечными полями 81
3.1.1 Аффинное разложение 81
3.1.2 Специальные разложения 83
3.1.3 Обобщенное разложение 84
3.1.4 Гибридный алгоритм поиска корней многочленов 84
3.2 Быстрое преобразование Фурье над конечным полем 86
3.2.1 Циклотомический алгоритм БПФ 86
3.2.2 Применение обратного преобразования Фурье для быстрого вычис¬ления вектора синдрома 93
3.3 Разреженное представление линейных кодов 99
3.3.1 Построение разреженного фактор-графа линейного двоичного кода . 99
3.3.2 Быстрое умножение вектора на двоичную матрицу 101
3.3.3 Разреженное представление кодов Рида-Соломона 101
3.4 Двумерная интерполяция при списочном декодировании кодов Рида- Соломона 102
3.4.1 Матричная интерпретация алгоритма Нильсена 103
3.4.2 Алгебро-геометрическая интерпретация алгоритма Нильсена . . . . 105
3.4.3 Быстрое вычисление произведения идеалов 107
3.5 Выводы 110
4 Применение адаптивных методов в широкополосных системах связи 111
4.1 Модели некоторых физических каналов 111
4.1.1 Модель радиоканала со стационарными в широком смысле некорре-лированными отражениями 111
4.1.2 Модель кабельного канала на основе неэкранированной витой пары 113
4.2 Адаптивная передача в однопользовательской системе 113
4.2.1 Построение семейства многоуровневых кодов 113
4.2.2 Адаптивное многоуровневое кодирование 119
4.3 Адаптивная передача в многопользовательской системе 122
4.3.1 Сравнение адаптивных методов 122
4.3.2 Анализ характеристик системы с адаптивным разделением подканалов124
4.3.3 Чувствительность предложенного метода к временным изменениям состояния канала 128
4.3.4 Чувствительность предложенного метода к неточности оценивания канала 129
4.3.5 Оценка сложности предложенного метода 129
Бурное развитие микроэлектроники, имевшее место в конце 20 века, создало возможность для реализации сложных высокопроизводительных вычислительных систем, используемых в настоящее время практически во всех отраслях народного хозяйства. Это в свою очередь потребовало организации взаимодействия этих систем, причем с ростом их производительности растут требования к скорости и качеству связи между ними. Для эффективного функционирования подобных систем необходим точный учет текущего состояния среды передачи данных. По мере его изменения необходимо осуществлять подстройку параметров системы связи с целью минимизации мощности передатчика, требуемой для поддержания заданного качества связи. Таким образом, возникает задача управления параметрами передатчика. Несмотря на то, что в теории информации были построены решения для этой задачи, их нельзя признать удовлетворительными с практической точки зрения. Причиной этого является оптимизационный критерий, используемый в подобных теоретико-информационных исследованиях, а именно максимизация суммарной (или взвешенной) пропускной способности всех пользователей системы. Это не позволяет учесть ограничений, связанных как с невозможностью достижения пропускной способности канала с помощью существующих методов передачи информации, так и с необходимостью поддержания определенного качества обслуживания отдельных пользователей системы. В связи с этим возникает необходимость разработки алгоритмов адаптивной передачи, учитывающих вышеприведенные ограничения. При этом использование многочастотного метода передачи, получившего широкое распространение в последние годы, позволяет существенно упростить реализацию соответствующих оптимизационных алгоритмов, а так¬же допускает использование при анализе системы достаточно простых математических моделей.
Построение адаптивной системы передачи данных требует наличия нескольких методов кодирования и модуляции, обеспечивающих различную степень защиты передаваемых данных от помех. При этом особую важность имеет эффективная реализация используемых методов обработки информации, в частности кодирования и декодирования корректирующих кодов. Алгоритмы кодирования и декодирования многих современных кодов включают в себя классические вычислительные примитивы, такие как циклическая свертка, поиск корней многочлена, дискретное преобразование Фурье и т.п. При этом в большинстве случае вычисления производятся в конечных полях. Несмотря на то, что известны быстрые алгоритмы решения указанных задач, во многих случаях их непосредственное использование при реализации алгоритмов кодирования и декодирования оказывается крайне неэффективным как в силу специфики вычислений в конечных полях, так и в силу ограничений, накладываемых структурой алгоритмов кодирования и декодирования. В связи с этим возникает задача эффективной реализации соответствующих вычислительных алгоритмов.
Целью данной диссертационной работы является построение методов оптимизации параметров кодирования в многочастотных системах, позволяющих снизить мощность передатчика, требуемую для достижения заданного качества работы системы. В рамках работы решаются следующие задачи:
1. Разработка методов настройки параметров помехоустойчивого кодирования, модуляции, разделения канала и распределения мощности в зависимости от текущего состояния физического канала связи.
2. Эффективная реализация соответствующих процедур обработки информации при кодировании и декодировании данных.
Объектом исследования являются широкополосные системы связи, основанные на принципе многочастотной передачи, а также алгоритмы кодирования и декодирования корректирующих кодов, используемых при передаче данных в подобных системах.
В данной работе используются методы теорий цифровой связи, условного экстремума, помехоустойчивого кодирования, чисел и коммутативной алгебры.
Достоверность полученных результатов обеспечена сопоставлением результатов теоретического анализа и имитационного моделирования, а также наличием программной реализации всех предложенных методов.
Предметом исследования являются оптимизация параметров передачи данных в многочастотных системах, а также алгоритмы кодирования и декодирования корректирующих кодов, используемых в них.
Научные результаты и их новизна:
1. Разработан метод оптимизации разделения канала, распределения мощности и скорости передачи в многопользовательских многочастотных системах вещания, позволяющий получить существенный (до 5 дБ) энергетический выигрыш по сравнению с известными методами.
2. Предложен новый метод адаптивной передачи в многочастотных системах на основе многоуровневого кодирования, позволяющий повысить точность адаптации по сравнению с существующими методами, что позволяет получить энергетический выигрыш до 2 дБ по сравнению с существующими методами.
3. Разработан метод быстрого нахождения корней многочлена локаторов ошибки при классическом декодировании кодов Рида-Соломона, обеспечивающий снижение сложности одного из этапов декодирования в 2 - 6 раз по сравнению со стандартными методами.
4. Построен циклотомический алгоритм быстрого преобразования Фурье (БПФ) над конечными полями, на основе него разработан метод вычисления вектора синдрома при классическом декодировании кодов Рида-Соломона. Данные алгоритмы обладают наименьшей сложностью среди известных аналогов.
5. Предложен новый метод двумерной интерполяции при списочном декодировании кодов Рида-Соломона, позволяющий построить параллельную реализацию вычислительно наиболее сложного шага алгоритма Гурусвами-Судана.
Практическая ценность работы состоит в разработке методов адаптивной передачи в одно- и многопользовательских системах, позволяющий существенно снизить требуемую мощность передатчика, а также методов декодирования некоторых классов кодов, исправляющих ошибки, со сложностью, существенно меньшей по сравнению со стандартными методами. Предложенный метод адаптивной передачи в однопользовательских системах при использовании кодов длины 3200 обеспечивает функционирование системы при вероятности ошибки на бит порядка 10-7 на отношении сигнал/шум, превышающем предел Шеннона всего на 3 децибела. Данный метод может быть также использован и в многопользовательских системах. Предложенный метод адаптивной передачи в много-пользовательских системах на основе кодового разделения позволяет снизить мощность передатчика, требуемую для достижения заданных параметров работы системы, на 5 дБ по сравнению с наилучшим известным автору методом, использующим частотное разделение. Предложенный метод нахождения корней многочленов над конечным полем обладает наименьшей сложностью среди известных аналогов. Предложенный алгоритм БПФ имеет наименьшую сложность среди известных алгоритмов на длине по крайней мере до 512 и позволяет построить алгоритмы вычисления синдрома при классическом декодировании кодов Рида-Соломона, обладающие наименьшей сложностью среди известных методов.
Публикации и апробация работы. Предложенные методы были опубликованы в журналах IEEE Transactions on Communications [38], Проблемы передачи информации [175], European Transactions on Telecommunications [31, 39], Информационно-управляющие си-стемы [174], на конференциях IEEE International Symposium on Information Theory [84], IEEE Vehicular Technology Conference [127], International OFDM Workshop [126]. По материалам диссертации получен Европейский патент [36].
Диссертационная работа организована следующим образом. В главе 1 представлен обзор некоторых методов обработки информации, используемых при реализации протоколов физического уровня систем связи. В главе 2 рассматриваются новые методы адаптивной передачи в многочастотных системах. Глава 3 посвящена построению новых вычислительных алгоритмов для систем с помехоустойчивым кодированием. Применение предложенных методов в широкополосных системах связи рассмотривается в главе 4
Основными результатами данной диссертационной работы являются:
1. Метод поиска корней многочленов над конечным полем, позволяющий снизить сложность соответствующего этапа декодирования кодов Рида-Соломона в 2-6 раз.
2. Метод вычисления быстрого преобразования Фурье над конечным полем, обладаю-щей наименьшей сложностью среди известных аналогов на длинах по крайней мере до 512.
3. Метод построения разреженных фактор-графов линейных кодов и его применение в задаче быстрого умножения матрицы на вектор в полях характеристики два.
4. Метод вычисления синдромного многочлена при декодировании кодов Рида- Соломона, обладающий наименьшей сложностью среди известных аналогов для кодов с длинами по крайней мере до 255.
5. Метод вычисления произведения нульмерных взаимно простых полиномиальных идеалов и основывающийся на нем алгоритм интерполяции при списочном декодировании кодов Рида-Соломона.
6. Метод адаптивной передачи с использованием многоуровневого кодирования в многочастотных системах.
7. Метод оценивания пропускной способности векторного Гауссовского канала с независимыми случайными передаточными коэффициентами.
8. Метод адаптивного распределения мощности, скорости и разделения канала в многопользовательских многочастотных системах.
Результаты, полученные в данной работе, позволяют выделить следующие направления дальнейших исследований:
1. Исследование возможности использования разреженного представления линейных кодов для их мягкого декодирования.
2. Разработка механизмов канального уровня, обеспечивающих поддержку предложенного метода адаптивной передачи в многопользовательских системах.
3. Исследование возможности дальнейшего снижения объема передаваемой служебной информации и сложности оптимизации в предложенном методе адаптивной передачи в многопользовательских системах.
4. Дальнейшее снижение сложности интерполяции при списочном декодировании кодов Рида-Соломона.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
