IT++ Logo

bch.cpp

Go to the documentation of this file.
00001 
00030 #include <itpp/comm/bch.h>
00031 #include <itpp/base/binary.h>
00032 #include <itpp/base/specmat.h>
00033 
00034 namespace itpp
00035 {
00036 
00037 //---------------------- BCH -----------------------------------
00038 
00039 BCH::BCH(int in_n, int in_k, int in_t, ivec genpolynom, bool sys) :
00040     n(in_n), k(in_k), t(in_t), systematic(sys)
00041 {
00042   //fix the generator polynomial g(x).
00043   ivec exponents(n - k + 1);
00044   bvec temp = oct2bin(genpolynom);
00045   for (int i = 0; i < temp.length(); i++) {
00046     exponents(i) = static_cast<int>(temp(temp.length() - i - 1)) - 1;
00047   }
00048   g.set(n + 1, exponents);
00049 }
00050 
00051 void BCH::encode(const bvec &uncoded_bits, bvec &coded_bits)
00052 {
00053   int i, j, degree,
00054   itterations = floor_i(static_cast<double>(uncoded_bits.length()) / k);
00055   GFX m(n + 1, k);
00056   GFX c(n + 1, n);
00057   GFX r(n + 1, n - k);
00058   GFX uncoded_shifted(n + 1, n);
00059   coded_bits.set_size(itterations*n, false);
00060   bvec mbit(k), cbit(n);
00061 
00062   if (systematic)
00063     for (i = 0; i < n - k; i++)
00064       uncoded_shifted[i] = GF(n + 1, -1);
00065 
00066   for (i = 0; i < itterations; i++) {
00067     //Fix the message polynom m(x).
00068     mbit = uncoded_bits.mid(i * k, k);
00069     for (j = 0; j < k; j++) {
00070       degree = static_cast<int>(mbit(j)) - 1;
00071       m[j] = GF(n + 1, degree);
00072       if (systematic) {
00073         c[j] = m[j];
00074         uncoded_shifted[j+n-k] = m[j];
00075       }
00076     }
00077     //Fix the outputbits cbit.
00078     if (systematic) {
00079       r = modgfx(uncoded_shifted, g);
00080       for (j = k; j < n; j++) {
00081         c[j] = r[j-k];
00082       }
00083     }
00084     else {
00085       c = g * m;
00086     }
00087     for (j = 0; j < n; j++) {
00088       if (c[j] == GF(n + 1, 0)) {
00089         cbit(j) = 1;
00090       }
00091       else {
00092         cbit(j) = 0;
00093       }
00094     }
00095     coded_bits.replace_mid(i*n, cbit);
00096   }
00097 }
00098 
00099 bvec BCH::encode(const bvec &uncoded_bits)
00100 {
00101   bvec coded_bits;
00102   encode(uncoded_bits, coded_bits);
00103   return coded_bits;
00104 }
00105 
00106 void BCH::decode(const bvec &coded_bits, bvec &decoded_bits)
00107 {
00108   int j, i, degree, kk, foundzeros, cisvalid,
00109   itterations = floor_i(static_cast<double>(coded_bits.length()) / n);
00110   bvec rbin(n), mbin(k);
00111   decoded_bits.set_size(itterations*k, false);
00112 
00113   GFX r(n + 1, n - 1), c(n + 1, n - 1), m(n + 1, k - 1), S(n + 1, 2*t), Lambda(n + 1),
00114   OldLambda(n + 1), T(n + 1), Ohmega(n + 1), One(n + 1, (char*)"0");
00115   GF delta(n + 1);
00116   ivec errorpos;
00117 
00118   for (i = 0; i < itterations; i++) {
00119     //Fix the received polynomial r(x)
00120     rbin = coded_bits.mid(i * n, n);
00121     for (j = 0; j < n; j++) {
00122       degree = static_cast<int>(rbin(j)) - 1;
00123       r[j] = GF(n + 1, degree);
00124     }
00125     //Fix the syndrome polynomial S(x).
00126     S[0] = GF(n + 1, -1);
00127     for (j = 1; j <= 2*t; j++) {
00128       S[j] =  r(GF(n + 1, j));
00129     }
00130     if (S.get_true_degree() >= 1) { //Errors in the received word
00131       //Itterate to find Lambda(x).
00132       kk = 0;
00133       Lambda = GFX(n + 1, (char*)"0");
00134       T = GFX(n + 1, (char*)"0");
00135       while (kk < t) {
00136         Ohmega = Lambda * (S + One);
00137         delta = Ohmega[2*kk+1];
00138         OldLambda = Lambda;
00139         Lambda = OldLambda + delta * (GFX(n + 1, (char*)"-1 0") * T);
00140         if ((delta == GF(n + 1, -1)) || (OldLambda.get_true_degree() > kk)) {
00141           T = GFX(n + 1, (char*)"-1 -1 0") * T;
00142         }
00143         else {
00144           T = (GFX(n + 1, (char*)"-1 0") * OldLambda) / delta;
00145         }
00146         kk = kk + 1;
00147       }
00148       //Find the zeros to Lambda(x).
00149       errorpos.set_size(Lambda.get_true_degree(), true);
00150       foundzeros = 0;
00151       for (j = 0; j <= n - 1; j++) {
00152         if (Lambda(GF(n + 1, j)) == GF(n + 1, -1)) {
00153           errorpos(foundzeros) = (n - j) % n;
00154           foundzeros += 1;
00155           if (foundzeros >= Lambda.get_true_degree()) {
00156             break;
00157           }
00158         }
00159       }
00160       //Correct the codeword.
00161       for (j = 0; j < foundzeros; j++) {
00162         rbin(errorpos(j)) += 1;
00163       }
00164       //Reconstruct the corrected codeword.
00165       for (j = 0; j < n; j++) {
00166         degree = static_cast<int>(rbin(j)) - 1;
00167         c[j] = GF(n + 1, degree);
00168       }
00169       //Code word validation.
00170       S[0] = GF(n + 1, -1);
00171       for (j = 1; j <= 2*t; j++) {
00172         S[j] =  c(GF(n + 1, j));
00173       }
00174       if (S.get_true_degree() <= 0) { //c(x) is a valid codeword.
00175         cisvalid = true;
00176       }
00177       else {
00178         cisvalid = false;
00179       }
00180     }
00181     else {
00182       c = r;
00183       cisvalid = true;
00184     }
00185     //Construct the message bit vector.
00186     if (cisvalid) { //c(x) is a valid codeword.
00187       if (c.get_true_degree() > 1) {
00188         if (systematic) {
00189           for (j = 0; j < k; j++)
00190             m[j] = c[j];
00191         }
00192         else {
00193           m = divgfx(c, g);
00194         }
00195         mbin.clear();
00196         for (j = 0; j <= m.get_true_degree(); j++) {
00197           if (m[j] == GF(n + 1, 0)) {
00198             mbin(j) = 1;
00199           }
00200         }
00201       }
00202       else { //The zero word was transmitted
00203         mbin = zeros_b(k);
00204         m = GFX(n + 1, (char*)"-1");
00205       }
00206     }
00207     else { //Decoder failure.
00208       mbin = zeros_b(k);
00209       m = GFX(n + 1, (char*)"-1");
00210     }
00211     decoded_bits.replace_mid(i*k, mbin);
00212   }
00213 }
00214 
00215 
00216 bvec BCH::decode(const bvec &coded_bits)
00217 {
00218   bvec decoded_bits;
00219   decode(coded_bits, decoded_bits);
00220   return decoded_bits;
00221 }
00222 
00223 
00224 // --- Soft-decision decoding is not implemented ---
00225 
00226 void BCH::decode(const vec &, bvec &)
00227 {
00228   it_error("BCH::decode(): Soft-decision decoding is not implemented");
00229 }
00230 
00231 bvec BCH::decode(const vec &)
00232 {
00233   it_error("BCH::decode(): Soft-decision decoding is not implemented");
00234   return bvec();
00235 }
00236 
00237 
00238 } // namespace itpp
SourceForge Logo

Generated on Thu Apr 23 20:04:04 2009 for IT++ by Doxygen 1.5.8