Вопросы по итеративному декодированию, Реализация CTC/BTC/LDPC кодов Опции

[des00]

Добрый день!

Наконец то появилось время подтянуть себя в вопросах реализации кодов с вероятностным декодированием. Первая задача реализация DVB-RCS/WiMAX CTC кодера на ПЛИС, часть проекта будет выложен в опенсорс. Решил создать отдельную тему для обсуждения вопросов по реализации

После штудирования литературы и примеров сорцов в сети возникла часть вопросов, на которые не хватает ума/настойчивости найти ответы:
1. Для DVB-RCS оговорены выкалывания под скорости кодирования 1/3, 2/5, 1/2, 2/3, 3/4, 4/5, 6/7. Почему не определены скорости 5/6 (удивляет "дырка" между скоростями 4/5 и 6/7) и 7/8? При этому матрица выкалывания под эти скорости возможна.
2. Полиномы RCS для Wimax и DVB одинаковые, но перемежители разные. Это сделано по политическим причинам или это результат "улучшения" характеристик декодера в процессе разработки стандарта?
3. В сверточных бинарных кодах, свойство tail-bitting используется при декодировании: В одной доке нашел что дополняют принятую последовательность вначале и в конце, затем декодируют по витерби и выкусывают нужное. В примере матлаба вообще составляют два фрейма, декодируют один за другим, потом из двух декодированных собирают один результат. Никакого намека на похожие операции в доках на турбокоды не нашел. Почему в алгоритмах SOVA/MAP/... для турбокодов это не делается?
4. По tail-bitting нашел в доках только то, что особым образом инициализируются рекурсия прямой и обратной метрики на первой итерации, а на всех остальных значения между итерациями сохраняются. Но
в сорцах от CML цикл по итерациям выглядит так :

Код

for it = 1:max_iterations
    inx1 = X + inner_extr;
    [outx1, outz1]=DuobinaryCRSCDecode( inx1, inz1, poly, decoder_type);
    
    llrx1 = outx1 - inner_extr;
    inx2(1:3*N) = llrx1( code_interleaver_GF4);
    [outx2, outz2, out_info]=DuobinaryCRSCDecode( inx2, inz2, poly, decoder_type);
    detected_data(code_interleaver.info_intl) = (out_info>0)+0;
    errors(it)= sum( sum(abs(detected_data - data)));
    if (errors(it) == 0)
        break;
    else
        inner_extr(code_interleaver_GF4) = outx2 - inx2;
    end
end

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

Код

    // initialization  for CRSC code
    for (i =0; i< max_states; i++)
    {
        alpha[i][0] = 0;
        beta[i][len] = 0;
    }

Т.е. не используется даже свойство одинакового начального состояния. Более того, в алгоритмах с оконным расчетом обратной рекурсии тоже забивают на свойство tail-bitting. Так насколько это важно и почему во всех доках настойчиво пишут кодировать данные 2 раза для определения состояния инициализации?
5. В алгоритмах, наследованных от Log-MAP метрика ветки считается как сумма корреляций метрик приемных битов с выходными битами решетки : gamma(Sk-1, S) = Lapri + (ys0*xs0 + ys1*xs1 + yp0*xp0 + yp1*xp1). При этом предполагается что y - надежность принятого символа , x = -1/1 выходной(переданный) бит. В сорцах от CML это место выглядит так :

Код

    int m_input = 2;  // 2 input bits,
    int max_states = 8; // total state numbers
    int M_input = 1<<m_input;
    int i, j, max_trellis = M_input * max_states;
.......
        for (j = 0; j< max_trellis; j++)
        {
            temp_input = j%M_input;
            temp_output = trellis_out[j];
            gamma[j] = ( temp_input ==0)? 0: inx[ (temp_input -1)+ i*llr_height ];   //llr for systematic symbol
            gamma[j] += ( temp_output ==0)? 0: inz[ (temp_output -1)+ i*llr_height ];  //llr for parity symbol
        }

