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

ON THE PERFORMANCE AND COMPLEXITY OF A GENERALIZED MINIMUM DISTANCE REED-SOLOMON decoding ALGORITHM

INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS 1994年第4期12卷 333-359页

作者： PEILE, RE Racal Research Ltd Worton Grange Reading Berkshire RG2 OSB U.K.

The article reports on the characteristics of an algorithm that implements generalized minimum distance (GMD) decoding of Reed-Solomon codes. The algorithm uses the novel Welch-Berlekamp (WB) algorithm, as modified by Tze-Hua, in order to minimize the complexity of the decoder. Both the WB algorithm and the GMD extension of the WB algorithm are described in outline. The performance of the GMD algorithm was simulated on AWGN channels and fading channels. Results are presented both for RS and concatenated RS codes. The gains over conventional decoding are larger for fading channels than for AWGN conditions but seem useful in all cases. The complexities of the GMD algorithm and the WB algorithm are analysed and compared to that of conventional RS decoding algorithms.

关键词： ERROR CORRECTION REED-SOLOMON CODES CONCATENATED CODES REED-MULLER CODES decoding algorithms GENERALIZED MINIMUM DISTANCE decoding WELCH-BERLEKAMP ALGORITHM BERLEKAMP-MASSEY ALGORITHM

来源：评论

学校读者我要写书评

暂无评论

Improved decoding of Reed-Solomon and algebraic-geometry codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1999年第6期45卷 1757-1767页

作者： Guruswami, V Sudan, M MIT Comp Sci Lab Cambridge MA 02139 USA

