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

[des00]

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

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

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

Спасибо.

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

 

[vadimuzzz]

не гуру, но:
1. да, для двоичных кодов БЧХ процедура проще, четные итерации можно пропустить. если эта картинка из Блейхута, то в главе 7.6 есть подробности.
2. в той же книге про алгоритм Евклида говорится: "считается, что он менее эффективен в практическом использовании"

[des00]

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

т.е. для двоичных кодов последнюю проверку (if deg(Lambda) == L) можно отбросить?

2. в той же книге про алгоритм Евклида говорится: "считается, что он менее эффективен в практическом использовании"

а вот Сарагоса с Кларком говорят что наоборот, для железа Евклид самое то. Вот мне и интересно почему %)

[vadimuzzz]

т.е. для двоичных кодов последнюю проверку (if deg(Lambda) == L) можно отбросить?

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

а вот Сарагоса с Кларком говорят что наоборот, для железа Евклид самое то. Вот мне и интересно почему %)

ну, они-то точно гуру

[des00]

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

1. неисправимую ошибку можно детектировать в процедуре ченя, когда количество найденных корней не совпадет с порядком локатора ошибок.
2. написал на сях алгоритм (на основе сорцов из сети), при количестве ошибок больше чем можно исправить дает выполнение этого равенства. Поэтому меня и заинтересовал этот момент. Чую что здесь что то не то (хотя может быть я просто в алгоритме ошибся %)).

UPD. Вот я ламер, неисправимая ошибка и количество неисправимых ошибок это же разные вещи %) Если я сделал правильные умозаключения, то для двоичных кодов эта проверка не нужна, т.к. для этих кодов ветка 2L > r-1 никогда не выполняется. Поэтому степень полинома локаторов изменяется одновременно с L.

[SKov]

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

Только для укороченных кодов. В остальных случаях Чень перебирает все элементы поля и среди них обязательно найдутся все корни полинома.

2. написал на сях алгоритм (на основе сорцов из сети), при количестве ошибок больше чем можно исправить дает выполнение этого равенства. Поэтому меня и заинтересовал этот момент. Чую что здесь что то не то (хотя может быть я просто в алгоритме ошибся %)).
UPD. Вот я ламер, неисправимая ошибка и количество неисправимых ошибок это же разные вещи %) Если я сделал правильные умозаключения, то для двоичных кодов эта проверка не нужна, т.к. для этих кодов ветка 2L > r-1 никогда не выполняется. Поэтому степень полинома локаторов изменяется одновременно с L.

Эта проверка редко, но срабатывает. Степень не всегда меняется одновременно с L.
Помоделируйте декодер и поймаете такую ситуацию.

[des00]

Только для укороченных кодов. В остальных случаях Чень перебирает все элементы поля и среди них обязательно найдутся все корни полинома.

Вот что странно, я использовал в качестве базы пример

Код

* Title:   Encoder/decoder for binary BCH codes in C (Version 3.1)
* Author:  Robert Morelos-Zaragoza

там используется следующий алгоритм ченя

Код

            // put elp into index form
            for (i = 0; i <= L; i++)
                elp[i] = index_of[elp[i]];

            printf("sigma(x) = ");
            for (i = 0; i <= L; i++)
                printf("%3d ", elp[i]);
            printf("\n");
            printf("Roots: ");

            // Chien search: find roots of the error location polynomial
            for (i = 1; i <= L; i++)
                reg[i] = elp[i]; // промежуточная переменная, локаторы в индексной форме

            count = 0;  // считаем реальное количество корней
            for (i = 1; i <= n; i++) {  // осуществляем полный перебор по всем словам для поиска корней локатора ошибок
                q = 1;                  // индексы корней уравнения локаторов ошибок определяют местоположения ошибок
                for (j = 1; j <= L; j++)
                    if (reg[j] != -1) {             // перемножение
                        reg[j] = (reg[j] + j) % n;  // умножение на alpha^(-i*k)
                        q ^= alpha_to[reg[j]];      // делаем сложение в полиномиальной форме
                    }
                if (!q) {   // получили 0, значит искомое число есть корень уравнения
                    // store root and error location number indices
                    root[count] = i;        // сохраняем индекс корня
                    loc[count]  = n - i;    // вписываем местоположение конретной ошибки (она обратная индексу корня)
                    count++;
                    printf("%3d ", n - i);
                }
            }
            printf("\n");

            if (count == L)  // если счетчик корней равен степени полинома локаторов ошибок
            // no. roots = degree of elp hence <= t errors
                for (i = 0; i < L; i++)
                    recd[loc[i]] ^= 1;
            else    // elp has degree > t hence cannot solve
                printf("Incomplete decoding: errors detected\n");

В атаче сишный файл реализации (15,5,7) двоичного кодера. Если я правильно понял теорию это код максимальной длинны. В примере задаются 4 битовые ошибки, которые кодер не может исправить. В этом случае deg(Lambda) == 3, L == 3. Алгоритм Берлекэмпа-Месси не находит предпосылок к невозможности декодирования. Выясняется это только в процедуре Ченя, когда сравнивается количество найденых корней (count == 0) со степенью полинома локатора ошибок == длине LFSR регистра. При этом не находится ни одного корня, тогда как по вашим словам корни быть обязаны

В атаче модифицированный файл, оригинальный файл был взят здесь

Эта проверка редко, но срабатывает. Степень не всегда меняется одновременно с L.
Помоделируйте декодер и поймаете такую ситуацию.

спасибо, соберу рандомно/переборный тест и проверю.

Прикрепленные файлы

 bch.zip ( 7.17 килобайт ) Кол-во скачиваний: 138