An official website of the United States government
This paper gives a simple method to construct generator matrices with polynomial entries (and hence offers an alternative encoding method to the one commonly used) for all quasi-cyclic low-density parity-check (QC-LDPC) codes, even for those that are rank deficient. The approach is based on constructing a set of codewords with the desired total rank by using minors of the parity-check matrix. We exemplify the method on several well-known and standard codes. Moreover, we explore the connections between the minors of the parity-check matrix and the known upper bound on minimum distance and provide a method to compute the rank of any parity-check matrix representing a QC-LDPC code, and hence the dimension of the code, by using the minors of the corresponding polynomial parity-check matrix.
more »
« less
Fast and Flexible Probabilistic Model Counting
We present a probabilistic model counter that can trade off running time with approximation accuracy. As in several previous works, the number of models of a formula is estimated by adding random parity constraints (equations). One key difference with prior works is that the systems of parity equations used correspond to the parity check matrices of Low Density Parity Check (LDPC) error-correcting codes. As a result, the equations tend to be much shorter, often containing fewer than 10 variables each, making the search for models that also satisfy the parity constraints far more tractable. The price paid for computational tractability is that the statistical properties of the basic estimator are not as good as when longer constraints are used. We show how one can deal with this issue and derive rigorous approximation guarantees by performing more solver invocations.
more »
« less
- Award ID(s):
- 1733884
- PAR ID:
- 10064719
- Date Published:
- Journal Name:
- Theory and Applications of Satisfiability Testing – SAT 2018
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Linear nested codes, where two or more sub-codes are nested in a global code, have been proposed as candidates for reliable multi-terminal communication. In this paper, we consider nested array-based spatially coupled low-density parity-check (SC-LDPC) codes and propose a line-counting based optimization scheme for minimizing the number of dominant absorbing sets in order to improve its performance in the high signal-to-noise ratio regime. Since the parity-check matrices of different nested sub-codes partially overlap, the optimization of one nested sub-code imposes constraints on the optimization of the other sub-codes. To tackle these constraints, a multi-step optimization process is applied first to one of the nested codes, then sequential optimization of the remaining nested codes is carried out based on the constraints imposed by the previously optimized sub-codes. Results show that the order of optimization has a significant impact on the number of dominant absorbing sets in the Tanner graph of the code, resulting in a trade-off between the performance of a nested code structure and its optimization sequence: the code which is optimized without constraints has fewer harmful structures than the code which is optimized with constraints. We also show that for certain code parameters, dominant absorbing sets in the Tanner graphs of all nested codes are completely removed using our proposed optimization strategy.more » « less
-
In this paper, we present an efficient strategy to enumerate the number of k-cycles, g ≤ k < +2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (n c , n v )-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)≜(HH⊤)⌊m/2⌋H(mmod2), where m ≥ 0. For example, in the case of QC-LDPC codes based on the 3 × n v fully-connected protograph, the complexity of determining the number of k-cycles, Nk, for k = 4, 6 and 8, is O(n2vlog(N)), O(n2vlog(nv)log(N)) and O(n4vlog4(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.more » « less
-
In this paper, we present an efficient strategy to enumerate the number of k-cycles, g≤k<2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (dv,dc)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)(HHT)m/2H(m2), where m≥0. We provide formulas for the number of k-cycles, Nk, by just taking into account repetitions in some multisets constructed from the matrices Bm(H). This approach is shown to have low complexity. For example, in the case of QC-LDPC codes based on the 3×nv fully-connected protograph, the complexity of determining Nk, for k=4,6,8,10 and 12, is O(nv2log(N)), O(nv2log(nv)log(N)), O(nv4log4(nv)log(N)), O(nv4log(nv)log(N)) and O(nv6log6(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.more » « less
-
Abstract In a recent article, one of the authors developed a multigrid technique for coarse‐graining dynamic powergrid models. A key component in this technique is a relaxation‐based coarsening of the graph Laplacian given by the powergrid network and its weighted graph, which is represented by the admittance matrix. In this article, we use this coarsening strategy to develop a multigrid method for solving a static system of nonlinear equations that arises through Ohm's law, the so‐called powerflow equations. These static equations are tightly knitted to the dynamic model in that the full powergrid model is an algebraic‐differential system with the powerflow equations describing the algebraic constraints. We assume that the dynamic model corresponds to a stable operating powergrid, and thus, the powerflow equations are associated with a physically stable system. This stability permits the coarsening of the powerflow equations to be based on an approximate graph Laplacian, which is embedded in the powerflow system. By algebraically constructing a hierarchy of approximate weighted graph Laplacians, a hierarchy of nonlinear powerflow equations immediately becomes apparent. This latter hierarchy can then be used in a full approximation scheme (FAS) framework that leads to a nonlinear solver with generally a larger basin of attraction than Newton's method. Given the algebraic multigrid (AMG) coarsening of the approximate Laplacians, the solver is an AMG‐FAS scheme. Alternatively, using the coarse‐grid nodes and interpolation operators generated for the hierarchy of approximate graph Laplacians, a multiplicative‐correction scheme can be derived. The derivation of both schemes will be presented and analyzed, and numerical examples to demonstrate the performance of these schemes will be given.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
