БЧХ декодер - поясните Опции

[alexPec]

Добрый день всем. Догнали и меня БЧХ коды. Делаю декодер, аппаратная реализация, перечитал кучу книжек, все равно непонятные моменты остались. Наворочены формулы, индексы - не поймешь, а в реализации все проще как оказывается. Такие вопросы, подскажите пожалуйста:

1. Если у меня 60 проверочных бит (исправляет 6 ошибок) - то у меня должно быть 60 бит синдрома ошибок?
2. Синдром вычисляем сдвиговым регистром (умножаем на порождающий полином). А вот дальше тупик. Что с ним делать?
Надо искать полином локаторов ошибок. Нашел реализацию процедуры ченя (картинка). Что есть что на ней непонятно, несколько раз прочитал- все равно не понятно. Кто имел дело с декодированием, наверняка все очевидно покажется.
3. Что такое альфа и лябда на картинке?
4. Чему равно t - количеству проверочных бит или общему количеству бит?
5. Написано все возможные положения ошибок проверяются последовательно - если у меня 560 бит всего, то я что, должен проверить 2^560 вариантов комбинаций ошибок? Что то нереально. Или по одной надо проверять последовательно?
6. Что делает квадрат на блок схеме с лябдой? Это регистр?

Если спросил что-то глупое- сразу извиняюсь, недавно в тему начал вникать, каша в голове

Эскизы прикрепленных изображений

 

[Fast]

спасибо, обнадежили, я думал, что гугл сломался ))
сделаю сам на C/C++ прототип, пару мес надеюсь хватит

[SKov]

сделаю сам на C/C++ прототип, пару мес надеюсь хватит

Не забудьте выложить в доступном месте
Если серьезно - пару месяцев уйдет на то, чтобы прочесть хотя бы 10 (лучше 30-50) статей и разобраться
с разновидностями декодеров и выбрать, что вам подходит по цвету и вкусу

[Fast]

Если серьезно - пару месяцев уйдет на то, чтобы прочесть хотя бы 10 (лучше 30-50) статей и разобраться с разновидностями декодеров и выбрать, что вам подходит по цвету и вкусу

ушло 2 часа на то, чтобы разобраться, что выбирать особо не из чего ))
пара удобоваримых для реализации алгоритмов для БЧХ (БМ и Евклида) и тройка для LDPC (мягкий BP, min-sum и класс многопороговых).
а если к вопросу подойти творчески, то внешний код БЧХ можно использовать лишь для обнаружения, исправляя все внутренним LDPC...

Не забудьте выложить в доступном месте

посмотрим

[SKov]

ушло 2 часа на то, чтобы разобраться, что выбирать особо не из чего ))
пара удобоваримых для реализации алгоритмов для БЧХ (БМ и Евклида) и тройка для LDPC (мягкий BP, min-sum и класс многопороговых).
а если к вопросу подойти творчески, то внешний код БЧХ можно использовать лишь для обнаружения, исправляя все внутренним LDPC...
посмотрим

У вас два часа ушло, чтобы выучить несколько красивых слов
Если Вы пишете про "мягкий BP" (а что, бывает жесткий?) и через запятую поминаете класс многопороговых алгоритмов - Вам еще разбираться и разбираться в этих хитросплетениях. И почему вы называете БЧХ внешним? Он там, скорее, внутренний
и предназначен не для обнаружения ошибок (LDPC и сам прекрасно все обнаруживает.)
В общем, "еще 5 тысяч ведер, и ключик будет ваш" )

[Fast]

У вас два часа ушло, чтобы выучить несколько красивых слов
Если Вы пишете про "мягкий BP" (а что, бывает жесткий?) и через запятую поминаете класс многопороговых алгоритмов - Вам еще разбираться и разбираться в этих хитросплетениях. И почему вы называете БЧХ внешним? Он там, скорее, внутренний
и предназначен не для обнаружения ошибок (LDPC и сам прекрасно все обнаруживает.)
В общем, "еще 5 тысяч ведер, и ключик будет ваш" )

мягкий BP - работающий по мягким решениям демодулятора, дающим начальные априорные вероятности для бит(символов)
термин мягкий употребляется по аналогии с мягким декодированием Витерби, или допустим мягким декодированием циклических кодов.
а что не понравилось во фразе класс МПД-алгоритмов ? это вообще-то целый табор вариантов формирования порогов и решающих схем исправления символов даже применительно к конкретному LDPC-коду, не считая алгоритмов MПД для двоичных/недвоичных, систематических/несист, блоковых/сверточных и т.д. кодов. Об этом есть фундаментальные труды Золотарева В.В.

если вести речь о конкретном стандарте DVB-S2, БЧХ все же внешний, ознакомьтесь повнимательнее
и может быть предназначен как для исправления, так и для обнаружения, в зависимости от схемы реализации декодера обощенного кода БЧХ-LDPC
т.е. по большому счету - это зависит от хотелок разработчика и с учетом характеристик канала связи.

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

