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
Generated on Thu Apr 24 13:38:59 2008 for IT++ by Doxygen 1.5.5