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 Sat Apr 19 11:01:25 2008 for IT++ by Doxygen 1.5.5