Jump to content

    

Вопросы по итеративному декодированию

Добрый день!

 

Наконец то появилось время подтянуть себя в вопросах реализации кодов с вероятностным декодированием. Первая задача реализация 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. Вот этот момент мне совсем не понятен.

 

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

Share this post


Link to post
Share on other sites

2. Полиномы RCS для Wimax и DVB одинаковые, но перемежители разные. Это сделано по политическим причинам или это результат "улучшения" характеристик декодера в процессе разработки стандарта?

 

Совершенно разные каналы генерируют совершенно разные ошибки (одиночные/пачки, длина пачки и т.д.), отсюда и разные перемежители, подобранные каждый под свои модели каналов.

 

3. В сверточных бинарных кодах, свойство tail-bitting используется при декодировании: В одной доке нашел что дополняют принятую последовательность вначале и в конце, затем декодируют по витерби и выкусывают нужное. В примере матлаба вообще составляют два фрейма, декодируют один за другим, потом из двух декодированных собирают один результат. Никакого намека на похожие операции в доках на турбокоды не нашел. Почему в алгоритмах SOVA/MAP/... для турбокодов это не делается?

 

Вопрос в получаемом энергетическом выигрыше и цене, которую за это надо заплатить. В случае сверточных кодов tail-biting дает +0.3 дБ, а платой за это является требование увеличения вычислительной мощности устройства, на котором реализуется декодер. По всей видимости в случае турбокодов это нецелесообразно.

Share this post


Link to post
Share on other sites

Пункт 1

 

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

 

Пункты 3-4

 

Сравнение реализаций с прологом и с использованием состояния, полученного на предудыщей итерации приведены здесь

http://www.see.ed.ac.uk/~slig/papers/zhan.icassp06.pdf

 

Пункт 5

 

Массив inx для каждого i похоже содержит предварительно 3 рассчитанные суммы вида ys0*xs0 + ys1*xs1 для входных пар бит 01, 10, 11, из которых уже вычтена сумма для 00

Edited by andyp

Share this post


Link to post
Share on other sites
Совершенно разные каналы генерируют совершенно разные ошибки (одиночные/пачки, длина пачки и т.д.), отсюда и разные перемежители, подобранные каждый под свои модели каналов.

Понятно. Интересно, есть ли работы по обоснованию выбора трасс таких перемежителей именно для турбокодов. Судя по формулам перемежения, они идентичны. разница только в P0...P3. Причем в Wimax перемежитель проще (всего 2 параметра P0/P1), хотя по идее он работает в более сложных условиях: широкополосный доступ/полузакрытые и закрытые интервалы.

 

По всей видимости в случае турбокодов это нецелесообразно.

Сравнение реализаций с прологом и с использованием состояния, полученного на предудыщей итерации приведены здесь

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

 

По этой же теме возник вопрос : насколько обоснованно укорочение CTC кодов и чем именно лучше делать укорочение? Например в BCH/RS просто зануляем укорачиваемые слова на кодере, а на декодере изменяем начальную точку декодирования. А в CTC наверное лучше заполнять не нулями, а какой нить ПСП ?

Share this post


Link to post
Share on other sites
По этой же теме возник вопрос : насколько обоснованно укорочение CTC кодов и чем именно лучше делать укорочение? Например в BCH/RS просто зануляем укорачиваемые слова на кодере, а на декодере изменяем начальную точку декодирования. А в CTC наверное лучше заполнять не нулями, а какой нить ПСП ?

 

WiMax работает так - входные данные добиваются 0xFF до размера выделенного кодового блока, прогоняются через рандомайзер (это XOR с определенной ПСП), затем поступают в кодер. Размеры кодовых блоков определены в стандарте. Для каждого размера кодового блока определяются параметры интерливера. Т.е. CTC WiMax работает только для фиксированного набора кодовых блоков.

Edited by andyp

Share this post


Link to post
Share on other sites
Массив inx для каждого i похоже содержит предварительно 3 рассчитанные суммы вида ys0*xs0 + ys1*xs1 для входных пар бит 01, 10, 11, из которых уже вычтена сумма для 00

Вы правы, так и есть, правда сумма для 00 не вычитается. Вот это место :

// llr = received LLR of the code bits.
...
Nbits = length(code_interleaver.info_intl);
N = Nbits/2;
...
depun_llr = zeros(1,3*Nbits);
....
depun_llr(1:3*Nbits) = llr;
.....
    temp_llr([1,2],:) = reshape( depun_llr(1:2*N), 2, N );
    temp_llr([3,4],:) = reshape( depun_llr(2*N+1:4*N), 2, N);
    temp_llr([5,6],:) = reshape( depun_llr(4*N+1:6*N), 2, N);
