检索结果-内蒙古大学图书馆

On Minimal pseudocodewords of Binary Hamming Codes

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第4期71卷 2360-2372页

作者： Liu, Haiyang Jiao, Xiaopeng Ma, Lianrong Chinese Acad Sci Inst Microelect Beijing 100029 Peoples R China Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China Tsinghua Univ Dept Math Sci Beijing 100084 Peoples R China

pseudocodewords, and in particular minimal pseudocodewords, play an important role in understanding the performance of linear programming (LP) decoding. In this paper, we investigate minimal pseudocodewords of binary Hamming codes described by full-rank parity-check matrices. We first provide some general results on minimal pseudocodewords with support size 3 of a binary parity-check matrix. We also prove a lower bound on the minimum binary symmetric channel (BSC) pseudoweight of a binary parity-check matrix. Then we prove that a full-rank parity-check matrix of a binary Hamming code has minimal pseudocodewords of certain types whose support sizes are larger than 3. Interestingly enough, the BSC pseudoweight of all these minimal pseudocodewords is 2. Using this fact as well as the above-mentioned lower bound, we further prove that a full-rank parity-check matrix of a binary Hamming code has minimum BSC pseudoweight 2. Moreover, the additive white Gaussian noise channel (AWGNC) pseudoweight of all these minimal pseudocodewords is 3. Based on numerical observations, we conjecture that a full-rank parity-check matrix of a binary Hamming code has minimum AWGNC pseudoweight 3. Finally, we provide more properties of a subset of minimal pseudocodewords of a full-rank parity-check matrix of a binary Hamming code.

关键词： Codes Maximum likelihood decoding Vectors Symmetric matrices Lower bound Linear codes Encoding Parity check codes Minimization Memoryless systems Binary linear codes Hamming codes linear programming (LP) decoding permanent pseudocodewords pseudoweight

来源：评论

学校读者我要写书评

暂无评论

pseudocodewords of tanner graphs

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第11期53卷 4013-4038页

作者： Kelley, Christine A. Sridhara, Deepak Ohio State Univ Dept Math Columbus OH 43210 USA Seagate Technol Pittsburgh PA 15222 USA

This paper 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. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value t that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.

关键词： iterative decoding low-density parity-check (LDPC) codes min-sum iterative decoder pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

pseudocodewords of Parity-Check Codes Over Fields of Prime Cardinality

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第9期60卷 5215-5227页

作者： Kositwattanarerk, Wittawat Matthews, Gretchen L. Mahidol Univ Dept Math Fac Sci Bangkok 10400 Thailand Commiss Higher Educ Ctr Excellence Math Bangkok 10400 Thailand Clemson Univ Dept Math Sci Clemson SC 29634 USA

This paper considers pseudocodewords of low-density parity-check codes over alphabets with prime cardinality p for use over the p-ary symmetric channel. pseudocodewords are decoding algorithm outputs that may not be legitimate codewords. Here, we consider pseudocodewords arising from graph cover decoding and linear programming decoding. For codes over the binary alphabet, such pseudocodewords correspond to rational points of the fundamental polytope. They can be characterized via the fundamental cone, which is the conic hull of the fundamental polytope;the pseudocodewords are precisely those integer vectors within the fundamental cone that reduce modulo 2 to a codeword. In this paper, we determine a set of conditions that pseudocodewords of codes over F-p, the finite field of prime cardinality p, must satisfy. To do so, we introduce a class of critical multisets and a mapping, which associates a real number to each pseudocodeword over F-p. The real numbers associated with pseudocodewords are subject to lower bounds imposed by the critical multisets. The inequalities are given in terms of the parity-check matrix entries and critical multisets. This gives a necessary and sufficient condition for pseudocodewords of codes over F-2 and F-3 and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F-3 are found as a Hilbert basis for the lifted fundamental cone.

关键词： Iterative decoding low-density parity-check (LDPC) code fundamental cone pseudocodewords irreducible pseudocodewords nonbinary code

来源：评论

学校读者我要写书评

暂无评论

pseudocodewords from Bethe Permanents

Pseudocodewords from Bethe Permanents

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Smarandache, Roxana Univ Notre Dame Dept Math & Elect Engn Notre Dame IN 46556 USA

It was recently conjectured that a vector with components equal to the Bethe permanent of certain submatrices of a parity-check matrix is a pseudocodeword. In this paper, we analyze some important cases for which the ... 详细信息

ISBN: (纸本)9781479904464

关键词： Bethe-permanents permanents pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

pseudocodewords of Linear Programming Decoding of 3-Dimensional Turbo Codes

Pseudocodewords of Linear Programming Decoding of 3-Dimensio...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Rosnes, Eirik Helmling, Michael Graell i Amat, Alexandre Univ Bergen Dept Informat N-5020 Bergen Norway Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany Chalmers Dept Signals & Syst SE-41296 Gothenburg Sweden

ISBN: (纸本)9781457705953

In this work, we consider pseudocodewords of (relaxed) linear programming (LP) decoding of 3-dimensional turbo codes (3D-TCs), recently introduced by Berrou et al.. Here, we consider binary 3D-TCs while the original work of Berrou et al. considered double-binary codes. We present a relaxed LP decoder for 3D-TCs, which is an adaptation of the relaxed LP decoder for conventional turbo codes proposed by Feldman in his thesis. The vertices of this relaxed polytope are the pseudocodewords. We show that the support set of any pseudocodeword is a stopping set of iterative decoding of 3D-TCs using maximum a posteriori constituent decoders on the binary erasure channel. Furthermore, we present a numerical study of small block length 3D-TCs, which shows that typically the minimum pseudoweight (on the additive white Gaussian noise (AWGN) channel) is smaller than both the minimum distance and the stopping distance. In particular, we performed an exhaustive search over all interleaver pairs in the 3D-TC (with input block length K = 128) based on quadratic permutation polynomials over integer rings with a quadratic inverse. The search shows that the best minimum AWGN pseudoweight is strictly smaller than the best minimum/stopping distance.

