Книги, научные публикации Pages:     | 1 | 2 | 3 |

Государственное образовательное учреждение высшего профессионального образования УСанкт-Петербургский государственный политехнический университетФ На правах рукописи Трифонов Петр Владимирович Адаптивное ...

-- [ Страница 2 ] --

2.1.3 Адаптивное кодирование в многочастотных системах Рассмотрим многочастотную OFDM систему с N подканалами, функционирующую в условиях частотно-селективного канала. Тогда принятый сигнал может быть представлен как ri = i si + i, i = 1..N, (2.4) где si Ч сигнал, переданный по i-му подканалу, i Ч комплексный передаточный коэффи2 циент, i Ч отсчеты аддитивного Гауссовского шума с дисперсией i. Ясно, что в этом случае характеристики подканалов различны и определяются их отношениями сигнал/шум 2 Vi2 i, где Vi2 = M[|si |2 ] Ч мощность сигнала на i-м подканале, i = |i2| Ч отношение i канал/шум. В связи с этим возникает необходимость использования различных методов передачи на каждом из подканалов. В частности, данные, передаваемые по каждому ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Многоуровневые кодеры Многоуровневые кодеры КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор подканал КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор КАМ модулятор подканал подканал подканал 2 подканал подканал 3 подканал подканал подканал подканал подканал 6 подканал подканал 6 подканал подканал подканал t (a) Независимое кодирование подканалов (b) Групповое кодирование подканалов Рис. 2.2 Отображение кодовых слов на подканалы при адаптивной передаче ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ из подканалов, могут кодироваться индивидуально подобранным многоуровневым кодом. Рисунок 2.2(a) иллюстрирует этот подход. Однако этот подход является достаточно сложным в реализации, т.к. требует наличия больших буферов в приемнике и передатчике и приводит к большой задержке передаваемых данных. Ввиду конечности множества многоуровневых кодов, поддерживаемых адаптивной системой, при практической реализации описанного сценария оказывается, что достаточно большие наборы подканалов кодируются одним и тем же многоуровневым кодом. Это может быть использовано для того, чтобы снизить сложность реализации. Действительно, адаптация может выполняться не для отдельных подканалов, а для их групп, причем группы не обязательно должны состоять из смежных подканалов. Этот подход представлен на рис. 2.2(b). Т.к. качество работы большинства существующих методов кодирования и модуляции может быть охарактеризовано их УрасстояниемФ до пропускной способности канала, естественно перенести этот принцип и на случай групп подканалов. Практически достижимая скорость передачи для группы из L подканалов с отношениями сигнал/шум i = Vi2 i, i = 1..L равна L L b= i= log2 (1 + i /) = log i= (1 + i/) = L log2 (1 + geom /), (2.5) Отсюда можно получить приближенное выражение [7] 1/L L L 1/N Таким образом, введено среднее отношение сигнал/шум для группы подканалов. Аналогичным образом может быть введено и среднее отношение канал/шум. При формировании групп подканалов желательно, чтобы отношения канал/шум в сформированном таким образом векторном канале обладали большим динамическим диапазоном, что позволяет значительно улучшить результаты оптимизации. Кроме того, известно, что среднее геометрическое (2.6) набора величин достигает своего максимума в том случае, когда все величины в наборе одинаковы. В связи с этим формирование групп целесообразно выполнять следующим образом: 1. Отсортировать все подканалы в соответствии с их отношениями канал/шум. 2. Объединить смежные подканалы в полученном списке в группы Bi, i = 1..Q размера L, причем N = LQ. Отношение канал/шум для каждой из групп Bi может быть вычислено как среднее геометрическое соответствующих отношений для отдельных подканалов, входящих в группу. Рассмотрим задачу минимизации мощности при фиксированной скорости передачи данных R. Предполагая, что используется многоуровневое кодирование на основе квадратурно-амплитудной модуляции, эту задачу можно сформулировать как Q geom = (1 + i /) i= i i= (2.6) min Vi i= Vi (2.7) ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ с ограничением Q log2 (1 + i= Vi2 i ) = R, (2.8) где Ч зазор между спектральной эффективностью используемого семейства методов передачи и пропускной спосбоностью канала, Q Ч число групп подканалов, i Ч среднее отношение канал/шум для группы подканалов Bi и R Ч требуемая скорость передачи (бит на OFDM-символ). Предполагая непрерывность множества допустимых скоростей передачи и используя классические методы условной оптимизации, получим лагранжиан Q Q L(Vi, ) = Vi i= + i= log2 (1 + Vi2 i )R (2.9) Седловая точка функции Лагранжа, соответствующая решению оптимизационной задачи (2.7)-(2.8), может быть найдена как решение системы нелинейных уравнений 2Vii /( ln 2) 1+ Vi2 i Q + 2Vi = 0, i = 1..Q log2 (1 + Vi2 i )=R (2.10) (2.11) i= Эта система может быть преобразована к виду Vi2 = max 0, Q ln 2 i log2 (1 +, i = 1..Q Vi2 i )=R (2.12) (2.13) i= Несложно заметить, что множитель Лагранжа однозначно определяет все остальные переменные. Таким образом, уравнение может быть решено методом бисекции [152] по переменной. Далее могут быть вычислены скорости кодирования для каждой группы V 2 подканалов как Ri = log2 (1 + i i ), i = 1..Q. Для передачи данных необходимо использовать многоуровневый код с максимальной скоростью, не превышающей Ri. Кроме того, в случае группового кодирования дополнительно может быть осуществлена подстройка коэффициентов усиления отдельных подканалов, входящих в группу, с целью обеспечения одинакового отношения сигнал/шум Vi2 i в пределах всей группы. Замечание 1. Данный шаг направлен на то, чтобы максимально приблизить условия функционирования системы к аддитивному Гауссовскому каналу, для которого была произведена оптимизация компонентных кодов. Альтернативный подход [91] состоит в использовании кодов, построенных с учетом различных условий передачи отдельных частей кодового слова. Однако в данном случае применение таких кодов представляется нецелесообразным ввиду необходимости построения чрезмерно большого их числа.

ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Т.к. множество доступных методов передачи (т.е. многоуровневых кодов) дискретно, применение метода Лагранжа в общем случае может привести к субоптимальному решению исходной оптимизационной задачи. Однако ясно, что погрешность метода будет уменьшаться с уменьшением шага скоростей имеющегося множества кодов. Несложно заметить, что уравнения (2.12) Ч (2.13) соответствуют классическому правилу водонаполнения, используемому во многих известных адаптивных алгоритмах. Новизна предлагаемого метода состоит в использовании большого семейства многоуровневых кодов, обеспечивающего более точную подстройку параметров каждого подканала. Как будет показано в п. 4.2.2, это позволяет снизить мощность, требуемую для достижения заданной скорости передачи данных.

