rs.c

无线通讯中使用的一种揪错算法,rs 1.0 揪错能力可配置 能纠正 (冗余长度)/2-1 个错误

/* 
 * Reed Solomon Encoder/Decoder 
 *
 * (c) Henry Minsky ([e-mail]), Universal Access 1991-1995
 */

#include <stdio.h>
#include <ctype.h>
#include "ecc.h"

/* Encoder parity bytes */
char pBytes[MAXDEG];

/* Decoder syndrome bytes */
char synBytes[MAXDEG];

/* generator polynomial */
char genPoly[MAXDEG*2];

int DEBUG = TRUE;

static void compute_genpoly (int nbytes, char genpoly[]);

// Initialize lookup tables, polynomials, etc.
void initialize_ecc ()
{
	// Initialize the galois field arithmetic tables
	init_galois_tables();

	// Compute the encoder generator polynomial
	compute_genpoly(NPAR, genPoly);
}
// Append the parity bytes onto the end of the message
void build_codeword (unsigned char msg[], int nbytes, unsigned char dst[])
{
	int i;
	
	memcpy ( dst , msg , nbytes ) ;
	for (i = 0; i < NPAR; i++) {
		dst[i+nbytes] = pBytes[NPAR-1-i];
	}
}

/**********************************************************
 * Reed Solomon Decoder 
 *
 * Computes the syndrome of a codeword. Puts the results
 * into the synBytes[] array.
 */

void decode_data(unsigned char data[], int nbytes)
{
	int i, j, sum;
	for (j = 0; j < NPAR; j++) {
		sum	= 0;
		for (i = 0; i < nbytes; i++) {
			sum = data[i] ^ gmult(gexp[j+1], sum);
		}
		synBytes[j]	= sum;
	}
}

// Check if the syndrome is zero
int check_syndrome (void)
{
	int i, nz = 0;
	for (i =0 ; i < NPAR; i++) {
		if (synBytes[i] != 0) nz = 1;
	}
	return nz;
}

/* Create a generator polynomial for an n byte RS code. 
 * The coefficients are returned in the genPoly arg.
 * Make sure that the genPoly array which is passed in is 
 * at least n+1 bytes long.
 */

static void compute_genpoly (int nbytes, char genpoly[])
{
	int i;
	char tp[256], tp1[256];
	
	// multiply (x + a^n) for n = 1 to nbytes

	zero_poly(tp1);
	tp1[0] = 1;

	for (i = 1; i <= nbytes; i++) {
		zero_poly(tp);
		tp[0] = gexp[i];		// set up x+a^n
		tp[1] = 1;
		
		mult_polys(genpoly, tp, tp1);
		copy_poly(tp1, genpoly);
	}
}

/* Simulate a LFSR with generator polynomial for n byte RS code. 
 * Pass in a pointer to the data array, and amount of data. 
 *
 * The parity bytes are deposited into pBytes[], and the whole message
 * and parity are copied to dest to make a codeword.
 * 
 */

void encode_data (unsigned char msg[], int nbytes, unsigned char dst[])
{
	int i, LFSR[NPAR+1],dbyte, j;
	
	for(i=0; i < NPAR+1; i++) LFSR[i]=0;

	for (i = 0; i < nbytes; i++) {
		dbyte = msg[i] ^ LFSR[NPAR-1];
		for (j = NPAR-1; j > 0; j--) {
			LFSR[j] = LFSR[j-1] ^ gmult(genPoly[j], dbyte);
		}
		LFSR[0] = gmult(genPoly[0], dbyte);
	}
	for (i = 0; i < NPAR; i++) 
		pBytes[i] = LFSR[i];
	build_codeword(msg, nbytes, dst);
}