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

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

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

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

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

Сообщение отредактировал Coder2009 - Aug 10 2009, 13:09

Не должно, у меня при моделировании такой конфигурации получается следующее:
Eb/No = 2,5 дБ; Pb вых = 1,2e-6; Pb вх = 3,4e-2
т.е. можно сказать, что ошибок на выходе практически нет

Правило 3 сигма слышали? 0.2*3 = 0.6 естественно ожидать, что отсчеты шума будут от -0.6 до 0.6 и очень редко вылетать за этот диапазон.

http://www.encyclopediaofmath.org/index.php/Three-sigma_rule

PS Чтобы минимально проверить генератор можно гистограмму построить и проверить, что получается знакомый гауссовский колокол. Но если охота всякие 1e-7 ловить, то лучше пользоваться генератором случайных чисел хорошего качества и хорошим алгоритмом для генерации нормального распределения.

Сообщение отредактировал andyp - Apr 10 2014, 11:54

О правиле 3 сигм не слышал А вот то, что 2-м аргументом выступает среднее квадратичное значение, это где то видел. Я попробовал туда подставлять (0.4)^2 и получил значения (-0.4, +0.4), надеюсь что с нормальным распределением...

Сегодня пол дня мучил свой модем, сравнивая BERы (по внутренним измерителям и используя контрольный внешний) в тех же режимах, что у импортного. Мой модем ничуть ему не уступал, включал и выключал Витерби, смотрел без кодирования... все BER-ы идентичны... кроме TPC

Что касается кодовых слов... приведу 3 варианта мной полученных с помощью модели на Си (возможны опечатки):

1. Входной сигнал x"87" из примера к стандарту для N=64 и N=864 (кодовое слово идентично получилось)
A=x"99", x"99", x"99"...
B=x"33", x"33", x"33"...
W1=x"55", x"55", x"55"...
Y1=x"33", x"33", x"33"...
W2=x"aa", x"aa", x"aa"...
Y2=x"66", x"66", x"66"...
Кодовое слово для R=1/2:
I(A)=x"99", x"99", x"99"... I(Y1)=x"33", x"33", x"33"...
Q(B )=x"33", x"33", x"33"...Q(Y2)=x"66", x"66", x"66"...

2. Входной сигнал x"87" & b"10" для N=64
A=x"9" & '1', ...
B=x"3" & '0', ...
W1=x"b9", x"20", x"d5", x"0f", x"37", x"24", x"1a", x"a1"
Y1=x"ab", x"c3", x"23", x"6f", x"95", x"78", x"64", x"6d"
W2=x"99", x"ab", x"7f", x"ff", x"f8", x"7b", x"84", x"92"
Y2=x"67", x"b5", x"ec", x"b2", x"cd", x"72", x"9d", x"f7"
Кодовое слово для R=1/2:
I(A)=x"9c"... I(Y1)=x"ab"...
Q(B )=x"31"...Q(Y2)=x"67"...

3. Входной сигнал x"87" & b"10" для N=864
A=x"9" & '1', ...
B=x"3" & '0', ...
W1=x"83", x"54"...
Y1=x"0c", x"8d"...
W2=x"94", x"60"...
Y2=x"78", x"09"...
Кодовое слово для R=1/2:
I(A)=x"9c", x"e7"... I(Y1)=x"0c", x"8d"...
Q(B )=x"31", x"8c"...Q(Y2)=x"78", x"09"...

Что касается измерений в модели:
Взял N=64 и R=1/2. Пропустил через кодек около 10000 бит с шумом от randG, Pb вх=3.7*10^-2, получил BER=0, ни на одной из итераций не было допущено ошибок. Не уже ли глюк на VHDL закрался... из-за джиттера тактового сигнала или где-то сигнал управления буферами обрезается при живых клоках. В симуляторе VHDL для N=864... сравнивал по итерациям LLR с моделью на Си... совпадало до последнего бита... Надо снова все перепроверить...

Сообщение отредактировал Neznaika - Apr 10 2014, 11:08

Ну так 0.4^2 * 3 = 0.48 - все должно в этих пределах быть. То, что второй аргумент - именно стандартное отклонение написано у Вас по ссылке

http://delphi.scps.ru/math/math5301.htm

я так понимаю, что информационная часть кодового слова представляет собой меандр, т.е. "10101010..." в битовом виде? если так, то это несовсем удачный выбор как для декодера, там и для модема в целом. в таком случае первая половина проверки будет содержать "единицы" - "11111111...", а вторая половина - обратный меандр - "01010101" . я Вам предлагаю для сравнения свое кодовое слово, 256 бит которого выглядят следующим образом:

"000110010011111001010110100001011111011100011100001100100100100010101101101
100111110110110101000011011011111000101101100001001110111101011100101011010101011
011010101100000100001010011011111110100010011101010011000011010001111110110100111
1111110001101101100"

Сергей! Не могли бы вы немного пояснить, где что в вашем кодовом слове. Я понимаю это N=64 и R=1/2... а само кодовое слово представляет последовательность, если привязываться к дуо-бинарному коду (A,B,W,Y): A0,B0,A1,B1,A2,B2.. A63,B63, Y10,Y20,Y11,Y21....Y163,Y263. Так? И сформировано оно с учетом состояния цикла двух кодеров? Если, да, то у меня все не так

В моем примере я расписал все биты в соответствии с названиями бит в стандарте...

