标题: 一种RS编码数据校验方法 源程序 [打印本页]
作者: yancey1989    时间: 2020-7-20 16:56
标题: 一种RS编码数据校验方法 源程序
数据收发可能会出现误码率，特别是在无线通信领域中， 通过增加数据长度， 可恢复误码数据。


  1. #include"reedsolomon.h"
  2. unsigned int poly_g[17] = {
  3.   79        ,  44        ,  81        , 100        ,  49        , 183        ,  56        ,  17        ,
  4. 232        , 187        , 126        , 104        ,  31        , 103        ,  52        , 118        ,
  5.    1        };
  6. unsigned int alpha_to[256] = {
  7.    1        ,   2        ,   4        ,   8        ,  16        ,  32        ,  64        , 128        ,
  8.   29        ,  58        , 116        , 232        , 205        , 135        ,  19        ,  38        ,
  9.   76        , 152        ,  45        ,  90        , 180        , 117        , 234        , 201        ,
  10. 143        ,   3        ,   6        ,  12        ,  24        ,  48        ,  96        , 192        ,
  11. 157        ,  39        ,  78        , 156        ,  37        ,  74        , 148        ,  53        ,
  12. 106        , 212        , 181        , 119        , 238        , 193        , 159        ,  35        ,
  13.   70        , 140        ,   5        ,  10        ,  20        ,  40        ,  80        , 160        ,
  14.   93        , 186        , 105        , 210        , 185        , 111        , 222        , 161        ,
  15.   95        , 190        ,  97        , 194        , 153        ,  47        ,  94        , 188        ,
  16. 101        , 202        , 137        ,  15        ,  30        ,  60        , 120        , 240        ,
  17. 253        , 231        , 211        , 187        , 107        , 214        , 177        , 127        ,
  18. 254        , 225        , 223        , 163        ,  91        , 182        , 113        , 226        ,
  19. 217        , 175        ,  67        , 134        ,  17        ,  34        ,  68        , 136        ,
  20.   13        ,  26        ,  52        , 104        , 208        , 189        , 103        , 206        ,
  21. 129        ,  31        ,  62        , 124        , 248        , 237        , 199        , 147        ,
  22.   59        , 118        , 236        , 197        , 151        ,  51        , 102        , 204        ,
  23. 133        ,  23        ,  46        ,  92        , 184        , 109        , 218        , 169        ,
  24.   79        , 158        ,  33        ,  66        , 132        ,  21        ,  42        ,  84        ,
  25. 168        ,  77        , 154        ,  41        ,  82        , 164        ,  85        , 170        ,
  26.   73        , 146        ,  57        , 114        , 228        , 213        , 183        , 115        ,
  27. 230        , 209        , 191        ,  99        , 198        , 145        ,  63        , 126        ,
  28. 252        , 229        , 215        , 179        , 123        , 246        , 241        , 255        ,
  29. 227        , 219        , 171        ,  75        , 150        ,  49        ,  98        , 196        ,
  30. 149        ,  55        , 110        , 220        , 165        ,  87        , 174        ,  65        ,
  31. 130        ,  25        ,  50        , 100        , 200        , 141        ,   7        ,  14        ,
  32.   28        ,  56        , 112        , 224        , 221        , 167        ,  83        , 166        ,
  33.   81        , 162        ,  89        , 178        , 121        , 242        , 249        , 239        ,
  34. 195        , 155        ,  43        ,  86        , 172        ,  69        , 138        ,   9        ,
  35.   18        ,  36        ,  72        , 144        ,  61        , 122        , 244        , 245        ,
  36. 247        , 243        , 251        , 235        , 203        , 139        ,  11        ,  22        ,
  37.   44        ,  88        , 176        , 125        , 250        , 233        , 207        , 131        ,
  38.   27        ,  54        , 108        , 216        , 173        ,  71        , 142        ,   0        
  39. };
  40. unsigned int index_of[256] = {
  41.    0        ,   1        ,  25        ,   2        ,  50        ,  26        , 198        ,   3        ,
  42. 223        ,  51        , 238        ,  27        , 104        , 199        ,  75        ,   4        ,
  43. 100        , 224        ,  14        ,  52        , 141        , 239        , 129        ,  28        ,
  44. 193        , 105        , 248        , 200        ,   8        ,  76        , 113        ,   5        ,
  45. 138        , 101        ,  47        , 225        ,  36        ,  15        ,  33        ,  53        ,
  46. 147        , 142        , 218        , 240        ,  18        , 130        ,  69        ,  29        ,
  47. 181        , 194        , 125        , 106        ,  39        , 249        , 185        , 201        ,
  48. 154        ,   9        , 120        ,  77        , 228        , 114        , 166        ,   6        ,
  49. 191        , 139        ,  98        , 102        , 221        ,  48        , 253        , 226        ,
  50. 152        ,  37        , 179        ,  16        , 145        ,  34        , 136        ,  54        ,
  51. 208        , 148        , 206        , 143        , 150        , 219        , 189        , 241        ,
  52. 210        ,  19        ,  92        , 131        ,  56        ,  70        ,  64        ,  30        ,
  53.   66        , 182        , 163        , 195        ,  72        , 126        , 110        , 107        ,
  54.   58        ,  40        ,  84        , 250        , 133        , 186        ,  61        , 202        ,
  55.   94        , 155        , 159        ,  10        ,  21        , 121        ,  43        ,  78        ,
  56. 212        , 229        , 172        , 115        , 243        , 167        ,  87        ,   7        ,
  57. 112        , 192        , 247        , 140        , 128        ,  99        ,  13        , 103        ,
  58.   74        , 222        , 237        ,  49        , 197        , 254        ,  24        , 227        ,
  59. 165        , 153        , 119        ,  38        , 184        , 180        , 124        ,  17        ,
  60.   68        , 146        , 217        ,  35        ,  32        , 137        ,  46        ,  55        ,
  61.   63        , 209        ,  91        , 149        , 188        , 207        , 205        , 144        ,
  62. 135        , 151        , 178        , 220        , 252        , 190        ,  97        , 242        ,
  63.   86        , 211        , 171        ,  20        ,  42        ,  93        , 158        , 132        ,
  64.   60        ,  57        ,  83        ,  71        , 109        ,  65        , 162        ,  31        ,
  65.   45        ,  67        , 216        , 183        , 123        , 164        , 118        , 196        ,
  66.   23        ,  73        , 236        , 127        ,  12        , 111        , 246        , 108        ,
  67. 161        ,  59        ,  82        ,  41        , 157        ,  85        , 170        , 251        ,
  68.   96        , 134        , 177        , 187        , 204        ,  62        ,  90        , 203        ,
  69.   89        ,  95        , 176        , 156        , 169        , 160        ,  81        ,  11        ,
  70. 245        ,  22        , 235        , 122        , 117        ,  44        , 215        ,  79        ,
  71. 174        , 213        , 233        , 230        , 231        , 173        , 232        , 116        ,
  72. 214        , 244        , 234        , 168        ,  80        ,  88        , 175        ,   0        
  73. };
  74. unsigned int Galois_Mul(unsigned int a, unsigned int b)
  75. {
  76.         unsigned int a1;
  77.         unsigned int b1;
  78.         if(a*b==0)
  79.                 return 0;
  80.         a1 = index_of[a-1];
  81.         b1 = index_of[b-1];
  82.         a1 = a1 + b1;
  83.         if(a1 >= (1<<RS_PARA_M) - 1)
  84.                 a1 = a1 - (1<<RS_PARA_M) + 1;
  85.         return alpha_to[a1];
  86. }
  87. unsigned int Galois_Add(unsigned int a, unsigned int b)
  88. {
  89.         int i;
  90.         unsigned int a1, b1, c;
  91.         c = 0;
  92.         for(i=0; i<RS_PARA_M; i++)
  93.         {
  94.                 a1 = a & (1<<i);
  95.                 b1 = b & (1<<i);
  96.                 c = c | a1^b1;
  97.         }
  98.         return c;
  99. }
  100. void rs_enc(unsigned int *msg, unsigned int *tx)
  101. {
  102.         int i,j;
  103.         unsigned int feedback;
  104.         unsigned int rr[RS_PARA_N - RS_PARA_K];
  105.         for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
  106.                 rr[i] = 0;
  107.         for(i=0; i<RS_PARA_K; i++)
  108.                 tx[i] = *msg++;
  109.         for(i=RS_PARA_K; i<RS_PARA_N; i++)
  110.                 tx[i] = 0;
  111.         for(i=0; i<RS_PARA_N; i++)
  112.         {
  113.                 feedback = rr[RS_PARA_N - RS_PARA_K - 1];
  114.                 for(j = RS_PARA_N - RS_PARA_K - 1; j>0; j--)
  115.                 {
  116.                         if(poly_g[j] != 0)
  117.                                 rr[j] = Galois_Add(rr[j-1], Galois_Mul(poly_g[j], feedback));
  118.                         else
  119.                                 rr[j] = rr[j-1];
  120.                 }
  121.                 rr[0] = Galois_Add(tx[i], Galois_Mul(poly_g[0], feedback));
  122.         }
  123.         for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
  124.                 tx[i+RS_PARA_K] = rr[RS_PARA_N - RS_PARA_K - i - 1];
  125. }
  126. unsigned int Galois_poly_val(unsigned int *poly_coef, unsigned int poly_order, unsigned int val)
  127. {
  128.         int i;
  129.         unsigned int x, y, tmp;
  130.         x = index_of[val - 1];
  131.         y = poly_coef[0];
  132.         for(i=0; i<poly_order-1; i++)
  133.         {
  134.                 tmp = (i+1)*x;
  135.                 while(tmp >= ((1<<RS_PARA_M) - 1))
  136.                         tmp = tmp - (1<<RS_PARA_M) + 1;
  137.                 tmp = alpha_to[tmp];
  138.                 tmp = Galois_Mul(poly_coef[i+1], tmp);
  139.                 y = Galois_Add(y, tmp);
  140.         }
  141.         return y;
  142. }
  143. unsigned int Galois_Reverse(unsigned int a)
  144. {
  145.         unsigned y;
  146.         y = index_of[a-1];
  147.         y = (1<<RS_PARA_M) - 1 - y;
  148.         y = alpha_to[y-1];
  149.         return y;
  150. }
  151. void circshift(unsigned int *msg, int msg_len, int shift)
  152. {
  153.         int i;
  154.         unsigned int tmp;
  155.         if(shift > 0)
  156.         {
  157.                 while(shift > 0)
  158.                 {
  159.                         tmp = msg[msg_len-1];
  160.                         for(i=msg_len-1; i>0; i--)
  161.                         {
  162.                                 msg[i] = msg[i-1];;
  163.                         }
  164.                         msg[0] = tmp;
  165.                         shift--;
  166.                 }
  167.         }
  168.         else
  169.         {
  170.                 while(shift < 0)
  171.                 {
  172.                         tmp = msg[0];
  173.                         for(i=0; i<msg_len-1; i++)
  174.                         {
  175.                                 msg[i] = msg[i+1];
  176.                         }
  177.                         msg[msg_len-1] = tmp;
  178.                         shift++;
  179.                 }
  180.         }
  181. }
  182. unsigned int max(unsigned int a, unsigned int b)
  183. {
  184.         if(a >= b)
  185.                 return a;
  186.         else
  187.                 return b;
  188. }
  189. unsigned int Galois_Rev(unsigned int a)
  190. {
  191.         a = index_of[a-1];
  192.         a = (1<<RS_PARA_M) -1 - a;
  193.         if(a >= (1<<RS_PARA_M) - 1)
  194.                 a = a - (1<<RS_PARA_M) +1;
  195.         return alpha_to[a];
  196. }
  197. int rs_dec(unsigned int *rx, unsigned int *msg)
  198. {
  199.         int i, j, flag, j_D;
  200.         unsigned int rrx[RS_PARA_N];
  201.         unsigned int syndrom[RS_PARA_N - RS_PARA_K];
  202.         unsigned int syndrom_x[RS_PARA_N - RS_PARA_K + 1];
  203.         unsigned int lamada[RS_PARA_N - RS_PARA_K + 2][RS_PARA_N - RS_PARA_K + 1];
  204.         unsigned int lamada_x[RS_PARA_N - RS_PARA_K + 1];
  205.         unsigned int lamada_x_order;
  206.         unsigned int D[RS_PARA_N - RS_PARA_K + 2];
  207.         unsigned int d[RS_PARA_N - RS_PARA_K + 2];
  208.         unsigned int temp[RS_PARA_N - RS_PARA_K + 1];
  209.         unsigned int mul_temp, rev_flag;
  210.         unsigned int err_poly_root[(RS_PARA_N - RS_PARA_K)/2 + 1];
  211.         unsigned int err_site[(RS_PARA_N - RS_PARA_K)/2 + 1];
  212.         unsigned int err_poly_root_order;
  213.         unsigned int w[2*(RS_PARA_N - RS_PARA_K) + 1];
  214.         unsigned int omega[RS_PARA_N - RS_PARA_K];
  215.         unsigned int lamada_dx[RS_PARA_N - RS_PARA_K + 1];
  216.         unsigned int omega_final, lambda_final;
  217.         unsigned int err_value[(RS_PARA_N - RS_PARA_K)/2 + 1];
  218.         unsigned int tx[RS_PARA_N];
  219.         for(i=0; i<RS_PARA_N; i++)
  220.                 rrx[i] = rx[RS_PARA_N-1-i];
  221.         for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
  222.                 syndrom[i] = Galois_poly_val(rrx, RS_PARA_N, alpha_to[i+1]);
  223.         for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
  224.         {
  225.                 if(syndrom[i] != 0)
  226.                 {
  227.                         i = -1;
  228.                         break;
  229.                 }
  230.         }
  231.         if(i>0)
  232.         {
  233.                 for(i=0; i<RS_PARA_K; i++)
  234.                 {
  235.                         *msg++ = *rx++;
  236.                 }
  237.                 return 0;
  238.         }
  239.         syndrom_x[0] = 1;
  240.         for(i=0; i<RS_PARA_N - RS_PARA_K; i++)
  241.         {
  242.                 syndrom_x[i+1] = syndrom[i];
  243.         }
  244.         for(i=0; i<RS_PARA_N - RS_PARA_K + 2; i++)
  245.                 for(j=0; j<RS_PARA_N - RS_PARA_K + 1; j++)
  246.                         lamada[i][j] = 0;
  247.         lamada[0][0] = 1;
  248.         lamada[1][0] = 1;
  249.         for(i=0; i<RS_PARA_N - RS_PARA_K + 2; i++)
  250.         {
  251.                 D[i] = 0;
  252.                 d[i] = 0;
  253.         }
  254.         d[0] = 1;
  255.         d[1] = syndrom_x[1];
  256.         flag = -1;
  257.         j_D = -1;
  258.         for(j=0; j<RS_PARA_N - RS_PARA_K; j++)
  259.         {
  260.                 if(d[j+1] == 0)
  261.                 {
  262.                         for(i=0; i<RS_PARA_N - RS_PARA_K + 1; i++)
  263.                         {
  264.                                 lamada[j+2][i] = lamada[j+1][i];
  265.                                 D[j+2] = D[j+1];
  266.                         }
  267.                 }
  268.                 else
  269.                 {
  270.                         for(i=0; i<RS_PARA_N - RS_PARA_K + 1; i++)
  271.                         {
  272.                                 temp[i] = lamada[flag+1][i];
  273.                         }
  274.                         circshift(temp, RS_PARA_N - RS_PARA_K + 1, j-flag);
  275.                         for(i=0; i<=RS_PARA_N - RS_PARA_K; i++)
  276.                         {
  277.                                 rev_flag = Galois_Rev(d[flag+1]);
  278.                                 mul_temp = Galois_Mul(d[j+1], rev_flag);
  279.                                 lamada[j+2][i] = Galois_Add(lamada[j+1][i], Galois_Mul(mul_temp, temp[i]));
  280.                         }
  281.                         D[j+2] = max(D[j+1], j-flag+D[flag+1]);
  282.                         if(j-(int)D[j+1] >= j_D)
  283.                         {
  284.                                 j_D = j-(int)D[j+1];
  285.                                 flag = j;
  286.                         }
  287.                 }
  288.                 if(j!=RS_PARA_N - RS_PARA_K-1)
  289.                 {
  290.                         d[j+2] = syndrom_x[j+2];
  291.                         for(i=1; i<=D[j+2]; i++)
  292.                         {
  293.                                 d[j+2] = Galois_Add(d[j+2], Galois_Mul(lamada[j+2][i], syndrom_x[j+2-i]));
  294.                         }
  295.                 }
  296.         }
  297.         lamada_x_order = D[RS_PARA_N - RS_PARA_K+1] + 1;
  298.         for(i=0; i<lamada_x_order; i++)
  299.                 lamada_x[i] = lamada[RS_PARA_N - RS_PARA_K+1][i];
  300.         err_poly_root_order=0;
  301.         for(i=0; i<RS_PARA_N; i++)
  302.         {
  303.                 mul_temp = Galois_Rev(alpha_to[i]);
  304.                 rev_flag =  Galois_poly_val(lamada_x, lamada_x_order, mul_temp);
  305.                 if(rev_flag == 0)
  306.                 {
  307.                         err_poly_root[err_poly_root_order] = mul_temp;
  308.                         err_site[err_poly_root_order] = i;
  309.                         err_poly_root_order = err_poly_root_order+1;
  310.                 }
  311.         }
  312.         for(i=0; i<=2*(RS_PARA_N - RS_PARA_K); i++)
  313.                 w[i] = 0;
  314.         for(i=1; i<RS_PARA_N - RS_PARA_K + 1; i++)
  315.                 for(j=0; j<lamada_x_order; j++)
  316.                         w[i+j-1] = Galois_Add(w[i+j-1],Galois_Mul(syndrom_x[i], lamada_x[j]));
  317.         for(i=0; i<2*err_poly_root_order; i++)
  318.                 omega[i] = w[i];
  319.         for(i=1; i<lamada_x_order; i++)
  320.                 if(i&1 == 1)
  321.                         lamada_dx[i-1] = lamada_x[i];
  322.                 else
  323.                         lamada_dx[i-1] = 0;
  324.         lamada_dx[i-1] = 0;
  325.         for(i=0; i<err_poly_root_order; i++)
  326.         {
  327.                 omega_final = Galois_poly_val(omega, 2*err_poly_root_order, err_poly_root[i]);
  328.                 lambda_final = Galois_poly_val(lamada_dx, lamada_x_order, err_poly_root[i]);
  329.                 err_value[i] = Galois_Mul(omega_final, Galois_Rev(lambda_final));
  330.         }
  331.         for(i=0; i<RS_PARA_N; i++)
  332.                 tx[i] = rrx[i];
  333.         for(i=0; i<err_poly_root_order; i++)
  334.                 tx[err_site[i]] = Galois_Add(tx[err_site[i]], err_value[i]);
  335.         for(i=0; i<RS_PARA_K; i++)
  336.                 msg[i] = tx[RS_PARA_N-i-1];
  337.         return 1;
  338. }


  341. void rs_test(void)
  342. {
  343.         short i;
  344.         unsigned int tmsg[RS_PARA_K];               
  345.         unsigned int tenc[RS_PARA_N];               
  346.         
  347.         unsigned int dmsg[RS_PARA_K];
  348.         unsigned int renc[RS_PARA_N];               

  350.         for(i=0; i<RS_PARA_K; i++)
  351.         {
  352.                 tmsg[i] = i;
  353.         }
  354.         rs_enc(tmsg, tenc);











  366.         for(i=0; i<RS_PARA_N; i++)
  367.         {
  368.                 renc[i] = tenc[i];
  369.         }
  370.         renc[2] = 8;
  371.         renc[3] = 23;
  372.         renc[7] = 0;

  374.         rs_dec(renc, dmsg);

  376. }
复制代码


作者: 51hei团团    时间: 2020-7-20 18:17
楼主你好 能分享一下头文件吗?



欢迎光临 (http://www.51hei.com/bbs/) Powered by Discuz! X3.1