Диссертация (1143626), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

3.8 представлена структурная схема вычисления Ak(i).Гk(l1, i)Ak-1(l1)Ak-1(l2)++Гk(l2, i)КомпараторMaxAk(i)Рис. 3.8. Структурная схема вычисления Max-Log алгоритмаАналогично, если обозначаем Bk(j) = log(βk(j)), то значение βk(j) в логарифмическом масштабе вычисляется по следующей формулеBk ( j )   exp  Bk 1 (l )   k 1 ( k , l ) ,(3.21)lТогда приближенное значение Bk(i) вычисляется такBk (i )  log   exp  Bk 1 (l )   k 1 (k , l )    max  Bk 1 (l )   k 1 (l , i )  .l l(3.22)Таким образом, формулу для вычисления логарифма отношения вероятностей LLR в (3.16) можно переписать так59 k  i, j  exp  Ak  i    k  i, j   Bk  j    (i , j ) (Ck 1) ( i , j ) (Ck 1)LLRk  log  log  k  i, j  exp  Ak  i    k  i, j   Bk  j    ( i , j ) ( Ck  0) (i , j ) (Ck 0)с учётом (3.17) следует, что:LLRk max( i , j ) Ck 1 A  i     i, j   B  j  kmax( i , j ) Ck 0kk A  i     i, j   B  j   ,kk(3.23)kРассмотренный алгоритм, получивший название Max-Log-BCJR, позволяетзаменить операцию умножения сложением, а экспоненту и логарифм простымнахождением максимума.3.3.

Сферичный алгоритмОтсчёты принятого сигнала могут быть записаны в матричном видеY  AC ,(3.24)где:• Y   y0 , y1 , ..., yL  K  2  – вектор формирующего сигналаT a0 a 1 ... aL1• A 0 ... 0 0 ... 00...a0...00...00...0... 0... ...0 ...... ...0...0...... 0... ...aL 2 ... a1aL 1 ... a2a0 ...a1 ...0000......00...0... ...... 0... ... ...0 ... a L1...a 20...0... 0... ...... 00 ...... ...0 ...aL1 ... a2... ... ...0 ... 00...0... ...... a100...

00  – формирующая... a0 a1 ... a0 матрица с размерами (K + L – 1)*K.• C = [C0, C1, …, CK – 1]T – вектор переданных символов.Очевидно, что формирующий сигнал получается выбором конечного числаточек из K-мерной решётки в евклидовом пространстве ZK. Процедура максимально правдоподобного декодирования эквивалентна нахождению ближайшей60точки решетки к точке принятого сигнала. Такое нахождение эквивалентно минимизации следующей метрики:2minY  AC ,ˆ KCZ(3.25)dРис. 3.9. Идея сферичного алгоритмаСферичный алгоритм (англ. Sphere Algorithm) реализует критерий максимального правдоподобия оценки всей последовательности переданных символов[28]. Реализация данного алгоритма сводится к проверке точек решётки, которыенаходятся внутри сферы c заданным радиусом d и центром в точке принятогосигнала для уменьшения сложности декодирования.

Геометрическое представление данного алгоритма изображено на рис. 3.9. Точка решётки находитсявнутри сферы если удовлетворяет следующему условию2d 2  Y  AC ,(3.26)Для упрощения вычисления, предлагали использовать следующее QR – разложениеA  QR ,(3.27)где: r0,0 r0,10 r1,1• R ... ...0 0r0,K 1 ... r1,K 1  – верхняя треугольная матрица с размером K*K,...... ... rK 1,K 1 ...61• Q = [Q1 Q2] – ортогональная матрица с размером (K + L – 1)*(K + L – 1);Q1 – матрицасразмером(K + L – 1)*K,Q2 – матрицасразмером(K + L – 1)*(L – 1).Из (3.26) получается22 Q1* ˆˆ  Q*Y  RCˆ  Q* Y 2 ,d  Y  [Q1 Q 2 ]RC   *  Y  RC12Q 2 22(3.28) – эрмитово-сопряженная матрица.где ()*22d 2  Q*2 Y  Q1*Y  RC ,(3.29)2Обозначим z  Q1*Y и d 2  d 2  Q*2 Y . Тогда неравенство (3.29) можетбыть представлено в таком видеK 1K 1i 0j id 2   ( zi   ri , jC j )2 ,(3.30)где ri,j – элемент матрицы R с индексом (i, j).Напомним, что матрица R является верхней треугольной.

Поэтому, праваячасть неравенства (3.30) может быть записана следующим образомd2  ( zK1  rK1,K1CK 1)2  (zK 2  rK2,K1CK1  rK2,K2CK 2 )2  ... ,(3.31)Заметим, что первое слагаемое этого неравенства зависит только от CK 1 ,второе слагаемое зависит от {CK – 1, CK – 2} и так далее. Таким образом, необходимым условием, чтобы точки решётки находились внутри сферы с радиусом d,являетсяd 2  ( z K 1  rK 1,K 1CK 1 ) 2Отсюда, получаем d   zK 1  d   zK 1  CK 1  ,rK 1, K 1r K 1, K 1 (3.32)где  ,  – округление вверх, вниз (соответственно) до ближайшего элементарешётки.62Для каждого значения CK 1 , которое удовлетворяет условию (3.32), обозначаем d K22  d 2  ( zK 1  rK 1,K 1 ) 2 и zK–2,K–1 = zK – 2 – rK – 2,K – 1CK – 1. Неравенство(3.31) приводит к условию для CK – 2 d K  2  zK  2,K 1  d K 2  z K 2,K 1 C,K 2rrK2,K2K2,K2(3.33)Разумный выбор d позволяет значительно ускорить декодирование благодаря необходимости проверки малого числа точек решётки.