....
X = [ temp_llr([2,1],:); temp_llr(1,:)+temp_llr(2,:)]; %% llr: 01, 10, 11
inz1  = [ temp_llr([5,3],:); temp_llr(3,:)+temp_llr(5,:)]; %% llr: 01, 10, 11
inz2  = [ temp_llr([6,4],:); temp_llr(4,:)+temp_llr(6,:)]; %% llr: 01, 10, 11

Судя по всему они определяют символы 0/1 а не -1/1. Занятно что в других местах не так.

 

Т.е. CTC WiMax работает только для фиксированного набора кодовых блоков.

Всё так, этот момент понятнен. Но что мешает поступить следующим образом : положим работаем с фреймом 53 байта и хотим укоротить его на 1 байт. Берем 52 байта данных и 1 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем.

Share this post


Link to post
Share on other sites
Вы правы, так и есть, правда сумма для 00 не вычитается. Вот это место :

Странно. Судя по коду, который Вы приводили выше, они считают, что гамма для переходов решетки с 00 равна 0. Я поэтому про вычитание и предположил. Может быть, это еще где учитывается.

 

Всё так, этот момент понятнен. Но что мешает поступить следующим образом : положим работаем с фреймом 53 байта и хотим укоротить его на 1 байт. Берем 52 байта данных и 1 байт добиваем нулями. Кодируем. Пары систематических символов, порожденные этим байтом в поток не передаем. На приемной стороне определяем эти биты как априори известные и декодируем.

 

В системном плане смысла нет. В WiMax единицей частотно-временного ресурса системы является слот. В случае OFDMA это определенным образом расставленные по времени и частоте поднесущие (там много всяких комбинаций). Планировщик передачи выделяет ресурс слотами. Разбивка на слоты в аплинке и даунлинке сообщается всем станциям через специальные сообщения, передаваемые на фиксированных местах фрейма. Все кодовые блоки содержат целое количество слотов. Так уж это работает.

Share this post


Link to post
Share on other sites

Занятное дело. Скидал в матлабе кодер, похожий на железный, и вот что обнаружилось: интерливер в сорцах CML и в стандарте разный. А именно отличается условие инверсии пар.

В стандарте интерливер работает так :

    for j=0:N-1
        i = get_paddr(j, N, P);        
        if mod(j,2) == 0 % equal standart             
            odat([1, 2],j+1) = idat([2, 1], i+1);
        else
            odat([1, 2],j+1) = idat([1, 2], i+1);
        end
    end

а в CML

    for j=0:N-1
        i = get_paddr(j, N, P);        
        if mod(i,2) == 0 % equal CML             
            odat([1, 2],j+1) = idat([2, 1], i+1);
        else
            odat([1, 2],j+1) = idat([1, 2], i+1);
        end
    end

Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально :)

 

Пример кода в приложении. При работе требует либу http://www.iterativesolutions.com/Matlab.htm

CTC.zip

Share this post


Link to post
Share on other sites
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 гибче, у него количество фреймов разной длинны больше :)

Share this post


Link to post
Share on other sites
Занятная вещь. Похоже местоположение инверсии пар не сильно принципиально :)

 

Только кодер перестанет быть стандартным :). Рассмотрим второе преобразование (перестановку пар) и кодовый блок с N=24 (P0=5, P1=P2=P3=0). Если рассмотреть j mod 4 = 0 (четное), то i = (5*j + 1) mod N - нечетное. Соответственно, А и В будут переставлены не у тех пар.

 

Я бы перестал ориентироваться на либу CML, тем более, что последний вариант, доступный в исходниках, очень старый.

Edited by andyp

Share this post


Link to post
Share on other sites

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

 

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

 

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

 

Share this post


Link to post
Share on other sites
Одни предлагают подавать на вход квантованные LLR, другие квантованные канальные символы (например для QAM16 - 2 бита целая часть, 4 бита дробная).

 

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

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

 

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

Это уже епархия демодулятора (АРУ, ограничители), чтобы все выходные значения лежали в заданном диапазоне

Share this post


Link to post
Share on other sites
Насколько я понимаю при декодировании речь может идти только о квантовании 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.

Share this post


Link to post
Share on other sites

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

 

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

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

 

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

 

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

hagenauer.pdf

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this