标题:
一种RS编码数据校验方法 源程序
[打印本页]
作者:
yancey1989
时间:
2020-7-20 16:56
标题:
一种RS编码数据校验方法 源程序
数据收发可能会出现误码率,特别是在无线通信领域中, 通过增加数据长度, 可恢复误码数据。
#include"reedsolomon.h"
unsigned int poly_g[17] = {
79 , 44 , 81 , 100 , 49 , 183 , 56 , 17 ,
232 , 187 , 126 , 104 , 31 , 103 , 52 , 118 ,
1 };
unsigned int alpha_to[256] = {
1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 ,
29 , 58 , 116 , 232 , 205 , 135 , 19 , 38 ,
76 , 152 , 45 , 90 , 180 , 117 , 234 , 201 ,
143 , 3 , 6 , 12 , 24 , 48 , 96 , 192 ,
157 , 39 , 78 , 156 , 37 , 74 , 148 , 53 ,
106 , 212 , 181 , 119 , 238 , 193 , 159 , 35 ,
70 , 140 , 5 , 10 , 20 , 40 , 80 , 160 ,
93 , 186 , 105 , 210 , 185 , 111 , 222 , 161 ,
95 , 190 , 97 , 194 , 153 , 47 , 94 , 188 ,
101 , 202 , 137 , 15 , 30 , 60 , 120 , 240 ,
253 , 231 , 211 , 187 , 107 , 214 , 177 , 127 ,
254 , 225 , 223 , 163 , 91 , 182 , 113 , 226 ,
217 , 175 , 67 , 134 , 17 , 34 , 68 , 136 ,
13 , 26 , 52 , 104 , 208 , 189 , 103 , 206 ,
129 , 31 , 62 , 124 , 248 , 237 , 199 , 147 ,
59 , 118 , 236 , 197 , 151 , 51 , 102 , 204 ,
133 , 23 , 46 , 92 , 184 , 109 , 218 , 169 ,
79 , 158 , 33 , 66 , 132 , 21 , 42 , 84 ,
168 , 77 , 154 , 41 , 82 , 164 , 85 , 170 ,
73 , 146 , 57 , 114 , 228 , 213 , 183 , 115 ,
230 , 209 , 191 , 99 , 198 , 145 , 63 , 126 ,
252 , 229 , 215 , 179 , 123 , 246 , 241 , 255 ,
227 , 219 , 171 , 75 , 150 , 49 , 98 , 196 ,
149 , 55 , 110 , 220 , 165 , 87 , 174 , 65 ,
130 , 25 , 50 , 100 , 200 , 141 , 7 , 14 ,
28 , 56 , 112 , 224 , 221 , 167 , 83 , 166 ,
81 , 162 , 89 , 178 , 121 , 242 , 249 , 239 ,
195 , 155 , 43 , 86 , 172 , 69 , 138 , 9 ,
18 , 36 , 72 , 144 , 61 , 122 , 244 , 245 ,
247 , 243 , 251 , 235 , 203 , 139 , 11 , 22 ,
44 , 88 , 176 , 125 , 250 , 233 , 207 , 131 ,
27 , 54 , 108 , 216 , 173 , 71 , 142 , 0
};
unsigned int index_of[256] = {
0 , 1 , 25 , 2 , 50 , 26 , 198 , 3 ,
223 , 51 , 238 , 27 , 104 , 199 , 75 , 4 ,
100 , 224 , 14 , 52 , 141 , 239 , 129 , 28 ,
193 , 105 , 248 , 200 , 8 , 76 , 113 , 5 ,
138 , 101 , 47 , 225 , 36 , 15 , 33 , 53 ,
147 , 142 , 218 , 240 , 18 , 130 , 69 , 29 ,
181 , 194 , 125 , 106 , 39 , 249 , 185 , 201 ,
154 , 9 , 120 , 77 , 228 , 114 , 166 , 6 ,
191 , 139 , 98 , 102 , 221 , 48 , 253 , 226 ,
152 , 37 , 179 , 16 , 145 , 34 , 136 , 54 ,
208 , 148 , 206 , 143 , 150 , 219 , 189 , 241 ,
210 , 19 , 92 , 131 , 56 , 70 , 64 , 30 ,
66 , 182 , 163 , 195 , 72 , 126 , 110 , 107 ,
58 , 40 , 84 , 250 , 133 , 186 , 61 , 202 ,
94 , 155 , 159 , 10 , 21 , 121 , 43 , 78 ,
212 , 229 , 172 , 115 , 243 , 167 , 87 , 7 ,
112 , 192 , 247 , 140 , 128 , 99 , 13 , 103 ,
74 , 222 , 237 , 49 , 197 , 254 , 24 , 227 ,
165 , 153 , 119 , 38 , 184 , 180 , 124 , 17 ,
68 , 146 , 217 , 35 , 32 , 137 , 46 , 55 ,
63 , 209 , 91 , 149 , 188 , 207 , 205 , 144 ,
135 , 151 , 178 , 220 , 252 , 190 , 97 , 242 ,
86 , 211 , 171 , 20 , 42 , 93 , 158 , 132 ,
60 , 57 , 83 , 71 , 109 , 65 , 162 , 31 ,
45 , 67 , 216 , 183 , 123 , 164 , 118 , 196 ,
23 , 73 , 236 , 127 , 12 , 111 , 246 , 108 ,
161 , 59 , 82 , 41 , 157 , 85 , 170 , 251 ,
96 , 134 , 177 , 187 , 204 , 62 , 90 , 203 ,
89 , 95 , 176 , 156 , 169 , 160 , 81 , 11 ,
245 , 22 , 235 , 122 , 117 , 44 , 215 , 79 ,
174 , 213 , 233 , 230 , 231 , 173 , 232 , 116 ,
214 , 244 , 234 , 168 , 80 , 88 , 175 , 0
};
unsigned int Galois_Mul(unsigned int a, unsigned int b)
{
unsigned int a1;
unsigned int b1;
if(a*b==0)
return 0;
a1 = index_of[a-1];
b1 = index_of[b-1];
a1 = a1 + b1;
if(a1 >= (1<<RS_PARA_M) - 1)
a1 = a1 - (1<<RS_PARA_M) + 1;
return alpha_to[a1];
}
unsigned int Galois_Add(unsigned int a, unsigned int b)
{
int i;
unsigned int a1, b1, c;
c = 0;
for(i=0; i<RS_PARA_M; i++)
{
a1 = a & (1<<i);
b1 = b & (1<<i);
c = c | a1^b1;
}
return c;
}
void rs_enc(unsigned int *msg, unsigned int *tx)
{
int i,j;
unsigned int feedback;
unsigned int rr[RS_PARA_N - RS_PARA_K];
for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
rr[i] = 0;
for(i=0; i<RS_PARA_K; i++)
tx[i] = *msg++;
for(i=RS_PARA_K; i<RS_PARA_N; i++)
tx[i] = 0;
for(i=0; i<RS_PARA_N; i++)
{
feedback = rr[RS_PARA_N - RS_PARA_K - 1];
for(j = RS_PARA_N - RS_PARA_K - 1; j>0; j--)
{
if(poly_g[j] != 0)
rr[j] = Galois_Add(rr[j-1], Galois_Mul(poly_g[j], feedback));
else
rr[j] = rr[j-1];
}
rr[0] = Galois_Add(tx[i], Galois_Mul(poly_g[0], feedback));
}
for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
tx[i+RS_PARA_K] = rr[RS_PARA_N - RS_PARA_K - i - 1];
}
unsigned int Galois_poly_val(unsigned int *poly_coef, unsigned int poly_order, unsigned int val)
{
int i;
unsigned int x, y, tmp;
x = index_of[val - 1];
y = poly_coef[0];
for(i=0; i<poly_order-1; i++)
{
tmp = (i+1)*x;
while(tmp >= ((1<<RS_PARA_M) - 1))
tmp = tmp - (1<<RS_PARA_M) + 1;
tmp = alpha_to[tmp];
tmp = Galois_Mul(poly_coef[i+1], tmp);
y = Galois_Add(y, tmp);
}
return y;
}
unsigned int Galois_Reverse(unsigned int a)
{
unsigned y;
y = index_of[a-1];
y = (1<<RS_PARA_M) - 1 - y;
y = alpha_to[y-1];
return y;
}
void circshift(unsigned int *msg, int msg_len, int shift)
{
int i;
unsigned int tmp;
if(shift > 0)
{
while(shift > 0)
{
tmp = msg[msg_len-1];
for(i=msg_len-1; i>0; i--)
{
msg[i] = msg[i-1];;
}
msg[0] = tmp;
shift--;
}
}
else
{
while(shift < 0)
{
tmp = msg[0];
for(i=0; i<msg_len-1; i++)
{
msg[i] = msg[i+1];
}
msg[msg_len-1] = tmp;
shift++;
}
}
}
unsigned int max(unsigned int a, unsigned int b)
{
if(a >= b)
return a;
else
return b;
}
unsigned int Galois_Rev(unsigned int a)
{
a = index_of[a-1];
a = (1<<RS_PARA_M) -1 - a;
if(a >= (1<<RS_PARA_M) - 1)
a = a - (1<<RS_PARA_M) +1;
return alpha_to[a];
}
int rs_dec(unsigned int *rx, unsigned int *msg)
{
int i, j, flag, j_D;
unsigned int rrx[RS_PARA_N];
unsigned int syndrom[RS_PARA_N - RS_PARA_K];
unsigned int syndrom_x[RS_PARA_N - RS_PARA_K + 1];
unsigned int lamada[RS_PARA_N - RS_PARA_K + 2][RS_PARA_N - RS_PARA_K + 1];
unsigned int lamada_x[RS_PARA_N - RS_PARA_K + 1];
unsigned int lamada_x_order;
unsigned int D[RS_PARA_N - RS_PARA_K + 2];
unsigned int d[RS_PARA_N - RS_PARA_K + 2];
unsigned int temp[RS_PARA_N - RS_PARA_K + 1];
unsigned int mul_temp, rev_flag;
unsigned int err_poly_root[(RS_PARA_N - RS_PARA_K)/2 + 1];
unsigned int err_site[(RS_PARA_N - RS_PARA_K)/2 + 1];
unsigned int err_poly_root_order;
unsigned int w[2*(RS_PARA_N - RS_PARA_K) + 1];
unsigned int omega[RS_PARA_N - RS_PARA_K];
unsigned int lamada_dx[RS_PARA_N - RS_PARA_K + 1];
unsigned int omega_final, lambda_final;
unsigned int err_value[(RS_PARA_N - RS_PARA_K)/2 + 1];
unsigned int tx[RS_PARA_N];
for(i=0; i<RS_PARA_N; i++)
rrx[i] = rx[RS_PARA_N-1-i];
for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
syndrom[i] = Galois_poly_val(rrx, RS_PARA_N, alpha_to[i+1]);
for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
{
if(syndrom[i] != 0)
{
i = -1;
break;
}
}
if(i>0)
{
for(i=0; i<RS_PARA_K; i++)
{
*msg++ = *rx++;
}
return 0;
}
syndrom_x[0] = 1;
for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
{
syndrom_x[i+1] = syndrom[i];
}
for(i=0; i<RS_PARA_N - RS_PARA_K + 2; i++)
for(j=0; j<RS_PARA_N - RS_PARA_K + 1; j++)
lamada[i][j] = 0;
lamada[0][0] = 1;
lamada[1][0] = 1;
for(i=0; i<RS_PARA_N - RS_PARA_K + 2; i++)
{
D[i] = 0;
d[i] = 0;
}
d[0] = 1;
d[1] = syndrom_x[1];
flag = -1;
j_D = -1;
for(j=0; j<RS_PARA_N - RS_PARA_K; j++)
{
if(d[j+1] == 0)
{
for(i=0; i<RS_PARA_N - RS_PARA_K + 1; i++)
{
lamada[j+2][i] = lamada[j+1][i];
D[j+2] = D[j+1];
}
}
else
{
for(i=0; i<RS_PARA_N - RS_PARA_K + 1; i++)
{
temp[i] = lamada[flag+1][i];
}
circshift(temp, RS_PARA_N - RS_PARA_K + 1, j-flag);
for(i=0; i<=RS_PARA_N - RS_PARA_K; i++)
{
rev_flag = Galois_Rev(d[flag+1]);
mul_temp = Galois_Mul(d[j+1], rev_flag);
lamada[j+2][i] = Galois_Add(lamada[j+1][i], Galois_Mul(mul_temp, temp[i]));
}
D[j+2] = max(D[j+1], j-flag+D[flag+1]);
if(j-(int)D[j+1] >= j_D)
{
j_D = j-(int)D[j+1];
flag = j;
}
}
if(j!=RS_PARA_N - RS_PARA_K-1)
{
d[j+2] = syndrom_x[j+2];
for(i=1; i<=D[j+2]; i++)
{
d[j+2] = Galois_Add(d[j+2], Galois_Mul(lamada[j+2][i], syndrom_x[j+2-i]));
}
}
}
lamada_x_order = D[RS_PARA_N - RS_PARA_K+1] + 1;
for(i=0; i<lamada_x_order; i++)
lamada_x[i] = lamada[RS_PARA_N - RS_PARA_K+1][i];
err_poly_root_order=0;
for(i=0; i<RS_PARA_N; i++)
{
mul_temp = Galois_Rev(alpha_to[i]);
rev_flag = Galois_poly_val(lamada_x, lamada_x_order, mul_temp);
if(rev_flag == 0)
{
err_poly_root[err_poly_root_order] = mul_temp;
err_site[err_poly_root_order] = i;
err_poly_root_order = err_poly_root_order+1;
}
}
for(i=0; i<=2*(RS_PARA_N - RS_PARA_K); i++)
w[i] = 0;
for(i=1; i<RS_PARA_N - RS_PARA_K + 1; i++)
for(j=0; j<lamada_x_order; j++)
w[i+j-1] = Galois_Add(w[i+j-1],Galois_Mul(syndrom_x[i], lamada_x[j]));
for(i=0; i<2*err_poly_root_order; i++)
omega[i] = w[i];
for(i=1; i<lamada_x_order; i++)
if(i&1 == 1)
lamada_dx[i-1] = lamada_x[i];
else
lamada_dx[i-1] = 0;
lamada_dx[i-1] = 0;
for(i=0; i<err_poly_root_order; i++)
{
omega_final = Galois_poly_val(omega, 2*err_poly_root_order, err_poly_root[i]);
lambda_final = Galois_poly_val(lamada_dx, lamada_x_order, err_poly_root[i]);
err_value[i] = Galois_Mul(omega_final, Galois_Rev(lambda_final));
}
for(i=0; i<RS_PARA_N; i++)
tx[i] = rrx[i];
for(i=0; i<err_poly_root_order; i++)
tx[err_site[i]] = Galois_Add(tx[err_site[i]], err_value[i]);
for(i=0; i<RS_PARA_K; i++)
msg[i] = tx[RS_PARA_N-i-1];
return 1;
}
void rs_test(void)
{
short i;
unsigned int tmsg[RS_PARA_K];
unsigned int tenc[RS_PARA_N];
unsigned int dmsg[RS_PARA_K];
unsigned int renc[RS_PARA_N];
for(i=0; i<RS_PARA_K; i++)
{
tmsg[i] = i;
}
rs_enc(tmsg, tenc);
for(i=0; i<RS_PARA_N; i++)
{
renc[i] = tenc[i];
}
renc[2] = 8;
renc[3] = 23;
renc[7] = 0;
rs_dec(renc, dmsg);
}
复制代码
作者:
51hei团团
时间:
2020-7-20 18:17
楼主你好 能分享一下头文件吗?
欢迎光临 (http://www.51hei.com/bbs/)
Powered by Discuz! X3.1