You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
296 lines
7.3 KiB
296 lines
7.3 KiB
/* Test the Reed-Solomon codecs |
|
* for various block sizes and with random data and random error patterns |
|
* |
|
* Copyright 2002 Phil Karn, KA9Q |
|
* May be used under the terms of the GNU Lesser General Public License (LGPL) |
|
*/ |
|
|
|
#include <stdio.h> |
|
#include <stdlib.h> |
|
#include <memory.h> |
|
#include <time.h> |
|
#include "fec.h" |
|
|
|
|
|
struct etab { |
|
int symsize; |
|
int genpoly; |
|
int fcs; |
|
int prim; |
|
int nroots; |
|
int ntrials; |
|
} Tab[] = { |
|
{2, 0x7, 1, 1, 1, 10 }, |
|
{3, 0xb, 1, 1, 2, 10 }, |
|
{4, 0x13, 1, 1, 4, 10 }, |
|
{5, 0x25, 1, 1, 6, 10 }, |
|
{6, 0x43, 1, 1, 8, 10 }, |
|
{7, 0x89, 1, 1, 10, 10 }, |
|
{8, 0x11d, 1, 1, 32, 10 }, |
|
{8, 0x187, 112,11, 32, 10 }, /* Duplicates CCSDS codec */ |
|
{9, 0x211, 1, 1, 32, 10 }, |
|
{10,0x409, 1, 1, 32, 10 }, |
|
{11,0x805, 1, 1, 32, 10 }, |
|
{12,0x1053, 1, 1, 32, 5 }, |
|
{13,0x201b, 1, 1, 32, 2 }, |
|
{14,0x4443, 1, 1, 32, 1 }, |
|
{15,0x8003, 1, 1, 32, 1 }, |
|
{16,0x1100b, 1, 1, 32, 1 }, |
|
{0, 0, 0, 0, 0}, |
|
}; |
|
|
|
int exercise_char(struct etab *e); |
|
int exercise_int(struct etab *e); |
|
int exercise_8(void); |
|
|
|
int main(){ |
|
int i; |
|
|
|
srandom(time(NULL)); |
|
|
|
printf("Testing fixed CCSDS encoder...\n"); |
|
exercise_8(); |
|
for(i=0;Tab[i].symsize != 0;i++){ |
|
int nn,kk; |
|
|
|
nn = (1<<Tab[i].symsize) - 1; |
|
kk = nn - Tab[i].nroots; |
|
printf("Testing (%d,%d) code...\n",nn,kk); |
|
if(Tab[i].symsize <= 8) |
|
exercise_char(&Tab[i]); |
|
else |
|
exercise_int(&Tab[i]); |
|
} |
|
exit(0); |
|
} |
|
|
|
int exercise_8(void){ |
|
int nn = 255; |
|
unsigned char block[nn],tblock[nn]; |
|
int errlocs[nn],derrlocs[nn]; |
|
int i; |
|
int errors; |
|
int derrors,kk; |
|
int errval,errloc; |
|
int erasures; |
|
int decoder_errors = 0; |
|
|
|
/* Compute code parameters */ |
|
kk = 223; |
|
|
|
|
|
/* Test up to the error correction capacity of the code */ |
|
for(errors=0;errors<=(nn-kk)/2;errors++){ |
|
|
|
/* Load block with random data and encode */ |
|
for(i=0;i<kk;i++) |
|
block[i] = random() & nn; |
|
memcpy(tblock,block,sizeof(block)); |
|
encode_rs_8(block,&block[kk],0); |
|
|
|
/* Make temp copy, seed with errors */ |
|
memcpy(tblock,block,sizeof(block)); |
|
memset(errlocs,0,sizeof(errlocs)); |
|
memset(derrlocs,0,sizeof(derrlocs)); |
|
erasures=0; |
|
for(i=0;i<errors;i++){ |
|
do { |
|
errval = random() & nn; |
|
} while(errval == 0); /* Error value must be nonzero */ |
|
|
|
do { |
|
errloc = random() % nn; |
|
} while(errlocs[errloc] != 0); /* Must not choose the same location twice */ |
|
|
|
errlocs[errloc] = 1; |
|
|
|
#if FLAG_ERASURE |
|
if(random() & 1) /* 50-50 chance */ |
|
derrlocs[erasures++] = errloc; |
|
#endif |
|
tblock[errloc] ^= errval; |
|
} |
|
|
|
/* Decode the errored block */ |
|
derrors = decode_rs_8(tblock,derrlocs,erasures,0); |
|
|
|
if(derrors != errors){ |
|
printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors); |
|
decoder_errors++; |
|
} |
|
for(i=0;i<derrors;i++){ |
|
if(errlocs[derrlocs[i]] == 0){ |
|
printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]); |
|
decoder_errors++; |
|
} |
|
} |
|
if(memcmp(tblock,block,sizeof(tblock)) != 0){ |
|
printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk); |
|
decoder_errors++; |
|
for(i=0;i<nn;i++) |
|
printf(" %02x",tblock[i] ^ block[i]); |
|
printf("\n"); |
|
} |
|
} |
|
return decoder_errors; |
|
} |
|
|
|
|
|
int exercise_char(struct etab *e){ |
|
int nn = (1<<e->symsize) - 1; |
|
unsigned char block[nn],tblock[nn]; |
|
int errlocs[nn],derrlocs[nn]; |
|
int i; |
|
int errors; |
|
int derrors,kk; |
|
int errval,errloc; |
|
int erasures; |
|
int decoder_errors = 0; |
|
void *rs; |
|
|
|
if(e->symsize > 8) |
|
return -1; |
|
|
|
/* Compute code parameters */ |
|
kk = nn - e->nroots; |
|
|
|
rs = init_rs_char(e->symsize,e->genpoly,e->fcs,e->prim,e->nroots,0); |
|
if(rs == NULL){ |
|
printf("init_rs_char failed!\n"); |
|
return -1; |
|
} |
|
/* Test up to the error correction capacity of the code */ |
|
for(errors=0;errors <= e->nroots/2;errors++){ |
|
|
|
/* Load block with random data and encode */ |
|
for(i=0;i<kk;i++) |
|
block[i] = random() & nn; |
|
memcpy(tblock,block,sizeof(block)); |
|
encode_rs_char(rs,block,&block[kk]); |
|
|
|
/* Make temp copy, seed with errors */ |
|
memcpy(tblock,block,sizeof(block)); |
|
memset(errlocs,0,sizeof(errlocs)); |
|
memset(derrlocs,0,sizeof(derrlocs)); |
|
erasures=0; |
|
for(i=0;i<errors;i++){ |
|
do { |
|
errval = random() & nn; |
|
} while(errval == 0); /* Error value must be nonzero */ |
|
|
|
do { |
|
errloc = random() % nn; |
|
} while(errlocs[errloc] != 0); /* Must not choose the same location twice */ |
|
|
|
errlocs[errloc] = 1; |
|
|
|
#if FLAG_ERASURE |
|
if(random() & 1) /* 50-50 chance */ |
|
derrlocs[erasures++] = errloc; |
|
#endif |
|
tblock[errloc] ^= errval; |
|
} |
|
|
|
/* Decode the errored block */ |
|
derrors = decode_rs_char(rs,tblock,derrlocs,erasures); |
|
|
|
if(derrors != errors){ |
|
printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors); |
|
decoder_errors++; |
|
} |
|
for(i=0;i<derrors;i++){ |
|
if(errlocs[derrlocs[i]] == 0){ |
|
printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]); |
|
decoder_errors++; |
|
} |
|
} |
|
if(memcmp(tblock,block,sizeof(tblock)) != 0){ |
|
printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk); |
|
decoder_errors++; |
|
for(i=0;i<nn;i++) |
|
printf(" %02x",tblock[i] ^ block[i]); |
|
printf("\n"); |
|
} |
|
} |
|
|
|
free_rs_char(rs); |
|
return 0; |
|
} |
|
|
|
int exercise_int(struct etab *e){ |
|
int nn = (1<<e->symsize) - 1; |
|
int block[nn],tblock[nn]; |
|
int errlocs[nn],derrlocs[nn]; |
|
int i; |
|
int errors; |
|
int derrors,kk; |
|
int errval,errloc; |
|
int erasures; |
|
int decoder_errors = 0; |
|
void *rs; |
|
|
|
/* Compute code parameters */ |
|
kk = nn - e->nroots; |
|
|
|
rs = init_rs_int(e->symsize,e->genpoly,e->fcs,e->prim,e->nroots,0); |
|
if(rs == NULL){ |
|
printf("init_rs_int failed!\n"); |
|
return -1; |
|
} |
|
/* Test up to the error correction capacity of the code */ |
|
for(errors=0;errors <= e->nroots/2;errors++){ |
|
|
|
/* Load block with random data and encode */ |
|
for(i=0;i<kk;i++) |
|
block[i] = random() & nn; |
|
memcpy(tblock,block,sizeof(block)); |
|
encode_rs_int(rs,block,&block[kk]); |
|
|
|
/* Make temp copy, seed with errors */ |
|
memcpy(tblock,block,sizeof(block)); |
|
memset(errlocs,0,sizeof(errlocs)); |
|
memset(derrlocs,0,sizeof(derrlocs)); |
|
erasures=0; |
|
for(i=0;i<errors;i++){ |
|
do { |
|
errval = random() & nn; |
|
} while(errval == 0); /* Error value must be nonzero */ |
|
|
|
do { |
|
errloc = random() % nn; |
|
} while(errlocs[errloc] != 0); /* Must not choose the same location twice */ |
|
|
|
errlocs[errloc] = 1; |
|
|
|
#if FLAG_ERASURE |
|
if(random() & 1) /* 50-50 chance */ |
|
derrlocs[erasures++] = errloc; |
|
#endif |
|
tblock[errloc] ^= errval; |
|
} |
|
|
|
/* Decode the errored block */ |
|
derrors = decode_rs_int(rs,tblock,derrlocs,erasures); |
|
|
|
if(derrors != errors){ |
|
printf("(%d,%d) decoder says %d errors, true number is %d\n",nn,kk,derrors,errors); |
|
decoder_errors++; |
|
} |
|
for(i=0;i<derrors;i++){ |
|
if(errlocs[derrlocs[i]] == 0){ |
|
printf("(%d,%d) decoder indicates error in location %d without error\n",nn,kk,derrlocs[i]); |
|
decoder_errors++; |
|
} |
|
} |
|
if(memcmp(tblock,block,sizeof(tblock)) != 0){ |
|
printf("(%d,%d) decoder uncorrected errors! output ^ input:",nn,kk); |
|
decoder_errors++; |
|
for(i=0;i<nn;i++) |
|
printf(" %02x",tblock[i] ^ block[i]); |
|
printf("\n"); |
|
} |
|
} |
|
|
|
free_rs_int(rs); |
|
return 0; |
|
}
|
|
|