Однако, если выбирается слишком маленькое значение d, то в сфере может не оказаться ни однойточки решётки. Практически значение d выбирают по тому или иному алгоритмуна основании значения отношения сигнал/шум. Если при этом в сфере не находится ни одна точка, то значение d увеличивается и процесс декодирования повторяется. Анализ вычислительной сложности сферичного алгоритма представлен в [29], где также предложен алгоритм выбора начального значения d.3.4.

Подоптимальный алгоритмКак сказано выше, при увеличении глубины МСИ (т.е. при увеличении L)и/или увеличении размера сигнального созвездия MC, количество состояний в решётке увеличивается по закону MCL – 1, что приводит к значительному увеличению вычислительной сложности алгоритма Витерби и BCJR. Для уменьшенияколичества вычислений предлагали использовать подоптимальные алгоритмы – М-Витерби [30], М-BCJR [31].M-Витерби алгоритмСуть M-Витерби алгоритма состоит в том, что на каждом шаге в памяти алгоритма сохраняются только M состояний с наименьшими метриками, в то времякак в алгоритме Витерби количество сохраняемых путей равно количеству состояний в решётке [30].

На рис. 3.10 представлена основная идея M-Витерби алгоритма.63MC штукВитербиM-Витерби...Состояние..................M штук...(а)...(б)(в)Рис. 3.10. М-Витерби алгоритмВ процессе работы алгоритма Витерби, для каждого последующего состояния рассчитываются метрики путей, которые сходятся в это состояние, количество таких путей равно размерности сигнального созвездия т.е. MС, как представлено на рис. 3.10 (а). Для каждого состояния сохраняется только один путь с лучшей метрикой, выделенный жирным. Такой путь называют выжившим.

В традиционном алгоритме Витерби количество путей в памяти всегда равно количествусостояний МС (рис. 3.10 (б)). В алгоритме М-Витерби сохраняются только М путей (рис. 3.10 (в)), имеющих лучшие метрики. В результате, такой алгоритм требует меньший объем памяти и имеет меньшую сложность, так как на следующемшаге будут рассматриваться только переходы из M состояний.M-BCJR алгоритмВ [31–32] предложили модифицированный алгоритм BCJR, в котором рассчитываются и сохраняются не все пути решётки, а только M из всех возможных.Такой подход получил название «M-BCJR». Как сказано в параграфе 3.2, в прямом проходе производится расчёт αk(i) для всех состояний, а в обратном проходе – βk(i), где: i – индекс состояния, k – индекс тактового интервала. В алгоритме M-BCJR предлагается сохранять только M путей на каждом шаге прямойрекурсии, имеющих наибольшие значения αk(i).

В обратной рекурсии, вычисления βk(i) производятся по двумя способам: первый – по путям, выжившим в прямой рекурсии, а второй – в независимости от прямой рекурсии, т.е. на каждомшаге в памяти сохраняются M путей с наибольшими значениями βk(i).64На рис. 3.11 представлена решётчатая диаграмма алгоритма M-BCJR, M = 2для L = 3 и MC = 2. Из рисунка видно, что количество сохраняемых путей в памяти равно двум. Недостатком первого способа является, что старт вычисленияв обратной рекурсии начинается только после совершения вычисления в прямойрекурсии. Однако в обратной рекурсии также необходимо выделять память длясохранения выживших путей и также метрик.x00Состояние(0)x2x1x3x4x5x6(1)(2)(3)1k=032465Рис.

3.11. Решётчатая диаграмма для вычисления α в прямом проходе для алгоритма M-BCJRВ втором подходе, расчёт αk(i), βk(i) происходит одновременно и независимодруг от друга, при этом не требуется сохранения выживших путей.(0)x00x2x1x3x4x5x6x7x8(1)Состояние(2)(3)(4)(5)(6)(7)k=012345678Рис. 3.12.

Решётчатая диаграмма для L = 5, MC = 2.Исследование показало, что независимое вычисление в прямой и обратнойрекурсиях приводит к ухудшению помехоустойчивости по сравнению с первымспособом. На рис. 3.12 представлена решётчатая диаграмма для вычисления αk(i)и βk(i) в независимости друг от друга. Отмеченные синие пути соответствуют65прямому проходу, зелёные пути соответствуют обратному проходу. Отмеченныекрасные ребра с двунаправленными стрелками означают существование перехода между сохраняемыми состояниями в прямом и обратном проходах. На таких тактовых интервалах возможно вычислять вероятность переданных символов.

На тактовых интервалах 2T, 3T, 4T на этом рисунке видно, что не существуетперехода между состояниями. При таких ситуациях переданному символу присвоится некое определённое значение, что приводит к увеличению ошибочнойвероятности приёма. Исследование показало, что проигрыш в этом случае не менее 10 дБ по сравнению с первым способом.Таблица 3.1АлгоритмВычислительная сложность обработки одного тактаВитербиO((N + L – 1)NS)BCJRO(2(N + L – 1)NS)M-ВитербиO((N + L – 1)M)М-BCJRO(2(N + L – 1)M)В табл.

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

Характеристики

Список файлов диссертации