Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Коды БЧХ
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Страницы: 1, 2, 3, 4
des00
Гуру кодирования, просвятите по теме

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

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

Спасибо.
vadimuzzz
не гуру, но:
1. да, для двоичных кодов БЧХ процедура проще, четные итерации можно пропустить. если эта картинка из Блейхута, то в главе 7.6 есть подробности.
2. в той же книге про алгоритм Евклида говорится: "считается, что он менее эффективен в практическом использовании" smile.gif
des00
Цитата(vadimuzzz @ Sep 22 2010, 00:13) *
1. да, для двоичных кодов БЧХ процедура проще, четные итерации можно пропустить. если эта картинка из Блейхута, то в главе 7.6 есть подробности.

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

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

а вот Сарагоса с Кларком говорят что наоборот, для железа Евклид самое то. Вот мне и интересно почему %)
vadimuzzz
Цитата(des00 @ Sep 22 2010, 13:22) *
т.е. для двоичных кодов последнюю проверку (if deg(Lambda) == L) можно отбросить?

я так понимаю это от задачи зависит: нужно ли детектировать несправимую ошибку? если нет - выбросить. если надо - ввести дополнительные невязки.
Цитата
а вот Сарагоса с Кларком говорят что наоборот, для железа Евклид самое то. Вот мне и интересно почему %)

ну, они-то точно гуру smile.gif
des00
Цитата(vadimuzzz @ Sep 22 2010, 01:34) *
я так понимаю это от задачи зависит: нужно ли детектировать несправимую ошибку? если нет - выбросить. если надо - ввести дополнительные невязки.

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

UPD. Вот я ламер, неисправимая ошибка и количество неисправимых ошибок это же разные вещи %) Если я сделал правильные умозаключения, то для двоичных кодов эта проверка не нужна, т.к. для этих кодов ветка 2L > r-1 никогда не выполняется. Поэтому степень полинома локаторов изменяется одновременно с L.
SKov
Цитата(des00 @ Sep 22 2010, 10:44) *
1. неисправимую ошибку можно детектировать в процедуре ченя, когда количество найденных корней не совпадет с порядком локатора ошибок.


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

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

Эта проверка редко, но срабатывает. Степень не всегда меняется одновременно с L.
Помоделируйте декодер и поймаете такую ситуацию.
des00
Цитата(SKov @ Sep 22 2010, 04:44) *
Только для укороченных кодов. В остальных случаях Чень перебирает все элементы поля и среди них обязательно найдутся все корни полинома.

Вот что странно, я использовал в качестве базы пример
Код
* 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.gif

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

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

спасибо, соберу рандомно/переборный тест и проверю.
SKov
Цитата(des00 @ Sep 22 2010, 20:03) *
При этом не находится ни одного корня, тогда как по вашим словам корни быть обязаны

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

Спасибо.
vadimuzzz
поделить на aplha^i, i=1..2t
Mikhalych
Цитата(des00 @ Sep 27 2010, 17:21) *
Есть такой вопрос по реализации декодера для ПЛИС. Для декодирования нужно определить 2t синдромов, если считать синдромы классически(через таблицы), получается сильно жирно по ресурсу памяти. По любому должен существовать способ расчета синдромов с помощью сдвиговых регистров с обратными связями. Подскажите плиз где можно про это прочитать? В основных книгах информации об этом я не нашел.

Спасибо.


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

1 - софтверная реализация и алгоритмы кодирования/декодирования
2 - аппаратная реализация декодера
3 - оптимизированный алгоритм Чейня
4 - реализация умножителей в поле Галуа (очень полезно)
5 - реализация декодера Рида-Соломона (очень похожа по струкруре блоков на БЧХ)
6 - ещё одна реализация декодера, но алгоритм SiBM тут с ошибкой (я делал RiBM)
7 - мегакнига по реализации кодов коррекции ошибок применительно к флэшкам
8 - готовая прожка кодирования/декодирования от микрона (по ней я отлаживался)

h__p://depositfiles.com/files/zmz0ppjzi
des00
Цитата(vadimuzzz @ Sep 27 2010, 09:31) *
поделить на aplha^i, i=1..2t

спасибо всё красиво получилось, вычисление синдрома 3 строчки (ну и + строк 40 для функций). Хочу что бы все функции декодера считались на SV, потом может быть выложу в тему про батл AHDL vs SV %)
Цитата(Mikhalych @ Sep 28 2010, 02:26) *
Вот что я тогда нашёл по этой тематике:
h__p://depositfiles.com/files/zmz0ppjzi