关键词： 3D turbo codes AWGN AWGN channel AWGN channels Maximum likelihood decoding Polynomials Turbo codes Upper bound Vectors binary erasure channel iterative decoding iterative decoding linear programming linear programming decoding maximum a posteriori constituent decoders maximum likelihood estimation pseudocodewords quadratic permutation polynomials turbo codes

来源：评论

学校读者我要写书评

暂无评论

On pseudocodewords and Decision Regions of Linear Programming Decoding of HDPC Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2012年第4期60卷 963-971页

作者： Lifshitz, Asi Be'ery, Yair Tel Aviv Univ Sch Elect Engn IL-69978 Ramat Aviv Israel

In this paper we explore the decision regions of Linear Programming (LP) decoding. We compare the decision regions of an LP decoder, a Belief Propagation (BP) decoder and the optimal Maximum Likelihood (ML) decoder. We study the effect of minimal-weight pseudocodewords on LP decoding. We present global optimization as a method for finding the minimal pseudoweight of a given code as well as the number of minimal-weight generators. We present a complete pseudoweight distribution for the [24, 12, 8] extended Golay code, and provide justifications of why the pseudoweight distribution alone cannot be used for obtaining a tight upper bound on the error probability.

关键词： Belief propagation bounded distance decoding generators global optimization linear programming LP relaxation pseudocodewords pseudoweight

来源：评论

学校读者我要写书评

暂无评论

Analysis of Connections Between pseudocodewords

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第9期55卷 4099-4107页

作者： Axvig, Nathan Dreher, Deanna Morrison, Katherine Psota, Eric Perez, Lance C. Walker, Judy L. Univ Nebraska Dept Math Lincoln NE 68588 USA Univ Nebraska Dept Elect Engn Lincoln NE 68588 USA

The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature-linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.

关键词： Graph cover decoding iterative message-passing decoding linear programming decoding low-density parity-check (LDPC) codes pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Graphical Characterizations of Linear Programming pseudocodewords for Cycle Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第9期59卷 5917-5934页

作者： Axvig, Nathan Dreher, Deanna Virginia Mil Inst Dept Appl Math Lexington VA 24450 USA Univ Nebraska Dept Math Lincoln NE 68502 USA

The performance of linear programming decoding is determined by the set of nonzero linear programming pseudocodewords. The minimum pseudoweight of this set of linear programming pseudocodewords is also generally accepted as a good predictor of the performance of iterative message-passing decoding. Since the linear programming decoder has a natural description based on the Tanner graph of a code, linear programming pseudocodewords can be analyzed from a graphical viewpoint. In this paper, two graphical characterizations of linear programming pseudocodewords of cycle codes are provided: one for the entire set of linear programming pseudocodewords, and one for the set of minimal linear programming pseudocodewords. The first of these characterizations is used to determine a formula for the minimum degree of a graph cover necessary to realize a linear programming pseudocodeword of a cycle code, and the second is used to prove a result concerning the asymptotic performance of the linear programming decoder when considering transmission over either the additive white Gaussian noise channel or the binary symmetric channel. Finally, a discussion contrasting these two characterizations both with each other and with Horn's characterization of bad pseudocycles is provided.

关键词： Coding theory graph theory linear programming (LP) pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Minimum pseudoweight and minimum pseudocodewords of LDPC codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第1期54卷 480-485页

作者： Xia, Shu-Tao Fu, Fang-Wei Tsing Hua Univ Grad Sch Shenzen Shenzhen 518055 Guangdong Peoples R China SE Univ Natl Mobile Commun Guangdong Nanjing 210096 Peoples R China Nankai Univ Chern Inst Math Tianjin 300071 Peoples R China Nankai Univ Key Lab Pure Math & Combinator Tianjin 300071 Peoples R China

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than 4 is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth 4, and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches 1 as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

关键词： fundamental cone linear programming (LP) decoding low-density parity-check (LDPC) codes pseudocodewords pseudoweight stopping sets

来源：评论

学校读者我要写书评

暂无评论

Suppressing Fractional pseudocodewords by Eliminating Small Instantons

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2016年第2期E99A卷 674-677页

作者： Guo, Junjun Mu, Jianjun Jiao, Xiaopeng Zhao, Peng Xian Technol Univ Sch Comp Sci & Engn Xian 710021 Peoples R China Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China

In this letter, a new method is presented to suppress fractional pseudocodewords by eliminating small instantons of irregular low-density parity-check (LDPC) codes under the linear programming (LP) decoding over the binary symmetric channel (BSC). By appending several new rows found by the integer linear programming formulation to the original parity-check matrix, the optimal distribution spectrum of BSC-instantons in the modified code is obtained. Simulation results show that the proposed method can improve the fractional distance of parity-check matrices and considerably enhance the error-correcting performance of irregular LDPC codes under the LP decoding at the cost of a slightly loss of the original code rate.

关键词： LDPC codes pseudocodewords instantons fractional distance linear programming (LP) decoding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：