Коды БЧХ, Вопросы по алгоритмам декодирования Опции

[des00]

Гуру кодирования, просвятите по теме

Потребовалось мне для проекта сделать БЧХ декодер работающий в поле GF(2), реализовал его по алгоритму Берлекэмпа-Месси приведенному на рисунке. Мне интересно, чем определяется необходимость последней проверки алгоритма перед процедурой Ченя(на рисунке выделено)? Ведь для бинарных БЧХ кодов четные невязки всегда будут равны нулю, а на нечетных проходах, по блок-схеме алгоритма, мы всегда попадаем на изменение длинны и степени полинома локатора ошибок. Т.е. эта проверка ничего не определяет. Тогда зачем она нужна? Или такая ситуация возможна только для не бинарных кодов?

И вопрос по алгоритму Евклида. Во всех книгах написано что он лучше подходит для аппаратной реализации, чем алгоритм Берлекэмпа-Месси, из-за своей регулярной структуры. Но один из шагов алгоритма деление полинома на полином. В железе же это делается с помощью регистров с линейными обратными связями, что приводит к многотактному делению и появлению лишних задержек, что ИМХО не айс. Так в чем же его преимущество перед алгоритмом Берлекэмпа-Месси ?

Спасибо.

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

 

[des00]

Купить усилитель на 3 дБ мощнее %)

Это точно не пойдет

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

я сильно ограничен по ресурсам, у меня на кодер/декодер есть около 1000 плиток(чем меньше, тем лучше). Мне нужно два декодера {255,233,4} на 200Мб/с и {127, 64, 10} на 2Мб/с. ИМХО на таких длинах TCM/LDPC и т.д. это как из пушки по воробьям.

Конечно, и в этом случае можно использовать декодер БЧХ для ДСК, применяя алгоритмы Чейза или декодирование по МОР (Форни.)

Хотя бы мягкое декодирование БЧХ по алгоритму Чейза используйте.

Доделаю жесткое, комитнусь и порою книги на эту тему %)

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

вроде как выбрал, надеюсь не прогадал %)

ЗЫ. А по определению примитивных полиномов можете что нить подсказать? Спасибо %)

[vadimuzzz]

А по определению примитивных полиномов можете что нить подсказать?

нужно разложить x^n - 1 на простые множители. примитивный полином - это полином минимальной степени, т.ч. его корень alpha обладает свойством, что его степени покрывают все поле (т.е. alpha - порождающий элемент поля).

[des00]

нужно разложить x^n - 1 на простые множители. примитивный полином - это полином минимальной степени, т.ч. его корень alpha обладает свойством, что его степени покрывают все поле (т.е. alpha - порождающий элемент поля).

это то понятно, вопрос был не что делать, а как делать? %) Где можно почерпнуть алгоритм разложения на простые множители? И алгоритм нахождения НОК от них для генераторного полинома.

UPD. Конечно можно сгенерить всё в матлабе и копипастом перенести в код. Но интересно написать функции генерации кода БЧХ на SV, которые будут определять всю структуру (все функции кроме генерации генераторного полинома на SV есть и работают, ква таки сила), чтобы не зависеть ни от каких генераторов.

[des00]

UPD. Конечно можно сгенерить всё в матлабе и копипастом перенести в код. Но интересно написать функции генерации кода БЧХ на SV, которые будут определять всю структуру (все функции кроме генерации генераторного полинома на SV есть и работают, ква таки сила), чтобы не зависеть ни от каких генераторов.

сорцы выложены тут автоматическое определение генераторного полинома еще не допилил %)

Спасибо.
Извините, забыл про ваш вопрос. Интересующие Вас минимальные многочлены можно
взять из таблицы в конце книжки Питерсона и Уэлдона. Она есть в и-нете.

вот что странно, в Си коде, который я приводил функция генерации генераторного полинома

CODE