Насколько я понимаю Си gamma[j] = ( temp_input ==0)? 0: inx[ (temp_input -1)+ i*llr_height ] - берет надежности символов кроме нулевого. Диапазон изменения temp_input = 0..3 или в битах 00/01/10/11. Вот этот момент мне совсем не понятен.

Пока всё Прошу помощи тех кто в теме.

[des00]

1. Для DVB-RCS оговорены выкалывания под скорости кодирования 1/3, 2/5, 1/2, 2/3, 3/4, 4/5, 6/7. Почему не определены скорости 5/6 (удивляет "дырка" между скоростями 4/5 и 6/7) и 7/8? При этому матрица выкалывания под эти скорости возможна.

Вероятно, кривая BER для 5/6 лежит слишком близко к кривым 4/5 и 6/7, поэтому в этой скорости нет смысла, если используется адаптивная модуляция-кодирование. Это только догадка, которую стоит проверить, если ответ интересен.

ларчик просто открывался. В DVB размеры фреймов сильно не кратны скоростям 5/6 и 7/8. Выкалывание скоростей 1/2, 2/3 и 4/5 хорошо ложится на размеры фреймов, выкалывания 3/4 и 6/7 требуют 3-х фреймов для выравнивания, а 5/6 требует уже 15. Похоже просто убрали скорость, чтобы не заморачиваться В этом вопросе WiMax гибче, у него количество фреймов разной длинны больше

[Dr.Alex]

.

[des00]

Возник вопрос по поводу расчета LLR канальных символов. Изучил другие темы на форуме и доку от AHA, все понятно и обосновано. Вопрос возник вот в каком моменте: посмотрел реализации других декодеров софтовых/хардварных. Одни предлагают подавать на вход квантованные LLR, другие квантованные канальные символы (например для QAM16 - 2 бита целая часть, 4 бита дробная).

Насколько я понимаю при декодировании речь может идти только о квантовании LLR, а по каким канальным символам она была вычислена, личное дело того кто использует декодер. Канальные символы квантуют что бы уменьшить требования к аппаратуре/памяти. Правильно ли это, или есть какой-то другой тайный смысл ?

Есть еще такой вопрос: рассмотрим нормированное созвездие QAM16. Возьмем угловую точку '00' 0.75 + 0.75i. В этом случае, канальный символ 0.99+0.99i будет трактован как очень надежный символ '00'. А как правильно, трактовать канальный символ 1.5 + 1.5i, т.е. выход точки за пределы нормировки созвездия (например на АРУ), который может возникнуть, ну положим, из-за импульсной помехи? Ведь для стационарного AWGN канала это нештатная ситуация и точка не может быть очень надежной и ее желательно "стереть". Или это уже из области, отличной от декодеров в AWGN канале?

[andyp]

Насколько я понимаю при декодировании речь может идти только о квантовании LLR, а по каким канальным символам она была вычислена, личное дело того кто использует декодер. Канальные символы квантуют что бы уменьшить требования к аппаратуре/памяти. Правильно ли это, или есть какой-то другой тайный смысл ?

Алгоритм BCJR, используемый при декодировании, работает в терминах вероятностей перехода из состояния в состояние по решетке, описывающей код. Его логарифмическая версия, требующая меньше вычислений, работает в терминах логарифмов этих вероятностей. Если говорить о дальнейшем упрощении (MAXLOGMAP), то добавление (вычитание) любой величины к логарифму вероятностей перехода по решетке ничего не меняет. Умножение всех логарифмов на константу изменяет в то же число раз рассчитанные LLR кодированных бит на выходе. Это (возможность вычитания) позволяет использовать LLR вместо логарифмов вероятностей переходов, поэтому декодер кушает LLR кодированных бит, из которых легко получить LLR переходов в решетке. Фиксированная разрядность имеет смысл только для практики, но не для теории. Также можно отметить еще одну штуку: из LLR легко получить логарифмы вероятностей отдельных бит. Легко показать, что если p(0) + p(1) = 1; LLR = log(p(1)/p(0)), то:
log(p(1)) = log(exp(LLR)/(exp(LLR)+1)); log(p(0)) = log(1/(exp(LLR)+1))

