Вопросы по итеративному декодированию, Реализация 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. Вот этот момент мне совсем не понятен.

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

[stealth-coder]

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

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

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

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

[andyp]

Пункт 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

Сообщение отредактировал andyp - Dec 25 2014, 07:08

[des00]

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

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

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

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

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

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

[andyp]

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

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

Сообщение отредактировал andyp - Dec 26 2014, 09:06

[des00]

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

[andyp]

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

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

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

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

[des00]

Занятное дело. Скидал в матлабе кодер, похожий на железный, и вот что обнаружилось: интерливер в сорцах 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 ( 2.31 килобайт ) Кол-во скачиваний: 39

 

[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 гибче, у него количество фреймов разной длинны больше

[andyp]

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

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

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

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

[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 канале?

[Serg76]

Одни предлагают подавать на вход квантованные 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 канале?

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

[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