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

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

来源：评论

学校读者我要写书评

暂无评论

A Cutting-Plane Method Based on Redundant Rows for Improving Fractional Distance

引用

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

作者： Miwa, Makoto Wadayama, Tadashi Takumi, Ichi Nagoya Inst Technol Grad Sch Engn Showa Ku Nagoya Aichi 4668555 Japan

decoding performance of linear programming (LP) decoding is closely related to geometrical properties of a fundamental polytope: fractional distance, pseudo codeword, etc. In this paper, an idea of the cutting-plane method is employed to improve the fractional distance of a given binary parity-check matrix. The fractional distance is the minimum weight (with respect to l(1)-distance) of nonzero vertices of the fundamental polytope. The cutting polytope is defined based on redundant rows of the parity-check matrix. The redundant rows are codewords of the dual code not yet appearing as rows in the parity-check matrix. The cutting polytope plays a key role to eliminate unnecessary fractional vertices in the fundamental polytope. We propose a greedy algorithm and its efficient implementation based on the cutting-plane method. It has been confirmed that the fractional distance of some parity-check matrices are actually improved by using the algorithm.

关键词： linear codes Golay codes linear programming decoding Fractional distance

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Minimum-Polytope-Based linear programming Decoder for LDPC Codes via ADMM Approach

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2019年第4期8卷 1032-1035页

作者： Bai, Jing Wang, Yongchao Lau, Francis C. M. Xidian Univ Collaborat Innovat Ctr Informat Sensing & Underst Sch Telecommun Engn State Key Lab Integrated Serv Networks Xian 710071 Shaanxi Peoples R China Hong Kong Polytech Univ Dept Elect & Informat Engn Hong Kong Peoples R China

In this letter, we develop an efficient linear programming (LP) decoding algorithm for low-density parity-check (LDPC) codes. The LP relaxation is formulated based on a check-node decomposition approach. Our main contributions are as follows. First, we propose an algorithm based on the alternating direction method of multipliers (ADMM) technique to solve this LP relaxation. By exploiting the orthogonality structure of the LP model, each ADMM update step can be implemented in parallel. Second, the proposed decoding algorithm under this LP formulation eliminates the Euclidean projection on the check polytope compared with the existing ADMM-based LP decoding algorithms. Third, the feasibility analysis of the proposed algorithm is presented. Moveover, complexity analysis shows that our proposed LP decoder in each iteration has a lower complexity than the state-of-the-art ADMM-based LP decoders. Simulation results demonstrate that the proposed LP decoder achieves better performance than other competing ADMM-based LP decoders in terms of decoding time.

关键词： linear programming decoding alternating direction method of multipliers (ADMM) minimum polytope

来源：评论

学校读者我要写书评

暂无评论

Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第9期59卷 6018-6048页

作者： Vontobel, Pascal O. Hewlett Packard Labs Palo Alto CA 94304 USA

We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help toward a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.

关键词： Bethe approximation Bethe entropy Bethe partition function graph cover graph-cover decoding linear programming decoding message-passing algorithm method of types pseudomarginal vector sum-product algorithm (SPA)

来源：评论

学校读者我要写书评

暂无评论

Analysis of Connections Between Pseudocodewords

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第9期55卷 4099-4107页

作者： Axvig, Nathan Dreher, Deanna Morrison, Katherine Psota, Eric Perez, Lance C. Walker, Judy L. Univ Nebraska Dept Math Lincoln NE 68588 USA Univ Nebraska Dept Elect Engn Lincoln NE 68588 USA

The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature-linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords-are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.

关键词： Graph cover decoding iterative message-passing decoding linear programming decoding low-density parity-check (LDPC) codes pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

LOCAL-OPTIMALITY GUARANTEES BASED ON PATHS FOR OPTIMAL decoding

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第4期27卷 2049-2063页

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

This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length h. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability of LP decoding for binary Tanner codes. When the local codes are restricted to single parity-check codes, these bounds also hold for decoding by a certain iterative message-passing decoding algorithm.

关键词： coding theory Tanner codes local optimality maximum likelihood linear programming decoding error probability iterative message-passing decoding repeat-accumulate codes

来源：评论

学校读者我要写书评

暂无评论

LP/SDP Hierarchy Lower Bounds for decoding Random LDPC Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第6期64卷 4423-4437页

作者： Ghazi, Badih Lee, Euiwoong MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Carnegie Mellon Univ Comp Sci Dept Pittsburgh PA 15213 USA Microsoft Res New England Cambridge MA 02142 USA

Random (d(v), d(c))-regular low-density paritycheck (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the binary symmetric channel, for sufficiently large dv and dc, under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the linear programming (LP) decoding algorithm of Feldman et al., which is known to correct an Omega(1/d(c)) fraction of errors. In this paper, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) for any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/d(c)) fraction of errors on a random (dv, dc)-regular LDPC code;and 2) for any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv, dc)-regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Our (algebraic) construction for the Lasserre hierarchy is based on designing sets of points in F-q(d) (for q any power of 2 and d = 2, 3) with special hyperplane-incidence properties-constructions that may be of independent interest. An intriguing consequence of our work is that expansion seems to be both the strength and the weakness of random regular LDPC codes. S

关键词： Random LDPC codes linear programming decoding convex relaxations Sherali-Adams hierarchy Lasserre hierarchy graph expansion

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：