кодер рида-соломона и вычисление синдрома Опции

[*Игорь*]

Доброго времени суток, прошу помощи. Что-то делаю не так, не могу понять что. При передаче не измененных данных с добавлением избытка синдром не нулевой. Кто соображает направьте на путь истинный пожалуйста.

CODE

#include <stdio.h>

int add(int x, int y);

int main ()

{
int Table[16]= {239, 8, 164, 97, 0, 212, 30, 83, 181, 151, 122, 252, 155, 120, 200, 91};
int Table2[16]= {136, 21, 169, 207, 44, 179, 59, 94, 50, 232, 211, 107, 48, 195, 220, 129};


int s1[16]={46,70,150,12,203,165,76,175,218,44,188,180,196,79,135,61};
int s2[16]={208,215,180,138,94,2,24,76,160,72,217,15,156,222,235,19};
int s3[16]={75,244,30,61,114,40,226,29,157,3,224,155,48,147,126,1};
int s4[16]={1,126,147,48,155,224,3,157,29,226,40,114,61,30,244,75};
int s5[16]={16,8,147,244,42,151,183,233,95,104,97,171,39,79,12,19};
int s6[16]={19,12,79,39,171,97,104,95,233,183,151,42,244,147,8,16};
int stemp[16];
int s[16];
int st[16];
int b[9]={1,0,0,0,0,0,0,0,0}, l[9]={1,0,0,0,0,0,0,0,0};
int alpha[256]={142,71,173,216,108,54,27,131,207,233,250,125,176,88,44,22,11,139,203
,235,251,243,247,245,244,122,61,144,
72,36,18,9,138,69,172,86,43,155,195,239,249,242,121,178,89,162,81,166,83,167,221
,224,112,56,28,14,7,141,200,
100,50,25,130,65,174,87,165,220,110,55,149,196,98,49,150,75,171,219,227,255,241,
246,123,179,215,229,252,126,
63,145,198,99,191,209,230,115,183,213,228,114,57,146,73,170,85,164,82,41,154,77,
168,84,42,21,132,66,33,158,79,
169,218,109,184,92,46,23,133,204,102,51,151,197,236,118,59,147,199,237,248,124,6
2,31,129,206,103,189,208,104,
52,26,13,136,68,34,17,134,67,175,217,226,113,182,91,163,223,225,254,127,177,214,
107,187,211,231,253,240,120,
60,30,15,137,202,101,188,94,47,153,194,97,190,95,161,222,111,185,210,105,186,93,
160,80,40,20,10,5,140,70,35,
159,193,238,119,181,212,106,53,148,74,37,156,78,39,157,192,96,48,24,12,6,3,143,2
01,234,117,180,90,45,152,76,
38,19,135,205,232,116,58,29,128,64,32,16,8,4,2,1,0};
int index[256] ={176,89,81,169,235,245,215,117,233,174,232,231,234,214,175,80,216,45,118,123,23
6,23,246,12,82,161,170,157,
177,96,90,204,91,63,205,188,178,135,97,252,171,86,158,42,83,60,162,109,247,112,1
3,128,237,74,24,197,119,165,
124,184,217,68,46,32,163,66,110,72,84,58,61,133,159,94,43,21,172,212,87,243,98,1
91,253,221,179,152,136,145,
206,208,189,150,92,210,64,56,47,138,33,36,218,147,69,18,125,181,185,39,120,154,1
66,228,25,255,198,50,238,
223,75,104,14,100,129,141,248,193,113,8,88,168,244,116,173,230,213,79,44,122,22,
11,160,156,95,203,62,187,134,
251,85,41,59,108,111,127,73,196,164,183,67,31,65,71,57,132,93,20,211,242,190,220
,151,144,207,149,209,55,137,
35,146,17,180,38,153,227,254,49,222,103,99,140,192,7,167,115,229,78,121,10,155,2
02,186,250,40,107,126,195,
182,30,70,131,19,241,219,143,148,54,34,16,37,226,48,102,139,6,114,77,9,201,249,1
06,194,29,130,240,142,53,15,
225,101,5,76,200,105,28,239,52,224,4,199,27,51,3,26,2,1,0};
int alpha_int [256];
int index_int [256];
int g;
int i,r,j;
int nev;
int pol_err[8];
int temp_inv;


int lt[8]={1,1,1,1,1,1,1,1};
int w[8]={1,1,1,1,1,1,1,1};
int data[240];
int data1[256];
int data2[256];
int fb[17]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},lfr1[17]={0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0},lfr[16]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
//int poli[16]={59,36,50,98,229,41,65,163,8,30,209,68,189,104,13,59};
int poli[17]={59,36,50,98,229,41,65,163,8,30,209,68,189,104,13,59,1};
//int poli[17]={1,121,105,108,110,103,162,77,4,92,192,148,170,183,195,226,121};
//int poli[17]={121,126,195,183,170,148,192,92,4,77,162,103,110,108,105,121,1};
int shift=0;
int mult;
int a1,a2,a3,a4;
int fullw = 256;
int n = 256;
int k = 240;
int shif[17];
int shif1[17];
int fbb1[17];
int fbb2[17];
int sum=0;
int syn_error=0;


