Computing the Stopping Distance of a Tanner Graph Is NP-Hard [PDF]
IEEE Transactions on Information Theory, 2007 Summary: Two decision problems related to the computation \(f\) stopping sets in Tanner graphs are shown to be NP-complete. It follows as a consequence that there exists no polynomial time algorithm for computing the stopping distance of a Tanner graph unless P \(=\) NP.
Karunakaran Murali Krishnan +1 more
exaly +4 more sources
Pseudocodeword-free criterion for codes with cycle-free Tanner graph [PDF]
Designs, Codes, and Cryptography, 2018 Iterative decoding and linear programming decoding are guaranteed to converge to the maximum-likelihood codeword when the underlying Tanner graph is cycle-free. Therefore, cycles are usually seen as the culprit of low-density parity-check (LDPC) codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a ...
Wittawat Kositwattanarerk
exaly +3 more sources
LDPC Codes on Balanced Incomplete Block Designs: Construction, Girth, and Cycle Structure Analysis [PDF]
EntropyIn this paper, we investigate the cycle structure inherent in the Tanner graphs of low-density parity-check (LDPC) codes constructed from balanced incomplete block designs (BIBDs).
Hengzhou Xu +4 more
doaj +2 more sources
Determining the Upper-Bound on the Code Distance of Quantum Stabilizer Codes Through the Monte Carlo Method Based on Fully Decoupled Belief Propagation [PDF]
EntropyThe code distance is a critical parameter of quantum stabilizer codes (QSCs), and determining it—whether exactly or approximately—is known to be an NP-complete problem.
Zhipeng Liang +4 more
doaj +2 more sources
Construction of Efficient High-Rate Protograph QC-LDPC Codes by Joint EXIT Chart, PEG, AWD, and QC-NLACE Techniques [PDF]
EntropyTo obtain efficient channel codes with high power efficiency at moderate signal-to-noise ratios (SNRs), an efficient high-rate protograph quasi-cyclic (QC) low-density parity-check (LDPC) codes is optimally constructed.
Ying Chen +4 more
doaj +2 more sources
Adaptive Learned Belief Propagation for Decoding Error-Correcting Codes [PDF]
EntropyWeighted belief propagation (WBP) for the decoding of linear block codes is considered. In WBP, the Tanner graph of the code is unrolled with respect to the iterations of the belief propagation decoder.
Alireza Tasdighi, Mansoor Yousefi
doaj +2 more sources
ON THE CLASS OF ARRAY-BASED APM-LDPC CODES [PDF]
Journal of Algebraic Systems, 2021 We construct an explicit class of affine permutation matrix low-density parity-check (APM-LDPC) codes based on the array parity-check matrix by using two affine maps f (x) = x-1 and g(x) = 2x-1 on Z_m, where m is an odd prime number, with girth 6 and ...
A. Nassaj, A. R. Naghipour
doaj +1 more source
Quantum message-passing algorithm for optimal and efficient decoding [PDF]
Quantum, 2022 Recently, Renes proposed a quantum algorithm called belief propagation with quantum messages (BPQM) for decoding classical data encoded using a binary linear code with tree Tanner graph that is transmitted over a pure-state CQ channel \cite{renes_2017 ...
Christophe Piveteau, Joseph M. Renes
doaj +1 more source
A REDUCTION IN THE SEARCH SPACE OF QC-LDPC CODES WITH GIRTH 8 [PDF]
Journal of Algebraic Systems, 2020 In this paper, we define a structure to obtain exponent matrices of girth-8 QC-LDPC codes with column weight 3. Using the difference matrices introduced by Amirzade et al., we investigate necessary and sufficient conditions which result in a Tanner graph
F. Amirzade +2 more
doaj +1 more source
Efficient Decoding of Turbo Codes with Nonbinary Belief Propagation
EURASIP Journal on Wireless Communications and Networking, 2008 This paper presents a new approach to decode turbo codes using a nonbinary belief propagation decoder. The proposed approach can be decomposed into two main steps.
Thierry Lestable +2 more
doaj +2 more sources