Results 1 to 10 of about 3,618 (149)
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 +5 more sources
Pseudocodewords of Tanner Graphs
IEEE Transactions on Information Theory, 2007 This papers presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel.
Christine Kelley
exaly +4 more sources
Advances in Mathematics of Communications, 2012 Codes defined on graphs and their properties have been subjects of intense recent research. In this work, we are concerned with codes that have planar Tanner graphs. When the Tanner graph is planar, message-passing decoders can be efficiently implemented on chips without any issues of wiring.
Andrew Thangaraj
exaly +2 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 ...
exaly +4 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
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
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