void gen_poly()
/*
* Compute the generator polynomial of a binary BCH code. Fist generate the
* cycle sets modulo 2**m - 1, cycle[][] = (i, 2*i, 4*i, ..., 2^l*i). Then
* determine those cycle sets that contain integers in the set of (d-1)
* consecutive integers {1..(d-1)}. The generator polynomial is calculated
* as the product of linear factors of the form (x+alpha^i), for every i in
* the above cycle sets.
*/
{
register int i, ii, jj, ll, kaux;
register int test, aux, nocycles, root, noterms, rdncy;
int cycle[1024][21], size[1024], min[1024], zeros[1024];

/* Generate cycle sets modulo n, n = 2**m - 1 */
cycle[0][0] = 0;
size[0] = 1;
cycle[1][0] = 1;
size[1] = 1;
jj = 1; /* cycle set index */
if (m > 9) {
printf("Computing cycle sets modulo %d\n", n);
printf("(This may take some time)...\n");
}
do {
/* Generate the jj-th cycle set */
ii = 0;
do {
ii++;
cycle[jj][ii] = (cycle[jj][ii - 1] * 2) % n;
size[jj]++;
aux = (cycle[jj][ii] * 2) % n;
} while (aux != cycle[jj][0]);
/* Next cycle set representative */
ll = 0;
do {
ll++;
test = 0;
for (ii = 1; ((ii <= jj) && (!test)); ii++)
/* Examine previous cycle sets */
for (kaux = 0; ((kaux < size[ii]) && (!test)); kaux++)
if (ll == cycle[ii][kaux])
test = 1;
} while ((test) && (ll < (n - 1)));
if (!(test)) {
jj++; /* next cycle set index */
cycle[jj][0] = ll;
size[jj] = 1;
}
} while (ll < (n - 1));
nocycles = jj; /* number of cycle sets modulo n */

/*
printf("Enter the error correcting capability, t: ");
scanf("%d", &t);
*/
t = 3;

d = 2 * t + 1;

/* Search for roots 1, 2, ..., d-1 in cycle sets */
kaux = 0;
rdncy = 0;
for (ii = 1; ii <= nocycles; ii++) {
min[kaux] = 0;
test = 0;
for (jj = 0; ((jj < size[ii]) && (!test)); jj++)
for (root = 1; ((root < d) && (!test)); root++)
if (root == cycle[ii][jj]) {
test = 1;
min[kaux] = ii;
}
if (min[kaux]) {
rdncy += size[min[kaux]];
kaux++;
}
}
noterms = kaux;
kaux = 1;
for (ii = 0; ii < noterms; ii++)
for (jj = 0; jj < size[min[ii]]; jj++) {
zeros[kaux] = cycle[min[ii]][jj];
kaux++;
}

k = length - rdncy;

if (k<0)
{
printf("Parameters invalid!\n");
// exit(0);
return ;
}

printf("This is a (%d, %d, %d) binary BCH code\n", length, k, d);

/* Compute the generator polynomial */
g[0] = alpha_to[zeros[1]];
g[1] = 1; /* g(x) = (X + zeros[1]) initially */
for (ii = 2; ii <= rdncy; ii++) {
g[ii] = 1;
for (jj = ii - 1; jj > 0; jj--)
if (g[jj] != 0)
g[jj] = g[jj - 1] ^ alpha_to[(index_of[g[jj]] + zeros[ii]) % n];
else
g[jj] = g[jj - 1];
g[0] = alpha_to[(index_of[g[0]] + zeros[ii]) % n];
/*
printf("Generator polynomial:\ng(x) = ");
for (i = 0; i <= 31; i++) {
printf("%d", g[i]);
}
printf("\n");
*/
}
printf("Generator polynomial:\ng(x) = ");
for (ii = 0; ii <= rdncy; ii++) {
printf("%d", g[ii]);
if (ii && ((ii % 50) == 0))
printf("\n");
}
printf("\n");
}

явно показывает что никакие таблицы не используются. Все вычисления производятся на лету. Надо будет еще раз к ней подойти до полной ясности %)