/// переворот таблицы
for (i=0;i<=255;i++)
{
alpha_int[i]=alpha[255-i];
index_int[i]=index[255-i];
}
////////////////////////////////////
///// инициализация даты
for (i=0 ; i<240; i++)
{
data[i] = 1;
data1[i] = 1;
}

for (i=1 ; i<240; i++)
{
data[i] = (data[i-1] + 1);
data1[i] = (data[i-1] + 1);
}

//////////////////////////////////



//data1[1] = 20;
///////////////////////////////////// обнуление сдвиговых регистров
for (i=0 ; i<17; i++)
{
shif[i]=0;
shif1[i]=0;
fbb1[i]=0;
fbb2[i]=0;
sum=0;
}
//////////////////////////////////////////////////
//// кодер вар 1
for (j=0 ; j<240; j++)
{
sum = data[j]^shif[15];
for (i=0 ; i<16; i++)
{
fbb1 [i] = alpha_int[add(index_int[sum],index_int[poli[i]])];
}
fbb2[0]= fbb1[0]^0;
for (i=1 ; i<16; i++)
{
fbb2[i]= fbb1[i]^shif[i-1];
}
for (i=0 ; i<16; i++)
{
shif[i]=fbb2[i];
}
}
/////////////////////////////////////////
/////кодер вар 2
for (i=0 ; i<240; i++)
{

fb[16]=lfr[15]^data[i];


for (j=0; j<16; j++)
{
//fb[j] = index_int[add(alpha_int[fb[16]],alpha_int[poli[j]])];
fb[j] = alpha_int[add(index_int[fb[16]],index_int[poli[j]])];

}
lfr[15]= fb[15]^lfr[14];
lfr[14]= fb[14]^lfr[13];
lfr[13]= fb[13]^lfr[12];
lfr[12]= fb[12]^lfr[11];
lfr[11]= fb[11]^lfr[10];
lfr[10]= fb[10]^lfr[9];
lfr[9]= fb[9]^lfr[8];
lfr[8]= fb[8]^lfr[7];
lfr[7]= fb[7]^lfr[6];
lfr[6]= fb[6]^lfr[5];
lfr[5]= fb[5]^lfr[4];
lfr[4]= fb[4]^lfr[3];
lfr[3]= fb[3]^lfr[2];
lfr[2]= fb[2]^lfr[1];
lfr[1]= fb[1]^lfr[0];
lfr[0] = fb[0]^0;

if (i==238)
n=n;

}
/////////////////////////////////////
///// добавление избытка
//for (i=240; i<256; i++)
for (j=0; j<16; j++)
//data1[255-j] = lfr [j];
data1[240+j] = lfr [j];
////////////////////////////////////////////
//// Syndrome Calculator
for (i=0;i<=15;i++)
{
s3[i]=0;
s4[i]=0;
}





