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

An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第4期54卷 1514-1520页

作者： Chertkov, Michael Stepanov, Mikhail G. Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA Univ Arizona Dept Math Tucson AZ 85721 USA

In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristically create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each'step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a psendocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.

关键词： error-floor linear programming decoding lowdensity parity-check (LDPC) codes

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of linear programming decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第8期54卷 3565-3578页

作者： Daskalakis, Constantinos Dimakis, Alexandros G. Karp, Richard M. Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94704 USA

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous nonasymptotic results for LDPC codes, and in particular, exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on the Tanner graph of the code. An interesting by-product of our analysis is to establish the existence of "probabilistic expansion" in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst case setting.

关键词： binary-symmetric channel (BSC) channel coding error-control coding expanders factor graphs linear programming decoding low-density parity-check (LDPC) codes randomized algorithms sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

On the analysis of spatially-coupled GLDPC codes and the weighted min-sum algorithm

On the analysis of spatially-coupled GLDPC codes and the wei...

引用

作者： Jian, Yung-Yih Texas A&M University

学位级别：Ph.D.

This dissertation studies methods to achieve reliable communication over unreliable channels. Iterative decoding algorithms for low-density parity-check (LDPC) codes and generalized LDPC (GLDPC) codes are analyzed. A new class of error-correcting codes to enhance the reliability of the communication for high-speed systems, such as optical communication systems, is proposed. The class of spatially-coupled GLDPC codes is studied, and a new iterative hard- decision decoding (HDD) algorithm for GLDPC codes is introduced. The main result is that the minimal redundancy allowed by Shannon’s Channel Coding Theorem can be achieved by using the new iterative HDD algorithm with spatially-coupled GLDPC codes. A variety of low-density parity-check (LDPC) ensembles have now been observed to approach capacity with iterative decoding. However, all of them use soft (i.e., non-binary) messages and a posteriori probability (APP) decoding of their component codes. To the best of our knowledge, this is the first system that can approach the channel capacity using iterative HDD. The optimality of a codeword returned by the weighted min-sum (WMS) algorithm, an iterative decoding algorithm which is widely used in practice, is studied as well. The attenuated max-product (AttMP) decoding and weighted min-sum (WMS) decoding for LDPC codes are analyzed. Applying the max-product (and belief-propagation) algorithms to loopy graphs are now quite popular for best assignment problems. This is largely due to their low computational complexity and impressive performance in practice. Still, there is no general understanding of the conditions required for convergence and/or the optimality of converged solutions. This work presents an analysis of both AttMP decoding and WMS decoding for LDPC codes which guarantees convergence to a fixed point when a weight factor, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both a linear-program

关键词： LDPC codes GLDPC codes density evolution product codes spatial coupling iterative hard-decision decoding belief propagation max-product algorithm min-sum algorithm linear programming decoding Thesis

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of linear programming decoding 18

Probabilistic analysis of linear programming decoding

引用

18th ACM-SIAM Symposium on Discrete Algorithms

作者： Daskalakis, Constantinos Dimakis, Alexandros G. Karp, Richard M. Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94704 USA

ISBN: (纸本)9780898716245

来源：评论

学校读者我要写书评

暂无评论

LDPC Codes for Compressed Sensing

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第5期58卷 3093-3114页

作者： Dimakis, Alexandros G. Smarandache, Roxana Vontobel, Pascal O. Univ So Calif Dept Elect Engn Syst Viterbi Sch Engn Los Angeles CA 90089 USA San Diego State Univ Dept Math & Stat San Diego CA 92182 USA Hewlett Packard Labs Palo Alto CA 94304 USA

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, channel coding linear programming decoding (CC-LPD), which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, compressed sensing linear programming decoding (CS-LPD), also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an underdetermined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of "good" channel codes can be used as provably "good" measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check codes constructed by Gallager.

关键词： Approximation guarantee basis pursuit channel coding compressed sensing graph cover linear programming decoding pseudocodeword pseudoweight sparse approximation zero-infinity operator

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An Efficient Instanton Search Algorithm for LP decoding of LDPC Codes Over the BSC

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第7期57卷 4417-4426页

作者： Chilappagari, Shashi Kiran Chertkov, Michael Vasic, Bane Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA Los Alamos Natl Lab LANL Complex Syst Grp Div Theory Los Alamos NM 87545 USA Los Alamos Natl Lab LANL Complex Syst Grp CNLS Los Alamos NM 87545 USA

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton;(b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.

关键词： Binary symmetric channel (BSC) error-floor linear programming decoding low-density parity-check (LDPC) codes pseudo-codewords

来源：评论

学校读者我要写书评

暂无评论

Ensemble Analysis of Pseudocodewords of Protograph-Based Non-Binary LDPC Codes

Ensemble Analysis of Pseudocodewords of Protograph-Based Non...

引用

IEEE Information Theory Workshop (ITW)

作者： Divsalar, Dariush Dolecek, Lara CALTECH Jet Prop Lab 4800 Oak Grove Dr Pasadena CA 91109 USA Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA

ISBN: (纸本)9781457704376

This paper presents a method for evaluating pseudocodeword weight enumerators of nonbinary LDPC codes built out of protographs. The ensemble enumerators are evaluated for both the finite-length and infinite-length regimes. Results of this type can be particularly useful for designing structured nonbinary LDPC codes with good properties under message passing or linear programming decoding.

关键词： Conferences Iterative decoding linear code Niobium Vectors binary codes decoding ensemble enumerator finite-length regime infinite-length regime linear codes linear programming linear programming decoding message passing decoding parity check codes protog

来源：评论

学校读者我要写书评

暂无评论

LP decoding of Regular LDPC Codes in Memoryless Channels

LP Decoding of Regular LDPC Codes in Memoryless Channels

引用

IEEE International Symposium on Information Theory

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

ISBN: (纸本)9781424469604

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：