More Like this

1. On the Tanner Cycle Distribution of QC-LDPC Codes from Polynomial Parity-Check Matrices

   https://doi.org/10.1109/isit54713.2023.10207005  

   Gómez-Fonseca, Anthony; Smarandache, Roxana; Mitchell, David G. (June 2023, 023 IEEE International Symposium on Information Theory (ISIT))

   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
2. Using Minors to Construct Generator Matrices for Quasi-Cyclic LDPC Codes

   https://doi.org/10.1109/ISIT50566.2022.9834862  

   Smarandache, Roxana; Gomez-Fonseca, Anthony; Mitchell, David G. (June 2022, 2022 IEEE International Symposium on Information Theory (ISIT))

   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
3. Concatenated Spatially Coupled LDPC Codes with Sliding Window Decoding for Joint Source-Channel Coding

   https://doi.org/10.1109/tcomm.2021.3126750  

   Golmohammadi, Ahmad; Mitchell, David G. (November 2021, IEEE Transactions on Communications)

   In this paper, a method for joint source-channel coding (JSCC) based on concatenated spatially coupled low-density parity-check (SC-LDPC) codes is investigated. A construction consisting of two SC-LDPC codes is proposed: one for source coding and the other for channel coding, with a joint belief propagation-based decoder. Also, a novel windowed decoding (WD) scheme is presented with significantly reduced latency and complexity requirements. The asymptotic behavior for various graph node degrees is analyzed using a protograph-based Extrinsic Information Transfer (EXIT) chart analysis for both LDPC block codes with block decoding and for SC-LDPC codes with the WD scheme, showing robust performance for concatenated SC-LDPC codes. Simulation results show a notable performance improvement compared to existing state-of-the-art JSCC schemes based on LDPC codes with comparable latency and complexity constraints. 

   more » « less
4. Matrix Multiplication Verification Using Coding Theory

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.42  

   Bennett, Huck; Gajulapalli, Karthik; Golovnev, Alexander; Warton, Evelyn (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three n × n matrices A, B, and C as input, to decide whether AB = C. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in Õ(n²) time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in o(n^ω) time). To that end, we give two algorithms for MMV in the case where AB - C is sparse. Specifically, when AB - C has at most O(n^δ) non-zero entries for a constant 0 ≤ δ < 2, we give (1) a deterministic O(n^(ω-ε))-time algorithm for constant ε = ε(δ) > 0, and (2) a randomized Õ(n²)-time algorithm using δ/2 ⋅ log₂ n + O(1) random bits. The former algorithm is faster than the deterministic algorithm of Künnemann (ESA, 2018) when δ ≥ 1.056, and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses log₂ n + O(1) random bits (in turn fewer than Freivalds’s algorithm). Our algorithms are simple and use techniques from coding theory. Let H be a parity-check matrix of a Maximum Distance Separable (MDS) code, and let G = (I | G') be a generator matrix of a (possibly different) MDS code in systematic form. Our deterministic algorithm uses fast rectangular matrix multiplication to check whether HAB = HC and H(AB)^T = H(C^T), and our randomized algorithm samples a uniformly random row g' from G' and checks whether g'AB = g'C and g'(AB)^T = g'C^T. We additionally study the complexity of MMV. We first show that all algorithms in a natural class of deterministic linear algebraic algorithms for MMV (including ours) require Ω(n^ω) time. We also show a barrier to proving a super-quadratic running time lower bound for matrix multiplication (and hence MMV) under the Strong Exponential Time Hypothesis (SETH). Finally, we study relationships between natural variants and special cases of MMV (with respect to deterministic Õ(n²)-time reductions). 

   more » « less
5. Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objects

   https://doi.org/10.1186/s13638-023-02273-0  

   Battaglioni, Massimo; Chiaraluce, Franco; Baldi, Marco; Pacenti, Michele; Mitchell, David G. (December 2023, EURASIP Journal on Wireless Communications and Networking)

   Abstract It is well known that some harmful objects in the Tanner graph of low-density parity-check (LDPC) codes have a negative impact on their error correction performance under iterative message-passing decoding. Depending on the channel and the decoding algorithm, these harmful objects are different in nature and can be stopping sets, trapping sets, absorbing sets, or pseudocodewords. Differently from LDPC block codes, the design of spatially coupled LDPC codes must take into account the semi-infinite nature of the code, while still reducing the number of harmful objects as much as possible. We propose a general procedure, based on edge spreading , enabling the design of good quasi-cyclic spatially coupled LDPC (QC-SC-LDPC) codes. These codes are derived from quasi-cyclic LDPC (QC-LDPC) block codes and contain a considerably reduced number of harmful objects with respect to the original QC-LDPC block codes. We use an efficient way of enumerating harmful objects in QC-SC-LDPCCs to obtain a fast algorithm that spans the search space of potential candidates to select those minimizing the multiplicity of the target harmful objects. We validate the effectiveness of our method via numerical simulations, showing that the newly designed codes achieve better error rate performance than codes presented in previous literature. 

   more » « less