[xromeo 0]

Попробовал сделать программную реализацию алгоритма Max-Log-MAP для Double-Binary турбокода. Реализацию делал согласно источнику "Low-Power Traceback MAP Decoding for Double-Binary Convolutional Turbo Decoder" (прикрепленный файл mlmap.pdf), раздел II - это оказался единственным более-менее понятным документом с описанием алгоритма для недвоичных свёрточных кодов из всех, что мне удалось найти. Программу писал на Си.

 

Вроде бы, ничего сложного, сделал всё один в один как написано, а результат получается неверный. Причём неверный результат даёт декодер SISO уже на первой итерации, при том, что на вход подаётся ВЕРНОЕ кодовое слово, не содержащее ошибок. Апостериорные вероятности получаются либо неверными, либо, порой, неоднозначными, ибо получаются равновероятными сразу несколько вариантов.

 

Буду благодарен, если подскажете, что и где я делаю не так, что именно недопонимаю (а может, и в самом источнике где-то что-то неверно?).

 

Ниже, в прикреплённом файле lmap.txt, привожу полное описание алгоритма с комментариями и фрагментами кода на Си.

 

Заранее огромное спасибо всем, кто решится изучить мою проблему.

mlmap.pdf

mlmap.txt

Изменено 10 августа, 2009 пользователем Coder2009

[xromeo 0]

Разобрался, вопрос снят, при расчёте обратной рекурсии была наибанальнейшая ошибка в индексе :) Выражение должно быть таким: (gamma[k][z] + alfa[k] + beta[k+1][s_Out[z]]).

Изменено 12 августа, 2009 пользователем Coder2009

[more 0]

Неясно где была ошибка, согласно прилагаемого файла обратная рекурсия расчитывалась:

 for (k = N-1; k >= 0; k--)
 {
   for (s = 0; s < 8; s++)
   { // beta[k][s] = MAX_z(gamma[k][s_Out[s][z]][z] + beta[k+1][s_Out[s][z]])
     tmp = gamma[k][s_Out[s][0]][0] + beta[k+1][s_Out[s][0]];
     for (z = 1; z < 4; z++)
       if ((tmp1 = gamma[k][s_Out[s][z]][z] + beta[k+1][s_Out[s][z]]) > tmp)
         tmp = tmp1;
     beta[k][s] = tmp;
   }
 }

А согласно поправки написано выражение

 
(gamma[k][s][z] + alfa[k][s] + beta[k+1][s_Out[s][z]])

как я понимаю для max[z] ?

так где же ошибка?

[Neznaika 0]

Всем привет! Нахожусь в затруднительном положении. Реализовывал TPC-кодек по стандарту DVB-RCS EML-MAP алгоритмом. Результаты BER для всех скоростей примерно на 1 дб S/N уступают ожидаемым. Может есть какие то ошибки в принципах реализации?

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

2. Для расчета обратной рекурсии использовал метод окон и метод граничных метрик (Border metric). Разбивал блок на окна, причем при 1-ой итерации в качестве начальных значений метрик обратной рекурсии использовал 0, сохранял последние значения метрик обратной рекурсии каждого окна, чтобы использовать их в качестве начальных метрик для вычисления окон обратной рекурсии при последующей итерации. На каждой итерации значения обновлялись.

3. Масштабировал внешнюю информацию с коэффициентом 0.75, Lex=0.75*(Lapo-Lapr-Lin).

4. Вход 4-битный, со средним уровнем входных данных 0.5.

 

Видел в статьях что то про Tailing Bitting - не совсем понятно зачем и для чего... но какая то привязка к цикличному кодированию есть...

Вообще архитектура себя ведет вполне предсказуемо, с увеличением числа итерации качество BER, растет. Игра с коэффициентом масштабирования внешней информации тоже дает положительный результат... При 1 и при 0.5 BER заметно хуже, чем при 0.75.

 

