Никто не находил/вычислял таблицы полиномов битов четности для всего диапазона скоростей/размеров кодов ARJ4A из оранжевой книги? Поделитесь, что бы с протографами не заморачиваться

По FLEX известно, что интерливер строится на основе Dithered Relative Prime алгоритма.
Нажмите для просмотра прикрепленного файла

Спасибо, теперь много понятнее. Ндя, интерливер для не ищущих легких путей. Придется таблицы использовать. Не до конца понятно использование различных решеток. Вроде как там структура внутреннего и внешнего кода фиксирована. Откуда разные решетки ?

Патент описывает некий турбоподобный код с хорошей гибкостью в плане изменения скорости кодирования. Внешний и внутренний коды, описанные в нём, отличаются от применяемых в FLDPC, поэтому я не уделял им внимания. В FLDPC используются два простейших кодера: внешний - 1+D, внутренний 1/1+D. Алгоритм их декодирования детально описан в статье, прикрепленной des00. Алгоритм декодирования подобных кодов можно посмотреть в матлабе, в хелпе SCCC, там свёрточники немного сложнее, но суть такая же.
PS. По скорости - автор статьи утверждает, что на virtex-II 8000 c тактовой 100 МГц они добились 300 Мбит/с с 10 итерациями.

Раскурил патент по запчастям

Похоже это описание FLEX кода, более прошаренного чем F-LDPC в плане noise floor. Но за это нужно заплатить ресурсом декодеров.

Если делать скользящее окно то да, это возможно. Правда тут все упирается в возможность реализации collision free интерливера.

В целом, архитектура этого кодека мне понятна. Параллельный MAP движок, collsion free интерливер и математика из CNODE движка LDPC для декодирования SPC. Спасибо за инфу !

А вы делали этот кодек? Использовали свой интерливер или из патента? Можете поделиться эталонными закодированными последовательностями для блоков разной длинны? Эталонного сравнения ради.

Изучая ссылки на статьи, наткнулся вот на такую книгу Turbo-like Codes Design for High Speed Decoding Может мимо кого пробегала. Прошу поделиться

http://bookfi.net/md5/4D7D9B149550E1F6803A197B6AEBDCF5

В статье A_New_Class_of_Turbo_like_Codes_with_Universally_Good_Performance_and_High_Speed
_Decoding, прикрепленной выше, описывается алгоритм мягкого декодирования интегрирующего кодера 1/1+D. В описание утверждается, что если подать на информационный вход нули, а на проверочный - полученные мягкие решения проверок, то на одном из выходов декодера мы получим исходную информационную последовательность, а на втором обновленную проверочную.
Что, собственно, я и делаю в прикрепленных м-файлах, но в некоторых случаях информационная последовательность действительно идентична исходной, а в некоторых появляется ошибка в первом бите.
Может быть у кого-то получится реализовать алгоритм без этой фичи

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


Вы про страницу 5 и формулы 11a - 11d? Там же вроде классические прямая и обратные рекурсии MAP алгоритма.

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

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

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

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


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

Туплю. В приложении алгоритм 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)

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

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

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

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

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

Чем больше смотрю на граф Таннера F-LDPC, тем больше кажется что метод декодирования SCCC с внутренним и внешним декодером тут не применимы. По той причине что:
1. Код систематический. Биты проверки - прореженный выход с Inner кодера.
2. Outer код + интерливер + SPC код - задает связь систематических битов со входом Inner кодера. Никакой решетки для декодирования тут нет. Посчитали вероятность на входе Inner декодера, уточнили ее в этом декодере и раскидали обратно, получив extrinsic метрики для следующего шага или выходные решения.

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

Не совсем. Разберем по частям, как работает кодер 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 коде

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

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

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

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

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

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

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


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


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

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


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

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

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

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

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

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

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

В приложении 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 классически и сравнить.

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

Спасибо.

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

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

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