спасибо за литературу %)
x736C
Сколько «жрет» ресурсов ваша реализация?
AHDL сравнивать с SV, мне кажется, неуместно. Языки разного поколения. AHDL разве объектно-ориентированный?
des00
Цитата(x736C @ Sep 28 2010, 06:43) *
Сколько «жрет» ресурсов ваша реализация?

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

да есть такая тема на форуме, если интересно в личку, не надо тут офтопить %)
SKov
Цитата(Mikhalych @ Sep 28 2010, 11:26) *
Недавно сам занимался аппаратной реализацией такого декодера - вообщемто всё удачно получилось.
....
6 - ещё одна реализация декодера, но алгоритм SiBM тут с ошибкой (я делал RiBM)

Без обратного элемента - это хорошо, но не всегда подходит. Часто заказчик требует
особо быстрого декодирования 1-2 ошибок, а там без обратного элемента не получается.
Mikhalych
Цитата(SKov @ Sep 28 2010, 15:58) *
Без обратного элемента - это хорошо, но не всегда подходит. Часто заказчик требует
особо быстрого декодирования 1-2 ошибок, а там без обратного элемента не получается.


Я делал на 12 ошибок - алгоритм БМ без обратного элелемнта в GF(2^13)
алгоритм RiBM вычислял коэф. за 24 такта, SiBM вычислил бы за 12 тактов, но чёто у меня не получилось его реализовать

Для 1-2 ошибок Хемминг лучше
x736C
Вопрос ко всем. А вы память используете?
Mikhalych
Цитата(x736C @ Sep 28 2010, 16:59) *
Вопрос ко всем. А вы память используете?


нет - всё на логике и сдвиговых регистрах
des00
Цитата(Mikhalych @ Sep 28 2010, 06:54) *
Я делал на 12 ошибок - алгоритм БМ без обратного элелемнта в GF(2^13)
алгоритм RiBM вычислял коэф. за 24 такта, SiBM вычислил бы за 12 тактов, но чёто у меня не получилось его реализовать

если я правильно понял, то БМ по 4 такта на цикл. использовали умножители в GF за такт?

ЗЫ. Классический алгоритм БМ, приведенный у блейхута это RiBM или SiBM?
SKov
Цитата(Mikhalych @ Sep 28 2010, 16:54) *
Для 1-2 ошибок Хемминг лучше

biggrin.gif
Вы не поняли. Декодер исправляет, например, до 12 ошибок, но на декодирование 12 ошибок требует, например, 1000 тактов,
а для 2-х ошибок - только 100. А для одной - 30.
Mikhalych
Цитата(des00 @ Sep 28 2010, 17:53) *
... использовали умножители в GF за такт?


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

Цитата(des00 @ Sep 28 2010, 17:53) *
ЗЫ. Классический алгоритм БМ, приведенный у блейхута это RiBM или SiBM?

У него iBM вроде =)

Если сравнивать аппаратные затраты и скорость вычислений для этих 3х алгоритмов - то тут данные такие:
t - исправляющая способность кода; GFA - сумматор в GF; GFM - умножитель в GF; MUX - мультиплексор; REG - регистр; Cycle - число тактов для вычисления коэф-тов

iBM -> GFA: 2t+1 GFM: 3+3 REG: 4t+4 MUX: t+1 Cycle: 3t
RiBM -> GFA: 3t+1 GFM: 6t+2 REG: 6t+2 MUX: 3t+1 Cycle: 2t
SiBM -> GFA: 2t GFM: 4t REG: 2t+1 MUX: 2t Cycle: t
des00
Цитата(Mikhalych @ Sep 28 2010, 07:54) *
алгоритм RiBM вычислял коэф. за 24 такта, SiBM вычислил бы за 12 тактов, но чёто у меня не получилось его реализовать

либо я тупой, либо одно из двух crying.gif в статьях выложенных выше приведены 4 варианта алгоритма SiBM. Но все они разные. В целях пристрелки реализовал один в один 3 штуки ни один не работает(причем в одном алгоритме была ошибка). Детальное исполнение алгоритма на бумажке показывает что косяков в реализации нет, но алгоритм не работает %)
Может быть у кого нить есть статья с описанием SiBM который приведен без ошибок?

Спасибо.
des00
Цитата(des00 @ Oct 1 2010, 02:40) *
либо я тупой, либо одно из двух

