/*
* Reed-Solomon coding and decoding
* Phil Karn (karn@ka9q.ampr.org) September 1996
* Separate CCSDS version create Dec 1998, merged into this version May 1999
*
* This file is derived from my generic RS encoder/decoder, which is
* in turn based on the program "new_rs_erasures.c" by Robert
* Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari Thirumoorthy
* (harit@spectra.eng.hawaii.edu), Aug 1995
* Copyright 1999 Phil Karn, KA9Q
* May be used under the terms of the GNU public license
*/
#include <stdio.h>
#include "rs.h"
#ifdef CCSDS
/* CCSDS field generator polynomial: 1+x+x^2+x^7+x^8 */
int Pp[MM+1] = { 1, 1, 1, 0, 0, 0, 0, 1, 1 };
#else /* not CCSDS */
/* MM, KK, B0, PRIM are user-defined in rs.h */
/* Primitive polynomials - see Lin & Costello, Appendix A,
* and Lee & Messerschmitt, p. 453.
*/
#if(MM == 2)/* Admittedly silly */
int Pp[MM+1] = { 1, 1, 1 };
#elif(MM == 3)
/* 1 + x + x^3 */
int Pp[MM+1] = { 1, 1, 0, 1 };
#elif(MM == 4)
/* 1 + x + x^4 */
int Pp[MM+1] = { 1, 1, 0, 0, 1 };
#elif(MM == 5)
/* 1 + x^2 + x^5 */
int Pp[MM+1] = { 1, 0, 1, 0, 0, 1 };
#elif(MM == 6)
/* 1 + x + x^6 */
int Pp[MM+1] = { 1, 1, 0, 0, 0, 0, 1 };
#elif(MM == 7)
/* 1 + x^3 + x^7 */
int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 1 };
#elif(MM == 8)
/* 1+x^2+x^3+x^4+x^8 */
int Pp[MM+1] = { 1, 0, 1, 1, 1, 0, 0, 0, 1 };
#elif(MM == 9)
/* 1+x^4+x^9 */
int Pp[MM+1] = { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 };
#elif(MM == 10)
/* 1+x^3+x^10 */
int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
#elif(MM == 11)
/* 1+x^2+x^11 */
int Pp[MM+1] = { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
#elif(MM == 12)
/* 1+x+x^4+x^6+x^12 */
int Pp[MM+1] = { 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1 };
#elif(MM == 13)
/* 1+x+x^3+x^4+x^13 */
int Pp[MM+1] = { 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
#elif(MM == 14)
/* 1+x+x^6+x^10+x^14 */
int Pp[MM+1] = { 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 };
#elif(MM == 15)
/* 1+x+x^15 */
int Pp[MM+1] = { 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
#elif(MM == 16)
/* 1+x+x^3+x^12+x^16 */
int Pp[MM+1] = { 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 };
#else
#error "Either CCSDS must be defined, or MM must be set in range 2-16"
#endif
#endif
/* This defines the type used to store an element of the Galois Field
* used by the code. Make sure this is something larger than a char if
* if anything larger than GF(256) is used.
*
* Note: unsigned char will work up to GF(256) but int seems to run
* faster on the Pentium.
*/
typedef int gf;
/* index->polynomial form conversion table */
static gf Alpha_to[NN + 1];
/* Polynomial->index form conversion table */
static gf Index_of[NN + 1];
/* No legal value in index form represents zero, so
* we need a special value for this purpose
*/
#define A0 (NN)
/* Generator polynomial g(x) in index form */
static gf Gg[NN - KK + 1];
static int RS_init; /* Initialization flag */
/* Compute x % NN, where NN is 2**MM - 1,
* without a slow divide
*/
static inline gf
modnn(int x)
{
while (x >= NN) {
x -= NN;
x = (x >> MM) + (x & NN);
}
return x;
}
#define min(a,b) ((a) < (b) ? (a) : (b))
#define CLEAR(a,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = 0;\
}
#define COPY(a,b,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = (b)[ci];\
}
#define COPYDOWN(a,b,n) {\
int ci;\
for(ci=(n)-1;ci >=0;ci--)\
(a)[ci] = (b)[ci];\
}
static void init_rs(void);
#ifdef CCSDS
/* Conversion lookup tables from conventional alpha to Berlekamp's
* dual-basis representation. Used in the CCSDS version only.
* taltab[] -- convert conventional to dual basis
* tal1tab[] -- convert dual basis to conventional
* Note: the actual RS encoder/decoder works with the conventional basis.
* So data is converted from dual to conventional basis before either
* encoding or decoding and then converted back.
*/
static unsigned char taltab[NN+1],tal1tab[NN+1];
static unsigned char tal[] = { 0x8d, 0xef, 0xec, 0x86, 0xfa, 0x99, 0xaf, 0x7b };
/* Generate conversion lookup tables between conventional alpha representation
* (@**7, @**6, ...@**0)
* and Berlekamp's dual basis representation
* (l0, l1, ...l7)
*/
static void
gen_ltab(void)
{
int i,j,k;
for(i=0;i<256;i++){/* For each value of input */
taltab[i] = 0;
for(j=0;j<8;j++) /* for each column of matrix */
for(k=0;k<8;k++){ /* for each row of matrix */
if(i & (1<<k))
taltab[i] ^= tal[7-k] & (1<<j);
}
tal1tab[taltab[i]] = i;
}
}
#endif /* CCSDS */
#if PRIM != 1
static int Ldec;/* Decrement for aux location variable in Chien search */
static void
gen_ldec(void)
{
for(Ldec=1;(Ldec % PRIM) != 0;Ldec+= NN)
;
Ldec /= PRIM;
}
#else
#define Ldec 1
#endif
/* generate GF(2**m) from the irreducible polynomial p(X) in Pp[0]..Pp[m]
lookup tables: index->polynomial form alpha_to[] contains j=alpha**i;
polynomial form -> index form index_of[j=alpha**i] = i
alpha=2 is the primitive element of GF(2**m)
HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows:
Let @ represent the primitive element commonly called "alpha" that
is the root of the primitive polynomial p(x). Then in GF(2^m), for any
0 <= i <= 2^m-2,
@^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
example the polynomial representation of @^5 would be given by the binary
representation of the integer "alpha_to[5]".
Similarily, index_of[] can be used as follows:
As above, let @ represent the primitive element of GF(2^m) that is
the root of the primitive polynomial p(x). In order to find the power
of @ (alpha) that has the polynomial representation
a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
we consider the integer "i" whose binary representation with a(0) being LSB
and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
"index_of[i]". Now, @^index_of[i] is that element whose polynomial
representation is (a(0),a(1),a(2),...,a(m-1)).
NOTE:
The element alpha_to[2^m-1] = 0 always signifying that the
representation of "@^infinity" = 0 is (0,0,0,...,0).
Similarily, the element index_of[0] = A0 always signifying
that the power of alpha which has the polynomial representation
(0,0,...,0) is "infinity".
*/
static void
generate_gf(void)
{
register int i, mask;
mask = 1;
Alpha_to[MM] = 0;
for (i = 0; i < MM; i++) {
Alpha_to[i] = mask;
Index_of[Alpha_to[i]] = i;
/* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */
if (Pp[i] != 0)
Alpha_to[MM] ^= mask; /* Bit-wise EXOR operation */
mask <<= 1; /* single left-shift */
}
Index_of[Alpha_to[MM]] = MM;
/*
* Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by
* poly-repr of @^i shifted left one-bit and accounting for any @^MM
* term that may occur when poly-repr of @^i is shifted.
*/
mask >>= 1;
for (i = MM + 1; i < NN; i++) {
if (Alpha_to[i - 1] >= mask)
Alpha_to[i] = Alpha_to[MM] ^ ((Alpha_to[i - 1] ^ mask) << 1);
else
Alpha_to[i] = Alpha_to[i - 1] << 1;
Index_of[Alpha_to[i]] = i;
}
Index_of[0] = A0;
Alpha_to[NN] = 0;
}
/*
* Obtain the generator polynomial of the TT-error correcting, length
* NN=(2**MM -1) Reed Solomon code from the product of (X+@**(B0+i)), i = 0,
* ... ,(2*TT-1)
*
* Examples:
*
* If B0 = 1, TT = 1. deg(g(x)) = 2*TT = 2.
* g(x) = (x+@) (x+@**2)
*
* If B0 = 0, TT = 2. deg(g(x)) = 2*TT = 4.
* g(x) = (x+1) (x+@) (x+@**2) (x+@**3)
*/
static void
gen_poly(void)
{
register int i, j;
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
FEC.rar (55个子文件)
fano1.1
fano.h 378B
fano.c 7KB
README 5KB
sim.c 1KB
seqtest.c 6KB
tab.c 922B
Makefile 317B
metrics.c 3KB
viterbi-3.0.1
viterbi37.c 6KB
vitfilt27.c 9KB
vitfilt37.c 10KB
viterbi27.c 5KB
vittest.c 5KB
encode37.c 914B
viterbi.c 5KB
README 5KB
viterbi27.h 3KB
sim.c 1KB
tab.c 922B
encode27.c 823B
Makefile 1KB
viterbi37.h 3KB
genviterbi.pl 6KB
metrics.c 3KB
rs32
rs32.h 2KB
rs32.c 12KB
README 562B
rs32asm.s 4KB
rstest.c 4KB
Makefile 217B
rs-2.0
rs.c 18KB
rs.h 2KB
rstest.c 4KB
readme 8KB
Makefile 152B
simd-viterbi-1.0
parity.c 407B
vtest27.s 26KB
sse2bfly29.s 6KB
ssebfly29.s 6KB
viterbi27.c 5KB
makefile 3KB
ssebfly27.s 4KB
cpu_features.s 198B
sse2bfly27.s 4KB
mmxbfly29.s 3KB
mmxbfly27.s 3KB
README 977B
viterbi27.h 1KB
vtest29.c 3KB
viterbi29.c 5KB
vtest27.c 3KB
parity.h 532B
viterbi29.h 2KB
simd-viterbi.3 7KB
www.pudn.com.txt 218B
共 55 条
- 1
goldmusic
- 粉丝: 0
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
前往页