Человек прав БЧХ - внешний, а LDPC - внутренний, более мощный, а вот по поводу многопороговых алгоритмов декодирования, то здесь с ним не соглашусь, для LDPC они не подходят, так как эти коды не соответсвуют условиям ортогональности.

http://www.mtdbest.iki.rssi.ru/

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

и какой же смысл несут термины внутренний-внешний, кроме того, что один код внутренний, а другой внешний ?

[SKov]

мягкий BP - работающий по мягким решениям демодулятора, дающим начальные априорные вероятности для бит(символов)

Это все понятно. Просто я хотел подчеркнуть, что выражение "мягкий BP" выдает с головой новичка в этой области.
Т.к. "жесткий" BP теоретически возможен, но я ни разу не встречал его применительно к LDPC.
Поэтому упоминание о мягкости BP мне показалось излишним.

термин мягкий употребляется по аналогии с мягким декодированием Витерби, или допустим мягким декодированием циклических кодов.

Декодер Витерби жесткий я встречал неоднократно. А вот жесткий BP - нет.
Если Вы встречали жесткий BP- с благодарностью приму от вас ссылку, как говорится, век живи - век учись.

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

Я вроде пытался ответить в предыдущем посте. Еще раз: характеристики МПД и BP абсолютно несравнимы
как по качеству декодироваия так и по сложности. Причем по качеству резкий перекос в одну сторону, а по сложности - в другую.

Об этом есть фундаментальные труды Золотарева В.В.

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

если вести речь о конкретном стандарте DVB-S2, БЧХ все же внешний,

Да я уже не спорю. Я просто хотел сказать, что сама конструкция совсем не каскадная в классическом смысле этого слова.
Понимаете, слово БЧХ кода является (информационной) частью кода LDPC и в этом смысле БЧХ находится
(в буквальном смысле) внутри слова LDPC. Поэтому хочется назвать его внутренним по отношению к LDPC;)

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

Это уже какая-то ерунда.

http://www.mtdbest.iki.rssi.ru/

Ой, вот только ссылок на МПД мне не надо! Увольте!!!

[Fast]

Это все понятно. Просто я хотел подчеркнуть, что выражение "мягкий BP" выдает с головой новичка в этой области.
Т.к. "жесткий" BP теоретически возможен, но я ни разу не встречал его применительно к LDPC.
Поэтому упоминание о мягкости BP мне показалось излишним.

BP никогда не делал, как и декодеры турбо-кодов. С последних проектов по TCM+констурукции Унгербоека прошло много лет, с момента, когда ручками прорешивал ПГЦ и БМА, строил порождающие и проверочные матрицы.., - еще больше. Поэтому современную терминологию, широко принятую в узких кругах, еще пока не освоил.

Я вроде пытался ответить в предыдущем посте. Еще раз: характеристики МПД и BP абсолютно несравнимы как по качеству декодироваия так и по сложности. Причем по качеству резкий перекос в одну сторону, а по сложности - в другую.

может вы не поняли, но я не сравнивал их по качеству и сложности.

Это уже какая-то ерунда.

а если хорошо подумать ? я сходу вижу три подхода
1. оба исправляют: LDPC-BP + БЧХ-БМА
2. LDPC оценивает,
- БЧХ исправляет методом усеченного перебора ранжированных по достоверности символов (по какому-то порогу достоверности)
- БЧХ исправляет Чейзом
- стираем 2t малодостоверных, БЧХ восстанавливает стирания
3. БЧХ оценивает (= считаем синдром)
1) LDPC-MinSum, исправляет
2) считаем синдром БЧХ,
синдром ненулевой => корректируем априорные вероятности (критерий пока не важен), идем к п.1

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

Ой, вот только ссылок на МПД мне не надо! Увольте!!!

ссылка вообще-то не вам была. увольняю )))

[SKov]

я сходу вижу три подхода
1. оба исправляют: LDPC-BP + БЧХ-БМА

Это наиболее разумный вариант. Я бы добавил, что БЧХ может и обнаруживать тяжелые ошибки,
если в обнаружении есть какой-то смысл.

2. LDPC оценивает,
- БЧХ исправляет методом усеченного перебора ранжированных по достоверности символов (по какому-то порогу достоверности)
- БЧХ исправляет Чейзом
- стираем 2t малодостоверных, БЧХ восстанавливает стирания
3. БЧХ оценивает (= считаем синдром)
1) LDPC-MinSum, исправляет
2) считаем синдром БЧХ,
синдром ненулевой => корректируем априорные вероятности (критерий пока не важен), идем к п.1

Это ерунда. ИМХО, конечно.

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

Предложить-то можно. Но делать не советую.

[Fast]

Это наиболее разумный вариант. Я бы добавил, что БЧХ может и обнаруживать тяжелые ошибки,
если в обнаружении есть какой-то смысл.