Отбой, все получилось, слишком невнимательно курил доки %)
Есть еще такой вопрос, в алгоритмах iBM, rIBM, sIBM отсутствует проверка корректности полинома локатора ошибок (deg(Lambda(x)) == L) ? значит ли это, что вся нагрузка на определение корректности полинома ложиться на ченя?
des00
Гуру кодирования прошу вашей помощи. Как поступают в том случае если число ошибок больше корректирующей способности БЧХ кода, а декодер считает что количество ошибок равно t и что-то исправляет?
Пример такого количества и местоположения ошибок для кода 15,5,7 в приложении.
petrov
Цитата(des00 @ Oct 4 2010, 13:58) *
Гуру кодирования прошу вашей помощи. Как поступают в том случае если число ошибок больше корректирующей способности БЧХ кода, а декодер считает что количество ошибок равно t и что-то исправляет?


ИМХО это нормальная ситуация, графики BER для кодированной и не кодированной модуляции пересекаются в области высокой вероятности ошибки, и не кодированная передача становится лучше, а в кодированной происходит размножение ошибок, шум превышает расстояние евклида или хемминга до границы принятия решения и декодер начинает принимать за истинные другие кодовые слова.
des00
Цитата(petrov @ Oct 4 2010, 06:10) *
ИМХО это нормальная ситуация, графики BER для кодированной и не кодированной модуляции пересекаются в области высокой вероятности ошибки, и не кодированная передача становится лучше, а в кодированной происходит размножение ошибок, шум превышает расстояние евклида или хемминга до границы принятия решения и декодер начинает принимать за истинные другие кодовые слова.

то что ситуация обычная это понятно, но ведь должен же существовать какой то способ, для определения того, что ошибок больше чем корректирующая способность(t)? На степень полинома локаторов надежды нет, т.к. он, алгоритмически ограничен t, поиск корней полинома тоже может дать сбой (как в этом примере). Вот мне и интересно, как определить что ошибок больше чем нужно и выдать сигнал decfailed, вместо мусора %)

По идее можно бы воспользоваться свойством вырождения матрицы синдромов, но считать детерминант на лету, не есть гуд. Еще нашел в блейхуте что можно вычислить спектр кода, но вот пока еще неясно как и даст ли это результат.
Mikhalych
Цитата(des00 @ Oct 4 2010, 17:04) *
Вот мне и интересно, как определить что ошибок больше чем нужно и выдать сигнал decfailed, вместо мусора %)

может CRC считать?
des00
Цитата(Mikhalych @ Oct 4 2010, 07:10) *
может CRC считать?

это для протокола более высокого уровня, мне нужно другое %)

Цитата(des00 @ Oct 4 2010, 07:04) *
По идее можно бы воспользоваться свойством вырождения матрицы синдромов, но считать детерминант на лету, не есть гуд.

да и не получится так, потому что синдром по определению определен на множестве элементов alpha^1 ...alpha^2t.
Mikhalych
Цитата(des00 @ Oct 4 2010, 17:11) *
это для протокола более высокого уровня, мне нужно другое %)

а если сделать декодер на t+1 ошибку... и если ошибок t и меньше - то всё хорошо, а если t+1 - то недоверяем и говорим decfailed?
petrov
Цитата(des00 @ Oct 4 2010, 17:04) *
то что ситуация обычная это понятно, но ведь должен же существовать какой то способ, для определения того, что ошибок больше чем корректирующая способность(t)? На степень полинома локаторов надежды нет, т.к. он, алгоритмически ограничен t, поиск корней полинома тоже может дать сбой (как в этом примере). Вот мне и интересно, как определить что ошибок больше чем нужно и выдать сигнал decfailed, вместо мусора %)


ИМХО не должен, если только дополнительную избыточность на это тратить.
des00
Цитата(Mikhalych @ Oct 4 2010, 07:19) *
а если сделать декодер на t+1 ошибку... и если ошибок t и меньше - то всё хорошо, а если t+1 - то недоверяем и говорим decfailed?

тогда есть опасность не влезть в требуемую полосу пропускания и что делать если ошибок будет ну например t+5 ? smile.gif

Цитата(petrov @ Oct 4 2010, 07:30) *
ИМХО не должен, если только дополнительную избыточность на это тратить.

хмм, неужели в и RS кодерах всё так же плохо. И даже проверка нулей спектра кода не поможет?

