Jump to content

    
des00

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

Recommended Posts

Покурил немного тему про TPC. Созрел глупый вопрос. Почему код Хэмминга не декодируют в мягкой форме по графу Таннера? Зачем связываться с алгоритмом Чейза, находить ненадежные метрики и т.д, если можно сделать все через сложение вероятностей, ведь уравнения четностей никуда не делись

можно и так...

parallel_architecture_for.pdf

Share this post


Link to post
Share on other sites
Покурил немного тему про TPC. Созрел глупый вопрос. Почему код Хэмминга не декодируют в мягкой форме по графу Таннера? Зачем связываться с алгоритмом Чейза, находить ненадежные метрики и т.д, если можно сделать все через сложение вероятностей, ведь уравнения четностей никуда не делись ?

 

Возможно, короткие циклы в графе Таннера.

 

Share this post


Link to post
Share on other sites
можно и так...

Об этом и веду речь, в статье классический min-sum и передача сообщений. В случае Parity Check кодов (2^N, 2^N-1) сие используют, а в случае Хэмминга (по сути тот же Parity Check) делают через чейза.

 

Именно так - частный случай MAP алгоритма. Может у кого-то есть код для этого случая?

скачал, буду смотреть. На первых страницах темы, есть ссылки на CML либу(где есть сверточники в сорцах) и мой матлабовский код RSC турбо декодера можно посмотреть организацию вычислений.

Share this post


Link to post
Share on other sites

Туплю. В приложении алгоритм SISO декодера для кода вида 1/(1+D), взятый из статьи. Не могу понять корреляцию этого кода с MAP алгоритмом.

 

MAX LOG MAP для бинарного сверточного кода с двумя состояниями и однобитным выходом должен же быть такой:

 

alpha(s', k+1) = alpha(s, k) + gamma(s, s');

beta(s, k) = beta(s', k+1) + gamma(s, s');

outLLR(k) = alpha(s, k) + gamma(s, s') + beta(s', k+1)

 

alpha - прямая ветка

beta - обратная ветка

