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

Pseudocodeword Performance Analysis for LDPC Convolutional Codes

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第6期55卷 2577-2598页

作者： Smarandache, Roxana Pusane, Ali E. Vontobel, Pascal O. Costello, Daniel J., Jr. San Diego State Univ Dept Math & Stat San Diego CA 92182 USA Univ Notre Dame Dept Elect Engn Notre Dame IN 46556 USA Hewlett Packard Labs Palo Alto CA 94304 USA

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound. In this paper, we address the pseudocodeword problem from the convolutional code perspective. In particular, we compare We performance of LDPC convolutional codes with that of their "wrapped" quasi-cyclic block versions and we show that the minimum pseudoweight of an LDPC convolutional code is at least as large as the minimum pseudoweight of an underlying quasi-cyclic code. This result, which parallels a well-known relationship between the minimum Hamming weight of convolutional codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due to the fact that every pseudocodeword in the convolutional code induces a pseudocodeword in the block code with pseudoweight no larger than that of the convolutional code's pseudocodeword. This difference in the weight spectra leads to improved performance at low-to-moderate SNRs for the convolutional code, a conclusion supported by simulation results.

关键词： Convolutional codes linear programming decoding low-density parity-check (LDPC) codes message-passing iterative decoding pseudocodewords pseudoweights quasi-cyclic codes

来源：评论

学校读者我要写书评

暂无评论

Minimum Pseudoweight Analysis of 3-Dimensional Turbo Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2014年第7期62卷 2170-2182页

作者： Rosnes, Eirik Helmling, Michael Graell i Amat, Alexandre Ceragon Networks AS N-5257 Kokstad Norway Simula Res Lab N-1325 Lysaker Norway Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany Chalmers Dept Signals & Syst S-41296 Gothenburg Sweden

In this paper, we consider pseudocodewords of (relaxed) linear programming (LP) decoding of 3-dimensional turbo codes (3D-TCs). We present a relaxed LP decoder for 3D-TCs, adapting the relaxed LP decoder for conventional turbo codes proposed by Feldman in his thesis. We show that the 3D-TC polytope is proper and C-symmetric and make a connection to finite graph covers of the 3D-TC factor graph. This connection is used to 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 compute ensemble-average pseudoweight enumerators of 3D-TCs and perform a finite-length minimum pseudoweight analysis for small cover degrees. Moreover, an explicit description of the fundamental cone of the 3D-TC polytope is given. Finally, we present an extensive numerical study of small-to-medium block length 3D-TCs, which shows that 1) typically (i.e., in most cases), when the minimum distance d(min) and/or the stopping distance h(min) is high, the minimum pseudoweight (on the additive white Gaussian noise channel) is strictly smaller than both d(min) and h(min) and that 2) the minimum pseudoweight grows with the block length, at least for small-to-medium block lengths.

关键词： Three-dimensional (3D) turbo codes graph cover hybrid concatenated codes linear programming (LP) decoding QPP interleavers pseudocodewords pseudoweight turbo codes uniform interleaver

来源：评论

学校读者我要写书评

暂无评论

Guessing Facets: Polytope Structure and Improved LP Decoder

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第8期55卷 3479-3487页

作者： Dimakis, Alexandros G. Gohari, Amin A. Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

We investigate the structure of the polytope underlying the linear programming (LP) decoder introduced by Feldman, Karger, and Wainwright. We first show that for expander codes, every fractional pseudocodeword always has at least a constant fraction of nonintegral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than that of any codeword. We further exploit these geometrical properties to devise an improved decoding algorithm with the same order of complexity as LP decoding that provably performs better. The method is very simple: it first applies ordinary LP decoding, and when it fails, it proceeds by guessing facets of the polytope, and then resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that the proposed algorithm, when applied to suitable expander codes, succeeds unless there exists a certain number of pseudocodewords, all adjacent to the ML codeword on the LP decoding polytope, and with higher likelihood than the ML codeword. We then describe an extended algorithm, still with polynomial complexity, that succeeds as long as there are at most polynomially many pseudocodewords above the ML codeword.

关键词： Belief propagation bit guessing decimation error-correcting codes iterative decoding linear programming (LP) low-density parity-check (LDPC) codes linear programming (LP) decoding pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Tree-based construction of LDPC codes having. good pseudocodeword weights

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2007年第4期53卷 1460-1478页

作者： Kelley, Christine A. Sridhara, Deepak Rosenthal, Joachim Univ Notre Dame Dept Math Notre Dame IN 46556 USA Fields Inst Toronto ON Canada Univ Zurich Inst Math CH-8057 Zurich Switzerland

We present a tree-based construction of low-density parity-check (LDPC) codes that have minimum pseudocodeword weight equal to or almost equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a d-regular tree for a fixed number of layers and employing a connection algorithm based on permutations or mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d = p(s) and d = p(s) + 1, for p a prime. One class corresponds to the well-known finite-geometry and finite generalized quadrangle LDPC codes;the other codes presented are new. We also present some bounds on pseudocodeword weight for p-ary LDPC codes. Treating these codes as p-ary LDPC codes rather than binary LDPC codes improves their rates, minimum distances, and pseudocodeword weights, thereby giving a new importance to the finite-geometry LDPC codes where p > 2.

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

来源：评论

学校读者我要写书评

暂无评论

Using linear programming to decode binary linear codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第3期51卷 954-972页

作者： Feldman, J Wainwright, MJ Karger, DR Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA MIT CSAIL Cambridge MA 02139 USA

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d(frac) of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to [d(frac)/2] - 1 errors and that there are codes with d(frac) = Omega(n(1-epsilon)). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.

关键词： belief propagation (BP) iterative decoding low-density parity-check (LDPC) codes linear codes linear programming (LP) LP decoding minimum distance pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient Linear Programming Decoding of HDPC Codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2011年第3期59卷 758-766页

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

We propose several improvements for Linear Programming (LP) decoding algorithms for High Density Parity Check (HDPC) codes. First, we use the automorphism groups of a code to create parity check matrix diversity and to generate valid cuts from redundant parity checks. Second, we propose an efficient mixed integer decoder utilizing the branch and bound method. We further enhance the proposed decoders by removing inactive constraints and by adapting the parity check matrix prior to decoding according to the channel observations. Based on simulation results the proposed decoders achieve near-ML performance with reasonable complexity.

关键词： Adaptive LP decoding automorphism groups BCH codes belief propagation branch and bound linear programming LP relaxation pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

Deriving Good LDPC Convolutional Codes from LDPC Block Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 835-857页

作者： Pusane, Ali E. Smarandache, Roxana Vontobel, Pascal O. Costello, Daniel J., Jr. Univ Notre Dame Dept Elect Engn Notre Dame IN 46556 USA San Diego State Univ Dept Math & Stat San Diego CA 92182 USA Hewlett Packard Labs Palo Alto CA 94304 USA

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-varying LDPC convolutional codes from LDPC block codes and show how earlier proposed LDPC convolutional code constructions can be presented within this framework. Some of the constructed convolutional codes significantly outperform the underlying LDPC block codes. We investigate some possible reasons for this "convolutional gain," and we also discuss the-mostly moderate-decoder cost increase that is incurred by going from LDPC block to LDPC convolutional codes.

关键词： Block codes convolutional codes low-density parity-check (LDPC) codes message-passing iterative decoding pseudocodewords pseudoweights quasi-cyclic codes unwrapping wrapping

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：