ЗЫ. Мне сильно желательно диагностика такой ситуации для канала без явной синхронизации. Чтобы лучше работала система синхронизации. Подобное я делал на корке RS, но никогда не задумывался, до сего момента, что decfailed корки мне врал %(
petrov
Цитата(des00 @ Oct 4 2010, 17:34) *
хмм, неужели в и RS кодерах всё так же плохо. И даже проверка нулей спектра кода не поможет?


Так если шум+кодовое слово прикидываются другим кодовым словом то ничего не поможет.
des00
Цитата(petrov @ Oct 4 2010, 08:38) *
Так если шум+кодовое слово прикидываются другим кодовым словом то ничего не поможет.

об этом я как то не подумал biggrin.gif но мне странно вот что, для решения уравнения по t ошибкам нужно 2t синдромов, неужели никак нельзя использовать сию "избыточность" чтобы сказать что ошибок больше максимума unsure.gif
petrov
Цитата(des00 @ Oct 4 2010, 17:50) *
об этом я как то не подумал biggrin.gif но мне странно вот что, для решения уравнения по t ошибкам нужно 2t синдромов, неужели никак нельзя использовать сию "избыточность" чтобы сказать что ошибок больше максимума unsure.gif


Думаю что "лишней избыточности" там нету.
vadimuzzz
Цитата(des00 @ Oct 4 2010, 20:34) *
хмм, неужели в и RS кодерах всё так же плохо.

как бы RS - это подмножество BCH smile.gif

Цитата(des00 @ Oct 4 2010, 20:34) *
но никогда не задумывался, до сего момента, что decfailed корки мне врал %(

он не врал, ЕМНИП у этого сигнала вполне конкретный смысл, он показывает неисправимые ошибки, но не все.
des00
Цитата(vadimuzzz @ Oct 4 2010, 09:22) *
как бы RS - это подмножество BCH smile.gif

да, но там недвочиные символы, если верить Блейхуту, то можно проверить все ли корректирующие символы из нужного алфавита.
Цитата
он не врал, ЕМНИП у этого сигнала вполне конкретный смысл, он показывает неисправимые ошибки, но не все.

под врал я понимал то, что когда он не показывал decfail нельзя было однозначно сказать были ошибки или нет %)

Подводя итог, как я понял бороть сей эффект бесполезно. Ну разве что расширить код добавив символ четности. Немного поможет %)
GetSmart
Цитата(des00 @ Oct 4 2010, 19:38) *
Ну разве что расширить код добавив символ четности. Немного поможет %)

Разве этого недостаточно?
des00
Цитата(GetSmart @ Oct 4 2010, 09:26) *
Разве этого недостаточно?

Если вы про расширение кода, то еще не знаю. надо рыть литературу. Правда, из-за выбранной сетки частот, мне нужны фреймы 2**m-1. Если про тот код что есть, буду смотреть. Может быть устроит то что получилось.

ЗЫ. Последний вопрос про бинарные БЧХ, неподскажите есть где нибудь внятное алгоритмическое описание получения генераторного полинома. Понятно что это НОК от примитивных полиномов членов поля, но как определяются эти примитивные полиномы? Разбирался с кодом с http://the-art-of-ecc.com/, даже портировал его в SV, но так до конца и не понял всех тонкостей алгоритма. crying.gif
GetSmart
Ещё раз подумал. Простой бит чётности в случае большого кол-ва ошибок не поможет (гарантированно). Т.к. кол-во ошибок неизвестно в случае превышения t, то чётность может совпасть, а может и не совпасть. Возможно она просто бесполезна и зря занимает символ.
petrov
Цитата(GetSmart @ Oct 4 2010, 19:57) *
Ещё раз подумал. Простой бит чётности в случае большого кол-ва ошибок не поможет (гарантированно). Т.к. кол-во ошибок неизвестно в случае превышения t, то чётность может совпасть, а может и не совпасть. Возможно она просто бесполезна и зря занимает символ.


Более того сами БЧХ коды практически бесполезны в АБГШ канале, маленький выигрыш дают, выкидываете избыточность, соответственно заужаете полосу и получаете почти ту же самую помехоустойчивость.
des00
Цитата(petrov @ Oct 4 2010, 10:15) *
Более того сами БЧХ коды практически бесполезны в АБГШ канале, маленький выигрыш дают, выкидываете избыточность, соответственно заужаете полосу и получаете почти ту же самую помехоустойчивость.

странно, в блейхуте, сарагосе и т.д. написано что для малых размеров блока БЧХ коды близки к оптимальным %) Да и в стандарте dvbs от них не отказываются %)
А что еще дешево (с точки зрения ресурса) и качественно используется для малых размеров блока? (меньше 255 бит)
Serg76
мало того, некоторые коды БЧХ используются в качестве компонентных при построении блоковых турбокодов
petrov
Цитата(des00 @ Oct 4 2010, 20:32) *
А что еще дешево (с точки зрения ресурса) и качественно используется для малых размеров блока? (меньше 255 бит)


Купить усилитель на 3 дБ мощнее %) Не знаю на счёт дёшево, но турбокоды явно больше дадут. Возможно TCM можно приспособить для коротких блоков, в гигабитном езернете что-то такое используется. Хотя бы мягкое декодирование БЧХ по алгоритму Чейза используйте.

