IT++ Logo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
reedsolomon.cpp
Go to the documentation of this file.
1 
29 #include <itpp/comm/reedsolomon.h>
30 #include <itpp/base/math/log_exp.h>
31 
32 namespace itpp
33 {
34 
35 //-------------------- Help Function ----------------------------
36 
39 {
40  int degree = f.get_true_degree();
41  int q = f.get_size();
42  int i;
43  GFX fprim(q, degree);
44  fprim.clear();
45  for (i = 0; i <= degree - 1; i += 2) {
46  fprim[i] = f[i+1];
47  }
48  return fprim;
49 }
50 
51 //-------------------- Reed-Solomon ----------------------------
52 //A Reed-Solomon code is a q^m-ary BCH code of length n = pow(q,m)-1.
53 //k = pow(q,m)-1-t. This class works for q==2.
54 Reed_Solomon::Reed_Solomon(int in_m, int in_t, bool sys):
55  m(in_m), t(in_t), systematic(sys)
56 {
57  n = pow2i(m) - 1;
58  k = pow2i(m) - 1 - 2 * t;
59  q = pow2i(m);
60  GFX x(q, (char *)"-1 0");
61  ivec alphapow(1);
62  g.set(q, (char *)"0");
63  for (int i = 1; i <= 2*t; i++) {
64  alphapow(0) = i;
65  g *= (x - GFX(q, alphapow));
66  }
67 }
68 
69 void Reed_Solomon::encode(const bvec &uncoded_bits, bvec &coded_bits)
70 {
71  int i, j, itterations = floor_i(static_cast<double>(uncoded_bits.length())
72  / (k * m));
73  GFX mx(q, k), cx(q, n);
74  GFX r(n + 1, n - k);
75  GFX uncoded_shifted(n + 1, n);
76  GF mpow;
77  bvec mbit(k*m), cbit(m);
78 
79  coded_bits.set_size(itterations*n*m, false);
80 
81  if (systematic)
82  for (i = 0; i < n - k; i++)
83  uncoded_shifted[i] = GF(n + 1, -1);
84 
85  for (i = 0; i < itterations; i++) {
86  //Fix the message polynom m(x).
87  for (j = 0; j < k; j++) {
88  mpow.set(q, uncoded_bits.mid((i*m*k) + (j*m), m));
89  mx[j] = mpow;
90  if (systematic) {
91  cx[j] = mx[j];
92  uncoded_shifted[j+n-k] = mx[j];
93  }
94  }
95  //Fix the outputbits cbit.
96  if (systematic) {
97  r = modgfx(uncoded_shifted, g);
98  for (j = k; j < n; j++) {
99  cx[j] = r[j-k];
100  }
101  }
102  else {
103  cx = g * mx;
104  }
105  for (j = 0; j < n; j++) {
106  cbit = cx[j].get_vectorspace();
107  coded_bits.replace_mid((i*n*m) + (j*m), cbit);
108  }
109  }
110 }
111 
112 bvec Reed_Solomon::encode(const bvec &uncoded_bits)
113 {
114  bvec coded_bits;
115  encode(uncoded_bits, coded_bits);
116  return coded_bits;
117 }
118 
119 void Reed_Solomon::decode(const bvec &coded_bits, bvec &decoded_bits)
120 {
121  int j, i, kk, l, L, foundzeros, decoderfailure,
122  itterations = floor_i(static_cast<double>(coded_bits.length()) / (n * m));
123  bvec mbit(m*k);
124  decoded_bits.set_size(itterations*k*m, false);
125 
126  GFX rx(q, n - 1), cx(q, n - 1), mx(q, k - 1), ex(q, n - 1), S(q, 2*t), Lambda(q),
127  Lambdaprim(q), OldLambda(q), T(q), Ohmega(q);
128  GFX dummy(q), One(q, (char*)"0"), Ohmegatemp(q);
129  GF delta(q), tempsum(q), rtemp(q), temp(q), Xk(q), Xkinv(q);
130  ivec errorpos;
131 
132  for (i = 0; i < itterations; i++) {
133  decoderfailure = false;
134  //Fix the received polynomial r(x)
135  for (j = 0; j < n; j++) {
136  rtemp.set(q, coded_bits.mid(i*n*m + j*m, m));
137  rx[j] = rtemp;
138  }
139  //Fix the syndrome polynomial S(x).
140  S.clear();
141  for (j = 1; j <= 2*t; j++) {
142  S[j] = rx(GF(q, j));
143  }
144  if (S.get_true_degree() == 0) {
145  cx = rx;
146  decoderfailure = false;
147  }
148  else {//Errors in the received word
149  //Itterate to find Lambda(x).
150  kk = 0;
151  Lambda = GFX(q, (char*)"0");
152  L = 0;
153  T = GFX(q, (char*)"-1 0");
154  while (kk < 2*t) {
155  kk = kk + 1;
156  tempsum = GF(q, -1);
157  for (l = 1; l <= L; l++) {
158  tempsum += Lambda[l] * S[kk-l];
159  }
160  delta = S[kk] - tempsum;
161  if (delta != GF(q, -1)) {
162  OldLambda = Lambda;
163  Lambda -= delta * T;
164  if (2*L < kk) {
165  L = kk - L;
166  T = OldLambda / delta;
167  }
168  }
169  T = GFX(q, (char*)"-1 0") * T;
170  }
171  //Find the zeros to Lambda(x).
172  errorpos.set_size(Lambda.get_true_degree(), false);
173  errorpos.clear();
174  foundzeros = 0;
175  for (j = q - 2; j >= 0; j--) {
176  temp = Lambda(GF(q, j));
177  if (Lambda(GF(q, j)) == GF(q, -1)) {
178  errorpos(foundzeros) = (n - j) % n;
179  foundzeros += 1;
180  if (foundzeros >= Lambda.get_true_degree()) {
181  break;
182  }
183  }
184  }
185  if (foundzeros != Lambda.get_true_degree()) {
186  decoderfailure = false;
187  }
188  else {
189  //Compute Ohmega(x) using the key equation for RS-decoding
190  Ohmega.set_degree(2*t);
191  Ohmegatemp = Lambda * (One + S);
192  for (j = 0; j <= 2*t; j++) {
193  Ohmega[j] = Ohmegatemp[j];
194  }
195  Lambdaprim = formal_derivate(Lambda);
196  //Find the error polynomial
197  ex.clear();
198  for (j = 0; j < foundzeros; j++) {
199  Xk = GF(q, errorpos(j));
200  Xkinv = GF(q, 0) / Xk;
201  ex[errorpos(j)] = (Xk * Ohmega(Xkinv)) / Lambdaprim(Xkinv);
202  }
203  //Reconstruct the corrected codeword.
204  cx = rx + ex;
205  //Code word validation
206  S.clear();
207  for (j = 1; j <= 2*t; j++) {
208  S[j] = rx(GF(q, j));
209  }
210  if (S.get_true_degree() >= 1) {
211  decoderfailure = false;
212  }
213  }
214  }
215  //Find the message polynomial
216  mbit.clear();
217  if (decoderfailure == false) {
218  if (cx.get_true_degree() >= 1) {// A nonzero codeword was transmitted
219  if (systematic) {
220  for (j = 0; j < k; j++) {
221  mx[j] = cx[j];
222  }
223  }
224  else {
225  mx = divgfx(cx, g);
226  }
227  for (j = 0; j <= mx.get_true_degree(); j++) {
228  mbit.replace_mid(j*m, mx[j].get_vectorspace());
229  }
230  }
231  }
232  decoded_bits.replace_mid(i*m*k, mbit);
233  }
234 }
235 
236 bvec Reed_Solomon::decode(const bvec &coded_bits)
237 {
238  bvec decoded_bits;
239  decode(coded_bits, decoded_bits);
240  return decoded_bits;
241 }
242 
243 // --- Soft-decision decoding is not implemented ---
244 
245 void Reed_Solomon::decode(const vec &, bvec &)
246 {
247  it_error("Reed_Solomon::decode(): Soft-decision decoding not implemented");
248 }
249 
250 bvec Reed_Solomon::decode(const vec &)
251 {
252  it_error("Reed_Solomon::decode(): Soft-decision decoding not implemented");
253  return bvec();
254 }
255 
256 } // namespace itpp
SourceForge Logo

Generated on Fri Mar 21 2014 17:14:13 for IT++ by Doxygen 1.8.1.2