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

IEEE International Symposium on Information Theory (ISIT)

作者： Zhang, Xiaojie Siegel, Paul H. Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (纸本)9781457705953

linear programming (LP) decoding approximates optimal maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of linear inequalities derived from the constraints represented by the rows of a parity-check matrix of the code. Adaptive linear programming (ALP) decoding significantly reduces the complexity of LP decoding by iteratively and adaptively adding necessary constraints in a sequence of smaller LP problems. Adaptive introduction of constraints derived from certain additional redundant parity check (RPC) constraints can further improve ALP performance. In this paper, we propose a new and effective algorithm to identify RPCs that produce linear constraints, referred to as "cuts," that can eliminate non-ML solutions generated by the ALP decoder, often significantly improving the decoder error-rate performance. The cut-finding algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. Simulation results for several low-density parity-check codes demonstrate that the modified ALP decoding algorithm significantly narrows the performance gap between LP decoding and ML decoding.

关键词： ALP decoding Iterative decoding LP decoding linear code linear matrix inequalities linear programming Maximum likelihood decoding RPC constraint adaptive codes adaptive cut generation adaptive linear programming decoding binary linear code block codes cut-finding algorithm decoder error-rate performance equivalent ML IP problem equivalent ML integer programming problem integer programming iterative decoding linear block code linear codes linear inequality linear programming linear programming decoding low-density parity-check matrix code maximum likelihood decoding optimal ML decoding optimal maximum-likelihood decoding parity check codes redundant parity check constraint

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Hardware-based linear programming decoding via the alternating direction method of multipliers

Hardware-based linear programming decoding via the alternati...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Mitchell Wasson Mario Milicevic Stark C. Draper Glenn Gulak University of Toronto Edward S. Rogers Sr. Department of Electrical and Computer Engineering Canada

ISBN: (纸本)9781509041183

We detail a field-programmable gate array (FPGA) based implementation of linear programming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief propagation (BP) that view error correction as a problem of graphical inference. LP decoding, when implemented with standard LP solvers, does not easily scale to the block-lengths of modern error-correction codes. This is the main challenge we surmount in this paper. In earlier work we demonstrated how to draw on decomposition methods from optimization theory to build an LP decoding solver competitive with BP, in terms of both performance and speed, but only in double-precision floating point. In this paper we translate the novel computational primitives of our new LP decoding technique into fixed-point. Using our FPGA implementation, we demonstrate that error-rate performance very close to double-precision is possible with 10-bit fixed-point messages.

关键词： linear programming decoding alternating direction method of multipliers field-programmable gate arrays low-density parity-check codes lowering error floors

来源：评论

学校读者我要写书评

暂无评论

Polytope of Correct (linear programming) decoding and Low-Weight Pseudo-Codewords

Polytope of Correct (Linear Programming) Decoding and Low-We...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Chertkov, Michael Stepanov, Mikhail LANL CNLS Los Alamos NM 87545 USA Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany

ISBN: (纸本)9781457705953

We analyze linear programming (LP) decoding of graphical binary codes operating over soft-output, symmetric and log-concave channels. We show that the error-surface, separating domain of the correct decoding from domain of the erroneous decoding, is a polytope. We formulate the problem of finding the lowest-weight pseudo-codeword as a non-convex optimization (maximization of a convex function) over a polytope, with the cost function defined by the channel and the polytope defined by the structure of the code. This formulation suggests new provably convergent heuristics for finding the lowest weight pseudo-codewords improving in quality upon previously discussed. The algorithm performance is tested on the example of the Tanner [155,64,20] code over the Additive White Gaussian Noise (AWGN) channel.

关键词： AWGN channel AWGN channels AWGN channels Convex functions decoding LP decoding Minimization Noise Optimization Parity check codes additive white gaussian noise channel binary codes channel coding concave programming convergent heuristic correct decoding cost function decoding erroneous decoding error correction codes error-surface separating domain graphical binary code linear programming linear programming decoding log-concave channel lowest-weight pseudo-codeword nonconvex optimization polytope soft-output channel symmetric channel

来源：评论

学校读者我要写书评

暂无评论

Pseudo-codeword analysis of tanner graphs from projective and euclidean planes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第7期53卷 2376-2393页

作者： Smarandache, Roxana Vontobel, Pascal O. San Diego State Univ Dept Math & Stat San Diego CA 92182 USA Univ Wisconsin Dept Elect & Comp Engn Madison WI 53706 USA MIT Dept Elect & Comp Engn Cambridge MA 02139 USA Hewlett Packard Labs Palo Alto CA USA

