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

Exploiting Parity-Polytope Geometry in Approximate and Randomized Scheduled ADMM-LP decoding

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第8期72卷 4551-4563页

作者： Asadzadeh, Amirreza Ho, Anthony Kschischang, Frank R. Draper, Stark C. Univ Toronto Edward S Rogers Sr Dept Elect & Comp Engn Toronto ON M5S 1A1 Canada

We present two strategies to reduce the complexity of the alternating direction method of multipliers when applied to linear programming (ADMM-LP) decoding of low-density parity-check codes. First, to address the high complexity of computing a projection onto the parity polytope, the complexity bottleneck of ADMM-LP decoding, we propose the sparse affine projection algorithm (SAPA). SAPA projects onto the affine hull of $\chi \leq d$ nearby local codewords where the check degree is d and where $\chi $ can be significantly smaller than d. Unlike exact projection, SAPA does not require a water-filling process, and thus can be implemented with lower per-iteration complexity. Second, to reduce the number of effective iterations needed for ADMM-LP decoding, we propose a randomized layered scheduling framework. Rather than updating checks in round-robin fashion in each iteration, more "problematic" checks have a higher probability of being updated. The probability mass function that governs the selection of which checks to update is based upon the location of replica vectors inside (or on) the parity polytope. The resultant decoder converges significantly faster under this randomized scheduling than under round-robin scheduling. This makes it well suited for use in applications that limit the number of iterations.

关键词： Iterative decoding decoding Schedules Complexity theory Vectors Approximation algorithms Symbols Low-density parity-check codes alternating direction method of multipliers linear-programming decoding parity polytope

来源：评论

学校读者我要写书评

暂无评论

A Note on the linear programming decoding of Binary linear Codes for Multiple-Access Channel

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2011年第6期E94A卷 1230-1237页

作者： Horii, Shunsuke Matsushima, Toshiyasu Hirasawa, Shigeichi Waseda Univ Dept Appl Math Tokyo 1698555 Japan Waseda Univ Waseda Res Inst Sci & Engn Tokyo 1698555 Japan Cyber Univ Fukuoka Japan

In this paper, we develop linear-programming (LP) decoding for multiple-access channels with binary linear codes. For single-user channels, LP decoding has attracted much attention in recent years as a good approximation to maximum-likelihood (ML) decoding. We demonstrate how the ML decoding problem for multiple-access channels with binary linear codes can be formulated as an LP problem. This is not straightforward, because the objective function of the problem is generally a non-linear function of the codeword symbols. We introduce auxiliary variables such that the objective function is a linear function of these variables. The ML decoding problem then reduces to the LP problem. As in the case for single-user channels, we formulate the relaxed LP problem to reduce the complexity for practical implementation, and as a result propose a decoder that has the desirable property known as the ML certificate property (i.e., if the decoder outputs an integer solution, the solution is guaranteed to be the ML codeword). Although the computational complexity of the proposed algorithm is exponential in the number of users, we can reduce this complexity for Gaussian multiple-access channels. Furthermore, we compare the performance of the proposed decoder with a decoder based on the sum-product algorithm.

关键词： multiple-access channel maximum likelihood decoding linear-programming decoding

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Correcting a Fraction of Errors in Nonbinary Expander Codes With linear programming

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第6期57卷 3698-3706页

作者： Skachek, Vitaly Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland Univ Coll Dublin Sch Math Sci Dublin 4 Ireland Nanyang Technol Univ Div Math Sci Sch Phys & Math Sci Singapore 637371 Singapore

A linear-programming decoder for nonbinary expander codes is presented. It is shown that the proposed decoder has the nearest-neighbor certificate properties. It is also shown that this decoder corrects any pattern of errors of a relative weight up to approximately 1/4 delta(A)delta(B) (where delta(A) and delta(B) are the relative minimum distances of the constituent codes).

关键词： Expander codes low-density parity-check (LDPC) codes linear-programming decoding nonbinary codes

来源：评论

学校读者我要写书评

暂无评论

On Minimal Pseudo-Codewords

On Minimal Pseudo-Codewords

引用

2010 IEEE International Symposium on Information Theory

作者： Smarandache, Roxana San Diego State Univ Dept Math & Stat San Diego CA 92182 USA

ISBN: (纸本)9781424469604

The performance of linear-programming decoding of a binary linear code described by a parity-check matrix depends on the set of pseudo-codewords associated to this matrix and in particular, on the set of minimal pseudo-codewords. This paper attempts to provide an algebraic characterization of the minimal pseudo-codewords. It also provides a connection between the fundamental cone of a Tanner graph and the fundamental cone of its Forney-style factor graph.

关键词： Fundamental cone linear-programming decoding low-density parity-check code pseudo-codewords

来源：评论

学校读者我要写书评

暂无评论

On LP decoding of Nonbinary Expander Codes

On LP Decoding of Nonbinary Expander Codes

引用

IEEE International Symposium on Information Theory (ISIT 2009)

作者： Skachek, Vitaly Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland

ISBN: (纸本)9781424443123

linear-programming (LP) decoder for nonbinary expander codes is presented. It is shown that the proposed decoder has the maximum-likelihood certificate properties. It is also shown that this decoder corrects any pattern of errors of a relative weight up to approximately 1/4 delta(A)delta (B) (where delta(A) and delta(B) are the relative minimum distances of the constituent codes).

关键词： Expander codes low-density parity-check codes linear-programming decoding nonbinary codes

来源：评论

学校读者我要写书评

暂无评论

A decomposition theory for binary linear codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第7期54卷 3035-3058页

作者： Kashyap, Navin Queens Univ Dept Math & Stat Kingston ON K7L 3N6 Canada

The decomposition theory of matroids initiated by Paul Seymour in the 1980s has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a binary-input discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Grotschel and Truemper from the combinatorial optimization literature to give examples of nontrivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes C for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code C-perpendicular to. However, we also show that such families of codes are not good in a coding-theoretic sense-either their dimension or their minimum distance must grow sublinearly with code length. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocodewords.

关键词： code decompositions linear codes linear-programming decoding matroids maximum-likelihood (ML) decoding pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds on the Minimum Pseudodistance for linear Codes with q-ary PSK Modulation over AWGN

Lower Bounds on the Minimum Pseudodistance for Linear Codes ...

引用

5th International Symposium on Turbo Codes and Related Topics

作者： Skachek, Vitaly Flanagan, Mark F. Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland Univ Bologna DEIS Cesena Italy

ISBN: (纸本)9781424428625

We present lower bounds on the minimum pseudocodeword effective Euclidean distance (or minimum "pseudodistance") for coded modulation systems using linear codes with q-ary phase-shift keying (PSK) modulation over the additive white Gaussian noise (AWGN) channel. These bounds apply to both binary and nonbinary coded modulation systems which use direct modulation mapping of coded symbols. The minimum pseudodistance may serve as a first-order measure of error-correcting performance for both linear-programming and message-passing based receivers. In the case of a linear-programming based receiver, the minimum pseudodistance may be used to form an exact bound on the codeword error rate of the system.

关键词： Iterative decoding linear-programming decoding factor graph graph cover pseudocodewords pseudodistance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：