j=0;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
if (i==239)
j=0;
if (i==254)
j=0;
}
j=1;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=2;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=3;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=4;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=5;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=6;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=7;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=8;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=9;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=10;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=11;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=12;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=13;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=14;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
}
j=15;
for (i=0;i<fullw;i++)
{
s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
if (i==239)
j=15;
if (i==254)
j=15;
}
/////////////////////////////////////////////////////////////////

}

int add(int x, int y)
{

if(x==0 || y==0)
return 0;
else if (x+y <= 256)
return x+y-1;
else
return x+y-256;
}

[*Игорь*]

Спасибо огромное за ссылки, долго пытался вникнуть. Очень интересный код.
Еще раз прошу помощи знающих и понимающих людей, может я не совсем точно и корректно задал вопрос, постараюсь расписать "больше некуда".

Коды Рида-Соломона.
Примитивный полином P = 1 +X^2 +X^3 +X^4 +X^8.
Порождающий полином = g =(X+ a^0 ) (X+ a^1 ) (X+ a^2 ) . . . (X+ a^15)

Немного теории. Идея кодов Рида-Соломона.
Основная идея помехозащитного кодирования Рида-Соломона заключается в умножении информационного слова, представленного в виде полинома D, на неприводимый полином G3, известный обеим сторонам, в результате чего получается кодовое слово C, опять-таки представленное в виде полинома. Декодирование осуществляется с точностью до наоборот: если при делении кодового слова C на полином G декодер внезапно получает остаток, то он может рапортовать наверх об ошибке. Соответственно, если кодовое слово разделилось нацело, его передача завершилась успешно.
Что делаем:
1. Добавляем к исходному информационному слову D справа k нулей, в результате чего у нас получается слово длины n = m + r и полином Xr∗D, где m – длина информационного слова.
2. Делим полученный полином X^r∗D на порождающий полином G и вычисляем остаток от деления R, такой что: X^r∗D = G∗Q + R, где Q – частное, которое игнорируется за ненадобностью, – интересует только остаток.
3. Добавляем остаток R к информационному слову D, в результате чего получаем симпатичное кодовое слово C, информационные биты которых хранятся отдельно от контрольных бит. Собственно, тот остаток, который получили в результате деления, и есть корректирующие коды Рида-Соломона. Способ кодирования, при котором информационные и контрольные символы хранятся раздельно, называется систематическим кодированием.
4. T = X^r∗D + R = G∗Q. - информационное слово + корректирующие коды.

И так вернемся к вопросу. Что бы далеко не ходить и глубоко не копать ссылка на статью Касперского http://samag.ru/archive/article/211, где можно найти простейшую схему кодера Рида-Соломона. Можно посмотреть для общего понятия.
Привожу два варианта кодера :

Код