Есть еще такой вопрос: рассмотрим нормированное созвездие QAM16. Возьмем угловую точку '00' 0.75 + 0.75i. В этом случае, канальный символ 0.99+0.99i будет трактован как очень надежный символ '00'. А как правильно, трактовать канальный символ 1.5 + 1.5i, т.е. выход точки за пределы нормировки созвездия (например на АРУ), который может возникнуть, ну положим, из-за импульсной помехи? Ведь для стационарного AWGN канала это нештатная ситуация и точка не может быть очень надежной и ее желательно "стереть". Или это уже из области, отличной от декодеров в AWGN канале?

Про рассчет LLR отдельных бит на выходе демодулятора писал здесь:
http://electronix.ru/forum/index.php?showt...t&p=1270246

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

Я обычно ограничиваю макс. значение в квадратурах уровнем max+d - max - макс. значение квадратуры созвездия, d - расстояние до ближайшей соседней от d точки. Т.е. Пусть имеем QAM16 - макс. по квадратуре 3, расстояние до ближайшей точки 2. Ограничиваю квадратуры на входе демаппера по уровню +/- 5.

[Maverick]

Прошу прощения, что влажу в чужую тему, но вопрос по теме вроде ...

Из того, что я находил, то декодирование блочных кодов по МАР-алгоритму (мягкое решение) лучше всего расписано в приложенном документе (стр. 9-11) и у Moon'а (стр. 663). Но там все также предполагается построение решетки на основе входного символа. В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном). + Там интересный вывод окончательной формулы для вычислений (выражение 63).
Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается...

Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже.

Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...

Прикрепленные файлы

 hagenauer.pdf ( 2.25 мегабайт ) Кол-во скачиваний: 92

 

[andyp]

В приложении есть подраздел, в котором указывается, насчет построения решетки и насчет 2 конечных состояний - этот момент я пока не понимаю (даже несмотря на то, что есть рисунок - вопросы именно по этим 2 состояниям в основном).

Глубоко копаешь .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке Lin Costello Error Control Coding Fundamentals and Applications (только 2е издание). Скачать ее можно здесь
http://bookzz.org/md5/8032998F071B09E087B9E8D81E7FFC1F
Тебе потребуется глава 9, а именно секция 9.5. Но хочу предупредить сразу - чтение не из легких.
Если кратко, получается, что код представляется (n+1)-секционной решеткой, метки ветвей соответствуют закодированным битам, метки состояний - линейная комбинация столбцов проверочной матрицы и кодовых бит, по которым пришли в это состояние. Очевидно, что n-ое состояние решетки будет единственным и будет состоять из (n-k) нулей по свойству проверочной матрицы. 0-е состояние - тоже 0. Из него начинаем.

Идем дальше. Рассмотрим кодовые слова кода, из которых вырезали к-ий бит. Предположим, что они все у нас есть (так проще) и будем строить решетку для них по тем же правилам, используя все столбцы проверочной матрицы оригинального кода, кроме к-го. В результате получим n-секционную решетку, начинающуюся в 0, и имеющую два хвоста. Почему хвостов 2? Да потому, что если в невыколотом кодовом слове в к-ой позиции был 0, то придем в нулевое состояние, если выколота была единица, то получим состояние, равное выколотому столбцу проверочной матрицы. Других вариантов нет. Именно про такую решетку пишут в статье.

Может мне кто-то пояснить и как быть если блок например 128х128 - количество решеток ооочень большое получается...

Чейз (2 вариант/алгоритм) в этом плане как-то по проще(понятней что-ли), но исправляющая способность у него ниже.

Именно поэтому чистый MAP для длинных блочных кодов не используется. Структура решетки не позволяет.

Может кто-то поделиться понятным алгоритмом для декодирования блочных кодов (мягкое решение по входу)...

В книжке есть секция 10, написанная проф. Fossorier. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

Сообщение отредактировал andyp - Dec 28 2014, 23:39

[Maverick]