Еще есть характерная особенность, что при достижении BER в 10^-7 появляется шумовая полка.. BER в нее упирается и уже не зависит от S/N.

Изменено 2 апреля, 2014 пользователем Neznaika

[FatRobot 0]

Вы могли бы уточнить про 10^-7? т.е. если шума нет (передатчик и приемник соеденины золотой проволокой), то тоже 10^-7?

 

Еще есть характерная особенность, что при достижении BER в 10^-7 появляется шумовая полка.. BER в нее упирается и уже не зависит от S/N.

[Neznaika 0]

Вот самое главное.. BER) Без шума все по нулям работает. Привожу 3 графика. 1 - результаты полученные мной, 2 - результаты моделирования из статьи по стандарту DVB-RCS, 3 - FER, к сожалению, а не BER архитектуры декодера, аналогичной моей.

[FatRobot 0]

Конечно, готвых рецептов "как починить" у меня нет.

 

Но если бы я столкнулся с такой задачей, то

1. Посмотрел, правильно ли у меня работает перемежитель-деперемежитель. 10е-7 может говорить, что, например, 1 позиция в матрице перемежителя неправильная.

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

3. Генератор мягких выходов для декодера Витерби. Он может тупо шуметь.

 

Про tail-biting посмотрите у Морелоса для начала. Там чуть другая идея декодирования, чем при обычном zero-tail, и проще ее понять, если представить, что пути декодирования нарисованы на ленте, свернутой в кольцо.

 

[Neznaika 0]

Спасибо за ответ)

1. Перемежитель еще раз проверю. У меня есть модель на Си и проект на VHDL, работают они идентично (с точностью до младшего бита) с одинаковыми входными сигналами. Вот только для модели могу проводить приблизительные измерения, добавляя шум функцией randome, а проект уже работает с реальным канальным шумом от железячного генератора шума.

2. "Посмотрел бы образующий сверточный кодер-декодер. Там, конечно, сложно так витьевато поломать, но хотя бы, что все лежит рядом с теоретическими пределами." - вот тут не понял, что такое образующий сверточный кодек и как проверить, что все лежит с теоретическими пределами?

3. В этой же системе Декодер Витерби работает очень даже здорово, все его BER-ы входят с хорошим запасом в маску по Витерби. А вот может ли демодулятор подшумливать на S/N при 3 дб... вот тут как проверить?

 

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

[Grumbler_2002 0]

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

 

Сам я применял tail-biting CTC с полным декодированием и с декодированием "скользящим" окном. Разницы между ними практически не было, но была исследовательская работа по определению величины перекрытия окна и анализу спектральных свойств синтезированных кодов.

[Serg76 0]

.

[andyp 9]

Еще есть характерная особенность, что при достижении BER в 10^-7 появляется шумовая полка.. BER в нее упирается и уже не зависит от S/N.

 

Так это ж характерная особенность турбо-кодов. В них всегда есть слова с маленьким весом, которые изредка портятся - событие маловероятное, но случающееся. Таков уж спектр кода. Вон у народа тоже дуобинарный код и полка на уровне 1e-7 примерно:

http://koasas.kaist.ac.kr/bitstream/10203/...4445%5B1%5D.pdf

 

Гугл на запрос turbo code noise floor выбрасывает море информации.

 

 

PS Если крутизна кривой BER соответствует ожидаемой в теории, я бы перепроверил все условия эксперимента (правильное ли количество шума подается, сколько добавляет квантователь на входе и т.п.).

Изменено 3 апреля, 2014 пользователем andyp

[Dr.Alex 0]

Так это ж характерная особенность турбо-кодов.

 

Нельзя так говорить. Еррор флор может быть особенностью какой-то конкретной реализации кода, но не всех турбокодов вообще. Обсуждаемый код мне неизвестен, но если в доке еррор флора на графике не видно, то его и не должно быть..

[FatRobot 0]

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

 

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

 

Что касается демодулятора:

- для начала демодулятор хорошо бы проверить и отладить, если нет возможности работать без него

 

потом:

- определяете чувствительность по любому критерию

- ставите сигнал на 20 дБ выше уровня чувствительности. демодулятор уже влиять не должен. проверяете это прогоном: ошибок быть не должно

- добавляете шум от внешнего генератора.

 

2. "Посмотрел бы образующий сверточный кодер-декодер. Там, конечно, сложно так витьевато поломать, но хотя бы, что все лежит рядом с теоретическими пределами." - вот тут не понял, что такое образующий сверточный кодек и как проверить, что все лежит с теоретическими пределами?

3. В этой же системе Декодер Витерби работает очень даже здорово, все его BER-ы входят с хорошим запасом в маску по Витерби. А вот может ли демодулятор подшумливать на S/N при 3 дб... вот тут как проверить?

[andyp 9]

Нельзя так говорить. Еррор флор может быть особенностью какой-то конкретной реализации кода, но не всех турбокодов вообще. Обсуждаемый код мне неизвестен, но если в доке еррор флора на графике не видно, то его и не должно быть..

 

Могу только посоветовать ознакомиться со следующей статьей:

L. C. Perez, J. Seghers, and D. J. Costello, “A distance spectrum interpretation of turbo codes,” IEEE Trans. Inform. Theory, vol. 42, pp.1698–1709, Nov. 1996

http://wireless.ece.ufl.edu/eel6550/lit/Tu...um_Costello.pdf

 

Там написано, чем определяется асимптотика кривой BER любого турбо-кода при высоких-средних SNR и почему в графике BER присутствует waterfall region на низких SNR.

[Neznaika 0]

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

 

Сам я применял tail-biting CTC с полным декодированием и с декодированием "скользящим" окном. Разницы между ними практически не было, но была исследовательская работа по определению величины перекрытия окна и анализу спектральных свойств синтезированных кодов.

 

При моделировании с функцией randG неоднократно рассматривал мягкие решения. Как правило если после первой итерации наблюдается какое то число ошибок, то в дальнейшем приблизительно с коэффициентом 2-3 оно снижается до 0... вот например результат: 61 14 6 4 - итог 4 итераций... причем те самые 4 пропущенные ошибки прошли сквозь все операции без исправления. Изначально использовал архитектуру из одной статьи, где на второй SISO подавались только LLR с первого SISO и проверочные мягкие решения для 2-го SISO. Система исправляла, но из-за аналогичного недобора в S/N.. решил использовать стандартный вариант с добавлением перемешенных входных данных, те ошибки которые наблюдались в блоках в первом варианте ушли, но декодер хоть и стал работать лучше, но не намного. Буквально только что проделал еще некоторые исследования с LLR.

Например на входе пара мягких 4-битных решений (доп. код) ( A,B )=(x"b",x"f"), без шума д.б. (1,1). LLR (11 бит) для нее по полуитерациям:

Ит.1 {LLR(01),LLR(10),LLR(11)}: {x"000",x"030",x"000"} {x"7f8",x"02c",x"000"}

Ит.2 {LLR(01),LLR(10),LLR(11)}: {x"7fc",x"018",x"018"} {x"7f0",x"018",x"034"}

Ит.3 {LLR(01),LLR(10),LLR(11)}: {x"7e0",x"024",x"044"} {x"7e8",x"00c",x"054"}

Ит.4 {LLR(01),LLR(10),LLR(11)}: {x"7d0",x"7f0",x"050"} {x"00c",x"014",x"094"}

Решения принимаются по значениям в доп. коде. Видно, что первоначальная операция определяет 10, но к 4-ой операции получаем 11, причем LLR(11) в 7 раз больше, чем LLR(10). Вроде бы неплохая сходимость.

Стал добавлять уровень шума до тех пор пока декодер не ошибся в блоке, причем по итерациям выдал ошибок: 9 6 4 5. Посмотрел LLR ошибочных бит. Без шума пара (0,1):