gamma(s,s') - вероятности перехода из состояний s в s'. в случае кода с двумя состояниями и одним выходом будет просто суммой метрик LLR_D(k), + LLR_P(k)

 

Вот в упор не вижу ничего похожего между этими двумя алгоритмами.

post-3453-1467261827_thumb.png

Share this post


Link to post
Share on other sites
Не могу понять корреляцию этого кода с MAP алгоритмом.....

похоже что это не MAP алгоритм, а классический min-sum, немного в измененной форме (стр 27)

High_Speed_Decoding_of_Serial_Concatenated_Codes.pdf

Share this post


Link to post
Share on other sites

В книге, автором которой является автор статьи (и, как я понял, Flex-кодов) на стр. 39 говорится, что FBA - это APP алгоритм, только вместо sum-product операций, тут применяются min-sum.

 

http://ru.bookzz.org/book/2093686/86e4d4

 

И, кстати, интересное наблюдение - в статье говорится об универсальности данного алгоритма для обоих кодов (внешнего и внутреннего) ввиду их, скажем так, ортогональности. Если на информационный вход подать проверки, а на проверочный вход информационные ЛЛР - получится декодер для дифференцирующего кода. И в этом случае ошибка, о которой я писал выше, не возникает.

Share this post


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

Чем больше смотрю на граф Таннера F-LDPC, тем больше кажется что метод декодирования SCCC с внутренним и внешним декодером тут не применимы. По той причине что:

1. Код систематический. Биты проверки - прореженный выход с Inner кодера.

2. Outer код + интерливер + SPC код - задает связь систематических битов со входом Inner кодера. Никакой решетки для декодирования тут нет. Посчитали вероятность на входе Inner декодера, уточнили ее в этом декодере и раскидали обратно, получив extrinsic метрики для следующего шага или выходные решения.

 

Из того, что мне не понятно, это граф Танера Inner кода. Проверочные биты должны быть vnode, состояния решетки тоже vnode. Не догоняю как ко всему этому приделать cnode. Т.е. как замкнуть Parity Check уравнение для декодирования по min-sum.

Share this post


Link to post
Share on other sites
1. Код систематический. Биты проверки - прореженный выход с Inner кодера.

 

Не совсем. Разберем по частям, как работает кодер SCCC c S-SCP:

1. Информация кодируется outer кодером (Например - 256 бит)

2. Дублируется в случае FLDPC (полученная последовательность 512 бит)

3. Перемежается интерливером (512 бит)

4. SCP - выходные данные этого блока свертка (сложение по мод2) соседних бит в случае 1/2. (256 бит)

5. inner code (256 бит).

 

inf(i,:) = randint(1, size);
out_enc_seq = outer_enc([inf(i,end) inf(i,:)]);                    % дифф кодер
dbl_seq(1:2:length(inf(i,:))*2-1) = out_enc_seq(2:size+1);         % дублирование
dbl_seq(2:2:length(inf(i,:))*2) = out_enc_seq(2:size+1);    
intrl_seq = intrlvr(dbl_seq, size);                                % перемежение
scp_seq = xor(intrl_seq(1:2:end), intrl_seq (2:2:end));        % перфорация
prt(i,:) = inner_enc(scp_seq);

Share this post


Link to post
Share on other sites
Не совсем. Разберем по частям, как работает кодер SCCC c S-SCP:

1. Информация кодируется outer кодером (Например - 256 бит)

2. Дублируется в случае FLDPC (полученная последовательность 512 бит)

3. Перемежается интерливером (512 бит)

4. SCP - выходные данные этого блока свертка (сложение по мод2) соседних бит в случае 1/2. (256 бит)

5. inner code (256 бит).

Все так. И в итоге это

Систематический код - код, в котором разряды распределены на две группы, одна из которых служит, для передачи информации, а вторая - для проверки правильности передачи, причем все разряды занимают строго фиксированные положения.

Т.е. систематические биты, лежат в выходном фрейме явно, а не свернутые.

 

Это я к тому, что ИМХО для декодирования по решетке (Витерби/MAP) систематического кода нужно знать входные (систематические) и выходные (проверочные биты) кода. Это нужно для того что бы посчитать метрики ветвей(переходов), а по ним метрики состояний. В случае FLDPC выходные биты Outer кода в явном виде не известны. Известны только после перемежения, накопления и выкалывания. Но где то же, систематические и проверочные биты должны встретиться. По логике вещей, это должно произойти в Inner коде

Share this post


Link to post
Share on other sites
В случае FLDPC выходные биты Outer кода в явном виде не известны. Известны только после перемежения, накопления и выкалывания.

 

А вот здесь самое интересное:

Если в алгоритм FBA информационные(систематические) ллр подать на проверочный вход, проверочный вход заполнить нулями, то на информационном выходе получим проверки. Этакое кодирование декодированием:)

Edited by maratz

Share this post


Link to post
Share on other sites
А вот здесь самое интересное:

Если в алгоритм FBA информационные(систематические) ллр подать на проверочный вход, проверочный вход заполнить нулями, то на информационном выходе получим проверки. Этакое кодирование декодированием:)

Сам пример я пока не запускал. Остановился на строчке

 %передача данных в канале ФМ-2 с ОСШ = 15, принимаем llr

ФМ-2 имеет пороговое С/Ш по 1е-6 10.5дб. Т.е. в тесте, если С/Ш верное, ошибок в канале нет. Декодер проверять таким тестом, сомнительное занятие.

 

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

Share this post


Link to post
Share on other sites
Сам пример я пока не запускал. Остановился на строчке

 %передача данных в канале ФМ-2 с ОСШ = 15, принимаем llr

ФМ-2 имеет пороговое С/Ш по 1е-6 10.5дб. Т.е. в тесте, если С/Ш верное, ошибок в канале нет. Декодер проверять таким тестом, сомнительное занятие.

 

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

