[repstosw 18]

Использую программное кодирование-декодирование Рида-Соломона.

Вначале взял RS GF(2^8), разбил пакет на части, сделал перемежение, затем закодировал, потом передал.  Затем принял, раскодировал, де-перемежил, скорректировал ошибки.  Всё работает, коды действительно облегчают условия приёма.  Я не знаю где находятся ошибки (стирания), поэтому число исправляемых ошибок в 2 раза меньше числа символов проверки.

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

Затем взял RS GF(2^16). Надобность в перемежении отпала, так как длина пакета меньше, чем 65535 байт (2^16 -1).  Здесь получается много нулевых байт, потому что размер пакета намного меньше, чем 65535.  К тому же ещё и 2-байтные слова.Нулевые байты, естественно, не передаю. В приёмнике их дописываю на известные позиции.

 

Работает тоже, но скорость работы просто ужасная.  Исходный пакет 8192 байта, число ошибок - 256.  Работает медленно - скорость декодирования всего 17 FPS (59 мс).

Получается  32 штуки 8-битных RS  работает намного быстрее, чем один 16-битный RS.

 

Есть ли способы ускорить работу декодера RS GF(2^16) за счёт того, что известно, что после полезного пакета до проверочных символов - идут нулевые символы?

И вообще, есть ли какое-нибудь кодирование-декодирование длинных пакетов 1 кбайт - 8 кбайт?

 

Изменено 30 июля, 2023 пользователем repstosw

[blackfin 32]

On 7/30/2023 at 5:44 AM, repstosw said:

Исходный пакет 8192 байта, число ошибок - 256.  Работает медленно - скорость декодирования всего 17 FPS (59 мс).

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

Эта задача давно и вполне успешно решена в стандарте DVB-T2.

[des00 25]

7 hours ago, repstosw said:

Получается  32 штуки 8-битных RS  работает намного быстрее, чем один 16-битный RS.

естественно, ведь при программном декодировании, математика GF(2^8) выполняется таблично (именно за это и любят это поле), тогда как GF(2^16) уже на логике и побитно.

7 hours ago, repstosw said:

Есть ли способы ускорить работу декодера RS GF(2^16) за счёт того, что известно, что после полезного пакета до проверочных символов - идут нулевые символы?

ну вообще RS обычно с головы укорачивают. Так экономнее кодировать и считать синдромы. Ну и зная укорочение можно немного сократить процедуру ченя. 

6 hours ago, blackfin said:

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

Эта задача давно и вполне успешно решена в стандарте DVB-T2.

ЕМНП у него нет доступа к мягкому решению, а без него, DVB LDPC код не очень эффективен. Ну и до кучи, если у него проблемы с производительностью для RS в поле GF(2^16), то будут точно такие же или еще больше когда он возьмет LDPC + BCH (GF^16).

[repstosw 18]

12 hours ago, des00 said:

ну вообще RS обычно с головы укорачивают. Так экономнее кодировать и считать синдромы. Ну и зная укорочение можно немного сократить процедуру ченя. 

Удалось ускорить работу декодера путём укорочения цыклов.

Было:

Стало:

Данные разместил близко к проверочным символам.

NN - общая длина кода (65536 символов 16-бит)

EE - длина кода проверки (256 символов 16-бит)

KK - общая длина полезного сообщения (с нулями в начале,  NN-EE)

K - интересующая длина полезного сообщения (без нулей,  4096 символов 16-бит)

 

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

 

Выкладываю проект целиком (исходники, сборка, готовый модуль) для тестирования на ПК, просьба помочь с кодером:

RS_GF(2^16).zip

 

Для замера времени используется rdtsc  (x64).  Частота ядра 3 ГГц.

[des00 25]

5 hours ago, repstosw said:

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

