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

38th Symposium on Information Theory and its Applications (SITA)

作者： Horii, Shunsuke Matsushima, Toshiyasu Hirasawa, Shigeichi Waseda Univ Tokyo 1698050 Japan

In this study, we develop a new algorithm for decoding binary linear codes for symbol-pair read channels. The symbol-pair read channel was recently introduced by Cassuto and Blaum to model channels with higher write resolutions than read resolutions. The proposed decoding algorithm is based on linear programming (LP). For LDPC codes, the proposed algorithm runs in time polynomial in the codeword length. It is proved that the proposed LP decoder has the maximum-likelihood (ML) certificate property, i.e., the output of the decoder is guaranteed to be the ML codeword when it is integral. We also introduce the fractional pair distance d(fp) of the code, which is a lower bound on the minimum pair distance. It is proved that the proposed LP decoder corrects up to. inverted left perpendiculard(fp)/2inverted right perpendicular - 1 errors.

关键词： symbol-pair read channel low-density parity-check codes linear programming decoding fractional distance

来源：评论

学校读者我要写书评

暂无评论

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

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第11期57卷 7386-7402页

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

We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Reduced-Complexity linear programming decoding Based on ADMM for LDPC Codes

引用

IEEE COMMUNICATIONS LETTERS 2015年第6期19卷 909-912页

作者： Wei, Haoyuan Jiao, Xiaopeng Mu, Jianjun Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China

The Euclidean projection onto check polytopes is the most time-consuming operation in the linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes. In this letter, instead of reducing the complexity of Euclidean projection itself, we propose a new method to reduce the decoding complexity of ADMM-based LP decoder by decreasing the number of Euclidean projections. In particular, if all absolute values of the element-wise differences between the input vector of Euclidean projection in the current iteration and that in the previous iteration are less than a predefined value, then the Euclidean projection at the current iteration will be no longer performed. Simulation results show that the proposed decoder can still save roughly 20% decoding time even if both the over-relaxation and early termination techniques are used.

关键词： linear programming decoding alternating direction method of multipliers (ADMM) reduce-complexity

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

HARDWARE-BASED linear programming decoding VIA THE ALTERNATING DIRECTION METHOD OF MULTIPLIERS

HARDWARE-BASED LINEAR PROGRAMMING DECODING VIA THE ALTERNATI...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Wasson, Mitchell Milicevic, Mario Draper, Stark C. Gulak, Glenn Univ Toronto Edward S Rogers Sr Dept Elect & Comp Engn Toronto ON Canada

ISBN: (纸本)9781509041176

We detail a field-programmable gate array (FPGA) based implementation of linear programming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief propagation (BP) that view error correction as a problem of graphical inference. LP decoding, when implemented with standard LP solvers, does not easily scale to the block-lengths of modern error-correction codes. This is the main challenge we surmount in this paper. In earlier work we demonstrated how to draw on decomposition methods from optimization theory to build an LP decoding solver competitive with BP, in terms of both performance and speed, but only in double-precision floating point. In this paper we translate the novel computational primitives of our new LP decoding technique into fixed-point. Using our FPGA implementation, we demonstrate that error-rate performance very close to double-precision is possible with 10-bit fixed-point messages.

关键词： linear programming decoding alternating direction method of multipliers field-programmable gate arrays low-density parity-check codes lowering error floors

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：