int alpha[256]={142,71,173,216,108,54,27,131,207,233,250,125,176,88,44,22,11,139,203
,235,251,243,247,245,244,122,61,144,
        72,36,18,9,138,69,172,86,43,155,195,239,249,242,121,178,89,162,81,166,83,16
7,221
,224,112,56,28,14,7,141,200,
        100,50,25,130,65,174,87,165,220,110,55,149,196,98,49,150,75,171,219,227,255
,241,
246,123,179,215,229,252,126,
        63,145,198,99,191,209,230,115,183,213,228,114,57,146,73,170,85,164,82,41,15
4,77,
168,84,42,21,132,66,33,158,79,
        169,218,109,184,92,46,23,133,204,102,51,151,197,236,118,59,147,199,237,248,
124,6
2,31,129,206,103,189,208,104,
        52,26,13,136,68,34,17,134,67,175,217,226,113,182,91,163,223,225,254,127,177
,214,
107,187,211,231,253,240,120,
        60,30,15,137,202,101,188,94,47,153,194,97,190,95,161,222,111,185,210,105,18
6,93,
160,80,40,20,10,5,140,70,35,
        159,193,238,119,181,212,106,53,148,74,37,156,78,39,157,192,96,48,24,12,6,3,
143,2
01,234,117,180,90,45,152,76,
        38,19,135,205,232,116,58,29,128,64,32,16,8,4,2,1,0};
    int index[256] ={176,89,81,169,235,245,215,117,233,174,232,231,234,214,175,80,216,45,118,123,23
6,23,246,12,82,161,170,157,
        177,96,90,204,91,63,205,188,178,135,97,252,171,86,158,42,83,60,162,109,247,
112,1
3,128,237,74,24,197,119,165,
        124,184,217,68,46,32,163,66,110,72,84,58,61,133,159,94,43,21,172,212,87,243
,98,1
91,253,221,179,152,136,145,
        206,208,189,150,92,210,64,56,47,138,33,36,218,147,69,18,125,181,185,39,120,
154,1
66,228,25,255,198,50,238,
        223,75,104,14,100,129,141,248,193,113,8,88,168,244,116,173,230,213,79,44,12
2,22,
11,160,156,95,203,62,187,134,
        251,85,41,59,108,111,127,73,196,164,183,67,31,65,71,57,132,93,20,211,242,19
0,220
,151,144,207,149,209,55,137,
        35,146,17,180,38,153,227,254,49,222,103,99,140,192,7,167,115,229,78,121,10,
155,2
02,186,250,40,107,126,195,
        182,30,70,131,19,241,219,143,148,54,34,16,37,226,48,102,139,6,114,77,9,201,
249,1
06,194,29,130,240,142,53,15,
        225,101,5,76,200,105,28,239,52,224,4,199,27,51,3,26,2,1,0};

//int poli[16]={59,36,50,98,229,41,65,163,8,30,209,68,189,104,13,59};
int poli[17]={59,36,50,98,229,41,65,163,8,30,209,68,189,104,13,59,1};
//int poli[17]={1,121,105,108,110,103,162,77,4,92,192,148,170,183,195,226,121};
//int poli[17]={121,126,195,183,170,148,192,92,4,77,162,103,110,108,105,121,1};
///////////////////////////////////// обнуление сдвиговых регистров
for (i=0; i<17; i++)
{
    shif[i]=0;
    shif1[i]=0;
    fbb1[i]=0;
    fbb2[i]=0;
    sum=0;
}

for (j=0; j<240; j++)
{
sum = data[j]^shif[15];
for (i=0; i<16; i++)
{
    fbb1 [i] = alpha_int[add(index_int[sum],index_int[poli[i]])];
}
fbb2[0]= fbb1[0]^0;
for (i=1; i<16; i++)
{
    fbb2[i]= fbb1[i]^shif[i-1];
}
for (i=0; i<16; i++)
{
    shif[i]=fbb2[i];
}
}
/////////////////////////////////////////
for (i=0; i<240; i++)
{
    
    fb[16]=lfr[15]^data[i];

    
    for (j=0; j<16; j++)
    {
        //fb[j] = index_int[add(alpha_int[fb[16]],alpha_int[poli[j]])];
        fb[j] = alpha_int[add(index_int[fb[16]],index_int[poli[j]])];
    
    }
    lfr[15]= fb[15]^lfr[14];
    lfr[14]= fb[14]^lfr[13];
    lfr[13]= fb[13]^lfr[12];
    lfr[12]= fb[12]^lfr[11];
    lfr[11]= fb[11]^lfr[10];
    lfr[10]= fb[10]^lfr[9];
    lfr[9]= fb[9]^lfr[8];
    lfr[8]= fb[8]^lfr[7];
    lfr[7]= fb[7]^lfr[6];
    lfr[6]= fb[6]^lfr[5];
    lfr[5]= fb[5]^lfr[4];
    lfr[4]= fb[4]^lfr[3];
    lfr[3]= fb[3]^lfr[2];
    lfr[2]= fb[2]^lfr[1];
    lfr[1]= fb[1]^lfr[0];
    lfr[0] = fb[0]^0;

    if (i==238)
        n=n;

}

