Jump to content

    

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

Сделал F-LDPC кодек в матлабе (сорцы причешу и чуть позже выложу), вижу недобор чутья, возникло 2 вопроса :

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

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Мельком посмотрел, исправляющая способность лучше, чем в моей реализации, буду внимательно изучать, но чуть позже.

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

high_speed_decoding_for_scc.pdf

Edited by maratz

Share this post


Link to post
Share on other sites
Надо попробовать сделать 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]);

 

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

Share this post


Link to post
Share on other sites

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

 

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

 

 

 

Share this post


Link to post
Share on other sites
Гыыы....

Расписал все уравнения. В статьях, выходные сообщения это именно 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 и за недельку можно скидать декодер :)

Share this post


Link to post
Share on other sites

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

 

Озадачился вопросом, есть ли возможность, априори оценить разность ЭВК для одного и того же кода, в зависимости от длинны блока? Понятно, что чем больше длинна блока тем лучше, сказывается эффект интегрирования шума. Но вот пример:

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дб.

 

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

 

Спасибо.

post-3453-1467868088_thumb.png

post-3453-1467868923_thumb.png

Share this post


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

Судя по рисунку, 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?

post-90332-1468592784_thumb.png

Edited by maratz

Share this post


Link to post
Share on other sites
Судя по рисунку, 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

Share this post


Link to post
Share on other sites
Возник вот такой вопрос. В 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);
        }

Edited by andyp

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Подниму старую тему.

Таки дошел до ситуации, когда хочу научится считать проверочные матрицы регулярных LDPC кодов, основанных на сдвинутых единичных матрицах. Хочу насчитать матрицы как в Wimax, но на более широкий диапазон скоростей кодирования. Интересуют 1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9, 9/10.

Накачал статьей с сети, но .... "говорила мне мама, учи математику сынок..." много не понятно.  Может кому попадалась хорошая литература или есть подборка литератуы по этому вопросу ? Можете поделится?

Спасибо.

ЗЫ. Сам давал ссылку на статьи П.Трифонова, они у меня есть, но см. причину выше)))

Share this post


Link to post
Share on other sites
On 11/14/2019 at 1:49 PM, des00 said:

 Хочу насчитать матрицы как в Wimax

полез в эту тему, сразу возник вопрос. Судя по всему мощность LDPC кода определяется термином girth, в материалах указано что girth = 4 сильно снижает мощность кода, лучше girth=6 и выше. Для практики сделал расчёт girth для Wimax матриц и получил вот такой результат.

5/6 блоки от 576 до 1440 обладают girth = 4, блоки от 1536 до 2304 girth = 6. 

3/4 блоки от 576 до 2304 обладают girth = 4 

2/3 блоки от 576 до 2304 обладают girth = 6

1/2 здесь в разнобой girth = 4/6

Собственно вопрос, много где пишут что girth = 4 это не хорошо, получается авторы стандарта сознательно пошли на ухудшение работы некоторых вариантов используемого кода, в угоду простоте кодирования и декодирования? Или это общее свойство (типовой girth 4-6) всех квази-регулярных LDPC кодов? 

PS. Сами характеристики кодов я снимал, есть эффект растекания шума после 1е-6, чего например нет у GSFC 7/8

Share this post


Link to post
Share on other sites
7 часов назад, des00 сказал:

Или это общее свойство (типовой girth 4-6) всех квази-регулярных LDPC кодов?

Есть коды данного подсемейства, для которых длина циклов 8: https://ieeexplore.ieee.org/abstract/document/1523756

Для итерационных алгоритмов, работающих с графами Таннера, весьма критично наличие циклов длины 4, уже менее критично 6. Обмен сообщениями происходит не так эффективно. Нужно использовать больше итераций, а возможно, вообще появится полка, то есть сходиться будет к какой-то величине ошибки, которая больше, чем для графов без циклов.  Детально не читал спецификацию WiMax, поэтому не могу сказать, чем обусловлен выбор. Может быть, скоро предстоит разбираться :)

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