не вижу у вас в коде укорачивания кода в кодере с головы) 

    for (i = KK-1 ; i >= 0 /*KK-K*/; i--) { //???
//        feedback = Index_of[data[i] ^ bb[NN - KK - 1]];

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

ЗЫ. А для синдромов вот такая организация цикла работает, потому что ему безразницы. 

ЗЫ. Код не компилировал, не проверял, только глянул. 

[repstosw 18]

1 hour ago, des00 said:

не вижу у вас в коде укорачивания кода в кодере с головы) 

Я же писал, что укоротить кодирование не вышло.

1 hour ago, des00 said:

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

Обратная связь меняется. Она зависит от bb[NN - KK - 1],  который меняется в любом случае.

Так просто не получится, как это сдалал в декодировании, укоротив циклы.

 

Немного ускорил кодирование до 28 FPS. За счёт более быстрой реализации функции (точнее - инлайна) остатка от деления на 65535:

static inline gf modnn(int x)
{
    x = (x >> 16) + (x & 0xFFFF); /* sum base 2**16 digits */
    if (x <      65535)  return x              ;
    if (x < (2 * 65535)) return x -      65535 ;
                         return x - (2 * 65535);
}

 

Пробовал задавать таблично - в итоге скорость проседала до 14 FPS.

 

И всё-же как оптимизировать алгоритм кодирования?

Изменено 31 июля, 2023 пользователем repstosw

[des00 25]

1 hour ago, repstosw said:

Я же писал, что укоротить кодирование не вышло.

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

Повторюсь: кодирование RS это деление на полином. Деление нуля (то самое заполнение нулями что вы делаете), не меняет результат. Если нули стоят в начале кодового слова, то можно их просто пропустить, подав сразу данные (начальное состояние частного должно быть одинаковое во всех случаях). На этом и основано укорочение кодов.

PS, Во избежание того что я не понимаю о чем говорю, вот мой универсальный RS кодер это RTL-SV, но понять можно. Как видно, структура кодера не меняется для укороченных или полных кодов, все определяется первым (isop) и последним (ieop) словом данных. Которых может быть от 1 до 2^n-1 - check.

[repstosw 18]

1 hour ago, des00 said:

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

Повторюсь: кодирование RS это деление на полином. Деление нуля (то самое заполнение нулями что вы делаете), не меняет результат. Если нули стоят в начале кодового слова, то можно их просто пропустить, подав сразу данные (начальное состояние частного должно быть одинаковое во всех случаях). На этом и основано укорочение кодов.

Были перепутаны хвост и грива у полинома который делится (исходные данные).

Теперь кодирование работает на 400+ FPS, при этом проверочные символы те же самые, что и без укорочения (что верно).

Чтобы кодирование с укорочением работало, нужно полезные данные ставить слева, а не перед проверочными:

 

Зато теперь с укороченным декодированием проблема - цикл в алгоритме Ченя не хочет укорачиваться (при этом длинное декодирование - работает):

 /*
     * Find roots of the error+erasure locator polynomial. By Chien
     * Search
     */
    COPY(&reg[1],&lambda[1],NN-KK);
    count = 0;		/* Number of roots of lambda(x) */
    for (i = 1; i <= NN ; i++) {

        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0) {
                reg[j] = modnn(reg[j] + j);
                q ^= Alpha_to[reg[j]];
            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] = i;
            loc[count] = NN - i;
            count++;
        }
    }

 

Мало того,  в декодере в остальных циклах приходится прерывать итерации из середины (как раз где нули):

            if((j>K-1)&&(j<KK))continue; //[0..K-1] ... [KK..NN-1]

 

Изменено 31 июля, 2023 пользователем repstosw

[des00 25]

1 hour ago, repstosw said:

Чтобы кодирование с укорочением работало, нужно полезные данные ставить слева, а не перед проверочными:

Это фича конкретно той реализации которую вы нашли, видимо вот так авторам было удобно) Можно еще процедуру ченя сделать быстрее, но надо будет заранее вычислить несколько констант.

 

[repstosw 18]

59 minutes ago, des00 said:

Можно еще процедуру чены сделать быстрее, но надо будет заранее вычислить несколько констант.

Какие?

[des00 25]

