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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved linear programming decoding and Bounds on the Minimum Distance of LDPC Codes

Improved Linear Programming Decoding and Bounds on the Minim...

引用

IEEE Information Theory Workshop (ITW)

作者： Burshtein, David Goldenberg, Idan Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

ISBN: (纸本)9781424482641

We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.

关键词： linear programming decoding iterative decoding maximum likelihood (ML) decoding low-density parity-check (LDPC) codes

来源：评论

学校读者我要写书评

暂无评论

Iterative Approximate linear programming decoding of LDPC Codes With linear Complexity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第11期55卷 4835-4859页

作者： Burshtein, David Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Ramat Aviv Israel

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.

关键词： linear programming decoding iterative decoding low-density parity-check (LDPC) codes

来源：评论

学校读者我要写书评

暂无评论

On the Pairwise Error Probability of linear programming decoding on Independent Rayleigh Flat-Fading Channels

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2009年第7期55卷 2942-2955页

作者： Rosnes, Eirik Univ Bergen Dept Informat N-5020 Bergen Norway

In this paper, we consider the pairwise error probability (PEP) of a linear programming (LP) decoder for a general binary linear code as formulated by Feldman et al. (IEEE Traits. Inf. Theory, Mar. 2005) on an independent (or memoryless) Rayleigh flat-fading channel with coherent detection and perfect channel state information (CSI) at the receiver. Let H be a parity- check matrix of a binary linear code and consider LP decoding based on H. The output of the LP decoder is always a pseuocodeword. We will show that the PEP of decoding to a pseudocodeword omega when the all-zero codeword is transmitted on the above-mentioned channel, behaves asymptotically as K(w) . (E-s/N-0) -(vertical bar chi(omega)vertical bar), where chi(omega) is the support set of omega, i.e., the set of nonzero coordinates, E-s/N-0 is the average signal-to-noise ratio (SNR), and K (omega) is a constant independent of the SNR. Note that the support set chi(omega) of w is a stopping set. Thus, the asymptotic decay rate of the error probability with the average SNR is determined by the size of the smallest nonempty stopping set in the Tanner graph of H. As an example, we analyze the well-known (155, 64) Tanner code and present performance curves on the independent Rayleigh flat-fading channel.

关键词： linear programming decoding low-density parity-check (LDPC) codes pairwise error probability pseudocodeword Rayleigh flat-fading channel stopping set union bound

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：