We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (NIL) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.

关键词： codes from Euclidean planes codes from projective planes linear programming decoding message-passing iterative decoding minimal codewords minimal pseudo-codewords pseudo-weight pseudo-weight spectra

来源：评论

学校读者我要写书评

暂无评论

LP decoding of Regular LDPC Codes in Memoryless Channels

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 887-897页

作者： Halabi, Nissim Even, Guy Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

We study error bounds for linear programming decoding of regular low-density parity-check (LDPC) codes. For memoryless binary-input output-symmetric channels, we prove bounds on the word error probability that are inverse doubly exponential in the girth of the factor graph. For memoryless binary-input AWGN channel, we prove lower bounds on the threshold for regular LDPC codes whose factor graphs have logarithmic girth under LP-decoding. Specifically, we prove a lower bound of sigma = 0.735 (upper bound of Eb/N-0 = 2.67 dB) on the threshold of (3, 6)-regular LDPC codes whose factor graphs have logarithmic girth. Our proof is an extension of a recent paper of Arora, Daskalakis, and Steurer [STOC 2009] who presented a novel probabilistic analysis of LP decoding over a binary symmetric channel. Their analysis is based on the primal LP representation and has an explicit connection to message passing algorithms. We extend this analysis to any MBIOS channel.

关键词： Additive white Gaussian noise (AWGN) channel channel coding error bounds factor graphs low-density parity-check (LDPC) codes linear programming decoding memoryless binary-input output-symmetric (MBIOS) channel thresholds

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Lowering the Error Floor of ADMM Penalized Decoder for LDPC Codes

引用

China Communications 2016年第8期13卷 127-135页

作者： Jiao Xiaopeng Mu Jianjun School of Computer Science and Technology Xidian University Xi'an 710071 Shaanxi Province China Key Laboratory of Information Coding and Transmission Southwest Jiaotong University Chengdu 610031 China

decoding by alternating direction method of multipliers(ADMM) is a promising linear programming decoder for low-density parity-check(LDPC) codes. In this paper, we propose a two-step scheme to lower the error floor of LDPC codes with ADMM penalized *** the undetected errors that cannot be avoided at the decoder side, we modify the code structure slightly to eliminate low-weight code words. For the detected errors induced by small error-prone structures, we propose a post-processing method for the ADMM penalized decoder. Simulation results show that the error floor can be reduced significantly over three illustrated LDPC codes by the proposed two-step scheme.

关键词： LDPC codes linear programming decoding alternating direction method of multipliers(ADMM) error floor

来源：评论

学校读者我要写书评

暂无评论

Low-Complexity LP decoding of Nonbinary linear Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2013年第8期61卷 3073-3085页

作者： Punekar, Mayur Vontobel, Pascal O. Flanagan, Mark F. Texas A&M Univ Dept Elect & Comp Engn Doha Qatar Hewlett Packard Labs Palo Alto CA 94304 USA Univ Coll Dublin Sch Elect Elect & Commun Engn Dublin Ireland

linear programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z(4), GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.

关键词： linear programming decoding nonbinary codes LDPC codes coordinate-ascent algorithm subgradient algorithm

来源：评论

学校读者我要写书评

暂无评论

Analysis of Message-Passing decoding of Finite-Length Concatenated Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2011年第8期59卷 2090-2100页

作者： Yang, Kai Wang, Xiaodong Alcatel Lucent Bell Labs Murray Hill NJ 07974 USA Columbia Univ Dept Elect Engn New York NY 10027 USA

We analyze the performance of message-passing decoding of finite-length concatenated codes. We first show that the message-passing decoder is closely related to a dual optimization decoder. The connections between these two decoders are further elucidated by proving that both of them attain the same objective function value of a generalized linear programming decoder in the limit as the signal-to-noise ratio (SNR) goes to infinity. Consequently, the framework of pseudo-weight analysis, which was originally proposed for analyzing the linear programming decoder, can be extended to analyze the performance of the message-passing decoder for finite-length codes. We then derive lower bounds to the pseudo-weights of general concatenated codes by utilizing the special structure of their parity-check matrices. We finally present a method to increase the max-fractional weight by adding redundant parity-check constraints and thereby improving the decoding performance. Simulation studies are carried out to assess the performance of the proposed algorithms and substantiate the theoretic claims.

关键词： Pseudo-weight analysis linear block codes concatenated codes message-passing algorithm linear programming decoding max-fractional weight dual optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：