Хочу разобраться с расширенным кодом БЧХ(1020, 998).

Генератор кода g(x)= m1(x)*m3(x)*m5(x)*(x^2+1), где
m1(x) = x^10+x^3 + 1
m3(x) = x^10+x^3+x^2+x+1
m5(x) = x^10+x^8+x^3+x^2+1

Перелопатил тонны литературы.
В основном пишут про расширение линейного кода в терминах проверочной матрицы.
или что к g(x) добавляется множитель (x+1),
который есть ни что иное, как бит четности.

Как декодировать такой код нигде не написано.
(есть про расширенный Рид-Соломон - но это другое - там добавляется целый проверочный СИМВОЛ).
У Блейхута описание идет в частотной области. ничего не понятно.

В книге
"L.Hanzo, T.H.Liew, B.L.Yeap - Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Wireless Channels"
Декодирование расширенных коды довольно поднобно описано. Но там мягкое декодирование.
Какие-то манипуляции с аналоговым сигналом.
Жестокая жесть.
Мне в общем нужет жесткий декодер. Ну может быть с поддержкой стираний
(так как будет использоваться в составе каскадного кода).

Замечу, что (x^2+1) = (x+1)(x+1).
В чем смысл добавления двух одинаковых множителей?
Что делать с двумя дополнительными проверочными битами?

Занимаюсь ECC-кодами около года. Сделал классический декодер кодов Рида-Соломона и БЧХ.
Декодер нерасширенного БЧХ сделан как прототип к текущему проекту. g(x) = m1(x)*m3(x)*m5(x).
Это код БЧХ "в узком смысле" (narrow sense): lcm(min_poly(alpha(1)), ... , min_poly(alpha(6))).
Работает и выдает неплохую производительность.

Кодирование, как я понял, делается обычным порядком - в проверочные позиции записывается остаток от деления на g(x).
Вот как работать с расширенным кодом - непонятно.
Прошу помощи клуба.

Обычно добавляется один множитель. Откуда взялся квадрат - непонятно.
Возьмите свой старый проект (нерасширенного кода БЧХ). И без всяких полевых изворотов тупо добавьте проверку
на четность по всему кодовому слову (один проверочный бит). Декодируете все по старому (не учитывая новый проверочный бит).
После декодирования проверяете, сколько ошибок было исправлено. Если их было (d-1)/2, то проверяете , выполняется ли проверка на четность
после исправления найденных ошибок. Если нет - вы обнаружили неисправимую комбинацию ошибок.
Как-то так.

Из спецификации.


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

Если не секрет, из какой?


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

G.975.1 I9

Расширенные коды тем и отличаются, что увеличивают длину кодового слова.
Нулевой корень (вернее alpha(0)) - это просто код не "в узком смысле" (синдромы нумеруются не с 1).

Да, от прочитанного у меня какая-то каша в голове.

Добавление множителя (x+1)(x+1) дает не биты четности, а новые синдромы (причем, со значениями из GF(2)).

Добавление множителя к генератору, как я понял, называется "выбрасывание" ("expurgation").
То есть, часть прежних кодовых слов перестают считаться таковыми.
Возможно, это то, что мне нужно (хотя в спеках четко написано "extended code")...
Как мне объяснили, вся эта чехарда с расширениями-укорочениями задумана для обратной совместимости формата кадра с кодом RS(255,239). Думаю, что дописывать проверочные биты, чтобы их сразу выкинуть смысла нет.

Вызывают трудности два момента:
1) Что делать с дополнительным коэффициентом/коэффициентами синдрома, локатора и т.д.
2) Степени корней (с учетом дополнительного множителя) не всегда идут попорядку.
(x+1) - это минимальный многочлен alpha(0) (тут вроде всё нормально, но корень двойной).
Есть еще один код, с генератором
gh(x) = x^30*m1(x^-1)*m3(x^-1)*m5(x^-1)*(x^2+x+1).
Его корни: lcm(min_poly(alpha(1017)), ... , min_poly(alpha(1022))) = lcm(min_poly(alpha(-1)), ... , min_poly(alpha(-6))).
Но дополнительный множитель (x^2+x+1) - это минимальный многочлен alpha(341) и alpha(682).
В определении же кодов БЧХ четко сказано, что степени должны идти попорядку...

Не пойму что-то почему код БЧХ(1020,988) является расширенным (и в рекомендации, указанной в этой теме G.975 I.9 они именуются как extended BCH code)? Вроде как это укороченный код от БЧХ(1023, 991). Или в рекомендации как-то по-другому понимается понятие укороченного кода?

Сообщение отредактировал Gold777 - Nov 14 2012, 17:55

Кто нибудь выяснил, чем отличается расширенный код от обычного?

Почитал стандарт - остались непонятны два момента:

1) Как все-таки декодировать код с полиномом gh(x) = x^30*m1(x^-1)*m3(x^-1)*m5(x^-1)*(x^2+x+1)?
2) Как добыть проверочные биты pH и pS для первого и второго кодеров из той мутаты, которая там вместо проверочных бит?

Могу ошибаться, но:

Легко показать, что этот код является подкодом кода БЧХ с полиномомx x^30*m1(x^-1)*m3(x^-1)*m5(x^-1) - если кодовые слова делятся на gh(x), то они делятся и на x^30*m1(x^-1)*m3(x^-1)*m5(x^-1). Причем ,кодовое расстояние подкода осталось таким же как было у кода БЧХ (это уже не совсем очевидно, но про это написано в гугле при поиске BCH (1020, 988), где про него говорят, что он triple error correcting )

Таким образом, вырисовывается следующая схема декодирования:
1. декодируем кодовые слова декодером кода БЧХ, исправляющим 3 ошибки
2. в случае успешного декодирования проверяем на равенство нулю два синдрома S(a^341) и S(a^682) (фактически, это проверка на принадлежность слова подкоду) - ну или еще каким способом убеждаемся, что кодовое слово после исправления ошибок делится на (x^2+x+1)

ps на счет точного равенство кодового расстояния могу и наврать - для подкода оно могло увеличиться на 1

Спасибо, именно так сделал с первым полиномом g(x)= m1(x)*m3(x)*m5(x)*(x^2+1). Сгенерил полином функциями gfconv, сгенерил в матлабе тестовую последовательность, поделил на m1(x)*m3(x)*m5(x)*(x^2+1) и на x^30*m1(x^-1)*m3(x^-1)*m5(x^-1), получив две группы проверочных бит. В первом случае поступил как вы и советовали, а во втором смутило (x^-1) и (x^2+x+1).
И все-таки пока осталось непонятно как добыть проверочные биты.

Ну все эти x^-1 и x^30 имеют отношение к т.н. reciprocal polynomials. Про них неплохая статья в википедии со сслыками на еще более хорошую книжку Pless, Vera, Introduction to the Theory of Error Correcting Codes

статья из вики:
http://en.wikipedia.org/wiki/Reciprocal_polynomial

книжку можно скачать здесь
http://bookzz.org/md5/c2cdbc18909140a2918271ecfc07b452



Я этим стандартом не занимался, так что ничем особо помочь не могу.

Спасибо, вы и так очень помогли, пойду читать