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 ---");
141 it_info(
"Dimension [ncheck x nvar]: " << ncheck <<
" x " << nvar);
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));
366 for (
int s = 0; s < nvar +
ncheck; s++) {
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; }
397 it_assert_debug((
get(j, k - ncheck) == 1) && (
get(p, l - ncheck) == 1),
398 "LDPC_Parity_Unstructured::cycle_removal_MGW(): " 402 it_assert_debug((
get(j, l - ncheck) == 0) && (
get(p, k - ncheck) == 0),
403 "LDPC_Parity_Unstructured::cycle_removal_MGW(): " 410 && G(k, j) == 1,
"G");
412 && G(k, p) == 0,
"G");
415 Ssmat Delta(ncheck + nvar, ncheck + nvar, 2);
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);
677 compute_CR(var_deg, chk_deg, Nvar, C, R);
681 if (method ==
"rand") {
682 generate_random_H(C, R, options);
697 const std::string& method,
700 generate(Nvar, var_deg, chk_deg, method, options);
705 const std::string& method,
709 compute_CR(var_deg, chk_deg, Nvar, C, R);
711 if (method ==
"rand") {
712 generate_random_H(C, R, options);
725 expand_base(base_matrix, exp_factor);
730 load_base_matrix(filename);
731 expand_base(H_b, exp_factor);
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);
776 expand_base(H_b, exp_factor);
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;
1001 it_assert(ver == LDPC_binary_file_version,
1002 "LDPC_Generator_Systematic::save(): Unsupported file format");
1004 f <<
Name(
"G") << G;
1013 f >>
Name(
"Fileversion") >> ver;
1014 it_assert(ver == LDPC_binary_file_version,
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;
1155 it_assert(ver == LDPC_binary_file_version,
"BLDPC_Generator::save(): " 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;
1171 it_assert(ver == LDPC_binary_file_version,
"BLDPC_Generator::load(): " 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;
1256 it_assert(ver == LDPC_binary_file_version,
"LDPC_Code::load_code(): " 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" 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" 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.
ivec sumX2
Actual number of ones in each row.
int nvar
Number of variable nodes.
void save_code(const std::string &filename) const
Save the codec to a file.
GF2mat H_enc
Preprocessed parity check matrix.
ITPP_EXPORT int round_i(double x)
Round to nearest integer.
bool init_flag
Flag that indicates proper initialization.
void open(const std::string &filename, bool trunc=false)
Open a file for reading and writing.
GF2mat transpose() const
Transpose.
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].
void write(const std::string &fname) const
Write alist data to a file named fname.
bvec get_row(int i) const
Get row.
void expand_base(const imat &base_matrix, int exp_factor)
Create BLDPC matrix from base matrix by expansion.
imat get_base_matrix() const
Get base matrix.
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 concatenate_horizontal(const GF2mat &X) const
Concatenate horizontally (append X on the right side of matrix)
virtual void save(const std::string &filename) const
Save generator data to a file.
LDPC_Parity_Regular()
Default constructor.
int get_ncheck() const
Get the number of check nodes.
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.
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.
Class for dense GF(2) matrices.
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.
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.
GF2mat_sparse to_sparse(bool transpose=false) const
Convert "alist" representation to GF2mat_sparse.
void construct(const BLDPC_Parity *const H)
Construct the BLDPC generator.
GF2mat inverse() const
Inversion.
void load_alist(const std::string &alist_file)
Load matrix from alist_file text file in alist format.
GF2mat concatenate_vertical(const GF2mat &X) const
Concatenate vertically (append X underneath)
int T_fact(GF2mat &T, GF2mat &U, ivec &P) const
TXP factorization.
void set(int r, int c, T v)
Set element (r, c ) equal to v.
Automatic naming when savingAn easy way to give a variable a name and optionally description when sav...
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_sparse get_H(bool transpose=false) const
Get the parity check matrix, optionally its transposed form.
GF2mat gf2dense_eye(int m)
GF(2) Identity matrix.
double to_double(QLLR l) const
Convert an LLR type to a "real" LLR.
std::string get_type() const
Return generator type.
void save(const std::string &filename) const
Save generator data to a file.
#define it_assert(t, s)
Abort if t is not true.
int length(const Vec< T > &v)
Length of vector.
int check_for_cycles(int L) const
Check for cycles of length L.
#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.
int cols() const
Get number of columns.
BLDPC_Generator(const std::string type="BLDPC")
Default constructor.
GF2mat get_submatrix(int m1, int n1, int m2, int n2) const
Submatrix from (m1,n1) to (m2,n2)
void set_size(int n, bool copy=false)
Resizing an Array<T>.
int get_nvar() const
Get the number of variable nodes.
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.
int cols() const
Returns the number of columns of the sparse 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.
std::string get_decoding_method() const
Return the decoding method.
void integrity_check()
Function to check the integrity of the parity check matrix and generator.
Sparse_Vec< bin > get_row(int r) const
Get a specific row from the matrix.
QLLR to_qllr(double l) const
Convert a "real" LLR value to an LLR type.
#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.
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.
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.
The IT++ file format reading class.
int get_ncheck() const
Get the number of check nodes (number of rows)
int M
Number of parity check bits = H_enc.rows()
void save_base_matrix(const std::string &filename) const
Save base matrix to a text file.
void set_row(int i, bvec x)
Set row i to a binary vector x.
int rows() const
Get number of rows.
int floor_i(double x)
The nearest smaller integer.
void save_alist(const std::string &alist_file) const
Save matrix to alist_file text file in alist format.
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 nnz()
Number of non-zero elements in the sparse vector.
bool syndrome_check(const QLLRvec &LLR) const
Syndrome check, on QLLR vector.
double get_rate() const
Get the code rate.
Sparse_Vec< bin > get_col(int c) const
Get a specific column from the matrix.
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 N
Codeword length = H_enc.cols()
bool T_fact_update_addcol(GF2mat &T, GF2mat &U, ivec &P, bvec newcol) const
TXP factorization update, when column is added.
double get_rate() const
Get the coderate.
Sparse_Mat< bin > GF2mat_sparse
Sparse GF(2) matrix.
void add_rows(int i, int j)
Add (or equivalently, subtract) rows.
bool is_valid() const
Verify initialisation.
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 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.
int get_exp_factor() const
Get expansion factor.
Binary arithmetic (boolean) class.
int get_nvar() const
Get the number of variable nodes (number of columns)
#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.
QLLR Boxplus(QLLR a, QLLR b) const
Hagenauer's "Boxplus" operator.
friend ITPP_EXPORT std::ostream & operator<<(std::ostream &os, const LDPC_Code &C)
Print some properties of the codec in plain text.
int rows() const
Returns the number of rows of the sparse matrix.
void initialize(int ncheck, int nvar)
Initialize an empty matrix of size ncheck x nvar.
bool is_initialized() const
Check if generator is initialized.
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.
virtual void display_stats() const
Display some information about the matrix.
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.
LDPC_Parity()
Default constructor.
GF2mat_sparse_alist export_alist() const
Export matrix to GF2mat_sparse_alist format.
Implementation of Low-Density Parity Check (LDPC) codes.
virtual void close()
Close the file.
virtual void encode(const bvec &input, bvec &output)
Encode codeword.
bin get(int i, int j) const
Getting element.
QLLRvec soft_syndrome_check(const QLLRvec &LLR) const
Soft syndrome check.
ivec sumX1
Actual number of ones in each column.
const Array< T > concat(const Array< T > &a, const T &e)
Append element e to the end of the Array a.