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