Ит.1 {LLR(01),LLR(10),LLR(11)}: {x"008",x"008",x"014"} {x"008",x"000",x"01c"}

Ит.2 {LLR(01),LLR(10),LLR(11)}: {x"004",x"004",x"010"} {x"7f0",x"7e8",x"018"}

Ит.3 {LLR(01),LLR(10),LLR(11)}: {x"004",x"7ec",x"024"} {x"000",x"7fc",x"02c"}

Ит.4 {LLR(01),LLR(10),LLR(11)}: {x"008",x"000",x"02c"} {x"00c",x"7e4",x"014"}

Вроде бы сходится, но очень медленно... к 4-ой итерации ошибка - вместо (0,1) - (1,1), решил добавить коэффициент 0.5 перед внешней информацией. При том же отношении С/Ш декодер не ошибся и выдал по итерациям: 11 4 2 0. Глянул LLR той же пары...

Ит.1 {LLR(01),LLR(10),LLR(11)}: {x"008",x"008",x"014"} {x"00c",x"000",x"01c"}

Ит.2 {LLR(01),LLR(10),LLR(11)}: {x"008",x"004",x"00c"} {x"7f4",x"7ec",x"010"}

Ит.3 {LLR(01),LLR(10),LLR(11)}: {x"00c",x"004",x"010"} {x"004",x"7f0",x"00c"}

Ит.4 {LLR(01),LLR(10),LLR(11)}: {x"018",x"00c",x"014"} {x"008",x"7e4",x"000"}

---

Ит.8 {LLR(01),LLR(10),LLR(11)}: ------- {x"010",x"7e0",x"7f0"}

Не ошибся и сходимость видна, ввел этот коэффициент и в проекте, но все заработало гораздо хуже. Вообщем я снова подвис.

Что касается интерливера/деинтерливера... то вчера успел проверить только интерливер, и ручкам посчитал и в симуляторе адреса перепроверил, все верно....

А что за tail-biting CTC такой? Там что то с цикличными состояниями кодера же связано? Я тупо в декодере использую последние значения рекурсий предыдущей итерации для последующей итерации. Для чего это надо? И куда вкрутить?

 

Могу только посоветовать ознакомиться со следующей статьей:

L. C. Perez, J. Seghers, and D. J. Costello, ”A distance spectrum interpretation of turbo codes,” IEEE Trans. Inform. Theory, vol. 42, pp.1698–1709, Nov. 1996

http://wireless.ece.ufl.edu/eel6550/lit/Tu...um_Costello.pdf

 

Там написано, чем определяется асимптотика кривой BER любого турбо-кода при высоких-средних SNR и почему в графике BER присутствует waterfall region на низких SNR.

 

Спасибо, продуктивная статья.. напоминает мой случай... но только диапазоны величин S/N другие... в статье около 1-2 дб... я же застЬял на 1-2 дБ выше... Но формы кривых похожи...

 

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

 

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

Я понял, спасибо.. хорошая идея для проверки перемежителей)

 

Что касается демодулятора:

- для начала демодулятор хорошо бы проверить и отладить, если нет возможности работать без него

 

потом:

- определяете чувствительность по любому критерию

- ставите сигнал на 20 дБ выше уровня чувствительности. демодулятор уже влиять не должен. проверяете это прогоном: ошибок быть не должно

- добавляете шум от внешнего генератора.

Без демодулятора скорее всего не получится, надо много железа переворотить, чтобы выбросить его из цепи. Чувствительность демодулятора около -85дБм... уровень сигнала около -70 дбм, я думаю демодулятор не должен ничего серьезного вносить. Есть конечно на 8PSK и 16QAM легкие раскачки фазы, но они на глаз малы, есть слабая размазанность точек без шумов, но тоже на мой взгляд ничего серьезного.

 

Изменено 4 апреля, 2014 пользователем Neznaika