Глубоко копаешь .
Сам метод построения решетки блочного кода по проверочной матрице описан в книжке Lin Costello Error Control Coding Fundamentals and Applications (только 2е издание). Скачать ее можно здесь
http://bookzz.org/md5/8032998F071B09E087B9E8D81E7FFC1F
Тебе потребуется глава 9, а именно секция 9.5. Но хочу предупредить сразу - чтение не из легких.
Если кратко, получается, что код представляется (n+1)-секционной решеткой, метки ветвей соответствуют закодированным битам, метки состояний - линейная комбинация столбцов проверочной матрицы и кодовых бит, по которым пришли в это состояние. Очевидно, что n-ое состояние решетки будет единственным и будет состоять из (n-k) нулей по свойству проверочной матрицы. 0-е состояние - тоже 0. Из него начинаем.

Идем дальше. Рассмотрим кодовые слова кода, из которых вырезали к-ий бит. Предположим, что они все у нас есть (так проще) и будем строить решетку для них по тем же правилам, используя все столбцы проверочной матрицы оригинального кода, кроме к-го. В результате получим n-секционную решетку, начинающуюся в 0, и имеющую два хвоста. Почему хвостов 2? Да потому, что если в невыколотом кодовом слове в к-ой позиции был 0, то придем в нулевое состояние, если выколота была единица, то получим состояние, равное выколотому столбцу проверочной матрицы. Других вариантов нет. Именно про такую решетку пишут в статье.



Именно поэтому чистый MAP для длинных блочных кодов не используется. Структура решетки не позволяет.



В книжке есть секция 10, написанная проф. Fossorier. Там приведены кое-какие алгоритмы. Может, часть из них окажется интересной.

спасибо за объяснение...
тогда и махlog-map тоже не подходит.

А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?

[andyp]

А какой же алгоритм брать для использования - чейза или есть другие по лучше алгоритмы?

Для длинных кодовых блоков и скорости, близкой к 1/2?

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.

[Maverick]

Для длинных кодовых блоков и скорости, близкой к 1/2?

Общего рецепта нет. Чейз для длинных кодов как-то тоже не очень - у него сложность тоже экспоненциальная, просто растет медленнее. Народ идет по пути синтеза хорошо декодируемых известными алгоритмами кодов. LDPC хорошо декодируются по графу итеративно. BTC - опять итеративное декодирование простых составных кодов. Как-то так. "Итеративно" - видимо ключевое слово на сегодяншний день. Есть еще алгоритмы мягкого декодирования Рида-Соломона, но я с ними не разбирался.

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)
Длинные эти коды или нет я не знаю
Интересуют именно алгоритмы мягкого декодирования
Момент итеративности(количества итераций) сейчас можно пока опустить...

[andyp]

Да, для блоковых кодов до (128*128)*(128*128) и до 3D: (128*128)*(128*128)*(64*64)
Длинные эти коды или нет я не знаю
Интересуют именно алгоритмы мягкого декодирования
Момент итеративности(количества итераций) сейчас можно пока опустить...

Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

Сложность алгоритма Чейза 2 растет (ну и всех основанных на нем алгоритмов SISO) экспоненциально от d/2. Если у тебя например 128-битный код Хамминга, то у него d=3 и декодировать его - плевое дело. Если будешь его декодировать по решетке, то в каждой секции будет не больше 2^7 состояний (количество состояний в решетке будет пропорционально 2^(n-k) или 2^k, смотря что меньше), так что MAP декодирование для составных кодов, остнованных на кодах Хемминга, опять же возможно для широкого диапазона битовых скоростей.

Есть еще всякие алгоритмы типа recursive MLD и итеративное декодирование по minimum weight subtrellis, но все они зависят от структуры кода.

Наверное, я не про то пишу и все-таки и не понимаю вопроса.

[Serg76]

Что ты понимаешь под (128*128)? Перемножение двух скобочек - это продакт код?

По всей видимости 2D TPC, где в качестве компонентных используются расширенные коды Хемминга или же, по-другому, (128, 120)x(128,120)