это не наиболее разумный вариант, а наиболее дубовый и худший по критерию вероятности ошибки декодирования. Ошибочное декодирование с выхода LDPC размножит ошибку, с которой может не справиться БЧХ в режиме исправления (декодируя в неправильное разрешенное КС).
По этой причине для декодирования вот таких вот составных кодов имеет смысл передавать на след. уровень не единственное решение декодера, а подмножество, М-список решений. п.2-3, которые вам кажутся ерундой, в упрощенном виде реализуют именно эту идею. У циклических кодов БЧХ очень мощная обнаруживающая способность, у LDPC исправляющая, на этом надо и играть.

умножитель в полях галуа вида variable by constant это ксор, определенных битов variable. вот эти определенные биты заранее рассчитываются и их маска сидит в "памяти".

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

[SKov]

это не наиболее разумный вариант, а наиболее дубовый и худший по критерию вероятности ошибки декодирования.

Худший по вероятности? Откуда такая уверенность?
Думаю, что это просто ваша смелая научная гипотеза.
Которая, вполне возможно, и не подтвердится.

Ошибочное декодирование с выхода LDPC размножит ошибку, с которой может не справиться БЧХ в режиме исправления (декодируя в неправильное разрешенное КС).

Если LDPC не справится, то в любом случае все пропало В типичной ошибочной ситуации у него на выходе будет
примерено то же, что и на выходе канала. Т.е. полная каша, разгрести которую не под силу никакому БЧХ.
Вы не понимаете. Там предусмотрен хилый БЧХ для подчистки мелкого "мусора" после LDPC (почитайте про error floor).
Ну и дополнительная возможность для обнаружения ошибок.
LDPC в ходе декодирования исправляет десятки и даже сотни ошибок, а БЧХ из этого стандарта всего 8 или 12 - сейчас точно не помню.
Но даже если бы там стоял мощный BЧХ, который вы декодировали бы по Чейзу или по Форни со стираниями,
он все равно и рядом не стоял бы с LDPC, работающем с непрерывным выходом канала.
Именно поэтому LDPC и ценят. А вы их все пытаетесь представить полноценными партнерами в этой связке. Это все равно,
что перечислить BP и МПД через запятую.

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

Идея богатая. Могу совершенно точно сказать, что вреда она точно не принесет.
А вот относительно заметной пользы - есть сомнения. Которые вы нам наверняка проясните после реализации в программе.
Ждем-с.

У циклических кодов БЧХ очень мощная обнаруживающая способность, у LDPC исправляющая, на этом надо и играть.

Смелая научная гипотеза. Очень смелая
LDPC и сам хорошо обнаруживает ошибки и редко ошибается в кодовое слово.
Чаще он находит "псевдослово" и на нем зацикливается, но при этом все равно обнаруживает его.
Сейчас с Вами пока не о чем спорить. Играйте. Пробуйте.
Когда начнете моделирование LDPC, для вас многое прояснится.

[Fast]

Худший по вероятности? Откуда такая уверенность?
Думаю, что это просто ваша смелая научная гипотеза.

лет 8 назад реализовывал связку TCM-код + CRC16, улучшив ЭВК около 0.6 дб относительно раздельного их декодирования. Как мне кажется, здесь тот же случай, только в профиль. Насколько правильно мы оценим подмножество малодостоверных символов на внутреннем коде LDPC, чтобы в него попало истинное КС, настолько больше шансов выбора из этого подмножества истинного КС внешним кодом БЧХ в режиме обнаружения.

Вы не понимаете. Там предусмотрен хилый БЧХ для подчистки мелкого "мусора" после LDPC (почитайте про error floor).
Ну и дополнительная возможность для обнаружения ошибок.
LDPC в ходе декодирования исправляет десятки и даже сотни ошибок, а БЧХ из этого стандарта всего 8 или 12 - сейчас точно не помню.
Но даже если бы там стоял мощный BЧХ, который вы декодировали бы по Чейзу или по Форни со стираниями,
он все равно и рядом не стоял бы с LDPC, работающем с непрерывным выходом канала....

Вы вообще-то совсем не поняли идею. Еще раз другими словами я ее передал выше. При декодировании составных кодов один из кодов можно использовать в режиме обнаружения, и лучше, чтобы это был код с меньшей исправляющей способностью и высокой обнаруживающей. т.е. в данном случае БЧХ. БЧХ будет исправлять по макс.правдоподобия, Чейзу или Форни уже выход LDPC, т.е. работать с подмножеством малодостоверных векторов.

а в целом да, пока не реализовал идею для конкретного случая, и не показал ЭВК, говорить со скептиками о ее состоятельности бесполезно.

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

спасибо, с HDL не очень дружу, но может разберусь если у себя затыки будут. Пока почти готов С/С++ прототип декодера БМА для укороченного РС(204,188) DVB-S, но тоже на задаваемый ручками полином и фикс. число ошибок. Хотел поглядеть на ваш, чтобы на БЧХ перенести на произв.полином и скорость
p.s. все, увидел с-пример Морелоса-Сарагосы