Цитата(Serg76 @ Oct 4 2010, 20:39) *
мало того, некоторые коды БЧХ используются в качестве компонентных при построении блоковых турбокодов


Это да TPC мощные коды.

SKov
Цитата(des00 @ Oct 4 2010, 20:32) *
странно, в блейхуте, сарагосе и т.д. написано что для малых размеров блока БЧХ коды близки к оптимальным %) Да и в стандарте dvbs от них не отказываются %)
А что еще дешево (с точки зрения ресурса) и качественно используется для малых размеров блока? (меньше 255 бит)

БЧХ коды нормально работают, если от них не требовать больше, чем они могут дать.
Если вы квантуете канал с АБГШ, то на БЧХ кодах вполне реально получить 3..5 дБ ЭВК даже при декодировании только двичных ошибок в дискретном канале.
Вообще, если есть ДСК, то БЧХ близки к лучшим кодам. Известно, что примитивные БЧХ,
исправляющие 2 ошибки, квазисовершенны. Для длин больше 1000 вообще трудно что-то приличнее придумать для ДСК.
Но это все в дискретном канале. А вот если у вас есть непрерывный выход, то ситуация кардинально меняется.
Конечно, и в этом случае можно использовать декодер БЧХ для ДСК, применяя алгоритмы Чейза или декодирование по МОР (Форни.)
Но много там не получишь (обычно в пределах 1.5...2 дБ дополнительного выигрыша к ЭВК дискретного канала).
Но для длин <100 это все равно надо делать и это будет хорошо.
А вот если длина хотя бы несколько сотен (а лучше - тысяч), то ситуация совсем другая. Тут уже начинают блистать LDPC коды.
Турбо-коды были модны лет 10 назад, но в последнее время их пододвинули LDPС. Тот же стандарт DVB -хх использует именно LDPC
с дурацкой примочкой из внешнего БЧХ-кода.
Так что определитесь, какие у вас ограничения на канал и сложность декодера, и выбирайте лучший вариант
из большого многообразия конструкций кодов и декодеров.
des00
Цитата(petrov @ Oct 4 2010, 10:54) *
Купить усилитель на 3 дБ мощнее %)

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

я сильно ограничен по ресурсам, у меня на кодер/декодер есть около 1000 плиток(чем меньше, тем лучше). Мне нужно два декодера {255,233,4} на 200Мб/с и {127, 64, 10} на 2Мб/с. ИМХО на таких длинах TCM/LDPC и т.д. это как из пушки по воробьям.
Цитата(SKov @ Oct 4 2010, 12:59) *
Конечно, и в этом случае можно использовать декодер БЧХ для ДСК, применяя алгоритмы Чейза или декодирование по МОР (Форни.)

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

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

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

ЗЫ. А по определению примитивных полиномов можете что нить подсказать? Спасибо %)
vadimuzzz
Цитата(des00 @ Oct 5 2010, 09:39) *
А по определению примитивных полиномов можете что нить подсказать?

нужно разложить x^n - 1 на простые множители. примитивный полином - это полином минимальной степени, т.ч. его корень alpha обладает свойством, что его степени покрывают все поле (т.е. alpha - порождающий элемент поля).
des00
Цитата(vadimuzzz @ Oct 5 2010, 00:00) *
нужно разложить x^n - 1 на простые множители. примитивный полином - это полином минимальной степени, т.ч. его корень alpha обладает свойством, что его степени покрывают все поле (т.е. alpha - порождающий элемент поля).

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

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

http://www.seanerikoconnor.freeservers.com...s/overview.html
des00
Цитата(vadimuzzz @ Oct 4 2010, 23:40) *
все украдено до нас smile.gif

пасиб, постараюсь прикрутить %)
petrov
Цитата(des00 @ Oct 5 2010, 06:39) *
я сильно ограничен по ресурсам, у меня на кодер/декодер есть около 1000 плиток(чем меньше, тем лучше). Мне нужно два декодера {255,233,4} на 200Мб/с и {127, 64, 10} на 2Мб/с. ИМХО на таких длинах TCM/LDPC и т.д. это как из пушки по воробьям.


В эзернете ограниченный бюджет задержки и там используется специальный TCM код с маленькой задержкой декодирования. Можно использовать TPC на основе расширенного БЧХ(16,11,4), длина блока 256, скорость 11^2/16^2, выигрыш около 5 дБ, ещё лучше на основе БЧХ(32,26,4), выигрыш около 6.5 дБ. По ресурсам не влезет конечно, но получить приличный выигрыш на относительно коротких блоках можно.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.