Отправлено si 27 августа 2003 г. 22:03 В ответ на: Ребята может подскажете эффективный алгоритм для декодирования кодов Рида-Соломона отправлено virtual_girl 27 августа 2003 г. 21:59

/*
Single error correcting (255,253) systematic Reed Solomon Code (over GF(256))
Encodes 253 bytes of data to the block of 255 bytes.
This perfect code can correct one byte error per block,
but can't detect more than one error.

(c)VLV
vlv@writeme.com
http://www.geocities.com/SiliconValley/4795
*/

#include
#include

#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 {
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;ireturn s;
}

//------ Encode block of data -------------

void Encode(unsigned char *block)
{
block[BLOCKSIZE-2]=Get_R(block);
block[BLOCKSIZE-1]=Get_S(block);
}

//----- Decode block of data (correct up to one error) -------
//------ Returns the amount of errors (0,1) ------------------

unsigned char Decode(unsigned char *block)
{
unsigned char r,s,sr,ss,i;

// Calculate the syndromes R and S

sr=block[BLOCKSIZE-2]^(r=Get_R(block));
ss=block[BLOCKSIZE-1]^(s=Get_S(block));

if((!sr)&&(!ss)) return 0; // No errors

if((sr)&&(!ss)) // Error in R
{
block[BLOCKSIZE-2]=r;
return 1;
}

if((!sr)&&(ss)) // Error in S
{
block[BLOCKSIZE-1]=s;
return 1;
}

// Error in data - calculate the position

i=0;
while(sr!=ss)
{
if(sr&0x80) sr=(sr<<1)^POLYNOM;
else sr<<=1;
i++;
}

// Field element to error location

i=(i>>3) + ((i&7)<<5) - 2;

// Correct the error

block[i]^=ss;

return 1;
}

//------- Example -------------------
void PrintData(unsigned char *block)
{
unsigned char i;

for(i=0;i {
if(!(i&0x07)) printf("\n");
printf("0x%02x,",block[i]);
}
}

void main(void)
{
unsigned char i,pos,e;
unsigned char block[BLOCKSIZE];

// Fill the block with the data to be protected

for(i=0;i// Encode the block to (255,253) code

Encode(block);

printf("\n\n Initial coded block:");
PrintData(block);

// Corrupt block with random error at random position

while(!(e=rand())); // Random error value, not equal to 0
while(0xFF==(pos=rand())); // Random error position, not equal to 255

block[pos]^=e;

printf("\n\n Corrupted block (error=%02x,position=%02x):",e,pos);
PrintData(block);

Decode(block);

printf("\n\n Corrected block:");
PrintData(block);
}

• Где инклуды :) — si   (27.08.2003 22:04, 41 байт)
  • А их ХТМЛ скушал — -=L.A.=-   (28.08.2003 08:14, пустое)