56 const std::string& format): init_flag(false)
58 if (format ==
"alist") {
62 it_error(
"LDPC_Parity::LDPC_Parity(): Only 'alist' format is supported");
87 "LDPC_Parity::set(): Wrong index i");
89 "LDPC_Parity::set(): Wrong index j");
92 int diff =
static_cast<int>(x) - static_cast<int>(
H(i, j));
112 "LDPC_Parity::display_stats(): Object not initialized");
115 vec vdeg =
zeros(cmax + 1);
116 vec cdeg =
zeros(vmax + 1);
117 for (
int col = 0; col <
nvar; col++) {
120 "LDPC_Parity::display_stats(): Internal error");
122 for (
int row = 0; row <
ncheck; row++) {
125 "LDPC_Parity::display_stats(): Internal error");
140 it_info(
"--- LDPC parity check matrix ---");
142 it_info(
"Variable node degree distribution from node perspective:\n" 144 it_info(
"Check node degree distribution from node perspective:\n" 146 it_info(
"Variable node degree distribution from edge perspective:\n" 147 << vdegedge / edges);
148 it_info(
"Check node degree distribution from edge perspective:\n" 149 << cdegedge / edges);
151 it_info(
"--------------------------------");
163 alist.
write(alist_file);
173 for (
int i = 0; i <
ncheck; i++) {
174 for (
int j = 0; j <
nvar; j++) {
185 "LDPC_Parity::export_alist(): Object not initialized");
193 int to_j,
int godir,
int L)
const 196 "LDPC_Parity::check_connectivity(): Object not initialized");
204 if ((from_i == to_i) && (from_j == to_j) && (godir != 0)) {
208 if (
get(from_i, from_j) == 0) {
214 if (
get(from_i, to_j) == 1) {
return 0; }
217 if (
get(to_i, from_j) == 1) {
return 0; }
222 if ((godir == 1) || (godir == 0)) {
224 for (i = 0; i <
length(cj); i++) {
225 if (cj(i) != from_i) {
236 for (j = 0; j <
length(ri); j++) {
237 if (ri(j) != from_j) {
252 "LDPC_Parity::check_for_cycles(): Object not initialized");
254 if ((L&1) == 1) {
return (-1); }
255 if (L == 0) {
return (-4); }
258 for (
int i = 0; i <
nvar; i++) {
260 for (
int j = 0; j <
length(ri); j++) {
295 "LDPC_Parity::cycle_removal_MGW(): Object not initialized");
303 for (
int j = 0; j <
nvar; j++) {
305 for (
int i = 0; i < col.
nnz(); i++) {
317 Gpow(0).set(i, i, 1);
326 int cycles_found = 0;
328 for (r = 4; r <= Maxcyc; r += 2) {
330 Gpow(r / 2) = Gpow(r / 2 - 1) * G;
333 traverse_again =
false;
335 it_info_debug(
"Starting new pass of cycle elimination, target girth " 336 << (r + 2) <<
"...");
342 if (ptemp > pdone + 10) {
347 if (((Gpow(r / 2))(i, j) >= 2) && ((Gpow(r / 2 - 2))(i, j) == 0)) {
353 G.get_col(j))).get_nz_indices();
357 "LDPC_Parity_Unstructured::cycle_removal_MGW(): " 361 Ssvec rowjk = Gpow(r / 2) * (Gpow(r / 2 - 1).get_col(j)
362 + Gpow(r / 2 - 1).get_col(k));
368 if (rowjk(l) != 0) {
continue; }
369 ivec colcandi = G.get_col(l).get_nz_indices();
370 if (
length(colcandi) > 0) {
372 for (
int u = 0; u <
length(colcandi); u++) {
376 goto found_candidate_vector;
384 found_candidate_vector:
387 if (p >=
ncheck) {
int z = l; l = p; p = z; }
388 if (j >=
ncheck) {
int z = k; k = j; j = z; }
398 "LDPC_Parity_Unstructured::cycle_removal_MGW(): " 403 "LDPC_Parity_Unstructured::cycle_removal_MGW(): " 410 && G(k, j) == 1,
"G");
412 && G(k, p) == 0,
"G");
428 && G(k, j) == 0,
"G");
430 && G(k, p) == 1,
"G");
434 for (
int z = 3; z <= r / 2; z++) {
435 Gpow(z) = Gpow(z - 1) * G;
438 traverse_again =
true;
442 if ((!traverse_again) && (cycles_found > 0)) {
447 while (cycles_found != 0);
450 <<
". Proceeding to next level.");
455 it_info_debug(
"Cycle removal (MGW algoritm) finished. Graph girth: " 456 << girth <<
". Cycles remaining on next girth level: " 475 for (
int i = 0;i < C.length();i++) {
476 for (
int j = 0; j < C(i); j++) {
477 for (
int m = 0; m < i; m++) Ne++;
488 for (
int i = 0;i < C.length();i++) {
489 for (
int j = 0; j < C(i); j++) {
490 for (
int m = 0; m < i; m++) {
500 for (
int i = 0;i < R.length();i++) {
501 for (
int j = 0; j < R(i); j++) {
502 for (
int m = 0; m < i; m++) {
513 ivec ind = sort_index(
randu(Ne));
519 for (
int i = 0; i <
length(cycopt); i++) {
520 Laim(i + 2) = cycopt(i);
522 for (
int i =
length(cycopt); i <
Nmax - 2; i++) {
523 Laim(i + 2) = cycopt(
length(cycopt) - 1);
528 const int Max_attempts = 100;
530 for (
int k = 0; k < Ne; k++) {
531 const int el = Ne - k - 2;
534 <<
". Variable node degree: " << vd(vcon(k))
535 <<
". Girth target: " << Laim(vd(vcon(k)))
536 <<
". Accumulated failures: " << failures);
538 const int c = cp(vcon(k));
539 int L = Laim(vd(vcon(k)));
542 if (attempt > 0 && attempt % apcl == 0 && L >= 6) { L -= 2; };
543 int r = rp(ccon(ind(k)));
548 int t = k + 1 +
randi(0, el - 1);
553 if (attempt == Max_attempts) {
570 int t = k + 1 +
randi(0, el - 1);
575 if (attempt == Max_attempts) {
617 if (
sum(C) != Nvar) {
619 C(ind(0)) = C(ind(0)) - (
sum(C) - Nvar);
631 R.set(ind(0), old - 1);
633 R.set(ind(0) - 1, old + 1);
637 if (ind(0) == R.length() - 1) {
642 R.set(ind(0), old - 1);
644 R.set(ind(0) + 1, old + 1);
661 const std::string& method,
664 generate(Nvar, k, l, method, options);
668 const std::string& method,
671 vec var_deg =
zeros(k);
672 vec chk_deg =
zeros(l);
681 if (method ==
"rand") {
697 const std::string& method,
700 generate(Nvar, var_deg, chk_deg, method, options);
705 const std::string& method,
711 if (method ==
"rand") {
741 for (
int r = 0; r < H_b.rows(); r++) {
742 for (
int c = 0; c < H_b.cols(); c++) {
749 for (
int i = 0; i < Z; ++i)
750 set(rz + i, cz + i, 1);
753 for (
int i = 0; i < Z; ++i)
754 set(rz + i, cz + (i + H_b(r, c)) % Z, 1);
779 calculate_base_matrix();
786 std::ifstream bm_file(filename.c_str());
787 it_assert(bm_file.is_open(),
"BLDPC_Parity::load_base_matrix(): Could not " 788 "open file \"" << filename <<
"\" for reading");
793 int line_counter = 0;
794 getline(bm_file, line);
795 while (!bm_file.eof()) {
797 std::stringstream ss(line);
804 if ((H_b.rows() == 0) || (row.size() == H_b.cols()))
807 it_warning(
"BLDPC_Parity::load_base_matrix(): Wrong size of " 808 "a parsed row number " << line_counter);
809 getline(bm_file, line);
814 if (H_b.rows() > H_b.cols())
815 H_b = H_b.transpose();
823 it_assert(H_b_valid,
"BLDPC_Parity::save_base_matrix(): Base matrix is " 825 std::ofstream bm_file(filename.c_str());
826 it_assert(bm_file.is_open(),
"BLDPC_Parity::save_base_matrix(): Could not " 827 "open file \"" << filename <<
"\" for writing");
829 for (
int r = 0; r < H_b.rows(); r++) {
830 for (
int c = 0; c < H_b.cols(); c++) {
831 bm_file << std::setw(3) << H_b(r, c);
840 void BLDPC_Parity::calculate_base_matrix()
842 std::string error_str =
"BLDPC_Parity::calculate_base_matrix(): " 843 "Invalid BLDPC matrix. Cannot calculate base matrix from it.";
844 int rows =
H.
rows() / Z;
845 int cols =
H.
cols() / Z;
847 H_b.set_size(rows, cols);
849 for (
int r = 0; r < rows; ++r) {
851 for (
int c = 0; c < cols; ++c) {
855 if (H_Z.
nnz() == 0) {
858 else if (H_Z.
nnz() == Z) {
861 while ((shift < Z) && (H_Z(0, shift) != 1))
864 for (
int i = 1; i < Z; ++i)
865 it_assert(H_Z(0, shift) == H_Z(i, (i + shift) % Z), error_str);
874 it_info(
"Base matrix calculated");
885 bool natural_ordering,
890 tmp =
construct(H, natural_ordering, ind);
895 bool natural_ordering,
896 const ivec& avoid_cols)
905 ivec col_order(nvar);
906 if (natural_ordering) {
907 for (
int i = 0; i < nvar; i++) {
913 vec col_importance =
randu(nvar);
914 for (
int i = 0; i <
length(avoid_cols); i++) {
915 col_importance(avoid_cols(i)) = (-col_importance(avoid_cols(i)));
917 col_order = sort_index(-col_importance);
920 ivec actual_ordering(nvar);
933 for (
int k = 0; k < nvar; k++) {
934 it_error_if(j1 >= nvar - ncheck,
"LDPC_Generator_Systematic::construct(): " 935 "Unable to obtain enough independent columns.");
937 bvec c = Hd.get_col(col_order(k));
941 actual_ordering(k) = nvar - ncheck;
948 actual_ordering(k) = nvar - ncheck + j2;
955 actual_ordering(k) = j1;
959 actual_ordering(k) = j1;
974 for (
int i = 0; i < ncheck; i++) {
975 for (
int j = 0; j < nvar; j++) {
985 "LDPC_Generator_Systematic::construct(): Incorrect generator matrix G");
992 return actual_ordering;
1000 f >>
Name(
"Fileversion") >> ver;
1002 "LDPC_Generator_Systematic::save(): Unsupported file format");
1004 f <<
Name(
"G") << G;
1013 f >>
Name(
"Fileversion") >> ver;
1015 "LDPC_Generator_Systematic::load(): Unsupported file format");
1016 std::string gen_type;
1017 f >>
Name(
"G_type") >> gen_type;
1019 "LDPC_Generator_Systematic::load(): Wrong generator type");
1020 f >>
Name(
"G") >> G;
1030 "generator not set up");
1031 it_assert(input.size() == G.
cols(),
"LDPC_Generator_Systematic::encode(): " 1032 "Improper input vector size (" << input.size() <<
" != " 1033 << G.
cols() <<
")");
1035 output =
concat(input, G * input);
1044 const std::string type):
1054 "initialized generator");
1055 it_assert(input.size() ==
K,
"BLDPC_Generator::encode(): Input vector " 1056 "length is not equal to K");
1060 output.set_size(
N,
true);
1063 for (
int k = 0; k <
Z; k++) {
1064 for (
int j = 0; j <
K; j++) {
1065 output(
K + k) +=
H_enc(
M - 1 - k, j) * input(j);
1067 for (
int j = 0; j < k; j++) {
1068 output(
K + k) +=
H_enc(
M - 1 - k,
K + j) * output(
K + j);
1073 for (
int k = 0; k <
M -
Z; k++) {
1074 for (
int j = 0; j <
K; j++) {
1075 output(
K +
Z + k) +=
H_enc(k, j) * input(j);
1077 for (
int j =
K; j <
K +
Z; j++) {
1078 output(
K +
Z + k) +=
H_enc(k, j) * output(j);
1080 for (
int j =
K +
Z; j <
K +
Z + k; j++) {
1081 output(
K +
Z + k) +=
H_enc(k, j) * output(j);
1100 for (
int i = 0; i <
M -
Z; i +=
Z) {
1102 for (
int j = 0; j <
Z; j++) {
1114 for (
int c1 =
K +
Z - 1; c1 >=
K; c1--) {
1117 while (
H_enc(r2, c1) == 0 && r2 <
M - 1)
1124 for (r2 = r1 + 1; r2 <
M; r2++) {
1125 if (
H_enc(r2, c1) == 1) {
1143 "BLDPC_Generator::save(): Can not save not initialized generator");
1146 for (
int i = 0; i <
M /
Z - 1; i++) {
1154 f >>
Name(
"Fileversion") >> ver;
1156 "Unsupported file format");
1158 f <<
Name(
"H_T") << H_T;
1159 f <<
Name(
"H_Z") << H_Z;
1160 f <<
Name(
"Z") <<
Z;
1170 f >>
Name(
"Fileversion") >> ver;
1172 "Unsupported file format");
1173 std::string gen_type;
1174 f >>
Name(
"G_type") >> gen_type;
1176 "BLDPC_Generator::load(): Wrong generator type");
1177 f >>
Name(
"H_T") >> H_T;
1178 f >>
Name(
"H_Z") >> H_Z;
1179 f >>
Name(
"Z") >>
Z;
1183 M = (H_T.rows() + 1) *
Z;
1187 for (
int i = 0; i < H_T.rows(); i++) {
1188 for (
int j = 0; j <
Z; j++) {
1189 for (
int k = 0; k <
N; k++) {
1190 if (H_T(i, (k /
Z)*
Z + (k +
Z - j) %
Z)) {
1207 max_iters(50), psc(true), pisc(false),
1212 bool perform_integrity_check):
1213 H_defined(false), G_defined(false), dec_method(new
std::string), max_iters(50),
1217 set_code(H, G_in, perform_integrity_check);
1222 H_defined(false), G_defined(false), dec_method(new
std::string), max_iters(50),
1232 bool perform_integrity_check)
1239 if (perform_integrity_check) {
1242 it_info_debug(
"LDPC_Code::set_code(): integrity check was not performed");
1250 it_info_debug(
"LDPC_Code::load_code(): Loading LDPC codec from " 1255 f >>
Name(
"Fileversion") >> ver;
1257 "Unsupported file format");
1258 f >>
Name(
"H_defined") >> H_defined;
1259 f >>
Name(
"G_defined") >> G_defined;
1260 f >>
Name(
"nvar") >> nvar;
1261 f >>
Name(
"ncheck") >> ncheck;
1262 f >>
Name(
"C") >> C;
1263 f >>
Name(
"V") >> V;
1264 f >>
Name(
"sumX1") >> sumX1;
1265 f >>
Name(
"sumX2") >> sumX2;
1266 f >>
Name(
"iind") >> iind;
1267 f >>
Name(
"jind") >> jind;
1272 it_assert(G_in != 0,
"LDPC_Code::load_code(): Generator object is " 1273 "missing. Can not load the generator data from a file.");
1279 it_info_debug(
"LDPC_Code::load_code(): Generator data not loaded. " 1280 "Generator object will not be used.");
1283 it_info_debug(
"LDPC_Code::load_code(): Successfully loaded LDPC codec " 1284 "from " << filename);
1291 it_assert(H_defined,
"LDPC_Code::save_to_file(): There is no parity " 1293 it_info_debug(
"LDPC_Code::save_to_file(): Saving LDPC codec to " 1297 f.
open(filename,
true);
1299 f <<
Name(
"H_defined") << H_defined;
1300 f <<
Name(
"G_defined") << G_defined;
1301 f <<
Name(
"nvar") << nvar;
1302 f <<
Name(
"ncheck") << ncheck;
1303 f <<
Name(
"C") << C;
1304 f <<
Name(
"V") << V;
1305 f <<
Name(
"sumX1") << sumX1;
1306 f <<
Name(
"sumX2") << sumX2;
1307 f <<
Name(
"iind") << iind;
1308 f <<
Name(
"jind") << jind;
1315 it_info_debug(
"LDPC_Code::save_code(): Missing generator object - " 1316 "generator data not saved");
1318 it_info_debug(
"LDPC_Code::save_code(): Successfully saved LDPC codec to " 1325 it_assert((method_in ==
"bp") || (method_in ==
"BP"),
1326 "LDPC_Code::set_decoding_method(): Not implemented decoding method");
1327 *dec_method = method_in;
1331 bool syndr_check_each_iter,
1332 bool syndr_check_at_start)
1334 it_assert(max_iters >= 0,
"LDPC_Code::set_nrof_iterations(): Maximum " 1335 "number of iterations can not be negative");
1336 max_iters = max_iters_in;
1337 psc = syndr_check_each_iter;
1338 pisc = syndr_check_at_start;
1343 llrcalc = llrcalc_in;
1349 it_assert(G_defined,
"LDPC_Code::encode(): LDPC Generator is required " 1351 G->
encode(input, output);
1365 QLLRvec qllrin = llrcalc.
to_qllr(llr_in);
1368 syst_bits = (qllrout.left(nvar - ncheck) < 0);
1374 decode(llr_in, syst_bits);
1380 QLLRvec qllrin = llrcalc.
to_qllr(llr_in);
1397 it_assert(H_defined,
"LDPC_Code::bp_decode(): Parity check matrix not " 1399 it_assert((LLRin.size() == nvar) && (sumX1.size() == nvar)
1400 && (sumX2.size() == ncheck),
"LDPC_Code::bp_decode(): Wrong " 1401 "input dimensions");
1408 LLRout.set_size(LLRin.size());
1413 QLLRvec ml(max_cnd);
1414 QLLRvec mr(max_cnd);
1417 for (
int i = 0; i < nvar; i++) {
1419 for (
int j = 0; j < sumX1(i); j++) {
1420 mvc[index] = LLRin(i);
1425 bool is_valid_codeword =
false;
1431 for (
int j = 0; j < ncheck; j++) {
1436 it_error(
"LDPC_Code::bp_decode(): sumX2(j)=0");
1438 it_error(
"LDPC_Code::bp_decode(): sumX2(j)=1");
1440 mcv[j+ncheck] = mvc[jind[j]];
1441 mcv[j] = mvc[jind[j+ncheck]];
1446 QLLR m0 = mvc[jind[j0]];
1447 int j1 = j0 + ncheck;
1448 QLLR m1 = mvc[jind[j1]];
1449 int j2 = j1 + ncheck;
1450 QLLR m2 = mvc[jind[j2]];
1451 mcv[j0] = llrcalc.
Boxplus(m1, m2);
1452 mcv[j1] = llrcalc.
Boxplus(m0, m2);
1453 mcv[j2] = llrcalc.
Boxplus(m0, m1);
1458 QLLR m0 = mvc[jind[j0]];
1459 int j1 = j0 + ncheck;
1460 QLLR m1 = mvc[jind[j1]];
1461 int j2 = j1 + ncheck;
1462 QLLR m2 = mvc[jind[j2]];
1463 int j3 = j2 + ncheck;
1464 QLLR m3 = mvc[jind[j3]];
1465 QLLR m01 = llrcalc.
Boxplus(m0, m1);
1466 QLLR m23 = llrcalc.
Boxplus(m2, m3);
1467 mcv[j0] = llrcalc.
Boxplus(m1, m23);
1468 mcv[j1] = llrcalc.
Boxplus(m0, m23);
1469 mcv[j2] = llrcalc.
Boxplus(m01, m3);
1470 mcv[j3] = llrcalc.
Boxplus(m01, m2);
1475 QLLR m0 = mvc[jind[j0]];
1476 int j1 = j0 + ncheck;
1477 QLLR m1 = mvc[jind[j1]];
1478 int j2 = j1 + ncheck;
1479 QLLR m2 = mvc[jind[j2]];
1480 int j3 = j2 + ncheck;
1481 QLLR m3 = mvc[jind[j3]];
1482 int j4 = j3 + ncheck;
1483 QLLR m4 = mvc[jind[j4]];
1484 QLLR m01 = llrcalc.
Boxplus(m0, m1);
1485 QLLR m02 = llrcalc.
Boxplus(m01, m2);
1486 QLLR m34 = llrcalc.
Boxplus(m3, m4);
1487 QLLR m24 = llrcalc.
Boxplus(m2, m34);
1488 mcv[j0] = llrcalc.
Boxplus(m1, m24);
1489 mcv[j1] = llrcalc.
Boxplus(m0, m24);
1490 mcv[j2] = llrcalc.
Boxplus(m01, m34);
1491 mcv[j3] = llrcalc.
Boxplus(m02, m4);
1492 mcv[j4] = llrcalc.
Boxplus(m02, m3);
1497 QLLR m0 = mvc[jind[j0]];
1498 int j1 = j0 + ncheck;
1499 QLLR m1 = mvc[jind[j1]];
1500 int j2 = j1 + ncheck;
1501 QLLR m2 = mvc[jind[j2]];
1502 int j3 = j2 + ncheck;
1503 QLLR m3 = mvc[jind[j3]];
1504 int j4 = j3 + ncheck;
1505 QLLR m4 = mvc[jind[j4]];
1506 int j5 = j4 + ncheck;
1507 QLLR m5 = mvc[jind[j5]];
1508 QLLR m01 = llrcalc.
Boxplus(m0, m1);
1509 QLLR m23 = llrcalc.
Boxplus(m2, m3);
1510 QLLR m45 = llrcalc.
Boxplus(m4, m5);
1511 QLLR m03 = llrcalc.
Boxplus(m01, m23);
1512 QLLR m25 = llrcalc.
Boxplus(m23, m45);
1513 QLLR m0145 = llrcalc.
Boxplus(m01, m45);
1514 mcv[j0] = llrcalc.
Boxplus(m1, m25);
1515 mcv[j1] = llrcalc.
Boxplus(m0, m25);
1516 mcv[j2] = llrcalc.
Boxplus(m0145, m3);
1517 mcv[j3] = llrcalc.
Boxplus(m0145, m2);
1518 mcv[j4] = llrcalc.
Boxplus(m03, m5);
1519 mcv[j5] = llrcalc.
Boxplus(m03, m4);
1523 int nodes = sumX2(j);
1524 if( nodes > max_cnd ) {
1525 std::ostringstream m_sout;
1526 m_sout <<
"check node degrees >" << max_cnd <<
" not supported in this version";
1532 m[0] = mvc[jind[jj[0]]];
1533 for(
int i = 1; i <= nodes; i++ ) {
1534 jj[i] = jj[i-1] + ncheck;
1535 m[i] = mvc[jind[jj[i]]];
1541 for(
int i = 1; i < nodes; i++ ) {
1542 ml[i] = llrcalc.
Boxplus( ml[i-1], m[i] );
1543 mr[i] = llrcalc.
Boxplus( mr[i-1], m[nodes-i] );
1547 mcv[jj[0]] = mr[nodes-1];
1548 mcv[jj[nodes]] = ml[nodes-1];
1549 for(
int i = 1; i < nodes; i++ )
1550 mcv[jj[i]] = llrcalc.
Boxplus( ml[i-1], mr[nodes-1-i] );
1556 for (
int i = 0; i < nvar; i++) {
1559 it_error(
"LDPC_Code::bp_decode(): sumX1(i)=0");
1564 QLLR m0 = mcv[iind[i]];
1566 LLRout(i) = LLRin(i) + m0;
1570 QLLR m0 = mcv[iind[i]];
1572 QLLR m1 = mcv[iind[i1]];
1573 mvc[i] = LLRin(i) + m1;
1574 mvc[i1] = LLRin(i) + m0;
1575 LLRout(i) = mvc[i1] + m1;
1580 QLLR m0 = mcv[iind[i0]];
1582 QLLR m1 = mcv[iind[i1]];
1584 QLLR m2 = mcv[iind[i2]];
1585 LLRout(i) = LLRin(i) + m0 + m1 + m2;
1586 mvc[i0] = LLRout(i) - m0;
1587 mvc[i1] = LLRout(i) - m1;
1588 mvc[i2] = LLRout(i) - m2;
1593 QLLR m0 = mcv[iind[i0]];
1595 QLLR m1 = mcv[iind[i1]];
1597 QLLR m2 = mcv[iind[i2]];
1599 QLLR m3 = mcv[iind[i3]];
1600 LLRout(i) = LLRin(i) + m0 + m1 + m2 + m3;
1601 mvc[i0] = LLRout(i) - m0;
1602 mvc[i1] = LLRout(i) - m1;
1603 mvc[i2] = LLRout(i) - m2;
1604 mvc[i3] = LLRout(i) - m3;
1608 QLLR mvc_temp = LLRin(i);
1610 for (
int jp = 0; jp < sumX1(i); jp++) {
1611 mvc_temp += mcv[iind[index_iind]];
1614 LLRout(i) = mvc_temp;
1616 for (
int j = 0; j < sumX1[i]; j++) {
1617 mvc[index_iind] = mvc_temp - mcv[iind[index_iind]];
1625 is_valid_codeword =
true;
1629 while (iter < max_iters);
1632 return (is_valid_codeword ? iter : -iter);
1638 QLLRvec llr = 1 - 2 *
to_ivec(x);
1648 for (j = 0; j < ncheck; j++) {
1651 for (i = 0; i < sumX2(j); i++) {
1658 if ((synd&1) == 1) {
1667 QLLRvec result(ncheck);
1670 for (j=0; j<ncheck; j++) {
1671 result(j)=-QLLR_MAX;
1673 for (i=0; i<sumX2(j); i++) {
1675 result(j) = llrcalc.
Boxplus(LLR(vi),result(j));
1690 sumX1 = Hmat->
sumX1;
1691 sumX2 = Hmat->
sumX2;
1694 int cmax =
max(sumX1);
1695 int vmax =
max(sumX2);
1700 jind =
zeros_i(ncheck * vmax);
1703 it_info_debug(
"LDPC_Code::decoder_parameterization(): Computations " 1705 for (
int i = 0; i < nvar; i++) {
1707 for (
int j0 = 0; j0 <
length(coli); j0++) {
1708 C(j0 + cmax*i) = coli(j0);
1712 it_info_debug(
"LDPC_Code::decoder_parameterization(): Computations " 1714 it_info_debug(
"Computing decoder parameterization. Phase 2");
1715 for (
int j = 0; j < ncheck; j++) {
1717 for (
int i0 = 0; i0 <
length(rowj); i0++) {
1718 V(j + ncheck*i0) = rowj(i0);
1722 it_info_debug(
"LDPC_Code::decoder_parameterization(): Computations " 1724 it_info_debug(
"Computing decoder parameterization. Phase 3.");
1725 for (
int j = 0; j < ncheck; j++) {
1726 for (
int ip = 0; ip < sumX2(j); ip++) {
1727 int vip = V(j + ip * ncheck);
1730 if (C(k + vip*cmax) == j) {
1735 jind(j + ip*ncheck) = vip + k * nvar;
1739 it_info_debug(
"LDPC_Code::decoder_parameterization(): Computations " 1741 for (
int i = 0; i < nvar; i++) {
1742 for (
int jp = 0; jp < sumX1(i); jp++) {
1743 int cjp = C(jp + i * cmax);
1746 if (V(cjp + k*ncheck) == i) {
break; }
1749 iind(i + jp*nvar) = cjp + k * ncheck;
1760 mcv.set_size(
max(sumX2) * ncheck);
1761 mvc.set_size(
max(sumX1) * nvar);
1769 it_info_debug(
"LDPC_Code::integrity_check(): Checking integrity of " 1770 "the LDPC_Parity and LDPC_Generator data");
1771 bvec bv(nvar - ncheck), cw;
1774 for (
int i = 0; i < nvar - ncheck; i++) {
1777 "LDPC_Code::integrity_check(): Syndrome check failed");
1778 bv.shift_right(bv(nvar - ncheck - 1));
1782 it_info_debug(
"LDPC_Code::integrity_check(): No generator defined " 1783 "- no check performed");
1794 for (
int i = 0; i < C.ncheck; i++) {
1799 for (
int j = 0; j < C.nvar; j++) {
1803 os <<
"--- LDPC codec ----------------------------------\n" 1804 <<
"Nvar : " << C.get_nvar() <<
"\n" 1805 <<
"Ncheck : " << C.get_ncheck() <<
"\n" 1806 <<
"Rate : " << C.get_rate() <<
"\n" 1807 <<
"Column degrees (node perspective): " << cdeg <<
"\n" 1808 <<
"Row degrees (node perspective): " << rdeg <<
"\n" 1809 <<
"-------------------------------------------------\n" 1810 <<
"Decoder parameters:\n" 1811 <<
" - method : " << C.get_decoding_method() <<
"\n" 1812 <<
" - max. iterations : " << C.max_iters <<
"\n" 1813 <<
" - syndrome check at each iteration : " << C.psc <<
"\n" 1814 <<
" - syndrome check at start : " << C.pisc <<
"\n" 1815 <<
"-------------------------------------------------\n" 1816 << C.llrcalc <<
"\n";
Mat< Num_T > elem_div(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Element wise division of two matrices.
#define it_error_if(t, s)
Abort if t is true.
int cycle_removal_MGW(int L)
Remove cycles (loops) from unstructured parity check matrix.
GF2mat_sparse Ht
The transposed parity check matrix.
imat get_base_matrix() const
Get base matrix.
ivec sumX2
Actual number of ones in each row.
int nvar
Number of variable nodes.
GF2mat H_enc
Preprocessed parity check matrix.
void write(const std::string &fname) const
Write alist data to a file named fname.
ITPP_EXPORT int round_i(double x)
Round to nearest integer.
bool init_flag
Flag that indicates proper initialization.
QLLR Boxplus(QLLR a, QLLR b) const
Hagenauer's "Boxplus" operator.
void open(const std::string &filename, bool trunc=false)
Open a file for reading and writing.
ITPP_EXPORT ivec zeros_i(int size)
A Int vector of zeros.
double randu(void)
Generates a random uniform (0,1) number.
Block LDPC code parity-check matrix.
int randi(int low, int high)
Generates a random integer in the interval [low,high].
int T_fact(GF2mat &T, GF2mat &U, ivec &P) const
TXP factorization.
void save(const std::string &filename) const
Save generator data to a file.
void expand_base(const imat &base_matrix, int exp_factor)
Create BLDPC matrix from base matrix by expansion.
void save_code(const std::string &filename) const
Save the codec to a file.
void set(int i, int j, bin s)
Set element i,j to s (0 or 1)
void set_decoding_method(const std::string &method)
Set the decoding method.
GF2mat inverse() const
Inversion.
LDPC_Parity_Regular()
Default constructor.
ivec find(const bvec &invector)
Return a integer vector with indicies where bvec == 1.
static const int LDPC_binary_file_version
Version of the binary file with generator and decoder data.
BLDPC_Parity()
Default constructor.
Class for dense GF(2) matrices.
int rows() const
Get number of rows.
void import_alist(const GF2mat_sparse_alist &H_alist)
Import matrix from GF2mat_sparse_alist format.
Mat< Num_T > elem_mult(const Mat< Num_T > &m1, const Mat< Num_T > &m2)
Element wise multiplication of two matrices.
bin get(int i, int j) const
Getting element.
int get_exp_factor() const
Get expansion factor.
std::ostream & operator<<(std::ostream &output, const bin &inbin)
Output stream of bin.
int ncheck
Number of check nodes.
int K
Number of information bits = N-M.
void from_sparse(const GF2mat_sparse &mat, bool transpose=false)
Import "alist" representation from GF2mat_sparse.
void construct(const BLDPC_Parity *const H)
Construct the BLDPC generator.
void load_alist(const std::string &alist_file)
Load matrix from alist_file text file in alist format.
void set(int r, int c, T v)
Set element (r, c ) equal to v.
QLLR to_qllr(double l) const
Convert a "real" LLR value to an LLR type.
Automatic naming when savingAn easy way to give a variable a name and optionally description when sav...
GF2mat concatenate_vertical(const GF2mat &X) const
Concatenate vertically (append X underneath)
T sum(const Vec< T > &v)
Sum of all elements in the vector.
#define it_info(s)
Print information message.
void set_code(const LDPC_Parity *const H, LDPC_Generator *const G=0, bool perform_integrity_check=true)
Set the codec, from a parity check matrix and optionally a generator.
GF2mat gf2dense_eye(int m)
GF(2) Identity matrix.
std::string get_type() const
Return generator type.
#define it_assert(t, s)
Abort if t is not true.
int length(const Vec< T > &v)
Length of vector.
#define it_info_no_endl_debug(s)
Print information message withot std::endl at the end if NDEBUG is not defined.
void decode_soft_out(const vec &llr_in, vec &llr_out)
This function is a wrapper for bp_decode()
GF2mat_sparse H
The parity check matrix.
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
double to_double(QLLR l) const
Convert an LLR type to a "real" LLR.
BLDPC_Generator(const std::string type="BLDPC")
Default constructor.
bool T_fact_update_addcol(GF2mat &T, GF2mat &U, ivec &P, bvec newcol) const
TXP factorization update, when column is added.
void set_size(int n, bool copy=false)
Resizing an Array<T>.
LDPC Generator pure virtual base class.
Templated sparse vector class.
ivec construct(LDPC_Parity *const H, bool natural_ordering=false, const ivec &ind="")
Construct systematic generator matrix.
ITPP_EXPORT double round(double x)
Round to nearest integer, return result in double.
ITPP_EXPORT vec zeros(int size)
A Double vector of zeros.
void close()
Close the file.
Sparse_Vec< bin > get_col(int c) const
Get a specific column from the matrix.
GF2mat get_submatrix(int m1, int n1, int m2, int n2) const
Submatrix from (m1,n1) to (m2,n2)
GF2mat_sparse get_H(bool transpose=false) const
Get the parity check matrix, optionally its transposed form.
void integrity_check()
Function to check the integrity of the parity check matrix and generator.
#define it_info_debug(s)
Print information message if NDEBUG is not defined.
int get_nz_index(int p)
Returns the vector index of the p-th non-zero element.
void set_exp_factor(int exp_factor)
Set expansion factor.
int cols() const
Get number of columns.
int get_ncheck() const
Get the number of check nodes (number of rows)
bool is_initialized() const
Check if generator is initialized.
virtual void save(const std::string &filename) const =0
Save generator data to a file.
T max(const Vec< T > &v)
Maximum value of vector.
void swap_rows(int i, int j)
Swap rows i and j.
The IT++ file format reading and writing class.
void load(const std::string &filename)
Read generator data from a file.
void generate(int Nvar, const vec &var_deg, const vec &chk_deg, const std::string &method="rand", const ivec &options="200 6")
Generate an irregular LDPC code.
vec to_vec(const Vec< T > &v)
Converts a Vec<T> to vec.
virtual void decode(const bvec &, bvec &)
Inherited from the base class - not implemented here.
Low-density parity check (LDPC) codec.
void load_code(const std::string &filename, LDPC_Generator *const G=0)
Set the codec, by reading from a saved file.
void set_llrcalc(const LLR_calc_unit &llrcalc)
Set LLR calculation unit.
The IT++ file format reading class.
bool syndrome_check(const QLLRvec &LLR) const
Syndrome check, on QLLR vector.
int M
Number of parity check bits = H_enc.rows()
void set_row(int i, bvec x)
Set row i to a binary vector x.
int floor_i(double x)
The nearest smaller integer.
QLLRvec soft_syndrome_check(const QLLRvec &LLR) const
Soft syndrome check.
virtual void load(const std::string &filename)
Read generator data from a file.
void load_base_matrix(const std::string &filename)
Load base matrix from a text file.
int get_nvar() const
Get the number of variable nodes (number of columns)
int nnz()
Number of non-zero elements in the sparse vector.
int nnz()
The number of non-zero elements in the sparse matrix.
ivec to_ivec(const Vec< T > &v)
Converts a Vec<T> to ivec.
int check_for_cycles(int L) const
Check for cycles of length L.
int N
Codeword length = H_enc.cols()
Sparse_Mat< bin > GF2mat_sparse
Sparse GF(2) matrix.
void add_rows(int i, int j)
Add (or equivalently, subtract) rows.
void generate_random_H(const ivec &C, const ivec &R, const ivec &cycopt)
Generate a random parity check matrix.
#define it_warning(s)
Display a warning message.
void save_base_matrix(const std::string &filename) const
Save base matrix to a text file.
void set_exit_conditions(int max_iters, bool syndr_check_each_iter=true, bool syndr_check_at_start=false)
Set the decoding loop exit conditions.
void encode(const bvec &input, bvec &output)
Generator specific encode function.
vec linspace(double from, double to, int points)
linspace (works in the same way as the MATLAB version)
Log-likelihood algebra calculation unit.
void decoder_parameterization(const LDPC_Parity *const H)
Function to compute decoder parameterization.
LDPC parity check matrix generic class.
Sparse_Mat< T > get_submatrix(int r1, int r2, int c1, int c2) const
Returns the sub-matrix from rows r1 to r2 and columns c1 to c2.
Binary arithmetic (boolean) class.
#define it_error(s)
Abort unconditionally.
void transpose(const Mat< T > &m, Mat< T > &out)
Transposition of the matrix m returning the transposed matrix in out.
virtual void encode(const bvec &input, bvec &output)
Generator specific encode function.
GF2mat transpose() const
Transpose.
virtual void display_stats() const
Display some information about the matrix.
GF2mat_sparse_alist export_alist() const
Export matrix to GF2mat_sparse_alist format.
int rows() const
Returns the number of rows of the sparse matrix.
Sparse_Vec< bin > get_row(int r) const
Get a specific row from the matrix.
int check_connectivity(int from_m, int from_n, int to_m, int to_n, int g, int L) const
Check for connectivity between nodes.
void initialize(int ncheck, int nvar)
Initialize an empty matrix of size ncheck x nvar.
bool is_valid() const
Verify initialisation.
GF2mat concatenate_horizontal(const GF2mat &X) const
Concatenate horizontally (append X on the right side of matrix)
void generate(int Nvar, int k, int l, const std::string &method="rand", const ivec &options="200 6")
Generate a (k,l) regular LDPC code.
virtual void load(const std::string &filename)=0
Read generator data from a file.
LDPC_Generator_Systematic()
Default constructor.
int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout)
Belief propagation decoding.
void set(int i, int j, bin value)
Set element (i,j) of the parity check matrix to value.
ivec get_nz_indices()
Return the indices of non-zero values.
void mark_initialized()
Mark generator as initialized.
LDPC_Code()
Default constructor.
void compute_CR(const vec &var_deg, const vec &chk_deg, const int Nvar, ivec &C, ivec &R)
Compute target number of columns (C) and rows (R) with a specific number of ones. ...
Parameterized "alist" representation of sparse GF(2) matrix.
virtual void encode(const bvec &input, bvec &output)=0
Generator specific encode function.
LDPC_Parity_Irregular()
Default constructor.
void setup_decoder()
Initialize decoder.
void clear_elem(const int r, const int c)
Clear the element in row r and column c (if it contains a non-zero value)
static const int Nmax
Maximum node degree class can handle.
double get_rate() const
Get the code rate.
GF2mat_sparse to_sparse(bool transpose=false) const
Convert "alist" representation to GF2mat_sparse.
LDPC_Parity()
Default constructor.
bvec get_row(int i) const
Get row.
virtual void save(const std::string &filename) const
Save generator data to a file.
Implementation of Low-Density Parity Check (LDPC) codes.
virtual void close()
Close the file.
void save_alist(const std::string &alist_file) const
Save matrix to alist_file text file in alist format.
virtual void encode(const bvec &input, bvec &output)
Encode codeword.
ivec sumX1
Actual number of ones in each column.
int cols() const
Returns the number of columns of the sparse matrix.
const Array< T > concat(const Array< T > &a, const T &e)
Append element e to the end of the Array a.