//for (i=240; i<256; i++)
    for (j=0; j<16; j++)
    //data1[255-j] = lfr [j];
    data1[240+j] = lfr [j];

Теперь приступаем к декодированию данных:
Принятое кодовое слово v с компонентами vi = ci + ei, где i = 0, … n – 1, представляет собой сумму кодового слова c и вектора ошибок e. Цель декодирования состоит в очистке кодового слова от вектора ошибки, описываемого полиномом синдрома и вычисляемого по формуле Sj = v(α^(j + j0 – 1)), где j изменяется от 1 до 2t, а α представляет собой примитивный член. Так же схему можно посмотреть по ссылке.
Код вычисления синдрома :

Код

//// Syndrome Calculator
    for (i=0;i<=15;i++)
        {
            s3[i]=0;
            s4[i]=0;
        }




    s3[0]=0;
    s4[0]=0;
    s5[0]=0;




        j=0;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
            if (i==239)
                j=0;
            if (i==254)
                j=0;
        }
        j=1;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=2;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=3;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=4;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=5;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=6;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=7;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=8;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=9;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=10;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=11;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=12;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=13;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=14;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
        }
        j=15;
        for (i=0;i<fullw;i++)
        {
            s3[j] = alpha_int[add(index_int[s3[j]],index_int[poli[j]])]^data1[i];
            if (i==239)
                j=15;
            if (i==254)
                j=15;
        }

Пожалуйста подскажите что не так где ошибка?.

Сообщение отредактировал *Игорь* - Dec 15 2015, 10:34

[_4afc_]

Еще раз прошу помощи знающих и понимающих людей, может я не совсем точно и корректно задал вопрос, постараюсь расписать "больше некуда".

Коды Рида-Соломона.
Примитивный полином P = 1 +X^2 +X^3 +X^4 +X^8.
Порождающий полином = g =(X+ a^0 ) (X+ a^1 ) (X+ a^2 ) . . . (X+ a^15)
Немного теории. Идея кодов Рида-Соломона...
И так вернемся к вопросу. Что бы далеко не ходить и глубоко не копать ссылка на статью Касперского.., где можно найти простейшую схему кодера Рида-Соломона.
Пожалуйста подскажите что не так где ошибка?

А вы сколько ошибок хотите исправить своими кодами Рида-Соломона?

Знаете, лет 25 назад я был Математиком. Тоже разговаривал на птичьем языке - аля синдром и галуа...
Раз уж вы искали понимающего - я вам расскажу как выглядит с точки зрения Инженера-практика код Рида-Соломона:

Возьмём конкретный пример, когда блок передаваемых данных меньше 256, исправляем один бит и полином равен 0x1d.
(при обработке 200 байт - 53 можно дополнить нулями)
вычисляем R и S, записываем их в 253 и 254 байт (при 253 данных от нуля).

Код

#define BLOCKSIZE       255
#define POLYNOM         0x1d    // Primitive polynomial over GF(256)
//------- Get R check symbol ------------
unsigned char Get_R(unsigned char *block)
{
unsigned char i,j,r,b;

r=0;
for(i=0;i<BLOCKSIZE-2;i++)
{
b=block[i];
for(j=0;j<8;j++)
  {
  if(r&0x80) r=(r<<1)^POLYNOM;
  else r<<=1;
  if(b&0x80) r^=POLYNOM;
  b<<=1;
  }
}
return r;
}
//------- Get S check symbol ------------
unsigned char Get_S(unsigned char *block)
{
unsigned char i,s;
s=0;
for(i=0;i<BLOCKSIZE-2;i++) s^=block[i];
return s;}

В декодере, если R и S не совпадут с переданными данными, то один из них указывает на байт в котором ошибка - другой на бит в байте, т.е. его надо инвертировать и всё.

Надеюсь декодер приводить не надо?