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

Generated on Sun Sep 14 18:52:27 2008 for IT++ by Doxygen 1.5.6