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
Generated on Thu Apr 19 14:43:44 2007 for IT++ by Doxygen 1.5.1