Given an error-correcting code over strings of length n and an arbitrary input string also of length n, the List decoding problem is that of finding all codewords within a specified Ramming distance from the input string. me present an improved list decoding algorithm for decoding Reed-Solomon codes, The list decoding problem for Reed-Solomon codes reduces to the following "curve-fitting" problem over a field F: Given n points {(x(i).y(i))}(i=1)(n), x(i) ,y(i) is an element of F, and a degree parameter L and error parameter e, find all univariate polynomials p of degree at most I;such that y(i) = p(x(i)) for all but at most e values of i is an element of {1, ..., n}, We give an algorithm that solves this problem for e < n - root kn, which improves over the previous best result [27], for every choice of k and n, Of particular interest is the ease of k/n > 1/3, where the result yields the first asymptotic improvement in four decades [21], The algorithm generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes (a class of codes including BCH codes) and algebraic-geometry codes. In both cases, we obtain a list decoding algorithm that corrects up to n - root n(n - d') errors, where n is the block length and d' is the designed distance of the code. The improvement for the case of algebraic-geometry codes extends the methods of [24] and improves upon their bound for every choice of n and d'. We also present some other consequences of our algorithm including a solution to a weighted curve-fitting problem, which may be of use in soft-decision decoding algorithms for Reed-Solomon codes.

关键词： algebraic-geometry codes decoding algorithms error-correcting codes list decoding polynomial time algorithms Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Efficient VLSI architecture for interpolation decoding of Hermitian codes

引用

IET COMMUNICATIONS 2014年第5期8卷 671-679页

作者： Srivastava, Shraddha Lee, Kwankyu Popovici, Emanuel Univ Coll Cork Dept Elect & Elect Engn Cork Ireland Chosun Univ Dept Math & Educ Kwangju South Korea

A fast, area efficient very large scale integration (VLSI) architecture is proposed for a unique decoding algorithm of Hermitian codes which was presented recently by Lee and O'Sullivan from an interpolation perspective. The algorithm iteratively computes the sent message through a majority voting procedure by using the Grobner bases of interpolation modules. The algorithm has a regular structure which makes it suitable for VLSI implementation. The circuitry is simplified as the decoding algorithm directly gives the message word at the end of the decoding algorithm without separate steps like Chien search and Forney's formula. In terms of hardware requirements, for the widely used high rate Hermitian codes, the Lee-O'Sullivan algorithm is q times faster than Kotters algorithm with the same space complexity of O(q(4)). Further speed improvements can be achieved by combining the main idea of Guruswami list decoding with the Lee-O'Sullivan algorithm. In terms of hardware, the addition of this concept, will further reduce the running time of the algorithm and make the circuitry about two times faster than the original Lee-O'Sullivan algorithm. The implementation results for both the Koetter and the Lee-O'Sullivan algorithms on Xilinx Virtex-5 shows that the proposed decoder can be operated at higher clock frequency with almost same area complexity.

关键词： VERY large scale integration of circuits INTERPOLATION decoding algorithms BLOCK codes PLANE curves

来源：评论

学校读者我要写书评

暂无评论

Efficiently decoding Reed-Muller Codes From Random Errors

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第4期63卷 1954-1960页

作者： Saptharishi, Ramprasad Shpilka, Amir Volk, Ben Lee Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India Tel Aviv Univ Sch Comp Sci IL-39040 Tel Aviv Israel

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0, 1}(m). We denote this code by RM(r, m). The minimum distance of RM(r, m) is 2(m-r) and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n = 2(m)) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r = o(root m)), we can correct a random set of (1/2-o(1)) n errors with high probability. For high rate codes (of degree m - r for r = o(root m/log m)), we can correct roughly m(r/2) errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m - (2r + 2), m), for which the same erasure pattern can be corrected in RM(m - (r + 1), m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kotter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

关键词： Linear codes Reed-Muller codes decoding algorithms random errors

来源：评论

学校读者我要写书评

暂无评论

Joint carrier phase estimation and turbo decoding using bit carrier phase APP decoder

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2007年第10期55卷 1884-1894页

作者： Saroka, Amir Raphaeli, Dan Hebrew Univ Jerusalem Fac Comp Sci IL-91905 Jerusalem Israel Tel Aviv Univ Fac Engn Sch Elect Engn IL-69978 Tel Aviv Israel

In this paper, we present an algorithm for joint carrier phase estimation and turbo decoding for the case of rapidly varying carrier phase during the transmitted block. The proposed algorithm shows improved performance over previously proposed communication schemes, both coherent and noncoherent, for channels with additive white Gaussian noise and high carrier phase noise. The novel algorithm utilizes a modified. "two dimensional" bit carrier phase a posteriori probability (BCAPP) decoder containing additional states representing the received carrier phase. The BCAPP decoder calculates two extrinsic metrics: one representing the bit soft value and the other representing the received carrier phase probability density function approximation. A modified structure of the turbo code iterations is suggested, implementing separate propagation of the two metrics;between the BCAPP decoders. One additional attractive property of the suggested algorithm is its robustness against phase noise model mismatch.

关键词： decoding algorithms error correction codes non-coherent reception phase decoding

来源：评论

学校读者我要写书评

暂无评论

A Generalization Belief Propagation decoding Algorithm for Polar Codes Based on Particle Swarm Optimization

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2014年第1期2014卷 1-10页

作者： Zhang, Yingxian Liu, Aijun Pan, Xiaofei He, Shi Gong, Chao PLA Univ Sci & Technol Coll Commun Engn Key Lab Mil Satellite Commun Nanjing 210007 Jiangsu Peoples R China PLA Unit 75706 Guangzhou 510000 Guangdong Peoples R China

We propose a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes. Through the analysis of the existing BP decoding algorithm, we first introduce a probability modifying factor to each node of the BP decoder, so as to enhance the error correcting capacity of the decoding. Then, we generalize the BP decoding algorithm based on these modifying factors and drive the probability update equations for the proposed decoding. Based on the new probability update equations, we show the intrinsic relationship of the existing decoding algorithms. Finally, in order to achieve the best performance, we formulate an optimization problem to find the optimal probability modifying factors for the proposed decoding algorithm. Furthermore, a method based on the modified PSO algorithm is also introduced to solve that optimization problem. Numerical results show that the proposed generalization BP decoding algorithm achieves better performance than that of the existing BP decoding, which suggests the effectiveness of the proposed decoding algorithm.

关键词： decoding algorithms PARTICLE swarm optimization PROBABILITY theory NUMERICAL analysis PROBLEM solving

来源：评论

学校读者我要写书评

暂无评论

decoding Single Molecule Time Traces with Dynamic Disorder

引用

PLOS COMPUTATIONAL BIOLOGY 2016年第12期12卷 e1005286-e1005286页

作者： Hwang, Wonseok Lee, Il-Buem Hong, Seok-Cheol Hyeon, Changbong Korea Inst Adv Study Seoul South Korea Korea Univ Dept Phys Seoul South Korea

Single molecule time trajectories of biomolecules provide glimpses into complex folding landscapes that are difficult to visualize using conventional ensemble measurements. Recent experiments and theoretical analyses have highlighted dynamic disorder in certain classes of biomolecules, whose dynamic pattern of conformational transitions is affected by slower transition dynamics of internal state hidden in a low dimensional projection. A systematic means to analyze such data is, however, currently not well developed. Here we report a new algorithm D Variational Bayes-double chain Markov model (VB-DCMM) D to analyze single molecule time trajectories that display dynamic disorder. The proposed analysis employing VB-DCMM allows us to detect the presence of dynamic disorder, if any, in each trajectory, identify the number of internal states, and estimate transition rates between the internal states as well as the rates of conformational transition within each internal state. Applying VB-DCMM algorithm to single molecule FRET data of H-DNA in 100 mM-Na+ solution, followed by data clustering, we show that at least 6 kinetic paths linking 4 distinct internal states are required to correctly interpret the duplex-triplex transitions of H-DNA.

关键词： SINGLE molecules decoding algorithms BIOMOLECULES MARKOV chain Monte Carlo TRANSITION flow

来源：评论

学校读者我要写书评

暂无评论

A matrix based list decoding algorithm for linear codes over integer residue rings

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2021年 614卷 376-393页

作者： Napp, Diego Pinto, Raquel Sacikara, Elif Toste, Marisa Univ Alicante Dept Math Alicante Spain Univ Zurich Inst Math Zurich Switzerland Univ Aveiro Dept Math CIDMA Ctr Res & Dev Math & Applicat Aveiro Portugal CIDMA Ctr Res & Dev Math & Applicat Aveiro Portugal Polytech Inst Coimbra Super Sch Technol & Management Olveira Hosp Coimbra Portugal

In this paper we address the problem of list decoding of linear codes over an integer residue ring Z(q), where q is a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Z(pr), called the standard form, and the p-adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Z(pr). From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field p(r-1)Z(pr),This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. (C) 2020 Published by Elsevier Inc.

关键词： Finite rings Linear codes over finite rings Erasure channel decoding algorithms Matrix representations Parity-check matrix

来源：评论

学校读者我要写书评

暂无评论

decoding a class of Lee metric codes over a Galois ring

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2002年第4期48卷 966-975页

作者： Byrne, E Natl Univ Ireland Dept Math Maynooth Kildare Ireland

We investigate a class of Lee metric alternant codes with symbols in Z(p)(n), establishing a lower bound on the minimum Lee distance where certain restrictions are placed on the code parameters. Corresponding to this bound, we have devised a decoding algorithm which is implemented over a finite field. The algorithm proceeds by finding a Grobner basis of the module M of solutions to a key equation. We obtain a necessary characterization of the solution module by solving iteratively a linear sequence over a Galois ring and show that the particular solution sought by the decoder is minimal in M. The required solution can then be found in an appropriate Grobner basis of M.

关键词： alternant codes decoding algorithms Galois rings Grobner bases key equation Lee distance

来源：评论

学校读者我要写书评

暂无评论

Graph-based message-passing schedules for decoding LDPC codes

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2004年第12期52卷 2098-2105页

作者： Xiao, H Banihashemi, AH Carleton Univ Broadband Commun & Wireless Syst Ctr Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

In this paper, we study a wide range of graph-based message-passing schedules for iterative decoding of low-density parity-check (LDPC) codes. Using the Tanner graph (TG) of the code and for different nodes and edges of the graph, we relate the first iteration in which the corresponding messages deviate from their optimal value (corresponding to a cycle-free graph) to the girths and the lengths of the shortest closed walks in the graph. Using this result, we propose schedules, which are designed based on the distribution of girths and closed walks in the TG of the code, and categorize them as node based versus edge based, unidirectional versus bidirectional, and deterministic versus probabilistic. These schedules, in some cases, outperform the previously known. schedules, and in other cases, provide less complex alternatives with more or less the same performance. The performance/complexity tradeoff and the best choice of schedule appear to depend not only on the girth and closed-walk distributions of the TG, but also on the iterative decoding algorithm and channel characteristics. We examine the application of schedules to belief propagation (sum-product) over additive white Gaussian noise (AWGN) and Rayleigh fading channels, min-sum (max-sum) over an AWGN channel, and Gallager's algorithm A over a binary symmetric channel.

关键词： coding decoding algorithms iterative decoding low-density parity-check (LDPC) codes message-passing schedules Tanner graph (TG)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：