rs255253.c

Reed Solomon（255/253）纠错码的编解码器

/*
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
[e-mail]
*/


#include <stdio.h>
#include <stdlib.h>

#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;
}

//------ 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<BLOCKSIZE;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<BLOCKSIZE-2;i++) block[i]=rand();

// 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);
}