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

Сделал F-LDPC кодек в матлабе (сорцы причешу и чуть позже выложу), вижу недобор чутья, возникло 2 вопроса :
1. Как могут терминироватся решетки в обоих кодерах? Ведь по идее лучше что бы решетка была циклической, но указаний на циркуляцию в доке я не нашел.
2. При вычислении экстринсиков в турбокодах, работающих с алгоритмом MAX LOG MAP вводят коэффициент пропорциональности меньше единицы (компенсация дельты в функции MAX* и "стабилизация" алгоритма). А как поступают в турбокодах, основанных на алгоритме min_sum (F-LDPC)?

[des00]

1. Как могут терминироватся решетки в обоих кодерах? Ведь по идее лучше что бы решетка была циклической, но указаний на циркуляцию в доке я не нашел.

Решетку зациркулировал, по логике здравого смысла. Чутье улучшилось. Но вопрос все же актуален.

В приложении F-LDPC кодек, в котором SPC декодер интегрирован в inner siso декодер, не дошел до мысли, как красиво его сделать отдельным.

Зы. Код специально написан примитивно и медленно, заточен к переносу на ПЛИС.

UPD. Немного мыслей по алгоритму сверточного декодирования из статьи. На уровне логики я понял почему они сделали все на min-sum функциях. Т.к. кодеры по сути работают как Parity Check. Но, вот смотрю как растут метрики и вижу странности. Например, рассмотрим уравнение MO[a(j)] = g(F(j), B(j+1) + MI[x(j)]. g - функция min-sum. Т.е. у нас может быть высокая надежность следующего состояния B(j+1), высокая корреляция с ним метрики выходного бита MI[x(j)], но низкая надежность текущего состояния F(j). И в итоге выходное сообщение будет с низкой надежностью. Тоже самое касается и уравнения B(j) =g(B(j+1)+MI[x(j)],MI[a(j)]). низкий MI[a(j)] перевешивает все.

До кучи нигде в коде не видно корреляции входных и выходных данных решетки (метрики перехода), тогда как в сверточниках это основной момент. ИМХО, мне кажется, что по этому, они не пишут про то, как декодируют FlexCode, там сверточники на 4 состояния, подобным образом не отскочишь. Надо попробовать сделать F-LDPC классически и сравнить.

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

 F_LDPC_mlab_05072016.7z ( 5.27 килобайт ) Кол-во скачиваний: 39

 

[maratz]

Мельком посмотрел, исправляющая способность лучше, чем в моей реализации, буду внимательно изучать, но чуть позже.
По инициализации решетки и, может быть, разъяснению алгоритма прикрепляю статью - в ней рассматривается тот же алгоритм, но с другого ракурса (это уже было, но в виде презентации - тут подробней).

Сообщение отредактировал maratz - Jul 5 2016, 07:14

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

 high_speed_decoding_for_scc.pdf ( 166.95 килобайт ) Кол-во скачиваний: 49

 

[des00]

Надо попробовать сделать F-LDPC классически и сравнить.

Гыыы. Расписал ручками решетку, а ведь они правы черт возьми. Итак решетка кода 1/(1+D)

Код

    trel.nextStates = [[0 1][1 0]];
    trel.outputs    = [[0 1][1 0]];
    trel.preStates  = [[0 1][1 0]];

Рассмотрим MAX LOG MAP с прямыми метриками. Метрики переходов gamma(state, input_bit) будут

Код

            gamma(0, 0) = 0*ma(i) + trel.outputs[0][0]*mx(i);
            gamma(0, 1) = 1*ma(i) + trel.outputs[0][1]*mx(i);
            gamma(1, 0) = 0*ma(i) + trel.outputs[1][0]*mx(i);
            gamma(1, 1) = 1*ma(i) + trel.outputs[1][1]*mx(i);

оптимизируем

Код

            gamma(0, 0) = 0;//00
            gamma(0, 1) = ma(i) + mx(i);//11
            gamma(1, 0) = mx(i);//01
            gamma(1, 1) = ma(i);//10

составляем уравнение расчета надежностей состояний при обратном проходе, с учетом решетки trel.preStates

Код

        beta[k][0] = max(gamma(0, 0) + beta[k+1][0], gamma(0, 1) + beta[k+1][1]);
        beta[k][1] = max(gamma(1, 1) + beta[k+1][0], gamma(1, 0) + beta[k+1][1]);

Переходим от вероятностей каждого состояния (беззнаковой) к разностной вероятности (помним что одинаковое смещение не влияет на MAX LOG MAP)

Код

        beta[k][0] = max(gamma(0, 0), gamma(0, 1) + beta[k+1][1] - beta[k+1][0]);
        beta[k][1] = max(gamma(1, 1), gamma(1, 0) + beta[k+1][1] - beta[k+1][0]);

оптимизируем B[k+1] = beta[k+1][1] - beta[k+1][0], gamma(0,0) = 0

Код

        beta[k][0] = max(          0, gamma(0, 1) + B[k+1]);
        beta[k][1] = max(gamma(1, 1), gamma(1, 0) + B[k+1]);

снова переходим к разностной вероятности

Код

        B[k] = max(gamma(1, 1), gamma(1, 0) + B[k+1]) - max(0, gamma(0, 1) + B[k+1]);

Делаем подстановку остальных gamma и вуаля.

Код

        B[k] = max(ma[i], mx[i] + B[k+1]) - max(0, ma[i] + mx[i] + B[k+1]);

Ну а работать в прямых или инверсных метриках это уже пожеланию

[des00]

Возник вот такой вопрос. В MAX LOG MAP алгоритме, с без знаковыми метриками, метрики состояний всегда растут в одну сторону. Нормировка метрик состояния в этом случае делается просто. А как быть в случае знаковой(разностной) метрики? Ведь тут вычитать или использовать модульную арифметику не получится. Ограничивать или использовать деление неправильно.

Как вариант вижу ограничение экстринсиков, что автоматически приведет в ограничению метрик состояния. Может есть другие варианты?

[des00]

Гыыы....

Расписал все уравнения. В статьях, выходные сообщения это именно extrinsic LLR. Никакой другой математики, по вычитанию метрик систематических бит не нужно.

Может есть другие варианты?

Состояния в этом коде это надежности значений аккумулятора, поэтому ограничение метрик состояний прекрасно работает.

Ну и до кучи, еще вытянуть немного чутья помогут следующие простые модификации
1. Небольшая утечка extrinsic LLR, коэффициента 0.75 достаточно.
2. Ограничение extrinsic LLR.
3. Аппроксимация min-sum* в виде g(x,y) = min(|x|, |y|)*sign(x)*sign(y) -0.25*sign(x)*sign(y).

В железе, все это реализуется с минимальным ресурсом.

Надо придумать как сделать N портовый collision free interleave и за недельку можно скидать декодер

[des00]

Доброго всем.

Озадачился вопросом, есть ли возможность, априори оценить разность ЭВК для одного и того же кода, в зависимости от длинны блока? Понятно, что чем больше длинна блока тем лучше, сказывается эффект интегрирования шума. Но вот пример:
1. FLDPC. блоки 4/8/16к. длинна отличается в 2 раза. Разница по 1е-6 между 4к и 8к ~0.2дб для всех скоростей, между 8к и 16к ~0.1дб.
2. Duo Binary RSC. блоки 30/60/120/240/480 байт. Разница по 1е-6 между 30/60/120/240 ~0.5дб, а между 240 и 480 ~0.2дб.

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

Спасибо.

Эскизы прикрепленных изображений

 

[maratz]

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

Судя по рисунку, 16к и 32к будут отличаться на 0.05 дБ. http://datumsystems.com/waterfall

По реализации. На входе стоит 1+D в мягкой форме, потом inner siso, потом outer siso, extrinsic LLR которого суммируется с начальными систематическими LLR(sLLR) и кодируется входным 1+D. Я убрал 1+D и sLLR подаю сразу на проверочный вход outer siso, а на информационный нули. Результат одинаковый, но времени уходит меньше.

Однако по исправляющей недобор. Хотел бы больше узнать об ограничении метрик состояний и extLLR. И что такое утечка extLLR?

Сообщение отредактировал maratz - Jul 16 2016, 11:53

Эскизы прикрепленных изображений

 

[des00]

Судя по рисунку, 16к и 32к будут отличаться на 0.05 дБ. http://datumsystems.com/waterfall

Спасибо. Интересная ссылка, надо в запасник отложить. Пригодится. Но мой вопрос был не о конкретном коде, а в принципе. Есть же предел Шеннона, задающий точку отсчета для декодера, должны быть и исследования оптимальных длин блоков. Съем кривых кодирования это уже эксперемент.

По реализации. На входе стоит 1+D в мягкой форме, потом inner siso, потом outer siso, extrinsic LLR которого суммируется с начальными систематическими LLR(sLLR) и кодируется входным 1+D. Я убрал 1+D и sLLR подаю сразу на проверочный вход outer siso, а на информационный нули. Результат одинаковый, но времени уходит меньше.

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

Хотел бы больше узнать об ограничении метрик состояний и extLLR. И что такое утечка extLLR?

в декодерах имеет смыл ограничить входные метрики и экстринсик метрики между итерациями на достаточно достоверном уровне, в противном случае возможно ухудшение сходимости декодера. Называется это scalling soft information - по сути утечка в терминах эквалайзирования/затухание фильтра. В приложенной статье, подбором коэффициента получают выигрыш до 0.6дб.

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

 heo2003.pdf ( 58.36 килобайт ) Кол-во скачиваний: 35

 

[andyp]

Возник вот такой вопрос. В MAX LOG MAP алгоритме, с без знаковыми метриками, метрики состояний всегда растут в одну сторону. Нормировка метрик состояния в этом случае делается просто. А как быть в случае знаковой(разностной) метрики? Ведь тут вычитать или использовать модульную арифметику не получится. Ограничивать или использовать деление неправильно.

Как вариант вижу ограничение экстринсиков, что автоматически приведет в ограничению метрик состояния. Может есть другие варианты?

Я ограничиваю альфы и беты снизу при вычислении минимума плюс при обновлении состояний решетки для текущего входного бита/дибита запоминаю максимальное насчитавшееся альфа. Если оно больше некоторого порога, то вычитаю из накопленных альф это пороговое значение.
Вычитание константы на величину экстринсика не влияет, там разность альф и бет используется.

Код

        for(state_type j = 0; j <= state_type(Trellis::num_trellis_states - 1); ++j)
        {
            std::pair<typename Trellis::Branch, typename Trellis::Branch> branches = _trellis.get_backward_branches(j);

            //max-log-MAP ядро
            state_type s0 = branches.first.state;
            LLRType gamma_s0 = branches.first.input? g1[s0] + apriories[i] : g0[s0];
            state_type s1 = branches.second.state;
            LLRType gamma_s1 = branches.second.input? g1[s1] + apriories[i] : g0[s1];
            LLRType next_alpha = std::max(a[s0] + gamma_s0, a[s1] + gamma_s1);

            //ограничиваем значение alpha снизу
            next_alpha = std::max(next_alpha,min_log_prob);
            a_next[j] = next_alpha;
            //максимальное значение alpha для состояний решетки в текущий момент времени
            max_a = std::max(max_a,next_alpha);
        }
        //нормализация
        if(max_a > max_log_prob)
        {
            for(state_type j = 0; j <= state_type(Trellis::num_trellis_states - 1); ++j)
                a_next[j] = std::max(LLRType(a_next[j] - max_log_prob), min_log_prob);
        }

Сообщение отредактировал andyp - Jul 21 2016, 10:34

[maratz]

Есть ли у кого-нибудь материалы или сведения о влиянии длины окна при обратном проходе в SOVA на исправляющую способность?