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

Lifting the Fundamental Cone and Enumerating the pseudocodewords of a Parity-Check Code

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 898-909页

作者： Kositwattanarerk, Wittawat Matthews, Gretchen L. Clemson Univ Dept Math Sci Clemson SC 29634 USA

The performance of message-passing iterative decoding and linear programming decoding depends on the Tanner graph representation of the code. If the underlying graph contains cycles, then such algorithms could produce a noncodeword output. The study of pseudocodewords aims to explain this noncodeword output. We examine the structure of the pseudocodewords and show that there is a one-to-one correspondence between graph cover pseudocodewords and integer points in a lifted fundamental cone. This gives a simple proof that the generating function of the pseudocodewords for a general parity-check code is rational (a fact first proved by Li, Lu, and Wang (Lecture Notes in Computer Science, vol. 5557, 2009) via other methods). Our approach yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Specifically, Barvinok's algorithm and the Barvinok-Woods projection algorithm are applied, and irreducible pseudocodewords are found via a Hilbert basis for the lifted fundamental cone.

关键词： Fundamental cone irreducible pseudocodewords iterative decoding linear programming (LP) decoding low-density parity-check (LDPC) code pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

CCS: It's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions

引用

ACTA INFORMATICA 2015年第2-3期52卷 175-205页

作者： van Glabbeek, Rob J. Hoefner, Peter NICTA Sydney NSW Australia UNSW Sydney NSW Australia

In the process algebra community it is sometimes suggested that, on some level of abstraction, any distributed system can be modelled in standard process-algebraic specification formalisms like CCS. This sentiment is strengthened by results testifying that CCS, like many similar formalisms, is Turing powerful and provides a mechanism for interaction. This paper counters that sentiment by presenting a simple fair scheduler-one that in suitable variations occurs in many distributed systems-of which no implementation can be expressed in CCS, unless CCS is enriched with a fairness assumption. Since Dekker's and Peterson's mutual exclusion protocols implement fair schedulers, it follows that these protocols cannot be rendered correctly in CCS without imposing a fairness assumption. Peterson expressed this algorithm correctly in pseudocode without resorting to a fairness assumption, so it furthermore follows that CCS lacks the expressive power to accurately capture such pseudocode.

关键词： CONSTRAINT programming (Computer science) FORMAL sociology SOCIAL interaction ABSTRACT thought SOCIAL isolation pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Linear-Programming Decoding of Nonbinary Linear Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第9期55卷 4134-4154页

作者： Flanagan, Mark F. Skachek, Vitaly Byrne, Eimear Greferath, Marcus Univ Coll Dublin Sch Elect Elect & Mech Engn Dublin 4 Ireland Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland Univ Coll Dublin Sch Math Sci Dublin 4 Ireland

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the "maximum-likelihood (ML) certificate" property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for the [11.6] ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

关键词： Coded modulation linear-programming decoding low-density parity-check (LDPC) codes 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

来源：评论

学校读者我要写书评

暂无评论

Adaptive Methods for Linear Programming Decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第12期54卷 5396-5410页

作者： Taghavi N, Mohammad H. Siegel, Paul H. Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Univ Calif San Diego Ctr Magnet Recording Res La Jolla CA 92093 USA

Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that by starting from a simple LP problem and adaptively adding the necessary constraints, the complexity of LP decoding can be significantly reduced. In particular, we observe that with adaptive LP decoding, the sizes of the LP problems that need to be solved become practically independent of the density of the parity-check matrix. We further show that adaptively adding extra constraints, such as constraints based on redundant parity checks, can provide large gains in the performance.

关键词： Cutting planes low-density parity-check (LDPC) codes linear programming (LP) LP decoding message passing maximum-likelihood (ML) decoding pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Pseudocodeword Weights for LDPC Codes under Differential PSK Transmission over the Noncoherent AWGN Channel

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2011年第5期59卷 1218-1223页

作者： Mo, Elisa Armand, Marc A. Natl Univ Singapore Dept Elect & Comp Engn Singapore Singapore

This Letter considers the finite-length analysis of iterative decoding of low-density parity-check codes under differential binary-phase-shift-keying (DBPSK) and differential quadrature-phase-shift-keying (DQPSK) over the noncoherent additive-white-Gaussian-noise channel. Specifically, we derive the weight of the pseudocodewords of a Tanner graph under these signaling schemes and use them to explain the difference in error performance between coded DBPSK and coded DQPSK.

关键词： Belief-propagation decoding differential phase-shift-keying graph-cover decoding iterative decoding pseudocodewords spectral thinning

来源：评论

学校读者我要写书评

暂无评论

On the Pseudocodeword Redundancy of Binary Linear Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第7期58卷 4848-4861页

作者： Zumbraegel, Jens Skachek, Vitaly Flanagan, Mark F. Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 2A7 Canada

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

关键词： Fundamental cone low-density parity-check codes pseudocodeword redundancy pseudocodewords pseudoweight

来源：评论

学校读者我要写书评

暂无评论

Augmented belief propagation decoding of low-density parity check codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2007年第7期55卷 1308-1317页

作者： Varnica, Nedeljko Fossorier, Marc P. C. Kavcic, Aleksandar Harvard Univ Cambridge MA 02138 USA Univ Hawaii Manoa Dept Elect Engn Honolulu HI 96822 USA Harvard Univ Div Engn & Appl Sci Cambridge MA 02138 USA

We propose an augmented belief propagation (BP) decoder for low-density parity check (LDPC) codes which can be utilized on memoryless or intersymbol interference channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where, at each stage, the original channel messages on select symbol,nodes are replaced by saturated messages. The key element of the proposed method is the symbol selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared to the standard locally-operating BP decoder) for short LDPC codes decoded on both memoryless and intersymbol interference Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.

关键词： belief propagation (BP) decoding error floors low-density parity check (LDPC) codes pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：