Книги, научные публикации
Pages: | 1 | 2 | 3 | -- [ Страница 1 ] --
Государственное образовательное учреждение высшего профессионального образования УСанкт-Петербургский государственный политехнический университетФ
На правах рукописи
Трифонов Петр Владимирович Адаптивное
кодирование в многочастотных системах 05.13.01 Ч Системный анализ, управление и обработка информации Диссертация на соискание ученой степени кандидата технических наук
Научный руководитель д.т.н., проф. Крук Е.А.
Санкт-Петербург Ч 2005 Оглавление Введение 1 Обработка информации на физическом уровне цифровых систем связи 1.1 Каналы передачи информации........................ 1.1.1 Двоичный канал со стираниями................... 1.1.2 Двоичный симметричный канал................... 1.1.3 Аддитивный Гауссовский канал................... 1.1.4 Линейный Гауссовский канал с межсимвольной интерференцией 1.1.5 Релеевский канал........................... 1.2 Модуляция................................... 1.2.1 Одноканальная M-ичная модуляция................. 1.2.2 Ортогональное разделение частот.................. 1.3 Многопользовательские системы связи................... 1.3.1 Временное разделение......................... 1.3.2 Частотное разделение......................... 1.3.3 Пространственное и поляризационное разделение......... 1.3.4 Кодовое разделение.......................... 1.4 Помехоустойчивое кодирование....................... 1.4.1 Основные понятия........................... 1.4.2 Коды Рида-Соломона......................... 1.4.3 Вычислительные алгоритмы алгебраического декодирования... 1.4.4 Низкоплотностные коды........................ 1.4.5 Фактор-графы............................. 1.4.6 Кодированная модуляция....................... 1.5 Методы адаптивной передачи......................... 1.5.1 Однопользовательские одноканальные системы.......... 1.5.2 Однопользовательские многочастотные системы.......... 1.5.3 Многопользовательские многочастотные системы......... 1.6 Выводы. Задачи диссертационной работы...................................................................... 5 8 8 9 10 10 13 15 16 16 18 20 21 22 22 22 26 26 27 32 37 40 43 46 46 48 52 56 58 58 58 58 61 65 66 2 Адаптивные методы передачи 2.1 Адаптивное многоуровневое кодирование.................... 2.1.1 Постановка задачи............................. 2.1.2 Семейство многоуровневых кодов.................... 2.1.3 Адаптивное кодирование в многочастотных системах......... 2.1.4 Анализ эффективности.......................... 2.2 Адаптивное разделение каналов в многопользовательских многочастотных системах...................................... 2.2.1 Постановка задачи............................. ОГЛАВЛЕНИЕ 2.2.2 Оптимизационный алгоритм........ 2.2.3 Анализ эффективности........... 2.2.4 Частотно-временное расширение...... 2.2.5 Сжатие служебной информации...... 2.2.6 Чувствительность к изменениям состояния 2.3 Выводы............................................ канала.................................................................
3 70 71 72 73 76 79 81 81 81 83 84 84 86 86 93 99 99 101 101 102 103 105 107 3 Вычислительные процедуры декодирования 3.1 Ускоренный поиск корней многочленов над конечными полями....... 3.1.1 Аффинное разложение.......................... 3.1.2 Специальные разложения......................... 3.1.3 Обобщенное разложение......................... 3.1.4 Гибридный алгоритм поиска корней многочленов........... 3.2 Быстрое преобразование Фурье над конечным полем............. 3.2.1 Циклотомический алгоритм БПФ.................... 3.2.2 Применение обратного преобразования Фурье для быстрого вычисления вектора синдрома.......................... 3.3 Разреженное представление линейных кодов.................. 3.3.1 Построение разреженного фактор-графа линейного двоичного кода. 3.3.2 Быстрое умножение вектора на двоичную матрицу.......... 3.3.3 Разреженное представление кодов Рида-Соломона........... 3.4 Двумерная интерполяция при списочном декодировании кодов РидаСоломона...................................... 3.4.1 Матричная интерпретация алгоритма Нильсена............ 3.4.2 Алгебро-геометрическая интерпретация алгоритма Нильсена.... 3.4.3 Быстрое вычисление произведения идеалов............... 3.5 Выводы.......................................
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 Оценка сложности предложенного метода............... ОГЛАВЛЕНИЕ 4.4 Выводы....................................... Выводы 4 131 Введение Бурное развитие микроэлектроники, имевшее место в конце 20 века, создало возможность для реализации сложных высокопроизводительных вычислительных систем, используемых в настоящее время практически во всех отраслях народного хозяйства. Это в свою очередь потребовало организации взаимодействия этих систем, причем с ростом их производительности растут требования к скорости и качеству связи между ними. Для эффективного функционирования подобных систем необходим точный учет текущего состояния среды передачи данных. По мере его изменения необходимо осуществлять подстройку параметров системы связи с целью минимизации мощности передатчика, требуемой для поддержания заданного качества связи. Таким образом, возникает задача управления параметрами передатчика. Несмотря на то, что в теории информации были построены решения для этой задачи, их нельзя признать удовлетворительными с практической точки зрения. Причиной этого является оптимизационный критерий, используемый в подобных теоретико-информационных исследованиях, а именно максимизация суммарной (или взвешенной) пропускной способности всех пользователей системы. Это не позволяет учесть ограничений, связанных как с невозможностью достижения пропускной способности канала с помощью существующих методов передачи информации, так и с необходимостью поддержания определенного качества обслуживания отдельных пользователей системы. В связи с этим возникает необходимость разработки алгоритмов адаптивной передачи, учитывающих вышеприведенные ограничения. При этом использование многочастотного метода передачи, получившего широкое распространение в последние годы, позволяет существенно упростить реализацию соответствующих оптимизационных алгоритмов, а также допускает использование при анализе системы достаточно простых математических моделей. Построение адаптивной системы передачи данных требует наличия нескольких методов кодирования и модуляции, обеспечивающих различную степень защиты передаваемых данных от помех. При этом особую важность имеет эффективная реализация используемых методов обработки информации, в частности кодирования и декодирования корректирующих кодов. Алгоритмы кодирования и декодирования многих современных кодов включают в себя классические вычислительные примитивы, такие как циклическая свертка, поиск корней многочлена, дискретное преобразование Фурье и т.п. При этом в большинстве случае вычисления производятся в конечных полях. Несмотря на то, что известны быстрые алгоритмы решения указанных задач, во многих случаях их непосредственное использование при реализации алгоритмов кодирования и декодирования оказывается крайне неэффективным как в силу специфики вычислений в конечных полях, так и в силу ограничений, накладываемых структурой алгоритмов кодирования и декодирования. В связи с этим возникает задача эффективной реализации соответствующих вычислительных алгоритмов. Целью данной диссертационной работы является построение методов оптимизации параметров кодирования в многочастотных системах, позволяющих снизить мощность передатчика, требуемую для достижения заданного качества работы системы. В рамках ВВЕДЕНИЕ работы решаются следующие задачи:
1. Разработка методов настройки параметров помехоустойчивого кодирования, модуляции, разделения канала и распределения мощности в зависимости от текущего состояния физического канала связи. 2. Эффективная реализация соответствующих процедур обработки информации при кодировании и декодировании данных. Объектом исследования являются широкополосные системы связи, основанные на принципе многочастотной передачи, а также алгоритмы кодирования и декодирования корректирующих кодов, используемых при передаче данных в подобных системах. В данной работе используются методы теорий цифровой связи, условного экстремума, помехоустойчивого кодирования, чисел и коммутативной алгебры. Достоверность полученных результатов обеспечена сопоставлением результатов теоретического анализа и имитационного моделирования, а также наличием программной реализации всех предложенных методов. Предметом исследования являются оптимизация параметров передачи данных в многочастотных системах, а также алгоритмы кодирования и декодирования корректирующих кодов, используемых в них. Научные результаты и их новизна: 1. Разработан метод оптимизации разделения канала, распределения мощности и скорости передачи в многопользовательских многочастотных системах вещания, позволяющий получить существенный (до 5 дБ) энергетический выигрыш по сравнению с известными методами. 2. Предложен новый метод адаптивной передачи в многочастотных системах на основе многоуровневого кодирования, позволяющий повысить точность адаптации по сравнению с существующими методами, что позволяет получить энергетический выигрыш до 2 дБ по сравнению с существующими методами. 3. Разработан метод быстрого нахождения корней многочлена локаторов ошибки при классическом декодировании кодов Рида-Соломона, обеспечивающий снижение сложности одного из этапов декодирования в 2 - 6 раз по сравнению со стандартными методами. 4. Построен циклотомический алгоритм быстрого преобразования Фурье (БПФ) над конечными полями, на основе него разработан метод вычисления вектора синдрома при классическом декодировании кодов Рида-Соломона. Данные алгоритмы обладают наименьшей сложностью среди известных аналогов. 5. Предложен новый метод двумерной интерполяции при списочном декодировании кодов Рида-Соломона, позволяющий построить параллельную реализацию вычислительно наиболее сложного шага алгоритма Гурусвами-Судана.
ВВЕДЕНИЕ Практическая ценность работы состоит в разработке методов адаптивной передачи в одно- и многопользовательских системах, позволяющий существенно снизить требуемую мощность передатчика, а также методов декодирования некоторых классов кодов, исправляющих ошибки, со сложностью, существенно меньшей по сравнению со стандартными методами. Предложенный метод адаптивной передачи в однопользовательских системах при использовании кодов длины 3200 обеспечивает функционирование системы при вероятности ошибки на бит порядка 107 на отношении сигнал/шум, превышающем предел Шеннона всего на 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. Обработка информации на физическом уровне цифровых систем связи В данной главе представлено описание некоторых методов передачи информации, используемых в данной диссертационной работе. Последовательность изложения в основном соответствует типичной структуре современной приемо-передающей аппаратуры цифровой связи. Раздел 1.1 посвящен краткому описанию математических моделей каналов передачи информации, рассматриваемых в данной работе. В разделе 1.2 описаны некоторые методы модуляции и демодуляции. Раздел 1.3 посвящен описанию некоторых методов множественного доступа и вещания. В разделе 1.4 рассматриваются некоторые классы кодов, исправляющих ошибки. Обзор некоторых методов адаптивной передачи представлен в разделе 1.5. Глава не содержит никаких новых результатов автора и предназначена исключительно для введения основных понятий, используемых в дальнейшем.
1.1 Каналы передачи информации Основной задачей теории связи является восстановление сообщения, сформированного передатчиком в некоторый момент времени в некоторой точке пространства, в некоторой другой точке пространства спустя некоторый интервал времени. Очевидно, что для решения этой задачи необходимо изучение свойств среды передачи информации, называемой также каналом. Под моделью канала здесь понимается математическая абстрация, позволяющая задать принимаемый сигнал r(t) как функцию (как правило, случайную) от передаваемого сигнала s(t), где t Чвремя. В цифровых системах связи принимаемый сигнал на некотором этапе его обработки дискретизуется как по времени, так и по амплитуде, поэтому рассматриваются также дискретные модели каналов, связывающие отсчеты ri и si принимаемого и передаваемого сигналов соответственно. При этом наличие дискретизации по амплитуде приводит к возникновению шума квантования, влияние которого может быть снижено путем увеличения числа уровней дискретизации. Т.к. современные аппаратные средства цифровой обработки сигналов имеют достаточно большую разрядность, этим эффектом можно в значительной степени пренебречь. Поэтому далее, если не указано иное, дискретизация сигнала по амплитуде учитываться не будет. Всякий канал передачи информации может быть охарактеризован входным алфавитом A, выходным алфавитом B и семейством условных распределений p(r|s), характеризующих статистические свойства принимаемого сигнала r = (..., ri1, ri, ri+1,...) в зависимости от передаваемого сигнала s = (..., ri1, si, si+1,...). Простейшим случаем канала передачи информации является канал без памяти, для которого справедливо p(ri |s1,..., si1 ) = p(ri |si), i N, ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ т.е. принимаемый сигнал зависит исключительно от сигнала, передаваемого в данный момент времени. В тех случаях, когда передаваемые символы si выбираются независимо от ранее принятых символов, т.е. p(si |s1,..., sn1, r1,..., rn1 ) = p(si |s1,..., sn1 ), несложно показать, что n p(r1,..., rn |s1,..., rn ) = i= p(ri |si ) Фундаментальной характеристикой любого канала связи является его пропускная способность, определяемая как C = max I(r;
s), (1.1) pA (s) где максимум вычисляется по всем возможным распределениям передаваемых символов pA (s), а I(r;
s) = H(r) H(r|s) Ч взаимная информация между принятой последовательностью r и переданной последовательностью s, H(x) = xB pB (x) log2 pB (x)dx Ч неопределенность (энтропия) случайной величины x, принимающей значения из некоторого множества B с плотностью распределения pB (x). Таким образом, выражение для пропускной способности имеет вид CA = max pA (s) sA pA (s)p(r|s) log p(r|s) p (s )p(r|s )ds s A A dsdr, (1.2) где pA (s) Ч плотность распределения передаваемых символов, а p(r|s) Ч условная плотность распределения принятого сигнала. В случае дискретного алфавита интеграл по A в этом выражении заменяется на сумму. Можно показать [161], что надежная передача информации по каналу возможна только со скоростью R, не превышающей эту величину. Под надежной передачей здесь понимается возможность построения такой пары передатчика и приемника, что сообщение достаточно большой длины n = Rk, несущее k бит информации, может быть восстановлено приемником со сколь угодно малой вероятностью ошибки. При этом необходимо отметить, что в большинстве практических систем распределение передаваемых символов не оптимизируется, что приводит к определенному снижению максимальной достижимой скорости передачи данных.
1.1.1 Двоичный канал со стираниями Предположим, что передача ведется с помощью двух сигналов, обозначаемых далее как 0 и 1, и приемник способен каким-либо образом достоверно распозать часть принятых символов (сигналов). Тогда оставшаяся часть принятых символов может быть объявлена недостоверной или стертой, т.е. множество сигналов на выходе канала равно {0, 1, _}. Такой канал характеризуется вероятностью pE того, что символ будет объявлен стертым, и носит название двоичного канала со стираниями. Модель двоичного канала со стираниями непосредственно возникает при рассмотрении сетей с коммутацией пакетов. Как известно, при передаче данных по ним некоторые ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ пакеты могут теряются. Очевидно, что обнаружение факта потери может быть интерпретировано как стирание. Эта модель также может быть использована для анализа свойств низкоплотностных кодов. Пропускная способность двоичного канала со стираниями равна CBEC = 1 pE 1.1.2 Двоичный симметричный канал Предположим, что передача ведется с помощью двух сигналов, обозначаемых далее как 0 и 1 (т.е. элементов конечного поля GF (2)). В результате воздействия шума принятые символы могут отличаться от переданных с некоторой ненулевой вероятностью pe, т.е. ri = si + i, ri, si, i GF (2), P {i = 1} = pe Такой канал носит название двоичного симметричного канала. Эта модель широко использовалась для анализа свойств кодов, исправляющих ошибки. Пропускная способность двоичного симметричного канала равна CBSC = 1 + pe log2 (pe ) + (1 pe ) log2 (pe ) 1.1.3 Аддитивный Гауссовский канал Предположим, что передаваемый символы принадлежат некоторому множеству A R, а помеха является аддитивной и представляет собой случайную величину с нормальным распределением, т.е. принятый сигнал может быть представлен как ri = si + i, si A, i N(0, 2 ). Аддитивный Гауссовский канал характеризуется отношением сигнал-шум на символ, которое определяется как M[s2 ] i =. 2 Кроме того, часто используется отношение сигнал-шум на бит Eb /N0 =, R где R Ч среднее число информационных бит, содержащихся в одном символе из алфавита A, передаваемом по каналу. Пропускная способность аддитивного Гауссовского канала достигается при условии нормального распределения передаваемых сигналов si (т.е. A = R) и равна CAW GN = 1 log2 (1 + ). 2 (1.3) Достаточно часто (например, при рассмотрении различных методов модуляции, отображающих передаваемые данные на некоторые (вещественные) сигналы, передаваемые по физическому каналу связи) возникает необходимость рассмотрения комплексных сигналов, ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ т.е. A C. В этом случае пропускная способность также максимизируется при условии нормального (комплексного) распределения передаваемых сигналов и равна CAW GN = log2 (1 + ). В общем случае необходимо рассмотрение непрерывных сигналов r(t) = s(t) + (t), где r(t) Ч принятый сигнал, (t) Ч Гауссовский случайный процесс со спектральной плотностью мощности N0, а s(t) Ч передаваемый сигнал, также представляющий собой Гауссовский процесс со спектральной полосой шириной W и имеющий спектральную плотность мощности Es. Можно показать [161, 176], что пропускная способность подобного канала равна Es. (1.5) CAW GN = W log2 1 + W N0 Однако достаточно часто оказывается, что передаваемые символы не являются гауссовскими, а вместо этого равномерно распределены по некоторому конечному множеству A. В этом случае пропускная способность может быть вычислена непосредственно с помощью выражения (1.2). Хотя использование таких сигналов и не является оптимальным, это позволяет существенно упростить процедуры приема и передачи. Простейшим способом организации приема является поиск символа (УжесткогоФ решения) si A, ближайшего к принятой величине ri, и передача его для дальнейшей обработки. Например, в случае 1, ri > 0, т.е. произвовходного алфавита A = {1, 1} это правило принимает вид si = 0, ri 0 дится дискретизация на два уровня. Тогда si можно рассматривать как результат передачи si по двоичному симметричному каналу с вероятностью ошибки pe = Q 1 Q(x) = x 2Eb N (1.4), где et 2 / dt.
Очевидно, что при такой организации приемника теряется достаточно много информации о принятом сигнале, которая могла бы быть использована при дальнейшей обработке для принятия более точного решения. В связи с этим в большинстве случаев производят дискретизацию на большее число уровней (принятие Умягкого решенияФ). Частным случаем такого подхода является использование стираний, т.е. указание позиций принятых символов si, для которых |ri | <, где Ч некоторое пороговое значение. Достаточно часто оказывается, что система связи может быть представлена в виде нескольких параллельных Гауссовских каналов (векторный Гауссовский канал), причем сигнал, принятый приемником i-го канала, может быть представлен как ri = i si + i, (1.6) где i C Ч различные передаточные коэффициенты. Каждый из таких подканалов 2 может быть охарактеризован своим отношением канал/шум i = |i2|, i = 1..N. Используя ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ i Номер подканала Vi Рис. 1.1 Принцип ФводонаполненияФ стандартные методы оптимизации, легко показать, что пропускная способность подобной системы при фиксированной общей мощности P достигается путем ее распределения по отдельным каналам в соответствии с правилом Vi2 = max ( 1/i, 0), (1.7) где константа подбирается таким образом, чтобы удовлетворить ограничение на общую мощность передатчика N Vi2 = P, i= и Vi2 = M[|si |2 ] Ч мощность сигнала, передаваемого по i-му подканалу. Это правило получило название принципа ФводонаполненияФ, т.к. мощность передатчика распределяется аналогично воде в резервуаре с неровным дном (см. рис. 1.1). Полная пропускная способность такого канала равна N CV AW GN = i= log2 1 + Vi2 i ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 1.1.4 Линейный Гауссовский канал с межсимвольной интерференцией В большинстве случаев среда передачи информации может быть достаточно хорошо описана как линейная система с некоторым импульсным откликом h( ). Тогда принимаемый сигнал может быть представлен как t r(t) = s(t )h( )d + (t), (1.8) где (t) Ч Гауссовский случайный процесс со спектральной плотностью мощности (f ). Выполняя дискретизацию по времени, получим L ri = j= sij hj + i, где L Ч длительность импульсного отклика. Очевидно, что такой канал обладает памятью, т.к. его выход зависит от N 1 символов, переданных ранее. Вычисляя преобразование Фурье от выражения (1.8), получим r(f ) = s(f )H(f ) + (f ) (1.9) Для анализа пропускной способности такого канала он может быть разбит на совокупность аддитивных Гауссовских каналов, ограниченных бесконечно малой полосой f. Используя выражение (1.5) и выполняя условную максимизацию пропускной способности, аналогично случаю векторного Гауссовского канала, несложно показать, что оптимальное распределение мощности сигнала по частоте имеет вид P (f ) = max(0, |(f )|2 ), |H(f )|2 (1.10) где константа подбирается так, чтобы удовлетворить ограничение на мощность сигнала P (f )df = P, а пропускная способность равна CISI = log2 1 + P (f )|H(f )|2 |(f )| df, (1.11) где |H(f )|2 Ч амплитудно-частотная характеристика канала. В кабельных системах связи межсимвольная интерференция возникает из-за наличия паразитных емкостей и индуктивностей. При этом поведение линии связи в большинстве случаев является детерминированным и может быть достаточно хорошо предсказано с помощью методов теории электрических цепей.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ В системах радиосвязи межсимвольная интерференция возникает из-за наличия большого числа путей распространения сигнала от передатчика к приемнику, создаваемых различными объектами, отражающими радиосигнал. Более того, перемещения этих объектов в пространстве и изменение их свойств приводит к тому, что импульсный отклик канала меняется во времени и представляет собой некоторый случайный процесс h(, t) = i i (t)e j 2fc i (t) ( i (t)), (1.12) где i (t) Ч задержка сигнала на i-м пути распространения в момент времени t и fc Ч несущая частота системы. Предполагая, что этот процесс стационарен в широком смысле, введем автокорреляционную функцию канала как [172] 1 h (1, 2, t) = M[h (1, t)h(2, t + t)] 2 (1.13) В большинстве случае имеет место некоррелированное рассеяние, т.е. затухание сигнала и сдвиг по фазе при различных задержках 1 и 2 некоррелированы. Тогда 1 M[h (1, t)h(2, t + t)] = h (1, t)(1 2 ) 2 Полагая t = 0, получим h ( ) = h (, 0) Ч характеристику средней мощности выхода канала как функцию задержки или спектр мощности задержек канала. Область значений, в которых h ( ) существенно больше нуля1, называется многопутевым рассеянием канала max. Аналогичная характеристика может быть получена в частотной области. Рассмотрим частотную передаточную функцию канала H(f, t) = h(, t)ej2f d Предполагая стационарность канала в широком смысле и некоррелированность рассеяния по различным путям, несложно показать [172], что автокорреляционная функция от H(f, t) H (f1, f2, t) по частоте зависит только от разности частот f = f2 f1. Кроме того, имеет место соотношение H (f ) = H (f, 0) = h ( )ej2f d В частотной области многопутевому рассеянию max соответствует полоса частотной когерентности канала, определяемая как (f )h 1 max Если эта величина мала по сравнению с полосой частот передаваемого сигнала, канал называется частотно селективным.
В данной работе это значение предполагается соответствующим затуханию сигнала на 30 дБ.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Т.к. местоположение отражателей относительно приемника и передатчика непрерывно изменяется, характеристики канала также изменяются во времени. При этом необходимо различать кратковременные изменения, связанные со сравнительно быстрыми перемещениями предметов друг относительно друга (эффект Доплера), и долговременные изменения, связанные с принципиальными изменениями в среде передачи сигнала (например, перемещение приемника вовнутрь некоторого сооружения). Для исследования кратковременных изменений вычислим преобразование Фурье функции H (f, t) по переменной t, т.е.
SH (f, ) = H (f, t)ej2t d(t) (1.14) Функция SH () = SH (0, ) называется доплеровским спектром мощности и характеризует его как функцию от частоты Доплера. Действительно, если канал не изменяется во времени, H (t) = K и SH () = K() для некоторого K. Область значений, в которой значение SH () существенно отлично от нуля, называется максимальным доплеровским рассеянием fD. Обратная величина называется временем когерентности канала 1 (t)h. fd Кроме того, необходимо различать медленные и быстрые замирания [176]. В первом случае состояние канала остается примерно постоянным на протяжении нескольких символьных интервалов.
1.1.5 Релеевский канал Для анализа радиоканалов с многопутевым распространением сигнала во многих случаях может быть использована релеевская модель канала. Основное отличие релеевского канала с замираниями и рассеяниями от гауссовского канала состоит в наличии как аддитивной, так и мультипликативной помех, т.е. ri = isi + i, si A, i N(0, 2 ), (1.15) причем вещественная и мнимая компоненты мультипликативной помехи i являются независимыми нормально распределенными случайными величинами с нулевым матожиданием. Тогда |i| имеет распределение Релея. Состояние такого канала удобно характеризовать отношением канал/шум, равным i = |i|2 / 2, имеющим экспоненциальное распределение В большинстве случаев оказывается, что i (и i) являются зависимыми случайными величинами. Приемник для случая релеевского канала может функционировать как без учета информации о текущей фазе i, так и с ее учетом [176]. В первом случае (некогерентный прием) демодуляция основывается исключительно на свойствах используемого сигнального множества. Во втором случае оказывается возможным оценивание по максимуму правдоподобия, состоящее в поиске такого si A, что |i si ri |2 минимально. Ясно, что в последнем случае можно добиться намного лучшего качества демодуляции. Ввиду большой вычислительной сложности этого подхода на практике в большинстве случаев ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ применяется упрощенная схема, состоящая в выравнивании принятого сигнала и использовании некоторой вычислительно простой функции v(i ) : C {0, 1}log2 |A|, позволяющей s по оценке переданного символа вычислить соответствующие ему информационные биты, а при необходимости и их отношения правдоподобия. Выравнивание состоит в вычислении si = gi ri, где gi Ч некоторый коэффициент. Наилучшие показатели в большинстве случаев обеспечивает выравнивание по минимуму среднего квадрата ошибки. В этом случае gi = i. |i|2 + 2 /M[|si |2 ] В том случае, когда передатчик никак не учитывает состояние канала, выражение для пропускной способности Релеевского канала может быть получено путем усреднения выражения (1.3) по всем возможным значениям отношения канал/шум i, что приводит к следующему выражению [176]: CRayleigh 1 1/ e ln 1/ et dt. t (1.16) С другой стороны, процесс передачи последовательности из n символов может рассматриваться как передача блока данных по векторному Гауссовскому каналу. В этом случае пропускная способность может быть существенно улучшена путем адаптации мощности передатчика в соответствии с принципом УводонаполненияФ [47]. Обобщениями релеевской модели канала являются модели Райса и Накагами. Выражения для пропускной способности этих каналов приведены в [5].
1. Модуляция В данном разделе представлено описание некоторых методов модуляции сигнала, рассматриваемых в данной работе. Под модуляцией здесь понимается процесс преобразования дискретной последовательности символов из конечного алфавита в непрерывный сигнал, пригодный для передачи по каналу.
1.2.1 Одноканальная M-ичная модуляция Передача данных по любой среде производится путем формирования некоторых вещественных сигналов sY (t), где t Ч время, а Y Ч передаваемая последовательность данных. Для простоты предположим, что Y = {..., yi, yi+1,...} представляет собой последовательность независимых M-ичных символов;
обобщения на случай кодированной передаваемой последовательности (кодированной модуляции) будут представлены ниже. Предполагая, что модуляция выполняется независимо для каждого из символов yi, получим, что переданный сигнал может быть представлен как s(t) = i s(t iTs, yi ), ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ где Ts Ч временной интервал, в течение которого передается один символ, а s(t, y) Ч сигнал, формируемый для передачи символа y. Важной характеристикой является средняя энергия, затрачиваемая на передачу одного символа. Если s(t) соответствует напряжению, то при импедансе передатчика, равном 1 Ом, и при условии равных вероятностей выбора всех передаваемых символов средняя энергия сигнала численно равна Es = 1 M s2 (t, yi )dt.
yi A Модуляция может производиться как с использованием несущей с частотой fc > 0, так и без несущей (т.е. fc = 0). В случае систем с несущей различают базовый сигнал (или видеосигнал), непосредственно кодирующий передаваемую информацию, и полосовой сигнал, получаемый наложением базового сигнала на несущую частоту. Однако при рассмотрении систем с несущей в большинстве случаев их оказывается возможным заменить эквивалентной системой без несущей. В данной работе рассматриваются следующие простейшие методы модуляции (т.е. функции s(t, yi )): 1. Импульсно-амплитудная модуляция (АМ). Передаваемая информация кодируется амплитудой некоторого импульса, т.е. сигнал формируется как s(t, yi) = (V (2G(yi) M + 1)gT (t)ej 2fc t ), 0 yi M 1 где V Ч некоторый коэффициент усиления, fc 0 Ч несущая частота, gT (t) задает форму импульса, а G(y) является функцией разметки сигнального множества. Одной из наиболее популярных функций разметки является код Грея, т.е. смежным сигналам сопоставляются значения yi, различающиеся ровно в одном бите. Такой способ позволяет снизить число неверно определяемых битов в случае ошибочной демодуляции. Пример сигнального множества с разметкой представлен на рис. 1.2(a). Вероятность ошибки на символ для M-ичной АМ равна [172] PM = 2(M 1) Q M 6Es (M 2 1)N0 (1.17) 2. Квадратурно-амплитудная модуляция. Передаваемая информация кодируется как амплитудой, так и фазой сигнала, т.е. s(t, xi ) = V (Axi ej 2f t ), где Axi C Ч один из элементов сигнального множества, представленного на рис. 1.2(b). Сигнал квадратурно-амплитудную модуляции можно также рассматривать как суперпозицию двух сигналов импульсно-амплитудной модуляции. Для случая аддитивного Гауссовского канала вероятность ошибки может быть вычислена как [172] 3Es Pe 4Q (1.18) (M 1)N ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 101 111 110 010 011 101 111 110 010 011 001 000 111 101 011 010 110 100 000 (a) Импульсно-амплитудная (b) Квадратурно-амплитудная модуляция модуляция Рис. 1.2 Примеры сигнальных множеств 1.2.2 Ортогональное разделение частот Ортогональное разделение частот (Orthogonal frequency Division Multiplexing, OFDM) [13] было предложено в конце 50-х годов 20 века [87, 141] и долгое время не применялось ввиду высокой сложности аппаратной реализации. Однако с появлением современных сигнальных процессоров эта проблема была снята и данный метод стал широко внедряться во многие практические системы. В системе с ортогональным частотным разделением данные передаются по набору подканалов с ортогональными несущими частотами. В результате полоса частот, занимаемая системой передачи данных, разбивается на большое число узких полос. Тогда условия распространения сигнала, передаваемого по каждому из подканалов, становятся близкими к ограниченному по полосе Гауссовскому каналу, что существенно упрощает построение приемника. Формально, отсчеты базового сигнала, передаваемого OFDM-системой, могут быть представлены как 1 Sk = N или, в непрерывном времени, 1 S(t) = N N 1 N i= si e2 j N, k = 0, 1,..., N 1, ik (1.19) i= si e2 j T, 0 t T, it (1.20) где T символьный интервал и si Ч сигналы, передаваемые по подканалам. Несложно заметить, что выражение (1.19) представляет собой обратное дискретное преобразование Фурье от символов, передаваемых по подканалам. Кроме того, к передаваемому сигналу добавляется префикс, состоящий из отсчетов Sv = SN v, Sv+1 = SN v+1,..., S1 = SN 1. Это дает возможность полностью исключить межсимвольную и межканальную интерференцию за счет некоторого снижения скорости передачи данных [13, 172]. Если это условие не выполняется, возникает необходимость применения специальных методов подавления ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Закодированные данные Добавл. цикл. префикса удален. цикл. префикса Модуляция Модуляция Модуляция Модуляция Модуляция Выравнивание Выравнивание Выравнивание Выравнивание Выравнивание К декодеру Демодуляция Демодуляция Демодуляция Демодуляция Демодуляция ДПФ ЦАП Канал с МСИ h( ) ОДПФ АЦП Передатчик Приемник Рис. 1.3 Структура OFDM-системы межсимвольной и межканальной интерференции [37, 101]. Требуемая величина циклического префикса может быть снижена с помощью фильтров, укорачивающих импульсный отклик канала [7, 6]. Передача сигнала S(t) по каналу с импульсным откликом h( ), который предполагается неизменным на протяжении символьного интервала T, приводит к возникновению межсимвольной интерференции, т.е. принятый сигнал R(t) после дискретизации может быть представлен как L1 N Rk = R(kT /N) = i= h(iT /N)S((k i)T /N) + (kT /N) = (1.21) где (t) Ч шумовой процесс Приемник OFDM-системы отбрасывает первые v принятых отсчетов, соответствующих циклическому префиксу. Несложно заметить, что оставшиеся отсчеты R0..RN 1 представляют собой циклическую свертку длины N последовательности Sk и дискретизованного импульсного отклика канала hi = h(iT /N). Следовательно, дискретное преобразование Фурье вектора (R0,..., RN 1 ) дает величины i= hi Ski + k, k = v..N 1, ri = i si + i, (1.22) L1 где i = k=0 h(kT /N)e j 2ki/N Ч передаточный коэффициент канала, а i Ч преобра2 зованные отсчеты аддитивного Гауссовский шум с дисперсиями i. Блок-схема OFDMсистемы представлена на рис. 1.3. Таким образом, передача данных по каналу с межсимвольной интерференцией может быть сведена к задаче передачи данных по векторному Гауссовскому каналу, каждый из подканалов которого может быть охарактеризован от2 ношением канал/шум i = |i2|. В большинстве случаев оказывается, что величины i i существенно различны, вследствие чего возникает необходимость адаптации используемой схемы передачи. Многочастотная передача может быть реализована в системах как с использованием несущей, так и без нее. Многочастотная передача без несущей носит название дискретной многотональной (Discrete Multitone, DMT) и применяется в кабельных системах электросвязи. В этом случае сигнал S(t) должен быть вещественным, что требует обеспечения эрмитовой симметрии символов si.
Необходимо отметить, что эти отсчеты не являются шумом и могут быть использованы для улучшения качества приема [138].
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Существенным недостатком OFDM является большой динамический диапазон формируемого сигнала, что может вызвать сложности при реализации аналогового тракта системы. Для преодоления этой проблемы был предложен ряд методов [119, 97, 85, 51, 56, 55, 96, 21, 123, 33, 54, 93], позволяющих уменьшить пиковую величину передаваемого сигнала за счет некоторого снижения скорости передачи данных или увеличения средней мощности сигнала. Если импульсный отклик канала изменяется с течением времени или имеет место несовпадение частот осцилляторов в приемнике и передатчике, возможно возникновение межблоковой и межканальной интерференции, подавление которой требует применения специальных методов [13, 144, 9]. В данной работе предполагается, что этими эффектами можно пренебречь.
1. Многопользовательские системы связи В данном разделе описаны некоторые широко используемые методы организации многопользовательских систем. Известно несколько типов систем связи со многими пользователями[172]. 1. Система множественного доступа, в которой несколько пользователей используют общий канал связи (например, полосу частот) для передачи инормации к приемнику. 2. Система вещания, в которой один передатчик передает информацию нескольким пользователям. Таким передатчиком может быть, например, базовая станция в системе мобильной связи. В [65] была установлена связь между характеристиками каналов множественного доступа и широковещательных каналов. 3. Сеть накопления-передачи, в которой некоторые (или все) узлы ретранслируют полученную информацию другим узлам. 4. Дуплексные системы связи. Предметом рассмотрения данной работы являются системы вещания. Основной характеристикой систем множественного доступа и систем вещания является область достижимых скоростей, т.е. такое подмножество C RK, что K пользователей системы могут осуществлять передачу (прием) данных с произвольно малой вероятностью ошибки со скоростями Rk, k = 0..K 1, такими что (R0,..., RK1) C. В большинстве случаев область достижимых скоростей является выпуклой. В этом случае ее граница может быть получена как решение оптимизационной задачи K k : max = k k Rk k= (1.23) при соответствующих ограничениях. При рассмотрении систем вещания достаточно часто оказывается полезным использование модели ухудшающегося дискретного канала (см. рис. 1.4(a)), рассмотренной в ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 2 N (0, 0 ) Источник 0 Передатчик Источник 1 Приемник 0 Приемник 1 Канал 0 Канал Источник 0 Передатчик Источник + N (0,12 ) Приемник + Приемник (a) Ухудшающийся широковещательный канал (b) Независимые широковещательные каналы Рис. 1.4 Широковещательные каналы [168]. Анализ подобной системы основывается на том, что если передаваемые сообщения могут быть восстановлены с произвольно малой вероятностью ошибки на выходе худшей составляющей канала, то они могут быть восстановлены и на выходе лучшей составляющей. Более общую модель независимых широковещательных каналов (см. рис. 1.4(b)) во многих случаях удается свести к модели ухудшающегося канала путем переупорядочения каналов различных пользователей в соответствии с их качеством [46].
1.3.1 Временное разделение Простейшим способом разделения канала между пользователями является разбиение некоторого временного отрезка T на N неперекрывающихся интервалов длительностью T /N. Каждому пользователю выделяется один из этих интервалов. Такая система носит название временного разделения. Рассмотрим область достижимых скоростей системы вещания, использующей временное разделение. Пусть = (0,..., K1) Ч вектор, характеризующий отношения канал/шум в каналах каждого из пользователей, причем сигналы, принятые всеми пользователями, предполагаются свободными от межсимвольной интерференции. Параметрами оптимизационной задачи (1.23) являются величины K1 j () : j=0 j () = 1. j () характеризует долю времени, выделяемую пользователю j при состоянии каналов. Можно показать [80], что множество достижимых скоростей имеет вид CT D (P ) = PF (R0,..., RK1) RK |Rj M j ()W log2 1 + Pj ()j W, (1.24) где F Ч множество всех правил распределения мощности P, удовлетворяющих ограничениям K1 M j ()Pj () P j=0, K1 j () = j= где P Ч максимальная допустимая мощность передаваемого сигнала. Необходимо отметить, что в тех случаях, когда ставится задача максимизировать полную пропускную ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 1 способность системы (т.е. 0 = 1 =... = K1 = K в (1.23)), оказывается достаточным выделить весь канал пользователю с наибольшим отношением канал/шум. В том случае, когда каналы являются частотно-селективными, величины j, j = 0..K 1 |Hj (f )|2 могут быть заменены на функции j (f ) = |j (f )|2. В этом случае область достижимых скоростей имеет вид CT D (P ) = PF (R0,..., RK1) RK |Rj W j (f ) log2 (1 + Pj (f )j (f )) df, (1.25) где F Ч множество всех правил распределения мощности по частоте P, удовлетворяющих ограничениям K1 j (, f )Pj (f )df P W j=0, K1 j (f ) = 1 f j= где j (, f ) задает параметры временного разделения различных частот.
1.3.2 Частотное разделение Метод частотного разделения состоит в разбиении имеющейся полосы частот на набор неперекрывающихся подполос, каждая из которых выделяется одному из пользователей. Большое распространение получил метод ортогонального частотного разделения, состоящий в выделении пользователям одного или нескольких подканалов в OFDM-системе. Можно показать [118], что средняя задержка сообщения в системе с частотным разделением больше, чем в случае временного разделения. В случае частотно-селективного канала полная пропускная способность системы может быть достигнута путем выделения каждого подканала i пользователю k = arg maxk ki [19, 149, 90].
1.3.3 Пространственное и поляризационное разделение Разделение сигналов различных пользователей может также осуществляться за счет использования поляризованных и многолучевых антенн. Это позволяет существенно повысить эффективность использования дефицитного частотного ресурса.
1.3.4 Кодовое разделение Альтернативой частотному и временному разделению является кодовое разделение. В этом случае допускается одновременная передача сигнала по одной и той же полосе частот несколькими пользователями. Прием сводится к декодированию принятого сигнала, причем сигналы от других пользователей рассматриваются как шум (однопользовательский детектор) или производится совместное декодирование (многопользовательский ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ детектор). Для упрощения процедуры детектирования используется прием расширения спектра, состоящий в том, что каждый символ, передаваемый пользователем, умножается на некоторую расширяющую последовательность, уникальную для каждого пользователя, т.е. передаваемый сигнал базовой станции может быть представлен как K (k) siS+s = k= aks yi, s = 0..S (k) (1.26) (k) где ak = (ak0,..., ak,S1) Ч расширяющая последовательность k-го пользователя, yi Ч i-й символ, передаваемый k-м пользователем. Детектирование сигнала, предназначенного k-му пользователю, может осуществляться следующими методами: Х Однопользовательское детектирование, состоящее в том, что сигналы других пользователей рассматриваются как шум. Если мощность сигнала каждого из пользователей равна E, то сигнал детектируемого пользователя оказывается пораженным интерференцией и аддитивным Гауссовским шумом общей мощностью W N0 +(K 1)P. Если расширяющие последовательности, принадлежащие различным пользователям, ортогональны, однопользовательское детектирование3 может быть произведено путем взаимной корреляции принятого сигнала с соответствующей последовательностью. Х Многопользовательское детектирование, состоящее в том, что декодер осуществляет поиск вектора, соответствующего наложенным сигналам пользователей, ближайшего к принятому сигналу. Эту процедуру можно также рассматривать как декодирование кода первого пользователя в условиях шума, создаваемого каналом и другими пользователями, вычитание его восстановленного сигнала из принятой последователности, декодирование кода второго пользователя и т.д. (последовательное декодирование). Таким образом, коды отдельных пользователей должны проектироваться с учетом шума, создаваемого друг другом. В более общем случае многомерного канала для проектирования пользовательских кодов, максимизирующих полную пропускную способность, могут быть использованы процедуры, представленные в работах [134, 149]. Как и в случае однопользовательских систем, архитектура приемника может быть существенно упрощена за счет использования многоканальной передачи. При этом возможны различные варианты отображения наложенных сигналов на параллельные подканалы [145]: 1. Многочастотное кодовое разделение (Multi-carrier CDMA, MC-CDMA), представленное на рис. 1.5(a). Каждая компонента совмещенного вектора длины S передается по отдельному подканалу, причем одновременно осуществляется передача P символов. Предположим, что набор из N подканалов4 разбит на P непересекающихся подмножеств Wp, p = 1..P размером Sf = N/P. Каждый из P символов каждого При передаче по аддитивному Гауссовскому каналу. Необходимо отметить, что здесь N не обязательно должно быть равно числу подканалов в OFDMсистеме. Описанная конструкция может быть реализована на любом их подмножестве.
4 ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Наложенные последовательности Наложенные последовательности Наложенные последовательности Перемежение Перемежение Перемежение ОДПФ ОДПФ (a) Многочастотное кодовое разде- (b) Многочастотное кодовое разде- (c) Многочастотное частотноление ление прямой последовательностью временное кодовое разделение Рис. 1.5 Отображение наложенных сигналов на подканалы в многочастотной системе пользователя после расширения передаются по подканалам, входящим в соответствующее множество Wp. Как правило, эти множества формируются таким образом, что подканалы, входящие в них, максимально удалены друг от друга, что создает эффект разнесения [172]. Однако необходимо также учитывать возможное изменение корреляционных свойств расширяющих последовательностей после передачи их компонент по каналам с различающимися передаточными коэффициентами, что может привести к возникновению межпользовательской интерференции. Формально, переданный сигнал может быть представлен в частотной области как K (j) swps = k= Vkp ykp cks, s = 0..Sf 1, p = 1..P (j) где K Ч число пользователей, (ck1..., ckSf ) Ч расширяющая последовательность (j) k-го пользователя, ykp Ч p-й символ, передаваемый k-му пользователю в момент времени j, Vkp Ч соответствующий коэффициент усиления. Данный метод является простейшим способом реализации кодового разделения в многочастотной системе. Каждый пользователь может выделить предназначенные ему символы после получения одного OFDM-символа. Ясно, что максимальное число пользователей в подобной системе равно числу ортогональных расширяющих последовательностей S. Т.к. применение длинных расширяющих последовательностей общего вида часто оказывается затруднительным, в некоторых случаях применяется смешанное частотно-кодовое разделение. 2. Многочастотное кодовое разделение прямой последовательностью (multi-carrier direct sequence CDMA), представленное на рис. 1.5(b). В данном случае CDMAсигнал формируется независимо для каждого из подканалов, т.е.
K si (jSt +s) = k= Vkiyki cks, s = 0..St (j) Если каждый пользователь использует ровно одну расширяющую последовательность и осуществляет передачу по всем подканалам одновременно, общее число ОДПФ ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ пользователей ограничено числом расширяющих последовательностей S. Однако в некоторых случаях допускается использование одним пользователем нескольких расширяющих последовательностей. Если рассматривать пары (подканал, расширяющая последовательность) как независимые каналы передачи информации, то они могут быть произвольным образом распределены между пользователями. В этом случае общее число пользователей ограничено NSf 3. Многочастотное частотно-временное кодовое разделение5, представленное на рис. 1.5(c), является обобщением двух вышеописанных методов. Компоненты совмещенного вектора длины S распределяются по Sf подканалам и St OFDM-символам. Формально, переданный сигнал может быть представлен как K (jS swpit +s) = k= Vkp ykp ck,iSt +s, s = 0..St 1, i = 0..Sf 1p = 1..P.
(j) где ck uv Ч компоненты расширяющей последовательности длины St Sf, используемой k-м пользователя. Можно показать [80], что при использовании в широковещательной системе кодового разделения с многопользовательским декодированием область достижимых скоростей имеет вид C(P ) = PF (R0,..., RK1 ) RK |Rj M W log 1+ W j + Pj () K1 i=0 Pi ()1[j < i ], (1.27) где Pj () Ч мощность, выделяемая в соответствии с некоторым правилом P для передачи данных j-го пользователя в том случае, когда каналы находятся в состоянии = (0,..., K1), F Ч множество всех правил распределения мощности, таких что M [ K1 Pj ()] P, 1(x) Ч индикаторная функция, равная 1 при выполнении логиj=0 ческого условия x и 0 в противном случае. Граница этой области может быть получена как множество решений оптимизационной задачи K1 P0 ()..PK1 () max M j= j log 1+ W j + Pj () K1 i=0 Pi ()1[j < i ] (1.28) при условии K M j=0 K1 j=0 j Pj () P = 1. Заметим, что решение этой оптимизационной зададля параметров j : чи соответствует двухуровневому УводонаполнениюФ в пространстве пользователей и в В [145] данная схема также называется MC-DS-CDMA, однако это название представляется не вполне адекватным ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 1 пространстве состояний канала. Если 0 = 1 =... = K1 = K, то оптимальным правилом P разделения является выделение всего канала для передачи данных пользователя с наименее зашумленным каналом. Аналогично случаю временного разделения, пропускная способность частотноселективного канала равна Pj (f ) K df, (R,..., RK1) R |Rj log2 1 + C(P ) = K1 0 W 1 PF + Pi (f )1[j (f ) < i (f )] j (f ) i=0 (1.29) K1 где F = P : j=0 W Pj (f )df P и интегрирование ведется по всей полосе частот, занимаемой системой. 1 Заметим, что при 0 = 1 =... = K1 = K оптимальное правило P, получаемое путем решения соответствующим образом модифицированной оптимизационной задачи (1.28), соответствует частотному разделению канала. При других значениях этих параметров совместное использование (на основе кодового или временного разделения) отдельных частот может оказаться неизбежным. Необхоимо также отметить, что максимизация взвешенной пропускной способности (см. (1.28), (1.23)), используемая при построении области достижимых скоростей, не позволяет гарантировать фиксированную пропускную способность канала для отдельных пользователей. Можно показать [80], что область достижимых скоростей при использовании кодового разделения без последовательного декодирования входит в область достижимых скоростей, соответствующую временному разделению. Тем не менее, в данной работе будут рассматриваться системы вещания, основанные на кодовом разделении с однопользовательским декодиронием, т.к. использование кодового разделения позволяет существенно упростить отображение передаваемых сигналов на многочастотную систему.
1.4 Помехоустойчивое кодирование В данном разделе описываются некоторые методы помехоустойчивого кодирования, используемые в последующих главах.
1.4.1 Основные понятия Пусть задано векторное пространство An, на котором определена метрика d(y), y An. Тогда [n, M, d] кодом C называется некоторое подмножество векторов из этого пространства, где M Ч размер кода (число векторов), d = min d(y1 y2 ) Ч его минимальное y1,y2 C, y1 =y расстояние. При практическом использовании кодов, исправляющих ошибки, необходимо также задание некоторого алгоритма, позволяющего по произвольному вектору z найти ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ ближайшее к нему кодовое слово y = arg min d(z y). В большинстве случаев полное yC решение этой задачи оказывается чрезмерно сложным, вследствие чего используются различные субоптимальные методы, основанные на некоторых специальных свойствах кода C. Кроме того, желательно наличие компактного способа задания кода и эффективного метода кодирования, т.е. отображения log2 M-битного сообщения в одно из слов C. Наибольшее распространение получили линейные коды над GF (q) [169]. В качестве метрики здесь наиболее часто используется метрика Хемминга Линейным (n, k, d) кодом называется k-мерное линейное подпространство GF (q)n. Очевидно, что размер кода равен M = q k. Всякий линейный код C характеризуется порождающей и проверочной матрицами G и H, причем C = {y GF (q)n |y = mG, m GF (q)k }, y C : H T y = 0. Видно, что GH T = 0. Несложно показать, что если принятый вектор может быть представлен как z = y + e, где e Ч вектор ошибки, то исходный вектор y может быть однозначно восстановлен, если wt(e) t = (d 1)/2. Если вес вектора ошибки превышает это значение, то может быть использовано списочное декодирование, состоящее в поиске всех кодовых слов, совпадающих с вектором z не менее чем в позициях. Известно достаточно много классов линейных кодов, обладающих эффективными алгоритмами декодирования. Далее будут описаны два класса линейных кодов, которые будут рассматриваться в последующих главах. d(y) = wt(y) = |{i|yi = 0}|. (1.30) 1.4.2 Коды Рида-Соломона Коды Рида-Соломона являются одним из наиболее популярных классов корректирующих кодов, используемых в современных системах. Их использование предусмотрено стандартами физического уровня многих телекоммуникационных систем. (n, k, d) код Рида-Соломона над GF (q) является циклическими кодом с порождающим многочленом g(x) = d2 (x +i ), где Ч примитивный элемент GF (q), 0, n q, т.е. код может i=0 быть представлен как n CRS = {(y1,..., yn )|Y (x) = yi xi = m(x)g(x), deg m(x) < k}, i= (1.31) где m(x) Ч многочлен, коэффициентами которого являются информационные символы. Из границ БЧХ и Синглтона [169] следует, что минимальное расстояние кода равно d = n k + 1. Во многих приложениях целесообразно применять систематическое кодирование, т.е. использовать для передачи данных кодовые слова, имеющие своей частью исходное сообщение. Несложно показать, что всякий многочлен вида c(x) = xd1 m(x) xd1 m(x) mod g(x) соответствует кодовому слову кода Рида-Соломона и его коэффициенты cd1,..., cn1 совпадают с коэффициентами информационного многочлена m(x). Поэтому данное выражение представляет собой способ систематического кодирования как кодов Рида-Соломона, так и любых других циклических кодов[169].
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ С другой стороны, все кодовые слова могут быть представлены как CRS = {(y1,..., yn )|yi = m(xi ), xi GF (q), i = 1..n}, (1.32) где xi Ч различные элементы конечного поля, называемые локаторами кода. Ясно, что для одного и того же многочлена m(x) описанные способы кодирования дают разные кодовые слова, но несложно показать, что они все эквивалентны6. Далее будут рассмотрены два метода алгебраического декодирования кодов РидаСоломона. Классическое синдромное декодирование Пусть z = y + e, причем y CRS, wt(e) t. В многочленном представлении принятый wt(e) n1 вектор может быть записан как Z(x) = Y (x) + E(x), Z(x) = i=0 zi xi, E(x) = l=1 ejl xjl, где Ejl Ч значение ошибки, произошедшей в символе jl. Вычислим синдромный многочлен этого вектора d S(x) = i= Si xi : Si = Z(+i ) = M(+i )g(+i) + E(+i) = E(+i ).
(1.33) Как и для всех линейных кодов, синдром принятого вектора зависит только от вектора ошибки. Предположим, что в результате воздействия канала искажению подверглись символы jl J : |J| t, т.е. Si = ejl (+i)jl.
jl J Величины El = ejl и Xl = jl носят названия значений и локаторов ошибок. Тогда d S(x) = jl J ejl jl i= (Xl x)i Т.к. 1 (Xl x)d1 = (1 Xl x) d2 i i=0 (Xl x) 1 mod xd1, получим El jl mod xd1 1 Xl x (1 Xl x) (1.34) S(x) = jl J Пусть (x) = jl J Ч многочлен локаторов ошибок (т.е. многочлен значений ошибок (x) = jl J Xl являются его корнями). Кроме того, введем El l 1 Xl x El l jp J/jl (1 Xp x) = (x) jl J Третий способ Ч при = 0.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Таким образом, получено ключевое уравнение для декодирования кодов Рида-Соломона (x) = (x)S(x) mod xd1. (1.35) Это уравнение может быть решено с помощью алгоритмов Берлекэмпа-Месси или Евклида [155]. После того, как получен многочлен (x), необходимо найти его корни, указывающие местоположение искаженных символов. Далее значения ошибок могут быть найдены как (алгоритм Форни) Xl (X 1 ) El = l l1 (1.36) (Xl ) Таким образом, задача вычисления вектора ошибки по принятому вектору разбивается на следующие этапы: 1. Вычисление синдромного многочлена (1.33). 2. Решение ключевого уравнения (1.35). 3. Поиск корней многочлена локаторов ошибок (1.34). 4. Вычисление значений ошибок (1.36). При реализации этого метода оказывается, что наиболее трудоемкими этапами являются вычисление синдрома и поиск корней многочлена локаторов ошибок. В разделе 1.4.3 представлено описание некоторых вычислительных алгоритмов, которые могут быть использованы для эффективной реализации этих шагов. Списочное декодирование Рассмотрим задачу списочного декодирования (n, k, n k + 1) кода Рида-Соломона, т.е. поиска для любого заданного вектора Y = (y1,..., yn ) всех кодовых слов, совпадающих с ним по крайней мере в позициях. С учетом (1.32), она может быть cформулирована как поиск всех многочленов f (j) (x) : deg f (j) (x) < k, совпадающих с заданным вектором (y1,..., yn ) по крайней мере в точках xi. Определение 1. j-й производной Хассе многочлена g(x) в точке x0 называется коэффициент при xj многочлена g (x) = g(x + x0 ): g [j](x0 ) = coe(g(x + x0 ), xj ) = j j j Cj gj xj j Заметим, что производная Хассе связана с обычной производной соотношением 1 j g(x) g (x0 ) = j! xj. Аналогично могут быть определены частные производные Хассе [j] x=x многочлена от двух переменных Q(x, y) = j1,j qj1 j2 xj1 y j2 :
j j Cj 1 Cj 2 qj1 j2 x j1 j1 j2 j2 1 2 j j1 j2 j2 y Q[j1,j2 ] (x0, y0 ) = coe(Q(x + x0, y + y0 ), xj1 y j2 ) = ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Определение 2. (wx, wy )-взвешенной степенью одночлена xi y j называется wdeg(wx,wy ) xi y j = iwx + jwy (wx, wy )-взвешенной степенью многочлена Q(x, y) = i,j qij xi y j называется максимальная (wx, wy )-взвешенная степень его членов qij xi y j : qij = 0. Многочлен Q(x, y) имеет корень кратности r в точке (x0, y0 ), если все его производные Хассе общего порядка до r равны 0. В работе [52] был предложен алгоритм списочного декодирования кодов РидаСоломона с полиномиальной сложностью, состоящий из следующих этапов: 1. Построить ненулевой многочлен Q(x, y) : wdeg(1,k-1) Q(x, y) l, имеющий точки (xi, yi ) корнями кратности r: i = 1..n, j1 + j2 < r : Q[j1,j2 ] (xi, yi ) = j j Cj 1 Cj 2 qj1 j2 xi j1 j1 j2 j2 1 2 j j1 j2 j2 yi = (1.37) 2. Найти все f (j) (x) : Q(x, f (j) (x)) = 0. Решениями задачи списочного декодирования являются все вектора (j) {(z1,..., zn )|zi (j) (j) = f (j) (xi ), deg f (j) (x) < k, {i|zi = yi } } (j) Здесь l и r являются параметрами алгоритма;
в [52, 95] представлены условия на них, позволяющие максимизировать число исправляемых ошибок. Введем лексикографическое упорядочение одночленов x y lex xa y b < a ( = a b). Т.к. алгоритм Гурусвами-Судана накладывает ограничения на взвешенную степень, введем упорядочение одночленов по их взвешенной степени: f wdeg g wdeg(1,k-1) (f ) < wdeg(1,k-1) (g) wdeg(1,k-1) (f ) = wdeg (1,k-1) (g) f lex g Пусть LT Q(x, y) обозначает старший член Q(x, y) относительно упорядочения wdeg. Для построения решения задачи интерполяции на первом шаге алгоритма достаточно 2 рассмотреть многочлены вида Q(x, y) = N qi mi, где N = nCr+1 Ч число уравнений в i=0 (1.37);
mi Ч все одночлены взвешенной степени не более l, упорядоченные в соответствии с отношением wdeg : m0 wdeg m1 wdeg... wdeg mi wdeg....
2 nCr+1 2 < Cr +1, k Несложно показать [95], что в этом случае wdeg(0,1) Q(x, y) r 1, где 2 Cr (1.38) Разобъем все многочлены Q(x, y) : wdeg(0,1) Q(x, y) r 1 на r непересекающихся классов Gj = {Q(x, y)| LT Q(x, y) = y j xi, i 0}. Будем последовательно обрабатывать ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ ITERATIVEINTERPOLATE(n, r, {(xi, yi ), i = 1..n}) 1 for j := 0 to r 1 2 do Qj (x, y) := y j 3 for i := 1 to n 4 do for := 0 to r 1 5 do for := 0 to r 1 [,] 6 do j := Qj (xi, yi ), j = 0..r 1 j0 := arg min Qj (x, y) j:j = 8 9 10 for j = j0 do Qj (x, y) := Qj (x, y) jj Qj0 (x, y) 0 Qj0 (x, y) := (x xi )Qj0 (x, y) return minj Qj (x, y) Рис. 1.6 Интерполяционный алгоритм Нильсена интерполяционные уравнения (1.37), строя на каждом шаге для каждого Gj многочлен, удовлетворяющий всем обработанным условиям. При этом допустимыми действиями являются умножение многочлена на константу, сложение многочлена из одного класса с меньшим многочленом из другого класса и умножение на многочлен первой степени. Ясно, что применение этих операций к многочлену не выводит его за пределы его класса. На рис. 1.6 представлен алгоритм Нильсена, реализующий описанный подход [95, 94]. В [95] показано, что многочлены Qj (x, y), получаемые после обработки всех интерполяционных условий, являются минимальными в классах Gj, удовлетворяющими им. Несложно показать, что алгоритм Нильсена с любым порядком обработки интерполяционных точек приведет к эквивалентным результатам. Видно, что сложность вычисления одной производной Хассе многочлена, имеющего s членов, равна O(s), т.е. асимптотическая сложность вычисления вектора невязок на каждом шаге равна O(r s) = O(r nr 2 ) = O(nr 3). Аналогично, сложность манипуляций с многочленами равна O(nr 3 ). Таким образом, общая асимптотическая сложность алгоритма составляет O(n2 r 5 ). Для поиска корней y = f (j) (x) интерполяционного многочлена Q(x, y), получаемого на первом шаге, может быть использован алгоритм Рота-Рукенштейна[113]. Этот подход k i основан на следующем свойстве. Предположим, что f (x) = i=0 fi x является корнем многочлена Q(x, y), рассматриваемого как полином от y, с коэффициентами, являющимися полиномами от x:
l Q(x, f (x)) = j= hj (x)(f (x))j = Если это необходимо, разделим многочлен Q(x, y) на множитель xs максимально возj можной степени. Тогда Q(0, f (0)) = l hj (0)f0 = 0. Решая это уравнение относительно j=0 f0, получим набор возможных значений начальных коэффициентов искомых многочленов f (x). Пусть f (x) = f (x)f0 = f1 + f2 x +.... Пусть Q (x, y) = Q(x, y + f0 );
Q (x, y) = Q (x, xy). x ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ RECONSTRUCT(Q(x, y), k, i, ) 1 Найти наибольшее t, такое что xr делит Q(x, y) 2 M(x, y) := Q(x, y)/xr ;
3 Найти корни mj многочлена от одной переменной M(0, y) ;
4 for Each root mj 5 do [i] := mj ;
6 if i = k 1 7 then return ;
8 else M (x, y) := M(x, y + mj );
9 M (x, y) := M(x, yx);
10 RECONSTRUCT(M (x, y), k, i + 1, );
Рис. 1.7 Поиск корней многочлена от двух переменных Тогда Q (x, f (x)) = Q (x, xf (x)) = Q(x, xf (x) + f0 ) = Q(x, f (x)) = Таким образом, коэффициент f1 может быть найден аналогично f0. Таким образом, корни многочлена от двух переменных могут быть рекурсивно выражены через корни многочленов от одной переменной. Асимптотическая сложность данного алгоритма равна O((l log2 l)k(n+ l log q)). Таким образом, вычислительно наиболее сложным этапом списочного декодирования кодов Рида-Соломона является интерполяционный шаг. Необходимо отметить, что для высокоскоростных кодов может быть выполнено преобразование данных, позволяющее снизить размерность задачи [73].
1.4.3 Вычислительные алгоритмы алгебраического декодирования В данном разделе представлено описание некоторых вычислительных алгоритмов, которые могут быть использованы для повышения производительности вышеописанных методов алгебраического декодирования кодов Рида-Соломона. Как было указано выше, наиболее трудоемкими этапами классического синдромного декодирования кодов РидаСоломона являются поиск корней многочленов над конечным полем, т.е. нахождение t x GF (q) : f (x) = fi xi = 0, i= и вычисление значений многочлена в наборе точек n Fj = f (j ) = i= fi ij.
Последняя задача может также рассматриваться как вычисление неполного дискретного преобразования Фурье многочлена над конечным полем. Заметим, что аналогичные вычислительные задачи возникают и при списочном декодировании кодов Рида-Соломона.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Известно достаточно большое число алгоритмов решения этих задач, среди которых можно выделить следующие: 1. Процедура Ченя является переборным методом поиска корней многочлена f (x) = t i i=0 fi x и состоит в переборе элементов поля с вычислением значений многочлена для каждого xj GF (2m ). Если многочлен f (x) не имеет кратных корней и требуется найти d корней из t при наличии n возможных кандидатов, то вычисления могут быть прекращены немедленно после нахождения последнего из d корней. В этом случае математическое ожидание числа обращений к процедуре вычисления значений многочлена равно W = W (d, n, t) = d n+1 t+1 (1.39) Доказательство. Вероятность того, что k-ый элемент множества возможных корней X = {xi GF (2m )|i = 1..n} окажется d-ым корнем равна p{f (xk ) = 0d } = d td Ck Cnk d t Cn k Математическое ожидание числа обращений к процедуре вычисления значений многочлена при поиске d корней равно d k p{f (xk ) = 0d } = t W= Cn k=1 Используя тождество r n m m+n+1 Cs+k Crk = Cr+s+1, k=0 n n d td Ck Cnk, k= получаем требуемое. Процедура Ченя может быть реализована двумя способами. Алгоритм Ченя [22] использует массив Q, инициализируемый коэффициентами многочлена: Qi := fi. На каждом шаге j значение многочлена вычисляется как f (xj ) = t Qi, после чего i=0 элементы массива обновляются: Qi := Qi i. Схема Горнера является оптимальным методом вычисления значения многочлена в одной точке. Значения вычисляются как f (x) = f0 + x(f1 + x(f2 +... + ft )). В обоих случаях сложность равна CChien = W (Cmul + Cadd )t, (1.40) где Cmul и Cadd Ч сложности операций умножения и сложения соответственно. 2. Орбитальный метод поиска корней многочленов [23]. Предположим, что исходный многочлен имеет два корня, лежащих в одном циклотомическом классе, т.е. f (x) = k f (x)(x x0 )(x x2 ). Тогда 0 GCD(f (x), f2k (x)) = (x x2 ), k (1.41) ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ где f2k (x) = i= t fi2 xi k (1.42) Многочлены, получаемые на основе соотношения (1.41), имеют, как правило, небольшую степень, что позволяет использовать для них эффективные методы поиска корней. Таким образом, часть корней может быть исключена в соответствии со следующим алгоритмом: Х Построить набор f2k (x), k = 1..r/2, где r Ч максимальный размер циклотомического класса по модулю 2m 1;
Х Вычислить gk (x) = GCD(f (x), f2k (x)) k Х Найти корни x2 многочленов gk (x). Корнями исходного многочлена являются ki k пары (xki, x2 ). ki Х Разделить исходный многочлен на многочлена j (x xj ), где xj Ч все известные корни Х Произвести перебор значений ji по всем циклотомическим классам по модулю 2m 1, проверяя выполнение соотношения f (ji ) = 0. При обнаружении такого значения оно должно быть внесено в список известных корней. Перебор элементов циклотомического класса, в котором на одном из этапов этой процедуры был найден хотя бы один корень, может не проводиться. Для ускорения вычислений на последнем этапе после нахождения очередного корня xi многочлен может быть разделен на (x xi ). 3. Поиск наименьшего аффинного кратного Определение 3. Линеаризованными многочленами над GF (2m ) называются многочлены вида i l(x) = li x2, li GF (2m ) i Несложно показать, что для линеаризованных многочленов выполняется l(a + b) = l(a) + l(b), a, b GF (2m ). (1.43) Следствием этого свойства является следующая теорема, представленная здесь в немного модифицированном виде: Теорема 1 ([154]). Пусть y GF (2m ) и элементы 0, 1,..., m1 образуют некоторый базис этого поля. Если m y= i= yi i, yi GF (2), m то l(y) = yil(i ).
i= ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Обобщением линеаризованных многочленов являются аффинные многочлены, т.е. многочлены вида a(x) = l(x) + b, b GF (2m ), где l(x) Ч линеаризованный многочлен. Теорема 1 позволяет использовать для поиска корней аффинных многочленов классические методы решения систем линейных уравнений. Действительно, если веm1 личина y = i=0 yii является корнем многочлена a(y) = l(y) + b, где элементы i образуют стандартный базис, то выполняется l(0 ) l(1 ) (1.44) (y0, y1,..., ym1 )... = (b0, b1,..., bm1 ), l(m1 ) где l(i ) рассматриваются как вектора над GF (2). Следовательно, решая систему (1.44), можно найти все корни аффинного многочлена.
Ввиду того, что для поиска корней аффинного многочлена может быть использован алгоритм Гаусса, задача нахождения корней произвольного многочлена f (x) может быть заменена задачей поиска кратного ему аффинного многочлена a(x) = p(x)f (x), поиска его корней и отбрасыванием паразитных корней многочлена p(x). Алгоритм для нахождения наименьшего аффинного кратного произвольного многочлена приведен в [154]. 4. Метод Берлекэмпа-Рамсея-Соломона поиска корней многочленов степени 2. Предположим, что необходимо найти все простые корни многочлена f (x) = x2 + + b. ax В тех случаях, когда a = 0, многочлен имеет один корень кратности 2 x = b, что свидетельствует об ошибке. В противном случае выполним подстановку x = ay. Тогда многочлен преобразуется в g(y) = y 2 + y + c, c = ab2. Т.к. полученный многочлен является аффинным, для нахождения его корней может быть использован метод Берлекэмпа-Рамсея-Соломона [154]. Поиск корней сводится к нахождению решений системы l(1) (y0, y1,..., ym1 )... = (c0, c1,..., cm1 ), (1.45) l(m1 ) где l(x) = x2 + x. Эта система имеет не более 2 решений. Необходимо отметить, что множество решений этой системы уравнений может быть построено заранее в общем виде. Это дает возможность найти решение уравнения к помощью набора простых логических схем, реализующих вектора умножение на столбцы некоторой матрицы.
5. Метод Чена поиска корней многочленов степени 2. Для поиска одного из корней квадратного трехчлена над GF (2m ), m mod 2 = 1 после его преобразования к виду G(y) = y 2 + y + b может использоваться формула [20] y1 = iI b2 = jJ i b2 ;
I = {1, 3,..., m 2}, J = {0, 2,..., m 1} j (1.46) ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ В случае четных m необходимо воспользоваться модифицированным следом эле(m2)/ мента Tr4 (a) = i= a2. Если многочлен y 2 + y + b имеет корни в GF (2m ), то 2i Tr4 (b) {0, 1}. В тех случаях, когда m = 2 mod 4, справедливы соотношения y1 = y1 = + 2+4i (m6)/4 (b + b2 )2, i=0 2+4i (m6)/4 (b + b2 )2, i= Tr4 (b) = 0, + = 1, Tr4 (b) = (1.47) Если m = 0 mod 4, то аналогичным образом может быть показано, что m/ y =S+S +b 2m m/41 m/ 1 + b 2i+m/ i=, (1.48) где S = j=1 i=j b 2i1+m/2 +22j.
6. Табличный метод поиска корней многочленов состоит в сведении произвольного многочлена к канонической форме с небольшим числом параметров и использовании их в качестве ключа для поиска по заранее подготовленной таблице корней многочленов [23]. Основным недостатком этого метода является наличие сравнительно больших таблиц корней с нерегулярной структурой, затрудняющей поиск. 7. Аналитический метод поиска корней многочленов третьей и четвертой степени основывается на известных выражениях для корней многочленов малой степени [158]. 8. Алгоритм Кули-Тьюки вычисления дискретного преобразования Фурье [155, 150]: n = n n, = n, = n i = i + n i, i = 0,..., n 1, i = 0,..., n 1 j = n j + j, j = 0,..., n 1, j = 0,..., n n 1 n Fj,j = i = i j i j i = i j fi,i, где Fj = Fj,j. Сложность данного алгоритма равна WCT (n(n + n ) + n)Cmul. 9. Алгоритм Гуда-Томаса вычисления дискретного преобразования Фурье: n = n n, N n + N n = 1, НОД(n, n ) = 1, = N (n ), = N (n ) i = i mod n, i = i mod n j = N j mod n, j = N j mod n n 1 n 2 Fj,j = i = i j i = i j fi,i Сложность данного алгоритма равна WGT n(n + n )Cmul.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 10. Метод Рейдера. Компоненты векторов f и F могут быть переупорядочены как fk = f k, Fl = F l, k, l = 0..n 2, где Ч порождающий элемент группы порядка n 1. Т.к. k : k = 0, выражение для ДПФ может быть переписано как n2 n2 n2 xl fk l=0 k= k+l F (x) = + f l= xl Видно, что при фиксированном l изменение k приводит к циклическому сдвиk+l i n2 i гу последовательности { }. Вводя обозначения i =, (x) = i=0 i x и f (x) = k fk xk, получим F (x) = f (x)(x) (mod xn1 1) + f0 xn1 1 x Таким образом, алгоритм БПФ может быть построен на основе быстрого алгоритма вычисления циклической свертки. 11. Алгоритм Герцеля для конечных полей. Пусть xn 1 = i i (x), где i (x) GF (q)[x] Ч минимальные многочлены элементов поля GF (q m ), n = q m 1. Всякий элемент этого поля является корнем ровно одного многочлена i (x). Вычислим остатки от деления многочлена f (x) на минимальные многочлены: f (x) = qi (x)i (x) + i (x) Тогда f (j ) = i (j ) для всех j : i (j ) = 0. Ясно, что вычисление значения многочлена i (x) требует намного меньших вычислительных затрат, чем аналогичная операция над многочленом f (x). Вычисление собственно многочленов i(x) требует только операций над простым подполем GF (q), которые, как правило, существенно проще операций в GF (q m ). Наличие ограничений на свойства n приводит к тому, что построение эффективного алгоритма БПФ для практически используемых длин становится самостоятельной задачей с плохо формализованными методами решения [160]. Более того, как было показано выше, при реализации алгоритмов декодирования кодов Рида-Соломона требуется вычисление неполного ДПФ или ДПФ многочлена малой степени. Большинство из описанных быстрых алгоритмов оказываются абсолютно неэффективными при такой постановке задачи.
1.4.4 Низкоплотностные коды Основные понятия Низкоплотностные коды были предложены Галлагером [43]. Отличительной особенностью (n, k)-низкоплотностного кода является существование разреженной проверочной m n, n k m матрицы H, т.е. такой матрицы, у которой число ненулевых элементов пренебрежимо мало по сравнению с ее размерами. Проверочная матрица может быть представлена в виде графа Таннера. Граф Таннера является двудольным неориентированным графом, имеющим n символьных и m проверочных узлов, причем i-ый символьный ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ узел соединен с j-ым проверочным узлом тогда и только тогда, когда Hji = 1. Код называется (wc, wr )-регулярным, если каждый столбец и каждая строка проверочной матрицы имеют ровно wc и wr ненулевых элементов соответственно. В противном случае код называется нерегулярным. (, )-нерегулярный код характеризуется многочленами (x) и (x) распределения степеней символьных и проверочных узлов соответственно. В многочлене dv (x) = d= d xd d равно доле ребер в графе Таннера, соединенных с символьными узлами степени d, где dv обозначает максимальную степень узла. Ясно, что (1) = 1. Аналогичным образом определяется многочлен распределения степеней проверочных узлов (x). Кроме того, несложно показать, что скорость кода связана с распределениями степеней узлов следующим образом: 1 (x)dx 0 r =1 1 (1.49) (x)dx 0 Итеративный алгоритм декодирования Предположим, что используется двоичный низкоплотностной код и допустим, что передача данных ведется по аддитивному Гауссовскому каналу, причем нулевые биты кодовых слов y передаются как 1, а единичные Ч как 1, т.е. ri = (1)yi + i, i = 1..n. (1.50) Алгоритм мягкого декодирования низкоплотностных кодов известен под названиями алгоритма передачи сообщений, алгоритма Усумма-произведениеФ и алгоритма распространения доверия. Его суть сводится к итеративному вычислению апостериорных вероятностей того, что каждый из символов переданного кодового слова y = (y0,..., yn1 ) равен 1 на основе принятого вектора r = (r0,..., rn1 ), т.е. P (yi = 1|r), или, эквивалентно, логарифмического отношения правдоподобия7 L(yi ) = ln P (yi = 0|r). P (yi = 1|r) Алгоритм декодирования состоит в передаче сообщений по сети, задаваемой графом Таннера. Во время первой полуитерации сообщения пересылаются от каждого из символьных узлов к смежным с ним проверочным узлам. Информация, содержащаяся в этих сообщениях, соответствует вероятности того, что соответствующий символ равен 1 при условии r и всех сообщений, принятых узлом на предыдущей полуитерации, причем сообщение, посылаемое любому из узлов вычисляется без учета сообщения, поступившего от этого узла на предыдущей полуитерации. Во время второй полуитерации сообщения посылаются от проверочных узлов к символьным узлам. При этом сообщения указывают Обычно отношение правдоподобия определяется как отношение вероятности 1 к вероятности 0, но в данном случае удобнее воспользоваться обратным отношением.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ вероятность того, что проверочное уравнение выполняется, если соответствующий символ равен 1. Введем следующие обозначения: 1. Vj Ч множество символьных узлов, соединенных с проверочным узлом #j;
2. Vj \i = Vj \{i};
3. Ci Ч множество проверочных узлов, соединенных с символьнным узлом #i;
4. Ci \j = Ci \{j};
Путем несложных преобразований можно показать [114], что декодирование низкоплотностных кодов может быть выполнено следующим образом: 1. Вычислить лог. отношения правдоподобия принятых символов. Для аддитивного Гауссовского канала с дисперсией шума, равной 2, они задаются выражением L(qij ) = L(yi ) = 2ri / 2. 2. Вычислить {L(rji)} в соответствии с выражением L(rji ) = i Vj \i (1.51) где ij = sign L(qij ), ij = |L(qij )|, и 1 (x) = (x), x > 0. Заметим, что ющее илиФ.
i j i Vj \i (i j ), (1.52) (x) = log tanh(x/2) i Vj \i (1.53) i j соответствует операции Уисключа 3. Вычислить {L(qij )} в соответствии с выражением L(qij ) = L(ci ) + j Ci \j L(rj i ).
(1.54) 4. Вычислить апостериорные лог. отношения правдоподобия для символов принятого вектора в соответствии с выражением L(Qi ) = L(ci ) + jCi L(rji ).
(1.55) 5. Проверить слово y = (0,..., yn1 ), где yi = 1 если L(Qi ) < 0, на предмет принад y лежности коду, т.е. y H T = 0. При выполнении этого условия производится останов. 6. Переход к шагу 2, до тех пор пока не будет превышено некоторое предельное число итераций.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Анализ и построение низкоплотностных кодов Графовая структура низкоплотностных кодов позволяет произвести анализ поведение декодера (по крайней мере, асимптотически). В [110, 111] был представлен метод вычисления распределений сообщений, циркулирующих по сети, задаваемой графом Таннера, на каждой итерации вышеописанного алгоритма декодирования. Это позволяет для заданной дисперсии шума в канале найти вероятность наличия в сети ошибочных сообщений после нескольких итераций. Кроме того, в [110] было доказано существование порогового отношения сигнал/шум 0, такого что для всех > 0 декодирование низкоплотностного кода бесконечной длины с заданными распределениями (x) и (x) является успешным. Это позволяет сформулировать оптимизационную задачу нахождения (x) и (x), минимизирующих 0 при заданной скорости кода. Вычислительные эксперименты позволяют получить оптимальные значения порога, вплотную приближающиеся к границе Шеннона [98]. На основе полученных таким образом параметров (x) и (x) могут быть алгоритмически построены коды умеренной длины с очень хорошими характеристиками. Вместе с тем, при построении низкоплотностных кодов необходим также учет как классических характеристик корректирующих кодов (например, минимального расстояния), так и специфических свойств итеративного алгоритма декодирования (псевдокодовых слов) [136]. Существующие классы низкоплотностных кодов могут быть разделены на псевдослучайные конструкции [104, 62, 29, 14], основывающиеся на оптимизированных распределениях (x) и (x), и алгебраические конструкции [142, 66, 133, 67, 79, 30, 27, 74, 112, 35], ориентированные на максимизацию минимального расстояния кода.
1.4.5 Фактор-графы Основные понятия Графы Таннера, используемые для описания низкоплотностных кодов, являются частным случаем фактор-графов [76]. Рассмотрим некоторую функцию g(x1,..., xn ) : A = A1 A2 An R. Предположим, что эта функция может быть факторизована как K g(x1,..., xn ) = i= fi (Xi ), (1.56) где Xi Ч некоторые комбинации переменных xj, j = 1..n. Построим двудольный факторграф, имеющий n символьных узлов, соответствующих переменным xj, и K факторузлов, соответствующих fi, а также набора ребер, причем символьный узел xj соединен с факторным узлом fi тогда и только тогда, когда xj Xi. Таким образом, получено графическое представление арифметического выражения g(x1,..., xn ). Введем понятие граничной функции gi (a) = xA:xi =a g(x).
Эту функцию удобно также обозначать следующим образом: gi (xi ) = (xi ) g(x1,..., xn ), (1.57) ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ т.е. суммирование выполняется по всем переменным, кроме xi. Примером граничной функции может быть вероятность того, что i-й символ кодового слова равен 1, вычисляемая на основе всех остальных компонентов принятого вектора. Однако область применения фактор-графов не ограничивается построением алгоритмов декодирования. Если функции fi (Xi ) представлены в виде граничных функций (возможно, с использованием скобочных конструкций), то соответствующий фактор-граф непосредственно задает процедуру вычисления gi (xi ). Для этого необходимо лишь представить его как дерево, имеющее xi своим корнем. Подробное описание этой процедуры приведено в [76]. Несложно заметить, что эта конструкция очень близка дереву выражений, используемому в теории построениия компиляторов. В тех случаях, когда необходимо вычислить не одну, а все граничные функции gi (xi ), представление в виде фактор-графа позволяет существенно снизить сложность вычислений, т.к. в этом случае одинаковые выражения, встречающися в выражениях для различных i, могут вычисляться однократно. Если фактор-граф не имеет циклов, вычисления завершаются сразу же, как только по каждому ребру графа прошли по одному сообщению в обоих направлениях. При наличии циклов в графе вышеописанный формализм уже нельзя рассматривать как спецификацию вычислительного алгоритма в строгом смысле, т.к. выполнение любого из его шагов модифицирует исходные данные, используемые на некоторых других шагах, вследствие чего вычислительная процедура становится бесконечно длинной. Но оказывается, что при выполнении определенных условий, специфичных для конкретной решаемой задачи, существует некоторая неподвижная точка, к которой сходятся промежуточные значения. Представление быстрых алгоритмов в виде фактор-графов Оказывается, что многие вычислительные алгоритмы также могут быть представлены в виде алгоритмов на фактор-графах [76]. Одним из наиболее известных алгоритмов быстрого преобразования Фурье является метод, основанный на разбиении преобразуемой последовательности на две части и вычислении их БПФ по отдельности. Рассмотрим пример вычисления БПФ последовательности w = (w0, w1,..., w7 ), т.е.
Wk = n= wn nk, k = 0..7, где Ч примитивный корень восьмой степени из единицы. Пусть n = 4x2 + 2x1 + x0 и k = 4y2 + 2y1 + y0, yi, xi {0, 1}. Рассмотрим функцию g(n, k) = wn nk = g(x0, x1, x2, y0, y1, y2) = w4x2 +2x1 +x0 (4x2 +2x1 +x0 )(4y2 +2y1 +y0 ) = f (x0, x1, x2 )(1)x2 y0 (1)x1 y1 (1)x0 y2 (j)x0 y1 (j)x1 y0 x0 y0, где f (x0, x1, x0 ) = w4x2 +2x1 +x0, 16 = 8 = 1, 4 = 1, 2 = j. Таким образом, ядро ДПФ представлено в виде произведения УлокальныхФ функций, как показано на рисунке 1.8. Заметим, что g(x0, x1, x2, y0, y1, y2). Wk = W4y2 +2y1 +y0 = x0 x1 x ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Рис. 1.8 Фактор-граф алгоритма БПФ u0 u u2 u3 u4 u 0 11 1 11 1 11 1 c0 c1 c2 c3 c4 c5 c6 c 11 1 1 2 1 1 1 11 1 11 1 1 2 1 11 1 1 2 1 1 3 1 Рис. 1.9 Разреженное представление (8, 6, 3) РС-кода над GF (9) Заметим, что каждая из внутренних сумм вычисляется при фиксированных значениях переменных внешних сумм, т.е. ДПФ может рассматриваться как граничная функция, аналогично тому, как при декодировании низкоплотностных кодов таковыми являются отношения правдоподобия отдельных символов. Разреженное представление кодов Рида-Соломона Рассмотрим задание кодов Рида-Соломона как ДПФ информационной последовательности (см. (1.32)). Предположим, что длина кода равна N = 2m и существует алгоритм БПФ такой длины [146]. Тогда значения символов кодового слова могут быть представлены как ДПФ информационных символов, а вычисление ДПФ может быть осуществлено с помощью указанного алгоритма БПФ. Как было показано выше, алгоритмы БПФ представимы в виде фактор-графов, причем, согласно определению быстрого алгоритма, число ребер в этом графе должно быть мало по сравнению с n2 Ч числом элементов матрицы ДПФ, т.е. фактор-граф является разреженным. Отсюда следует, что коды Рида-Соломона также обладают представлением в виде разреженного фактор-графа. На рисунке 1.9 представлен пример фактор-графа, полученный с помощью описанного ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ ab соответствуют операции умножения указанcd ной матрицы на вектор (x0, x1 ), соответствующий левым входам в блок, т.е. уравнению (y0, y1 ) = A(x0, x1 ), где (y0, y1 ) Ч правые входы блока. Существенным недостатком данного метода являются ограничения на параметры кодов, вытекающие из условий существования ДПФ. метода [146]. Здесь блоки вида A = 1.4.6 Кодированная модуляция Очевидно, что применение помехоустойчивого кодирования приводит к определенному снижению скорости передачи данных. Поэтому автономное использование кодов, исправляющих ошибки, как правило, практикуется только в системах, ограниченных по мощности, т.е. R/B < 1, где R Ч скорость передачи данных, B Ч доступная полоса пропускания [172]. Для систем, ограниченных по полосе пропускания, т.е. R/B > 1, возникает необходимость применения методов модуляции с большим числом сигнальных точек. В этом случае непосредственное применение помехоустойчивого кодирования приводит к существенному увеличению отношения сигнал/шум, требуемого для достижения заданной скорости передачи. Данная проблема может быть решена путем совместной оптимизации модуляции и кодирования, т.е. кодированной модуляции. Т.к. вероятность ошибки при передаче по аддитивному Гауссовскому каналу зависит от расстояния между последовательностями, соответствующими различным кодовым словам, при проектировании схемы кодированной модуляции целесообразно найти такое отображение кодовых слов на точки сигнального множества, при котором это расстояние максимизируется [129]. Простейшим и достаточно эффективным способом осуществления этого является отображение на основе разбиения сигнального множества. Основная идея метода состоит в том, что сигнальное множество разбивается на несколько подмножеств так, что расстояние внутри каждого из подмножеств увеличивается (в большинстве случаев одинаково для каждого из полученных подмножеств). Далее биты кодового слова используются для выбора одного из полученных подмножеств. Конкретная сигнальная точка из выбранного подмножества выбирается далее с помощью некоторого количества некодированных битов. Особое распространение подобный метод получил в сочетании со сверточными кодами. Пример его использования представлен на рис. 1.10. Более общий способ построения схем кодированной модуляции Ч многоуровневое кодирование Ч был предложен в [63]. Основная идея метода состоит в том, что точки в сигнальном множестве выбираются с помощью некоторых индексов. Каждый из бит индекса xi может быть защищен с помощью отдельного корректирующего кода C i (см. рис 1.11(a)). Блок данных q разбивается на подблоки q0, q1,..., ql1. Каждый подблок кодируется своим (n, ki) кодом8 Ci, причем это могут быть и тривиальные коды с ki = n. Биты этих l1 кодовых слов обозначаются как xi, j = 1..n. Слова (x0,..., xj ) используются для выбора j j Для простоты здесь предполагается, что все коды имеют одинаковую длину, но в общем случае это необязательно.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 1 бит Сверт. код со скор. 1/ 2 кодированных бита Выбор смежного класса 2 / 22 ABCD Одна из 64 сигнальных точек 4 некодированных бита Выбор сигнальной точки A C A C A C A C B D B D B D B D A C A C A C A C B D B D B D B D A C A C A C A C B D B D B D B D A C A C A C A C B D B D B D B D Рис. 1.10 Решеточно-кодированная модуляция n точек из сигнального множества. Тогда кодовая скорость полученной схемы равна l R= i= 1 Ri = n l ki = i= k n (1.58) По сравнению с решеточно-кодированной модуляцией многоуровневое кодирование предоставляет намного большую свободу в выборе скорости передач, т.к. размерность сигнального множества и скорости кодов могут выбираться практически независимо. Кроме того, могут использоваться любые известные классы корректирующих кодов. Однако подбор скоростей этих кодов требует специального анализа. Неверный их выбор может существенно ухудшить качество работы из-за распространения ошибок, произошедших на нижних уровнях кодирования. Известно достаточно много методов преодоления этой проблемы (см., например, [143]), но оказывается, что намного проще выбрать надлежащим образом скорость кодов, чем реализовать сложный алгоритм демодуляции. Рассмотрим декодирование многоуровневого кода. Взаимная информация между переданным символом s A и принятым сигналом r Y, где A Ч используемое сигнальное множество, а Y Ч выходной алфавит канала, может быть записана как I(Y ;
A) = I(Y ;
X 0, X 1,..., X l1 ) = I(Y ;
X 0 ) + I(Y ;
X 1 |X 0 ) +... + I(Y ;
X l1|X 0,..., X l2 ), (1.59) 0 1 l1 где I(Y ;
X, X,..., X ) взаимная информация между адресным вектором x {0, 1}l и принятым сигналом y Y. Это выражение задает естественный способ декодирования многоуровневых кодов (см. рис. 1.11(b)): компонентные коды декодируются начиная с нижнего уровня с учетом решений, принятых на предыдущих уровнях. Эта процедура носит название многошагового декодирования (multi-stage decoding). Кроме того, из описания этого алгоритма следует, что скорости компонентных кодов должны выбираться в соответствии с пропускными способностями эквивалентных подканалов, соотвествующих ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ ql 1 q Кодер El xl Декодер l-...
Разделение потока данных x l q1 q Кодер x1 E1 E0 x Отображение a y... Декодер x Кодер Декодер x (a) Многоуровневый кодер (b) Многошаговый декодер Рис. 1.11 Многоуровневое кодирование компонентам адресного вектора [137]. Эти пропускные способности могут быть вычислены как C i = Ki Ki+1, (1.60) где Ki Ч пропускная способность сигнального подмножества, соответствующего i фиксированным кодовым символам. Пропускная способность K(B) произвольного множества равновероятных сигнальных точек B может быть вычислена с помощью выражения (1.2) [60]. Предполагая, что шум является Гауссовским, получим 2 (yam ) 2 (yam ) 1 e 22 1 dy (1.61) K(B) = e 22 log2 |B| (yak )2 |B| a B 2 2 2 2 m ak B e Другими правилами выбора скоростей являются [137]: 1. Правило сбалансированных расстояний. Несложно заметить, что минимальное Евклидово расстояние между различными кодовыми словами многоуровневого кода равно d = min(dl l ), l где dl Ч минимальное расстояние l-го компонентного кода, а l Ч расстояние между точками на l-м уровне разбиения сигнального множества. Ясно, что для максимизации d желательно иметь все произведения dl l примерно равными. Однако вероятность ошибки декодирования зависит не только от минимального расстояния кода, но и от числа слов малого веса. Оказывается, что применение этого правила приводит к кодам с очень большим числом таких слов, что существенно увеличиает вероятность ошибки декодирования. 2. Правило равных вероятностей ошибки. Предположим, что известны выражения, позволяющие оценить вероятности ошибки декодирования компонентных кодов с различными их параметрами. Тогда целесообразно выбрать параметры кодов таким образом, чтобы вероятность ошибки на всех уровнях была примерно одинаковой.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 3. Правило экспонент кодирования основывается на границе для вероятности ошибки при случайном кодировании [161]. Данное правило требует, чтобы значения вероятности ошибки, даваемые этой границей, были одинаковы для всех уровней. 4. Правило скоростей среза применимо к кодам, не достигающим пропускной способности канала. Например, при использовании сверточных кодов и последовательного декодирования [171], предельно достижимая скорость передачи носит название скорости среза. Данное правило предполагает, что на каждом из уровней используется код со скоростью, равной скорости среза соответствующего подканала. С практической точки зрения предпочтительным является использование правила равных вероятностей ошибки. Однако его использование требует знания весовых спектров используемых компонентных кодов, нахождение которых, как правило, сопряжено с чрезвычайно большими вычислительными сложностями.
1.5 Методы адаптивной передачи В тех случаях, когда состояние канала изменяется во времени достаточно медленно возникает возможность подстройки параметров передатчика, т.е. адаптивного кодирования [176]. В зависимости от технических требований к системе могут быть сформулированы различные оптимизационные критерии. В настоящей работе рассматривается задача минимизации мощности передатчика при условии поддержания заданной скорости передачи данных отдельных пользователей и заданной вероятности ошибки декодирования. При этом предполагается, что приемник и передатчик имеют возможность оценить состояние канала каким-либо образом. Рассмотрение методов оценивания канала выходит за рамки данной работы. В данном разделе представлено описание некоторых известных методов адаптивной передачи.
1.5.1 Однопользовательские одноканальные системы Одной из простейших форм адаптивной передачи является адаптивная модуляция. Этот метод был предложен в работе [163, 53] и достаточно долго не использовался ввиду отсутствия соответствующих аппаратных ресурсов. Исследования в этой области возобновились с появлением высокопроизводительных цифровых интегральных микросхем [140, 115, 4, 48, 124]. Первоначально адаптивная передача рассматривалась в контексте каналов без рассеяния (1.15). В этом случае основная идея метода может быть сформулирована как поддержание постоянного отношения сигнал/шум путем подстройки мощности передатчика, скорости передачи, методов модуляции и кодирования или комбинации этих параметров. Эти позволяет обеспечить заданную вероятность ошибки, передавая данные с большой скоростью тогда, когда канал находится в хорошем состоянии, и снижая скорость при его ухудшении. Пропускная способность канала опеределяется максимальной возможной мощностью передатчика E и допустимой спектральной полосой сигнала B. В каждый момент времени ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ i качество канала связи характеризуется отношением канал/шум i = |i2|, являющимся случайной величиной с некоторой плотностью распределения p(). Средняя пропускная способность может быть вычислена как [48] C= E():
max E()p()d = E W log2 (1 + E()) p()d, (1.62) где E() представляет собой правило адаптации мощности передатчика к текущему состоянию канала. Аналогично (1.11), можно показать, что оптимальное правило имеет вид S() = E 1, 0, 1/ < (1.63) для некоторой величины 0. Тогда пропускная способность равна C= 1/ W log2 ()p()d.
(1.64) Для сравнения различных методов передачи удобно также рассматривать спектральную эффективность, определяемую как C/B. Для практической реализации методов адаптивной модуляции, как правило, анализируется качество работы (например, вероятность ошибки на бит) различных методов, на основе чего составляется набор порогов переключения {j }, таких что j-й метод передаj j+1. При этом желательно наличие чи (со скоростью Rj ) используется, если аналитических функций (или, по крайней мере, аппроксимаций) Pj (), характеризующих вероятность ошибки для рассматриваемых схем. Т.к. количество различных методов передачи ограничено, оказывается необходимым осуществлять подстройку можности передатчика для поддержания требуемого отношения сигнал/шум в приемнике. В [26] было показано, что правило распределения скоростей слабо зависит от конкретного вида Pj (), в то время как зависимость соответствующего правила подстройки мощности выражена намного сильнее. Спектральная эффективность адаптивной системы может быть оценена как [48] R = B N j= Rj P {j j+1}.
(1.65) Ясно, что эта величина зависит от значений порогов переключения и распределения значений отношения канал/шум. Используя стандартные методы оптимизации, можно по лучить набор порогов переключения j, максимизирующих (1.65) или любой другой показатель [48, 125, 24, 100, 78]. Описанный метод может быть обобщен на случай использования методов кодированной модуляции. В этом случае задача адаптации сводится к поддержке фиксированного расстояния внутри смежных классов сигнальных множеств [49, 57]. В [106] было показано, что независимое использование кодирования и модуляции в адаптивных системах не дает существенного выигрыша. Методы адаптации, разработанные для однопользовательских систем, могут быть использованы и в многопользовательских системах, однако при этом необходим учет межпользовательской интерференции [77].
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ 1.5.2 Однопользовательские многочастотные системы Одной из основный причин использования многочастотной передачи является ее устойчивость к межсимвольной интерференции, достигаемая за счет преобразования исходного частотно-селективного канала к набору отдельных частотно-неселективных подканалов, ограниченных по полосе. Таким образом, возникает векторный Гауссовский канал, задача максимизации пропускной способности которого была рассмотрена в разделе 1.1.3. Однако при этом не учитывались практические ограничения, связанные с реализацией соответствующих методов модуляции, кодирования и т.п. В связи с этим было опубликовано большое число работ, посвященных построению практических адаптивных методов передачи для подобных многоканальных систем [61, 25, 40, 71, 75, 10, 1, 24, 32]. В данном разделе представлен краткий обзор некоторых из этих методов. Далее будет предполагаться, что для каждого из подканалов принятый сигнал может быть представлен как ri = i si + i, (1.66) где i, i = 1..N Ч комплексные коэффициенты передачи, i Ч отсчеты Гауссовского шума 2 с дисперсией i, N Ч число подканалов, Vi = M[|si |2 ] Ч коэффициент усиления на i-м подканале. Как правило, удобно рассматривать отношения канал/шум, определяемые как 2 i = |i |2 /i. В большинстве случаев рассматривается следующая задача: необходимо найти коэф фициенты усиления Vi = Ei и размеры сигнальных множест Mi -КАМ, такие что вероятность ошибки для всех подканалов одинакова. При этом требуется или максимизировать общую скорость передачи данных при фиксированной общей мощности передатчика, или минимизировать общую мощность передатчика при фиксированной скорости передачи. Алгоритмы, решающие одну из этих задач, могут быть адаптированы для решения другой. Задача минимизации мощности иногда формулируется также как задача максимизации запаса мощности, характеризующего максимальное допустимое увеличение мощности шума, не приводящее к катастрофическому снижению качества работы системы. В силу дискретности множества доступных методов модуляции данная задача представляет собой проблему целочисленного программирования. Использование наилучших подканалов Простейшим методом адаптации в однопользовательской системе является использование только нескольких наилучших подканалов [32]. Данный метод крайне неэффективно использует доступную спектральную полосу и требует увеличения размера используемого сигнального множества. Алгоритм Хугеса-Хартогса Алгоритм Хугеса-Хартогса [61] является оптимальным, но вычислительно сложным методом адаптации многочастотного передатчика. В ходе выполнения алгоритма вычисляется матрица P = ||pmi ||, где pmi Ч мощность, которую необходимо затратить на передачу m бит данных по подканалу i с заданной вероятностью ошибки. Инкрементальная матрица мощности определяется как P = ||pmi pm1 i ||. На каждой итерации алгоритма ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ общая скорость передачи увеличивается на единицу, путем увеличения скорости передачи по подканалу, требующему наименьшей дополнительной мощности: 1. Пусть M = 0 и Ptot = 0;
2. Найти наименьшее P1i, т.е. подканал, требующий наименьшей дополнительной мощности для увеличения скорости передачи на единицу;
3. Увеличнть скорость передачи по подканалу i на единицу;
4. Пусть M := M + 1;
Ptot := Ptot + P1,i ;
если Ptot Pmax, где Pmax максимальная допустимая мощность, завершить работу. 5. Сдвинуть вверх на одну позицию содержимое столбца i, т.е. Pmi = Pm+1 i. 6. Перейти к шагу 2. Было доказано, что этот алгоритм является оптимальным. Однако он требует выполнения большого числа операций сортировки и поиска. Алгоритм Чоу-Чиоффи-Бингама Алгоритм, предложенный в [25], основан на распределении скоростей передачи в соответствии с пропускной способностью подканалов. Скорость передачи по каждому подканалу может быть приближенно вычислена как Ri = log2 1 + Vi2 i, (1.67) где характеризует УрасстояниеФ до пропускной способности канала, зависящее от требуемой вероятности ошибки. В ходе работы алгоритма итеративно вычисляется запас мощности margin, такой что Ri = log2 1 + Vi2 i margin, Далее осуществляется подстройка скоростей для каждого из подканалов аналогично алгоритму Хугеса-Хартогса, так чтобы обеспечить заданную общую скорость передачи данных. Далее осуществляется подстройка мощности для каждого подканала с целью обеспечения заданной вероятности ошибки. Алгоритм Фишера-Хубера Основная идея алгоритма, описанного в [40], состоит в распределении скоростей передачи информации и мощности передатчика с целью минимизации вероятности ошибки. В ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ случае использования квадратурно-амплитудной модуляции вероятность ошибки на символ для i-го подканала может быть вычислена как (см. также (1.18)) Pi = Ki Q d2 /4 i 2 i, (1.68) где di Ч минимальное Евклидово расстояние между точками в сигнальном множестве, используемом для передачи по этому подканалу, а Ki Ч среднее число ближайших соседей произвольно выбранной точки из этого множества (эта величина может считаться постоянной для всех используемых сигнальных множеств). Предполагая, что вещественная и мнимая компоненты выбираются из множества {1Vi, 3Vi,...}, т.е. d2 = 4Vi2, и требуя, i чтобы вероятность ошибки на символ была одинаковой для всех подканалов, получим Vi2 |i |2 = S0 max 2 i (1.69) для всех i. При этом накладываются ограничения на общую скорость передачи и мощность передатчика Rtot = i Ri = const Etot = i 2 Vi2 (2Ri 1) = const. Производя условную максимизацию (1.69), можно получить набор величин Ri для каждого подканала. Однако очень часто эти величины оказываются нецелочисленными или даже отрицательными. В этом случае их необходимо соответствующим образом округлить, что приводит к субоптимальности получаемого решения. Алгоритма Кронгольда-Рамчандрана-Джонса Алгоритм, представленный в [75], аналогичен алгоритму Фишера-Хубера, но основан на ином критерии. Далее представлено его описание, несколько отличающееся от оригинального. Рассмотрим задачу минимизации общей мощности передатчика при фиксированной вероятности ошибки Ri i = Rtot (1.70) i Pi min Pi = P Ограничение на вероятность ошибки преобразуется в ограничение на расстояние между символами в сигнальном множестве, т.е. Vi2 i = S0, (1.71) ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ где vi Ч коэффициент усиления для подканала i, i Ч отношение канал/шум. Таким образом, необходимо найти размеры сигнальных множеств Mi, минимизирующих функцию S0 2(Mi 1), 3i i при наличии ограничения на общую скорость передачи log2 (Mi ) = Rtot.
i При этом временно не будем учитывать дискретность множества доступных схем передачи, т.е. множества значений Mi. Используя классические методы условной оптимизации, получим следующий лагранжиан: L(Mi ;
) = S0 2(Mi 1) + Rtot 3i log2 (Mi ), i (1.72) i дифференцирование которого приводит к системе уравнений S0 1 L =2 =0 Mi 3i Mi ln 2 L = Rtot log2 (Mi ) = 0 i (1.73) (1.74) Несложно заметить, что параметр однозначено определяет Mi. Таким образом, система сводится к одному уравнению относительно. Т.к. в практических системах Mi могут принимать только дискретные значения, необходимо введение понятия порогов, которое уже использовалось при рассмотрении одноканальных адаптивных систем. Для этих целей для каждого допустимого Mi вычисляются 2 ln 2 S0 Mi (1.75) i = 3 Эти величины используются для построения таблицы, используемой далее при выборе метода модуляции для каждого из подканалов. Уравнение (1.74) может быть решено методом бисекции [152] по, т.е. на начальном этапе выбираются некоторые значения l и h, а (l) (h) также соответствующие им параметры модуляции {Mi } и {Mi }. Этим значениям соот(h) (l) N ветствуют некоторые общие скорости передачи Rl = i=1 log2 Mi и Rh = N log2 Mi, i=1 причем Rl < Rtot < Rh. Новое значение вычисляется как Rtot Rl = l + (h l ) (1.76) Rh Rl Метод модуляции для каждого из подканалов определяется следующим образом. Вычисляется набор значений i = i, по которым определяются величины Mi путем поиска соответствующего интервала в таблице (1.75). Полученное значение скорости передачи сравнивается с требуемым Rtot и используется далее в качестве Rh или Rl на следующей итерации алгоритма. Коэффициент усиления vi вычисляется согласно (1.71). Алгоритм завершает работу, как только выполняется условие (1.74). Было показано, что данный алгоритм дает несколько лучшие результаты, чем алгоритмы Чоу-Чиоффи-Бингама и Фишера-Хубера.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Адаптивное кодирование в многочастотных системах Методы адаптивного кодирования, разработанные для одноканальных систем, могут быть использованы и в многочастотных системах, работающих в условиях частотноселективного канала. В [70] было предложено использование адаптивной турбокодированной модуляции в OFDM-системе. Т.к. использование отдельной схемы кодирования для каждого из подканалов достаточно затруднительно с точки зрения реализации, смежные подканалы могут быть сгруппированы в полосы, в пределах которых используется одна схема кодированной модуляции, выбираемая в расчете на наихудший подканал. При этом используется тот же набор порогов, что и в [125].
1.5.3 Многопользовательские многочастотные системы В данном разделе представлен обзор некоторых адаптивных методов передачи в многопользовательских многочастотных системах. При этом рассматривается передача данных от базовой станции к мобильному терминалу. В этом случае сигнал, принятый k-м пользователем по i-му подканалу, может быть представлен как rki = kisi + ki, k = 1..K, i = 1..N, где si Ч символ, переданный базовой станцией по i-му подканалу, ki Ч отсчеты Гауссовского шума с дисперсией 2. Адаптивное выделение подканалов и распределение скоростей в системах с частотным разделением В разделе 1.5.2 был описан ряд алгоритмов, позволяющих оптимизировать распределение скоростей передачи данных в многочастотной однопользовательской системе. В случае наличия в системе нескольких пользователей, возникает также задача обеспечения разделения канала передачи данных между этими пользователями. Одним из простейших способов разделения является частотное разделение. Однако при этом оказывается необходимым оптимизировать также распределение пользователей по подканалам [89]. Необходимо найти скорости передачи cki и коэффициенты усиления Vki, k = 1..K, i = 1..N для K пользователей и N подканалов, т.ч. Х Выполняются требования на скорость передачи данных каждым пользователем N Rk = i= cki (1.77) Х Каждый подканал используется не более чем одним пользователем |{k|Mki > 1}| 1 (1.78) ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Последнее требование означает, что задача принадлежит классу задач булевского программирования, которые, как известно, являются NP -полными. Это приводит к необходимости разработки субоптимальных алгоритмов оптимизации. Введем индикаторные переменные ki = 1, еслиcki > 0. 0, иначе С целью упрощения задачи допустим, что ki могут также принимать значения в (0, 1). Тогда задача может быть переформулирована как N cki,ki K min i=1 k= ki f (cki ) ki (1.79) с ограничениями N Rk = i=1 K ki cki ki k= (1.80) (1.81) (1.82) 1= 0 ki, ki где ki = |2| Ч отношение канал/шум для пользователя k и подканала i, f (cki) = (2cki 1) Ч функция, характеризующая отношение сигнал/шум, необходимое для получения требуемой вероятности ошибки9. Воспользуемся подстановкой rki = cki ki для того, чтобы свести исходную задачу к задаче выпуклого программирования. Тогда функция Лагранжа для преобразованной задачи может быть записана как N K L(ki, rki, k, i ) = i=1 k= ki f ki rki ki K N N K k k=1 i= rki Rk i i=1 k= ki (1.83) Известно, что подобная аппроксимация справедлива для большинства используемых схем модуляции/кодирования [42] ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Седловая точка этой функции, соответствующая решению описанной задачи условного экстремума, может быть найдена путем решения системы уравнений > 0, if rki = 0 1 rki L = f k = 0, if rki (0, c ki ) rki ki ki < 0, if rki = c ki 1 L = ki ki K f rki ki f rki ki rki ki i = 0, < 0, if ki (0, 1) if ki = Rk = k=1 N rki ki, i= 1= (1.84) где c Ч максимальная допустимая скорость передачи данных по подканалу. Однако, как будет показано ниже, численное решение этой системы уравнений представляет собой достаточно сложную задачу. В связи с этим в [89] был предложен субоптимальный алгоритм ее решения (алгоритм Вонга). Данный алгоритм начинает свою работу с некоторых малых величин k и увеличивает их до тех пор, пока не будут удовлетворены ограничения на скорость передачи данных. После вычисления значений ki {0;
1} для нахождения размеров сигнальных множеств и коэффициентов усиления для каждого из подканалов может быть использован любой из известных алгоритмов однопользовательской оптимизации. Было предложено большое число модификаций алгоритма Вонга [107, 147, 109, 72, 102, 44, 103, 34, 122, 28, 50, 121], направленных на снижение его сложности и обеспечение поддержки иных оптимизационных критериев. Одним из широко распространенных приемов является выделение из процесса оптимизации еще одного этапа, состоящего в оценивании числа подканалов, требуемых для каждого пользователя, после чего задача распределения пользователей по подканалам существенно упрощается. Алгоритм Вонга строит решения с ki {0, 1}. Хотя это и соответствует специфике системы с частотным разделением, это свидетельствует о субоптимальности алгоритма с точки зрения оптимизационной задачи (1.79) Ч (1.82). Кроме того, если точное решение системы уравнений имеет нецелочисленные значения ki для некоторого i, то это означает, что подканал должен быть разделен между пользователями, что принципиально невозможно в рамках частотного разделения10. Как было показано в разделе 1.3.4, данная проблема может быть решена с помощью кодового разделения. Далее будет представлено описание некоторых адаптивных алгоритмов, основанных на кодовом разделении.
Авторы [89] предлагают использовать в этом случае временное раздление, хотя и не дают метода вычисления точных значений ki. Отметим, что временное разделение является частным случаем кодового разделения с расширяющими последовательностями вида ak = (0,..., 0, 1, 0,..., 0).
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Адаптивный выбор каналов Простейший из методов адаптивной передачи с использованием кодового разделения был описан в [88]. Суть метода состоит в том, что данные каждого пользователя передаются только по одному наилучшему подканалу. При этом данные каждого из пользователей расширяются его индивидуальной расширяющей последовательностью, что позволяет восстановить символы, переданные каждым из пользователей, в случае совпадения наилучших подканалов для нескольких пользователей. Основным недостатком данного метода является неполное использование пропускной способности исходного широкополосного канала. Адаптивное формирование полос Рассмотрим многочастотную систему с гибридным кодово-частотным разделением. Пусть B = {1,..., N} Ч множество подканалов, а U = {1,..., K} Ч множество пользователей. Пусть S Ч длина расширяющей последовательности. Пусть пользователи распределены по группам Uq U, (Ui Uj =, i = j, Q Ui = U), причем пользователи из i=1 каждой группы Uq осуществляют передачу одновременно P символов, используя при этом только полосу Bq B, (Bi Bj =, i = j, Q Bi = B). При этом каждая из подполос i=1 является классической MC-CDMA системой. Пропускная способность k-го пользователя по подканалу n может быть вычислена как Ck,i = log2 1 + |k,i|2 2 ki, (1.85) где k,i Ч передаточный коэффициент для k-го пользователя по подканалу i. Тогда полная пропускная способность пользователя k по полосе Bq равна SP Ck,Bq = i= Ck,Bq (i), где Bq (i) Ч номер i-го подканала, входящего в полосу Bq. Пропускная способность группы пользователей Uq может быть вычислена как Kq SP CUq,Bq = k=1 i= CUq (k),Bq (i), где Uq (k) Ч номер k-го пользователя, входящего в группу Uq. Следовательно, полная пропускная способность системы равна Q CT OT = q= CUq,Bq.
(1.86) В [18] был предложен алгоритм, осуществляющий поиск разбиений {Bi } и {Ui }, максимизирующий CT OT. Данный алгоритм начинает свою работу с генерации некоторых ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ случайных разбиений {Bi } и {Ui }. Далее предпринимается попытка найти такую пару пользователей, входящих в две различные группы, обмен которыми приводит к увеличению текущей пропускной способности системы. Аналогично, предпринимается попытка найти такую пару подканалов, включенных в различные полосы, обмен которыми приводит к увеличению текущей пропускной способности системы. Эти действия выполняются итеративно до тех пор, пока пропускная способность не перестает увеличиваться. Для достижения лучших результатов алгоритм может быть выполнен несколько раз с различными начальными разбиениями. Можно заметить определенное сходство данного метода с генетическими алгоритмами оптимизации. Данный метод не использует адаптивной модуляции или адаптивного распределения мощности;
единственным объектом оптимизации является распределение подканалов между пользователями. Его применение позволяет существенно снизить мощность передатчика, требуемую для достижения некоторой фиксированной вероятности ошибки, однако какие-либо явные ее гарантии отсутствуют.
1.6 Выводы. Задачи диссертационной работы Как было показано выше, для эффективного осуществления передачи данных в как в одно-, так и в многопользовательских системах необходима адаптация используемой схемы передачи к меняющимся условиям канала. В данной работе рассматривается задача управления параметрами многочастотной системы связи с целью минимизации мощности передатчика, требуемой для достижения заданной скорости передачи и заданной вероятности ошибки. Идеальное решение этой задачи соответствует Управилу водонаполненияФ или его модификациям на случай многопользовательских систем. Практическая реализация этого правила приводит к необходимости использования дискретных скоростей передачи. Это приводит к тому, что параметры реально используемой схемы передачи данных отличаются от идеального решения оптимизационной задачи, соответствующего Управилу водонаполненияФ, что приводит к некоторому увеличению требуемой мощности передатчика. Таким образом, можно ожидать повышения эффективности адаптивной системы в случае использования набора схем кодирования/модуляции с малым шагом скоростей, что может быть реализовано на основе концепции многоуровневого кодирования. В случае многопользовательских систем вещания обеспечение фиксированной скорости передачи данных для каждого из пользователей может потребовать совместного использования подканалов для передачи данных нескольким абонентам, что требует разработки соответствующих оптимизационных алгоритмов. Использование корректирующих кодов в свою очередь, требует эффективной реализации соответствующих вычислительных алгоритмов. При этом особый интерес представляет снижение вычислительной сложности без снижения качества декодирования, т.е. без введения различного рода аппроксимаций. Данная задача может быть решена путем алгебраических преобразований исходных вычислительных примитивов. В том случае, когда вычисления производятся над конечными полями, как при декодировании кодов Рида-Соломона, применение некоторых их специальных свойств может привести к существенному снижению вычислительной сложности.
ОБРАБОТКА ИНФОРМАЦИИ НА ФИЗИЧЕСКОМ УРОВНЕ Задачами данной диссертационной работы являются:
1. Разработка адаптивных методов передачи, учитывающих использование помехоустойчивого кодирования и возможность разделения канала между различными пользователями. 2. Разработка эффективных вычислительных алгоритмов, используемых на различных этапах декодирования кодов Рида-Соломона. В частности, интерес представляют задачи вычисления синдромного многочлена, поиска корней многочлена локаторов ошибок и двумерная интерполяция.
Глава 2. Адаптивные методы передачи В данной главе описываются новые адаптивные методы передачи для многочастотных систем. Раздел 2.1 посвящен адаптивному многоуровневому кодированию. Метод адаптивного разделения канала описывается в разделе 2.2.
2. Адаптивное многоуровневое кодирование 2.1.1 Постановка задачи Большинство существующих адаптивных методов передачи требует наличия нескольких схем передачи, пригодных для использования в различных условиях. При этом увеличение числа доступных схем позволяет получить решение оптимизационной задачи, более близкое к идеальному правилу УводонаполненияФ. Известные методы адаптивной передачи в многочастотных системах в большинстве случаев основаны на адаптивной модуляции;
применение адаптивного кодирования, как правило, сводится к рассмотрению схем решеточно-кодированной модуляции. Это существенно ограничивает набор доступных скоростей передачи. Однако, как было показано в разделе 1.4.6, применение многоуровневого кодирования позволяет производить выбор формата сигнального множества и параметров помехоустойчивого кодирования независимо, что существенно повышает гибкость системы. В данном разделе будет описан метод адаптивного выбора многоуровневых кодов в многочастотной однопользовательской системе, позволяющий увеличить количество схем передачи, доступных для использования в адаптивной системе, и за счет этого приблизить решение задачи адаптации к идеальному. Более конкретно, будет рассмотрена задача выбора многоуровных кодов и отображения их кодовых слов на подканалы многочастотной системы, минимизирующих мощность передатчика, требуемую для обеспечения заданной скорости передачи данных и вероятности ошибки. Методы, описываемые в данном разделе, могут быть использованы и в многопользовательских системах.
2.1.2 Семейство многоуровневых кодов Рассмотрим построение семейства многоуровневых кодов для M-уровневой амплитудной модуляции, т.е. для случая сигнального множества, состоящего из точек {(M + 1 + 2j)d0 /2|0 j M 1}. Воспользуемся двоичным разбиением сигнального множества, представленным на рисунке 2.1. Видно, что символы кодовых слов, порождаемых кодером i, выбирают одно из подмножеств сигнальных точек, причем расстояние между точками, входящими в это подмножество, равно 2i d0, где d0 Ч расстояние между точками в исходном сигнальном множестве. Необходимо отметить, что предположения об использовании M-ичной амплитудной модуляции и двоичном разбиении сигнального множества сделаны ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 1 0 1 0 1 0 1 0 Кодер 0 Кодер 1 Кодер 1 1 0 0 1 1 0 1 1 1 1 0 0 0 Рис. 2.1 Двоичное разбиение сигнального множества здесь исключительно в целях упрощения изложения;
методы, описываемые ниже, могут быть легко перенесены на случай иных сигнальных множеств. Согласно правилу пропускной способности (см. раздел 1.4.6), для кодирования данных на каждом из уровней должен быть использован код со скоростью, равной пропускной способности данного уровня. Однако это утверждение справедливо только для кодов бесконечной длины. В практической системе более предпочтительным является правило равных вероятностей ошибки. Однако его практическое применение вызывает определенные сложности, т.к. его для его использования необходимо знание весовых спектров компонентных кодов. Допустим, что для используемого семейства компонентных кодов теоретически или экспериментально построена функция R(C), характеризующая скорость кода конечной длины, который обеспечивает заданную вероятность ошибки при передаче по каналу с пропускной способностью C при условии использования надлежащей процедуры приема и декодирования. Примером такой функции является выражение (4.6). Тогда предполагая, что показатели качества декодирования используемых кодов не претерпевают существенных изменений при переходе от аддитивного Гауссовского канала к эквивалентным каналам в многоуровневом коде1, можно воспользоваться функцией R(C) для вычисления скоростей компонентных кодов. При этом пропускные способности подканалов могут быть вычислены с помощью выражений (1.60) и (1.61). Для случая двоичного разбиения и аддитивного Гауссовского канала выражение (1.61) для пропускной способности сигнального Необходимо отметить, что эквивалентные каналы в многоуровневом коде существенно отличаются по своим свойствам от гауссовского канала [17]. Однако в большинстве случаев оказывается, что это не оказывает существенного влияния на характеристики системы.
ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ подмножества принимает вид 1 K(i, d0 ) = M/2i M 2i e (y(M +1+2i+1 m)d0 /2)2 2 m= 2 Таким образом, процедура построения многоуровневого кода, использующего M-ичную амплитудную модуляцию и способного функционировать с заданной вероятностью ошибки на заданном отношении сигнал/шум, состоит из следующих шагов: 1. Построить семейство компонентных кодов {Cj, j = 1..J} с достаточно большим диапазоном скоростей. 2. Для каждого из кодов Cj построить теоретически или путем имитационного моделирования кривую pj () вероятности ошибки в зависимости от отношения сигнал/шум при передаче по аддитивному Гауссовскому каналу. В случае имитационного моделирования может быть использована среднеквадратическая аппроксимация функцией подходящего вида, например (4.5). 3. Для каждого из имеющихся компонентных кодов Cj найти отношение сигнал/шум j, обеспечивающее заданную вероятность ошибки, т.е. решить уравнение pj () = Ptarget. Это дает отображение rj j или rj C(j ), которое также может быть аппроксимировано некоторой функцией r(C), например (4.6). Здесь C() Ч пропускная способность аддитивного Гауссовского канала при отношении сигнал/шум, 4. Вычислить пропускные способности Ci, i = 0..l 1 эквивалентных подканалов Mичной амплитудной модуляции с помощью выражений (1.60) и (2.1). 5. Для каждого из подканалов i найти скорость кода r(Ci), пригодного для использования в качестве компонентного на данном подканале, округляя ее вниз при необходимости. Описанная процедура позволяет выбрать для каждого набор компонентных кодов, максимизирующих скорость передачи при заданной вероятности ошибки. Ясно, что если имеется возможность использования сигнальных множеств с различным числом уровней M, то для каждого может быть выбрано сигнальное множество, обеспечивающее максимальную скорость передачи. Заметим, что данный метод может рассматриваться как модификация известного правила равных вероятностей ошибки. Действительно, для каждого компонентного кода веростность ошибки при передаче по аддитивному Гауссовскому каналу однозначно определяется отношением сигнал/шум. С другой стороны, отношение сигнал/шум однозначно характеризует пропускную способность канала, т.е. пропускная способность канала однозначно определяет вероятность ошибки декодирования. Предлагаемый метод основывается на предположении о том, что при переходе от аддитивному Гауссовскому каналу к i+1 2 M2i e (y(M +1+2 2 m)d0 /2) 2 log2 i dy M 2 1 (y(M +1+2i+1 k)d0 /2)2 2 2 e k= ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ эквивалентным подканалам в многоуровневом коде эта зависимость не претерпевает существенных изменений. Основным достоинством предлагаемого метода является простота процедуры построения многоуровневого кода, которая не требует достаточно сложного анализа вероятности ошибки декодирования. Для многих кодов такой анализ практически неосуществим. Как будет показано на рисунке 4.4, кривая спектральной эффективности семейства многоуровневых кодов, построенного описанным образом, проходит достаточно близко к кривой пропускной способности аддитивного Гауссовского канала CAW GN = 1 log2 (1 + ), 2 (2.1) где Ч отношение сигнал/шум, и может быть охарактеризована некоторым УзазоромФ [42], т.е. 1 R log2 (1 + ). (2.2) 2 Описанный метод позволяет построить достаточно большой набор многоуровневых кодов малым шагом скоростей, используя сравнительно небольшое семейство компонентных кодов. Более того, могут быть получены сигнально-кодовые конструкции с нецелочисленными значениями скорости, что существенно упрощает оптимизацию многочастотных систем. Описанный метод может быть обобщен на случай квадратурно-амплитудной модуляции путем рассмотрения ее символов как композиции двух символов амплитудной модуляции. В этом случае R log2 (1 + ). (2.3) В работе [8] независимо была предложена аналогичная система, использующая единственный компонентный (низкоплотностной) код на нижних уровнях и код Рида-Соломона на верхних уровнях. Однако при этом требуются достаточно длинные (порядка 105 ) компонентные коды. Как будет показано ниже, подход, предложенный в данной работе, позволяет использовать существенно менее длинные коды, что важно с точки зрения реализации.
Pages: | 1 | 2 | 3 | Книги, научные публикации