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

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

来源：评论

学校读者我要写书评

暂无评论

Lifting the Fundamental Cone and Enumerating the pseudocodewords of a Parity-Check Code

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 898-909页

作者： Kositwattanarerk, Wittawat Matthews, Gretchen L. Clemson Univ Dept Math Sci Clemson SC 29634 USA

The performance of message-passing iterative decoding and linear programming decoding depends on the Tanner graph representation of the code. If the underlying graph contains cycles, then such algorithms could produce a noncodeword output. The study of pseudocodewords aims to explain this noncodeword output. We examine the structure of the pseudocodewords and show that there is a one-to-one correspondence between graph cover pseudocodewords and integer points in a lifted fundamental cone. This gives a simple proof that the generating function of the pseudocodewords for a general parity-check code is rational (a fact first proved by Li, Lu, and Wang (Lecture Notes in Computer Science, vol. 5557, 2009) via other methods). Our approach yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Specifically, Barvinok's algorithm and the Barvinok-Woods projection algorithm are applied, and irreducible pseudocodewords are found via a Hilbert basis for the lifted fundamental cone.

关键词： Fundamental cone irreducible pseudocodewords iterative decoding linear programming (LP) decoding low-density parity-check (LDPC) code pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

CCS: It's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions

引用

ACTA INFORMATICA 2015年第2-3期52卷 175-205页

作者： van Glabbeek, Rob J. Hoefner, Peter NICTA Sydney NSW Australia UNSW Sydney NSW Australia

In the process algebra community it is sometimes suggested that, on some level of abstraction, any distributed system can be modelled in standard process-algebraic specification formalisms like CCS. This sentiment is strengthened by results testifying that CCS, like many similar formalisms, is Turing powerful and provides a mechanism for interaction. This paper counters that sentiment by presenting a simple fair scheduler-one that in suitable variations occurs in many distributed systems-of which no implementation can be expressed in CCS, unless CCS is enriched with a fairness assumption. Since Dekker's and Peterson's mutual exclusion protocols implement fair schedulers, it follows that these protocols cannot be rendered correctly in CCS without imposing a fairness assumption. Peterson expressed this algorithm correctly in pseudocode without resorting to a fairness assumption, so it furthermore follows that CCS lacks the expressive power to accurately capture such pseudocode.

关键词： CONSTRAINT programming (Computer science) FORMAL sociology SOCIAL interaction ABSTRACT thought SOCIAL isolation pseudocodewords

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the Pseudocodeword Redundancy of Binary Linear Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第7期58卷 4848-4861页

作者： Zumbraegel, Jens Skachek, Vitaly Flanagan, Mark F. Univ Coll Dublin Claude Shannon Inst Dublin 4 Ireland McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 2A7 Canada

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

关键词： Fundamental cone low-density parity-check codes pseudocodeword redundancy pseudocodewords pseudoweight

来源：评论

学校读者我要写书评

暂无评论

Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2012年第10期58卷 6581-6594页

作者： Zhang, Xiaojie Siegel, Paul H. Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Univ Calif San Diego Ctr Magnet Recording Res La Jolla CA 92093 USA

Linear programming (LP) decoding approximates 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 box constraints together with a set of linear inequalities called "parity inequalities" that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or "cut," at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding.

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

来源：评论

学校读者我要写书评

暂无评论

Minimum pseudoweight and minimum pseudocodewords of LDPC codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第1期54卷 480-485页

作者： Xia, Shu-Tao Fu, Fang-Wei Tsing Hua Univ Grad Sch Shenzen Shenzhen 518055 Guangdong Peoples R China SE Univ Natl Mobile Commun Guangdong Nanjing 210096 Peoples R China Nankai Univ Chern Inst Math Tianjin 300071 Peoples R China Nankai Univ Key Lab Pure Math & Combinator Tianjin 300071 Peoples R China

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than 4 is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth 4, and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches 1 as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

关键词： fundamental cone linear programming (LP) decoding low-density parity-check (LDPC) codes pseudocodewords pseudoweight stopping sets

来源：评论

学校读者我要写书评

暂无评论

Pseudocodeword Weights for LDPC Codes under Differential PSK Transmission over the Noncoherent AWGN Channel

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2011年第5期59卷 1218-1223页

作者： Mo, Elisa Armand, Marc A. Natl Univ Singapore Dept Elect & Comp Engn Singapore Singapore

This Letter considers the finite-length analysis of iterative decoding of low-density parity-check codes under differential binary-phase-shift-keying (DBPSK) and differential quadrature-phase-shift-keying (DQPSK) over the noncoherent additive-white-Gaussian-noise channel. Specifically, we derive the weight of the pseudocodewords of a Tanner graph under these signaling schemes and use them to explain the difference in error performance between coded DBPSK and coded DQPSK.

关键词： Belief-propagation decoding differential phase-shift-keying graph-cover decoding iterative decoding pseudocodewords spectral thinning

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：