Так не декодер проверяем в этом коде. Там ведется проверка приведенного в статье алгоритма и слов автора. Важное подчеркнул:

image.png

 

image.png

 

Share this post


Link to post
Share on other sites
Так не декодер проверяем в этом коде. Там ведется проверка приведенного в статье алгоритма и слов автора.

У меня с английским не важно, но напишу свой вариант перевода первых двух абзацев, с моими умозаключениями:

Необходимо отметить, что каждый уровень решетки, в решетке аккумулятора требует 3-х g операций и 4-х сложений(сложение в 11b и в 11c одинаковое). Если нет входной метрики переменой x[j] (MI[x[j]] == 0 для всех j) и нет выходной информации по переменной x[j] то количество g операций остается тем же, тогда как сложения исчезают. Это соответствует обработке по формуле 6, которая является обработкой чек нодов LDPC кода. Если же входная метрика переменной x[j] есть, но нет соответствующей ей выходной информации, то количество операций сложения уменьшается до 2-х.

Тут не сказано о том, что можно что-то занулять. Просто дан расклад на количество операций по решетке, в различных случаях.

 

Теперь опишем как SISO для аккумуляторной решетки может быть использован для декодирования GRA и F-LDPC кодов. Для начала рассмотрим RSPC генератор, который включает в себя SPC и аккумулятор в обоих кодах. Используя формулу 10, мы может установить соответствие переменных d[j] к a[j] и p[m] к x[m][j] вместе с другими выколотыми x[j]. Из этого следует что MI[a[j]] в формулах 11 это сообщения d[j] прочитанные из интерливера, и MI[x[j]] это набор канальных метрик проверочных битов p[m] для случая j = mJ и нули для всех остальных случаев. Отметим что выходное сообщение по проверочным битам MO[x[j]] не рассчитывается.

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

Если в алгоритм FBA информационные(систематические) ллр подать на проверочный вход, проверочный вход заполнить нулями, то на информационном выходе получим проверки. Этакое кодирование декодированием

 

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

Share this post


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

Ну как же - прямым текстом написано MI(x) = 0 для всех j.

 

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

Вот тут немного не понял, о чем я говорю, что не вяжется со статьей?

Я утверждаю, что приведенный алгоритм может восстановить проверочную часть, имея лишь систематическую. Также я утверждаю, что этот алгоритм должен подходить как для кода 1+D(outer), так и для 1/1+D(inner). Об этом пишется в статье, я это выделил. Также есть эксперимент, в ходе которого подтверждается теория для outer кода, но не подтверждается для inner - в первой и только первой позиции иногда появляется ошибка.

Собственно, для поиска источника этой ошибки я обратился сюда:)

 

 

 

Share this post


Link to post
Share on other sites
Ну как же - прямым текстом написано MI(x) = 0 для всех j.

Вы упускаете важную фразу "Если нет входной метрики переменой". Что делать если она есть, а она действительно есть.

Вот тут немного не понял, о чем я говорю, что не вяжется со статьей?

Я утверждаю, что приведенный алгоритм может восстановить проверочную часть, имея лишь систематическую.

Полагаю остаться при своих. Вы изучаете этот алгоритм больше, вам должно быть виднее. Останусь при своем мнении, то что вы пишете, не возможно. Для декодирования по решетке нужен весь объем информации. Мнение основано на материалах по декодированию сверточных кодов в любом учебнике по кодированию.

Также есть эксперимент, в ходе которого подтверждается теория для outer кода, но не подтверждается для inner - в первой и только первой позиции иногда появляется ошибка.

ИМХО эксперимент не корректен, но вам виднее.

 

ЗЫ. Полагаю что все решится при снятии кривых кодирования F-LDPC кода, благо образец для подражания есть в доках. Сорцы кодека, когда закончу, выложу сюда, сможете сравнить результаты со своими.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.