Всем привет.

Хочу собрать 2D Block Turbo Code. Как работает понятно. Восстанавливаем строки и столбцы(если требуется востановление) в определенной последовательности
Хочу использовать упрощенный код Рида-Соломона без erasures.


http://wireless-e.ru/articles/technologies/2006_1_63.php


Мне непонятен момент с проверочными символами от проверочных. Это, что такое? Т.е. допустим, первая строка содержит проверочные символы для первого столбца проверочных кодов и первой строки проверочных кодов?

Перемежитель вообще нужно использовать? По этому вопросу единого мнения не нашел.

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


нет, он встроен в такой код

Т.е. "проверочные от проверочных" проверяют проверочные символы строк(оранжевый столбец справа) ?

да, если сначала кодируются строки

Понятно. Спасибо.

глупый вопрос, а зачем итеративное декодирование для кодов Р-С, если они в основном декодируются жестко?

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

конкретно в турбокодах они декодируются мягко. ЕМНИП, они немого хуже по характеристикам, чем БЧХ или Хемминга, но пропускная способность намного выше

известные практические схемы (стандарты) не приведете? декодирование, я так понимаю, по Чейзу?

Low-Complexity High-Rate Reed--Solomon Block Turbo Codes

http://ieeexplore.ieee.org/xpl/login.jsp?t...3341%2F04303371

вот нашел и практическую схему RS TPC с декодированием, как и предполагал, по Чейзу (метод 2)

Нажмите для просмотра прикрепленного файла

еще стоит поискать предыдущие авторов этой статьи, там д.б. более полные теоретические выкладки.

ага, спс. до этого имел дело только с TPC на базе Хемминга и БЧХ, ну еще плюс к этому проверка на четность

про РС не скажу, а про БЧХ по чейзу же не выгодно декодировать, фактически метод близкий к полному перебору, основанному на вероятности ошибки. Как я понимаю в 2D кодах кол-во вариантов будет дюже большим. В чем смысл ?


а у вас случайно нет доступа что бы эту статью скачать ?


Не то что бы я сомневаюсь в работоспособности такой схемы, просто непонимаю почему бы не взять другие итеративные коды с нормальным мягким решением. LDPC например %)

Та как-то не совсем хочется тратить 31$ на PDF.


У меня мысль появилась. Ведь в 2D матрице легко вычислить координаты ошибки. И если уж после нескольких итераций ошибки уже не исправляются, то подставить парочку раз рандомное число. Так хоть все перебирать не придется.

есть Fast Chase с частичным перебором, он субоптимальный (проигрыш в районе 0.5 дБ)

я в свое время не осилил

понятно, пойдем другим путем

У меня мысль появилась. Ведь в 2D матрице легко вычислить координаты ошибки. И если уж после нескольких итераций ошибки уже не исправляются, то подставить парочку раз рандомное число. Так хоть все перебирать не придется.

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

все уже украдено для нас

Обычно в методах итерационного декодирования используется критерий "ранней" остановки, т.е. после каждой
итерации проверяем наличие оставшихся ошибок (по синдрому, например) и в случае их отсутствия отказ от дальнейшего
декодирования.

Это естественно.

Но если ошибки перестали исправляться. Т.е. пакет сильно поврежден.

PS: Ничего хорошего из добавления списка не вышло. Это все равно, что тыкать пальцем в небо.

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

Результат. Проверял в VS2012

Нажмите для просмотра прикрепленного файла



Провел испытания с рандомной генерацией пакета и ошибок. Отловил такие случаи когда количество ошибок не уменьшается, но после парочки итераций пакет восстанавливается. Надо сказать случаи не такие уж и редкие. На 300-400 пакетов 1 случай.

это как раз то, о чем я говорил

Сейчас, в моей реализации, решения принимаются жестко.

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

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

Одним словом каскад.

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

Я исхожу из такого понимания.

Когда передатчик близок к приемнику. Шум не оказывает влияние на сигнал, либо оказывает незначительное влияние. В этом случае я не вижу смысла работать по мягкой схеме. Ведь очень высокая вероятность, что данные будут восстановлены после первого/второго прохода.

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

В итоге устройство будет быстро восстанавливать данные на близких и медленно на дальних.

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

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



это в каком канале (системе) рассматривается? для АБГШ все символы априори равновероятны, а мягкое декодирование (поправлюсь: мягкие решения) как раз и дает ответ на то, какой из символов наиболее достоверен.

Чето сомневаться начал в необходимости жестких решений. Смысла в таком каскаде особо нет((.



Я говорил чисто теоретически, в реальности наверное такого и не будет.

нет, ну почему же? просто мы не знаем Вашей ситуации, непонятно из каких соображений Вы остановили свой выбор именно на такой схеме FEC - RS TPC, может для Ваших целей стоит остановиться на более простой схеме, может быть достаточно будет даже жесткого декодирования? это исследовательская работа или реальный проект какой-то?

Я делаю для себя либу на будущее. Заодно и смотрю сколько какой алгоритм требует ресурсов.

В последнее время вожусь много с RF.

ок. тогда можно "поиграться" еще с TPC на базе Хемминга/БЧХ и как советовали еще LDPC, в настоящее время они более популярны.

Улучшил характеристики. Но еще тестирую

N - длина RS кодов
Er - количество ошибок

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

После делаю проход по строкам. Если в строке количество ошибок Err = N, то все ошибки помечаются как erasures и исправляются.


Пробовал Чейза(как я понял это Чейз), чтоб получить возможность исправлять ситуации Err = (N+1).
N ошибок помечаются как erasures а ошибка N+1 перебирается. Но этот метод оказался жутко медленным. В худшем случае требуется 255 итераций.

У Чейза есть 3 метода + модификации, между собой отличаются количеством сгенерированных пробных последовательностей и,следовательно, помехоустойчивостью. Как правило, используется метод 2, практически получаем метод максимального правдоподобия.

Как я понял.

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

если помеха повреждает только единичные биты, то зачем тогда РС код? перебирать надо только те комбинации, которые имеют всевозможные символы на определенном числе наименее достоверных позициях. например, для расширенного Хемминга этот список состоял из 16 пробных кодовых последовательностей, т.е. определялось 4 наименее достоверных символа (бита). для РС не знаю какое количество надо генерировать.

Почитайте про Чейза сами, в нем нет ничего сложного. Вот дока, которую Вам рекомендовали по быстрому Чейзу:

Нажмите для просмотра прикрепленного файла