2. Входной сигнал x"87" & b"10" для N=64
A=x"9" & '1', ...
B=x"3" & '0', ...
W1=x"b9", x"20", x"d5", x"0f", x"37", x"24", x"1a", x"a1"
Y1=x"ab", x"c3", x"23", x"6f", x"95", x"78", x"64", x"6d"
W2=x"99", x"ab", x"7f", x"ff", x"f8", x"7b", x"84", x"92"
Y2=x"67", x"b5", x"ec", x"b2", x"cd", x"72", x"9d", x"f7"
Кодовое слово для R=1/2:
I(A)=x"9c"... I(Y1)=x"ab"...
Q(B )=x"31"...Q(Y2)=x"67"...

Т.е... А и B - это пары информационной последовательности. Если представить битовую последовательность информационного блока, то она будет иметь вид A0,B0,A1,B1,A2,B2.. A63,B63 или согласно тесту, где A0,A1,..A4=b"10011", а B0,B1,..B4=b"00110"... в итоге получаем:
b"1000011110,1000011110..." или x"87" & b"10", x"87" & b"10"... Я тестовый сигнал сделал периодическим, чтобы легче было его проверять и воспроизводить визуально... ну и использовал 16-ичное представление тоже с этой целью... Извините, что не очевидно расписал свой тест

Не получается у меня по Вашему примеру, проверочные биты не совпадают. Во-первых, проверка формируется на основании состояний двух кодеров С1 и С2, соответственно, для прямой и перемеженной (и попарно инвертированной) информационной последовательностей. Во-вторых, для скорости 1/2 выход W перфоратора не используется, на выходе будут присутствовать только Y проверочные биты.

В моем примере я привел Вам все биты кодового слова, где первая половина соответствует входной информационной последовательности А(0), В(0), ..., А(N-1), В(N-1), а вторая половина состоит из проверочной части Y1(N), Y2(N), ..., Y1(2*N-1), Y2(2*N-1), полученной на основе прямой информ. последовательности ( длина будет рвна четверти от общей длины всего кодового слова, т.е. 64 бита) и перемеженной последовательности ( ее длина тоже будет составлять 64 бита). Итого получаем 128 + 64 + 64 = 256

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

А у вас получается кодовое слово примера из стандарта, где тестовый сигнал x"87", x"87"... я как раз из-за него определил, что изначально перестановки для интерливера у меня были сделаны не верно и скорректировал их. В первом примере, который я привел, получается так же как и в стандарте. У вас тоже сходится с его примером? Просто очень похожая ситуация к которой я пришел чуть ранее обнаружив, что есть расхождения моего кодового слова с кодовым словом из стандарта именно в проверочных битах Y2.

Выложите стандарт с этим примером

Конечно... вот страница 39...
http://www.etsi.org/deliver/etsi_tr/101700...790v010401p.pdf

Хммм...., вот это уже интересно, с этим примером не сходится )))

Ура! Спешу поделиться хорошей новостью) Благодарю, Сергей, за помощь) На QPSK, R=1/2, S/N=3.2 дБ BER=0!!!!! На S/N=2.5дБ BER=8*10^-7. Как здорово, что вы попросили выложить этот стандарт, рядом с примером обратил внимание на странице 40 на абзац:

Measurements, using samples from a real demodulator with Automatic Gain Control, have put into evidence that the
position of the "sample clouds" within the quantizer range could be optimized for Turbo decoding. One implementation
uses the following rule-of-thumb: "multiply the analogue samples of the demodulator by a constant so that after 4-bit
quantization, the average of the unsigned values is equal to Rate Ч 8, Rate being the Turbo code rate (6/7, 4/5, 3/4,
etc.)".

Про это масштабирование натыкался 2 недели назад, изучая документацию на AHA4540, но решили, что оно не очень важно и не стали корректировать. Сегодня же снова уткнулся в этот текст и от безысходности решили ввести этот коэффициент. Декодер тут же откликнулся с благодарностью, выдав нужную BER. Ввели для R=1/2 коэффициент 1.5. А вот R=3/4 заработало хуже, чем было, коэффициент то 1.5 остался, нужен видимо другой. Похоже все-таки здесь причина))) Спасибо, еще раз! А то я уже стал унывать, а тут такая поддержка. Вы очень меня подзарядили и с шашкой на голо бросившись на декодер, удалось таки нанести ему брешь в непоколебимую броню! Ура! Ура! Ура!)))

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

Сообщение отредактировал Neznaika - Apr 11 2014, 09:16

Я рад, что Вы рады, поздравляю ))), но по характеристикам под S/N я так понимаю подразумевается Eb/No, а то как-то круто получается?

еще вопросик, немного отойду от темы: с LDPC (DVB-S2) получилось?

Да, конечно Eb/N0) С LDPC по DVB-S мне удалось разобраться в тонкостях реализации... я остановился на пол пути, отвлекшись на TPC. Кодер у меня реализован в моделе и на VHDL... а вот декодер... дошел только до отладки блоков FU, которые вычисляют метрики ветвей в двух режимах. Самое сложное было понять организацию памяти для сохранения метрик и как работает сдвигатель Барреля, остальное пока не вызывает вопросов кроме одного маленького, но пока не буду на него обращать внимания. По-моему не очень существенен) Но вот еже ли не заработает?...)

Всем привет) Застьял на измерениях BER) Ситуация следующая... меряю BER BPSK и QPSK без кодирования - все здорово как в книжке. Включаю TPC-кодек R=1/2 и меряю BER систематических данных без декодирования, т.е. вычленяю из кодового слова информационные биты и подаю их на BER-тестер. BER-тестер выдает BER на 1.5-2 дБ хуже, чем должен. Прогонял свой тестовый сигнал, посмотрел как разбросаны ошибки - никакой закономерности не увидел, их много и размазаны. Без шума ошибки исчезают. Пробовал делать искусственный джиттер приемника, делая скорости на передачу и прием немного разные - ошибок нет. Я подвис(