Перейти к содержанию
    

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

 

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

 

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

 

Спасибо.

post-3453-1285133581_thumb.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

не гуру, но:

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 

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

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

 

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

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

Эта проверка редко, но срабатывает. Степень не всегда меняется одновременно с L.

Помоделируйте декодер и поймаете такую ситуацию.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

 * 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 регистра. При этом не находится ни одного корня, тогда как по вашим словам корни быть обязаны :unsure:

 

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

 

Эта проверка редко, но срабатывает. Степень не всегда меняется одновременно с L.

Помоделируйте декодер и поймаете такую ситуацию.

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

bch.zip

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

При этом не находится ни одного корня, тогда как по вашим словам корни быть обязаны

Да, похоже, что Акела промахнулся. Я, кажется, погорячился.

Полином локаторов, в случае превышения максимального числа ошибок, совсем

не обязан иметь ВСЕ корни в этом поле.

Звиняюсь.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Есть такой вопрос по реализации декодера для ПЛИС. Для декодирования нужно определить 2t синдромов, если считать синдромы классически(через таблицы), получается сильно жирно по ресурсу памяти. По любому должен существовать способ расчета синдромов с помощью сдвиговых регистров с обратными связями. Подскажите плиз где можно про это прочитать? В основных книгах информации об этом я не нашел.

 

Спасибо.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Есть такой вопрос по реализации декодера для ПЛИС. Для декодирования нужно определить 2t синдромов, если считать синдромы классически(через таблицы), получается сильно жирно по ресурсу памяти. По любому должен существовать способ расчета синдромов с помощью сдвиговых регистров с обратными связями. Подскажите плиз где можно про это прочитать? В основных книгах информации об этом я не нашел.

 

Спасибо.

 

Недавно сам занимался аппаратной реализацией такого декодера - вообщемто всё удачно получилось.

Вот что я тогда нашёл по этой тематике:

 

1 - софтверная реализация и алгоритмы кодирования/декодирования

2 - аппаратная реализация декодера

3 - оптимизированный алгоритм Чейня

4 - реализация умножителей в поле Галуа (очень полезно)

5 - реализация декодера Рида-Соломона (очень похожа по струкруре блоков на БЧХ)

6 - ещё одна реализация декодера, но алгоритм SiBM тут с ошибкой (я делал RiBM)

7 - мегакнига по реализации кодов коррекции ошибок применительно к флэшкам

8 - готовая прожка кодирования/декодирования от микрона (по ней я отлаживался)

 

h__p://depositfiles.com/files/zmz0ppjzi

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

поделить на aplha^i, i=1..2t

спасибо всё красиво получилось, вычисление синдрома 3 строчки (ну и + строк 40 для функций). Хочу что бы все функции декодера считались на SV, потом может быть выложу в тему про батл AHDL vs SV %)

Вот что я тогда нашёл по этой тематике:

h__p://depositfiles.com/files/zmz0ppjzi

спасибо за литературу %)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Сколько «жрет» ресурсов ваша реализация?

AHDL сравнивать с SV, мне кажется, неуместно. Языки разного поколения. AHDL разве объектно-ориентированный?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Сколько «жрет» ресурсов ваша реализация?

как доделаю тогда будет ясно, т.к. я в этом деле ламер всё двигается медленно %)

AHDL сравнивать с SV, мне кажется, неуместно. Языки разного поколения. AHDL разве объектно-ориентированный?

да есть такая тема на форуме, если интересно в личку, не надо тут офтопить %)

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Недавно сам занимался аппаратной реализацией такого декодера - вообщемто всё удачно получилось.

....

6 - ещё одна реализация декодера, но алгоритм SiBM тут с ошибкой (я делал RiBM)

Без обратного элемента - это хорошо, но не всегда подходит. Часто заказчик требует

особо быстрого декодирования 1-2 ошибок, а там без обратного элемента не получается.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...