skip to main content


Title: Using Minors to Construct Generator Matrices for Quasi-Cyclic LDPC Codes
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
Award ID(s):
1757207 2145917 2148358 1914635
NSF-PAR ID:
10366059
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
2022 IEEE International Symposium on Information Theory (ISIT)
Page Range / eLocation ID:
548 to 553
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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
  2. 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
  3. 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 onedge 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
  4. The linear representation of a subset of a finite projective space is an incidence system of affine points and lines determined by the subset. In this paper we use character theory to show that the rank of the incidence matrix has a direct geometric interpretation in terms of certain hyperplanes. We consider the LDPC codes defined by taking the incidence matrix and its transpose as parity-check matrices, and in the former case prove a conjecture of Vandendriessche that the code is generated by words of minimum weight called plane words. In the latter case we compute the minimum weight in several cases and provide explicit constructions of minimum weight codewords. 
    more » « less
  5. null (Ed.)
    This paper presents a ternary low-density parity-check (LDPC) error correction system for wireless electrocardiogram sensors to improve the accuracy of arrhythmia classification. The classification system is based on ternary Delta-modulated bitstreams and rotation linear kernel support vector machines, which identifies the supraventricular ectopic beat (SVEB) and the ventricular ectopic beat (VEB) over the normal heartbeats. We model errors using a ternary symmetric channel with probability parameter p and construct a variety of ternary LDPC codes with different coding rates by concatenating two-component sub-matrices to form a parity-check matrix with a quasi-cyclic structure that facilitates the hardware design. In particular, a hardware-friendly LDPC encoder circuit is proposed that leverages the highly structured parity-check matrix to perform serial generation of the parity symbols using an accumulator and a look-up table. The encoder circuits are implemented on FPGA and synthesized on ASIC using a 32 nm CMOS process. Simulation results show that the ternary LDPC codes can significantly improve classification accuracy in the presence of errors. For example, with an error probability of up to 21% in the sensor output bitstreams, the classification accuracy remains above 99% with the proposed error correction system. 
    more » « less