23 minutes ago, repstosw said:

Какие?

Чень работает итерационно, а именно последовательно подбирает корни и подставляет их в уравнение локаторов, проверяя является ли данный локатор символа, символом с ошибкой. Если при подстановке получаем ноль, значит ошибка в этом символе. В отбрасываемых, при передаче нулевых символов, априори ошибок быть не может поэтому и считать их не нужно. Можно пропустить их рассчет, но нужно учесть значение локатора корня, которое должно быть на шаге, перед актуальным словом данных. Это значение фиксированно для конкретного RS кода (длина кода, количество проверочных символов, количество отбрасываемых символов).

[repstosw 18]

13 hours ago, des00 said:

В отбрасываемых, при передаче нулевых символов, априори ошибок быть не может поэтому и считать их не нужно. Можно пропустить их рассчет, но нужно учесть значение локатора корня, которое должно быть на шаге, перед актуальным словом данных. Это значение фиксированно для конкретного RS кода (длина кода, количество проверочных символов, количество отбрасываемых символов).

Не удаётся полностью избежать вычислений в алгоритме Ченя для нулей.  Алгоритм требует переменных с предыдущего состояния.

Массив reg[ ] в коде. Не удаётся разлепить.  Пока найдены условия, при которых ошибка не генерируется (нули) - переменная q:

//if(((NN-i)>K-1)&&((NN-i)<KK)) //[0..K-1] ... [KK..NN-1]
                                
    /*
     * Find roots of the error+erasure locator polynomial. By Chien
     * Search
     */
    COPY(&reg[1],&lambda[1],NN-KK);

    count = 0;		/* Number of roots of lambda(x) */


    for (i = 1; i <= NN ; i++) {

if(((NN-i)>K-1)&&((NN-i)<KK)) //[0..K-1] ... [KK..NN-1]
{
        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=reg[j]+j;
             if(reg[j]>=65535)reg[j]-=65535; //modnn
            }
}
else
{
        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=reg[j]+j;
             if(reg[j]>=65535)reg[j]-=65535; //modnn
             q ^= Alpha_to[reg[j]] ;

            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] = i;
            loc[count] = NN - i; //позиции ошибочных байт
            count++;
        }

}

    }

 

14 hours ago, des00 said:

Это фича конкретно той реализации которую вы нашли, видимо вот так авторам было удобно)

Это не зависит от реализации.  Деление идёт со старших разрядов полинома и завершается делением младших, пока не получится остаток от деления. Поэтому для правильного кодирования старшие разряды должны быть нулевыми.

Никто не начинает деление с младших разрядов делимого. И вроде это даже невозможно

Изменено 31 июля, 2023 пользователем repstosw

[des00 25]

3 hours ago, repstosw said:

Не удаётся полностью избежать вычислений в алгоритме Ченя для нулей.  Алгоритм требует переменных с предыдущего состояния.

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

3 hours ago, repstosw said:

Это не зависит от реализации.  Деление идёт со старших разрядов полинома и завершается делением младших, пока не получится остаток от деления. Поэтому для правильного кодирования старшие разряды должны быть нулевыми.

Никто не начинает деление с младших разрядов делимого. И вроде это даже невозможно

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

ЗЫ. Строки 359-399 показывают как пропустить часть Ченя, при усеченных кодах, для полинома локаторов и полинома значений ошибок. Но, нужно помнить, что при усечении еще может потребоваться коррекция начального значения коэффициента масштабирования ошибки. Это можно посмотреть в строках 405-427. Зависит она от первого корня генераторного полинома, расстояния между корнями и от реализации алгоритма берлекампа. Но вам проще. Надо при отладке записать те константы что будут, а потом просто начать алгоритм с нужного шага. 

[repstosw 18]

5 hours ago, des00 said:

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

