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

Characterizations of pseudo-codewords of (low-density) parity-check codes

ADVANCES IN MATHEMATICS 2007年第1期213卷 205-229页

作者： Koetter, Ralf Li, Wen-Ching W. Vontobel, Pascal O. Walker, Judy L. Univ Nebraska Dept Math Lincoln NE 68588 USA Tech Univ Munich Inst Commun Engn D-80333 Munich Germany Penn State Univ Dept Math University Pk PA 16802 USA Hewlett Packard Labs Palo Alto CA 94304 USA

An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph. (c) 2007 Elsevier Inc. All rights reserved.

关键词： (low-density) parity-check codes pseudo-codewords fundamental cone graph covers zeta functions Newton polyhedron

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Instanton-Based Techniques for Analysis and Reduction of Error Floors of LDPC Codes

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2009年第6期27卷 855-865页

作者： Chilappagari, Shashi Kiran Chertkov, Michael Stepanov, Mikhail G. Vasic, Bane Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA LANL Div Theory Los Alamos NM 87545 USA LANL CNLS Los Alamos NM 87545 USA Univ Arizona Dept Math Tucson AZ 85721 USA

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.

关键词： Low-density parity-check codes Error Floor Iterative Decoding Linear Programming Decoding Instantons pseudo-codewords Trapping Sets

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Non-Binary Protograph-Based LDPC Codes: Enumerators, Analysis, and Designs

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第7期60卷 3913-3941页

作者： Dolecek, Lara Divsalar, Dariush Sun, Yizeng Amiri, Behzad Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA CALTECH Jet Prop Lab Pasadena CA 91109 USA

This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.

关键词： LDPC codes nonbinary codes protographs weight enumerators asymptotic analysis pseudo-codewords trapping sets stopping sets iterative decoding thresholds EXIT chart analysis finite-length code design

来源：评论

学校读者我要写书评

暂无评论

On deriving good LDPC convolutional codes from QC LDPC block codes

On deriving good LDPC convolutional codes from QC LDPC block...

引用

IEEE International Symposium on Information Theory

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

ISBN: (纸本)9781424413973

In this paper we study the iterative decoding behavior of time-invariant and time-varying LDPC convolutional codes derived by unwrapping QC LDPC block codes. In particular, for a time-varying LDPC convolutional code, we show that the minimum pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying QC code. We also prove that the unwrapped convolutional codes have fewer short cycles than the QC codes. These results taken together lead to improved BER performance in the low-to-moderate SNR region, where the decoding behavior is influenced by the complete pseudo-codeword spectra and by the Tanner graph cycle histogram, with the time-varying convolutional codes outperforming both the underlying QC block codes and their time-invariant convolutional counterparts.

关键词： low-density parity-check codes convolutional codes pseudo-codewords cycles iterative decoding

来源：评论

学校读者我要写书评

暂无评论

Spectral Graph Analysis of Quasi-Cyclic Codes

Spectral Graph Analysis of Quasi-Cyclic Codes

引用

IEEE Global Telecommunications Conference (GLOBECOM 09)

作者： Smarandache, Roxana Flanagan, Mark F. San Diego State Univ Dept Math & Stat San Diego CA 92182 USA Univ Coll Dublin Dept Elect Engn Dublin Ireland

ISBN: (纸本)9781424441471

In this paper we analyze the bound on the additive white Gaussian noise channel (AWGNC) pseudo-weight of a (c, d)-regular linear block code based on the two largest values lambda(1) > lambda(2) of the eigenvalues of (HH)-H-T: w(p)(min)(H) >= n 2c-lambda(2)/lambda(1)-lambda(2.) [6]. In particular, we analyze (c, d)-regular quasi-cyclic (QC) codes of length rL described by J x L block parity-check matrices with circulant block entries of size r x r. We proceed by showing how the problem of computing the eigenvalues of the rL x rL matrix (HH)-H-T can be reduced to the problem of computing eigenvalues for r matrices of size L x L. We also give a necessary condition for the bound to be attained for a circulant matrix H and show a few classes of cyclic codes satisfying this criterion.

关键词： Low-density parity-check codes pseudo-codewords pseudo-weights eigenvalues eigenvectors

来源：评论

学校读者我要写书评

暂无评论

Low-density parity-check codes: Asymptotic behavior and zeta functions

Low-density parity-check codes: Asymptotic behavior and zeta...

引用

作者： Lu, Min The Pennsylvania State University

学位级别：Ph.D.

A LDPC code is binary linear code equipped with a sparse parity-check matrix. A bipartite graph, called Tanner graph, can be associated to a parity-check matrix. Then message passing iterative decoding (MPID) algorithms can be applied on the Tanner graph to do fast efficient decoding. Richardson and Urbanke proposed a scheme, called density evolution, to analyze the performance of MPID algorithms. Using density evolution we shall report new approaches to designing asymptotically good LDPC code ensembles over binary erasure channel (BEC). We then answer an open question raised by Shokrollahi and Oswald during their study on capacity-achieving sequences over BEC. Next, in order to understand MPID algorithms better we bring up the discussion of pseudo-codewords, which are regarded as the cause of decoding errors. We shall present two rational functions whose monomials in the Taylor expansion enumerate all the pseudo-codewords of a general binary parity-check code.

关键词： LDPC codes iterative decoding pseudo-codewords capacity-achieving sequences

来源：评论

学校读者我要写书评

暂无评论

Analysis of failures of decoders for LDPC codes

Analysis of failures of decoders for LDPC codes

引用

作者： Chilappagari, Shashi Kiran The University of Arizona

学位级别：Ph.D.

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown. An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC). For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability. We also propose an algorithm to identify the most probable noise conf

关键词： Error floor Gallager A algorithm Instantons LDPC codes pseudo-codewords Trapping sets

来源：评论

学校读者我要写书评

暂无评论

Low-Density Parity-Check Codes: Asymptotic Behavior and Zeta Functions

Low-Density Parity-Check Codes: Asymptotic Behavior and Zeta...

引用

作者： Lu, Min PennState University Libraries

学位级别：Doctor of Philosophy

关键词： LDPC codes iterative decoding pseudo-codewords capacity-achieving sequences

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：