IT++ Logo Newcom Logo

bch.cpp

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

Generated on Thu Apr 19 14:18:30 2007 for IT++ by Doxygen 1.5.1