ЗЫ. Строки 359-399 показывают как пропустить часть Ченя, при усеченных кодах, для полинома локаторов и полинома значений ошибок. Но, нужно помнить, что при усечении еще может потребоваться коррекция начального значения коэффициента масштабирования ошибки. Это можно посмотреть в строках 405-427. Зависит она от первого корня генераторного полинома, расстояния между корнями и от реализации алгоритма берлекампа. Но вам проще. Надо при отладке записать те константы что будут, а потом просто начать алгоритм с нужного шага. 

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

Я записывал массив reg[ ] для случая нулевых байт каждый кадр, и несмотря на то что нули, значения reg[ ] всегда разные. 

Пока получилось разбить на 3 цикла, цикл в середине - как раз соотносится к нулевым байтам.  Получилось 35 FPS. 

Пробовал выкинуть этот цикл (декодирование при этом неверное) - скорость повышается до 50 FPS.

   /* Convert lambda to index form and compute deg(lambda(x)) */
    deg_lambda = 0;
    for(i=0; i<NN-KK+1; i++) {
        lambda[i] = Index_of[lambda[i]];
        if(lambda[i] != A0)
            deg_lambda = i;
    }
    /*
     * Find roots of the error+erasure locator polynomial. By Chien
     * Search
     */
    COPY(&reg[1],&lambda[1],NN-KK);

                        count = 0;		/* Number of roots of lambda(x) */


for (i = NN-1; i >= KK; i--) //Parity
{
        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=modnn(reg[j]+j); //modnn
             q ^= Alpha_to[reg[j]] ;
            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] =NN-i;
            loc[count] = i;    //позиции ошибочных байт
            count++;
        }

}

for (i = KK-1; i >= K ; i--)  //Zero
{
        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=modnn2(reg[j]+j); //modnn
            }
}

for (i = K-1; i >= 0 ; i--) //Data
{
        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=modnn(reg[j]+j); //modnn
             q ^= Alpha_to[reg[j]] ;
            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] =NN-i;
            loc[count] = i;    //позиции ошибочных байт
            count++;
        }
}

    printf("\n Final error positions:\t");
    for (i = 0; i < count; i++)
        printf("%d ", loc[i]);
    printf("\n");
                          
    if (deg_lambda != count) {
        /*
         * deg(lambda) unequal to number of roots => uncorrectable
         * error detected
         */
        return -1;
    }

 

[repstosw 18]

1 hour ago, repstosw said:

Пробовал выкинуть этот цикл (декодирование при этом неверное) - скорость повышается до 50 FPS.

Оптимизировал эту гадость до такого уровня:

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]+=j*(KK-K);
             reg[j]=modnn2(reg[j]);
            }

Внешний цикл для нулей (с переменной i)   ушёл.

Теперь скорость около 50 FPS.

Корень зла в частых вызовах функции modnn. Теперь  она вызывается в KK-K раз меньше, когда нулевые элементы.

 

В целом код Ченя выглядит так:

/*
     * Find roots of the error+erasure locator polynomial. By Chien
     * Search
     */
    COPY(&reg[1],&lambda[1],NN-KK);

    count = 0;		/* Number of roots of lambda(x) */

for (i = NN-1; i >= KK; i--) //Parity
{
        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=modnn(reg[j]+j); //modnn
             q ^= Alpha_to[reg[j]] ;
            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] =NN-i;
            loc[count] = i;    //позиции ошибочных байт
            count++;
        }

}

        for (j = deg_lambda; j > 0; j--) //Zero data
            if (reg[j] != A0)
            {
             reg[j]+=j*(KK-K);
             reg[j]=modnn2(reg[j]);
            }

for (i = K-1; i >= 0 ; i--) //Data
{
        q = 1;

        for (j = deg_lambda; j > 0; j--)
            if (reg[j] != A0)
            {
             reg[j]=modnn(reg[j]+j); //modnn
             q ^= Alpha_to[reg[j]] ;
            }

        if (!q) {
            /* store root (index-form) and error location number */
            root[count] =NN-i;
            loc[count] = i;    //позиции ошибочных байт
            count++;
        }
}

 

Изменено 1 августа, 2023 пользователем repstosw