2.1.4 Анализ эффективности Рассмотрим задачу вычисления функции E(R) = Q Vi2, характеризующей мощность i=1 передатчика, необходимую для поддержания заданной скорости R, или обратной к ней функции R(E). Как видно из системы уравнений (2.12)-(2.13), значения Vi зависят не только от требуемой скорости R, но и от отношений канал/шум i, являющихся случайными величинами. Для упрощения задачи возникает необходимость применения приближенных и асимптотических методов. Заметим, что пропускная способность канала не зависит от того, в каком порядке заданы величины i. Отсортируем их по возрастанию. В этом случае рассмотрение исходного набора случайных величин i, i = 1..N заменятся рассмотрением набора их порядковых статистик i:N. Можно показать [164], что если функция плотности распределения p(x) случайной величины дифференцируема в окрестности P 1 (w), 0 < w < 1, где P (x) Ч функция распределения, и p(P 1 (w)) > 0, то распределение wn-й порядковой статистики Xwn:n для выборки из n независимых случайных величины сходится при достаточно больших n w(1w) к нормальному с математическим ожиданием P 1 (w) и дисперсией np2 (P 1 (w)). Предполагая, что отношения канал/шум i независимы и имеют экспоненциальную плотность распределения p() = exp(), получим, что асимптотическое распределение их порядковых статистик нормально с математическим ожиданием N (2.14) M[i:N ] ln N i и дисперсией (i/N)(1 i/N) i D[i:N ] = (2.15) N N(N i) N exp(2 ln N i ) Таким образом, при достаточно больших N и i < N дисперсия i:N стремится к нулю, что дает возможность пренебречь их случайностью и рассматривать их как детерминированные величины. Вместе с тем, отметим, что эти выражения справедливы только при i < N при достаточно больших. Для i = N (т.е. наилучшего подканала) можно 2 показать [164], что M[N :N ] ln(N) 0.5772 и D[N :N ] 6 1.64. Известно также, что N :N ln(N) распределено по закону Гумбеля, т.е. P {N :N ln(N) x} exp( exp(x)) ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Кроме того, заметим, что выражение (2.14) дает M[N 1:N ] = ln N, что несколько больше чем точное значение M[N :N ], и M[N :N ] =, что не имеет смысла. Для компенсации этих эффектов можно исключить N :N из дальнейшего рассмотрения. Для больших N это не приведет к существенным погрешностям. Заметим, что описанные неточности вызваны применением асимптотической формулы для центральных квантилей порядковых статистик при w = 1. Тогда система уравнений (2.12)Ц(2.13) преобразуется к виду N E= i=1 N max 0, ln 2 ln NN i (2.16) (2.17) R= i= log2 (max 1, N ln ln 2 N i Эти уравнения не зависят от случайных величин и позволяют построить параметрическую кривую зависимости скорости передачи данных адаптивной системы R от мощности передатчика E. Они могут быть также использованы для анализа пропускной способности канала ( = 1). Обобщения для других стохастических моделей каналов могут быть получены путем модификации выражения (2.14). Согласно имеющейся у автора информации, до настоящего времени не были опубликованы явные методы оценивания средней пропускной способности канала и спектральной эффективности адаптивных методов, основанных на принципе водонаполнения2. В некоторых работах [15, 45], посвященных аналогичной тематике, игнорируется тот факт, что некоторые (особо плохие) подканалы могут быть не задействованы при передаче, что не дает возможность построить адекватные оценки в области малых отношений сигнал/шум. Как будет показано ниже, такие оценки представляют большой инетерес при рассмотрении многопользовательских систем. Необходимо отметить, что описанный метод предполагает независимость передаточных коэффициентов канала. В большинстве современных систем связи это условие не выполняется. Однако, как будет показано в разделе 4.2.2, влияние этого фактора на характеристики системы весьма незначительно. С другой стороны, аппарат порядковых статистик может быть применен и в случае зависимых случайных величин. Однако в этом случае требуется знание многомерных функций распределения отношений канал/шум [82].

2. Адаптивное разделение каналов в многопользовательских многочастотных системах Рассмотрим задачу вычисления коэффициентов разделения подканалов ki в многопользовательской системе вещания, описанную в контексте OFDMA-системы в разделе 1.5.3.

В работе [120] был проанализирован адаптивный алгоритм Фишера-Хубера (см. п. 1.5.2), который не в полной мере основан на этом принципе.

ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 2.2.1 Постановка задачи Известно, что в многочастотной системе вещания принятый сигнал для каждого из K пользователей и N подканалов может быть представлен как rki = ki si + ki, i = 0..N 1, k = 0..K (j) (j) (j) (j) (j) (2.18) где ki Ч передаточный коэффициент i-го подканала, наблюдаемый k-м пользователем в (j) момент времени j, si Ч сигнал, передаваемый по i-му подканалу в j-й момент времени, (j) ki Ч отсчеты аддитивного Гауссовского шума. Предположим, что пользователи могут с помощью кодового разделения совместно использовать подканалы многочастотной системы или их блоки(подполосы), состоящие из смежных подканалов, т.е.

St Sf (jS +m) sqSft+s = l= sql al,sSt +m, s = 0..Sf 1, m = 0..St 1, q = 0..N/Sf (j) (2.19) где St, Sf Ч коэффициенты расширения пользовательского сигнала по времени и по часто(j) те, sql Ч модулированный сигнал, предназначенный l-му пользователю, назначенному на q-й подканал (подполосу), al = (al,0,..., al,S1 ) Ч l-я расширяющая последовательность, S = St Sf Ч общий коэффициент расширения. Заметим, что каждый из K пользователей системы может быть назначен на произвольный набор подканалов (подполос) и на каждой из них использовать произвольный набор (размером от нуля до S) расширяющих последовательностей. При этом различные пользователи, назначенные на данный подканал, должны использовать различные расширяющие последовательности. Это позволяет рассматривать каждый их N/Sf подканалов (подполос) как набор из S логических подканалов с идентичными свойствами. Здесь предполагается, что подполосы состоят из смежных подканалов. Ниже будет показано, что наличие этого ограничения не приводит к каким-либо серьезным потерям в характеристиках системы. Вместе с тем, это ограничение может быть устранено путем (j) переупорядочения коэффициентов ki. Заметим, что временное разделение является частным случаем кодового разделения с расширяющими последовательностями вида al = (0,..., 0, 1, 0..., 0). В случае Sf = (j) 1 и стационарного канала (т.е. ki = ki ) тип используемых последовательностей не имеет значения. Однако при наличии временных изменений состояния канала или Sf > 1 применение УистинноФ кодового разделения может дать эффект разнесения [172]. Для простоты рассмотрим вначале систему с Sf = 1. Пусть ki [0, 1] обозначает долю i-го подканала, занимаемую k-м пользователем, i = 0..N 1, k = 0..K 1. Эта величина соответствует доле расширяющих последовательностей, используемых k-м пользователем по i-му подканалу. Пусть cki обозначает скорость передачи данных k-м пользователем по i-му подканалу, а Vki Ч соответствующий коэффициент усиления. Необходимо отметить, что усилению подвергаются формируемые пользователями символы до того, как они накладываются, образуя собственно передаваемый сигнал si (см. рис. 2.3). Предположим, что полностью отсутствует межпользовательская интерференция, что может быть достигнуто при идеальной синхронизации базовой станции и мобильных п ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Модуляция Оптимизируемые параметры Усиление Расширение Пользователь 0 Пользователь ОДПФ Пользователь K- Рис. 2.3 Архитектура оптимизируемой системы устройств. В случае кодового разделения для этого дополнительно требуется неизменность канала во времени и ортогональность используемых расширяющих последовательностей (таковыми, например, являются последовательности Уолша-Адамара). Кроме того, предположим, что для k-го пользователя необходимо обеспечить скорость передачи данных N Rk = i= ki cki, k = 0..K 1, i = 0..N 1, где cki = log2 Mki Ччисло бит в одном символе, передаваемом k-м пользователем по подканалу i. Первоначально предположим, что используется кодовое разделение подканалов на основе ортогональных расширяющих последовательностей (например, Уолша-Адамара) длины St = S. Это означает, что множество допустимых коэффициентов разделения подканалов имеет вид ki {0, 1/S,..., (S 1)/S, 1}. Вместе с тем, в нижеприведенных преобразованиях предполагается, что ki R. Ясно, что путем увеличения S точность оптимизации может быть повышена. (0) Пусть3 f (ki, cki) = f (cki) указывает отношение сигнал/шум, которое необходимо обеспечить для достижения требуемой вероятности ошибки при скорости передачи данных cki. Предположим, что эта функция является выпуклой, монотонно возрастающей и удовлетворяющей условию f (0) = 0. Для большинства практически используемых методов 3 (j) ki Для простоты здесь предполагается, что канал стационарен, т.е. для отношений канал/шум выполняется | (j) ki = 2 = ki. В этом случае определение функции f (c) идентично использованному в [89]. Но при наличии стохастических изменений канала эту функцию целесообразно определить как отношение сигнал/шум в начальный момент времени, необходимое для передачи данных со скоростью c и заданной вероятностью ошибки.

| ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ модуляции и кодирования эта функция может быть приближенно представлена как f (c) = (2c 1), (2.20) ki где зависит от требуемой вероятности ошибки. Пусть ki = |2| Ч отношение канал/шум для пользователя k по подканалу i. Ясно, что тогда коэффициент усиления должен быть равен (2.21) Vki = f (cki)/ki.

Таким образом, оптимизационная задача может быть сформулирована как N 1 K1 cki,ki min i=0 k= ki f (cki ) ki (2.22) с ограничениями N Rk = i=0 K ki cki ki k= (2.23) (2.24) (2.25) 1= 0 ki.

Производя замену переменных pki = cki ki, получим задачу выпуклого программирования с функцией Лагранжа N 1 K L(ki, pki, k, i, ki) = i=0 k=0 N 1 K ki f ki pki ki K N k k=0 N 1 K1 i= pki Rk i i=0 k= ki kiki, i=0 k= где k, i, ki Ч множители Лагранжа. Дифференцируя это выражение и учитывая условия Куна-Таккера [159], получим L = pki L = ki f (pki /ki ) ki 1 ki k =0 i ki = 0 = Rk =1 =0 f (pki/ki ) pki f (pki /ki) ki N 1 i=0 pki K1 k=0 ki kiki ki ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Эта система может быть преобразована к следующему виду: 0= Rk = 1= i (k) i i (k) N 1 i= i ki (2.26) (2.27) (2.28) (2.29) ki f 1 (k ki ) = K1 k=0 ki 1 ( )) f 1 ( ) f (f k ki k ki k ki. ki Несложно заметить, что система состоит из NK + K уравнений и N неравенств и является разреженной. В настоящее время известны различные методы, предназначенные для численного решения больших разреженных систем нелинейных уравнений [12, 58, 108]. Несмотря на это оказывается, что решение этой системы весьма затруднено ввиду наличия большого числа решений, т.е. наборов значений ki, удовлетворяющих описанным ограничениям. Следствием этого является наличие большого числа точек в пространстве параметров задачи, в которых матрица Якоби системы уравнений (2.26)Ц(2.29) вырождена. Это приводит к существенному замедлению сходимости многих численных методов. В связи с этим возникает необходимость построения оптимизационного алгоритма, ориентированного на данную задачу.

2.2.2 Оптимизационный алгоритм Для построения специализированного оптимизационного алгоритма заметим, что из (2.27) следует, что для заданного набора {ki } k может быть однозначно найдено из Rk. С другой стороны, как было показано в [89], из (2.26) следует, что i должно быть (k) (k) равно mink i и только пользователи с i = i могут использовать подканал i. Поэтому (k) величина i может рассматриваться как мера непригодности пользователя k для работы по подканалу i. Используя этот факт, можно построить следующий алгоритм: 1. Сформировать начальный набор {ki }. 2. Вычислить k из (2.27) и подставить это значение в (2.29), получив i. 3. Найти наихудший подканал и наихудшего пользователя, назначенного на этот (k) подканал (iw, kw ) = arg max (i i ), а также наилучшего пользователя kb = i,k:ki >0 (k) arg min iw. k (k) 4. Уменьшить долю kw,iw подканала iw, занимаемую пользователем kw, на 1/S и увеличить долю kb,iw, занимаемую пользователем kb, на эту же величину. 5. Повторять шаги 2 Ч 4 заданное число раз. Вычисления могут быть прекращены досрочно, если в течение нескольких шагов не происходит уменьшение величины (k) = max (i i ) i,k:ki > ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 6. Воспользоваться каким-либо алгоритмом оптимизации однопользовательских многочастотных систем для нахождения распределения мощности передаваемого сигнала и скоростей передачи по подканалам, выделенным каждому из пользователей. Замечание 2. Заметим, что на каждой итерации алгоритма достаточно обновлять значения k лишь для k = kw и k = kb. Замечание 3. Шаг 6 может быть полезен исключительно для обеспечения более точного учета дискретных ограничений на скорость кодирования/модуляции для отдельных подканалов. Замечание 4. Описанный алгоритм минимизирует величину, связанную с максимальной невязкой уравнения (2.26). При этом автоматически учитывается дискретность множества допустимых коэффициентов разделения подканалов. Исходное распределение пользователей по подканалам может быть получено, например, следующим образом. Для каждого пользователя могут быть найдены наилучшие подканалы и для них установлено ki = > 0. Те подканалы, которые не вошли в число наилучших ни для одного пользователя, могут быть назначены, например, пользователям с наилучшими отношениями канал/шум на них. При этом должно выполняться условие нормировки (2.28). Данный алгоритм не опирается на Унебольшие константыФ, используемые в алгоритме Вонга [89] для инициализации и обновления множителей Лагранжа k ;

оказывается, что их выбор существенно влияет на само решение и сложность алгоритма. Кроме того, предложенный алгоритм реализует иную структурку итеративного процесса: осуществляется подстройка коэффициентов разделения подканалов до достижения ими условий оптимальности, в то время как в алгоритме Вонга осуществляется подстройка констант УводонаполненияФ k. Иногда описанный алгоритм сталкивается с той же проблемой, что и стандартные итеративные алгоритмы оптимизации, а именно возникновением колебаний на шаге 4. В этом случае несколько пользователей циклически обмениваются подканалами, что препятствует достижению оптимального решения. Причиной этого является то, что передача доли подканала от одного пользователя к другому может незначительно улучшить условия работы первого пользователя и существенно ухудшить показатели второго пользователя, вследствие чего на следующей итерации алгоритма будет произведен обратный обмен. Эта проблема может быть преодолена, с помощью стандартного приема УсглаживанияФ. В данном случае он может быть реализован путем принудительного запрета на выбор на шаге 3 в качестве УнаихудшихФ тех пользователей, которые были выбраны на предыдущих W итерациях в качестве УнаилучшихФ.

2.2.3 Анализ эффективности Точный теоретический анализ адаптивной многопользовательской системы оказывается достаточно сложной задачей, что обусловлено усложнением системы уравнений (2.26) - (2.29) по сравнению с аналогичной системой в однопользовательском случае. Ввиду того, что решение оптимизационной задачи зависит не только от передаточных коэффициентов, но и от их соотношения для различных пользователей, здесь уже нельзя напрямую ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Таблица 2.1 Граница однопользовательского Число пользователей 4 8 16 Скорость каждого из пользователей R, 16 16 16 бит/OFDM символ Мощность в однопользовательской си- -17 -17 -17 стеме P0, дБ Оценка минимальной требуемой мощно- -11 -8 -5 сти, дБ УводонаполненияФ 32 64 4 8 16 16 256 128 -17 -2 -17 1 -1 5 -5 16 64 -10 32 32 -13 воспользоваться аппаратом порядковых статистик, использованным при анализе однопользовательской системы. В связи с этим возникает необходимость введения дополнительных упрощающих предположений. Предположим, что передача данных каждого из пользователей производится в соответствии с правилом традиционного однопользовательского УводонаполненияФ и скорость передачи данных каждого из пользователей достаточно мала, так что каждым из них используется небольшое число наилучших подканалов. Кроме того, допустим, что передаточные коэффициенты подканалов для различных пользователей независимы. Тогда множества их наилучших подканалов также будут являться независимыми. Следовательно, вероятность совпадения подканалов, используемых различными пользователями, достаточно мала. Пусть P (R) Ч функция, характеризующая мощность передатчика однопользовательской системы, необходимую для передачи данных со скоростью R (см. (2.16),(2.17)). Тогда общая мощность передатчика системы вещания может быть оценена как K P (R1,..., RK ) P (Rk ) k= (2.30) Эта граница не учитывает эффектов, связанных с возможным совпадением множеств наилучших подканалов различных пользователей. Числовые значения этой границы для случая системы с 512 подканалами и 2, 66 представлены в таблице 2.1. Функция достижимой спектральной эффективности в идеальной адаптивной КАМ-системе, функционирующей в условиях независимых затуханий, представлена на рисунке 2.4. Замечание 5. Использованная методика оценки опирается на возможность точного вычисления спектральной эффективности адаптивной системы в области малых отношений сигнал/шум (см. раздел 2.1.4). Согласно имеющейся у автора информации, все опубликованные до настоящего времени методы оценивания спектральной эффективности адаптивных систем не позволяют получить удовлетворительных результатов в этом случае, т.к. не учитывают возможность использования только нескольких наилучших подканалов.

2.2.4 Частотно-временное расширение Вышеописанный метод может быть использован и в случае частотно-временного расширения, т.е. если символы каждого CDMA-слова занимают Sf подканалов, образующих ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 0. 0. 0. 0. - относительная мощность передатчика, дБ - - - - Рис. 2.4: Спектральная эффективность идеальной адаптивной однопользовательской КАМ-системы в канале с независимыми замираниями подполосу, и St = S/Sf OFDM-символов. Для каждой из подполос может быть вычислено среднее геометрическое (см. п. 2.1.3) отношение канал/шум ki, k = 0..K 1, i = 0..N/Sf 1, после чего вышеописанный оптимизационный алгоритм может быть использован без каких-либо изменений. При этом возникает еще один параметр оптимизации, а именно разбиение множества подканалов на подполосы. Для минимизации межпользовательской интерференции, вызываемой нарушением ортогональности расширяющих последовательностей из-за частотноселективного затухания, желательно формировать подполосы из подканалов с близкими отношениями канал/шум ki для пользователей, использующих эти подполосы. Кроме того, векторный канал, образованный этими подполосами, должен быть как можно более частотно-селективным с целью максимизации его пропускной способности. В принципе, можно построить оптимизационный алгоритм, реализующий эти критерии. С другой стороны, т.к. передаточные коэффициенты смежных в подканалах в большинстве практических систем являются сильно коррелированными, разумно предположить, что группировка смежных подканалов в подполосы может автоматически удовлетворить вышеописанным требованиям. Оказывается, что этот простой подход обеспечивает достаточно хорошие показатели качества работы системы.

2.2.5 Сжатие служебной информации Ясно, что после выполнения описанной оптимизации ее результаты должны быть переданы приемникам. Для осуществления демодуляции передаваемого сигнала приемник должен обладать следующей информацией: 1. Распределение пользователей по подканалам и расширяющим последовательностям ki. 2. Скорость модуляции и кодирования cki для каждого пользователя и каждого подканала.

спектральная эффективность, бит/с/Гц 0. ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 3. Коэффициенты усиления Vki. 4. Передаточные коэффициенты канала ki.

Передаточные коэффициенты ki могут быть оценены приемником с использованием любого стандартного метода оценивания канала [86]. Заметим, что приемник может восстановить коэффициенты Vki, используя оцененные значения ki с помощью функции f (x). Однако ввиду возможного наличия погрешности оценивания ki это может привести к некоторому увеличению вероятности ошибки. Для каждого из подканалов i = 0..N/Sf 1 на основе величин ki может быть сформирован список пользователей, использующих его. Каждый из таких списков имеет размер ровно S. Одна запись в списке может представлять собой номер пользователя и номер используемого сигнального множества. Таким образом, общий объем служебной информации равен N S(log(K) + log(Mmax )), (2.31) Iaux = Sf где Mmax Ч максимальное число точек в сигнальном множестве. Эта величина может быть существенно уменьшена путем использования какого-либо алгоритма сжатия данных. Отсюда видно, что частотное расширение требует передачи намного меньшего объема служебной информации, чем временное расширение. Сложность оптимизации также существенно сокращается. Ввиду того, что в реальных системах радиосвязи коэффициенты ki являются зависимыми, а также в силу специфики адаптивной системы, в которой передача данных производится только по лучшим подканалам, управляющие данные, порождаемые с помощью вышеописанного алгоритма, обладают большой избыточностью. Это может быть использовано для снижения объема служебной информации, передаваемой пользователям. Предположим, что если несколько пользователей используют один и тот же подканал (или подполосу) i, то первый из этих пользователей k1 использует расширяющие последовательности a0,..., aSk1,i 1, второй пользователь k2 Ч aSk1,i,..., aSk2,i 1 и т.д. Таким образом, параметры разделения каждого из подканалов однозначно определяются списком пользователей, использующих данный подканал, и коэффициентами разделения канала4. Тогда схема передачи данных может быть однозначно задана следующими параметрами: 1. Списками подканалов (подполос), используемых каждым из пользователей (т.е. таких, что ki > 0 и cki > 0). Ясно, что эти списки могут быть упорядочены, например, по возрастанию номера подканала. Эта последовательность данных будет обозначаться далее как S. 2. Величинами ki S, характеризующими используемую долю подканала. Эта последовательность данных будет обозначаться далее как R. 3. Параметрами модуляции/кодирования cki для каждого из используемых подканалов. Эта последовательность данных будет обозначаться далее как C.

Здесь удобнее перейти от величин ki к их целочисленным аналогам ki S.

ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Т.к. в большинстве случаев отношения канал/шум для смежных подканалов обладают сильной статистической зависимостью, оказывается, что списки подканалов в основном состоят из перечисления номеров смежных подканалов;

параметры кодирования также оказываются сильно зависимыми. В связи с этим можно ожидать хороших результатов при применении простейшего метода кодирования длины пробегов [170], состоящего в замене n повторов символа x на пару (x, n). Перед применением данного метода для кодирования списка используемых подканалов S (ik1, ik2,..., ikl ) необходимо преобразовать его к виду (дельта-кодирование) (ik1, ik2 ik1,..., ikl ik,l1 ). Последовательности данных, получаемые после кодирования длин пробегов в массивах S и C, обозначаются далее S и C соответственно. Последовательность символов, получаемая после описанных преобразований, обладает существенно неравномерным распределением вероятностей появления различных символов. Следовательно, возможно дальнейшее сжатие служебной информации путем использования кодов Хаффмана [170]. При этом оказывается, что массивы S, C и R обладают несколько различающимися статистическими свойствами. В связи с этим целесообразно осуществлять их обработку независимо. Использование кодов Хаффмана требует передачи не только собственно сжатых данных, но и таблицы (дерева) кодирования, которая в рассматриваемом случае оказывается сопоставимой по размеру со сжатыми данными. В связи с этим целесообразно использование универсального кода Хаффмана, построенного для некоторой типичной конфигурации системы. Соответствующая таблица может быть сконструирована заранее и размещена как на базовой станции, так и в мобильных устройствах. Недостатком такого подхода является то, что при изменении количества активных пользователей в системе, их требований к скорости передачи данных, условий распространения сигнала и т.д. статистические свойства массивов S, C и R также изменяются, вследствие чего универсальные коды Хаффмана не обеспечивают оптимального сжатия. Альтернативой является использование динамических кодов Хаффмана (см., например, [135]). При их использовании обработка передаваемых данных осуществляется в один проход. При поступлении очередного символа xi передатчик кодирует его с помощью кода Хаффмана, оптимального для последовательности символов x1,..., xi1 и обновляет свою таблицу кодирования;

если символ xi отсутствует в таблице, он передается в незакодированном виде. Приемник также динамически обновляет свою таблицу декодирования. Однако использование динамических кодов Хаффмана связано с определенными сложностями: 1. Если кодер (и декодер) начинает работу с пустой таблицы, объем служебных данных на начальном этапе может существенно превышать средний. 2. Ошибка декодирования служебного блока данных может привести к рассинхронизации таблиц кодера и декодера, что сделает невозможной дальнейшую работу приемника. 3. Подключение нового пользователя к системе затруднено ввиду необходимости синхронизации его таблицы декодирования.

ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ Эти проблемы могут быть решены путем использования в качестве начальных таблиц в кодере и декодере некоторых универсальных кодов Хаффмана, а также периодической реинициализации кодера базовой станции и декодеров всех пользователей.

2.2.6 Чувствительность к изменениям состояния канала Вышеописанный оптимизационный подход предполагает, что состояние канала передачи данных остается неизменным по крайней мере во время передачи одного кадра. Однако в практических радиосистемах это предположение в большинстве случаев не выполняется. Более того, в связи с тем, что требуемый объем служебной информации (2.31) достаточно велик, желательно производить оптимизацию схемы передачи как можно реже. Это требует учета возможных изменений состояния канала. Одним из наиболее распространенных методов учета изменений состояния канала яв(j) ляется линейное предсказание (см., например, [2]) коэффициентов ki, где j Ч номер OFDM-символа, на основе нескольких предшествующих наблюдений и корреляционной функции канала. Однако полная реализация данного метода в многочастотной многопользовательской системе представляется достаточно затруднительной ввиду чрезвычайно большого объема требуемой информации и высокой вычислительной сложности. Кроме того, применение этого подхода не позволяет полностью решить проблему временных изменений канала, т.к. само понятие адаптации предполагает выбор схемы передачи, ориентированной на определенное состояние канала. Ясно, что периодически необходимо производить оптимизацию для учета изменившегося состояния канала. В связи с этим требуется произвести анализ временного интервала, в течение которого одна и та же оптимизированная схема передачи может использоваться без изменений. Предположим, что дисперсия шума в канале равна 2 и в начальный момент времени ki получена некоторая оценка отношения канал/шум ki = 2. Индексы k и i будут далее для простоты опускаться. Предположим далее, что распространение радиосигнала может (j) (j) (j) (j) 2 быть описано с помощью Релеевской модели, т.е. (j) = q + j i, q, i N(0, /2). (j) (j) Тогда случайная величина (j) = a2 + b2, где aj = q /, bj = i / распределены по j j нормальному закону N(0, /2), /2 = 22, имеет экспоненциальное распределение с плотностью 1 p( (j)) = exp( (j) /). (2.32) Пусть M[a0 aj ] = M[b0 bj ] = j /2, M[a0 b0 ] = M[aj bj ] = 0, M[a0 bj ] = M[aj b0 ] = j /2. Тогда ( (0), (j) ) имеет двумерное экспоненциальное распределение [82, 69] 2 2 + j j x+y 1 xy, I0 exp p(0), (j) (x, y) = 2 2 2 2 2 2 2 (1 j j ) (1 j j ) (1 j j )/ (0) (0) 2 Далее будет использоваться обозначение 2 + j = 2. j j Предположим, что в результате работы оптимизационного алгоритма для некоторого подканала была выбрана схема кодирования/модуляции со скоростью c(0). С течением времени состояние канала будет изменяться. Эти изменения могут быть охарактеризованы ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ величинами c(j), соответствующими практически достижимой скорости передачи данных в момент времени j при условии сохранения того же коэффициента усиления V 2. Ясно, что это определение предполагает возможность динамического изменения параметров кодирования/модуляции в каждом символе, что практически невозможно реализовать. Вместе с тем, оно может быть полезно для определения средней достижимой скорости для последовательности символов, что дает возможность, например, подобрать параметры внешнего кода, за счет использования которого могут быть сглажены временные изменения состояния канала. Для определенности предположим, что функция f (c) имеет вид f (c) = (2c 1), где Ч параметр, зависящий от используемых методов кодирования и модуляции, а также требований к вероятности ошибки. Тогда с учетом ограничения (2.21) c(j) может быть выражена как (j) (0) c(j) = log2 1 + (0) (2c 1, (2.33) где (j) и (0) Ч отношения канал/шум в моменты времени j и 0 соответственно. Т.к. (j) является случайной величиной, изменения качества канала могут быть охарактеризованы с помощью условного математического ожидания C(x, c, j ) = M[c(j) | (0) = x, c(0) = c] = = 1 (1 2 ) j log (j) c(0) (2 1 p(j) |(0) (y|x)dy = (0) 0 y + x2 2|j | xy (j) c(0) j 1 + (0) (2 1 exp I0 dy.(2.34) (1 2 ) (1 2 ) j j log2 1 + Отметим, что это выражение не зависит от, т.е. конкретных параметров кодирования/модуляции и требований к вероятности ошибки декодирования. Вместе с тем, если используется кодирование по нескольким подканалам, применение этого выражения, вообще говоря, некорректно. Тем не менее, как будет показано ниже, оно может быть использовано для оценки средних показателей качества работы системы. Рисунок 2.5 иллюстрирует эту зависимость. Можно заметить, что подканалы с наилучшими отношениями канал/шум наиболее чувствительны к временным изменениям состояния канала. Кроме того, потенциальное ухудшение качества подканалов, использующих высокоскоростные методы кодирования, менее существенно, чем в низкоскоростном случае. Это связано с нелинейностью функции f (c), т.е. с тем, что для обеспечения высокой скорости передачи требуется обеспечить столь высокое отношение сигнал/шум, что оно не может существенно ухудшиться при стохастических изменениях свойств канала. Этот подход может быть применен и для анализа адаптивных систем. В этом случае (0) (0) величины ki являются случайными, а cki Ч их функцией. Задача может быть упрощена (0) путем перехода к порядковым статистикам отношений канал/шум ki, аналогично тому, как это было сделано в п. 2.2.3 и п. 2.1.4. Пусть R(0) Ч общая скорость для некоторой схемы передачи данных, построенной в соответствии с принципом УводонаполненияФ. Используя выражение (2.14), получим, что практически достижимая скорость передачи данных в момент времени j в случае канала с независимыми Релеевскими замираниями ит ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ j=0.1, =1 j=0.9, = M[c(j)|(0)=x,c(0)=c]/c M[c(j)|(0)=x,c(0)=c]/c 1 0.8 0.6 0.4 0.2 00 12 14 16 1 0.8 0.6 0.4 0.2 00 c 12 14 16 6 x 20 6 x 20 c Рис. 2.5 Нормализованное ухудшение качества канала N=512 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 100 200 300 400 500 600 700 800 900 1000 j=0.1 j=0.5 j=0. R(j)/R(0) проп. способность Рис. 2.6: Нормализованная практически достижимая скорость для многочастотной системы, = 1 может быть вычислена как R(j) = i:> ln N Ni C(ln N, j ),, N i ln NN i (2.35) где Ч константа УводонаполненияФ (см. (2.16)). Графики этой функции для различных значений j приведены на рис. 2.6. Здесь снова можно заметить уменьшение чувствительности к изменениям состояния канала с ростом общей скорости передачи данных. Длительность временного интервала, в течение которого может использоваться одна и та же схема передачи, определяется следующими факторами: 1. Ухудшение качества работы системы вследствие изменений состояния канала. Ясно, что с ростом L Ч числа смежных OFDM символов, использующих одну и ту же схему передачи, качество работы системы (величина R(j) ) уменьшается.

ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ 2. Величина издержек на построение оптимизированной схемы передачи данных. Это включает в себя оценку состояния канала, вычисление параметров оптимизированной схемы, их передача пользователям и т.п. Пусть d Ч количество OFDM-символов, на протяжении которых осуществляются описанные подготовительные действия. Очевидно, что требования минимизации издержек и увеличения качества работы системы являются противоречивыми. В качестве критерия качества работы подобной системы может рассматриваться величина R(j), r(L, d) = (d + L)R(0) L j= (2.36) называемая далее нормализованной эффективной скоростью передачи данных и характеризующая близость средней скорости передачи данных к идеальной. Как правило, величина d жестко определяется конструктивными параметрами системы, в то время как длительность межоптимизационного интервала L может варьироваться в достаточно широких пределах. Таким образом, возникает задача выбора значения L, максимизирующего r(L, d). Для этого необходимо знание автокорреляционной функции канала. В том случае, когда стохастические изменения состояния канала описываются моделью Джейкса [64], можно показать, что j = J0 (2fD j), где fD Ч максимальный Допплеровский сдвиг, Ч длительность одного OFDM-символа, J0 (x) Ч функция Бесселя нулевого порядка. На рисунке 2.7 представлены кривые функции r(L, d), построенные с учетом этого выражения. Несмотря на отмеченную выше более сильную чувствительность к изменениям канала высокоскоростных схем передачи, оптимальные значение L для всех рассмотренных скоростей оказывается достаточно близким. Это связано с тем, что при небольших d построение новой оптимизированной схемы сопряжено с меньшими издержками по сравнению с использованием неоптимизированной схемы. Отсюда также следует, что значение L, оптимальное с точки зрения пропускной способности ( = 1), будет близко к оптимальному и для реальных схем кодирования/модуляции ( > 1). В данном разделе снова игнорировалась возможность совпадения наилучших подканалов для нескольких пользователей. Т.к. рассматриваемая система допускает совместное использование подканалов, это предположение не оказывает существенного влияния на результаты анализа.

2. Выводы В данной главе были представлены адаптивные методы передачи для однопользовательских и многопользовательских систем. В случае однопользовательской системы применение многоуровневого кодирования позволяет повысить точность подбора скорости кодирования/модуляции для отдельных подканалов. Был предложен прагматический способе построения семейства многоуровневых кодов на основе сравнительно небольшого числа двоичных линейных кодов, не требующий нахождения весового спектра компонентных ГЛАВА 2. АДАПТИВНЫЕ МЕТОДЫ ПЕРЕДАЧИ d=4, N=512, fc= 5 GHz 1.4 R=16, v=20 km/h R=16, v=50 km/h R=150, v=20 km/h R=150, v=50 km/h 1. r(L,d) 0. 0. 0. 0. 0 0 10 20 30 40 50 L 60 70 80 90 Рис. 2.7 Нормализованная эффективная скорость передачи данных кодов, что существенно упрощает проектирование системы. Кроме того, предложен способ оценки пропускной способности (а также спектральной эффективности) адаптивных систем, функционирующих в условиях канала со случайными независимыми передаточными коэффициентами, позволяющий оценить характеристики системы в области малых отношения сигнал/шум без использования имитационного моделирования. Предложенный метод адаптивного многоуровневого кодирования может быть также использован и в случае многопользовательской системы. Для случая многопользовательской системы был предложен метод адаптивного распределения мощности, скорости передачи и кодового разделения канала, позволяющий, как будет показано ниже, получить энергетический выигрыш до 5 дБ по сравнению с аналогичной системой на основе частотного разделения. Предложен метод сжатия служебной информации, порождаемой адаптивной системой. Приведена теоретическая нижняя граница для мощности передатчика в адаптивной системе, использующей данный алгоритм. Было проанализировано поведение предложенной адаптивной системы при наличии временных стохастических изменений его состояния.

Глава 3. Вычислительные процедуры декодирования В данной главе представлены новые алгоритмы решения вычислительных задач, возникающих при алгебраическом декодировании некоторых кодов, исправляющих ошибки. В разделе 3.1 описывается метод ускорения процедуры Ченя, используемой в классическом синдромном декодере. Раздел 3.2 посвящен описанию метода быстрого вычисления дискретного преобразования Фурье над конечным полем, что может быть использовано для ускоренного вычисления синдромного многочлена. В разделе 3.3 описывается метод построения разреженного представления линейных блоковых кодов. В разделе 3.4 представлен метод параллельного вычисления интерполяционного многочлена при списочном декодировании кодов Рида-Соломона.

3. Ускоренный поиск корней многочленов над конечными полями 3.1.1 Аффинное разложение В данном разделе описывается улучшенный алгоритм вычисления значений многочлена в большом числе точек, который может быть использован при переборном поиске корней [38]. Стандартным приемом снижения сложности вычислительных процедур является повторное использование на каждом шаге результатов ранее выполненных вычислений. В случае линеаризованных и аффинных многочленов для этого может быть использовано свойство (1.43). Действительно, предположим, что необходимо вычислить набор значений аффинного многочлена A(x) = L(x) + во всех точках x(i) GF (2m). В силу теоремы 1, эта задача может быть представлена как m1 m A(x(i) ) = + j= xj L(j ), x(i) = j= (i) xj j, xj GF (2).

(i) (i) (3.1) Тогда A(x(i) ) = A(x(i1) ) + (i) (i1) j:xj =xj L(j ), x(0) = 0.

(3.2) Выражение (3.2) задает процедуру вычислений, приводящую к набору значений многочлена A(x) во всех x(i) GF (2m ). Для своего функционирования он требует наличия значений L(j ), которые должны быть найдены на подготовительном этапе вычислений.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Для минимизации сложности этой процедуры необходимо найти такое упорядочение элементов конечного поля, при котором число сложений на каждом шаге было бы минимально, т.е. необходимо найти такую последовательность элементов конечного поля x(i), m (i) (i1) что 2 1 |{j|xj = xj }| минимально. При этом отметим, что каждое из слагаемых в i=1 этом выражении не может быть меньше единицы. Определение 4. Кодом Грея называется такая последовательность двоичных векторов длины m, что соседние вектора различаются ровно в одной позиции. В силу того, что каждому элементу GF (2m ) может быть сопоставлен двоичный вектор длины m, элементы поля всегда могут быть упорядочены в соответствии с каким-либо кодом Грея. Поэтому на каждом шаге процедуры (3.2) придется выполнять ровно одно сложение. В настоящее время известны эффективные методы порождения кода Грея [173], что делает описанную процедуру чрезвычайно эффективной. Описанный подход может быть обобщен на случай произвольных многочленов, если удастся разбить их на набор аффинных. Теорема 2. Всякий многочлен f (x) = гочленов, кратных аффинным: f (x) = f3 x + i=0 3 t i i=0 fi x может быть разложен на сумму мно (t4)/ x5i (f5i + Li (x)), (3.3) где Li (x) = 3 2j j=0 f5i+2j x Ч линеаризованные многочлены, fj = 0 для всех j > t Доказательство. Пусть k = (t 4)/5. Выражение (3.3) может быть переписано как k f (x) = fk (x) = f3 x + i= x5i (f5i + Li (x)) = Fk1 (x) + x5k (f5k + f5k+1 x + f5k+2 x2 + f5k+4 x4 ) + x5(k1) f5k+3 x8, где f1 (x) = 0. Для k = 0 (t 4) справедливость теоремы очевидна. Предположим, что она выполняется для некоторого k 1 > 0. Тогда очевидно, что предпоследнее слагаемое (3.4) является многочленом, кратным аффинному, а последнее может быть сгруппировано с соответствующим слагаемым fk1 (x). Таким образом, для вычисления значения многочлена во всех точках конечного поля может использоваться следующий алгоритм: 1. Построить таблицы значений линеаризованных многочленов из разложения (3.3): (k) Li = Li (k ), k = [0;

m 1], i [0;

(t 4)/5];

2. Произвести инициализацию Ai = f5i ;

(0) ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 3. Представив все элементы поля xj GF (2m ), j [0;

2m 1], разложенные в стан((x,x )) (j) (j1) + Li j j1, j дартном базисе, как элементы кода Грея, вычислить Ai = Ai [1;

2m 1], где (xj, xj1 ) указывает координату, в которой xj отличается от xj1 ;

4. Вычислить f (xj ) = f3 x3 + j корнем многочлена.

(t4)/5 i= x5i Ai, j [0;

2m 1]. Если f (xj ) = 0, xj является j (j) Сложность данного алгоритма равна Caf f = m t+1 (4Cmul + 3Cadd ) + 5 t+1 (2Cadd + Cmul ) + 2Cexp W, 5 (3.4) где W Ч число обращений к процедуре вичисления значений многочлена (1.39). Необходимо отметить, что впервые подход, основанный на сведении произвольного многочлена к набору аффинных, был предложен в работе [128]. Однако описанное там преобразование было возможно только для некоторых многочленов степени не выше 11 и требовало громоздких предварительных вычислений. По имеющейся у автора информации, применение кода Грея для вычисления значений аффинных многочленов в литературе описано не было.

3.1.2 Специальные разложения В некоторых случаях оказывается возможным построить более эффективные алгоритмы на основе других разложений. Пример 1. Для многочленов степени t 8 может быть использовано разложение 8 i A1 (x) + x3 (A2 (x) + f6 x3 ), F (x) = i=0 fi x = A1 (x) = f0 + L1 (x) = f0 + f1 x + f2 x2 + f4 x4 + f8 x8, A2 (x) = f3 + L2 (x) = f3 + f5 x2 + f7 x4.

(3.5) Использование этого разложения позволяет избежать выполнения одной операции возведения в степень. Сложность вычислений с использованием этого разложеиня равна C8 = m(6Cmul + 4Cadd ) + (4Cadd + 2Cmul + Cexp ) W. Пример может быть обобщен на случай t 17: F (x) = A1 (x) + x3 (A2 (x) + x3 (f6 + x3 (A3 (x) + x3 (A4 (x) + f15 x3 ))), A3 (x) = f9 + f10 x + f11 x2 + f13 x4 + f17 x8, A4 (x) = f12 + f14 x2, Сложность вычислений с использованием этого разложения равна C17 = m(12Cmul + 8Cadd ) + (9Cadd + 5Cmul + Cexp ) W. (3.8) (3.6) Пример 2.

(3.7) ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 3.1.3 Обобщенное разложение Одним из возможных методов построения разложений, отличных от (3.3), является замена показателя степени 5 (эта величина будет называться далее показателем разложения) другим числом. Рассмотрим ограничения, которым должен удовлетворять показатель разложения. Определение 5. Число r называется примитивным корнем по модулю простого числа p, если (j : 0 < j < p) i : 0 i < p 1 : r i j (mod p) Для того, чтобы построить разложение по многочленам, кратным аффинным, необходимо так сгруппировать слагаемые, чтобы выполнялось соотношение: i A j, k : i = pj + 2k, (3.9) где A Ч множество номеров коэффициентов, группируемых в остаточный член произвольного вида (например, в разложении (3.3) A = {3}). Это приведет к разложению F (x) = F0 (x) + i xpi Ai (x), где F0 (x) Ч некоторый остаточный член, соответствующий множеству A, p Ч простое число, Ai (x) Ч аффинные многочлены. Очевидно, что условие (3.9) эквивалентно тому, что число 2 является примитивным корнем по модулю p. Однако оказывается, что для простых чисел, больших 5, не удается построить разложения с небольшим остаточным членом (множеством A малой мощности). Эта трудность может быть преодолена, если учесть, что все ненулевые элементы конечного поля GF (2m ) образуют циклическую группу по умножению порядка n = 2m 1. Предположим, что n = pi, где pi Ч простые числа, одно из которых p0 имеет примитивный корень 2. Тогда (3.9) может быть заменено на i j, k : i p0 j + 2k mod n (3.10) i В силу того, что 2 является примитивным корнем по модулю p0, последнее соотношение выполняется для всех i < n, т.е. возможно построение разложения с нулевым остаточным членом.

3.1.4 Гибридный алгоритм поиска корней многочленов Ввиду того, что аналитический алгоритм поиска корней многочленов степени не выше 4 выполним за детерминированное и достаточно малое время, представляется целесообразным использовать его при поиске корней произвольных многочленов. Это может быть t выполнено путем деления исходного многочлена степени t на многочлен i= (x xi ), где xi Ч корни многочлена, которые должны быть найдены каким-либо иным методом. Исследования показали, что наиболее быстрым алгоритмом является метод аффинного разложения (см. п. 3.1.1). Таким образом, можно предложить следующий алгоритм поиска корней многочленов произвольной степени:

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Таблица 3.1 Среднее время (мкс) поиска корней Степень Алгоритм Общее СпециЧеня аффинное альное разлоразложение жение (3.3) (3.5) 5 14,6 13,4 10,0 6 17,2 14,8 10,1 7 19,6 14,9 10,8 8 22,2 15,1 10,8 9 24,9 15,4 Ч 10 27,3 16,9 Ч 11 29,8 18,0 Ч 12 32,3 18,1 Ч 13 34,8 18,2 Ч 14 37,3 18,2 Ч 15 39,8 20,1 Ч 16 42,3 21,3 Ч 17 44,9 21,3 Ч многочленов Гибридный метод, основанный на (3.5) 2,3 3,6 4,9 5,8 Ч Ч Ч Ч Ч Ч Ч Ч Ч различными Специальное разложение (3.7) Ч Ч Ч 11,4 15,5 16,4 16,4 16,4 16,9 17,4 17,4 17,9 17, методами Гибридный метод, основанный на (3.7) Ч Ч Ч 6,7 9,5 11,0 11,6 12,2 13,5 14,2 14,8 15,8 16, 1. Если степень многочлена превышает 4, то построить аффинное разложение в соответствии с п. 3.1.1 и перебирать элементы поля, упорядоченные в соответствии с кодом Грея, вычисляя значение многочлена. При обнаружении корня xi разделить исходный многочлен на (x xi ). Как только степень многочлена понизится до 4, перейти к аналитическому методу поиска корней. 2. Корни многочленов степени 3 и 4 могут быть найдены аналитически [131]. С другой стороны, они могут быть найдены и вышеописанным способом. 3. Значения корней многочлена степени 2 после линейной подстановки могут быть найдены с помощью логической схемы умножения на фиксированную матрицу (см. п. 4 на стр. 35). Для оценки реальной эффективности предложенных методов поиска корней многочленов локаторов ошибок они были реализованы программно на языке C++. В таблице 3.1 представлены результаты замеров скорости вычислений, выполненных на ПК с процессором AMD Athlon XP 1700+ под управлением ОС Windows XP. Видно, что применение аффинного разложения позволяет достичь выигрыша по быстродействию до 2 раз, а применение специальных разложений в сочетании с аналитическим методом поиска корней может дать шестикратный выигрыш по производительности.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 3. Быстрое преобразование Фурье над конечным полем При решении многих вычислительных задач, возникающих при реализации алгоритмов кодирования и декодирования, оказывается необходимым вычислять дискретное преобразование Фурье. В данном разделе описан эффективный алгоритм решения этой задачи, а также представлен пример его использования для вычислении вектора синдрома при классическом декодировании кодов Рида-Соломона.

3.2.1 Циклотомический алгоритм БПФ Циклотомическое разложение Рассмотрим набор циклотомических классов по модулю n над GF (2): {0}, {k1, k1 2, k122,..., k1 2m1 1 },..., {kl, kl 2, kl 22,..., kl 2ml 1 }, где ki ki 2mi mod n. Многочлен f (x) = i=0 n fi xi, fi GF (2m ) может быть разложен как l mi f (x) = i= Li (x ), ki Li (y) = j= fki 2j mod n y 2.

j (3.11) Действительно, выражение (3.11) представляет собой способ группировки чисел s [0, n 1] по циклотомическим классам: s ki 2j mod n. Очевидно, что такое разложение существует всегда. Заметим, что при ki = 0 свободный член f0 мы можем записать как значение многочлена L0 (y) = f0 y при y = x0. Выражение (3.11) будем называть циклотомическим разложением многочлена f (x). Пример 3. Многочлен f (x) = 6 i i=0 fi x, fi GF (23 ) представляется как f (x) = L0 (x0 ) + L1 (x) + L2 (x3 );

L0 (y) = f0 y, L1 (y) = f1 y + f2 y 2 + f4 y 4, L2 (y) = f3 y + f6 y 2 + f5 y 4. Быстрое вычисление преобразования Фурье l j ki В соответствии с разложением (3.11) запишем f (j ) = ). Как известно i=0 Li ( ki [169], элемент является корнем соответствующего минимального многочлена степени mi и, следовательно, лежит в подполе GF (2mi ), mi | m. Таким образом, все величины (ki )j принадлежат полю GF (2mi ) и могут быть разложены в каком-либо базисе (i,0,..., i,mi 1 ) mi этого поля:

j ki = s= aijs i,s, aijs GF (2). Тогда значения каждого из линеаризованных многочленов могут быть вычислены в базисных точках соответствующего подполя по формуле ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ mi Li (i,s ) = p= 2 i,s fki 2p, p i [0, l], s [0, mi 1].

(3.12) Базисы (i,0,..., i,mi 1 ) для каждого из линеаризованных многочленов Li (y) могут выбираться независимо. В соответствии с теоремой 1 компоненты преобразования Фурье многочлена f (x) являются линейными комбинациями этих значений l mi Fj = f ( ) = i=0 s=0 l mi 1 mi 1 2 i,s fki 2p p= p j aijs Li (i,s ) = (3.13) aijs i=0 s=, j [0, n 1].

Последнее выражение может быть записано в матричной форме как F = ALf, где F = (F0, F1,..., Fn1 )T, f = (f0, fk1, fk1 2, fk1 22,..., fk1 2m1 1,..., fkl, fkl2, fkl 22,..., fkl 2ml 1 )T есть перестановка вектора коэффициентов исходного многочлена f (x), соответствующая разложению (3.11), A Ч матрица, составленная из элементов aijs GF (2), L Ч блочно2p диагональная матрица, составленная из элементов i,s. Очевидно, что для линеаризованных многочленов одинаковой степени mi, входящих в разложение (3.11), можно выбрать одинаковые базисы (i,s ) в подполях GF (2mi ), вследствие чего матрица L будет содержать большое число одинаковых блоков. Таким образом, задача БПФ разбивается на два этапа: умножение блочнодиагональной матрицы L на исходный вектор f и умножение двоичной матрицы A на полученный вектор S = Lf F = ALf. (3.14) Рассмотрим более подробно первый этап преобразования Фурье Ч задачу вычисления произведения S = Lf. Блочно-диагональная матрица L0 0... 0 0 L1... 0 L=............ 0 0... Ll состоит из блоков 2 i,0 i,0 2 i,1 Li = i,1...... 2 i,mi 1 i,mi Выберем в качестве (i,0,..., i,mi 1 ) нормальный базис i, i2,..., i2 L состоит из блоков вида 2m 1... i,0 i 2m 1... i,1 i....... 2m 1... i,mii mi. Тогда матрица ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ m 1... i2 i 0... i2....... m 2... i2 i В силу блочно-диагональной структуры матрицы L вычисление произведения S = Lf может быть представлено как S = (b0, b1,..., bl )T = L (a0, a1,..., al )T, где bi = (bi,0, bi,1,..., bi,mi 1 ) Ч подвектора искомого вектора S, ai = (ai,0, ai,1,..., ai,mi 1 ) Ч подвектора исходного вектора f. Представим вычисление bT = Li aT как циклическую свертку i i bi (x) = bi,0 + bi,mi 1 x +... + bi,1 xmi 1 = m 1 (i + i2 i x +... + i2 xmi 1 )(ai,0 + ai,1 x +... +ai,mi 1 xmi 1 ) mod (xmi 1). Для ее вычисления могут быть применены известные алгоритмы [155, 160, 150]. При m 1 этом использование свойства нормального базиса i + i2 +... + i2 i = 1 позволяет заметно сократить число операций при вычислении циклической свертки. Отметим, что вычисление значений линеаризованных многочленов с помощью циклической свертки было описано в монографии [160]. Описанный подход позволяет свести задачу умножения блочно-диагональной матрицы L на исходный вектор f над GF (2m ) к задаче вычисления l + 1 циклических сверток малой длины mi. Существующие алгоритмы вычисления циклических сверток bi (x) = i (x)ai (x) mod (xmi 1) могут быть записаны в матричном виде как i bi,0 2mi 1 bi,1 (Pi ai ), = Qi Di i (3.15) bi =...... bi,mi 1 i2 ведение векторов. Очевидно, что вектор Ci = Di i, i2 i,..., i2 может быть вычислен заранее. Таким образом, выражение (3.14) может быть переписано как F = AQ (C (P f )), (3.16) где Qi, Di и Pi являются двоичными матрицами, а x y обозначает покомпонентное произm i2 i2 2 i4 Li = i...... 0 2mi 1 i i T где Q Ч двоичная блочно-диагональная матрица объединенных последующих сложений для l+1 циклической свертки, C Ч объединенный вектор констант, P Ч двоичная блочнодиагональная матрица объединенных предварительных сложений. Учитывая формулы (3.14) и (3.16), второй этап БПФ может рассматриваться как умножение двоичной матрицы AQ на вектор C (P f ). Для вычисления произведения (AQ) (C (P f )) могут быть использованы модифицированный алгоритм Учетырех русскихФ (В.Л.Арлазаров, Е.А.Диниц, М.А.Кронрод, И.А.Фараджев) для умножения булевых матриц со сложностью O(n2 / log n) сложений над элементами поля GF (2m) [151] или алгоритм, описываемый в разделе 3.3.2.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Оценка сложности алгоритма Как было показано, задача вычисления БПФ многочлена над GF (2m ) сводится к набору задач вычисления циклической свертки многочленов и умножению на двоичную матрицу. Предполагая, что сложность вычисления короткой циклической свертки в конечном поле асимптотически равна Cconv (t) = O(m logt m), t 2, получим, что сложность всего алгоритма равна C= l i=0 l Cconv (mi ) + Cbm = i=0 O(mi logt mi ) + Cbm = n O( m m logt m) + Cbm = O(n logt log n) + Cbm.

Здесь Cbm Ч сложность умножения на двоичную матрицу. Асимптотическая оценка сложности процедуры умножения на двоичную матрицу, порождаемой вышеописанным алгоритмом, на момент написания данной работы автору неизвестна и требует дальнейших исследований. Если оценить сложность данного этапа через сложность алгоритма Учетырех русскихФ (n2 / log n), то следует признать, что предложенный алгоритм БПФ эффективен только при малых значениях длины преобразования (см. таблицу 3.2), хотя известны асимптотически более эффективные алгоритмы БПФ для конечных полей со сложностью O(n log2 n) операций в основном поле [139, 3]. Пример Пример 4. Продолжим рассмотрение БПФ длины 7 над полем GF (23 ). Пусть Ч корень примитивного многочлена x3 + x + 1. В качестве базиса поля GF (23 ) выберем нормальный базис (, 2, 4 ), где = 3. Разложим многочлен f (x) как в примере 3 и представим компоненты преобразования Фурье в виде сумм f (0) = L0 (0 ) + L1 (0 ) + L2 (0 ) = L0 (1) + L1 () + L1 ( 2 ) + L1 ( 4 ) + L2 () + L2 ( 2 ) + L2 ( 4 ) f (1) = L0 (0 ) + L1 () + L2 (3 ) = L0 (1) + L1 ( 2 ) + L1 ( 4 ) + L2 () f (2) = L0 (0 ) + L1 (2 ) + L2 (6 ) = L0 (1) + L1 () + L1 ( 4 ) + L2 ( 2 ) f (3) = L0 (0 ) + L1 (3 ) + L2 (2 ) = L0 (1) + L1 () + L2 () + L2 ( 4 ) f (4) = L0 (0 ) + L1 (4 ) + L2 (5 ) = L0 (1) + L1 () + L1 ( 2 ) + L2 ( 4 ) f (5) = L0 (0 ) + L1 (5 ) + L2 () = L0 (1) + L1 ( 4 ) + L2 ( 2 ) + L2 ( 4 ) f (6) = L0 (0 ) + L1 (6 ) + L2 (4 ) = L0 (1) + L1 ( 2 ) + L2 () + L2 ( 2 ).

Эти тождества могут быть записаны в матричной форме как ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 1 F0 F1 1 F2 1 F = F3 = 1 F4 1 F5 1 1 F6 L0 (1) 1 0 L1 () 0 L1 ( 2 ) 1 L1 ( 4 ) = AS. 1 L2 () 1 L2 ( 2 ) L2 ( 4 ) 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 1 Первый этап алгоритма БПФ состоит в вычислении двух циклических сверток 1 2 4 ai,0 bi,0 bi,1 = 2 4 1 ai,1, i = 1, 2, ai,2 4 1 2 bi,2 где a0,0 f0 b0,0 L0 (1) f1 a1,0 L1 () b1,0 f2 a1,1 L1 ( 2 ) b1,1 L1 ( 4 ) = b1,2, f = f4 = a1,2. S= f3 a2,0 L2 () b2,0 2 f6 a2,1 b2,1 L2 ( ) 4 a2,2 f5 b2,2 L2 ( ) Тогда задачу БПФ можно переписать 10 0 1 0 2 F = A 0 4 0 0 0 0 в виде f0 00000 2 4 f1 0 0 0 4 1 0 0 0 f2 1 2 0 0 0 f4. 0 0 1 2 4 f3 0 0 2 4 1 f6 f5 0 0 4 1 Используя алгоритм вычисления трехточечной циклической свертки bi (x) = bi,0 +bi,2 x+ bi,1 x2 = ( + 4 x + 2 x2 )(ai,0 + ai,1 x + ai,2 x2 ) mod (x3 1), представленный в [155], получим 111 bi,0 1011 bi,1 = 1 1 1 0 0 1 1 4 bi = 1 1 0 2 bi,2 1101 101 111 0 1 1 ai,0 1 1 0 ai,1 = ai,2 101 Qi (Ci (Pi ai )), i = 1, 2.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ С учетом + 2 + 4 = 1 видно, что алгоритм требует 3 умножений, 4 предварительных и 5 последующих сложений. Теперь можно записать формулу (3.16) для рассматриваемого примера в матричной форме 111 F0 F1 1 0 1 F2 1 1 0 F = F3 = 1 1 0 F4 1 1 1 F5 1 0 0 101 F6 1 1 1 0 2 + 4 0 + 4 0 + 2 0 1 0 2 + 4 0 + 4 0 + 2 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 0 00000000 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 00001101 0 0 f0 0 f1 0 f2 0 f4 = (AQ)(C (P f )). 1 f3 1 f6 0 f5 0 0 0 0 0 1 0 1 Этот этап может быть выполнен за 17 сложений. Таким образом, БПФ длины 7 сводится к следующей последовательности действий:

Второй этап БПФ состоит в 1 1 1 F = 1 1 1 умножении двоичной матрицы AQ на вектор C (P f ) 10001000 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 (C (P f )). 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ выполнение предварительных сложений P f V1 V2 V3 V4 = f2 + f4 = f1 + f2 = f1 + f4 = f1 + V1 V8 = f6 + f5 V9 = f3 + f6 V10 = f3 + f5 V11 = f3 + V8, выполнение умножений на константы C (P f ) V5 = V1 V6 = V2 2 V7 = V3 4 V12 = V8 V13 = V9 2 V14 = V10 4, умножение матрицы AQ на вектор C (P f ) T10 = V12 + V14 T11 = f0 + V11 T14 = f0 + V4 T15 = V5 + V6 T16 = V6 + V13 F0 = V4 + T11 T9 = V12 + T16 T7 = V7 + T9 T8 = V5 + T9 F2 = T8 + T11 F3 = T7 + T14 T12 = F2 + T10 T13 = F3 + T15 F4 = T7 + T12 F5 = T10 + T13 F6 = F5 + T7 F1 = F4 + T8.

Общая сложность алгоритма составляет 23 = 6 умножений и 24+17 = 25 сложений, что на одно сложение меньше, чем для алгоритма, представленного в работе [165]. Сравнение сложности алгоритмов быстрого преобразования Фурье Вычисление a + b (или a b) будем считать сложением (умножением) только тогда, когда оба слагаемых (сомножителя) принадлежат основному полю [156], то есть операции в простом подполе не учитываются [155]. В таблице 3.2 приведена сложность БПФ длины n = 2m 1 над полями GF (2m ) в числе умножений Nmul и сложений Nadd. Схема Горнера описана, например, в [160], а модификация алгоритма Герцеля для конечных полей рассмотрена в монографии [155]. Описанный метод представляет собой систематический подход к построению преобразования Фурье над конечным полем. Вместе с тем, необходимо отметить, что приведенные преобразования имеют много общего с [165]. Основные отличия состоят в следующем: 1. Матрица L имеет регулярную структуру. Это позволяет свести задачу минимизации числа умножений к классической задаче вычисления циклической свертки. 2. Алгоритм содержит всего два умножения двоичных матриц на векторы, что может быть использовано для более глубокой оптимизации.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ n 7 15 31 63 127 255 Таблица 3.2 Сложность некоторых алгоритмов БПФ Метод ГорнеАлгоритм Алгоритмы из Метод Захара Герцеля [160] и [150] ровой [165] Nmul Nadd Nmul Nadd Nmul Nadd Nmul Nadd 36 42 12 42 9 35 6 26 196 210 38 210 20 70 16 100 900 930 120 930 108 645 60 388 3844 3906 282 3906 158 623 97 952 15876 16002 756 16002 594 5770 468 3737 64516 64770 1718 64770 1225 4715 646 35503 260100 260610 4044 260610 4374 Ч Ч Ч Предлагаемый метод Nmul Nadd 6 25 16 77 54 315 97 805 216 2780 586 7919 1014 3. Используется более эффективный алгоритм оптимизации последовательности сложений.

3.2.2 Применение обратного преобразования Фурье для быстрого вычисления вектора синдрома Т.к. все матрицы в (3.14) обратимы, обратное преобразование Фурье может быть записано как f = L1 A1 F. (3.17) Легко показать, что матрица, обратная к циркулянтной матрице, также является циркулянтной [59]. Поэтому задача вычисления ОПФ сводится к умножению на двоичную матрицу и вычислению нескольких циклических сверток. В силу известного свойства симметрии ОПФ может быть получено из прямого преобразования перестановкой координат вектора. Следовательно, выражение (3.17) также задает алгоритм вычисления прямого преобразования. Это позволяет рассматривать предложенный алгоритм как обобщение алгоритма Герцеля. Действительно, деление на минимальные многочлены можно рассматривать как умножение на двоичную матрицу, а вычисление значений полученных остатков может рассматриваться как умножение векторов их коэффициентов на соответствующие матрицы Вандермонда. Пример 5. Рассмотрим построение алгоритма БПФ длины 7 над конечным полем GF (23 ). Пусть Ч корень примитивного многочлена x3 + x+ 1. В качестве базиса поля GF (23) выберем нормальный базис (, 2, 4 ), где = 3. Тогда алгоритм БПФ может быть записан в следующем виде:

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Учитывая связь прямого и обратного преобразований Фурье, получим следующую эквивалентную запись алгоритма БПФ f0 F0 f1 F6 f2 F5 1 1 F = F3 = L A f3 = L1 A1 f, f4 F4 f5 F1 f6 F2 где через F и f обозначены перестановки векторов коэффициентов F и f.

Обратное преобразование Фурье вектора F может быть получено следующим образом f0 f1 f2 f = f4 = L1 A1 F = f3 f6 f5 F0 1111111 1000000 0 1 2 4 0 0 0 1 0 0 1 1 1 0 F1 0 2 4 1 0 0 0 1 1 0 1 0 0 1 F2 0 4 1 2 0 0 0 1 0 1 0 0 1 1 F3. 0 0 0 0 1 2 4 1 1 0 0 1 0 1 F4 0 0 0 0 2 4 1 1 1 1 0 0 1 0 F5 F6 1011100 0 0 0 0 4 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 1 100 1 0 0 1 2 0 0 2 4 1 0 4 1 1 0 0 0 1 0 0 0 000 F0 F1 F2 F = F3 = ALf = F4 F5 F6 f0 0000 4 0 0 0 f1 1 0 0 0 f2 2 0 0 0 f4. 0 1 2 4 f3 0 2 4 1 f6 f5 0 4 1 ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Используя алгоритм вычисления трехточечной циклической свертки bi (x) = bi,0 +bi,2 x+ bi,1 x2 = ( + 4 x + 2 x2 )(ai,0 + ai,1 x + ai,2 x2 ) mod (x3 1), представленный в [155], получим bi,0 1011 1 1 1 0 bi = bi,1 = bi,2 1101 111 111 0 1 1 4 0 1 1 ai,0 1 1 0 2 1 1 0 ai,1 = ai,2 101 101 Qi (Ci (Pi ai )), i = 1, 2. С учетом + 2 + 4 = 1 видно, что алгоритм требует 3 умножений, 4 предварительных и 5 последующих сложений. Таким образом, получаем следующую запись алгоритма БПФ 100000000 F0 F6 0 1 0 1 1 0 0 0 0 F5 0 1 1 1 0 0 0 0 0 F = F3 = 0 1 1 0 1 0 0 0 0 F4 0 0 0 0 0 1 0 1 1 F1 0 0 0 0 0 1 1 1 0 000001101 F2 1 1 1 0 2 + 4 0 + 4 0 + 2 0 1 0 2 + 4 0 + 4 0 + 2 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 f0 1 0 f1 1 f2 1 f3 = 1 f4 0 f5 f6 Или, перемножая матрицы P и A1, имеем 1 1 1 1 2 + 4 0 + 4 0 F = Q + 2 0 1 1 2 + 4 0 + 4 0 0 + Q(C (P A1 f )). 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 f0 0 f1 1 f2 1 f3. 1 f4 0 f5 1 f6 ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Таким образом, вычисление БПФ длины 7 сводится к следующей последовательности действий: выполнение предварительных сложений (P A1 ) f V10 = f3 + f5 V11 = f1 + V10 V2 = f2 + V11 V6 = f4 + V11 V9 = f6 + V2 V12 = f4 + V9 F0 = f0 + V12 V8 = f5 + V9 V13 = f6 + F0 V1 = V10 + V13 V5 = V1 + V12 V7 = V6 + V8 V4 = V7 + V10 V3 = V2 + V4, выполнение умножений на константы C (P A1 f ) V14 = V2 V15 = V3 2 V16 = V4 4 V17 = V6 V18 = V7 2 V19 = V8 4, умножение матрицы Q на вектор C (P A1 f ) T1 = V1 + V16 T2 = V14 + V15 F6 = V15 + T1 F5 = V1 + T2 F3 = V14 + T1 T3 = V5 + V19 T4 = V17 + V18 F4 = V18 + T3 F1 = V5 + T4 F2 = V17 + T3.

Общая сложность алгоритма составляет 23 = 6 умножений и 14+25 = 24 сложения, что на одно сложение меньше, чем для алгоритма, представленного в табл. 3.2. Рассмотрим далее применение описанного алгоритма БПФ для вычисления компонентов вектора синдрома при декодировании кодов Рида-Соломона. В соответствии с (1.33), они могут быть представлены как Sl = Z(l ), l = 0..d 2, где Ч примитивный элемент поля GF (2m ) и Z(x) Ч многочлен, соответствующий принятой последовательности. Очевидно, что эта последовательность представляет собой неполное дискретное преобразование Фурье. Воспользуемся для его вычисления алгоритмом (3.17). Т.к. в большинстве случаев d < n, где n = 2m 1 Ч число ненулевых элемен тов поля, все требуемые компоненты вектора F покрываются небольшим числом блоков 1 матрицы L. Естественно, что выполнять умножение вектора A1 f на оставшиеся блоки не требуется. Это дает возможность отбросить также часть строк матрицы A1. Таким образом, получено следующее выражение для вычисления вектора синдрома (неполного ДПФ): S = Q (C (P f )), (3.18) ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ где матрица Q образована вычеркиванием ненужных блоков матрицы Q, вектор C получен аналогичным образом из вектора C, матрица P образована таким же образом из матрицы P A. Кроме того, в большинстве случаев не требуется вычислять все компоненты произведения матрицы A на отдельный блок матрицы L1, т.е. возникает задача вычисления неполной циклической свертки. Алгоритмы, являющиеся оптимальными для случая полной циклической свертки, в общем случае перестают быть таковыми в случае их применения для вычисления неполной циклической свертки. Далее будет описан подход, позволяющий преобразовать билинейный алгоритм для вычисления полной циклической свертки вида (3.15) в эффективный алгоритм для вычисления неполной циклической свертки. Очевидно, что неполная циклическая свертка может быть вычислена путем вычеркивания части строк из матрицы Qi в (3.15). Это может привести к образованию в ней нулевых столбцов. Ясно, что не требуется вычислять те компоненты вектора попарных произведений, которые соответствуют нулевым столбцам, что дает некоторое снижение сложности. Более того, анализируя алгоритмы вычисления циклической свертки, представленные в [155], можно заметить, что вычеркивая различные комбинации строк из матрицы Qi, можно получить различное число нулевых столбцов в оставшейся части матрицы. Т.к. изменение порядка элементов нормального базиса (коэффициентов одного из многочленов, участвующих в циклической свертке) приводит к изменению порядка коэффициентов результирующего многочлена, можно подобрать такое упорядочение коэффициентов нормального базиса, что требуемые компоненты вектора ДПФ будут покрываться строками матрицы Q с наибольшим числом нулевых столбцов, что приведет к существенному снижению требуемого числа умножений. Пример 6. Рассмотрим применение алгоритма БПФ-7 из примера 5 к задаче вычисления первых двух компонент F0 и F1 вектора ДПФ (компоненты вектора синдрома для кода (7, 5, 3) Рида-Соломона над GF (23 )). Вычеркивая избыточные строки матрицы Q, получим f0 f1 1 1 1 1 1 1 1 1 f 1 0 0 0 1 1 0 0 1 0 1 1 2 F0 f3. 2 = F1 0 1 1 1 + 4 0 1 0 1 1 1 0 0 0 1 0 1 1 1 f4 + 4 f5 f ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Таблица 3.3 Код (n, k, d) (255, 253, 3) (255, 251, 5) (255, 249, 7) (255, 247, 9) (255, 245, 11) (255, 243, 13) (255, 241, 15) (255, 239, 17) (255, 223, 33) Сложность вычисления Предложенный метод Nmul Nadd 7 508 17 905 27 1250 37 1643 45 1909 55 2350 65 2689 75 2938 149 синдрома для некоторых Схема Горнера Nmul Nadd 254 508 762 1016 1270 1524 1778 2032 2286 2540 2794 3048 3302 3556 3810 4064 7874 кодов Рида-Соломона Метод Захаровой Nmul Nadd 7 529 18 875 30 1268 41 1652 51 2036 62 2391 74 2789 85 2989 167 Это дает следующий алгоритм вычисления вектора синдрома: T0 := f5 + f6 ;

T1 := f2 + f4 ;

T2 := f0 + f3 ;

T3 := f1 + f4 ;

T4 := T0 + T2 ;

T5 := T0 + T1 ;

T6 := f1 + T4 ;

F0 := T8 ;

T7 := T8 := T9 := T10 := T11 := T12 := f3 + T3 T1 + T6 f5 + T7 T9 2 T5 T10 + T F1 := T4 + T Заметим, что изменение порядок элементов нормального базиса (например, ( 2, 4, )) приведет к изменению порядка строк матрицы Q. Однако ввиду небольшой размерности рассматриваемого примера, в данном случае это не приведет к изменению числа нулевых столбцов. Описанный метод был использован для построения алгоритма вычисления синдромного многочлена для (255, 239, 17) кода Рида-Соломона (определенного, например, в стандарте IEEE 802.16a). Полученный алгоритм требует 75 умножений и 2938 сложений, в то время как применение классической схемы Горнера требует 15 254 = 3810 умножений и 15 254 + 254 = 4064 сложений. Результаты имитационного моделирования показывают, что построенный алгоритм в 8 раз быстрее аналогичного алгоритма, основанного на схеме Горнера. Точное число операций, требуемое для вычисления синдромного многочлена для различных кодов Рида-Соломона, представлено в таблице 3.3. Для сравнения там же приведена сложность аналогичных алгоритмов, полученных с помощью метода Захаровой [166, 165].

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 3. Разреженное представление линейных кодов В большинстве практических систем передачи данных возникает необходимость производить мягкое декодирование используемых корректирующих кодов. Несмотря на то, что многих классов линейных кодов известны чрезвычайно эффективные алгебраические алгоритмы декодирования, для осуществления мягкого декодирования часто возникает необходимость использования комбинаторных алгоритмов (например, алгоритмов Витерби [172] или Бала [99]). Это связано с тем, что большинство алгебраических алгоритмов не учитывают точные значения отношения правдоподобия принятых символов, а их расширения (например, декодирование по обобщенному минимальному расстоянию [41]) во многих случаях дают лишь незначительное повышение качества декодирования. При этом, как правило, сложность комбинаторных алгоритмов декодирования возрастает экспоненциально с ростом длины кода. Однако для некоторых классов кодов оказывается возможным построение приближенных алгоритмов, обеспечивающих очень хорошее качество мягкого декодирования при весьма небольшой сложности. Одним из таких алгоритмов является алгоритм распространения доверия, используемый для декодирования низкоплотностных кодов. Данный алгоритм опирается в своей работе на разреженный фактор-граф линейного кода. В данном разделе описываются два подхода к построению разреженных фактор-графов линейных кодов. Первый подход может быть применен к любому линейному двоичному коду и может быть интерпретирован в контексте быстрого вычисления произведения матрицы и вектора в поле GF (2), что было использовано при построении вышеописанного циклотомического алгоритма БПФ. Второй подход применим к кодам Рида-Соломона и основан на эффективной процедуре вычисления синдрома для кода Рида-Соломона, основанной на циклотомическом алгоритме БПФ.

3.3.1 Построение разреженного фактор-графа линейного двоичного кода Как известно, любой линейный (n, k, d) код может быть задан с помощью своей проверочной r n, r = n k, матрицы H, т.е. все кодовые слова должны удовлетворять соотношению Hy = 0. Это соотношение может также рассматриваться как система линейных уравнений относительно компонентов вектора y h11 y1 +... + h1n yn = 0... hr1 y1 +... + hrn yn = Как было показано в п. 1.4.5, системы уравнений могут быть представлены в виде фактор-графа, в котором символьные узлы соответствуют компонентам y, а проверочные узлы соответствуют отдельным уравнениям. В контексте помехоустойчивого кодирования, восстановление кодового слова по зашумленным оценкам его компонент может быть про ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ изведено с помощью вышеописанного итеративного алгоритма обмена сообщениями на фактор-графе. Однако оказывается, что для большинства известных классов линейных кодов факторграфы, построенные по проверочным матрицам в их стандартном представлении, имеют высокую плотность и большое число циклов длины 4, что препятствует успешному использованию итеративного алгоритма декодирования. В связи с эти возникает задача поиска такого представления кода, которое позволило бы эффективно использовать данный алгоритм. Заметим, что для любой невырожденной матрицы A матрица H = AH задает тот же самый код, что и исходная матрица H. Выберем такую матрицу A, что число единиц в матрице H было бы минимальным. Ясно, что это эквивалентно минимизации плотности фактор-графа (графа Таннера) данного кода. Однако в большинстве случаев оказывается, что в полученном графе сохраняется достаточно большое число циклов длины 4, что препятствует успешному применению итеративного алгоритма декодирования. Необязательно производить полную минимизацию веса матрицы H. Для практических целей оказывается достаточным взять в качестве матрицы H линейно независимый набор векторов малого веса из пространства строк матрицы H. Такой набор может быть получен, например, с помощью алгоритма в [16]. Более того, во многих случаях хорошие результаты дает простейший метод, состоящий в поиске слов достаточно малого веса среди всех линейных комбинаций двух строк матрицы H. Каждый из циклов длины 4 в графе Таннера соответствует наличию комбинации двух слагаемых yi + yj в двух различных проверочных соотношениях. Введем дополнительную переменную yn+1 и положим yn+1 = yi + yj или yn+1 + yi + yj = 0. Несложно заметить, что данная операция эквивалентна введению в граф Таннера символьного и проверочного узлов. Модифицированная проверочная матрица имеет вид H (1) = H (0) 0, w (1) 1 (3.19) где w (1) : wt(w (1) ) = 2 Ч вектор, содержащий две единицы в позициях i и j, т.е. к исходной матрице дописана строка веса 3 и столбец веса 1. Ясно, что если эту строку сложить с другими строками, имеющими единицы в этих позициях, то это приведет к исчезновению циклов длины 4, проходящих через эту пару символьных узлов. Этот процесс может выполняться итеративно до тех пор, пока не будут удалены все циклы длины 4. При этом символьные узлы, соответствующие дополнительным столбцам, могут рассматриваться как внутренние узлы фактор-графа. Тогда для декодирования исходного кода необходимо объявить соответствующие символы стертыми (т.е. присвоить им нулевое отношение правдоподобия) и воспользоваться итеративным алгоритмом декодирования, описанным в разделе 1.4.4. К сожалению, непосредственное применение этого подхода приводит к фактор-графам с большим количеством псевдокодовых слов малого веса, что затрудняет их декодирование в Гауссовском канале. Однако при рассмотрении двоичного канала со стираниями оказывается, что качество декодирования с помощью алгоритма распространения доверия практически не отличается от декодирования по максимуму правдоподобия, что дает воз ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ можность применить данный подход к решению задачи умножения вектора на двоичную матрицу.

3.3.2 Быстрое умножение вектора на двоичную матрицу Рассмотрим задачу вычисления произведения y = Ax, где A Ч некоторая фиксированная m n матрица над GF (2), x Ч произвольный вектор длины n над GF (2m ), m > 0. Ясно, что если компоненты вектора x разложить в некотором базисе GF (2m ), то умножение этого вектора на матрицу сводится к умножению m двоичных векторов на матрицу A, поэтому далее можно ограничиться рассмотрением случая GF (2). Несложно заметить, что исходный вектор x и результат операции y должны удовлетворять соотношению yT (I|A) T = 0, x что позволяет рассматривать матрицу H = (I|A) как проверочную матрицу некоторого кода, а процесс умножения Ч как декодирование в этом коде вектора (_,..., _, x1,..., xn ) со стертыми первыми m символами. Воспользуемся вышеописанным методом для построения разреженного фактор-графа кода с этой проверочной матрицей. Результатом этого является набор соотношений вида ci + cj + ck = 0, где ci, cj, ck соответствуют исходным, промежуточным или окончательным значениям. Анализируя полученный набор соотношений и выделяя те из них, которые содержат два известных члена (например, ci и cj ), можно построить последовательность операций вида ck := ci + cj, позволяющую найти значения промежуточных или окончательных значений. Отметим, что после построения каждой такой операции значение ck становится известным и может быть использовано при дальнейшем построении операций. Этот процесс может рассматриваться как декодирование вектора в двоичном канале со стираниями, выполняемое на этапе построения вычислительного алгоритма. Данный метод был использован при построении циклотомического алгоритма БПФ, описанного в п. 3.2.

3.3.3 Разреженное представление кодов Рида-Соломона Ввиду того, что циклотомический алгоритм БПФ оказывается наилучшим в большинстве практических случаев, целесообразно воспользоваться им для построения разреженного фактор-графа кодов Рида-Соломона. Для этого заметим, что все кодовые слова c кода должны удовлетворять S = HcT = 0, ание ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ XOR2 XOR7 XOR9 XOR0 XOR4 XOR3 XOR5 XOR6 XOR1 XOR8 = V V T T T V V T T T T V V T V T T * XOR * P S P = Рис. 3.1 Разреженный фактор-граф (7, 5, 3) кода над GF (8). т.е. их синдром должен быть равен нулю. Воспользуемся методом построения быстрого алгоритма вычисления синдрома, описанным в п. 3.2.2. Будем рассматривать алгоритм, построенный с помощью этого метода, как набор соотношений, соответствующий факторузлам, а входные параметры алгоритма и его внутренние переменные сопоставим символьным узлам. Это немедленно приводит к некоторому фактор-графу, пример которого представлен на рис. 3.1 (нумерация узлов изменена). При этом его разреженность следует из вычислительной эффективности (малого числа операторов) использованного алгоритма БПФ. На этом рисунке прямоугольные блоки соответствуют тождествам a + b + c = 0, треугольные блоки с метками i Ч b = i, V i соответствует i-му символу кодового слова, треугольные блоки с метками = и = 0 Ч a = b и a = 0. Блоки = и = 0 могут быть удалены из графа путем перекоммутации дуг в соответствии с вышеуказанными тождествами. Это приведет также к удалению узлов T 0, S1, XOR8. Заметим, что описанный метод построения разреженного фактор-графа кода РидаСоломона над GF (2m ) опирается на циклотомический алгоритм БПФ, важной составной частью которого является процедура быстрого умножения на матрицы, реализуемая путем построения разреженного фактор-графа соответствующего линейного кода над GF (2).

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

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 3.4.1 Матричная интерпретация алгоритма Нильсена Лемма 1. Пусть Qj (x, y), j = 0..r 1 Ч набор многочленов, построенный алгоритмом Нильсена после обработки множества V интерполяционных точек (с учетом их кратности r). Тогда все многочлены Q(x, y) : wdeg(0,1) Q(x, y) r 1, имеющие точки из множества V в качестве корней кратности r, могут быть представлены как r Q(x, y) = j= pj (x)Qj (x, y) Доказательство. Пусть задан некоторый многочлен Q(x, y) : wdeg(0,1) Q(x, y) r 1, имеющий точки из множества V корнями кратности r. Следующая процедура аналогична алгоритму деления многочленов от нескольких переменных [167] и алгоритму деления матричных полиномов [162]. 1. Упорядочим члены Q(x, y) в соответствии с wdeg и положим R(x, y) = 0, pj (x) = 0. 2. Пусть LT Q(x, y) = xa y b и LT Qb (x, y) = xc y b. Если a c, то pb (x) := pb (x) + xac, Q(x, y) := Q(x, y) xac Qb (x, y). В противном случае R(x, y) := R(x, y) + LT Q(x, y), Q(x, y) := Q(x, y) LT Q(x, y). 3. Выполнять действия п. 2 до получения Q(x, y) = 0. Ясно, что данная процедура приведет к разложению Q(x, y) = j pj (x)Qj (x, y) + R(x, y). Т.к. все Qj (x, y) имеют все точки множества V корнями кратности r, эти точки будут являться корнями той же кратности многочлена R(x, y). Таким образом, получен многочлен, принадлежащий некоторому классу j = wdeg(0,1) R(x, y) r 1, имеющий корни кратности r во всех точках множества V, такой что R(x, y) wdeg Qj (x, y), что противоречит свойству минимальности Qj (x, y). Определение 6 ([153]). Модулем M над кольцом с единицей R называется множество объектов с определенными над ними операциями + : M M M и : R M M, удовлетворяющими следующим свойствам: 1. a, b, c M : (a + b) + c = a + (b + c) 2. a, b M : a + b = b + a 3. 0 Ma M : a + 0 = a 4. a Mb M : a + b = 0 5. r1, r2 R, m M : r1 (r2 m) = (r1 r2 ) m 6. m M : 1 m = m 7. r R, m, n M : r (m + n) = (r m) + (r n) 8. r1, r2 R, m M : (r1 + r2 ) m = (r1 m) + (r2 m) ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Понятие модуля является обобщением понятия линейного векторного пространста. Очевидно, что множество Q(x, y) : wdeg(0,1) Q(x, y) r 1 является модулем, а множество многочленов, рассматриваемых в Лемме 1 Ч его подмодулем. Таким образом, многочлены Qj (x, y) образуют базис модуля интерполяционных многочленов Q(x, y) : wdeg(0,1) Q(x, y) r 1. r 1 Вектор базисных многочленов Qj (x, y) = i=0 qij (x)y i, j = 0..r 1 может быть представлен как q00 (x) q01 (x)... q0 r 1 (x) q (x) q11 (x)... q1 r 1 (x) = YQ(x), (3.20) Q = (y 0, y 1,..., y r 1 ) 10 qr 1 0 (x) qr 1 1 (x)... qr 1 r 1 (x) где Q(x) Ч матрица многочленов. Тогда каждый шаг алгоритма Нильсена может рассматриваться как умножение этой матрицы на матрицу вида 1 0... 0... 0 0 1... 0... 0... 0 (3.21) 1. 1 j0 j0... (x xi )... j0... 0 0... 0... 1 Отметим, что определитель этой матрицы равен (x xi ), GF (q)\{0}, т.е. над любым расширением GF (q) она вырождена только при x = xi. Таким образом, алгоритм Нильсена может быть представлен как последовательное построение матричного полинома Q(x), столбцы которого являются базисом искомого модуля интерполяционных многочленов. Как уже отмечалось, выполнение алгоритма Нильсена с различным порядком интерполяционных точек приводит к эквивалентным результатам. Предположим, что с его помо(1) (2) щью построены два набора базисных полиномов Qj (x, y) и Qj (x, y) для наборов точек V1, V2 : V1 V2 =. Тогда выполнение алгоритма Нильсена для набора точек V = V1 V2 должно привести к многочленам Qj (x, y), таким что Q(x) = Q(1) (x)P1 (x) = Q(2) (x)P2 (x), (s) (3.22) где Q(x), Q(s) (x) Ч матричные полиномы, соответствующие Qj (x, y) и Qj (x, y) соответственно, а Ps (x) Ч матричные полиномы, образованные произведением матриц (3.21) и унитарных матриц (т.е. матриц, определители которых принадлежат GF (q)\0) линейных преобразований, необходимых для уравнивания многочленов. Определение 7. Правым наименьшим общим кратным матричных полиномов A(x) и B(x) называется такой полином C(x), что: 1. Он делится слева на A(x), B(x): C(x) = A(x)P1 (x) = B(x)P2 (x) ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 2. Всякий другой многочлен C (x), удовлетворяющий вышеприведенному условию, делится слева на C(x), т.е. C (x) = C(x)D(x) Для нахождения ПНОК может быть использована следующая процедура [68]. Сформируем матрицу A(x) B(x) и с помощью элементарных преобразований над столбцами приведем ее к виду R(x) 0, т.е. A(x) B(x) U11 (x) U12 (x) U21 (x) U22 (x) = R(x) 0 (3.23) Несложно показать, что многочлен R(x) является левым набольшим общим делителем A(x) и B(x), а правое наименьшее общее кратное может быть вычислено как C(x) = A(x)U12 (x) = B(x)U22 (x). Таким образом, базисные многочлены для набора точек V1 V2 : V1 V2 = могут быть найдены как ПНОК матричных полиномов, соответствующих базисным многочленам для наборов точек V1 и V2. Однако оказывается, что даже при использовании более эффективных, чем простое применение элементарных преобразований, алгоритмов нахождения ПНОК (например, [11]), сложность этого метода оказывается чрезвычайно большой. Заметим также, что модуль интерполяционных многочленов для набора точек V1 V2 : V1 V2 = является пересечением модулей интерполяционных многочленов, построенных для V1 и V2 по отдельности.

3.4.2 Алгебро-геометрическая интерпретация алгоритма Нильсена Как видно из определения ПНОК, суть описанного выше подхода состоит в пересечении модулей. Но модуль, используемый в алгоритме Нильсена, обладает рядом дополнительных свойств помимо перечисленных в определении 6, что может быть использовано для снижения сложности: 1. Определена операция умножения двух элементов модуля, причем произведение принадлежит некоторому модулю большей размерности, 2. Модуль может рассматриваться как подмножество идеала многочленов от двух переменных. Таким образом, операция пересечения может быть выполнена в надмножестве модуля Ч идеале, а ее результат преобразован далее к требуемому виду. Задача интерполяции может рассматриваться как построение идеала, содержащего все многочлены, имеющие интерполяционные точки корнями заданной кратности, с последующим выбором наименьшего элемента из этого идеала (см., например, [117]). Тогда алгоритм Нильсена может рассматриваться как процесс последовательного добавления интерполяционных точек в аффинное многообразие, порождаемое базисными многочленами Qj (x, y). Введем основные понятия теории идеалов [167]. Определение 8. Подмножество I F[x1,..., xn ], где F Ч некоторое поле, называется идеалом, если выполнены следующие условия:

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ 1. 0 I;

2. Если f, g I, то f + g I;

3. Если f I и h F[x1,..., xn ], то hf I. Идеал может быть порожден конечным набором многочленов Ч базисом:

s < f1,..., fs >= i= hi fi, h1,..., hs F[x1,..., xn ] Определение 9. Пусть F Ч некоторое поле, f1,..., fs F[x1,..., xn ]. Аффинным многообразием, порожденным многочленами fi, i = 1..s называется V (f1,..., fs ) = {(a1,..., an ) Fn |fi (a1,..., an ) = 0, 1 i s} Разобьем множество интерполяционных точек V на непересекающиеся подмножества (s) V1, V2 и построим для каждого из них базисные многочлены Qj (x, y), s {1, 2}. Построим ПНОК для соответствующих им матричных многочленов. Как было показано выше, оно будет соответствовать базисным многочленам для множества V. Таким образом, всякий многочлен Q(x, y), имеющий точки из множества V корнями заданной кратности, может (2) (2) (1) (1) быть представлен как Q(x, y) = r 1 Qj (x, y)pj (x) = r 1 Qj (x, y)pj (x), т.е. j=0 j=0 Q(x, y) I1 I2, Is =< Qj >, s = 1, 2.

(s) Таким образом, задача нахождения ПНОК матричных полиномов может быть заменена задачей пересечения идеалов. Ясно, что пересечение идеалов соответствует объединению соответствующих им аффинных многообразий. Однако алгоритм построения пересечения идеалов [167] достаточно сложен. Лемма 2. Пусть заданы наборы интерполяционных точек V1, V2 : V1 V2 = и со(1) (2) ответствующие им базисные многочлены Qj (x, y), Qj (x, y). Тогда идеалы Is =< (s) Qj (x, y) >, s = 1, 2 являются нульмерными и взаимно простыми. Доказательство. Рассмотрим аффинные многообразия, соответствующие I1 и I2. Заметим, что необходимым условием существования общего корня (x0, y0 ) многочленов (s) Qj (x, y), j = 0..r 1 является вырожденность соответствующей полиномиальной матрицы Q(s) (x) в точке x0. По построению, множество корней ее определителя равно {xi GF (q)|(xi, yi ) Vs }. Т.к. эти множества содержат точки с различными xi, аффинные многообразия, соответствующие I1 и I2, не пересекаются. Следовательно, аффинное многообразие V (I1 + I2 ) пусто и, в соответствии со слабой теоремой Гильберта о нулях, этот идеал совпадает с кольцом многочленов GF (q)[x, y], где GF (q) Ч алгебраическое замыкание исходного поля GF (q). Следовательно, идеалы взаимно просты. Заметим также, что если некоторая величина x0 является корнем определителя матрицы Q(s) (x), то она является вырожденной в этой точке, т.е. существуют такие ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ вектора Y : YQ(s) (x0 ) = 0, причем эти вектора образуют линейное подпространство (s) Y GF (q)r. Т.к. общие корни (xi, yi ) многочленов Qj (x, y) соответствуют векторам 01 вида Yi = (yi, yi,..., yi r 1 ), в Y может быть выделен линейно независимый набор векторов Yi : xi = x0. В силу того, что пространство Y является конечномерным, этот набор также конечен. Таким образом, каждому корню x0 определителя матрицы Q(s) (x) соответствует конечное число нулей (xi, yi ) : xi = x0 идеала Is. Следовательно, идеалы Is являются нульмерными. В соответствии с китайской теоремой об остатках для идеалов, если идеалы взаимно просты, то их пересечение совпадает с их произведением. Таким образом, идеал, соответствующий набору интерполяционных точек V = V1 V2, V1 V2 = может быть построен как I = I1 I2, где I1, I2 Ч идеалы, соответствующие наборам точек V1, V2. Необходимо подчеркнуть, что нахождение некоторого базиса идеала интерполяционных многочленов не является достаточным для решения задачи списочного декодирования. В алгоритме Гурусвами-Судана требуется построение интерполяционного многочлена со взвешенной степенью, не превышающей некоторой фиксированной величины, зависящей от параметров кода. Этот многочлен принадлежит идеалу интерполяционных многочленов, но его выделение требует дополнительных вычислений. Определение 10 ([167]). Пусть задано некоторое мономиальное упорядочение. Базисом Грёбнера полиномиального идеала I F[x1, x2,..., xn ], где F Ч некоторое поле, называется конечное подмножество G = {g1, g2,..., gs } I, такое что < LT (g1 ),..., LT (gs ) >=< LT (I) >. Это определение может быть также переформулировано следующим образом: множество {g1, g2,..., gs } I является базисом Грёбнера, если старший член любого элемента идеала I делится на старший член хотя бы одного элемента G. Таким образом, интерполяционный многочлен минимальной взвешенной степени должен принадлежать базису Грёбнера идеала интерполяционных многочленов, построенных по заданному набору интерполяционных точек. Для нахождения базиса Грёбнера произвольного полиномиального идеала может быть использован алгоритм Бухбергера [167], являющийся обобщением алгоритмов Гаусса и Евклида.

3.4.3 Быстрое вычисление произведения идеалов Как было показано выше, задача интерполяции может быть сведена к вычислению произведения двух взаимно простых идеалов, соответствующих непересекающимся наборам интерполяционных точек. Несложно показать, что произведение двух идеалов (1) (1) (2) (2) (1) (2) I1 =< Q0,..., Qr 1 > и I2 =< Q0,..., Qr 1 > равно идеалу I =< Qj1 Qj2 >. Видно, что число его элементов равно 2. Сопоставляя это значение с оценками размерности r базиса модуля интерполяционных многочленов, представленными выше, можно заметить, что данный базис обладает чрезвычайно большой избыточностью. Действительно, вычислительные эксперименты показывают, что редуцированный базис Гребнера произведения м ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ Ws Vs ( x1, y 1 ) (x2, y2 ) ( x3, y 3 ) Рис. 3.2 Структура множества Ws идеалов имеет намного меньшее число элементов1. Таким образом, непосредственное вычисление произведения идеалов требует вычисления 2 произведений многочленов от двух r переменных и последующего вычисления редуцированного базиса Грёбнера, в ходе которого число многочленов в базисе резко сокращается. Очевидно, что данный метод далек от оптимального. Попытаемся свести задачу вычисления произведения идеалов к задаче вычисления произведения многочленов. Для этого сопоставим базисам исходных идеалов их Упроизводящие функцииФ r Q (x, y, z) = i= (s) Qi (x, y)z i (s) (s) (3.24) Заметим, что порядок записи базисных многочленов Qi (x, y) несущественен. Ясно, что множество корней многочлена Q(s) (x, y, z) имеет вид Ws = {(x, y, z)|(x, y) Vs, z GF (q)} As, (3.25) где Vs Ч аффинное многообразие, соответствующее идеалу Is, и As GF (q) Ч некоторое множество, зависящее от порядка записи базисных многочленов, причем ((x0, y0, z0 ) A) : z GF (q) : (x0, y0, z) A. Структура этого множества представлена на рисунке 3.2. Можно заметить, что точки исходного многообразия соответствуют прямым в множестве корней Q(s) (x, y, z), причем каждая точка, лежащая на такой прямой, имеет кратность не меньшую, чем кратность исходной точки. Кроме того, возникает некоторое количество посторонних корней. Вычислим произведение (2) r 1 (1) Q(x, y, z) = Q(1) (x, y, z)Q(2) (x, y, z) = 2r 2 z i j=0 Qij (x, y)Qj (x, y). Ясно, что прямые, i=0 входящие в множество корней этого многочлена, соответствуют объединению многообразий V1 и V2. Рассмотрим идеал, порождаемый коэффициентами при z i в этом многочлене, В некоторых случаях оно оказывается даже меньше, чем размерность соответствующего модуля, полученного с помощью алгоритма Нильсена.

ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ (1) (2) r 1 т.е. I =< j=0 Qij (x, y)Qj (x, y), i = 0..2r 2 >. Ясно, что множество его нулей совпадает с множеством нулей I = I1 I2.

Теорема 3. Пусть Is =< Q0 (x, y),..., Qr 1 (x, y) >, s = 1, 2 Ч взаимно простые нуль(2) r 1 (1) мерные идеалы. Тогда идеалы I =< j=0 Qij (x, y)Qj (x, y), i = 0..2r 2 > и I = I1 I2 совпадают. Заметим, что эта теорема может быть легко обобщена на случай произвольного числа переменных. Однако для простоты изложения здесь целесообразно ограничиться случаем двух переменных. Для доказательства этой теоремы необходимо ввести следующее определение. Определение 11 ([83]). Пусть D [i,j] Ч дифференциальный оператор, соответствующий взятию смешанной частной производной Хассе порядка i по переменной x и порядка j по переменной y. Пусть xl ym (D [i,j] (s) (s) )= D [il,jm], 0, ilj m иначе.

Подмножество G множества дифференциальных операторов называется замкнутым, если (l, m) Z2, G : xl ym () G Доказательство. Пусть V1, V2 Ч аффинные многообразия, соответствующие идеалам I1 и I2. В соответствии с [83, Теорема 2.8], каждой из точек (xi, yi) Vs, s = 1, 2 соответствует замкнутое множество Gi = Span(i1,..., isi ), такое что f Is ij (xi, yi )(f ) = 0, где (xi, yi)(f ) соответствует значению производной Хассе, задаваемой оператором, от функции f (x, y), вычисленной в точке (xi, yi). Тогда производящие функции идеалов могут быть представлены как Q(s) (x, y, z) = (j1,j2 ):D [j1,j2 ] Gi / (x xi )j1 (y yi )j2 Pij1 j2 (x, y, z), (xi, yi ) Vs, где Pij1 j2 (x, y, z) Ч некоторые многочлены, причем Pij1 j2 (xi, yi, z) = 0. Из взаимной простоты идеалов I1 и I2 следует, что если (xi, yi) V1, то Q(2) (xi, yi, z) = 0 и наоборот. Следовательно, Q(x, y, z) = (j1,j2 ):D [j1,j2 ] Gi / (x xi )j1 (y yi)j2 Pij1 j2 (x, y, z)Q(2) (x, y, z), (xi, yi) V1 (x xi )j1 (y yi)j2 Pij1 j2 (x, y, z)Q(1) (x, y, z), (xi, yi) V2, Q(x, y, z) = (j1,j2 ):D [j1,j2 ] Gi / причем Pij1 j2 (xi, yi, z)Q(2) (xi, yi, z) = 0, (xi, yi ) V1 и Pij1 j2 (xi, yi, z)Q(1) (xi, yi, z) = 0, (xi, yi) V2, т.е. кратность нулей идеала, полученного путем перемножения производящих функций, совпадает с кратностью соответствующих нулей сомножителей. Следовательно, (3.26) f I ((xi, yi ) V1 V2 )ij (xi, yi)(f ) = 0, ГЛАВА 3. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕДУРЫ ДЕКОДИРОВАНИЯ где дифференциальные операторы ij те же, что и для идеалов I1 и I2. Т.к. все пары (1) (2) Qi (x, y)Qj (x, y) принадлежат как I1, так и I2, для них выполняется условие (3.26), откуда следует их принадлежность I. Следовательно, I I. Обратное включение очевидно. Таким образом, задача вычисления произведения нульмерных взаимно простых идеалов сводится к задаче вычисления произведения двух многочленов, для решения которой было разработано большое число вычислительно эффективных алгоритмов. При этом необходимо отметить, что применение данного подхода не освобождает от необходимости использования алгоритма Бухбергера [167] для построения редуцированного базиса Гребнера идеала I. Но т.к. размерность базиса I, получаемого с помощью данного метода, оказывается существенное меньшей, чем в случае вычисления произведения идеалов по определению, можно ожидать существенного снижения сложности этого шага. Заметим, что данный метод позволяет параллельно построить базисные многочлены для различных интерполяционных точек, после чего УобъединитьФ результаты.

3.5 Выводы В данной главе были представлены новые алгоритмы решения вычислительных задач, возникающих при алгебраическом декодировании некоторых кодов (Рида-Соломона и т.п.), исправляющих ошибки, в частности: 1. Метод поиска корней многочленов над конечным полем, позволяющий снизить сложность соответствующего этапа декодирования кодов Рида-Соломона в 2Ц3,5 раза. 2. Метод вычисления быстрого преобразования Фурье над конечным полем (циклотомический алгоритм), обладающей наименьшей сложностью на длинах по крайней мере до 512. 3. Как часть циклотомического алгоритма БПФ, был получен метод построения разреженных фактор-графов линейных кодов, который может быть использован для быстрого умножения матрицы на вектор в полях характеристики два. 4. Метод вычисления синдромного многочлена при декодировании кодов РидаСоломона, обладающей наименьшей сложностью среди известных методов для кодов на длине по крайней мере до 512. 5. Следствием метода вычисления синдромного многочлена является метод построения разреженного фактор-графа кода Рида-Соломона. Необходимо отметить, что циклотомический алгоритм БПФ для умножения матрицы на вектор использует алгоритмически конструируемый разреженный фактор-граф, но, с другой стороны, он сам может быть использован для построения фактор-графа кода РидаСоломона.

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

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

4.1.1 Модель радиоканала со стационарными в широком смысле некоррелированными отражениями В ходе эксплуатации устройств мобильной радиосвязи достаточно часто возникает ситуация, при которой отсутствует прямой путь распространения радиосигнала от передатчика к приемнику. В результате многочисленных отражений, претерпеваемых сигналом на пути своего распространения приемник получает несколько искаженных копий переданного сигнала. Очевидно, что такая ситуация может быть описана как линейный Гауссовский канал с межсимвольной интерференцией, причем импульсный отклик канала равен [105] 1 h( ) = P P p= ej p ( p ), где p и p Ч фазовый сдвиг и задержка сигнала на пути p, а P Ч общее число путей. Формально допустим, что затухание сигнала при распространении по всем путям одинаково, но при этом допускается существование нескольких путей с одинаковой задержкой, за счет чего может быть получено неравномерное распределение мощности принимаемого сигнала во времени. Кроме того, предположим, что p и p, p = 1..P статистически независимы. В результате движения приемника характеристики канала изменяются, т.к. каждый из путей распространения испытывает независимый Доплеровский сдвиг fC v fDp = cos(p ), c ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ Таблица 4.1 Параметры модели Модель канала WSSUS Распределение мощности Экспоненциальное Полоса 20 МГц Число подканалов N 512 где p Ч угол относительно направления движения, под которым сигнал, прошедший по пути p, приходит к приемнику, fC Ч частота несущей, c Ч скорость распространения света в данной среде. Тогда меняющийся во времени импульсный отклик канала может быть представлен как P 1 ej p ej 2fDp t ( p ). h(t, ) = P p=1 Вычисляя преобразование Фурье от этого выражения, получим передаточную функцию канала P 1 H(t, f ) = ej p ej 2fDp t e j 2f p. P p=1 Заметим, что при большом количестве путей распространения сигнала сложение случайных величин, находящихся под знаком суммирования, приводит к нормально распределенным квадратурным компонентам передаточных коэффициентов H(t, f ), т.е. Релеевской модели. Для целей имитационного моделирования осуществляется генерация дискретизованных реализаций импульсного отклика канала. При этом можно предположить, что фазовые сдвиги сигнала на различных путях распространения распределены равномерно в интервале [0, 2), задержки сигнала на различных путях имеют усеченное экспоненциальное распределение p( ) = 1 eamax a ea, 0 < max в противном случае, Описанная модель носит название стационарного в широком смысле канала с некоррелированными рассеяниями (Wide Sense Stationary Uncorrelated Scattering) [105]. В таблице 4.1 представлены параметры модели, используемые в данной работе.

где a = 3 ln(10)/max, т.е. max соответствует затуханию на 30 дБ. Если направления прихода сигнала к приемнику равновероятны, то Доплеровские сдвиги на отдельных путях имеют распределение Джейкса 1, |fD | < fDmax 2 fD p(fD ) = fDmax 1 fDmax 0 иначе ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ Таблица 4.2 Параметры модели кабельного канала Параметр Удельное сопротивление кабеля, Ом/м Удельная индуктивность, Гн/м Удельная емкость, Ф/м Удельная проводимость изоляции, См/м Константа аппроксимации, См Константа аппроксимации, с1 Постоянная скин-эффекта, Ом/м/с1/2 Обозначение r L C g g d k Величина 0,0938 6,13E-7 5,6E-8 1E-10 1E-4 29E7 2,9E- 4.1.2 Модель кабельного канала на основе неэкранированной витой пары Кабельный канал на основе витой пары представляет собой классический пример электрической цепи с распределенными параметрами. Известно, что передаточная функция подобной цепи равна [157] (4.1) H(f ) = e (R+2 j f L)(G+2 j f C)l, где R, L, G, C Ч сопротивление, индуктивность кабеля, проводимость и емкость изоляции на единицу длины кабеля, а l Ч его длина. При высокоскоростной передач оказывается, что эти параметры зависят от частоты. Эта зависимость может быть приближенно представлена как [92, 148, 132] (4.2) R = r + k 2 j f f G = g + gd 22fj+d, (4.3) j где r сопротивление кабеля на метр длины по постоянному току, k Ч постоянная скинэффекта, g Ч проводимость изоляции на метр длины, gd, d Ч некоторые константы аппроксимации. Значения этих параметров, позволяющие получить хорошую аппроксимацию замеренной частотной характеристики канала, представлены в таблице 4.1.2.

4. Адаптивная передача в однопользовательской системе 4.2.1 Построение семейства многоуровневых кодов Для реализации адаптивной системы передачи данных необходимо наличие набора схем передачи, поддерживающих различные скорости. В разделе 1.4.6 были описаны правила построения многоуровневых кодов с любыми заданными скоростями. Их использование требует наличия семейства компонентных двоичных корректирующих кодов с различными скоростями, способных обеспечивать достаточно малую вероятность ошибки при ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ отношениях сигнал/шум, максимально приближенных к границе Шеннона. В настоящее время известны два основных класса кодов, удовлетворяющих последнему критерию: низкоплотностные коды и турбо-коды. Однако для турбо-кодов свойственен эффект УнасыщенияФ кривой вероятности ошибки при достаточно больших отношениях сигнал/шум. Кроме того, построение хороших высокоскоростных турбо-кодов является достаточно сложной задачей. В связи с этим представляется целесообразным использование низкоплотностных кодов. В данной работе используются два класса кодов: низкоплотностные коды, основанные на кодах Рида-Соломона (RSLDPC) [27] и PEG-коды [62]. Далее представлен анализ некоторых их свойств, необходимых для выбора параметров кодов. Рассмотрим задачу построения набора компонентных кодов для системы с адаптивным многоуровневым кодированием. В данном разделе не ставится задача построения какихлибо новых конструкций кодов;

интерес представляет лишь выбор значений параметров известных конструкций низкоплотностных кодов, позволяющих построить компонентные коды с большим диапазоном скоростей. Как было указано в разделе 1.4.4, основными параметрами низкоплотностных кодов являются их скорость, размерность проверочной матрицы, минимальное расстояние и распределение степеней узлов графа Таннера. Эти параметры определяют скорость передачи данных и качество декодирования. Основным показателем помехоустойчивости низкоплотностного кода при условии использования алгоритма декодирования Усумма-произведениеФ является пороговое значение дисперсии шума в аддитивном Гауссовском канале, при превышении которого вероятность ошибки итеративного декодира оказывается ограниченной снизу достаточно большой величиной, а в противном случае Ч стремится к нулю для кодов бесконечной длины. Благодаря графовой структуре низкоплотностных кодов оказывается возможным предсказать их поведение, не прибегая к трудоемким процедурам имитационного моделирования или оценки весового спектра. Известно, что большинство хороших низкоплотностных кодов имеет очень малый вес строк проверочной матрицы, что позволяет снизить вероятность искажения более чем одного символа из числа входящих в каждую проверку на четность. Однако вес строк влияет также и на максимальную достижимую скорость кода. Можно показать [130], что при использовании регулярных по строкам низкоплотностных кодов (т.е. (x) = xd1 ) бесконечной длины надежная передача данных возможна, только если скорость кода удовлетворяет 1 C() R 1, (4.4) h(e(d, )) где C() Ч пропускная способность канала с двоичной фазовой модуляцией при отношении сигнал/шум, h(x) = x log2 (x) (1 x) log2 (1 x) Ч функция двоичной энтропии, 1 e(d, ) = 2 1 (1 2Pe ())d, и Pe () = Q Ч вероятность ошибки до декодирования. 2 Эта граница представлена на рис. 4.1 для нескольких различных значений веса строк d. На этом же рисунке приведена кривая пропускной способности аддитивного Гауссовского канала с двоичной фазовой модуляцией. Видно, что при малых значения отношения сигнал/шум вес строк проверочной матрицы практически не оказывает влияния на верхнюю границу скорости1, но при увеличении отношения сигнал/шум вес строк также должен Однако это не означает, что характеристики кодов не зависят от веса строк.

ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ 0. 0.6 r 0. 0. отношение сигнал/шум 6 d=50 d=15 d=5 d= проп. способность Рис. 4.1 Верхняя граница скорости низкоплотностного кода RSLDPC(50,64,) codes 6 0.98 rate r 0.96 5.5 0.94 0.92 5 Eb/N0, dB 0.9 0.88 4.5 R 0.86 0.84 0.82 3.5 0.8 0.78 3 0.76 0.76 0.78 0.8 0.82 0.84 0.86 R 0.88 0.9 0.92 0.94 0.96 0.98 0 10 20 30 RSLDPC(50,64,) codes (a) Пороговое ОСШ на бит (b) Скорость кода расти. В [116] было показано, что уменьшение веса строк увеличивает число исправимых ошибок в случае двоичного симметричного канала2. В связи с этим целесообразно рассматривать низкоскоростные коды с малыми весами строк и высокоскоростные коды с большими весами строк. Данное правило достаточно хорошо согласуется со свойствами низкоплотностных кодов, используемых в данной работе. Рассмотрим свойства этих кодов более подробно. Рисунок 4.2(a) иллюстрирует зависимость порогового значения отношения сигнал/шум на бит от скорости кода из семейства RSLDPC. Можно заметить, что в высокоскоростном диапазоне оно быстро уменьшается с уменьшением скорости кода. В диапазоне скоростей 0.8 < r < 0.9 зависимость от скорости кода практически исчезает, а при 0.78 < r < 0.8 наблюдается ее резкое увеличение. Последнее связано с тем, что число проверок на четность3, необходимое для достижения соответствующей скорости, оказывается чрезвычай2 Необходимо отметить, что рассматриваются абсолютные значения веса строк. Общее число проверок на четность в RSLDP C(, q, )-коде равно q.

ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ Asymptotic threshold for PEG codes 4.5 4 3.5 3 Threshold Eb/N0, dB 2.5 2 1.5 1 0.5 0 -0.5 0 0.1 0.2 0.3 0.4 0.5 Code rate r 0.6 0.7 0.8 0. Рис. 4.2: Асимптотическое поведение оптимизированных нерегулярных низкоплотностных кодов но большим (см. рис. 4.2(b)), что существенно увеличивает сложность декодирования. На рисунке 4.2 представлен аналогичный график, построенный для оптимизированных ансамблей нерегулярных низкоплотностных кодов;

соответствующие распределения степеней узлов приведены в таблице 4.3 на стр. 118. Видно, что на всем диапазоне скоростей пороговое значение отношения сигнал/шум на бит для оптимизированных кодов существенно ниже, чем в случае регулярных RSLDPC кодов. Однако необходимо учесть, что существующие методы построения нерегулярных кодов не позволяют получить хорошие высокоскоростные коды умеренной длины. В связи с этим целесообразно использовать алгебраические RSLDPC-коды в диапазоне скоростей, соответствующем умеренной избыточности (т.е. числу линейно зависимых строк) проверочной матрицы (в данном случае r > 0.8), и нерегулярные коды при r 0.8. При этом для построения нерегулярных кодов может быть использована, например, процедура PEG. В настоящее время отсутствуют конструктивные способы аналитического построения кривой вероятности ошибки декодирования в зависимости от отношения сигнал/шум для конкретного кода конечной длины. В связи с этим возникает необходимость построения таких кривых для выбранного семейства кодов путем имитационного моделирования. Было замечено [81], что кривая вероятности ошибки итеративного декодирования низкоплотностных кодов может быть аппроксимирована функцией p() = a, (1 + eb(c) )d (4.5) где Ч отношение сигнал/шум, а a, b, c, d Ч параметры аппроксимации. Эта функция может рассматриваться как Усглаженный минимумФ некоторой константы p0 = a, характеризующей вероятность ошибки при малых отношениях сигнал/шум4 и функцией e, фигурирующей в приближенной объединенной верхней границе [172]. Заметим, что т.к.

Известно [111], что при малых отношениях сигнал шум вероятность ошибки итеративного декодирования ограничена снизу положительной величиной ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ последняя включает в себя сумму экспонент с различными показателями, выражение (4.5) не всегда обеспечивает адекватную аппроксимацию истинной вероятности ошибки;

например, может не учитываться эффект насыщения, наблюдаемый для некоторых кодов при больших отношениях сигнал/шум. Но т.к. при построении практических систем связи целесообразно выбирать коды, для которых эффект насыщения наступает на пренебрежимо малых вероятностях ошибки, применение аппроксимации (4.5) вполне адекватно. После построения набора кривых pi (), где i Ч номер кода, для каждого i (и соответствующего ему значению скорости кода ri ) может быть вычислено отношение канал/шум5 i, необходимое для обеспечения заданной вероятности ошибки, что позволяет построить функцию спектральной эффективности семейства кодов r(). Было установлено, что эта кривая может быть хорошо аппроксимирована функцией вида R() = C() (1 C())eC() 2 +, (4.6) где C() - пропускная способность канала с двоичной модуляцией при отношении сигнал/шум, а, Ч параметры аппроксимации, которые могут быть найдены, например, с помощью метода наименьших квадратов. Это дает возможность вычислить значение скорости кода R(C) на основе пропускной способности канала C. Для обеспечения передачи данных может быть использован код из данного семейства с наибольшей скоростью, не превосходящей R(C). В таблице 4.3 представлены распределения степеней символьных узлов низкоплотностных кодов, использованных при построении рассматриваемого далее семейства многоуровневых кодов. Для кодов со скоростью r 0.8 проверочные матрицы были построены с помощью алгоритма PEG. Для r > 0.8 использовалась конструкция RSLDPC. Распределения степеней узлов, представленные в таблице 4.3, не являются асимптотически наилучшими;

асимптотический порог итеративного декодирования thr может быть несколько улучшен путем увеличения максимальной степени символьных узлов. Однако при построении кодов конечной длины с помощью алгоритма PEG наличие символьных узлов высокой степени приводит к образованию коротких циклов в графе Таннера, что может привести к уменьшению минимального расстояния кода и возникновению эффекта насыщения кривой вероятности ошибки. Значения, приведенные в таблице 4.3, представляют собой компромисс между хорошим асимптотическим поведением кода и ограничениями, накладываемыми конечностью длины кода. Рисунок 4.3(a) иллюстрирует кривые вероятности ошибки для кодов с различными скоростями r из рассматриваемого семейства, полученные путем имитационного моделирования, а также приближенные кривые (4.5), полученные путем подбора коэффициентов методом наименьших квадратов. Рисунок 4.3(b) иллюстрирует спектральную эффективность семейства кодов, т.е. максимальную скорость кода, позволяющую осуществлять передачу данных с заданной вероятностью ошибки. На этом же рисунке представлены кривые пропускной способности канала и асимптотического порога итеративного декодирования (см. таблицу 4.3). Негладкое поведение кривой асимптотического порога декодирования вблизи точки r = 0.85 связано с переходом к регулярным RSLDPC кодам. Можно Т.к. здесь коэффициент усиления передаваемого сигнала предполагается равным единице, отношения сигнал/шум и канал/шум совпадают.

ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ Таблица 4.3: Распределения степеней символьных узлов используемых низкоплотностных кодов Скорость 0.05 (x) 0.7417x1 +0.1545x2 +0.01814x3 +0.01186x4 + 0.04544x5 +0.01004x6 +0.009352x12 +0.004843 x17 + 0.001053x19 + 0.001536x20 + 0.001364x21 0.659 x1 + 0.1942 x2 + 0.01032 x3 + 0.05913 x4 + 0.05837 x7 + 0.01886 x24 0.6143x1 +0.231x2 +9.1941105 x3 +0.008891 x4 + 0.06609 x5 + 0.04498 x6 + 0.003214 x9 + 0.004953 x13 + 0.02636 x20 0.5357 x1 + 0.2538 x2 + 0.04059 x4 + 0.07154 x5 + 0.02591 x9 + 0.04435 x10 + 0.002382 x11 + 0.02564 x49 0.4345 x1 + 0.3907 x2 + 0.0683 x3 + 0.02216 x5 + 0.02765 x8 + 0.04597 x9 + 0.01059 x10 0.4898 x1 + 0.2706 x2 + 0.00055 x3 + 0.1378 x4 + 0.1011 x14 0.4618 x1 + 0.3173 x2 + 0.1346 x5 + 0.01369 x11 + 0.07242 x12 0.4231 x1 + 0.3262 x2 + 0.02313 x4 + 0.128 x5 + 0.09939 x14 0.4366 x1 + 0.345 x2 + 0.2183 x4 x9 x8 x7 x6 x5 x4 x3 x2 Средний вес строки 3 Пороговое значение thr 3. 0.1 0. 3.5 4. 2.55535 1. 0. 6. 1. 0.4 0.5 0.6 0.7 0.8 0.85 0.86 0.87 0.885 0.898 0.91 0.92 0. 5.5 5.5 10 14 15 50 50 50 50 50 50 50 1.10267 0.964619 0.828411 0.720552 0.596579 0.509595 0.505344 0.500378 0.494335 0.486903 0.477054 0.463035 0. ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ 1 Simulated, r=0.1 Approximated, r=0.1 Simulated, r=0.6 Approximated, r=0.6 Simulated, r=0.3 Approximated, r=0.3 проп. способность LDPC threshold Spectral efficiency S.E. approximation 0. 0. вероятность ошибки на бит 0. 0.001 r 0. 0. 0. 1e-005 0.2 1e- 1e-007 0 0.2 0.4 0.6 0. 1. 1. 1. 1. 0. 1. 2. 3. 4. (a) Вероятность ошибки (b) Спектральная эффективность Рис. 4.3 Характеристики семейства низкоплотностных кодов заметить, что эта эмпирическая кривая достаточно близка по форме кривой пропускной способности C() и хорошо аппроксимируется функцией (4.6). На рисунке 4.4 представлена кривая спектральной эффективности набора многоуровневых кодов, полученных на основе описанного семейства низкоплотностных кодов. В качестве базовых использовались сигнальные множества 2l -уровневой импульсно-амплитудной модуляции. Видно, что эта кривая может быть получена сдвигом кривой пропускной способности канала, т.е. может быть охарактеризована некоторым УзазоромФ.

4.2.2 Адаптивное многоуровневое кодирование На рисунке 4.5(a) представлен график спектральной эффективности адаптивной многочастотной системы, использующей оптимизационный алгоритм, описанный в разделе 2.1.3, для случая канала с независимыми Релеевскими коэффициентами затухания. Можно заметить, что в адаптивной системе сохраняется УзазорФ в 3 дБ, наблюдавшийся в исходном наборе многоуровневых кодов (см. рисунок 4.4). Кроме того, увеличение размера группы L приводит к крайне незначительному увеличению мощности передатчика, требуемой для обеспечения заданного качества работы системы. Рисунок 4.6 иллюстрирует зависимость качества оптимизации от числа J используемых многоуровневых кодов. Видно, что увеличение их числа с 12 до 82 позволяет снизить мощность передатчика, требуемую для достижения заданных параметров системы, примерно на 2 дБ. При этом необходимо отметить, что сложность реализации системы в основном определяется числом используемых компонентных (бинарных) кодов. Предложенный в данной работе прагматический способ построения семейства многоуровневых кодов позволяет построить большое число кодов на основе сравнительно небольшого семейства компонентных двоичных кодов. На рисунке 4.5(b) представлен аналогичный график для случая кабельного канала. Видно, что кабельный канал допускает использование существенно большего размера группы подканалов. Однако ввиду сильного затухания высокочастотных сигналов дости ад ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ P0=1E-7 проп. способность аппроксимация спектральная эффективность, бит/с/Гц l=1 l=2 l=3 l=4 l= 0 - - 10 15 Es/N0, dB Рис. 4.4 Спектральная эффективность семейства многоуровневых кодов независимые релеевские замирания, 512 подканалов 8 кабельный канал UTP5, 2048 подканалов L=1 L=2 L=4 L=8 L=16 L=32 L= проп. способность 7 1. проп. способность L=1 L=2 L=4 L=8 L=16 L=32 L=64 L=128 L= спектральная эффективность, бит/с/Гц 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0 - скорость, бит/OFDM символ 0 - - - - относительная мощность передатчика, дБ относительная мощность передатчика, дБ (a) Канал с независимым Релеевским затуханием (b) Кабельный канал Рис. 4.5: Спектральная эффективность системы с адаптивным многоуровневым кодированием ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ L=1, P0=1E-7 8 J=82 J=54 J=24 J= спектральная эффективность, бит/с/Гц 0 - - - относительная мощность передатчика, дБ Рис. 4.6 Влияние числа используемых многоуровневых кодов на качество адаптации WSSUS канал, полоса 20 МГц, 512 подканалов, скорость 3.9 бит/с/Гц проп. способность (модел.) проп. способность (анал.) L=1 L= адаптивная система (анал.) относительная мощность передатчика, дБ 13 0 1e-006 2e-006 3e-006 4e-006 5e-006 6e-006 7e-006 8e-006 9e-006 1e-005 1.1e- многопутевое рассеяние max, с Рис. 4.7 Показатели качества адаптивной однопользовательской системы жимая спектральная эффективность оказывается существенно меньше, чем в случае канала с независимыми Релеевскими затуханиями На рисунке 4.7 представлены кривые, иллюстрирующие зависимость мощности передатчика, требуемой для обеспечения заданной скорости, от условий распространения сигнала в стационарном радиоканале с независимыми отражениями (WSSUS). Видно, что c ростом величины максимальной задержки сигнала (т.е. с увеличением частотной селективности канала) потери, связанные с использованием группового кодирования, увеличиваются. Кроме того, увеличение частотной селективности канала приводит к снижению мощности, требуемой для достижения заданной пропукной способности канала. Необходимо также отметить, что предложенный метод анализа характеристик адаптивной системы позволяет дает результаты, достаточно близкие к результатам, полученным с помощью имитационного моделирования.

ПРИМЕНЕНИЕ АДАПТИВНЫХ МЕТОДОВ независимые релеевские замирания, 512 подканалов 9 8 спектральная эффективность, бит/с/Гц проп. способность (анал.) проп. способность (модел.) адаптивная система (анал.) адаптивная система (модел.) 6 5 4 3 2 1 0 - - - относительная мощность передатчика, дБ Рис. 4.8 Теоретическая оценка спектральной эффективности Полученные результаты интересно сопоставить с теоретическими оценками, построенными в п. 2.1.4. На рисунке 4.8 представлены кривые для спектральной эффективности адаптивной системы, функционирующей в условиях канала с независимыми Релеевскими замираниями. Можно заметить, что кривая для пропускной способности канала, полученная с помощью выражений (2.16) и (2.17) при = 1, в точности совпадает с кривой, полученной усреднением по большому числу реализаций канала, что подтверждает адекватность использованного метода построения оценки. Кривая для спектральной эффективности рассматриваемой системы точно совпадает с теоретической оценкой в диапазоне отношений сигнал/шум до 15 дБ и начинает незначительно отклоняться от нее при более высоких его значениях. Это связано с наличием ограничения на максимальное число уровней в используемом семействе многоуровневых кодов. Таким образом, можно утверждать, что предложенный метод адаптивного многоуровневого кодирования близок к оптимальному.

Pages:     | 1 | 2 | 3 |    Книги, научные публикации