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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Multivariate Weight Enumerator for Tail-biting Trellis pseudocodewords

引用

Journal of Generalized Lie Theory and Applications 2015年第S1期9卷 1-4页

作者： Nigel Boston

Tail-biting-trellis representations of codes allow for iterative decoding algorithms, which are limited in effectiveness by the presence of pseudocodewords. We introduce a multivariate weight enumerator that keeps track of these pseudocodewords. This enumerator is invariant under many linear transformations, often enabling us to compute it exactly. The extended binary Golay code has a particularly nice tail-biting-trellis and a famous unsolved question is to determine its minimal AWGN pseudodistance. The new enumerator provides an inroad to this problem.

关键词： Binary golay code invariant theory pseudocodewords Tail-biting trellis Weight enumerators

来源：评论

学校读者我要写书评

暂无评论

Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第3期66卷 1281-1317页

作者： Rosnes, Eirik Helmling, Michael Simula UiB N-5020 Bergen Norway Univ Koblenz Landau Math Inst D-50722 Koblenz Germany Fraunhofer Inst Ind Math ITWM D-67663 Kaiserslautern Germany

In this work, we consider adaptive linear programming (ALP) decoding of linear codes over prime fields, i.e., the finite fields F-p of size p where p is a prime, when used over a p-ary input memoryless channel. In particular, we provide a general construction of valid inequalities (using no auxiliary variables) for the codeword polytope (or the convex hull) of the so-called constant-weight embedding of a single parity-check (SPC) code over any prime field. The construction is based on sets of vectors, called building block classes, that are assembled to form the left-hand side of an inequality according to several rules. In the case of almost doubly-symmetric valid classes we prove that the resulting inequalities are all facet-defining, while we conjecture this to be true if and only if the class is valid and symmetric. Valid symmetric classes impose certain symmetry conditions on the elements of the vectors from the class, while valid doubly-symmetric classes impose further technical symmetry conditions. For p=3, there is only a single valid symmetric class and we prove that the resulting inequalities together with the so-called simplex constraints give a complete and irredundant description of the codeword polytope of the embedded SPC code. For p>5, we show that there are additional facets beyond those from the proposed construction. As an example, for p=7, we provide additional inequalities that all define facets of the embedded codeword polytope. The resulting overall set of linear (in)equalities is conjectured to be irredundant and complete. Such sets of linear (in)equalities have not appeared in the literature before, have a strong theoretical interest, and we use them to develop an efficient (relaxed) ALP decoder for general (non-SPC) linear codes over prime fields. The key ingredient is an efficient separation algorithm based on the principle of dynamic programming. Furthermore, we construct a decoder for linear codes over arbitrary fields F-q with q=p(m) an

关键词： Maximum likelihood decoding Linear codes Parity check codes Lattices Heuristic algorithms Linear programming Adaptive linear programming (LP) decoding dynamic programming low-density parity-check (LDPC) codes pseudocodewords nonbinary codes

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Pseudocodeword-free criterion for codes with cycle-free Tanner graph

引用

DESIGNS CODES AND CRYPTOGRAPHY 2018年第12期86卷 2791-2805页

作者： Kositwattanarerk, Wittawat Mahidol Univ Dept Math Fac Sci Bangkok 10400 Thailand Commiss Higher Educ Ctr Excellence Math Si Ayutthaya RD Bangkok 10400 Thailand

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 codes. In this paper, we argue in the context of graph cover pseudocodeword that, for a code that permits a cycle-free Tanner graph, cycles have no effect on error performance as long as they are a part of redundant rows. Specifically, we characterize all parity-check matrices that are pseudocodeword-free for such class of codes.

关键词： Iterative decoding Linear programming decoding Low-density parity-check (LDPC) code Tanner graphs pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved Penalty Functions of ADMM Penalized Decoder for LDPC Codes

引用

IEEE COMMUNICATIONS LETTERS 2017年第2期21卷 234-237页

作者： Wang, Biao Mu, Jianjun Jiao, Xiaopeng Wang, Zhongfei Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China Baoji Univ Arts & Sci Sch Math & Informat Sci Baoji 721013 Peoples R China

By making the pseudocodewords more costly than codewords, the alternating direction method of multipliers (ADMM) penalized decoder can improve the error rate performances significantly for low-density parity-check (LDPC) codes at low signal-to-noise ratios. In this letter, we design two improved piecewise penalty functions for ADMM penalized decoder by increasing the slope of the penalty function at the points near x = 0 and x = 1. The improved penalty functions can punish pseudocodewords more quickly and thus increase the decoding speed. Simulation results over two LDPC codes show that the proposed method improves the error rate performances and reduces the decoding time considerably.

关键词： Alternating direction method of multipliers (ADMM) LDPC codes penalty function pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：